COMP5270 Assignment 3 Feedback-only 中文详细题解
来源: Assignment 3 (Feedback-only) Solutions.pdf
主题: Hamming ANN/LSH, Knapsack approximation, streaming max coverage, AMS sketch, reservoir sampling
这份 feedback-only assignment 有 5 个问题：
| 题目 | 类型 | 核心内容 | 复习建议 |
|---|---|---|---|
| Problem 1 | Programming | 实现 Hamming ANN / LSH，并用 ANN Benchmarks 比较性能 | PDF 没给理论 solution；实现和 benchmark 不是优先复习重点 |
| Problem 2 | Theoretical | Knapsack 的 2-approximation 和 streaming 版本 | 重点，贪心 + fractional knapsack relaxation |
| Problem 3 | Theoretical | 只选 |
重点，threshold greedy + guessing optimum |
| Problem 4 | Theoretical | 用 Tug-of-War / AMS sketch 估计 |
很重要，streaming sketch + 4-wise independence |
| Problem 5 | Theoretical | 不知道 stream 长度时，均匀随机抽 |
重点，reservoir sampling |
PDF 开头说明：Problem 1 是 programming，Problem 2-5 是 theoretical，并且 solutions 只提供 theoretical questions。 所以下面不会写 ANN Benchmarks 的代码实现，只整理它的任务目标和复习取舍；后面四题会详细写。
统一背景与符号
故事背景是 D&D / magical items。
有
含义：
是 item identifier； 是价格； 是 item 给第 个 characteristic 的 bonus； 是 characteristic 数量； - 一般假设
，但不能把 当常数，除非题目特别说。
定义 item
Problem 1: Hamming ANN / LSH 编程题
题目在做什么
Problem 1 要你实现一个 Hamming space 上的 Approximate Nearest Neighbours data structure。
它基于两块内容：
- 课上讲过的 Baby ANN for Hamming distance；
- Tutorial 7 Problem 4 里的 doubling search reduction，把 Baby ANN 扩展成最终的 “Adult ANN”。
然后用 ANN Benchmarks 去比较你自己的实现和至少两个现有 ANN libraries，例如：
- Annoy；
- NNDescent / pynndescent。
为什么这里不展开代码
这题是明确的 programming / benchmark task。PDF 也说：
Solutions will only be provided for the theoretical questions.
因此这里不写
module.py、config.yml、fit、query
的实现细节。
复习时只需要记住：
- LSH 的目标是让近的点更容易 collide，远的点不容易 collide；
- Hamming LSH 的基本 hash 可以是随机选坐标；
- Baby ANN 通常对固定距离阈值工作；
- doubling search 用不同半径逐步找合适 scale；
- 代码 benchmark 本身不是理论证明重点。
Problem 1 用到的知识点
- Hamming distance；
- Approximate Nearest Neighbours；
- Locality-Sensitive Hashing；
- Baby ANN；
- doubling search；
- empirical benchmarking。
Problem 2: Knapsack 的 2-Approximation 与 Streaming 版本
题目
现在有预算
最大化总 bonus：
并满足预算约束：
目标不是精确最优，而是给一个 constant-factor approximation。
2.1 这是什么 NP-Hard 问题
这就是 Knapsack problem。
标准 Knapsack：
- 每个 item 有 weight
； - 每个 item 有 profit
； - 总 weight 不能超过
； - 最大化总 profit。
这里对应关系是：
| Knapsack | 本题 |
|---|---|
| weight |
cost |
| profit |
bonus |
| budget |
money |
| selected subset | bought magical items |
Knapsack 的 decision version 是 NP-complete，所以精确求解一般不能指望多项式时间，除非 P=NP。
2.2 贪心算法
算法：
- 丢掉所有太贵的 item：
这些 item 单独都买不起，不可能出现在任何 feasible solution 中。
- 对剩余 items 按 ratio 降序排序：
- 按这个顺序取最大的 feasible prefix，得到集合
。
也就是说，从 ratio 最高的 item 开始一直拿，直到下一个 item 会超预算。
- 如果存在下一个 item
，令：
否则：
- 返回
和 中总 bonus 更大的那个：
2.3 时间复杂度
逐步分析：
- 丢掉
的 items： ； - 对剩余
个 items 按 ratio 排序：
- 扫描 prefix，找到最大 feasible prefix：
； - 比较
与 ：如果前面顺手维护 ，就是 ；否则最多 。
总时间由排序主导：
2.4 为什么这是 2-approximation
核心工具是 Fractional Knapsack relaxation。
Fractional Knapsack 允许拿 item 的一部分。也就是说，每个 item 的选择变量从
放宽成
因为 fractional version 放宽了限制，所以：
Fractional Knapsack 的最优解就是按 ratio
从高到低拿：
- 前
个 item 完整拿； - 第
个 item 只拿一部分。
因此：
其中
而
当
所以：
再用简单不等式：
所以算法返回的解
因此这是 2-approximation：
2.5 为什么必须考虑
如果只返回 greedy prefix
构造反例：
- 预算是
，且 可以远大于 ； - 前
个 items：
ratio 是：
- 最后一个 item：
ratio 是：
所以 greedy order 会先拿前
若这些小 items 总价格
但最后一个大 item 单独可行，并且：
当
可以任意大。
所以
2.6 输出解的最大 cardinality 与表示空间
所有 item 的 cost 至少是 1，因此预算
个 items。
当然总共只有
单个 item
需要存：
- identifier
： bits； - cost
： bits； 个 characteristic values，每个在 ： bits。
所以单个 item 需要：
bits。
一个解最多有
2.7 Streaming 2-Approximation
现在 items 一个一个到来，不能全部存下来。目标是 one-pass streaming algorithm，最后仍然输出 2-approximation。
关键观察：
离线 greedy 算法只会真正看排序后前
个 valid items。
为什么是
- 每个 item cost 至少是 1；
- prefix
最多包含 个 items； - 还要看下一个 item
作为 ； - 所以最多需要前
个按 ratio 最好的 valid items。
Streaming algorithm 维护一个集合
里始终保存目前为止见过的、按 ratio 排名前 的 valid items； - valid 指
。
处理新 item
- 如果
，丢弃； - 如果
，加入 ； - 否则找出
中 ratio 最差的 item； - 如果新 item ratio 更好，就替换掉 ratio 最差的 item。
stream 结束后，在
因为
因此仍然是：
空间复杂度来自存
当
则
所以空间是：
Problem 2 用到的知识点
- Knapsack problem；
- NP-hardness；
- greedy by profit/weight ratio；
- Fractional Knapsack relaxation；
- approximation ratio；
- counterexample construction；
- streaming top-
maintenance； - bit complexity；
- one-pass streaming algorithm。
Problem 3:
Streaming Max Coverage with
题目
现在不考虑 item 价格，只能携带
目标不是最大化总 bonus，而是最大化至少有一个 bonus 的 characteristics 数量。
对 item
对选择集合
也就是
最优值：
这本质上是 Max Coverage 的 streaming approximation 版本。
3.1 如果知道
算法维护：
- 已选 items 集合
； - 已覆盖 characteristics 集合
。
初始化：
stream 中看到 item
如果：
； - 新覆盖至少为
则加入这个 item：
并更新覆盖集合：
3.2 空间复杂度
需要存：
- 选中的 item IDs：最多
个，每个 bits； - 已覆盖集合
：可用长度为 的 bit array，空间 ； - 数值
：需要 bits。
所以总空间：
如果不用 bit array，而用 list 存 covered characteristics，则可能写成
3.3 为什么是 2-approximation
首先，算法只有在
接下来证明：
分两种情况。
情况 1：算法选满了
每次加入 item 时，它至少贡献：
个新的 characteristics。
如果选满
情况 2：算法没有选满
考虑一个最优解
算法没选某个最优 item
如果把所有没被算法选中的最优 items 加进来，最多有
所以相对于最优解，算法最多损失：
因此：
两种情况都得到：
这就是 2-approximation。
3.4 如果只知道近似的
现实中不知道
算法把 threshold 改成：
选满
没选满时，每个没选的最优 item 的新贡献小于：
最多
因此：
所以 approximation factor 是：
因此：
3.5 不知道
因为
可以用几何序列猜测：
同时并行跑多个 threshold greedy 实例。
选择：
则一定存在某个
stream 结束后，比较所有实例得到的解：
返回
因为其中至少有一个实例使用了好 guess，所以最终输出也至少和它一样好。
若取常数级很小的
3.6 空间复杂度
单个实例空间：
因为：
所以：
实例数：
当
所以总空间：
官方给出的目标形式是：
这里的
3.7 当
如果
情况 1：
则：
空间变为：
情况 2：
代入：
或官方较松版本：
若
或使用较松表示时：
Problem 3 用到的知识点
- Max Coverage；
- streaming algorithm；
- threshold greedy；
- approximation proof by charging missing optimal items；
- guessing unknown optimum；
- geometric guesses；
- parallel streaming instances；
- bit array representation；
- space complexity analysis。
Problem 4: AMS / Tug-of-War Sketch 估计平方和
题目
每个 item
现在想估计总 magic energy：
但 stream 不是一个 item 一个 item 完整给出，而是一条条给出：
也就是说，每次只知道某个 item 在某个 characteristic 上的 bonus。
假设每个
所以 stream 长度：
4.1 算法应该做什么
算法从 4-wise independent hash family 中选：
维护一个 estimator accumulator：
每看到 stream item：
更新：
这里缺失符号
因为 hash 是对 item id 做的，而不是对 characteristic 做。
最终单个 estimator 输出：
多个 independent instances 必须 parallel 跑，因为题目明确说 stream 只能看一遍，不能 sequentially 多次扫描，也不能 different passes。
4.2 把
stream 里每个
所以：
按 item id 重新分组：
而：
所以：
这个形式非常重要：它就是 AMS / Tug-of-War sketch 对 frequency vector 的随机符号投影。
4.3 期望：为什么
单个 estimator：
展开：
取期望：
如果
所以：
如果
因此交叉项全部消失，只剩：
所以：
这说明
期望分析只需要：
4.4 方差分析：为什么需要 4-wise independence
为了控制 variance，需要看：
而：
展开后有四重求和：
这个期望什么时候不为 0？
如果四个下标中有某个下标只出现一次，比如
非零情况只有：
- 四个下标都相同；
- 两两配对，例如
这种 2+2 pattern。
要让这个四阶展开合法，需要：
也就是 4-wise independent hash family。
官方计算得到：
因此：
所以单个 estimator 的方差上界是：
这个方差和
4.5 最小 independence 是多少
期望分析需要：
方差分析需要：
所以本证明所需的最小值是：
4.6 应该用 median 还是 average
题目问最后输出应该是：
- median；
- average；
- either works。
答案是：
原因：
- Median trick 用来放大“已有粗精度 estimator 成功”的概率；
- 但这里单个 estimator 的 variance 很大，只有粗略常数级精度；
- 想要
高精度，必须降低 variance； - 独立 estimator 的平均值可以把 variance 降低
倍。
令
输出：
则：
因为 independent：
4.7 准确率与
用 Chebyshev：
代入方差：
要让失败概率至多
等价于：
所以：
这样得到：
也就是一个
4.8 空间复杂度
单个 estimator 需要存：
- 一个 4-wise independent hash function：
bits；
- accumulator
。
所以需要：
bits。
每个 estimator 的空间：
一共并行跑：
个 estimators。
所以总空间：
在
这就是经典的 Tug-of-War / AMS sketch，用来估计 frequency vector 的 squared 2-norm：
这里的 frequency 是：
Problem 4 用到的知识点
- streaming model；
- AMS / Tug-of-War sketch；
- estimating
； - 4-wise independent hashing；
- unbiased estimator；
- variance calculation；
- fourth-moment expansion；
- averaging independent estimators；
- Chebyshev inequality；
- space complexity of sketches。
Problem 5: Reservoir Sampling
题目
现在 stream 中有
目标是在 stream 结束时输出一个大小为
并且它在所有
也就是说，每个大小为
5.1 如果已知
如果提前知道 stream 长度
- 从
中均匀随机选 个不同 indices； - stream 到来时，如果当前 index 被选中，就存下该 item。
这样正确性直接来自“随机选择
空间：
- 存
个 indices： bits，因为 ； - 如果要存完整
个 items，每个 item 需要
bits。
所以空间：
5.2 不知道
当不知道
维护一个大小为
算法：
- 前
个 items 直接放入 ； - 对第
个 item： - 以概率
选择它进入 reservoir； - 如果被选择，则从
最终返回
5.3 空间复杂度
如果只存 item indices：
有 个位置； - 每个 index 需要
bits。
所以：
处理当前 item 还需要：
bits。
此外还要存：
- 当前时间
： ； - replacement index
： 。
总空间：
如果要完整存 reservoir 中的
5.4 每个 item 被保留的概率是
要证明 reservoir sampling 正确，先证明一个 invariant：
在处理完第
个 item 后，前 个 items 中每一个都以概率 在 中。
Base case:
前
Inductive step
假设处理完
处理第
新 item
新 item 以概率
被加入
所以它在处理完第
旧 item
固定一个旧 item
它在第
在第
- 新 item 没有进入 reservoir；或
- 新 item 进入了 reservoir，但替换掉的是其他位置，不是 item
的位置。
新 item 进入 reservoir 的概率是：
如果进入，它替换固定旧 item 的概率是：
所以旧 item 被替换掉的概率是：
旧 item 保留下来的概率是：
因此旧 item 最终还在
归纳完成。
所以处理完最终
这说明每个 item 的边际概率是正确的。更强地，这个算法输出的是 uniform
random
更强 invariant：
处理完第
个 item 后，reservoir 在所有来自前 个 items 的 -subsets 上均匀分布。
也就是对任意
都有：
base case
假设
固定任意
Case 1:
最终 reservoir 是
- 第
步 reservoir 已经是 ； - 第
个 item 没有被选入。
因此：
因为：
且：
所以：
Case 2:
令：
则
最终 reservoir 是
在前
对每个这样的旧 item
由归纳假设，它的概率是：
然后第
并且它要替换掉
所以：
化简：
两种情况都成立，所以 reservoir sampling 在每一步都保持 uniform
5.5 如何用随机 bit 实现
Bernoulli
第
方法：
- 均匀随机生成
- 若
则令
这样：
问题变成如何用 fair random bits 生成 uniform
如果
令：
抽
需要：
bits。
如果
使用 rejection sampling。
令：
抽
如果
一次成功概率是：
因为：
所以成功概率至少是
尝试次数是 geometric random variable，期望是：
每次尝试用
5.6 为什么算法解决问题
处理完 stream 长度
由上面的 invariant，每个 item 被包含概率都是：
标准 reservoir sampling 结论进一步保证：
每个大小为
的 subset 都以相同概率被输出。
因此该算法在不知道
Problem 5 用到的知识点
- reservoir sampling；
- one-pass streaming；
- induction proof；
- uniform random subset；
- Bernoulli sampling；
- rejection sampling；
- geometric random variable；
- expected random bits。
总结：Assignment 3 的复习重点
1. 可以略过的实现部分
Problem 1 是 Hamming ANN/LSH 的 programming + benchmark。复习理论考试时优先级低。知道它和 LSH、Baby ANN、doubling search 有关即可。
2. 必须掌握的理论结构
| 题目 | 关键结论 |
|---|---|
| Problem 2 | Knapsack greedy + next item gives 2-approximation |
| Problem 3 | Threshold greedy gives 2-approx for coverage; unknown optimum 用 geometric guesses |
| Problem 4 | AMS/Tug-of-War sketch gives unbiased |
| Problem 5 | Reservoir sampling solves unknown stream
length uniform |
3. 最值得背的公式
Knapsack 2-approx：
Max coverage threshold：
Approximate guess：
AMS estimator：
Unbiasedness：
Variance：
Averaging:
Reservoir sampling invariant：
4. 一句话记忆
Assignment 3 的主线是 streaming 和 approximation：不能存全部输入时，用 greedy threshold、sketching、random sampling 这些小空间工具，牺牲一点精确性来换取可证明的近似保证。