COMP5270 Sample Exam 1 中文详细题解
来源:
Sample Exam #1.pdf
说明: 原 PDF 是 sample exam 题目册，没有附官方 solutions。下面是按课程讲义和 tutorial/assignment 思路整理的中文详细题解。
重点: MIS 的 LP relaxation + randomized rounding、triangle counting estimator、streaming reservoir sampling。
总览
这份 sample exam 一共 4 题：
| 题目 | 分值 | 主题 |
|---|---|---|
| Problem 1 | 10 | MCQ，覆盖随机算法、hashing、Bloom filter、LP、LSH |
| Problem 2 | 15 | Maximum Independent Set 的 ILP/LP relaxation 和 randomized rounding |
| Problem 3 | 15 | 在 query access 下估计 triangle 数量 |
| Problem 4 | 20 | one-pass streaming 下 uniform edge sampling，并接上 Problem 3 的 triangle estimator |
Problem 1: Multiple Choice
每小题 1 分，答错 0 分，不答 0.5 分。
(1)
题意：如果一道 MCQ 有 3 个选项，随机猜是否比不答更好？
答案：False。
理由：
随机猜的期望分数是
不答给
(2)
题意：哪种算法 worst-case running time 有界，但允许小概率错误？
答案：Monte Carlo。
对比：
- Las Vegas：永远正确，运行时间随机；
- Monte Carlo：运行时间有界，答案允许小概率错误；
- nondeterministic：不是这里的 randomized algorithm 分类。
(3)
题意：若
答案：False。
Universal hashing 只保证对
它控制的是碰撞概率，不是每个单点
(4)
题意：从含有
答案：
这是 coupon collector。收集到第
(5)
题意：Karger 算法解决哪个问题？
答案：Min-Cut。
Karger 随机收缩边，保留 parallel edges，直到剩两个 supernodes，输出对应 cut。它是 randomized algorithm for global minimum cut。
(6)
题意：CountMinSketch、CountSketch、Misra-Gries 都是哪个问题的 streaming algorithms？
答案：Frequent Elements。
它们都用于 frequency estimation / heavy hitters / frequent elements：
- Misra-Gries：deterministic additive error；
- CountMinSketch：
additive overestimate； - CountSketch：
error，支持 general turnstile。
(7)
题意：Bloom filter 可能报告哪类错误？
答案：False positives。
插入过的元素对应 bits 已经被置为 1，所以不会 false negative。未插入元素的若干 bits 可能被其他元素置为 1，所以可能 false positive。
(8)
题意：ILP 的 LP relaxation 可以高效求解，并且得到同一个 optimal solution？
答案：False。
LP relaxation 可以高效求解，但通常只给 fractional optimum，不一定是 integral optimum。对 minimization，LP optimum 常是 lower bound；对 maximization，LP optimum 常是 upper bound。
(9)
题意：Strongly universal hash family 保证没有 collisions with high probability？
答案：False。
Strongly universal 只说明两个不同 key 的 hash values
独立且均匀。因此一对 key 的碰撞概率是
(10)
题意：LSH 中 sensitivity parameter
答案：Increases。
在 Hamming space 中典型关系是
Problem 2: MIS 的 ILP、LP Relaxation 和 Randomized Rounding
Maximum Independent Set, MIS：
给定无向图
(a) 哪个 ILP 对应 MIS？
答案：左边。
左边 ILP 是：
subject to
解释：
表示选择 vertex ； - 对每条边
，约束 表示不能同时选择两个端点； - 最大化
就是最大化选择的点数。
右边的变量是按 edge 选的，更像 edge cover / vertex covering constraints，不是 MIS。
(b) MIS 解和 ILP 解之间的互相转换
从 independent set 到 ILP solution
给定 independent set
因为
目标值是
所以 independent set 给出一个同值的 ILP feasible solution。
从 ILP optimal solution 到 MIS solution
给定一个 integral feasible solution
若存在边
违反 ILP 约束。所以
目标值仍然是
因此 ILP optimum 和 MIS optimum 相同。
(c) LP relaxation
把 binary constraint
放松成
得到 LP：
subject to
记最优 LP 解为
(d) 为什么算法返回的
算法分两种情况。
情况 1：Line 3 返回单点集
如果返回
情况 2：Line 10 返回
算法先随机生成
- 如果
且 ，说明这条边在 中造成冲突； - 算法把
都加入 ； - 最后返回
。
反证。若最终
因为
因此返回的
(e) Line 3 情况下的
Line 3 发生时：
算法返回一个 arbitrary vertex，所以
又因为
所以
也就是说返回解的大小至少是 optimum 的
下面假设
因此算法执行 Lines 5 to 10。
(f) 计算
每个 vertex
令
由 linearity of expectation：
(g) 证明
对每条边
因为
如果某条边
取期望：
不一定是 equality。原因是同一个 vertex 可能因为多条 bad edges 被加入
例如一个 triangle 中，如果三个点都在
(h) 证明
先证明对每条边
第一步：
因为
等价于
这里如果担心这一步太快，可以这样证明：因为
令
第二步：
LP 约束给出
所以
于是对每条边都有
代入 (g)：
(i) 得到 approximation guarantee
因为
所以
取期望：
由 (f) 和 (h)：
现在使用假设
这等价于
因此
所以
又因为
所以
算法输出的 expected solution size 至少是 optimum 的
Problem 3: Triangle Counting with Query Access
已知：
已知， ； 已知； - 但 edge set
不直接给出； - 可用 query：
- uniform random edge；
- edge check；
- uniform random vertex。
目标：估计 triangle 数量
(a)
做法：
- 对每一对 vertices
，调用 edge check； - 用
次 query 建出完整 adjacency matrix； - 枚举所有 triples
； - 若三条边都存在，则计数加 1。
query complexity：
正确性：edge check 已经恢复了整张图，所以之后本地枚举 triples 得到的
triangle 数量就是精确的
(b)
使用 random edge query，把边当成 coupon。
算法：
- 进行
次 random edge query；
- 把抽到的 edges 存入 set；
- 在已收集的 edge set 上数 triangles。
注意：算法不一定知道自己已经收齐了所有 edges。它只是直接在 sample
到的 edge set
上计数；如果确实收齐，则答案精确。如果没收齐，答案可能偏小。所以
correctness statement 是“以至少
为什么高概率收集到所有 edges？
对固定 edge
对所有
选足够大的常数
(c) 不知道
因为 vertex set
然后把这个 order 限制到真正的 edge set
比较两条已经给出的 edges 时，只需要比较它们的两个 endpoint labels，不需要 query graph。
(d) Algorithm 1 的实现、时间和 query complexity
Algorithm 1 做的事：
- random edge query 得到
； - 从
均匀抽 ； - edge check 检查
和 ； - 再检查 order 条件：
是否是这三条边里最早的边； - 若通过，返回
，否则返回 0。
实现细节：
- 抽 uniform random edge：1 次 edge query；
- 抽
： - 如果本地允许从已知 vertex list 采样，则不需要 graph query；
- 如果只能用 vertex query，则 rejection sampling：不断抽 uniform
vertex，直到不是
。成功概率是 ，期望次数是 ，因为 ；
- edge checks：最多 2 次；
- order comparison：本地计算，不需要 query。
因此 expected query complexity 是
如果用本地采样
时间复杂度同理是 expected
(e) 证明
设算法一次输出的随机变量为
对每个 triangle
它有三条边。根据固定 order，其中恰好有一条最早的边，记为
Algorithm 1 会因为这个 triangle 返回
- random edge query 抽到
； - 随机 vertex
抽到这个 triangle 的第三个 vertex。
这两个事件概率分别是
所以固定 triangle 被成功命中的概率是
order 条件保证每个 triangle 只会被它最早的 edge 计一次，不会被三条边重复计数。
令
于是
所以 estimator unbiased。
(f) 证明
一次运行中，
由 (e)，命中概率是
因此二阶矩：
方差满足
(g) 重复
令
无偏性：
方差：
希望得到
with probability at least
用 Chebyshev：
题目给 promise：
所以只要
并把 hidden constant 取足够大，就能让失败概率至多
因此 query complexity 是
次 Algorithm 1，每次 expected
(h) Dense graph 且有
Dense graph 意味着
又给出 promise：
三种算法的 query complexity：
- exact adjacency matrix：
- coupon collector 收集所有 edges：
- sampling estimator：
若
若只要 2-approximation，取
次 samples。
因此 dense 且 triangle-rich 的情况下，应使用 sampling estimator，因为
query complexity 是常数级，而 exact algorithms 至少
Problem 4: Streaming Uniform Edge Sampling
现在图以 one-pass edge stream 给出：
每条 edge 恰好出现一次。
目标：最后输出一条从
(a) 如果知道
最简单方法：
- 在读 stream 前，随机选择
- 读 stream 时维护 counter
； - 当
时，存下 ； - stream 结束输出存下的 edge。
正确性：
对每条 edge
所以输出是 uniform edge。
空间复杂度：
- 存
和 counter ： bits； - 存一条 edge，两端点来自
： bits。
总空间：
(b) 不知道
答案：
这就是 reservoir sampling for
算法含义：
- 第 1 条 edge 先存下来；
- 第
条 edge 到来时，用概率 替换当前样本。
不能选：
：后面的元素替换概率太大，最终偏向 stream 后部； ：概率太小，且和当前已见元素数量无关； ：算法运行时不知道 。
(c)
证明任意 step
用 induction。
Base case:
只有
Inductive step
假设 step
到 step
新 edge
它被选中的概率正是替换概率：
旧 edge
它在 step
所以 step
(d) 如何用 random bits
实现 Bernoulli
目标：生成
做法：
- 令
- 用
个 unbiased random bits 生成
uniformly；
- 如果
，拒绝并重新生成； - 如果
，则 在 上均匀； - 输出
接受概率：
所以 expected repetitions 至多 2。每次用
(e) Space complexity 和正确性
算法需要存：
- 当前 sample edge：
bits； - 当前时间
：由于 ，所以 bits； - 临时随机数：
bits。
总空间：
由 (c)，stream 结束时
所以算法确实输出 uniform random edge from
(f) 在 streaming setting 中估计 triangles
目标：把 Problem 3 的 estimator 搬到 one-pass stream。
关键难点：
Problem 3 的 Algorithm 1 需要：
- uniform random edge；
- uniform random third vertex；
- 判断另外两条边是否存在；
- 判断 sampled edge 是否是三角形三条边中 order 最早的边。
在 streaming 中不能随时做 arbitrary edge check，因为不能存完整
单个 estimator 的 streaming 版本
对一份 estimator，维护：
- reservoir sample edge
； - 抽到该 edge 时的第三个 vertex
； - 两个 flags：
- 是否后来见过
； - 是否后来见过
。
- 是否后来见过
stream 处理方式：
- 用 reservoir sampling 维护当前 sample edge。
- 每当 sample edge 被替换成当前边
时，重新抽
并把两个 flags 重置为 false。
- 在之后的 stream 中，如果看到
或 ，就设置对应 flag。 - stream 结束时，如果两个 flags 都为 true，则该 estimator 输出
否则输出 0，其中
为什么这模拟了 Problem 3？
对任意 triangle，它在 stream order 下恰好有一条最早出现的 edge。
这个 estimator 输出非零，正好对应：
- reservoir 最终选中了该 triangle 的最早 edge；
选中了 triangle 的第三个 vertex； - 另外两条 triangle edges 在 stream 中出现在它之后，因此 flags 会被看到。
如果 reservoir 选到的不是三角形中最早的 edge，那么至少有一条相关 edge 已经在之前出现过，flags 不会同时变 true，这和 Problem 3 的 order condition 输出 0 一致。
所以单次 estimator 仍然是 unbiased：
方差分析沿用 Problem 3：
重复次数
如果已知 promise
Problem 3 给出需要
由于 streaming 开始时不知道
因为
Space complexity
每个 copy 存：
- 当前 sampled edge：
； - third vertex
： ； - 两个 flags：
； - reservoir sampling 所需的少量状态。
全局还要存 stream counter
因此总空间为
bits。
如果用更紧的
输出
最后复习重点
这份卷子最值得记的套路：
- LP relaxation for maximization：
。 - Randomized rounding + deletion：先按 fractional
value 缩放采样，再删除冲突，用
证明期望大小。 - Triangle estimator：sample edge + sample third vertex + order condition，保证每个 triangle 只被 count 一次。
- 方差到 sample complexity：若
，平均 次后用 Chebyshev 得 。 - Reservoir sampling：第
个元素用概率 替换，归纳证明每个已见元素概率都是 。 - Streaming triangle trick：把 edge order 设成 stream order，只需要检查 sampled edge 之后出现的两条边，避免存完整图。