矩陣略圖與流數(shù)據(jù)機器學習

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

Zhi-hua

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

Zhi-hua

Zhou計算/存儲資源受限潛在的

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

突發(fā)/空閑

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

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

矩陣近似問題

矩陣近似問題

矩陣近似問題

矩陣近似問題

矩陣近似問題…

矩陣近似問題…

…

矩陣略圖(Matrix

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

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

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

矩陣略圖在流式機器學習上的研究和應用線性老虎機算法[Kuzborskijetal.,AISTATS’19][Chenetal.,IJCAI’20]

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

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

從頻率估計問題出發(fā)理解FD算法

CPUMemoryi1i1i2i5i9i1i1i9i7Nitemsi3頻率估計問題

CPUMemoryi1i1i2i5i9i1i1i9i3i7Nitems頻率估計問題

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

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

123456789頻率估計矩陣略圖123456789111…1234567895623

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

123456789頻率估計矩陣略圖123456789111…1234567895623

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

123456789頻率估計矩陣略圖123456789111…1234567895623

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

123456789頻率估計矩陣略圖123456789111…1234567895623

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

123456789頻率估計v.s.矩陣略圖頻率估計矩陣略圖123456789111…1234567895623

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

123456789頻率估計v.s.矩陣略圖頻率估計矩陣略圖123456789111…123456789563

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

123456789

256131111111

123456789頻率估計v.s.矩陣略圖頻率估計矩陣略圖123456789111…123456789563

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

123456789

14521111

123456789

頻率估計v.s.矩陣略圖頻率估計矩陣略圖123456789123456789111…123456789

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

FrequentDirections算法分析

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

報告提綱流數(shù)據(jù)計算與學習背景介紹FrequentDirections(FD)矩陣略圖算法簡介OurWorks滑動窗口上的最優(yōu)矩陣略圖算法矩陣略圖加速老虎機的通用框架總結與展望滑動窗口上的矩陣近似問題

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

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

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

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

滑動窗口上的最優(yōu)矩陣略圖算法問題：滑動窗口上的矩陣略圖的最優(yōu)空間復雜度為多少？

LM-FDDi-FD

DS-FDSlidingwindow

FDFull

Stream

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

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

滑動窗口：頻率估計v.s.矩陣略圖滑動窗口上的頻率估計問題i1i1i2i5i9i1i1i9i3i7N=4

滑動窗口上的矩陣略圖問題

滑動窗口：頻率估計v.s.矩陣略圖滑動窗口上的頻率估計問題滑動窗口上的矩陣略圖問題i1i1i2i5i9i1i1i9i3i7N=4

滑動窗口：頻率估計v.s.矩陣略圖滑動窗口上的頻率估計問題滑動窗口上的矩陣略圖問題i1i1i2i5i9i1i1i9i3i7N=4

滑動窗口：頻率估計v.s.矩陣略圖滑動窗口上的頻率估計問題滑動窗口上的矩陣略圖問題i1i1i2i5i9i1i1i9i3i7N=4

滑動窗口：頻率估計v.s.矩陣略圖滑動窗口上的頻率估計問題滑動窗口上的矩陣略圖問題i1i1i2i5i9i1i1i9i3i7N=4

滑動窗口：頻率估計v.s.矩陣略圖滑動窗口上的頻率估計問題滑動窗口上的矩陣略圖問題i1i1i2i5i9i1i1i9i3i7N=4

滑動窗口：MGv.s.FD123456789頻率估計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.頻率估計SlidingWindowMG[PODS2006]矩陣略圖滑動窗口：MGv.s.FD

12345678948182537

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

滑動窗口：MGv.s.FD

12345678948182537

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

滑動窗口：MGv.s.FD

25123456789374818

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

滑動窗口：MGv.s.FD

25123456789374818

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

滑動窗口：MGv.s.FD

25123456789374818

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

滑動窗口：MGv.s.FD

25123456789374818

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

滑動窗口：MGv.s.FD

25123456789374818

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

滑動窗口：MGv.s.FD

25123456789374818

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

滑動窗口：MGv.s.FD

2512345678937481855

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

滑動窗口：MGv.s.FD

25123456789374855

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

滑動窗口：MGv.s.FD

Time頻率估計SlidingWindowMG[PODS2006]矩陣略圖OurMethod

[VLDB2024]123456789

TimeHanyanYin,DongxieWen,JiajunLi,ZheweiWei,XiaoZhang,ZengfengHuang,FeifeiLi.OptimalMatrixSketchingoverSlidingWindows.VLDB2024滑動窗口：MGv.s.FD

Time123456789

Time

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

[VLDB2024]

Time123456789

Time

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

[VLDB2024]

Time123456789

Time

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

[VLDB2024]

Time123456789

Time

=

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

[VLDB2024]

Time123456789

Time

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

[VLDB2024]非歸一化向量&

Time-basedModel

Level0Level1Level2

Time......

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

…

…

SlidingWindow1SlidingWindow2

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

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

ScanningDataSketchQueryRLS

Estimate

獎勵向量數(shù)據(jù)矩陣2011-2017