Revision | 程序设计实习
Abstract. 程序设计实习(实验班)复习笔记。
其实也没什么好看的,看着玩玩。本文所有定理均不证。
随机算法概述
概率不等式
Theorem 1(Markov Bound). 随机变量
Theorem 2(Chernoff Bound, user-friendly).
利用 Chernoff Bound 可以将一个具有
Theorem 3(Hoeffding Inequality). 独立随机变量
C++ 随机库
minstd_rand
线性同余生成器,周期约 ,生成int32
。mt19937
随机性没有特别好,但是非常快。normal_distribution
从正态分布采样,定义方法是normal_distrubusion d{mu, sigma}
,调用方法是d(rnd)
,其中rnd
是随机数生成器。
采样
矩阵乘法结果验证
直接随机向量
因为是低维子空间,所以概率是 0。但实际上空间是离散的,所以说还是需要多次重复实验。
Reject Sampling
用
本质上是在二分
1 | int bern(double p, Generator *G){ |
中位数估计
Claim. 采样
将所有数据分成小中大三个部分(
低维度 1-Median 近似
给定点集
的
这个题用到了很多 Trick,我们从头看一遍。
首先我们找到一个
注意
而每一维坐标的中位数最小化了
接下来我们以
对于属于最内层的点,直接 round 到圆心。对于其他层的环,有环中每一个点到中心的距离都属于
假设第
下面分析我们的做法确实是一个
Claim 1.
由三角形不等式可证。
因为是独立采样,所以显然这东西是无偏估计。将
这里你希望
为了以
接下来我们分析总误差。
哈希
好像说不考,但还是看一下。
服务器负载均衡
有若干文件要存到服务器上,要使每个服务器的负载比较均衡,且支持添加服务器。
把文件和服务器用哈希打到一个环上,每个文件顺时针找第一个碰到的服务器存在上面(可以用经典数据结构如平衡树等维护)。
插入服务器时,只需要重构一台机器。哈希是独立的,因此典型情况下负载仍然均衡。
Count-min Sketch
用于求数据流频数向量。用
Bloom Filter
高效维护集合插入删除。将插入的元素用
这里
距离度量
相似度量
Jacard Similarity.
近似两个集合的交并比。
MinHash:
Cosine Similarity.
近似两个向量的夹角余弦。
Simhash:考虑
那么有
所以说余弦相似度实际上可以打到 Hamming 空间上去做。
那么选择 Cosine Similarity 作为距离函数的最近邻就可以转化到 Hamming 空间最近邻。
Hamming 空间最近邻
将所有位 Random Shuffle 之后找最长前缀的那一个。多次实验取最小值。
欧氏空间
下面这几个技术是比较常见的。
格点离散化
先求答案的一个常数倍近似
一些应用:
点集直径 求欧氏空间下点集的直径。
最小包围球 Coreset 对于一个点集
由此得到最小包围球的快速算法,类似地有近似求
四分树
和熟悉的四分树是一个东西。记四分树的节点集合为
可以用来求欧式最近邻的
对于每一个
那么这个格子不需要被考虑(
- 首先另
为 的所有节点的儿子。 - 用
更新 。 - 用现在的
扔掉所有不需要的子节点。
算法的正确性是显然的,现在分析其时间。我们只需要分析每一层的点数上界。这里不剪枝条件是
Claim. 算法结束前每一层都有
Proof. 算法结束前至少
化简得到
变形一下即得证。
所以说当前的所有格子里面都存在一个点到
所以说算法总复杂度为
WSPD
用来离散化点对。
点集
其中
有一个显然的四分树上递归算法:
这里的
这个算法的正确性显然,我们来分析时间复杂度。
Claim 1.
观察代码立即可得。
Claim 2. 任何一个格子作为较小的格子被加入的次数为
分两个格子差一层和差两层讨论,注意判断条件都是在父亲处没有被加入而在儿子处被加入了,黑体字指出加入的点的可能来源是一个以
四分树中节点只有
注意四分树缩二度点后只有
这给出了一个精确求最近点对的算法。
首先构造一个
Claim. WSPD 中一定存在
假设包含
和
自然 WSPD 也可以用来求直径。
Spanner
用下面的技术可以把欧氏空间上的点集保距离地 embed 到一个图上。
这里
算法是直接求
施归纳法于点对之间的距离,因为点数有限,距离是离散化的,所以归纳是正确的。
考虑
对于最近点对,前面一段告诉我们必然有一个对是这两个单点,因此这两个点连通,路径长度恰好为
。否则假设
, 的代表点分别是 和 ,那么有发现这里只要
即可满足在 充分小时 (取 4 是不行的)。但是实践中即使求 WSPD 都还是过了,很神秘。
Spanner 可以近似欧几里得 MST。直接求 Spanner 然后在上面 Kruskal 即可。
Tree Embedding
直接随机平移然后 embed 到四分树上去,距离直接看成四分树上的距离(边权写成
近似比非常大,为
用 Tree Embedding 可以近似:高维 MST,高维最小权匹配。
降维
JL
将一个
在
每个向量正交投射到
首先容易证明这时候模长是无偏估计。
最后一步基于
这里如果数据集是有限的,只需要一步 Union Bound 就可以约束住所有点的误差,但是如果数据集是某个线性空间,有 JL 结论的子空间版本:
时,有
一个改进是随机一个每一列只有一个元素非零、均匀随机取