首页 > 其他分享 >Frequent Directions

Frequent Directions

时间:2024-11-06 15:41:31浏览次数:2  
标签:le ell counter FD 奇异 Directions hat Frequent

目录

Ghashami M., Liberty E., Phillips J. M. and Woodruff D. P. Frequent directions : Simple and deterministic matrix sketching. 2015.

Yin H., Wen D., Li J., Wei Z., Zhang X., Huang Z. and Li F. Optimal matrix sketching over sliding windows. VLDB, 2024.

通过魏老师的分享找了这些论文看了一下, 感觉之后可能会用到.

Frequent Directions

  • FD 的任务是, 希望维护一个 sketch matrix \(B \in \mathbb{R}^{\ell \times d}\) 使得 (\(A \in \mathbb{R}^{n \times d}\)),

    \[\|A^T A - B^T B \|_2, \quad \|A - \pi_{B_k}(A) \|_F^2, \forall k < \ell \]

    这几个误差都尽可能小, 其中

    \[\pi_{B_k}(A) = A V_kV_k^T, \]

    \(V_k\) 是 \(B = U\Lambda V^T\) 的 top-\(k\) 奇异值所对应的右奇异向量. 换言之, 我们通过维护 \(\ell \ll n\) 便保存了 \(A\) 中的大部分信息.

  • 这个问题比较有意思的点在于, 如何处理, \(A\) 通过一行一行的形式得到, 然后我们动态地维护 \(B\) (否则这个问题就有一般方法了).

  • FD 启发自一个非常经典的问题: 频率估计问题.

    • 假设, 我们有 \(A = \{a_1, \cdots, a_n\}\), 其中 \(a _i \in \{1, \ldots, d\}\). 我们会一个一个地接收到其中的元素, 问题是如何动态估计每个元素出现的频率:

    \[\hat{f}_j \rightarrow f_j = |\{a_i \in A | a_i = j\}|. \]

    • Misra-Gries 算法是频率估计的一个最优算法:

      1. 维护一个长度为 \(\ell\) 的 counters;
      2. 新来一个元素 \(a\): I) 若已经有 counter 在计数 \(a\) 则, 该 counter 加一; II) 倘若任有 counter 剩余 (即 counter 计数为 0), 则选择其一用于计数 \(a\); III) 倘若没有 counter 剩余, 则所有 counter 递减直到有其中一个 counter 为 0, 将此 counter 用于计数 \(a\).
    • 容易发现, 由于每次'递减'操作减去的频率为'\(\ell\)', 所以最多有 \(n / \ell\) 次这种递减操作. 换言之:

      \[0 \le f_j - \hat{f}_j \le n / \ell, \forall j. \]

      于是我们就得到了一个还算可以的频率估计, 实际上, 这个估计是最优的.

  • 我们可以把这个推广到矩阵的形式. 假设 \(A \in \mathbb{R}^{n \times d}\) 的每一行为 \(\{e_j: j=1,2,\ldots, d\}\), 其中 \(e_j\) 表示第 \(j\) 个元素为 1, 其余元素为 0 的向量. 此时, 我们有:

    \[f_j = \|A e_j\|^2. \]

    我们可以令 \(B\) 的第 \(j\) 行为: \(\hat{f}_j^{1/2} e_j\), 则有

    \[\|Be_j\|^2 = \hat{f}_j, \]

    进一步地:

    \[\|A^T A - B^TB \|_2 = \max_j |f_j - \hat{f}_j| \le \|A\|_F^2 / (\ell - k). \]

  • FD 的最终算法就是有这样的一个'减'的操作:

  • 具体操作就是, 新来一行 \(a\) 后, 拼接在最后, 然后进行奇异值分解, 然后所有的奇异值减去最小的奇异值, 此时

    \[\sqrt{\Sigma^2 - \delta I_{\ell}} V^T \]

    的最后一行一定为 0. 这相当于我们空出来了一个 'counter'.

  • FD 可以进一步加速:

  • 此时, 减去的是排中间的奇异值, 相当于我们会空出一半的 'counters'.

  • 最后的 bound 请参考原文.

Frequent Directions over Slidding Windows

  • 有些时候, 我们并不希望 \(B\) 去保存过去所有的信息, 而是最近的 N 行, 即逼近 \(A_W = A_{T-N, T} \in \mathbb{R}^{N \times d}\) 的信息 (\(T\) 表示当前的时刻).

  • 其实, 这个算法也是启发自基于滑动窗口的频率估计问题:

    1. 给定阈值 \(\theta = N / \ell\);
    2. 按照普通的方式统计每个元素的频率, 此时时刻 \(T\) 来了一个新的元素 \(a\), 按照之前的 MG 的方式统计.
    3. 之后, 如果 \(a\) 的计数 \(\ge \theta\), 则将其归零, 并将 \((a, T)\) 加入一个列表 \(S\) 中.
    4. 检查 \(S\) 中的时间, 如果时间不在窗口内, 则舍弃.
  • 最后, 我们可以以 \(S\) 中的记录以及 counters 中的记录作为频率, 其余不在其中的频率记为 \(0\). 容易发现,

    • 对于 \(\hat{f}_j = 0\) 的:

      \[0 \le f_j - \hat{f}_j \le N / \ell. \]

    • 对于 \(\hat{f}_j \not = 0\) 的, 由于舍弃的部分 (就是还在 counters 中的) 不会超过 \(N / \ell\), 所以也有

      \[0 \le f_j - \hat{f}_j \le N / \ell. \]

注: 我不太了解这个算法, 感觉应该是这样的.

  • 所以 FD over lisding windows 的算法也是类似的:

  • 和普通的 FD 主要有两点不同:

    1. 需要维护两个额外的列表 \(S, S'\), 用于维护超出阈值 \(\theta\) 的奇异向量;
    2. 每次经过普通的 FD 操作后, 如果首奇异值超过 \(\theta\), 对应的频谱就被剔除了.
  • 此外, 每次更新还需要检查, 保存在 \(S, S'\) 中的奇异向量是否超过了窗口时间.

代码

[official-code]

标签:le,ell,counter,FD,奇异,Directions,hat,Frequent
From: https://www.cnblogs.com/MTandHJ/p/18530353

相关文章

  • [nltoSql]A Survey on Text-to-SQL Parsing: Concepts, Methods, and Future Directio
    全文总结这篇论文题为《ASurveyonText-to-SQLParsing:Concepts,Methods,andFutureDirections》。研究背景背景介绍: 这篇文章的研究背景是文本到SQL解析任务的重要性和挑战性。文本到SQL解析的目标是将自然语言(NL)问题转换为结构化查询语言(SQL),以便在关系数据库上执......
  • Federated Learning Challenges, Methods, and Future Directions
    本文讨论了联邦学习的独特特征和挑战,提供了当前方法的广泛概述,并概述了与广泛的研究社区相关的未来工作的几个方向。背景:现代分布式网络中的设备(如移动电话、可穿戴设备和自动驾驶汽车等)每天会产生大量数据,由于这些设备的计算能力不断增强,以及对传输私人信息的担忧,在本地......
  • Speaking-Asking for or giving directions
    1)onthesecondfloor2)taketheelevatorontheelevator 3)whenyougetoffthe elevator,turnleft4)attheendofthecorridorontherightside5)turnrightatthecornerandgostraightahead.It'sonyourright,nexttothebakeryahead......
  • [题解]UVA11235 Frequent values
    https://www.luogu.com.cn/problem/UVA11235没看到多测调了半天每组数据给定\(n,q\)。接下来给出一个长度为\(n\)的不降序列\(A\)。接下来\(q\)次询问,每次询问给定\(l,r\),求\(A_{l\simr}\)中出现最多的那个数出现了多少次。\(1\len,q\le10^5\)。序列不降,意味着一个数在序......
  • Redis精通系列——LFU算法详述(Least Frequently Used - 最不经常使用)
    转:Redis精通系列——LFU算法详述(LeastFrequentlyUsed-最不经常使用)  ......
  • Frequently CRSD Appear Unresponsive/Intermediate/Offline Status (Doc ID 2352557.
    事件背景描述:环境:Linux/Oracle12.2.0.1.0/RAC问题:数据库监听无法连接,集群异常问题处理过程:1.登录数据库查看相关状态,如下,发现crsd进程状态为cleaning2.发现crsd进程异常后,判断可能是网络层面问题,通过查杀gipc进程集群并未恢复正常3.联系主机工程师上线排查网络问题,网络工程师排......
  • 【脚本】GutcOJ Helper 发布页 - FReQuenter 的博客园
    地址:https://www.cnblogs.com/FReQuenter5156/p/GutcOJ-Helper.html/GutcOJHelper基于油猴,不知道什么是油猴请自行百度适配GuctOJ3.0和2.0版本。经由NFLSOJHelper改编而来。NFLSOJHelper发布页:http://www.nfls.com.cn:20035/article/1197更新日志:https://www.luog......
  • 347. Top K Frequent Elements [Medium]
    347.TopKFrequentElementsGivenanintegerarraynumsandanintegerk,returnthekmostfrequentelements.Youmayreturntheanswerinanyorder.Constra......
  • LeetCode347. Top K Frequent Elements
    题意给一个序列,输出其前K个出现频次的数字方法优先队列代码classSolution{public:structnode{intval;//值intcnt;//出现次数......
  • ZOJ 2132 the most frequent number
    DescriptionSeven(actuallysix)problemsmaybesomewhatfewforacontest.ButIamreallyunabletodeviseanotherproblemrelatedtoFantasyGameSeries.......