Revision | 程序设计实习

Abstract. 程序设计实习（实验班）复习笔记。

其实也没什么好看的，看着玩玩。本文所有定理均不证。

• 随机算法概述
  • 概率不等式
  • C++ 随机库
  • 采样
  • 哈希
• 距离度量
  • 相似度量
  • 欧氏空间
    • 格点离散化
    • 四分树
    • WSPD
    • Spanner
    • Tree Embedding
• 降维
  • JL

随机算法概述

概率不等式

Theorem 1（Markov Bound）. 随机变量 $X \geq 0$，那么

$$
\mathrm{Pr}(X \geq a) \leq \mathbb{E}[X] / a
$$

Theorem 2（Chernoff Bound, user-friendly）. $n$ 个随机变量 $X_1, …, X_n$ 独立同期望 $\mu$，记 $X = \frac 1n \sum\limits_i^n X_i$ 那么对于任意的 $\delta \in (0, 1)$ 有

$$
\mathrm{Pr}\left(|X - \mu| \geq \sqrt{\dfrac{\log(1/\delta)}{n\mu}}\mu\right) \leq \delta
$$

利用 Chernoff Bound 可以将一个具有 $p > 0.5$ 概率正确的算法（常数概率正确）的正确率强化至任意的 $1-\delta$，称为 Median Trick。做法是直接做 $T$ 次独立重复实验取众数，这里

$$
T = O(\log (1/\delta))
$$

Theorem 3（Hoeffding Inequality）. 独立随机变量 $X_1, …, X_m \in [s, t]$，令 $X = \sum_{i=1}^m X_i$，那么

$$
\mathrm{Pr}(X - \mathbb{E}[X] > z) \leq 2\exp\left(-\frac{2z^2}{m(t-s)^2}\right)
$$

C++ 随机库

• minstd_rand 线性同余生成器，周期约 $2^32$，生成 int32。
• mt19937 随机性没有特别好，但是非常快。
• normal_distribution 从正态分布采样，定义方法是 normal_distrubusion d{mu, sigma}，调用方法是 d(rnd)，其中 rnd 是随机数生成器。

采样

矩阵乘法结果验证

$O(n^2)$ 时间验证 $\boldsymbol{AB}$ 是否等于 $\boldsymbol{C}$。

直接随机向量 $\boldsymbol{x}$，验证是否相等。这里当 $\mathbf{AB} \ne \mathbf{C}$ 时，算法错误的概率是

$$
\mathrm{Pr}(\boldsymbol{x}\in \ker(\mathbf{AB}-\mathbf{C})) = 0
$$

因为是低维子空间，所以概率是 0。但实际上空间是离散的，所以说还是需要多次重复实验。

---

Reject Sampling

用 $p=\frac 12$ 的两点分布生成一个任意 $p$ 的两点分布。

本质上是在二分 $p$ 这个点。

int bern(double p, Generator *G){
    double now = p;
    while(1) {
        int b = G->rand(), cur = floor(p * 2);
        p = p * 2 - cur;
        if(b < cur) return 1;
        if(b > cur) return 0;
    }
}

---

中位数估计

Claim. 采样 $O(1/\varepsilon^2)$ 次位数误差大常数概率不超过 $2\varepsilon n$。

将所有数据分成小中大三个部分（$A_1, A_2, A_3$），你可以用 Chernoff bound 算出大常数概率 $A_1, A_3$ 中元素个数不超过 $(0.5-\varepsilon)T$。

---

低维度 1-Median 近似

给定点集 $S$，多次读入 $r$，高速求

$$
\mathrm{cost}(S, q) = \sum_{p\in S} |p - q|
$$

的 $1+\varepsilon$ 近似。

这个题用到了很多 Trick，我们从头看一遍。

首先我们找到一个 $c$ 使得 $\mathrm{cost}(S, c)$ 是 $\min\limits_x(\mathrm{cost}(S, x))$ 的常数倍近似，不妨直接取每一维坐标的中位数。

注意

$$
\sum_{i=1}^d |x_i| \leq d\sqrt{\sum\limits_{i=1}^d x_i^2}
$$

而每一维坐标的中位数最小化了 $\sum|x - x_i|$，所以说我们求出的 $c$ 是答案的 $d-$近似。

接下来我们以 $\varepsilon\mathrm{cost}(S, c), 2\varepsilon\mathrm{cost}(S, c), …, 2^k\varepsilon\mathrm{cost}(S, c), …$ 为半径做圆。然后有下面的采样算法：

对于属于最内层的点，直接 round 到圆心。对于其他层的环，有环中每一个点到中心的距离都属于 $[r, 2r]$。

假设第 $i$ 层环的点构成的集合是 $P_i$，我们从环上独立采样 $m$ 个点 $x_{i1}, …, x_{im}$，然后用下面的式子来估计 $\mathrm{cost}(P_i, q)$：

$$
\frac{|P_i|}{m}\sum_{j=1}^m |x_{ij} - q|
$$

下面分析我们的做法确实是一个 $1+\varepsilon$ 近似。内圈的分析是显然的，记环上的点集是 $P$，采样得到的点为 $x_1, …, x_m$。

Claim 1. $||x_i - q| - |x_j - q|| \leq 2r$。

由三角形不等式可证。

因为是独立采样，所以显然这东西是无偏估计。将 $|x_i - q|$ 视为 $m$ 个随机变量带入 Hoeffding 不等式得到

$$
\mathrm{Pr}\left(X - \mathrm{cost}(P, q)\frac{m}{|P|} \geq z\right) \leq 2\exp\left(-\frac{2z^2}{m(t-s)^2}\right)
$$

这里你希望 $\frac{2z^2}{m(t-s)^2}$ 是 $O(m)$ 级别的，这样失败概率可以被 $m$ 以指数级控制，于是你可以采样 $O(\log n)$ 个点来实现近似，因此 $z = O(\varepsilon(t-s)m) = O(\varepsilon r m)$。此时观察左边概率内部的式子，我们得到估计值的误差为

$$
\frac{|P|}{m}\sum_{i=1}^m |x_i - q| = \mathrm{cost}(P, q)\pm \varepsilon |P|r
$$

为了以 $1-\delta$ 概率成功需要满足

$$
2\exp(-\varepsilon^2 m)\leq \delta \Rightarrow m = O(1/\varepsilon^2\log(1/\delta))
$$

接下来我们分析总误差。

$$
\begin{align}
\varepsilon |P|r &\leq \varepsilon \sum_{x\in P} |p - c| \\
&\leq d\varepsilon\sum_{x\in P} |p - q| \\
&= O(\varepsilon\mathrm{cost(P, q)})
\end{align}
$$

哈希

好像说不考，但还是看一下。

服务器负载均衡

有若干文件要存到服务器上，要使每个服务器的负载比较均衡，且支持添加服务器。

把文件和服务器用哈希打到一个环上，每个文件顺时针找第一个碰到的服务器存在上面（可以用经典数据结构如平衡树等维护）。

插入服务器时，只需要重构一台机器。哈希是独立的，因此典型情况下负载仍然均衡。

---

Count-min Sketch

用于求数据流频数向量。用 $T = \log n$ 个独立的哈希将 $n$ 个元素打到 $m$ 个指标上（这里 $m<<n$），多次实验取 $\min$。

---

Bloom Filter

高效维护集合插入删除。将插入的元素用 $k$ 个独立的哈希打到 $k$ 个 $[1, m]$ 的值上面，判断一个元素属于集合若哈希之后的 $k$ 个位置都是 $1$。

这里 $m = O(n)$，$n$ 是插入次数。为小常数线性空间算法。

距离度量

相似度量

Jacard Similarity.

近似两个集合的交并比。

MinHash：$T$ 次将元素随机哈希打到 $(0, 1)$，假设最小值相同的次数为 $n$，则 Jacard Similarity 近似为 $n/T$。这样可以将一次求解的复杂度从 $O(n)$ 变成 $O(T)$。

---

Cosine Similarity.

近似两个向量的夹角余弦。

Simhash：考虑 $\boldsymbol{w}$ 是随机高斯向量，记

$$
h(x) = \mathrm{sgn}(\langle\boldsymbol{w}, \boldsymbol{x}\rangle)
$$

那么有

$$
\cos \langle x, y\rangle = \mathrm{Pr}(h(x)=h(y))
$$

所以说余弦相似度实际上可以打到 Hamming 空间上去做。

那么选择 Cosine Similarity 作为距离函数的最近邻就可以转化到 Hamming 空间最近邻。

---

Hamming 空间最近邻

将所有位 Random Shuffle 之后找最长前缀的那一个。多次实验取最小值。

欧氏空间

下面这几个技术是比较常见的。

格点离散化

先求答案的一个常数倍近似 $T$，然后将整个空间划分成 $\dfrac 1{2\sqrt d}\epsilon T$ 的网格，每个数据点 round 到其所在的网格中心。这样可以有效减少数据量，并保证 $1+\varepsilon$ 近似。

一些应用：

点集直径 求欧氏空间下点集的直径。

$2-$近似点集直径有一个经典做法就是随便找一个点和一个距离他最远的点。

最小包围球 Coreset 对于一个点集 $P$，定义 $f(P, c)$ 为以 $c$ 为圆心的最小包围球直径。

$P$ 的一个 $\varepsilon-$coreset 定义为一个点集 $S$，使得 $\forall c, f(S, c)\geq (1-\varepsilon)f(P, c)$。

由此得到最小包围球的快速算法，类似地有近似求 $k-$center 的快速算法。

四分树

和熟悉的四分树是一个东西。记四分树的节点集合为 $\square_1, …, \square_m$。

---

可以用来求欧式最近邻的 $(1+\varepsilon)-$近似。查询点记为 $p$，真正的最优解记为 $r^*$。

对于每一个 $\square_i$ 取一个代表点 $q_i$。如果一个格子满足

$$
\hat r \leq (1+\varepsilon)(|p - q_i| - \mathrm{diam}(\square_i))
$$

那么这个格子不需要被考虑（$\hat r$ 是当前最优解）。那么我们的做法是，逐层求解四分树上第 $i$ 层需要考虑的格子集合 $A_i$。

• 首先另 $A_i$ 为 $A_{i-1}$ 的所有节点的儿子。
• 用 $A_i$ 更新 $\hat r$。
• 用现在的 $\hat r$ 扔掉所有不需要的子节点。

算法的正确性是显然的，现在分析其时间。我们只需要分析每一层的点数上界。这里不剪枝条件是

$$
|p - q_i| < \frac{r}{1+\varepsilon} + \mathrm{diam}(\square_i)
$$

Claim. 算法结束前每一层都有

$$
\frac{\hat r}{1+\varepsilon} + \mathrm{diam}(\square_i) \leq O(1/\varepsilon)\mathrm{diam}(\square_i)
$$

Proof. 算法结束前至少 $\hat r$ 所在的格子没有被剪枝（否则 $|A_i| = 0$，算法停止），所以

$$
\hat r < (1+\varepsilon)(\hat r + \mathrm{diam}(\square_i))
$$

化简得到

$$
\hat r \leq \frac{1+\varepsilon}{\varepsilon} \mathrm{diam}(\square_i)
$$

变形一下即得证。

所以说当前的所有格子里面都存在一个点到 $q$ 的距离不超过 $O(1/\varepsilon)\mathrm{diam}(\square_i)$，用总体积估计一下格子数量得到

$$
\mathrm{diam(\square_i)}^d|A| < O(1/\varepsilon^d)\mathrm{diam}(\square_i) \Rightarrow |A| < O(1/\varepsilon^d)
$$

所以说算法总复杂度为 $O(1/\varepsilon^d\log(V))$

WSPD

用来离散化点对。

点集 $P$ 的一个 $\varepsilon-$WSPD 定义为若干 $(A_i, B_i)$，使得

1. $$
   \bigcup_{i} A_i \times B_i = P\times P
   $$
2. $$
   \max(\rm{diam}(A_i), \rm{diam}(B_i)) \leq \varepsilon \rm{dis}(A_i, B_i)
   $$

其中 $\rm{dis}$ 定义为最近点对距离。

有一个显然的四分树上递归算法：

$$
\begin{align*}
1~ &\mathbf{WSPD}(\square_u, \square_v) \\
2~ &\hspace{2em}\mathrm{if}(u=v \wedge \delta(\square_u)=0)~\mathrm{return} \\
3~ &\hspace{2em}\mathrm{if}(\delta(\square_u) < \delta(\square_v))~\mathrm{swap}(\square_u, \square_v) \\
4~ &\hspace{2em}\mathrm{if}(\delta(\square_v) \leq \varepsilon\mathrm{dis}(\square_u, \square_v))~\mathrm{return}~(\square_i, \square_j)\\
5~ &\hspace{2em}\mathrm{return}~\bigcup_{\square_i \in \mathrm{son}(\square_v)} \mathrm{WSPD}(\square_u, \square_i)
\end{align*}
$$

这里的 $\delta$ 是估计直径的量，如果只有一个点那么为 $0$，如果有两个点那么就取 $\mathrm{diam}(\square_i)$。

这个算法的正确性显然，我们来分析时间复杂度。

Claim 1. $\square_u, \square_v$ 最多差一层。

观察代码立即可得。

Claim 2. 任何一个格子作为较小的格子被加入的次数为 $O(\varepsilon^{-d})$。

分两个格子差一层和差两层讨论，注意判断条件都是在父亲处没有被加入而在儿子处被加入了，黑体字指出加入的点的可能来源是一个以 $O(\varepsilon\mathrm{diam}(\square_i))$ 为半径的球，用体积估计一下立即得到上述结论。

四分树中节点只有 $O(n\log V)$ 个，所以说本算法复杂度为 $O(\varepsilon^{-d}n\log V)$。

注意四分树缩二度点后只有 $O(n)$ 个节点，在压缩四分树上做 WSPD，时间复杂度为 $O(\varepsilon^{-d}n)$，但是分析就很阴间了。

---

这给出了一个精确求最近点对的算法。

首先构造一个 $\varepsilon-$WSPD，只需要满足 $\varepsilon < 1$ 即可。

Claim. WSPD 中一定存在 $({p}, {q})$，其中 $(p, q)$ 为最近点对。

假设包含 $p, q$ 的极小的对 $(A_i, B_i)$ 中，$p$ 和某个 $x$ 均在 $A_i$ 中，那么有

$$
\mathrm{dis}(p, x)\leq \mathrm{diam}(A_i) < \mathrm{dis}(A_i, B_i) < \mathrm{dis(p, q)}
$$

和 $(p, q)$ 是最近点对矛盾。

---

自然 WSPD 也可以用来求直径。

Spanner

用下面的技术可以把欧氏空间上的点集保距离地 embed 到一个图上。

$(1+\varepsilon)-$Spanner 是一个欧式图的子图（完全图，边权为欧几里得距离），满足
$$
(\forall x, y\in P) |x-y|\leq \mathrm{dis}_G(x, y) \leq (1+\varepsilon) |x-y|
$$

这里 $\mathrm{dis}_G$ 是图上的最短路。

算法是直接求 $\varepsilon/k-$WSPD（$k > 4$），然后每一个对取一对代表点连边。下面我们证明这个图确实连通，而且满足上述条件。

施归纳法于点对之间的距离，因为点数有限，距离是离散化的，所以归纳是正确的。

考虑 $(x, y)$。

• 对于最近点对，前面一段告诉我们必然有一个对是这两个单点，因此这两个点连通，路径长度恰好为 $|x-y|$。

• 否则假设 $(x, y)\in (A, B)$，$A, B$ 的代表点分别是 $x^*$ 和 $y^*$，那么有

  $$
  \begin{align}
  \mathrm{dis}_G(x, y) &\leq \mathrm{dis}_G(x, x^*) + |x^* - y^*| + \mathrm{dis}(y^*, y) & \text{(Triangular inequality on $G$)}\\
  &\leq (1+\varepsilon)|x - x^*| + |x^* - y^*| + (1+\varepsilon)|y^*-y| & \text{(Inducion hypothesis)} \\
  &\leq 2(1+\varepsilon)\frac{\varepsilon}{k}\mathrm{dis(A, B)} + |x^* - y^*| & \text{(Properties of $\varepsilon/k-$WSPD)} \\
  &\leq \left(2(1+\varepsilon)\frac{\varepsilon}k + 1+\frac{2\varepsilon}k\right)|x - y| & \text{(Properties of $\varepsilon/k-$WSPD)}
  \end{align}
  $$

  发现这里只要 $k > 4$ 即可满足在 $\varepsilon$ 充分小时 $\mathrm{dis}_G(x, y) < (1+\varepsilon)|x-y|$（取 4 是不行的）。但是实践中即使求 $20-$WSPD 都还是过了，很神秘。

---

Spanner 可以近似欧几里得 MST。直接求 Spanner 然后在上面 Kruskal 即可。

Tree Embedding

直接随机平移然后 embed 到四分树上去，距离直接看成四分树上的距离（边权写成 $\mathrm{diam}(\square_i) / 2$，$\square_i$ 为儿子节点）

近似比非常大，为 $O(dh)$，$h$ 是四分树高度。不想证了。

用 Tree Embedding 可以近似：高维 MST，高维最小权匹配。

降维

JL

将一个 $n$ 维空间保距地降到 $m$ 维。

在 $n$ 维空间中随机取 $m$ 个高斯向量 $\boldsymbol{w}_1, …, \boldsymbol{w}_m$（每一维标准差为 $1$，均值为 $0$），不归一化。

每个向量正交投射到 $\langle \boldsymbol{w}_1, …, \boldsymbol{w}_m \rangle$，然后取坐标 $/\sqrt m$。换言之就是随机一个 $n\times m$ 的正态矩阵 $A$，然后直接乘 $A/\sqrt m$。

首先容易证明这时候模长是无偏估计。

$$
\begin{align}
&\sum_{i=1}^m \langle \boldsymbol{w}_i, \boldsymbol{v} \rangle^2 \\
=& \sum_{i=1}^m \sum_{j=1}^n (w_{ij} v_j)^2 \\
=& \sum_{j=1}^n v_j^2 \sum_{i=1}^n w_{ij}^2 \\
=& \sum_{j=1}^n v_j^2
\end{align}
$$

最后一步基于 $w_{ij}$ 的均值和标准差。

$$
\mathrm{Pr}\left(|\hat x - \hat y|^2\in(1\pm\varepsilon)|x-y|^2\right)\geq 1-\exp(O(\varepsilon^2m))
$$

这里如果数据集是有限的，只需要一步 Union Bound 就可以约束住所有点的误差，但是如果数据集是某个线性空间，有 JL 结论的子空间版本：

$U$ 是 $\mathbb{R}^n$ 的 $d$ 维子空间，当

$$
m = O\left(\frac{d\log \varepsilon^-1+\log 1/\delta}{\varepsilon^2}\right)
$$

时，有

$$
\mathrm{Pr}\left(v\in U, |\hat v|^2\in(1\pm\varepsilon)|v|^2\right)\geq 1-\delta
$$

---

一个改进是随机一个每一列只有一个元素非零、均匀随机取 $1, -1$ 的稀疏矩阵 $A$，有类似的保证。