书 · 2012 · 约翰·麦考密克（John MacCormick）

《改变未来的九大算法》

计算机与 AI书单第 18 名

一句话结论

电脑的许多惊人能力，来自巧妙的信息组织、数学结构和协作规则；但再聪明的算法也有无法跨越的边界。

值不值得读完整本？

值得读完整本。它用不要求编程基础的方式，解释搜索、通信、安全、学习和数据库背后的关键机制，并以不可计算性给技术乐观设下边界。

先读第1章，再连读第2—3章，区分搜索引擎怎样找到候选网页，以及怎样排列网页。
把第4章公钥密码与第9章数字签名配对阅读，抓住保密、身份验证和内容完整性的区别。
把第5章纠错码与第7章数据压缩配对阅读：一个有意增加冗余，一个利用冗余缩短表示，两者解决不同问题。
第6章模式识别、第8章数据库和第10章可计算性都应细读；它们分别解释怎样从例子学习、怎样避免记录相互矛盾，以及哪些问题不存在通用算法。
序言、人物故事和第11章展望可以略读。建议配合纸笔练习：画一个链接网络、手算简单校验、演示一次转账中断；考前应能解释九类主题的机制，而不只是记住名称。

核心观点

1. 搜索要分别解决找得到与排得好

倒排索引让搜索引擎快速找到包含查询词的网页，PageRank则利用链接关系估计网页的重要性。这是两项相互配合、作用不同的技术。

为什么：如果每次查询都重新阅读整个网络，绝大部分工作都会重复。倒排索引预先建立从词语到网页及词语位置的对应关系，让查询集中处理有关记录。PageRank进一步把链接看成带有权重的推荐：受到重要网页推荐的页面，也应获得较高分数。随机浏览者沿链接移动并偶尔跳转，其长期访问比例提供了计算这种重要性的办法；它衡量的是链接结构中的地位，并不直接证明内容真实。

2. 公开通信也能建立秘密，但保密与签名是两回事

公钥密码体系使没有预先共享秘密的双方也能建立安全通信，数字签名则让接收者验证内容与某个私钥持有者的关系。

为什么：关键是利用某些数学运算正向容易、逆向在适当条件下很难的差别，让公开信息不等于公开秘密。密钥交换可以让双方通过公开交换的信息得到共同秘密，而旁观者难以重建它。公钥加密则把公开的加密能力与秘密的解密能力分开。数字签名让私钥持有者为具体内容生成可公开验证的凭据，密码学摘要帮助把签名绑定到内容上。验证结果仍依赖公钥来源可信，也不能据此认定签名内容本身正确。

3. 冗余既能被删去以节省空间，也能被加入以抵抗错误

压缩利用数据中的规律减少表示长度，纠错码增加经过设计的冗余以便恢复受损信息。两者都在设计信息的表示方式。

为什么：无损压缩把重复片段、常见符号等规律换成较短的表达，解码时再恢复原来的数据。有损压缩还允许舍弃部分细节，以换取更大的体积缩减。纠错编码走向另一个方向，让合法表示之间保留足够差异，使有限的错误不至于把一个合法消息变成另一个。接收者因此可以根据额外的约束发现错误，并在编码能力范围内确定原消息。节省空间与抵抗噪声各有代价，不能指望任意数据都可无损缩小，也不能指望有限冗余修复任意破坏。

4. 模式识别把经验转化为处理新输入的规则

许多识别任务不适合逐条手写规则，可以让计算机从已有样例中形成分类方法。最近邻、决策树和神经网络展示了不同的学习思路。

为什么：真实输入有大量变化，同一个数字也可能有许多种写法，穷举规则很困难。最近邻方法利用相似输入往往具有相同类别这一假设，用已知样例判断新样例。决策树通过逐步提问划分类别，神经网络则通过调整连接权重改善输出。它们能否处理未见过的输入，取决于样例是否包含可推广的规律，以及表示方式和学习方法能否抓住这些规律。

5. 数据库可靠，靠的是组织关系与协调更新

数据库不仅负责保存数据，还必须让相关记录在更新和故障之后保持一致。关系表、事务日志和两阶段提交分别解决数据关联、故障恢复与多方协调问题。

为什么：把所有信息反复抄进不同记录，容易造成更新遗漏，关系表及其关联查询让数据可以分开保存、组合使用。一次业务操作又常涉及多项修改，而计算机可能在修改中途崩溃。预写日志先留下恢复所需的信息，让系统能够完成或撤销尚未完成的事务，避免留下半次操作。当事务涉及多个参与方时，两阶段提交先确认各方准备情况，再协调提交或中止。可靠性因此来自明确的记录与协议，但协调过程可能需要等待。

6. 有些问题缺少的不是速度，而是可能存在的通用算法

计算机的限制不只是运行慢或存储不足：某些定义明确的问题，不存在对所有输入都能正确结束并给出答案的算法。

为什么：计算机程序本身也能成为另一个程序的输入，因此可以研究程序分析程序的情形。假设存在一种万能分析器，能够判断任意程序是否具有某种特定行为，就可以据此构造一个专门违背其预测的程序。再让这个程序分析自身，假设就会导出矛盾。这种论证排除的是通用解法的存在，增加处理器速度并不能消除逻辑矛盾。

反对意见

链接重要性不能代替对搜索权力的分析（Safiya Umoja Noble）

Noble在《Algorithms of Oppression》中指出，搜索结果会受到商业利益、平台权力和社会偏见影响，可能强化对有色人种女性的歧视。由此看，理解PageRank怎样计算分数，还不足以判断搜索结果是否公平、是否值得信任。这是对本书技术视角的补充，并非针对本书的直接书评，也不否定PageRank的数学机制。

把问题变成分类任务，可能遗漏真正重要的背景（Andrew D. Selbst等）

Selbst等人在《Fairness and Abstraction in Sociotechnical Systems》中指出，把决策系统抽象成输入、模型和输出，可能排除制度、使用者和社会关系，使技术上的公平修补失效。对本书模式识别章节的补充是：分类方法有效，并不自动意味着现实中的决策合理；还应追问标签怎样产生、错误由谁承担。这篇论文讨论的是机器学习应用的边界，并非直接反驳本书。

数据库协调不能同时消除所有故障代价（Seth Gilbert、Nancy Lynch）

Gilbert与Lynch在关于Brewer猜想的论文中证明：在其模型中，允许网络分区时，系统无法同时保证线性一致性和每个非故障节点收到的请求最终都得到响应。因此，不能把日志与提交协议理解成数据库在任何故障下都能保持一致并持续服务的保证。这里的线性一致性也不等同于事务的业务约束一致性；该论文提供的是更严格的边界，并非对本书的直接批评。