矩陣略圖與流數(shù)據(jù)機(jī)器學(xué)習(xí)

矩陣略圖與流數(shù)據(jù)機(jī)器學(xué)習(xí)報(bào)告提綱流數(shù)據(jù)計(jì)算與學(xué)習(xí)背景介紹FrequentDirections(FD)矩陣略圖算法簡(jiǎn)介OurWorks滑動(dòng)窗口上的最優(yōu)矩陣略圖算法矩陣略圖加速老虎機(jī)的通用框架總結(jié)與展望數(shù)據(jù)流模型數(shù)據(jù)流是一個(gè)由海量數(shù)據(jù)組成的數(shù)據(jù)序列SinglePass:每個(gè)數(shù)據(jù)最多訪問(wèn)一次SmallSpace:存儲(chǔ)空間非常小Smalltime:更新(插入刪除)速度快CPU內(nèi)存：數(shù)據(jù)摘要回答近似查詢(xún)頻繁項(xiàng)有哪些/數(shù)據(jù)分布是什么/Top-K是什么？流式機(jī)器學(xué)習(xí)StreamEfficientLearning(LearnabilitywithTime-SharingComputationalResourceConcerns),

Zhi-hua

Zhou傳統(tǒng)機(jī)器學(xué)習(xí)流式機(jī)器學(xué)習(xí)數(shù)據(jù)特性基于預(yù)先給定的有限數(shù)據(jù)集處理潛在無(wú)限且不斷變化的數(shù)據(jù)流數(shù)據(jù)大小數(shù)據(jù)集大小已知，數(shù)據(jù)集包含所有數(shù)據(jù)數(shù)據(jù)流可能無(wú)限大，需要及時(shí)處理數(shù)據(jù)變化數(shù)據(jù)特征在數(shù)據(jù)集中已隱含，假設(shè)不變數(shù)據(jù)特征可能隨時(shí)間變化計(jì)算/存儲(chǔ)資源假設(shè)有足夠的資源處理所有數(shù)據(jù)有限的資源，需要及時(shí)處理數(shù)據(jù)學(xué)習(xí)策略通常采用離線學(xué)習(xí)策略需要近似的略圖算法和動(dòng)態(tài)調(diào)整策略Z.-H.Zhou,“LearnabilitywithTime-SharingComputationalResourceConcerns,”Aug.24,2024,arXiv:arXiv:2305.02217.Accessed:Oct.08,2024.[Online].Available:/abs/2305.02217流式機(jī)器學(xué)習(xí)StreamEfficientLearning(LearnabilitywithTime-SharingComputationalResourceConcerns),

Zhi-hua

Zhou計(jì)算/存儲(chǔ)資源受限潛在的

無(wú)限數(shù)據(jù)流流量變化

突發(fā)/空閑

分布變化流學(xué)習(xí)模型調(diào)度策略高效算子流式高效機(jī)器學(xué)習(xí)設(shè)計(jì)高效吞吐能力的流數(shù)據(jù)算法刻畫(huà)誤差與計(jì)算/存儲(chǔ)復(fù)雜度之間的理論關(guān)系依據(jù)數(shù)據(jù)流變化動(dòng)態(tài)分析需要使用的流數(shù)據(jù)算子自適應(yīng)地實(shí)現(xiàn)計(jì)算資源與近似精度的折中ML4Sketch&

Sketch4ML機(jī)器學(xué)習(xí)優(yōu)化的略圖算法(ML4Sketch)基于學(xué)習(xí)的頻率估計(jì)[Hsuetal.2019]基于學(xué)習(xí)的低秩近似[Indyketal.2019]基于學(xué)習(xí)的分位數(shù)估計(jì)[Schieferetal.2023]基于學(xué)習(xí)的子圖計(jì)數(shù)估計(jì)[Zhaoetal.2023]略圖算法優(yōu)化的機(jī)器學(xué)習(xí)(Sketch4ML)在線學(xué)習(xí)線性老虎機(jī)算法[Kuzborskijetal.2019,Yuetal.2017]在線梯度下降[Luoetal.2016]核學(xué)習(xí)增量略圖近似核矩陣[Zhangetal.2019]圖機(jī)器學(xué)習(xí)動(dòng)態(tài)圖上的異常檢測(cè)[Bhatiaetal.2023]本次報(bào)告聚焦數(shù)據(jù)流上的矩陣略圖算法及其在流式機(jī)器學(xué)習(xí)上的應(yīng)用矩陣近似問(wèn)題

矩陣近似問(wèn)題

矩陣近似問(wèn)題

矩陣近似問(wèn)題

矩陣近似問(wèn)題

矩陣近似問(wèn)題…

矩陣近似問(wèn)題…

…

矩陣略圖(Matrix

Sketch)相關(guān)工作FrequentDirections(FD)Sketch[Liberty,KDD’13,BestPaper]

LM-FD&DI-FDSketch[Weietal.,SIGMOD’16]

SparseFDSketch[Huang,ICML’18,BestPaperrunnerup]滑動(dòng)窗口上的矩陣略圖算法數(shù)據(jù)流上的矩陣略圖算法稀疏向量流上的矩陣略圖算法可持久化的矩陣略圖算法FDATTP&FDBITPSketch[Shietal.,SIGMOD’21]滑動(dòng)窗口上的最優(yōu)矩陣略圖算法DS-FDSketch[Yinetal.,VLDB’24,BestPaperNomination]

矩陣略圖在流式機(jī)器學(xué)習(xí)上的研究和應(yīng)用線性老虎機(jī)算法[Kuzborskijetal.,AISTATS’19][Chenetal.,IJCAI’20]

在線核學(xué)習(xí)[Zhangetal.,ICML’19]圖機(jī)器學(xué)習(xí)[Bhatiaetal.,KDD’23]報(bào)告提綱流數(shù)據(jù)計(jì)算與學(xué)習(xí)背景介紹FrequentDirections(FD)矩陣略圖算法簡(jiǎn)介OurWorks滑動(dòng)窗口上的最優(yōu)矩陣略圖算法矩陣略圖加速老虎機(jī)的通用框架總結(jié)與展望FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

從頻率估計(jì)問(wèn)題出發(fā)理解FD算法

CPUMemoryi1i1i2i5i9i1i1i9i7Nitemsi3頻率估計(jì)問(wèn)題

CPUMemoryi1i1i2i5i9i1i1i9i3i7Nitems頻率估計(jì)問(wèn)題

CPUMemoryi1i1i2i5i9i1i1i9i3i7NitemsMisra-Gries摘要（1982）

123456789

Demaine,Lopez-Ortiz與Munro(2002)Karp,Shenker與Papadimitriou(2003)

123456789

Demaine,Lopez-Ortiz與Munro(2002)Karp,Shenker與Papadimitriou(2003)Misra-Gries摘要（1982）

123456789Demaine,Lopez-Ortiz與Munro(2002)Karp,Shenker與Papadimitriou(2003)

Misra-Gries摘要（1982）

123456789Demaine,Lopez-Ortiz與Munro(2002)Karp,Shenker與Papadimitriou(2003)

Misra-Gries摘要（1982）

123456789Demaine,Lopez-Ortiz與Munro(2002)Karp,Shenker與Papadimitriou(2003)

Misra-Gries摘要（1982）

123456789Demaine,Lopez-Ortiz與Munro(2002)Karp,Shenker與Papadimitriou(2003)

Misra-Gries摘要（1982）

123456789Demaine,Lopez-Ortiz與Munro(2002)Karp,Shenker與Papadimitriou(2003)

Misra-Gries摘要（1982）

123456789Demaine,Lopez-Ortiz與Munro(2002)Karp,Shenker與Papadimitriou(2003)

Misra-Gries摘要（1982）

Misra-Gries算法分析

123456789

111…1234567895613

頻率估計(jì)可視為一種特殊的矩陣略圖頻率估計(jì)矩陣略圖頻率估計(jì)v.s.矩陣略圖

123456789頻率估計(jì)矩陣略圖123456789111…1234567895623

頻率估計(jì)可視為一種特殊的矩陣略圖1頻率估計(jì)v.s.矩陣略圖

123456789頻率估計(jì)矩陣略圖123456789111…1234567895623

頻率估計(jì)可視為一種特殊的矩陣略圖1頻率估計(jì)v.s.矩陣略圖

123456789頻率估計(jì)矩陣略圖123456789111…1234567895623

頻率估計(jì)可視為一種特殊的矩陣略圖111頻率估計(jì)v.s.矩陣略圖

123456789頻率估計(jì)矩陣略圖123456789111…1234567895623

頻率估計(jì)可視為一種特殊的矩陣略圖111頻率估計(jì)v.s.矩陣略圖

123456789頻率估計(jì)v.s.矩陣略圖頻率估計(jì)矩陣略圖123456789111…1234567895623

頻率估計(jì)可視為一種特殊的矩陣略圖11111

123456789頻率估計(jì)v.s.矩陣略圖頻率估計(jì)矩陣略圖123456789111…123456789563

頻率估計(jì)可視為一種特殊的矩陣略圖111112

123456789

256131111111

123456789頻率估計(jì)v.s.矩陣略圖頻率估計(jì)矩陣略圖123456789111…123456789563

頻率估計(jì)可視為一種特殊的矩陣略圖111112

123456789

14521111

123456789

頻率估計(jì)v.s.矩陣略圖頻率估計(jì)矩陣略圖123456789123456789111…123456789

頻率估計(jì)可視為一種特殊的矩陣略圖1114512

FrequentDirections算法分析

E.Liberty,“Simpleanddeterministicmatrixsketching,”inProceedingsofthe19thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining,ChicagoIllinoisUSA:ACM,Aug.2013,pp.581–588.

報(bào)告提綱流數(shù)據(jù)計(jì)算與學(xué)習(xí)背景介紹FrequentDirections(FD)矩陣略圖算法簡(jiǎn)介OurWorks滑動(dòng)窗口上的最優(yōu)矩陣略圖算法矩陣略圖加速老虎機(jī)的通用框架總結(jié)與展望滑動(dòng)窗口上的矩陣近似問(wèn)題

流數(shù)據(jù)模型vs.滑動(dòng)窗口模型滑動(dòng)窗口上的矩陣略圖問(wèn)題流數(shù)據(jù)上的矩陣略圖問(wèn)題

流數(shù)據(jù)模型vs.滑動(dòng)窗口模型滑動(dòng)窗口上的矩陣略圖問(wèn)題流數(shù)據(jù)上的矩陣略圖問(wèn)題

流數(shù)據(jù)模型vs.滑動(dòng)窗口模型滑動(dòng)窗口上的矩陣略圖問(wèn)題流數(shù)據(jù)上的矩陣略圖問(wèn)題

流數(shù)據(jù)模型vs.滑動(dòng)窗口模型滑動(dòng)窗口上的矩陣略圖問(wèn)題流數(shù)據(jù)上的矩陣略圖問(wèn)題

滑動(dòng)窗口上的最優(yōu)矩陣略圖算法問(wèn)題：滑動(dòng)窗口上的矩陣略圖的最優(yōu)空間復(fù)雜度為多少？

LM-FDDi-FD

DS-FDSlidingwindow

FDFull

Stream

2016-2016OurworkVLDB‘24BestPaperNomination2013KDD‘13BestPaper滑動(dòng)窗口算法數(shù)據(jù)流算法頻率估計(jì)問(wèn)題矩陣略圖問(wèn)題思路：與頻率估計(jì)問(wèn)題建立聯(lián)系！思路：與頻率估計(jì)問(wèn)題建立聯(lián)系！滑動(dòng)窗口算法

數(shù)據(jù)流算法頻率估計(jì)問(wèn)題矩陣略圖問(wèn)題滑動(dòng)窗口：頻率估計(jì)v.s.矩陣略圖滑動(dòng)窗口上的頻率估計(jì)問(wèn)題滑動(dòng)窗口上的矩陣略圖問(wèn)題i1i1i2i5i9i1i1i9i3i7N=4

滑動(dòng)窗口：頻率估計(jì)v.s.矩陣略圖滑動(dòng)窗口上的頻率估計(jì)問(wèn)題i1i1i2i5i9i1i1i9i3i7N=4

滑動(dòng)窗口上的矩陣略圖問(wèn)題

滑動(dòng)窗口：頻率估計(jì)v.s.矩陣略圖滑動(dòng)窗口上的頻率估計(jì)問(wèn)題滑動(dòng)窗口上的矩陣略圖問(wèn)題i1i1i2i5i9i1i1i9i3i7N=4

滑動(dòng)窗口：頻率估計(jì)v.s.矩陣略圖滑動(dòng)窗口上的頻率估計(jì)問(wèn)題滑動(dòng)窗口上的矩陣略圖問(wèn)題i1i1i2i5i9i1i1i9i3i7N=4

滑動(dòng)窗口：頻率估計(jì)v.s.矩陣略圖滑動(dòng)窗口上的頻率估計(jì)問(wèn)題滑動(dòng)窗口上的矩陣略圖問(wèn)題i1i1i2i5i9i1i1i9i3i7N=4

滑動(dòng)窗口：頻率估計(jì)v.s.矩陣略圖滑動(dòng)窗口上的頻率估計(jì)問(wèn)題滑動(dòng)窗口上的矩陣略圖問(wèn)題i1i1i2i5i9i1i1i9i3i7N=4

滑動(dòng)窗口：頻率估計(jì)v.s.矩陣略圖滑動(dòng)窗口上的頻率估計(jì)問(wèn)題滑動(dòng)窗口上的矩陣略圖問(wèn)題i1i1i2i5i9i1i1i9i3i7N=4

滑動(dòng)窗口：MGv.s.FD123456789頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖182537

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.123456789182537

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖滑動(dòng)窗口：MGv.s.FD

12345678948182537

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

12345678948182537

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

25123456789374818

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

25123456789374818

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

25123456789374818

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

25123456789374818

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

25123456789374818

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

25123456789374818

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

2512345678937481855

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

25123456789374855

L.K.LeeandH.F.Ting,“Asimplerandmoreefficientdeterministicschemeforfindingfrequentitemsoverslidingwindows,”inProceedingsofthetwenty-fifthACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems,Jun.2006,pp.290–297.頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖

滑動(dòng)窗口：MGv.s.FD

Time頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖OurMethod

[VLDB2024]123456789

TimeHanyanYin,DongxieWen,JiajunLi,ZheweiWei,XiaoZhang,ZengfengHuang,FeifeiLi.OptimalMatrixSketchingoverSlidingWindows.VLDB2024滑動(dòng)窗口：MGv.s.FD

Time123456789

Time

HanyanYin,DongxieWen,JiajunLi,ZheweiWei,XiaoZhang,ZengfengHuang,FeifeiLi.OptimalMatrixSketchingoverSlidingWindows.VLDB2024滑動(dòng)窗口：MGv.s.FD頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖OurMethod

[VLDB2024]

Time123456789

Time

HanyanYin,DongxieWen,JiajunLi,ZheweiWei,XiaoZhang,ZengfengHuang,FeifeiLi.OptimalMatrixSketchingoverSlidingWindows.VLDB2024滑動(dòng)窗口：MGv.s.FD頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖OurMethod

[VLDB2024]

Time123456789

Time

=HanyanYin,DongxieWen,JiajunLi,ZheweiWei,XiaoZhang,ZengfengHuang,FeifeiLi.OptimalMatrixSketchingoverSlidingWindows.VLDB2024滑動(dòng)窗口：MGv.s.FD頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖OurMethod

[VLDB2024]

Time123456789

Time

=

HanyanYin,DongxieWen,JiajunLi,ZheweiWei,XiaoZhang,ZengfengHuang,FeifeiLi.OptimalMatrixSketchingoverSlidingWindows.VLDB2024滑動(dòng)窗口：MGv.s.FD頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖OurMethod

[VLDB2024]

Time123456789

Time

HanyanYin,DongxieWen,JiajunLi,ZheweiWei,XiaoZhang,ZengfengHuang,FeifeiLi.OptimalMatrixSketchingoverSlidingWindows.VLDB2024滑動(dòng)窗口：MGv.s.FD頻率估計(jì)SlidingWindowMG[PODS2006]矩陣略圖OurMethod

[VLDB2024]非歸一化向量&

Time-basedModel

Level0Level1Level2

Time......

...CurrentWindowExpiredSnapshotDroppedSnapshotSavedSnapshotOptimalHanyanYin,DongxieWen,JiajunLi,ZheweiWei,XiaoZhang,ZengfengHuang,FeifeiLi.OptimalMatrixSketchingoverSlidingWindows.VLDB2024最優(yōu)性證明

…

…

SlidingWindow1SlidingWindow2

實(shí)驗(yàn)結(jié)果相比于其他算法，使用相同空間開(kāi)銷(xiāo)可達(dá)成更好的估計(jì)質(zhì)量實(shí)驗(yàn)中算法的實(shí)際誤差從未超出理論誤差界報(bào)告提綱流數(shù)據(jù)計(jì)算與學(xué)習(xí)背景介紹FrequentDirections(FD)矩陣略圖算法簡(jiǎn)介OurWorks滑動(dòng)窗口上的最優(yōu)矩陣略圖算法矩陣略圖加速老虎機(jī)的通用框架總結(jié)與展望線性老虎機(jī)

智能體環(huán)境一組上下文（contexts）決策反饋基于矩陣略圖加速老虎機(jī)

ScanningDataSketchQueryRLS

Estimate

獎(jiǎng)勵(lì)向量數(shù)據(jù)矩陣2011-2017