矩阵略图与流数据机器学习

矩阵略图与流数据机器学习报告提纲流数据计算与学习背景介绍FrequentDirections(FD)矩阵略图算法简介OurWorks滑动窗口上的最优矩阵略图算法矩阵略图加速老虎机的通用框架总结与展望数据流模型数据流是一个由海量数据组成的数据序列SinglePass:每个数据最多访问一次SmallSpace:存储空间非常小Smalltime:更新(插入删除)速度快CPU内存：数据摘要回答近似查询频繁项有哪些/数据分布是什么/Top-K是什么？流式机器学习StreamEfficientLearning(LearnabilitywithTime-SharingComputationalResourceConcerns),

Zhi-hua

Zhou传统机器学习流式机器学习数据特性基于预先给定的有限数据集处理潜在无限且不断变化的数据流数据大小数据集大小已知，数据集包含所有数据数据流可能无限大，需要及时处理数据变化数据特征在数据集中已隐含，假设不变数据特征可能随时间变化计算/存储资源假设有足够的资源处理所有数据有限的资源，需要及时处理数据学习策略通常采用离线学习策略需要近似的略图算法和动态调整策略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计算/存储资源受限潜在的

无限数据流流量变化

突发/空闲

分布变化流学习模型调度策略高效算子流式高效机器学习设计高效吞吐能力的流数据算法刻画误差与计算/存储复杂度之间的理论关系依据数据流变化动态分析需要使用的流数据算子自适应地实现计算资源与近似精度的折中ML4Sketch&

Sketch4ML机器学习优化的略图算法(ML4Sketch)基于学习的频率估计[Hsuetal.2019]基于学习的低秩近似[Indyketal.2019]基于学习的分位数估计[Schieferetal.2023]基于学习的子图计数估计[Zhaoetal.2023]略图算法优化的机器学习(Sketch4ML)在线学习线性老虎机算法[Kuzborskijetal.2019,Yuetal.2017]在线梯度下降[Luoetal.2016]核学习增量略图近似核矩阵[Zhangetal.2019]图机器学习动态图上的异常检测[Bhatiaetal.2023]本次报告聚焦数据流上的矩阵略图算法及其在流式机器学习上的应用矩阵近似问题

矩阵近似问题

矩阵近似问题

矩阵近似问题

矩阵近似问题

矩阵近似问题…

矩阵近似问题…

…

矩阵略图(Matrix

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

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

SparseFDSketch[Huang,ICML’18,BestPaperrunnerup]滑动窗口上的矩阵略图算法数据流上的矩阵略图算法稀疏向量流上的矩阵略图算法可持久化的矩阵略图算法FDATTP&FDBITPSketch[Shietal.,SIGMOD’21]滑动窗口上的最优矩阵略图算法DS-FDSketch[Yinetal.,VLDB’24,BestPaperNomination]

矩阵略图在流式机器学习上的研究和应用线性老虎机算法[Kuzborskijetal.,AISTATS’19][Chenetal.,IJCAI’20]

在线核学习[Zhangetal.,ICML’19]图机器学习[Bhatiaetal.,KDD’23]报告提纲流数据计算与学习背景介绍FrequentDirections(FD)矩阵略图算法简介OurWorks滑动窗口上的最优矩阵略图算法矩阵略图加速老虎机的通用框架总结与展望FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

FD算法

从频率估计问题出发理解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.

报告提纲流数据计算与学习背景介绍FrequentDirections(FD)矩阵略图算法简介OurWorks滑动窗口上的最优矩阵略图算法矩阵略图加速老虎机的通用框架总结与展望滑动窗口上的矩阵近似问题

流数据模型vs.滑动窗口模型滑动窗口上的矩阵略图问题流数据上的矩阵略图问题

流数据模型vs.滑动窗口模型滑动窗口上的矩阵略图问题流数据上的矩阵略图问题

流数据模型vs.滑动窗口模型滑动窗口上的矩阵略图问题流数据上的矩阵略图问题

流数据模型vs.滑动窗口模型滑动窗口上的矩阵略图问题流数据上的矩阵略图问题

滑动窗口上的最优矩阵略图算法问题：滑动窗口上的矩阵略图的最优空间复杂度为多少？

LM-FDDi-FD

DS-FDSlidingwindow

FDFull

Stream

2016-2016OurworkVLDB‘24BestPaperNomination2013KDD‘13BestPaper滑动窗口算法数据流算法频率估计问题矩阵略图问题思路：与频率估计问题建立联系！思路：与频率估计问题建立联系！滑动窗口算法

数据流算法频率估计问题矩阵略图问题滑动窗口：频率估计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最优性证明

…

…

SlidingWindow1SlidingWindow2

实验结果相比于其他算法，使用相同空间开销可达成更好的估计质量实验中算法的实际误差从未超出理论误差界报告提纲流数据计算与学习背景介绍FrequentDirections(FD)矩阵略图算法简介OurWorks滑动窗口上的最优矩阵略图算法矩阵略图加速老虎机的通用框架总结与展望线性老虎机

智能体环境一组上下文（contexts）决策反馈基于矩阵略图加速老虎机

ScanningDataSketchQueryRLS

Estimate

奖励向量数据矩阵2011-2017