尧图网站建设 
MIT 6.854 高级算法Advanced Algorithms是研究生阶段一门非常有代表性的理论算法课。它不满足于让学生记住数据结构模板或背诵某个排序复杂度而是系统训练用随机化、线性规划、半定规划、流模型和稀疏性分析来处理复杂计算问题的能力。对于准备研究生入学、参与算法竞赛、做机器学习理论或底层系统优化的人来说这门课的内容能补上从“会写算法”到“会设计算法”的关键跨度。用户给出的材料里哈希、流算法、线性规划、半定规划、压缩感知这些词正是本课程最核心的五个主题板块。本文不是简单罗列课程目录而是围绕这五条技术主线把每个主题要解决什么问题、关键原理是什么、怎么验证理解、实际落地时容易踩哪些坑讲清楚最后再给出一套适合中文学习者使用这门双语字幕课程的学习路线。1. MIT 6.854 到底在教什么高级算法不只是“更难的数据结构”1.1 这门课程在研究生算法体系中的位置本科算法课通常围绕排序、搜索、图论、动态规划、分治这些经典问题展开重点训练的是“给定一个明确的问题设计一个正确且高效的算法”。到了研究生阶段问题的形态开始发生改变输入数据不一定能一次性读入内存约束条件可能不是整数而是连续区间目标函数也不是简单的最大最小路径而是需要在线性空间、半正定矩阵锥、稀疏信号这些更抽象的结构上做优化。MIT 6.854 正是站在这个分界点上的课程。它把“算法设计”从单一的确定性过程扩展成“随机化 优化建模 近似分析”的组合方法。课程中反复出现的不是某个数据结构的操作方法而是以下几类问题在数据无法全部存储时如何用少量空间得到近似统计结果。一个组合优化问题如何用连续优化工具来松弛再通过舍入恢复整数解。什么时候随机化能让算法更简单什么时候随机化只增加不确定性而没有收益。一个看似不可能完成的任务比如从远低于奈奎斯特率的采样中恢复信号在什么条件下变得可行。这门课的直接收益是理论能力提升但它的间接收益更大学生接触到的流式统计、哈希设计、凸优化建模、稀疏恢复几乎是现代数据库、推荐系统、网络监控、机器学习系统里的通用组件。1.2 五个核心主题之间的内在联系哈希、流算法、线性规划、半定规划、压缩感知看似各自独立实际上存在一条清晰的技术链路。哈希解决了“如何映射和查找”的问题是随机化算法的第一块基石。流算法建立在哈希之上用一组随机哈希函数把大规模数据流投影到固定大小的计数空间换取出误差可控的统计结果。线性规划把优化问题从离散结构放宽到连续凸集而对偶理论又给了算法设计者一个衡量近似解质量的标准。半定规划在线性规划的基础上把变量从向量扩展为矩阵用来处理那些需要刻画“内积关系”或“相似度结构”的组合问题。压缩感知则利用信号本身的稀疏结构从极少量线性测量中恢复原始信号其理论基础既包含矩阵分析也涉及凸优化中的 L1 范数最小化。可以用一句话串起这五个主题哈希给算法提供随机化工具流算法用随机化换空间线性规划用连续松弛逼近离散优化半定规划用矩阵锥处理更高阶结构压缩感知用稀疏先验打破采样限制。理解这条主线后学习每个主题时就不会觉得它们是一堆孤立技巧而是同一套算法思维在不同场景下的应用。1.3 适合谁学需要什么前置基础这门课适合以下几类读者已经掌握本科算法基础想进一步提升算法设计能力的研究生。准备从事机器学习、数据挖掘、网络系统、数据库内核方向的工程师。准备参加国内外算法竞赛但觉得竞赛题停留在技巧层面、想补充理论深度的人。对理论计算机科学感兴趣想了解近似算法、随机算法和凸优化关系的自学者。前置基础建议按以下表格自检缺哪一项就先补哪一项知识模块具体内容建议参考概率论期望、方差、Union Bound、Chernoff Bound、Markov 不等式《概率论及其应用》或《概率方法》前几章线性代数矩阵乘法、特征值、半正定矩阵、范数、奇异值分解《线性代数应该这样学》算法基础摊还分析、网络流、图算法、分治法、动态规划CLRS《算法导论》优化基础拉格朗日乘子、凸集、凸函数、KKT 条件Boyd《凸优化》前两三章如果这些内容只是“见过但要翻书才能想起来”完全可以边学边补。6.854 的特点是用到哪部分数学就现场推导哪部分而不是像纯数学课一样先建立完备的公理体系。上课时真正困难的地方不是某个公式看不懂而是如何判断“这个问题适合用哪一类算法工具”这正是教材和视频里反复示范的能力。2. 哈希与随机化从哈希表到算法设计中的哈希思维2.1 哈希为什么能成为算法设计的基本工具哈希的通俗解释是把任意长度的输入映射到固定长度的输出。在数据结构里这个输出通常是一个数组下标在算法设计里哈希可以把一个大集合的元素“打散”到多个桶中使得每个桶内元素尽量少在概率算法中哈希可以把一个复杂的对象压缩成一个短指纹用来判断相等性或做集合成员查询。MIT 6.854 讲哈希并不停留在“key 到 bucket 的映射”这个层面而是把它当作随机化算法的基础构件。课程里会讨论这样一个问题如果给定一个静态集合 S如何设计一个哈希函数使得查找任意元素时都只需要常数次比较且最坏情况可证明答案是两级哈希FKS 方案或完美哈希。第一级用哈希把元素分配到桶中第二级在每个桶内再使用一个独立哈希函数映射到无冲突的小表。这里的关键不是“怎么写得快”而是如何证明第二级表中冲突概率足够低以及为什么需要随机选择哈希函数而不是固定一个。2.2 冲突处理、负载因子与摊还分析哈希表最常见的实现是链地址法和开放地址法。链地址法把冲突元素挂在同一个桶的链表上开放地址法在冲突时探测下一个空位。两者的核心指标都是负载因子alpha n / m即元素数量与桶数量的比值。链地址法在alpha为常数时查找的期望时间是 O(1 alpha)。当alpha增长到接近 1 时开放地址法的性能会急剧下降因此动态哈希表通常会在alpha超过某个阈值时触发 rehash把所有元素重新分布到一个更大的表中。rehash 是一个典型的需要摊还分析的场景。每次 rehash 的代价是 O(n)但它不是每次插入都发生。如果能保证表大小按 2 倍增长则每个元素的摊还插入代价仍然是 O(1)。这就是为什么 C 的unordered_map、Java 的HashMap在设计时都选择“扩容 重新哈希”而不是放任冲突链无限增长。这里最容易犯的错误是把“平均 O(1)”当作“所有元素都 O(1)”。对于任意固定哈希函数都存在一组输入使所有元素落入同一个桶。解决方式不是祈祷输入“不坏”而是从一族哈希函数中随机选取一个使恶意输入无法事先针对你选择的函数构造冲突。这个思路在课程中会反复出现是理解随机化算法设计的核心。2.3 从确定性哈希到通用哈希与完美哈希通用哈希族Universal Hashing的定义可以这样记忆从哈希函数族 H 中随机选一个 h对任意两个不同的 key x 和 y冲突概率不超过 1/m。这个性质保证期望冲突数可控而且冲突概率只与表大小相关与具体输入无关。完美哈希则更进一步对静态集合 S构造一个哈希函数使得 S 中所有元素都不冲突查找时最坏情况 O(1)。两级哈希的构造思路如下第一级使用哈希函数 h把 S 中元素分布到 m 个桶中。设第 i 个桶内元素数为 n_i第二级为该桶分配 n_i^2 大小的内部表。从独立哈希族中为每个桶选择第二级函数直到该桶内无冲突。关键证明点是当第二级表大小为桶内元素数的平方时该桶内出现冲突的概率不超过 1/2因此尝试两次就能以高概率成功。这个证明过程比最终构造本身更有价值因为它展示了“随机化设计 概率分析”的范式。2.4 工程常见坑哈希冲突攻击与哈希函数误用哈希在实际项目里最常见的坑有三个。第一个坑是把哈希表当成无脑的“万能查找”工具。哈希表适合按键查找但不适合范围查询、前缀查询或有序遍历。如果需要这些操作应该选择红黑树或跳表而不是强行在哈希表的基础上做额外排序。第二个坑是忽略哈希碰撞攻击。公开网络的接口如果使用固定哈希函数来限制请求频率或分发用户请求攻击者可以构造大量哈希值相同的 key使哈希表退化成一个长链表直接把单次请求复杂度从 O(1) 拖到 O(n)。应对方式包括使用带随机种子的一次性哈希函数或对链表长度设置阈值并转换成树形结构。第三个坑是混淆哈希与加密摘要。MD5、SHA-1、SHA-256 是密码学哈希函数设计目标是抗碰撞而哈希表的哈希函数只需要分布均匀不需要防恶意构造。反过来把哈希表的哈希函数输出当作安全签名会带来严重安全风险。一个工程上的典型验证方法在你实现的哈希表上先插入随机数据观察链表的平均长度和最大长度再构造所有 key 都撞到同一位置的输入观察插入时间是否急剧上升。前者反映平均性能后者反映抗冲突能力。 ## 3. 流算法在无法存下数据时如何统计 ### 3.1 数据流模型的特殊性单次扫描、子线性空间 传统算法可以假设输入数据已经存在可以多次读取。流算法面对的模型不同数据以流的形式一个一个到达无法回退内存空间远小于数据规模通常只能存储 O(log n) 或 O(1) 个数字相关的信息。这个模型不是人为刁难而是真实场景路由器每秒处理数百万条网络包不可能把所有包的源地址都存在内存里广告系统每天处理几十亿次曝光不可能把每次曝光都落库后再统计。 在流模型下很多看似简单的问题变得不再平凡。比如“统计数据流中不同元素的数量基数”如果数据规模是 10 亿精确存储至少需要 10 亿量级的空间。流算法的目标是用远小于数据规模的空间给出误差可控的估计值。 ### 3.2 频次估计CountMin Sketch CountMin Sketch 是流算法中使用最广泛的技术之一用来估计每个元素在数据流中出现的次数。它的结构非常简单 - 初始化一个 d 行 w 列的计数器矩阵全部置 0。 - 选择 d 个独立的哈希函数每个哈希函数对应一行。 - 每来一个元素 x对每一行用对应的哈希函数计算桶下标然后该行对应计数器加 1。 - 查询元素 x 的频次时取 d 个哈希函数对应桶中计数的最小值。 CountMin Sketch 的查询结果永远不会小于真实值因为每个计数器都包含了冲突元素带来的增量。误差上界由 w 和 d 共同控制选择 w ceil(e / epsilon)、d ceil(ln(1 / delta)) 时查询结果以至少 1 - delta 的概率满足 text 估计值 - 真实值 epsilon * 总元素个数 CountMin Sketch 的核心价值在于它用几十个计数器的空间换来了对大规模数据流频次的可证明近似估计。实际使用时需要根据可接受的相对误差 epsilon 和失败概率 delta 反推矩阵尺寸。 python import math import random class CountMinSketch: def __init__(self, epsilon, delta): self.w int(math.ceil(math.e / epsilon)) self.d int(math.ceil(math.log(1.0 / delta))) self.table [[0] * self.w for _ in range(self.d)] self.hashers [self._make_hasher(i) for i in range(self.d)] def _make_hasher(self, seed): random.seed(seed) a random.randint(1, 1 30) b random.randint(0, 1 30) def h(x): return (a * hash(x) b) % (1 31) % self.w return h def add(self, key, delta1): for i in range(self.d): self.table[i][self.hashers[i](key)] delta def query(self, key): return min(self.table[i][self.hashers[i](key)] for i in range(self.d)) 这里要注意Python 的 hash() 对字符串是随机化的但同一个进程内是稳定的在真实系统里要使用可复现的哈希函数方便调试和跨节点合并。 CountMin Sketch 一个容易被忽略的优点是可合并性。两个 CountMin Sketch 如果使用相同的哈希函数和相同的矩阵尺寸它们的矩阵可以逐元素相加得到包含两个数据流汇总信息的 sketch。这个性质在分布式统计中非常关键比如多个机房各自统计后汇总全局数据。 ### 3.3 基数估计HyperLogLog 基数估计的目标是回答“数据流里有多少个不同的元素”。直观做法是使用一个集合但空间很快会耗尽。HyperLogLog 的思路非常巧妙把每个元素哈希成一个固定长度的位串记录所有位串中“从高位开始连续 0 的个数”的最大值。 如果哈希函数足够均匀那么出现连续 k 个 0 的概率是 2^-k因此当观测到最大前缀 0 长度为 k 时可以估计不同元素数量约为 2^k。这种原始估计在小数据量时偏差很大所以 HyperLogLog 会把输入分成 m 个桶每个桶内部记录局部最大前缀 0 长度最后用调和平均把各桶估计组合起来。 HyperLogLog 的实际误差近似为 1.04 / sqrt(m)。当 m 1024 时误差约 3.2%内存占用却只有几 KB。这正是流算法的魅力用极小的常数空间覆盖上亿级数据的统计需求。 ### 3.4 Top-K 与重型打击者Misra-Gries 算法 统计流中最频繁的元素是另一个经典问题。Misra-Gries 算法维护一个最多包含 k - 1 个候选元素的计数器表 - 新元素到来时如果它在表中计数器加 1。 - 如果不在表中且表未满加入表并设置计数为 1。 - 如果不在表中且表已满所有计数器减 1计数为 0 的项移除。 这个算法的直观解释是当内存不足时用“多对元素互相抵消”的方式来排除低频元素。最终表中保留的元素一定包含真正的 Top-K 元素但计数并不是元素的真实频次而是频次减去被抵掉的部分。Misra-Gries 的优点是单次扫描、空间 O(k)工程上常用于热点资源检测、热门商品统计、网络流量分析。 ### 3.5 精度与空间的权衡速查表 | 算法 | 解决的问题 | 空间复杂度 | 典型误差 | 适用场景 | | --- | --- | --- | --- | --- | | CountMin Sketch | 元素频次估计 | O((1/epsilon) * log(1/delta)) | 相对误差 epsilon | 频率统计、热点检测 | | HyperLogLog | 基数估计 | O(log log n) | 1.04 / sqrt(m) | UV 统计、独立访问数 | | Misra-Gries | Top-K 重型打击者 | O(k) | 无概率误差但估计值偏低 | 网络流量 TopK | | Bloom Filter | 集合成员判断 | O(k) 位 | 有假阳性无假阴性 | 缓存穿透过滤 | 实际项目中需要先明确“这是计数问题、去重问题、成员判断问题还是 TopK 问题”再选择对应 sketch不要把 CountMin 和 HyperLogLog 混为一谈。 ### 3.6 流算法的工程落地与验证方法 流算法在工程中落地时第一步是在离线数据上验证误差是否符合理论预期。建议用一份 100 万条以上的数据把真实统计结果与 sketch 输出做对比绘制误差分布图确认没有实现层面的 bug。 常见的实现 bug 包括多个哈希函数之间共享随机数导致哈希结果高度相关对不同流使用不同哈希函数导致 sketch 无法合并查询时对矩阵维度使用错误下标把整型计数器溢出当成不存在的低频场景。 验证时最重要的是计算相对误差而不是只看估计值是否和真实值“差不多”。相对误差超过理论范围说明实现或参数设置存在系统性问题。用以下脚本可以快速评估 CountMin 的误差 python import random from collections import Counter data [random.randint(1, 10000) for _ in range(1000000)] real Counter(data) cms CountMinSketch(epsilon0.01, delta0.05) for x in data: cms.add(x) errors [] for key, cnt in real.most_common(200): est cms.query(key) errors.append((est - cnt) / cnt) print(max relative error:, max(errors)) print(mean relative error:, sum(errors) / len(errors)) 如果最大相对误差远大于 epsilon需要检查哈希函数是否均匀、矩阵尺寸是否按公式计算、以及数据是否存在极端偏斜。 ## 4. 线性规划不只求解器更是算法设计语言 ### 4.1 线性规划的几何与代数基础 线性规划Linear Programming, LP解决的是这样一类问题在一组线性不等式约束下最小化或最大化一个线性目标函数。其标准形式可以写成 text minimize c^T x subject to A x b x 0 其中 x 是决策变量向量。线性规划有一个非常重要的几何性质可行域是一个凸多面体最优值如果在有限范围内一定可以在某个顶点处取到。这个性质让 LP 有成熟的算法基础也让 LP 成为组合优化问题松弛时的首选工具。 理解 LP 不需要先掌握晦涩的凸分析。可以把每个线性不等式理解为高维空间中的一张“切面”所有不等式的交集形成了一个高维多面体。目标函数是沿着某个方向在这个多面体上移动直到碰到边界。最优解一定出现在这些边界交点中的某个位置。 ### 4.2 单纯形法与内点法两种路线 求解 LP 有两个主流路线。单纯形法从一个顶点出发沿着多面体的边寻找更优的相邻顶点直到无法改进。它在实际运行中非常快但在最坏情况下可能遍历指数多个顶点。 内点法走的是另一条路从可行域内部出发沿着一条接近中心的方向逐步逼近最优解多项式时间收敛不会出现单纯形法那样的指数退化。现代求解器通常同时实现两种方法根据问题规模、稀疏性和数值特征自动选择。 这里要特别提醒一句不要试图手写内点法来解决实际工程问题。优化求解器是一个高度工程化的组件包含了预处理、稀疏矩阵分解、迭代精化、数值容差调整等大量细节。正确做法是掌握 LP 建模方法把问题转化成求解器能接受的形式把数值计算交给成熟工具。 ### 4.3 对偶理论为什么重要 对偶理论是 6.854 中贯穿多个主题的核心工具它的地位远不止“可以用另一个 LP 验证答案”这么简单。 对于原始问题Primal text minimize c^T x subject to A x b x 0 对偶问题Dual是 text maximize b^T y subject to A^T y c y 0 弱对偶定理说明对任意可行解 x 和 y都有 c^T x b^T y。也就是说对偶问题的任意可行解都给出原始问题的下界。强对偶定理进一步说明当两个问题都有可行解时最优解处的目标值相等。 对偶在算法设计中有三个直接用途 1. 验证解的最优性构造对偶可行解如果目标值相等则原始解已经最优。 2. 设计近似算法对组合优化问题做 LP 松弛后对偶问题往往能给一个很好的下界。这个下界不是拍脑袋猜的而是有数学保证。 3. 设计原对偶算法在增广路径、费用流、网络设计问题里原对偶方法经常能得到比直接求解 LP 更简单、更接近最优的组合算法。 ### 4.4 用 LP 设计组合优化算法最大流与最小割 最大流和最小割是理解 LP 对偶的最佳例子。最大流可以建模成一个 LP最大化从源点到汇点的总流量满足每条边的容量约束和每个中间节点的流量守恒。最小割可以理解为每种源汇割都有一个容量最小割是这些容量中的最小值。 这两个问题的关系恰好构成一个对偶对最大流的 LP 对偶就是最小割而最大流等于最小割的结论正是强对偶定理的一个特例。从这个角度看网络流中的许多经典结论本质上是 LP 对偶理论在组合图上的表现。 用同样的思路处理顶点覆盖问题原始整数规划很难但可以先松弛成 LP求解得到分数解再做随机舍入。每一步 LP 解的目标值提供最优解的下界随机舍入后的期望值可以证明不超过某个常数倍的最优值于是得到一个常数近似比算法。 ### 4.5 使用求解器时的数值问题和建模技巧 实际使用 LP 求解器时容易遇到以下问题 | 问题现象 | 可能原因 | 处理方式 | | --- | --- | --- | | 求解器报告无界 | 约束方向写反或缺失约束 | 检查每个变量的可行范围 | | 求解器报告不可行 | 约束之间互相矛盾 | 用 IIS 分析找出不可行约束子集 | | 结果出现 NaN 或很离谱 | 数值尺度差异太大 | 对约束和目标做归一化 | | 解不满足整数要求 | 忘记声明整数变量 | 检查变量类型是否设置为 integer 或 binary | 建模时还有一个常见坑决策变量之间如果存在强关联直接使用大 M 参数可能让求解器数值稳定性变差。建议优先使用 indicator 约束或 SOS 约束而不是把大 M 加到目标函数里。 在 6.854 的课程语境里LP 不只是“调包求解”的工具而是算法设计的语言。理解了 LP 和对偶后再去读近似算法的论文会发现很多近似比证明的第一步都是同一个动作写出整数规划松弛成 LP给出对偶做舍入分析。 ## 5. 半定规划从线性空间走向矩阵约束 ### 5.1 SDP 的定义和与 LP 的差异 半定规划Semidefinite Programming, SDP的变量不是向量而是一个对称矩阵 X。它的约束条件是 text minimize C · X subject to A_i · X b_i, i 1, ..., m X 是半正定矩阵 其中 C · X 表示两个矩阵的内积即 sum(C_ij * X_ij)。半正定约束 X 0 等价于对任意非零向量 v都有 v^T X v 0。 通俗地说LP 是在“向量构成的凸多面体”上做优化SDP 是在“矩阵构成的半正定锥”上做优化。SDP 的计算代价远高于 LP但它能表达更丰富的约束关系矩阵 X 可以理解为 n 个点的内积矩阵X_ij 直接刻画第 i 个点与第 j 个点之间的相似程度。 ### 5.2 为什么 SDP 能用于组合优化MaxCut 与 GW 算法 SDP 在理论计算机科学中最著名的应用是 MaxCut 问题。MaxCut 要求把一个图的顶点分成两组使得横跨两组的边数量最大。这个问题是 NP 难的但 Goemans 和 Williamson 在 1995 年给出了一个基于 SDP 的近似算法近似比约为 0.878。 GW 算法的思想非常优雅 1. 把每个顶点 i 映射成一个单位向量 v_i。 2. MaxCut 的目标变成最大化 sum((1 - v_i · v_j) / 2)。 3. 把这个松弛后的 SDP 问题求解出来。 4. 随机选一个超平面把向量分为两侧从而得到顶点分组。 这里的核心在于向量内积给“两个顶点是否应该分开”提供了一个比单纯二元取值更连续的表示。求解 SDP 得到的是最优连续解随机超平面舍入后期望割收益至少为最优解的 0.878 倍。 GW 算法说明了一个重要的方法论组合优化的难点在于整数约束而 SDP 可以用更丰富的几何结构来松弛整数约束松弛得越好舍入后损失越小。这个思想后来被推广到聚类、图分割、传感器网络定位等多个领域。 ### 5.3 SDP 的求解难度和工程现实 SDP 在理论上可以多项式时间内求解但工程实现远没有 LP 那么成熟。内点法求解一个 n 维变量的 SDP每次迭代需要处理一个与 n 相关的线性方程组内存和计算量都可能非常大。实际问题中当 n 超过几千时直接用通用 SDP 求解器就可能变得很慢。 因此工程上通常不直接把大规模问题丢给 SDP 求解器而是 - 先压缩问题规模利用低秩假设把半正定矩阵分解为 X V V^T其中 V 是 n*k 矩阵。 - 使用一阶方法比如交替方向乘子法ADMM避免维护完整的半正定矩阵。 - 使用随机投影在低维空间上近似求解再用近似解指导原始问题的迭代。 这些优化手段说明学习 SDP 不能只停留在“会调用 CVXPY”这一层还要理解问题的结构否则遇到大规模实例时无从下手。 ### 5.4 从 SDP 到实际应用的延伸 SDP 在更广泛的工程场景中也有实际价值。推荐系统中低秩矩阵补全可以写成核范数最小化的 SDP 松弛谱聚类中归一化拉普拉斯的特征值问题本质上和半正定松弛有关量子信息中的纠缠判断也需要通过 SDP 来验证某组测量结果是否违反可分离性条件。 6.854 课程里讲 SDP不是为了让每个学生都成为 SDP 领域专家而是让大家知道当问题里出现“相似度”“内积”“二次型”这些结构时SDP 是一个比 LP 更强的表达工具。它的代价更高但收益也可能更大。 ## 6. 压缩感知用稀疏性突破采样瓶颈 ### 6.1 传统采样定理与压缩感知的根本差别 传统信号处理依赖奈奎斯特-香农采样定理要完美重建一个最高频率为 f 的信号采样率至少为 2f。这个定理的前提是“不依赖任何信号先验信息”只要不知道信号长什么样就只能用均匀高频采样来保证信息不丢失。 压缩感知Compressed Sensing彻底改变了这个假设。它考虑的信号不是任意信号而是一个 n 维向量 x大部分分量为 0只有 k 个分量非零即 k-稀疏信号。如果信号本身足够稀疏就可以用 m 次线性测量恢复 x其中 m 远小于 n。 这个结论的反直觉之处在于我们采集的数据量甚至少于信号本身的维度却仍然能恢复出精确的信号。关键在于稀疏性先验 测量矩阵的特殊性质 非线性恢复算法三者配合。 ### 6.2 信号稀疏性与测量矩阵RIP 条件 压缩感知的数学模型是 text y A x 其中 x 是 n 维稀疏信号A 是 m*n 的测量矩阵y 是 m 维测量结果。这里 m 远小于 n所以方程是欠定方程理论上 x 有无穷多个解。 要让“最稀疏的解”成为唯一的真实解测量矩阵 A 必须满足限制等距性质Restricted Isometry Property, RIP text (1 - delta) ||x||_2^2 ||A x||_2^2 (1 delta) ||x||_2^2 对任意 k-稀疏向量 x 成立。RIP 要求的直观解释是A 在稀疏向量方向上近似保持范数不把不同稀疏向量映射到几乎相同的测量。 RIP 条件很难直接验证但随机矩阵以高概率满足 RIP。常见选择是随机高斯矩阵或随机伯努利矩阵。因此工程上不需要手工设计测量矩阵生成一个随机矩阵并用理论公式估算所需测量次数即可。 所需测量次数 m 的经验下限是 text m C * k * log(n / k) C 是一个常数因子与测量矩阵类型和恢复算法有关。这个公式说明测量次数和稀疏度 k 线性相关而和信号维度 n 只是对数关系。 ### 6.3 恢复算法L1 最小化与匹配追踪 已知 y 和 A恢复 x 最自然的想法是求解 text minimize ||x||_0 subject to A x y 其中 L0 范数表示非零元素个数。这个优化问题是 NP 难的不能直接求解。 压缩感知的关键突破是意识到在 RIP 条件下可以用 L1 范数最小化来替代 L0 最小化 text minimize ||x||_1 subject to A x y L2 范数会倾向于把所有元素都变到很小而不是集中到少数分量上L1 范数具有“在坐标轴上取得最小值”的几何特性天然促进稀疏解。这也是为什么 L1 正则化在机器学习中同样常用于特征选择。 工程中更常用的恢复算法是贪婪类算法例如正交匹配追踪Orthogonal Matching Pursuit, OMP。OMP 每次从测量矩阵中找出与当前残差最相关的列把它加入支撑集再用最小二乘求解支撑集上的系数然后更新残差。它的实现比 L1 最小化更简单迭代次数也容易控制。 python import numpy as np def omp(A, y, k): m, n A.shape x np.zeros(n) r y.copy() support [] for _ in range(k): corr A.T r idx np.argmax(np.abs(corr)) support.append(idx) A_s A[:, support] coef, _, _, _ np.linalg.lstsq(A_s, y, rcondNone) r y - A_s coef x[support] coef return x 这段代码的要点是每一步选择与残差最相关的列然后完全不修改已选支撑集之外的系数。实际使用中要注意支撑集里可能出现重复选择同一个索引需要去重否则 lstsq 会因为矩阵列线性相关而给出数值不稳定的结果。 ### 6.4 一个最小示例从随机测量恢复稀疏向量 用一个具体数字实验来验证压缩感知的流程 python import numpy as np n 256 k 10 m 64 # 生成 k-稀疏信号 x_true np.zeros(n) idx np.random.choice(n, k, replaceFalse) x_true[idx] np.random.randn(k) # 随机高斯测量矩阵 A np.random.randn(m, n) / np.sqrt(m) y A x_true # 使用 OMP 恢复 x_est omp(A, y, k) print(recovery error:, np.linalg.norm(x_est - x_true) / np.linalg.norm(x_true)) 在 m 64、n 256、k 10 的情况下恢复误差通常可以降到 1e-10 以下。如果 k 增大到 40 或 50上述参数下的恢复就会失败因为测量次数不足。这个实验能直观验证“m 与 k 线性相关”的理论结论。 ### 6.5 压缩感知的工程前提与常见误区 压缩感知不是一个通用信号处理黑盒它需要三个条件同时成立 1. 信号在某个基下确实稀疏。很多自然信号在时域不稀疏但在小波基或傅里叶基下稀疏需要先做变换。 2. 测量矩阵满足 RIP 或至少与稀疏基不相关。随机矩阵和大多数正交基都有很好的不相关性。 3. 噪声不能太大。当测量含噪声时恢复问题变为鲁棒 L1 最小化误差上界与噪声能量成正比。 工程中常见的误区是 - 没有先验证信号的稀疏性直接套压缩感知结果恢复质量很差。 - 把压缩感知理解成“无损压缩方案”实际上它在测量环节就把信号压缩了恢复结果通常是有损或近似的。 - 对含噪数据不做任何处理直接用无噪声模型恢复。 - 使用确定性稀疏矩阵时没有验证 RIP只因为某篇论文中说某种矩阵“可以”就认为所有矩阵都可以。 ## 7. 学习 MIT 6.854 的实践路线与排错清单 ### 7.1 学习前的知识自检清单 开始看视频前先用下面的清单做一次自检 | 检查项 | 状态 | 如果不过关怎么办 | | --- | --- | --- | | 能独立写出快排并做摊还分析 | 是/否 | 先复习 CLRS 第 7 章 | | 理解 Chernoff Bound 的含义 | 是/否 | 先补概率论重点看“尾概率”一节 | | 能写出最大流的 Ford-Fulkerson 算法 | 是/否 | 先做一次网络流专题练习 | | 知道矩阵特征值和半正定矩阵的定义 | 是/否 | 线性代数补第二章相关部分 | | 会使用 Python 的 NumPy 做矩阵运算 | 是/否 | 先跑 30 分钟快速教程 | 自检不必全部通过但对角线都是“否”时直接开始 6.854 会很吃力。建议花一到两周补齐最薄弱的两项。 ### 7.2 双语字幕课程的高效学法 使用中英双语字幕课程时最容易犯的错误是把视频当“听力材料”或“刷剧”一样看。更有效的方式是分段看 1. 每一讲开始前先看讲义或课程主页的幻灯片从中提取本节课的关键定理和结论。 2. 播放视频时先关掉中文只看英文字幕迫使自己理解英文术语遇到实在卡住的地方再开中文对照。 3. 每看完一个主题用 5 分钟把黑板上或幻灯片里的核心证明复述一遍。复述不是背字幕而是用自己的话解释“为什么要引入这个引理”“这一步放缩的意义是什么”。 4. 在关键定理处暂停尝试在视频推导之前自己猜下一步。猜错了也没关系这个猜测过程本身就是建立理解的过程。 textarea 6.854 属于快节奏的研究生课程不要试图一次看完一整讲。建议每个视频拆成 20 分钟一个段落配合讲义、笔记和课后习题交叉进行。学习效果取决于你重写了多少遍证明而不是看完多少分钟视频。 ### 7.3 主题练习与复现方法 每个主题都要做一次“理论 实验”的双重验证。理论任务是从零证明一遍课程中的核心定理实验任务是用 Python 或 C 实现一个小规模算法并验证结果。 具体来说 - 哈希主题实现一个带 rehash 的哈希表并构造一组冲突输入验证最坏情况确实退化。 - 流算法主题用 CountMin Sketch 统计一个英文小说文件的单词频次和 collections.Counter 对比。 - 线性规划主题用 CVXPY 建模一个最小生成树或顶点覆盖的 LP 松弛观察分数解和整数解的差距。 - 半定规划主题实现 GW 算法在随机图上运行检查割收益是否接近理论近似比。 - 压缩感知主题用 OMP 和 L1 方法分别恢复稀疏信号绘制恢复误差与测量次数 m 的关系曲线。 这些实验不需要做大系统只需要能回答一个问题课程里的理论结论在我自己的数据集上是否成立。 ### 7.4 五大主题的常见误区排查表 | 主题 | 常见误区 | 正确认识 | 排查方式 | | --- | --- | --- | --- | | 哈希 | 认为哈希表最坏情况 O(1) | 哈希表是期望 O(1)最坏 O(n) | 对固定哈希函数构造冲突输入测试 | | 流算法 | 以为 CountMin 不给真实值上界 | CountMin 查询结果不小于真实频率 | 用真实频率对比查询结果 | | 线性规划 | 把对偶单纯当作数学练习 | 对偶是算法设计和近似比证明工具 | 用对偶构造顶点覆盖的 LP 下界 | | 半定规划 | 把 SDP 当“高级调包”不知道为什么要松弛 | SDP 的价值在于表达内积结构 舍入分析 | 重写 GW 算法的松弛和舍入步骤 | | 压缩感知 | 忽略稀疏先验什么信号都敢恢复 | 不稀疏的信号无法用压缩感知理论保证 | 在非稀疏信号上观察恢复失败现象 | ### 7.5 从课程到研究和工程实践的扩展路径 学完 6.854 后可以沿着以下方向深入 - 如果对随机算法感兴趣读《Probability and Computing》和《Randomized Algorithms》重点研究随机游走和马尔可夫链蒙特卡洛方法。 - 如果对优化感兴趣读 Boyd《Convex Optimization》把 SDP 的算法实现和凸优化理论补齐。 - 如果对大数据系统感兴趣把 CountMin、HyperLogLog、Bloom Filter 等 sketch 用在你熟悉的数据存储系统里实践线上数据统计。 - 如果对理论计算机科学感兴趣继续读近似算法经典教材《The Design of Approximation Algorithms》其中大量章节直接使用课程里讲过的 LP 对偶和 SDP 松弛。 这门课最重要的不是记住某个算法的具体步骤而是建立“问题 - 松弛 - 求解 - 舍入 - 证明”的算法设计思维链。带着这条思维链去读论文、写系统、做实验会在很多看似不相关的问题里发现相同的底层模型。 实际项目中最值得记住的一点是高级算法的价值不在课堂证明本身而在于它能帮你在工程中判断哪些问题有理论下界、哪些问题可以近似、哪些空间换精度值得做。把哈希、流算法、线性规划、半定规划、压缩感知当成一套工具箱而不是五门独立课程才是学习 MIT 6.854 最大的收获。 MIT 6.854高级算法：从哈希到压缩感知的系统学习路线
MIT 6.854 高级算法Advanced Algorithms是研究生阶段一门非常有代表性的理论算法课。它不满足于让学生记住数据结构模板或背诵某个排序复杂度而是系统训练用随机化、线性规划、半定规划、流模型和稀疏性分析来处理复杂计算问题的能力。对于准备研究生入学、参与算法竞赛、做机器学习理论或底层系统优化的人来说这门课的内容能补上从“会写算法”到“会设计算法”的关键跨度。用户给出的材料里哈希、流算法、线性规划、半定规划、压缩感知这些词正是本课程最核心的五个主题板块。本文不是简单罗列课程目录而是围绕这五条技术主线把每个主题要解决什么问题、关键原理是什么、怎么验证理解、实际落地时容易踩哪些坑讲清楚最后再给出一套适合中文学习者使用这门双语字幕课程的学习路线。1. MIT 6.854 到底在教什么高级算法不只是“更难的数据结构”1.1 这门课程在研究生算法体系中的位置本科算法课通常围绕排序、搜索、图论、动态规划、分治这些经典问题展开重点训练的是“给定一个明确的问题设计一个正确且高效的算法”。到了研究生阶段问题的形态开始发生改变输入数据不一定能一次性读入内存约束条件可能不是整数而是连续区间目标函数也不是简单的最大最小路径而是需要在线性空间、半正定矩阵锥、稀疏信号这些更抽象的结构上做优化。MIT 6.854 正是站在这个分界点上的课程。它把“算法设计”从单一的确定性过程扩展成“随机化 优化建模 近似分析”的组合方法。课程中反复出现的不是某个数据结构的操作方法而是以下几类问题在数据无法全部存储时如何用少量空间得到近似统计结果。一个组合优化问题如何用连续优化工具来松弛再通过舍入恢复整数解。什么时候随机化能让算法更简单什么时候随机化只增加不确定性而没有收益。一个看似不可能完成的任务比如从远低于奈奎斯特率的采样中恢复信号在什么条件下变得可行。这门课的直接收益是理论能力提升但它的间接收益更大学生接触到的流式统计、哈希设计、凸优化建模、稀疏恢复几乎是现代数据库、推荐系统、网络监控、机器学习系统里的通用组件。1.2 五个核心主题之间的内在联系哈希、流算法、线性规划、半定规划、压缩感知看似各自独立实际上存在一条清晰的技术链路。哈希解决了“如何映射和查找”的问题是随机化算法的第一块基石。流算法建立在哈希之上用一组随机哈希函数把大规模数据流投影到固定大小的计数空间换取出误差可控的统计结果。线性规划把优化问题从离散结构放宽到连续凸集而对偶理论又给了算法设计者一个衡量近似解质量的标准。半定规划在线性规划的基础上把变量从向量扩展为矩阵用来处理那些需要刻画“内积关系”或“相似度结构”的组合问题。压缩感知则利用信号本身的稀疏结构从极少量线性测量中恢复原始信号其理论基础既包含矩阵分析也涉及凸优化中的 L1 范数最小化。可以用一句话串起这五个主题哈希给算法提供随机化工具流算法用随机化换空间线性规划用连续松弛逼近离散优化半定规划用矩阵锥处理更高阶结构压缩感知用稀疏先验打破采样限制。理解这条主线后学习每个主题时就不会觉得它们是一堆孤立技巧而是同一套算法思维在不同场景下的应用。1.3 适合谁学需要什么前置基础这门课适合以下几类读者已经掌握本科算法基础想进一步提升算法设计能力的研究生。准备从事机器学习、数据挖掘、网络系统、数据库内核方向的工程师。准备参加国内外算法竞赛但觉得竞赛题停留在技巧层面、想补充理论深度的人。对理论计算机科学感兴趣想了解近似算法、随机算法和凸优化关系的自学者。前置基础建议按以下表格自检缺哪一项就先补哪一项知识模块具体内容建议参考概率论期望、方差、Union Bound、Chernoff Bound、Markov 不等式《概率论及其应用》或《概率方法》前几章线性代数矩阵乘法、特征值、半正定矩阵、范数、奇异值分解《线性代数应该这样学》算法基础摊还分析、网络流、图算法、分治法、动态规划CLRS《算法导论》优化基础拉格朗日乘子、凸集、凸函数、KKT 条件Boyd《凸优化》前两三章如果这些内容只是“见过但要翻书才能想起来”完全可以边学边补。6.854 的特点是用到哪部分数学就现场推导哪部分而不是像纯数学课一样先建立完备的公理体系。上课时真正困难的地方不是某个公式看不懂而是如何判断“这个问题适合用哪一类算法工具”这正是教材和视频里反复示范的能力。2. 哈希与随机化从哈希表到算法设计中的哈希思维2.1 哈希为什么能成为算法设计的基本工具哈希的通俗解释是把任意长度的输入映射到固定长度的输出。在数据结构里这个输出通常是一个数组下标在算法设计里哈希可以把一个大集合的元素“打散”到多个桶中使得每个桶内元素尽量少在概率算法中哈希可以把一个复杂的对象压缩成一个短指纹用来判断相等性或做集合成员查询。MIT 6.854 讲哈希并不停留在“key 到 bucket 的映射”这个层面而是把它当作随机化算法的基础构件。课程里会讨论这样一个问题如果给定一个静态集合 S如何设计一个哈希函数使得查找任意元素时都只需要常数次比较且最坏情况可证明答案是两级哈希FKS 方案或完美哈希。第一级用哈希把元素分配到桶中第二级在每个桶内再使用一个独立哈希函数映射到无冲突的小表。这里的关键不是“怎么写得快”而是如何证明第二级表中冲突概率足够低以及为什么需要随机选择哈希函数而不是固定一个。2.2 冲突处理、负载因子与摊还分析哈希表最常见的实现是链地址法和开放地址法。链地址法把冲突元素挂在同一个桶的链表上开放地址法在冲突时探测下一个空位。两者的核心指标都是负载因子alpha n / m即元素数量与桶数量的比值。链地址法在alpha为常数时查找的期望时间是 O(1 alpha)。当alpha增长到接近 1 时开放地址法的性能会急剧下降因此动态哈希表通常会在alpha超过某个阈值时触发 rehash把所有元素重新分布到一个更大的表中。rehash 是一个典型的需要摊还分析的场景。每次 rehash 的代价是 O(n)但它不是每次插入都发生。如果能保证表大小按 2 倍增长则每个元素的摊还插入代价仍然是 O(1)。这就是为什么 C 的unordered_map、Java 的HashMap在设计时都选择“扩容 重新哈希”而不是放任冲突链无限增长。这里最容易犯的错误是把“平均 O(1)”当作“所有元素都 O(1)”。对于任意固定哈希函数都存在一组输入使所有元素落入同一个桶。解决方式不是祈祷输入“不坏”而是从一族哈希函数中随机选取一个使恶意输入无法事先针对你选择的函数构造冲突。这个思路在课程中会反复出现是理解随机化算法设计的核心。2.3 从确定性哈希到通用哈希与完美哈希通用哈希族Universal Hashing的定义可以这样记忆从哈希函数族 H 中随机选一个 h对任意两个不同的 key x 和 y冲突概率不超过 1/m。这个性质保证期望冲突数可控而且冲突概率只与表大小相关与具体输入无关。完美哈希则更进一步对静态集合 S构造一个哈希函数使得 S 中所有元素都不冲突查找时最坏情况 O(1)。两级哈希的构造思路如下第一级使用哈希函数 h把 S 中元素分布到 m 个桶中。设第 i 个桶内元素数为 n_i第二级为该桶分配 n_i^2 大小的内部表。从独立哈希族中为每个桶选择第二级函数直到该桶内无冲突。关键证明点是当第二级表大小为桶内元素数的平方时该桶内出现冲突的概率不超过 1/2因此尝试两次就能以高概率成功。这个证明过程比最终构造本身更有价值因为它展示了“随机化设计 概率分析”的范式。2.4 工程常见坑哈希冲突攻击与哈希函数误用哈希在实际项目里最常见的坑有三个。第一个坑是把哈希表当成无脑的“万能查找”工具。哈希表适合按键查找但不适合范围查询、前缀查询或有序遍历。如果需要这些操作应该选择红黑树或跳表而不是强行在哈希表的基础上做额外排序。第二个坑是忽略哈希碰撞攻击。公开网络的接口如果使用固定哈希函数来限制请求频率或分发用户请求攻击者可以构造大量哈希值相同的 key使哈希表退化成一个长链表直接把单次请求复杂度从 O(1) 拖到 O(n)。应对方式包括使用带随机种子的一次性哈希函数或对链表长度设置阈值并转换成树形结构。第三个坑是混淆哈希与加密摘要。MD5、SHA-1、SHA-256 是密码学哈希函数设计目标是抗碰撞而哈希表的哈希函数只需要分布均匀不需要防恶意构造。反过来把哈希表的哈希函数输出当作安全签名会带来严重安全风险。一个工程上的典型验证方法在你实现的哈希表上先插入随机数据观察链表的平均长度和最大长度再构造所有 key 都撞到同一位置的输入观察插入时间是否急剧上升。前者反映平均性能后者反映抗冲突能力。 ## 3. 流算法在无法存下数据时如何统计 ### 3.1 数据流模型的特殊性单次扫描、子线性空间 传统算法可以假设输入数据已经存在可以多次读取。流算法面对的模型不同数据以流的形式一个一个到达无法回退内存空间远小于数据规模通常只能存储 O(log n) 或 O(1) 个数字相关的信息。这个模型不是人为刁难而是真实场景路由器每秒处理数百万条网络包不可能把所有包的源地址都存在内存里广告系统每天处理几十亿次曝光不可能把每次曝光都落库后再统计。 在流模型下很多看似简单的问题变得不再平凡。比如“统计数据流中不同元素的数量基数”如果数据规模是 10 亿精确存储至少需要 10 亿量级的空间。流算法的目标是用远小于数据规模的空间给出误差可控的估计值。 ### 3.2 频次估计CountMin Sketch CountMin Sketch 是流算法中使用最广泛的技术之一用来估计每个元素在数据流中出现的次数。它的结构非常简单 - 初始化一个 d 行 w 列的计数器矩阵全部置 0。 - 选择 d 个独立的哈希函数每个哈希函数对应一行。 - 每来一个元素 x对每一行用对应的哈希函数计算桶下标然后该行对应计数器加 1。 - 查询元素 x 的频次时取 d 个哈希函数对应桶中计数的最小值。 CountMin Sketch 的查询结果永远不会小于真实值因为每个计数器都包含了冲突元素带来的增量。误差上界由 w 和 d 共同控制选择 w ceil(e / epsilon)、d ceil(ln(1 / delta)) 时查询结果以至少 1 - delta 的概率满足 text 估计值 - 真实值 epsilon * 总元素个数 CountMin Sketch 的核心价值在于它用几十个计数器的空间换来了对大规模数据流频次的可证明近似估计。实际使用时需要根据可接受的相对误差 epsilon 和失败概率 delta 反推矩阵尺寸。 python import math import random class CountMinSketch: def __init__(self, epsilon, delta): self.w int(math.ceil(math.e / epsilon)) self.d int(math.ceil(math.log(1.0 / delta))) self.table [[0] * self.w for _ in range(self.d)] self.hashers [self._make_hasher(i) for i in range(self.d)] def _make_hasher(self, seed): random.seed(seed) a random.randint(1, 1 30) b random.randint(0, 1 30) def h(x): return (a * hash(x) b) % (1 31) % self.w return h def add(self, key, delta1): for i in range(self.d): self.table[i][self.hashers[i](key)] delta def query(self, key): return min(self.table[i][self.hashers[i](key)] for i in range(self.d)) 这里要注意Python 的 hash() 对字符串是随机化的但同一个进程内是稳定的在真实系统里要使用可复现的哈希函数方便调试和跨节点合并。 CountMin Sketch 一个容易被忽略的优点是可合并性。两个 CountMin Sketch 如果使用相同的哈希函数和相同的矩阵尺寸它们的矩阵可以逐元素相加得到包含两个数据流汇总信息的 sketch。这个性质在分布式统计中非常关键比如多个机房各自统计后汇总全局数据。 ### 3.3 基数估计HyperLogLog 基数估计的目标是回答“数据流里有多少个不同的元素”。直观做法是使用一个集合但空间很快会耗尽。HyperLogLog 的思路非常巧妙把每个元素哈希成一个固定长度的位串记录所有位串中“从高位开始连续 0 的个数”的最大值。 如果哈希函数足够均匀那么出现连续 k 个 0 的概率是 2^-k因此当观测到最大前缀 0 长度为 k 时可以估计不同元素数量约为 2^k。这种原始估计在小数据量时偏差很大所以 HyperLogLog 会把输入分成 m 个桶每个桶内部记录局部最大前缀 0 长度最后用调和平均把各桶估计组合起来。 HyperLogLog 的实际误差近似为 1.04 / sqrt(m)。当 m 1024 时误差约 3.2%内存占用却只有几 KB。这正是流算法的魅力用极小的常数空间覆盖上亿级数据的统计需求。 ### 3.4 Top-K 与重型打击者Misra-Gries 算法 统计流中最频繁的元素是另一个经典问题。Misra-Gries 算法维护一个最多包含 k - 1 个候选元素的计数器表 - 新元素到来时如果它在表中计数器加 1。 - 如果不在表中且表未满加入表并设置计数为 1。 - 如果不在表中且表已满所有计数器减 1计数为 0 的项移除。 这个算法的直观解释是当内存不足时用“多对元素互相抵消”的方式来排除低频元素。最终表中保留的元素一定包含真正的 Top-K 元素但计数并不是元素的真实频次而是频次减去被抵掉的部分。Misra-Gries 的优点是单次扫描、空间 O(k)工程上常用于热点资源检测、热门商品统计、网络流量分析。 ### 3.5 精度与空间的权衡速查表 | 算法 | 解决的问题 | 空间复杂度 | 典型误差 | 适用场景 | | --- | --- | --- | --- | --- | | CountMin Sketch | 元素频次估计 | O((1/epsilon) * log(1/delta)) | 相对误差 epsilon | 频率统计、热点检测 | | HyperLogLog | 基数估计 | O(log log n) | 1.04 / sqrt(m) | UV 统计、独立访问数 | | Misra-Gries | Top-K 重型打击者 | O(k) | 无概率误差但估计值偏低 | 网络流量 TopK | | Bloom Filter | 集合成员判断 | O(k) 位 | 有假阳性无假阴性 | 缓存穿透过滤 | 实际项目中需要先明确“这是计数问题、去重问题、成员判断问题还是 TopK 问题”再选择对应 sketch不要把 CountMin 和 HyperLogLog 混为一谈。 ### 3.6 流算法的工程落地与验证方法 流算法在工程中落地时第一步是在离线数据上验证误差是否符合理论预期。建议用一份 100 万条以上的数据把真实统计结果与 sketch 输出做对比绘制误差分布图确认没有实现层面的 bug。 常见的实现 bug 包括多个哈希函数之间共享随机数导致哈希结果高度相关对不同流使用不同哈希函数导致 sketch 无法合并查询时对矩阵维度使用错误下标把整型计数器溢出当成不存在的低频场景。 验证时最重要的是计算相对误差而不是只看估计值是否和真实值“差不多”。相对误差超过理论范围说明实现或参数设置存在系统性问题。用以下脚本可以快速评估 CountMin 的误差 python import random from collections import Counter data [random.randint(1, 10000) for _ in range(1000000)] real Counter(data) cms CountMinSketch(epsilon0.01, delta0.05) for x in data: cms.add(x) errors [] for key, cnt in real.most_common(200): est cms.query(key) errors.append((est - cnt) / cnt) print(max relative error:, max(errors)) print(mean relative error:, sum(errors) / len(errors)) 如果最大相对误差远大于 epsilon需要检查哈希函数是否均匀、矩阵尺寸是否按公式计算、以及数据是否存在极端偏斜。 ## 4. 线性规划不只求解器更是算法设计语言 ### 4.1 线性规划的几何与代数基础 线性规划Linear Programming, LP解决的是这样一类问题在一组线性不等式约束下最小化或最大化一个线性目标函数。其标准形式可以写成 text minimize c^T x subject to A x b x 0 其中 x 是决策变量向量。线性规划有一个非常重要的几何性质可行域是一个凸多面体最优值如果在有限范围内一定可以在某个顶点处取到。这个性质让 LP 有成熟的算法基础也让 LP 成为组合优化问题松弛时的首选工具。 理解 LP 不需要先掌握晦涩的凸分析。可以把每个线性不等式理解为高维空间中的一张“切面”所有不等式的交集形成了一个高维多面体。目标函数是沿着某个方向在这个多面体上移动直到碰到边界。最优解一定出现在这些边界交点中的某个位置。 ### 4.2 单纯形法与内点法两种路线 求解 LP 有两个主流路线。单纯形法从一个顶点出发沿着多面体的边寻找更优的相邻顶点直到无法改进。它在实际运行中非常快但在最坏情况下可能遍历指数多个顶点。 内点法走的是另一条路从可行域内部出发沿着一条接近中心的方向逐步逼近最优解多项式时间收敛不会出现单纯形法那样的指数退化。现代求解器通常同时实现两种方法根据问题规模、稀疏性和数值特征自动选择。 这里要特别提醒一句不要试图手写内点法来解决实际工程问题。优化求解器是一个高度工程化的组件包含了预处理、稀疏矩阵分解、迭代精化、数值容差调整等大量细节。正确做法是掌握 LP 建模方法把问题转化成求解器能接受的形式把数值计算交给成熟工具。 ### 4.3 对偶理论为什么重要 对偶理论是 6.854 中贯穿多个主题的核心工具它的地位远不止“可以用另一个 LP 验证答案”这么简单。 对于原始问题Primal text minimize c^T x subject to A x b x 0 对偶问题Dual是 text maximize b^T y subject to A^T y c y 0 弱对偶定理说明对任意可行解 x 和 y都有 c^T x b^T y。也就是说对偶问题的任意可行解都给出原始问题的下界。强对偶定理进一步说明当两个问题都有可行解时最优解处的目标值相等。 对偶在算法设计中有三个直接用途 1. 验证解的最优性构造对偶可行解如果目标值相等则原始解已经最优。 2. 设计近似算法对组合优化问题做 LP 松弛后对偶问题往往能给一个很好的下界。这个下界不是拍脑袋猜的而是有数学保证。 3. 设计原对偶算法在增广路径、费用流、网络设计问题里原对偶方法经常能得到比直接求解 LP 更简单、更接近最优的组合算法。 ### 4.4 用 LP 设计组合优化算法最大流与最小割 最大流和最小割是理解 LP 对偶的最佳例子。最大流可以建模成一个 LP最大化从源点到汇点的总流量满足每条边的容量约束和每个中间节点的流量守恒。最小割可以理解为每种源汇割都有一个容量最小割是这些容量中的最小值。 这两个问题的关系恰好构成一个对偶对最大流的 LP 对偶就是最小割而最大流等于最小割的结论正是强对偶定理的一个特例。从这个角度看网络流中的许多经典结论本质上是 LP 对偶理论在组合图上的表现。 用同样的思路处理顶点覆盖问题原始整数规划很难但可以先松弛成 LP求解得到分数解再做随机舍入。每一步 LP 解的目标值提供最优解的下界随机舍入后的期望值可以证明不超过某个常数倍的最优值于是得到一个常数近似比算法。 ### 4.5 使用求解器时的数值问题和建模技巧 实际使用 LP 求解器时容易遇到以下问题 | 问题现象 | 可能原因 | 处理方式 | | --- | --- | --- | | 求解器报告无界 | 约束方向写反或缺失约束 | 检查每个变量的可行范围 | | 求解器报告不可行 | 约束之间互相矛盾 | 用 IIS 分析找出不可行约束子集 | | 结果出现 NaN 或很离谱 | 数值尺度差异太大 | 对约束和目标做归一化 | | 解不满足整数要求 | 忘记声明整数变量 | 检查变量类型是否设置为 integer 或 binary | 建模时还有一个常见坑决策变量之间如果存在强关联直接使用大 M 参数可能让求解器数值稳定性变差。建议优先使用 indicator 约束或 SOS 约束而不是把大 M 加到目标函数里。 在 6.854 的课程语境里LP 不只是“调包求解”的工具而是算法设计的语言。理解了 LP 和对偶后再去读近似算法的论文会发现很多近似比证明的第一步都是同一个动作写出整数规划松弛成 LP给出对偶做舍入分析。 ## 5. 半定规划从线性空间走向矩阵约束 ### 5.1 SDP 的定义和与 LP 的差异 半定规划Semidefinite Programming, SDP的变量不是向量而是一个对称矩阵 X。它的约束条件是 text minimize C · X subject to A_i · X b_i, i 1, ..., m X 是半正定矩阵 其中 C · X 表示两个矩阵的内积即 sum(C_ij * X_ij)。半正定约束 X 0 等价于对任意非零向量 v都有 v^T X v 0。 通俗地说LP 是在“向量构成的凸多面体”上做优化SDP 是在“矩阵构成的半正定锥”上做优化。SDP 的计算代价远高于 LP但它能表达更丰富的约束关系矩阵 X 可以理解为 n 个点的内积矩阵X_ij 直接刻画第 i 个点与第 j 个点之间的相似程度。 ### 5.2 为什么 SDP 能用于组合优化MaxCut 与 GW 算法 SDP 在理论计算机科学中最著名的应用是 MaxCut 问题。MaxCut 要求把一个图的顶点分成两组使得横跨两组的边数量最大。这个问题是 NP 难的但 Goemans 和 Williamson 在 1995 年给出了一个基于 SDP 的近似算法近似比约为 0.878。 GW 算法的思想非常优雅 1. 把每个顶点 i 映射成一个单位向量 v_i。 2. MaxCut 的目标变成最大化 sum((1 - v_i · v_j) / 2)。 3. 把这个松弛后的 SDP 问题求解出来。 4. 随机选一个超平面把向量分为两侧从而得到顶点分组。 这里的核心在于向量内积给“两个顶点是否应该分开”提供了一个比单纯二元取值更连续的表示。求解 SDP 得到的是最优连续解随机超平面舍入后期望割收益至少为最优解的 0.878 倍。 GW 算法说明了一个重要的方法论组合优化的难点在于整数约束而 SDP 可以用更丰富的几何结构来松弛整数约束松弛得越好舍入后损失越小。这个思想后来被推广到聚类、图分割、传感器网络定位等多个领域。 ### 5.3 SDP 的求解难度和工程现实 SDP 在理论上可以多项式时间内求解但工程实现远没有 LP 那么成熟。内点法求解一个 n 维变量的 SDP每次迭代需要处理一个与 n 相关的线性方程组内存和计算量都可能非常大。实际问题中当 n 超过几千时直接用通用 SDP 求解器就可能变得很慢。 因此工程上通常不直接把大规模问题丢给 SDP 求解器而是 - 先压缩问题规模利用低秩假设把半正定矩阵分解为 X V V^T其中 V 是 n*k 矩阵。 - 使用一阶方法比如交替方向乘子法ADMM避免维护完整的半正定矩阵。 - 使用随机投影在低维空间上近似求解再用近似解指导原始问题的迭代。 这些优化手段说明学习 SDP 不能只停留在“会调用 CVXPY”这一层还要理解问题的结构否则遇到大规模实例时无从下手。 ### 5.4 从 SDP 到实际应用的延伸 SDP 在更广泛的工程场景中也有实际价值。推荐系统中低秩矩阵补全可以写成核范数最小化的 SDP 松弛谱聚类中归一化拉普拉斯的特征值问题本质上和半正定松弛有关量子信息中的纠缠判断也需要通过 SDP 来验证某组测量结果是否违反可分离性条件。 6.854 课程里讲 SDP不是为了让每个学生都成为 SDP 领域专家而是让大家知道当问题里出现“相似度”“内积”“二次型”这些结构时SDP 是一个比 LP 更强的表达工具。它的代价更高但收益也可能更大。 ## 6. 压缩感知用稀疏性突破采样瓶颈 ### 6.1 传统采样定理与压缩感知的根本差别 传统信号处理依赖奈奎斯特-香农采样定理要完美重建一个最高频率为 f 的信号采样率至少为 2f。这个定理的前提是“不依赖任何信号先验信息”只要不知道信号长什么样就只能用均匀高频采样来保证信息不丢失。 压缩感知Compressed Sensing彻底改变了这个假设。它考虑的信号不是任意信号而是一个 n 维向量 x大部分分量为 0只有 k 个分量非零即 k-稀疏信号。如果信号本身足够稀疏就可以用 m 次线性测量恢复 x其中 m 远小于 n。 这个结论的反直觉之处在于我们采集的数据量甚至少于信号本身的维度却仍然能恢复出精确的信号。关键在于稀疏性先验 测量矩阵的特殊性质 非线性恢复算法三者配合。 ### 6.2 信号稀疏性与测量矩阵RIP 条件 压缩感知的数学模型是 text y A x 其中 x 是 n 维稀疏信号A 是 m*n 的测量矩阵y 是 m 维测量结果。这里 m 远小于 n所以方程是欠定方程理论上 x 有无穷多个解。 要让“最稀疏的解”成为唯一的真实解测量矩阵 A 必须满足限制等距性质Restricted Isometry Property, RIP text (1 - delta) ||x||_2^2 ||A x||_2^2 (1 delta) ||x||_2^2 对任意 k-稀疏向量 x 成立。RIP 要求的直观解释是A 在稀疏向量方向上近似保持范数不把不同稀疏向量映射到几乎相同的测量。 RIP 条件很难直接验证但随机矩阵以高概率满足 RIP。常见选择是随机高斯矩阵或随机伯努利矩阵。因此工程上不需要手工设计测量矩阵生成一个随机矩阵并用理论公式估算所需测量次数即可。 所需测量次数 m 的经验下限是 text m C * k * log(n / k) C 是一个常数因子与测量矩阵类型和恢复算法有关。这个公式说明测量次数和稀疏度 k 线性相关而和信号维度 n 只是对数关系。 ### 6.3 恢复算法L1 最小化与匹配追踪 已知 y 和 A恢复 x 最自然的想法是求解 text minimize ||x||_0 subject to A x y 其中 L0 范数表示非零元素个数。这个优化问题是 NP 难的不能直接求解。 压缩感知的关键突破是意识到在 RIP 条件下可以用 L1 范数最小化来替代 L0 最小化 text minimize ||x||_1 subject to A x y L2 范数会倾向于把所有元素都变到很小而不是集中到少数分量上L1 范数具有“在坐标轴上取得最小值”的几何特性天然促进稀疏解。这也是为什么 L1 正则化在机器学习中同样常用于特征选择。 工程中更常用的恢复算法是贪婪类算法例如正交匹配追踪Orthogonal Matching Pursuit, OMP。OMP 每次从测量矩阵中找出与当前残差最相关的列把它加入支撑集再用最小二乘求解支撑集上的系数然后更新残差。它的实现比 L1 最小化更简单迭代次数也容易控制。 python import numpy as np def omp(A, y, k): m, n A.shape x np.zeros(n) r y.copy() support [] for _ in range(k): corr A.T r idx np.argmax(np.abs(corr)) support.append(idx) A_s A[:, support] coef, _, _, _ np.linalg.lstsq(A_s, y, rcondNone) r y - A_s coef x[support] coef return x 这段代码的要点是每一步选择与残差最相关的列然后完全不修改已选支撑集之外的系数。实际使用中要注意支撑集里可能出现重复选择同一个索引需要去重否则 lstsq 会因为矩阵列线性相关而给出数值不稳定的结果。 ### 6.4 一个最小示例从随机测量恢复稀疏向量 用一个具体数字实验来验证压缩感知的流程 python import numpy as np n 256 k 10 m 64 # 生成 k-稀疏信号 x_true np.zeros(n) idx np.random.choice(n, k, replaceFalse) x_true[idx] np.random.randn(k) # 随机高斯测量矩阵 A np.random.randn(m, n) / np.sqrt(m) y A x_true # 使用 OMP 恢复 x_est omp(A, y, k) print(recovery error:, np.linalg.norm(x_est - x_true) / np.linalg.norm(x_true)) 在 m 64、n 256、k 10 的情况下恢复误差通常可以降到 1e-10 以下。如果 k 增大到 40 或 50上述参数下的恢复就会失败因为测量次数不足。这个实验能直观验证“m 与 k 线性相关”的理论结论。 ### 6.5 压缩感知的工程前提与常见误区 压缩感知不是一个通用信号处理黑盒它需要三个条件同时成立 1. 信号在某个基下确实稀疏。很多自然信号在时域不稀疏但在小波基或傅里叶基下稀疏需要先做变换。 2. 测量矩阵满足 RIP 或至少与稀疏基不相关。随机矩阵和大多数正交基都有很好的不相关性。 3. 噪声不能太大。当测量含噪声时恢复问题变为鲁棒 L1 最小化误差上界与噪声能量成正比。 工程中常见的误区是 - 没有先验证信号的稀疏性直接套压缩感知结果恢复质量很差。 - 把压缩感知理解成“无损压缩方案”实际上它在测量环节就把信号压缩了恢复结果通常是有损或近似的。 - 对含噪数据不做任何处理直接用无噪声模型恢复。 - 使用确定性稀疏矩阵时没有验证 RIP只因为某篇论文中说某种矩阵“可以”就认为所有矩阵都可以。 ## 7. 学习 MIT 6.854 的实践路线与排错清单 ### 7.1 学习前的知识自检清单 开始看视频前先用下面的清单做一次自检 | 检查项 | 状态 | 如果不过关怎么办 | | --- | --- | --- | | 能独立写出快排并做摊还分析 | 是/否 | 先复习 CLRS 第 7 章 | | 理解 Chernoff Bound 的含义 | 是/否 | 先补概率论重点看“尾概率”一节 | | 能写出最大流的 Ford-Fulkerson 算法 | 是/否 | 先做一次网络流专题练习 | | 知道矩阵特征值和半正定矩阵的定义 | 是/否 | 线性代数补第二章相关部分 | | 会使用 Python 的 NumPy 做矩阵运算 | 是/否 | 先跑 30 分钟快速教程 | 自检不必全部通过但对角线都是“否”时直接开始 6.854 会很吃力。建议花一到两周补齐最薄弱的两项。 ### 7.2 双语字幕课程的高效学法 使用中英双语字幕课程时最容易犯的错误是把视频当“听力材料”或“刷剧”一样看。更有效的方式是分段看 1. 每一讲开始前先看讲义或课程主页的幻灯片从中提取本节课的关键定理和结论。 2. 播放视频时先关掉中文只看英文字幕迫使自己理解英文术语遇到实在卡住的地方再开中文对照。 3. 每看完一个主题用 5 分钟把黑板上或幻灯片里的核心证明复述一遍。复述不是背字幕而是用自己的话解释“为什么要引入这个引理”“这一步放缩的意义是什么”。 4. 在关键定理处暂停尝试在视频推导之前自己猜下一步。猜错了也没关系这个猜测过程本身就是建立理解的过程。 textarea 6.854 属于快节奏的研究生课程不要试图一次看完一整讲。建议每个视频拆成 20 分钟一个段落配合讲义、笔记和课后习题交叉进行。学习效果取决于你重写了多少遍证明而不是看完多少分钟视频。 ### 7.3 主题练习与复现方法 每个主题都要做一次“理论 实验”的双重验证。理论任务是从零证明一遍课程中的核心定理实验任务是用 Python 或 C 实现一个小规模算法并验证结果。 具体来说 - 哈希主题实现一个带 rehash 的哈希表并构造一组冲突输入验证最坏情况确实退化。 - 流算法主题用 CountMin Sketch 统计一个英文小说文件的单词频次和 collections.Counter 对比。 - 线性规划主题用 CVXPY 建模一个最小生成树或顶点覆盖的 LP 松弛观察分数解和整数解的差距。 - 半定规划主题实现 GW 算法在随机图上运行检查割收益是否接近理论近似比。 - 压缩感知主题用 OMP 和 L1 方法分别恢复稀疏信号绘制恢复误差与测量次数 m 的关系曲线。 这些实验不需要做大系统只需要能回答一个问题课程里的理论结论在我自己的数据集上是否成立。 ### 7.4 五大主题的常见误区排查表 | 主题 | 常见误区 | 正确认识 | 排查方式 | | --- | --- | --- | --- | | 哈希 | 认为哈希表最坏情况 O(1) | 哈希表是期望 O(1)最坏 O(n) | 对固定哈希函数构造冲突输入测试 | | 流算法 | 以为 CountMin 不给真实值上界 | CountMin 查询结果不小于真实频率 | 用真实频率对比查询结果 | | 线性规划 | 把对偶单纯当作数学练习 | 对偶是算法设计和近似比证明工具 | 用对偶构造顶点覆盖的 LP 下界 | | 半定规划 | 把 SDP 当“高级调包”不知道为什么要松弛 | SDP 的价值在于表达内积结构 舍入分析 | 重写 GW 算法的松弛和舍入步骤 | | 压缩感知 | 忽略稀疏先验什么信号都敢恢复 | 不稀疏的信号无法用压缩感知理论保证 | 在非稀疏信号上观察恢复失败现象 | ### 7.5 从课程到研究和工程实践的扩展路径 学完 6.854 后可以沿着以下方向深入 - 如果对随机算法感兴趣读《Probability and Computing》和《Randomized Algorithms》重点研究随机游走和马尔可夫链蒙特卡洛方法。 - 如果对优化感兴趣读 Boyd《Convex Optimization》把 SDP 的算法实现和凸优化理论补齐。 - 如果对大数据系统感兴趣把 CountMin、HyperLogLog、Bloom Filter 等 sketch 用在你熟悉的数据存储系统里实践线上数据统计。 - 如果对理论计算机科学感兴趣继续读近似算法经典教材《The Design of Approximation Algorithms》其中大量章节直接使用课程里讲过的 LP 对偶和 SDP 松弛。 这门课最重要的不是记住某个算法的具体步骤而是建立“问题 - 松弛 - 求解 - 舍入 - 证明”的算法设计思维链。带着这条思维链去读论文、写系统、做实验会在很多看似不相关的问题里发现相同的底层模型。 实际项目中最值得记住的一点是高级算法的价值不在课堂证明本身而在于它能帮你在工程中判断哪些问题有理论下界、哪些问题可以近似、哪些空间换精度值得做。把哈希、流算法、线性规划、半定规划、压缩感知当成一套工具箱而不是五门独立课程才是学习 MIT 6.854 最大的收获。