随机算法总结

Count-min Sketch

这是一种，估计出现次数的数据结构，适用于数据流（强在线），不同的元素数不多的情况。

基本思想是一个哈希表可以估计某个值的出现的次数，但是会估多，因此多个哈希取最小值即可。这里的哈希要取均匀哈希才能保证理论复杂度的正确性。

详见 「随机算法专题」Count-min Sketch 入门。

Karp-Rabin Hash

简单的字符串哈希：$h(s) \triangleq \sum_{i = 1}^{|s|} s_ix^{|s| - i}$。区间哈希：

$$h(s[l, r]) = h(s[1, r]) - h(s[1, l-1])x^{r-l+1}$$

二维的情况：$h(a_{n\times m})\triangleq \sum_{i = 1}^{n}\sum_{j = 1}^m a_{ij}x^{n - i}y^{n - j}$。矩阵哈希（差分）：

$$h(a[l_1, r_1][l_2, r_2]) = [h(a[1, r_1][1, r_2]) - h(a[1, r_1][1, l_2 - 1])y^{r_2 - l_2 + 1}]\\ -[h(a[1, l_1-1][1, r_2]) - h(a[1, l_1-1][1, l_2 - 1])y^{r_2 - l_2 + 1}]x^{r_1 - l_1 + 1}$$

Min-Hash

估计两个集合（这里考虑整数集）的相似度，可以使用交并比来描述：$J(A, B) = \frac{|A\cap B|}{|A\cup B|}$¹。

同样是考虑一个数据流的背景，每个集合只能遍历一次（预处理），然后我们若干次询问两个集合的相似度。

考虑一个均匀随机哈希$h$。那么$J(A, B) = J(h(A), h(B)) = E_x[x\in h(A)\cup h(B)]$。我们的大致思路是构造$T$个不同的哈希$h$，每次随机一个$x$，判断是否$x\in h(A) \cup h(B)$，然后取平均值。

考虑每次随机的$x = \min h(A \cup B)$。显然$x\in h(A) \cup h(B)\iff x = \min h(A) = \min h(B)$。这样的$x$由于每个哈希函数$h$不同的随机性，可以看成是随机的。

Sim-Hash

估计两个高维向量的相似度，可以考虑估计他们的夹角$\theta(x, y)$²。

考虑一个高维随机高斯向量（每一位高斯分布，然后单位化）$w$，那么$E[\mathbf{1}_{(x, w)\ge 0} \oplus \mathbf{1}_{(y, w)\ge 0}] = \frac{\theta(x, y)}{\pi}$。

设$h(x, w) = \mathbf{1}_{(x, w)\ge 0}$，取$T$个随机的高斯向量$w_1, \ldots, w_T$，那么可以视$x\mapsto \{h(x, w_i)\}$为一个”保度量“的$\mathbf{R}^n\to \mathbf{H}^T$变换³。

Hamming-NN Approximation

在$\mathbf{H}^d$（$d$约为$64$左右）中给定$p_1, \ldots, p_n$，每次询问$q$，查询$p_i$到$q$的最近邻。

Hamming 空间的度量是特殊的，并且每个维度只有$0$或$1$。因此距离的分析可以转化为不同分量个数的分析。

考虑把这件事变得随机一点。我们把每个点（$q$和$p_i$）作用一个排列$\sigma$来均匀随机打乱坐标。然后我们在$\{ \sigma p_i \}$中找与$\sigma q$的 LCP 最大的$N$个点加入候选集合$S$。多次取不同的排列$\sigma$，最后求$S$到$q$的最近邻即可⁴。

总体思路类似于将 Hamming 距离通过重排列来近似转化为 LCP 长度。

Well-Separated Pair Decomposition

对点集$P$的一个$\varepsilon$-WSPD 是一系列欧氏空间点集对$\{ (A_i, B_i) \}$满足

1. $\max(\operatorname{diam} A_i, \operatorname{diam} B_i) \le \varepsilon \operatorname{dist}(A_i, B_i)$（点集的距离为点对距离的最小值）；
2. $\bigcup A_i\times B_i = P\times P$。

基于任意递归的空间划分形成的树形结构都可以有一个朴素的$\varepsilon$-WSPD 构造方法：

1. 初始的点集对为$(P, P)$；
2. 对于当前的点集对$(A, B)$，不妨$\operatorname{diam}A > \operatorname{diam}B$。如果$(A, B)$满足条件就直接返回，否则将$A$按照树形结构的划分拆分成子集$\{A_i\}$，然后对$(A_i, B)$递归地构造 WSPD 即可。

复杂度$O(n\varepsilon^{-d}\log\Delta)$，$\Delta$为值域，$d$为空间维度。二维平面的情况可以四分树或者 KD-Tree，后者事实上任意维度均通用。

构造$\varepsilon = \frac{1}{2}$的 WSPD，则最近点对必然是某个孤点集对（但其实求最近点对可以直接 KD-Tree）。

t-Spanner

$t$-Spanner⁷ 是欧氏空间点集$P$的一个欧氏子图$H = (P, E)$，其中$E\subseteq P\times P$。$H$上的距离定义为最短路，边长为欧氏距离。并且$\forall x, y\in P$有$\Vert x - y \Vert_2 \le \operatorname{dist}_H(x, y) \le t\Vert x - y \Vert_2$。

可以用 WSPD 来构造$(1 + \varepsilon)$-Spanner：构造$\frac{\varepsilon}{4}$-WSPD，然后将代表点连边（总共$O(n\varepsilon^{-d}\log \Delta)$条边）。

证明可以通过对$\Vert x - y \Vert_2$归纳来完成。

在$(1 + \varepsilon)$-Spanner 上求 MST 可以得到点集$P$的一个$(1 + \varepsilon)$-近似 MST。

Tree Embedding

类似 Spanner，Tree Embedding 是将$d$维欧氏空间$[0, \Delta]^d$上的点集$P$映射到一棵树$T = (V, E)$（$P\subseteq V$），将点对的距离用树上的最短路距离代替。衡量指标为 distortion：$\max_{x\ne y} \frac{\operatorname{dist}_T(x, y)}{\Vert x - y\Vert_2}$，越小越好。

考虑构造一个$2^d$分树，然后将其随机平移（等价于固定$2^d$分树的总体范围，然后平移整个平面）。数据点构成树的叶子，高度为$i$的点到高度为$i + 1$的点的边权值为$\sqrt{d}2^i$（假设所有叶子结点深度相同）。$\sqrt{d}$可以理解为$d$维立方体对角线长度，是一个距离的常数。

这个做法的 distortion 是期望$O(d h)$级别。$h$是$2^d$分树的高度。

也可以用 KD-Tree 做一个魔改版，但是会导致逼近效果减弱（相当于曼哈顿距离）。

Johnson-Lindenstrauss Transform

Johnson-Lindenstrauss 是一种降维变换$f: \mathbf{R}^d \to \mathbf{R}^m$，能够一定误差内保$n$个$\mathbf{R}^d$上的点$p_i$两两之间的距离：$\Vert f(p_i) - f(p_j) \Vert_2 \in (1\pm \varepsilon) \Vert p_i - p_j \Vert_2$⁵。

应用：快速 Linear Regression。其本质是求$\arg\min_w \Vert Xw - y \Vert_2$（$X\in \mathbf{R}^{n\times d}, y\in \mathbf R^n, w\in \mathbf R^d$）。这里$X$事实上可以看成$d$个$n$维空间上的点（转置），于是线性回归就变成了一个欧氏距离下的近似线性表出的问题。

Subspace 版本 JL：

• 原始方法：构造$A = \frac{1}{\sqrt m} (w_1, \ldots, w_m)^T$，$w_i\in \mathbf R^n$为随机高斯向量，$A\in \mathbf R^{m\times n}$。
• 更优的做法：生成每列（随机）只有一个非零元素的 01 矩阵$A_{m\times n}$。

问题转化为$\arg\min_w \Vert AXw-Ay\Vert_2$。设$\tilde X = AX, \tilde y = Ay$，取$m = d$，则$\tilde X^T\tilde X$大概率可逆。于是$\hat w \approx (\tilde X^T\tilde X)^{-1} \tilde X^T y$⁶。

Power Iteration

主成分分析（Principal Component Analysis）是另外一种降维方法，主旨是对于$n$个$d$维空间上的点$p_i$找到$m$个单位正交向量$v_1, \ldots, v_m$，最大化$\frac{1}{n} \sum_{i = 1}^n\sum_{j = 1}^m (x_i, v_j)^2$（在此子空间上的投影长度和）。

Power Iteration 一种粗暴的求最大主成分（Top Principal Component）的算法。

不妨设$X = (x_1, \ldots, x_n)^T \in \mathbf R^{n\times d}$，那么 TPC 的目标可以写成$\max \Vert Xv\Vert _2 = \max v^TX^TXv$。

设$A = X^T X$是实对称矩阵，可以对角化。设$A = Q^TDQ$，并不妨设$D_{1,1}$是最大的特征值。则目标可以写成$\max (Qv)^T DQv$，结论是$\hat v$取$Q^T$第一列时最大化（因为算出来就是$D_{1,1}$）。

注意到$A = Q^T D Q$的本质是先旋转，再拉伸，再旋转（单位球映射成椭球），拉伸的方向就对应了 TPC 的方向。因此我们对任意一个向量$u$，只要其不垂直于$\hat v$，就可以在反复应用$A$后拉伸到 TPC 的方向。

因此我们不断计算$A^k u$然后单位化即可。

另外如果$X$足够稀疏，那么可以用$Au = X^T(Xu)$的方式计算。

Sparse Recovery

数据流（Streaming）模型：可以描述为一个插入/删除的操作构成的序列，只允许单次、顺序访问，在结束后回答一些询问，一般不要求实时，但是会有较强的空间限制。

前面的 Min-Hash，Sim-Hash，Hamming-NN 均可看作数据流算法。

事实上数据集可以等价地用每个元素出现的频数构成的频数向量$x$表达⁸。

记$\operatorname{supp}(x) = \{ p \mid x_p \ne 0\}$表示数据流中出现过的所有元素。定义$\ell_0$范数：$\Vert x\Vert _0 = |\operatorname{supp}(x)|$。若$\Vert x\Vert_0 \le k$，称之$k$-sparse。

Sparse Recovery 是一个数据流算法，能够给定$k$：

1. 检测数据流是否$k$-sparse；
2. 将$k$-sparse 的数据流的$\operatorname{supp}(x)$完全恢复

直径估计：设$\mathcal S_i$为$2^i\varepsilon$边长的格点划分，$i = 0, 1, \ldots, O(\log \Delta)$。在数据流的过程中对一个点的增删转化为其在$\mathcal S_i$所在格子的代表点的增删。询问时，找到最小的$i_{\min}$使得$\mathcal S_{i_{\min}}$是$k$-sparse 的，然后在$\mathcal S_{i_{\min}}$上估计直径。

Stream’s Sparse Recovery

对于一个$k$-sparse 的数据流，我们可以设计算法来恢复其频数向量：

1. 首先设计一种方法，能够保证对于每个数据流中的值$v$，存在一个只保留了$v$相关特征的信息；
2. 找到这个信息，还原$v$的特征。

考虑构造$T = O(\log k)$个$[n] \to [2k]$的均匀哈希$h_1, \ldots, h_T$来统计每个值的出现次数。那么对于$v \in [n]$，存在$h_i$满足没有别的值与$v$冲突的概率很高。

具体地，我们可以用哈希维护三个量：$c_1(v) = \sharp v$、$c_2(v) = v\times \sharp v$，$c_3(v) = r^v\times \sharp v$¹¹。$r$是事先确定的随机值（fingerprint）。那么如果$c_1(v)$整除$c_2(v)$且$r^vc_1(v) = c_3(v)$，那么说明这个哈希的$v$没有与别的值冲突（只有整除并不一定能证明不冲突，需要用 fingerprint 来保证），并且我们可以计算$\frac{c_2(v)}{c_1(v)}$来得到$v$。事实上这是一个$1$-sparse 信息。

这算法事实上在不知道数据流是否$k$-sparse 的情况下也能写。而我们可以通过把恢复出来的信息删掉来检验原数据流是否$k$-sparse。

Linear Sketch：上述算法相当于是将频数向量进行特定的线性变换，并从$Ax$来还原$x$。其优点是具有线性可加性，也可以减。也就是说我们可以恢复一个区间的频数向量。

Compressed Sensing

压缩感知是一种从低维信息还原高维的（稀疏的）信息的方法。

具体设定：找到一个$A\in \mathbf R^{m\times n}\; (m < n)$使得对于任意$z \in \mathbf R^n$，设$b = Az$，那么我们总可以通过求解$Ax = b$来近似地找到$z$。$A$可以视为$m$个线性感知器（Linear Sketch）。

我们可以构造随机高斯矩阵$A$，然后使用线性规划 solver 暴力求解$x$。若$x$是$n$维$k$-sparse 向量，那么当$m = O(k\log \frac{n}{k})$时这种方法基本上可以完美还原。

$\ell_0$-Sampling

$\ell_0$-Sampling 可以对于数据流返回一个$\operatorname{supp}(x)$上的均匀采样$p$，主要用于 support 比较大的情况。

一个对于$\operatorname{supp}(x)$的均匀采样可以这样得到：

1. 将$\operatorname{supp}(x)$中的元素以$\frac{1}{t}$的概率采样（以$\frac{1}{t}$的概率选择这个元素）；
2. 在选出来的元素中均匀采样。

事实上选出来的元素中只有一种值的概率是常数，因此可以用$1$-Sparse Recovery 来找到这个元素⁹。

因此我们分别取$t = 2^i$，$i = 1, \ldots, O(\log n)$构造采样哈希$h^{(i)} : [n] \to \{ 0, 1\}$，满足$\Pr [h^{(i)} (p) = 1] = \frac{1}{2^i}$。然后任意找到其中的一个$1$-Sparse 做为采样结果。算法的空间复杂度$O(\operatorname{poly}(\log n))$，时间复杂度$O(\log n)$。以$1 - \frac{1}{\operatorname{poly}(n)}$的概率成功。重复若干次即可得到一个高成功的采样方法。但要注意，同样的采样哈希得到的采样是相同的，因此多次重复需要使用不同的哈希。

Stream MST Approximation

图数据流是指点集不变，边集是一个数据流的模型。

考虑在图数据流上求连通分量。

考虑类似 Boruvka 算法的过程：维护当前连通块集合，每次将每个连通块的跨越边找出，然后连起来，更新连通块信息。这个算法的可拓展性在于记录跨越边的方法。

考虑对于$u \in V$，定义当前边集$E$的频数向量为$x^u$，满足$x^u(u, v) = \operatorname{sgn}(u - v)$。定义$x^S = \sum_{u\in S} x^u$，那么可以发现$\operatorname{supp}(x^S)$恰好是$S$的跨越边。于是可以使用$\ell_0$采样的方式来找到跨越边。

当然我们可以沿用这个思路去求图数据流的$(1 + \varepsilon)$-近似 MST。

但是注意到我们只能做$\ell_0$均匀采样，而不能很方便地找最小值。这里考虑一个暴力的做法：将边权离散化，然后从小到大暴力枚举。

离散化：将边权 round 到最近的$(1 + \varepsilon)$的方幂。仔细想想是有道理的，并且可以显著降低不同边权个数¹⁰，也就将数据流稀疏化了。

离散化后就可以对每个边权$i$和每个结点$u$分别维护频数向量$x^{u, i}$。查询跨越边时从小到大枚举$i$，在$\sum _{u\in S} x^{u, i}$中查询即可。

复杂度分析：设有$L$种边权。对于每种边权我们构造一个可加的$\ell_0$采样，空间复杂度$O(nL\operatorname{poly}(\log |V|))$，找到跨越边的复杂度是$O(L\log n)$，总时间复杂度$O(nL\log^2 n)$。

Comments & References

¹. Jaccard Similarity，空集的情况为$0$​​​ ↩

². 有时也估计他们的 Cosine Similarity ↩

³.$\mathbf{H}$​​​ 为 Hamming 空间，距离为曼哈顿距离，这里的保度量是指夹角和 Hamming 距离 ↩

⁴. 其实还需要再选择$2N$​​ 个 LCP 最大的去求最近邻，不过实践证明不太需要 ↩

⁵. 这说明：对于近似算法来说，“⾼维” =$O(\log n)$​ 维 ↩

⁶. 如何理解：$Xw=y$，则$w = X^{-1}y$，而$X$不可逆，则形式上构造$X^{-1}y = X^{-1}X^{-T}X^Ty=(X^TX)^{-1}X^Ty$↩

⁷. 个人理解：命名为 Spanner 的原因是$H$​ 是原图的一个生成子图 ↩

⁸. ⼀般假设：频数向量每⼀维的最⼤绝对值是$O(\operatorname{poly}(n))$​​ ↩

⁹. 1-Sparse 可以只需存那三个值 ↩

¹⁰. 例如$\log_{1.1}(10^{10}) \approx 242$↩

¹¹. 通过一些预处理方式可以$O(1)$​ 计算$r^v$​ ↩