音像算法之美

序言
1 很优停止理论：如何准确选择停止观望的时机？
秘书问题
37%从何而来？
情场上的出手时机
掌握候选对象的完整信息
卖房子的时机
很优停车位置
见好就收的时机
随时准备停止
2 探索与利用：要近期新的还是要优选的？
什么是探索与利用？
如何利用剩余时间？
赢留输变
基廷斯指数
遗憾与乐观
网上“土匪”
试验中的临床实验
不安分的世界
孜孜不倦地探索
3 排序：建立秩序
排序狂潮
排序带来的苦恼
大O符号：衡量坏情况的标准
平方时间：冒泡排序与插入排序
打破平方时间的魔咒：分治算法
比较法：比对数更好的算法
排下序是搜索的准备工作
排序与体育
发牢骚的权利：噪声与健壮
杀戮排序：啄食顺序与优势等级
以竞争取代争斗
4 缓存：忘了它吧
分级存储器体系
缓存清理与未卜先知
重整图书馆藏书
本地需求
家庭生活中的“高速缓存”
归档与堆存
遗忘曲线
经验
5 时间调度理论：要事先行
安排时间是一门科学
处理时限
把事情做好
找出问题所在
优先级反转和优先约束
减速带
放弃所有：抢占和不确定
抢占并不是随意的：关联转换
颠簸状态
中断合并
6 贝叶斯法则：预测未来
贝叶斯牧师的倒推理
拉普拉斯定理
贝叶斯法则与先验信念
哥白尼原则
贝叶斯与哥白尼
真实世界先验……
他们的预测规则
小数据与思维
我们的预测体现出我们自己
机械复制时代的先验
7 过度拟合：不要想太多
反对复杂案例
数据崇拜
过度拟合无处不在
检测过度拟合：交叉验
如何应对过度拟合：惩罚复杂
启发法
人类进化中的过度拟合
何时应该想的更少？
8 松弛：顺其自然
很优化的难度
定义的难度
放松吧
无数灰色地带：持续的松弛
只是一张超速罚单：拉格朗日松弛算法
学会松弛
9 随机：何时应用随机？
抽样
随机算法
抽样的优势
三部分的权衡
山、谷和陷阱
局部优选值之外
模拟退火算法
随机、进化和创造力
10 网络：我们如何联系？
分组交换
信息确认
指数退避算法：宽恕的算法
流量控制和拥塞避免
反馈语：语言学的流量控制
缓存膨胀：这就是，瓜 迟到不如永远不到
11 博弈论：别人的想法
达到均衡
占优策略，无论好坏
公地悲剧
机制设计：改变游戏
机制设计的演变
信息瀑布：泡沫的悲剧理
你自己的计算
结语 计算善意

布莱恩·克里斯汀(Brian Christian)，《日报》书《很有人的人》作者，该书入选《纽约时报》编辑书目，被《纽约客》杂志评为年度好书。他的多篇作品先后刊登在《纽约客》《大西洋》《连线》《日报》《卫报》《巴黎评论》及《认知科学》等杂志上，被翻译成11种语言。
汤姆·格里菲思(Tom Griffiths)，加州大学伯克利分校心理学和认知科学教授，计算认知科学实验室主任。格里菲思发表过150多篇科学，内容涉及认知心理学、文化演进等，受到美国科学会、斯隆会、美国心理学会和心理环境学会等颁发的各类奖项。

设你想租房子，正在旧金山四处寻找房源。旧金山可能是整个美国难找房子的城市了。由于技术产业的蓬勃发展，再加上城市区划法律严格建造新住房，旧金山的房租已经与纽约不相上下，甚至比纽约还高。房源清单列出来几分钟，房子就会被人们一抢而空。通常情况下，只有个把定金支票塞房东里的人，才能拿到房子的钥匙。理论上讲，认真调查、仔细斟酌是理消费者的一大特征，但是旧金山的残酷市场并没有为他们留有权衡考虑的机会。在购物中心或者网上购物时，人们可以反复权衡再做出决定，但是将要入住旧金山的租客没有这个特权，他们必须迅速做出决定：要么舍弃所有可能的选择，就选定当前正在看的这套房子，要么掉头就走，再也不要回头。简单起见，我们姑且设，你专享关心的就是尽优选可能增加挑中理想公寓的机会。你的目标是把“看过的好房子被人挑走”与“还有好房子没来得及看”这两种遗憾的发生概率降至大力度优惠。于是，你立刻发现自己陷入了两难境地：如果没有衡量的标准，如何判断一套公寓是合的呢？如果你不先看一些公寓（这些公寓将被你放弃），又如何确定衡量标准？你收集的信息越多，越能在合的机会出现时准确地认出它，但是你已经与合的机会失之交臂的可能也越。那么，到底该怎么办？如果收集信息的行为会危及结果，那么怎样才能在掌握足够多信息的基础上做出明智决定呢？这个令人极其为难的情境近乎于一个悖论。在被问及此类问题时，大多数人凭直觉给出的回答可能大致如此：这需要在继续挑选与立刻下手之间达成某种平衡。也就是说，你必须先看足够多的房子，确定一个标准，然后接受符合这个标准的房子。事实上，平衡概念正是解决这类问题的关键。但是，大多数人根本无法确定这个平衡点在哪里。好消息是，这个平衡点已经被找出来了。就是37%。如果你希望选中合公寓的可能达到优选，那么在看前37%的房子时不要做出任何决定（如果你准备花一个月的时间挑选房子，那么在前11 天不要做出决定）。这段时间你是在为制定标准做准备，因此看房子时把银行卡放在家里吧。但是，过了这个时间点之后，你就要做好随时签约的准备（包括准备好定金等），一旦你对某套房子的满意程度超过之前看过的所有房子，就立刻下手。在继续挑选与立刻下手之间做出的这种妥协，并不仅仅是一种直觉，而是已经得到明的很优解。我们知道这个，是因为找房子问题属于数学上被称作“很优停止”（optimal stopping）的一类问题。37% 法则明确了解决这些问题的一系列简单步骤（计算机科学称之为“算法”）。事实明，找房子仅仅是很优停止问题在日常生活中的表现形式之一。在面临一连串选择时如何做出决定的难题，经常会改头换面，以不同的形式出现在我们的生活当中。在驶入停车位之前，需要绕整个停车场多少圈？在商业风险中何时脱身？在买房子或者停车时，何时是结束观望、做出决定的很好时机？在约会这个更加令人头疼的问题上，人们也经常要面对这样的难题。很优停止理论是一一婚姻制度催生的科学。每天，人们都要面临很优停止问题的困扰（当然，诗人更愿意追逐的话题肯定是求婚带来的烦恼，而不是停车时的两难境地），有时至会因此而痛苦不堪。不过，我们大可不必如此，因为这类问题至少可以通过数学方法来解决。借并不繁复的算法，我们不仅可以解决找房子的问题，生活中遭遇的所有很优停止问题都可以被妥善处理。从本质上讲，我们身边经常出现因为租房子、停车、求婚而感到苦恼的人，这些人其实就是在自寻烦恼。他们需要的不是治疗师，而是一种算法。治疗师告诉他们要在冲动与多虑之间找到一个正确的、舒服的平衡点。算法告诉他们这个平衡点就是37%。本书将探讨人类事务算法设计这个概念，以帮人们更好地处理日常生活中遇到的难题。将计算机科学的研究方法应用于日常生活，可以在多个层面上产生深远的影响。首先，它可以提供切实有效的建议，帮我们解决具体问题。例如，很优停止理论可以告诉我们何时应该小心观察，何时应该果断行动；探索– 利用平衡理论教会我们如何在尝试新事物与因循守旧之间找到平衡点；排序理论可以帮我们判断出需要以及如何整理办公室；缓存理论可以帮我们合理地填充橱柜；日程安排理论则可以提供合理安排时间的高招。其次，计算机科学还为我们理解这些领域的深层次运行规则提供了一套语汇。卡尔·萨根指出：“与其说科学是大量知识的汇总, 不如说它是一种思考方式。”即使生活中的某些情况很好复杂，我们无法进行严格的数值分析，找不到任何现成的，我们也可以考虑这些问题的简单化表现形式，从而得出某些直觉和概念，帮我们理解其中的关键环节并取得进展。从更广泛的意义上看，借计算机科学，我们可以了解人类思想的本质和理的意义，学会回答如何度过一生这个古老的问题。把认知视为一种解决周围环境所造成的问题（从本质上看，都是一些计算问题）的手段，并认真地加以研究，就有可能改变我们对人类理的理解。认为研究计算机内部运行机制能够帮我们学会思考与决策、判断某个事物可信、选择行为方式的观点，在很多人看来，不仅把问题过于简单化了，而且具有误导。即使计算机科学告诉我们应该如何思考、应该采取哪些行动，我们愿意接受吗？读一读讲人工智能和机器人的科幻小说就会发现，那样的生活似乎都不是我们所向往的。之所以如此，部分原因是我们把计算机看成了机械呆板的确定系统——这些机器借严谨的演绎逻辑，通过穷举所有可选方案，无论花费多少时间、问题难度如何，它都可以给出接近正确的。事实上，在阿兰·图灵当时的想象中，计算机就应该是这样。这位个设想出计算机的人通过类比的方式给出了计算的定义，而类比的原型就是认真钻研的人类数学家——他们通过长长的计算步骤，得出保正确的。因此，当人们发现现代计算机处理难题的方式与他们对计算机的认识并不一致的时候，他们也许会大吃一惊。当然，简单的算术对现代计算机而言没有任何难度。目前，计算机科学面临的难解决的问题其实是人机对话、修复破损文件、下围棋取胜，这些问题都具有规则不明确、所需信息不全，或者需要考虑无数种可能才可以找出正确的特点。研究人员已经开发出各种算法，使计算机在解决难度极大的问题时不需要接近依赖穷举计算。要解决这些来自现实世界的任务，就必须正确处理好可能问题，利用粗略估算，在时间与准确度之间做出某种妥协。随着计算机处理现实任务的能力不断，计算机算法不仅对于人类自己的生活具有借鉴意义，同时还为人们理解人类认知提供了一个更好的比较标准。在过去的一二十年里，行为经济学对人类进行了很好具体的研究，结果发现，人类是不理的，很容易犯错误，而问题的源头在很大程度上就是大脑这个古怪而独特的硬件。这种自我贬低的认识越来越普遍，却无法解释某些令人困惑的问题。例如，在完成包括想象、语言、因果推理在内的大量认知任务时，4 岁儿童的能力仍然超过成本高昂的不错计算机，这到底是什么原因？从计算机科学为日常问题提供的解决方案可以看出，人类思维具有另外一种特点——人生充满了难以解决的问题。人经常犯错误，虽然这可以说明人类大脑容易出错，但是也表明这些问题具有难以解决的本质特点。通过算法来思考我们周围的世界，了解我们所面临问题的基本结构以及计算机给出的解决方案的特，可以帮我们真实地了解我们自己，更好地理解我们所犯的那些错误。事实上，人类需要不断面对计算机科学所研究的一些高难度问题，在不确定及时间有限、信息不全、情况瞬息万变等不利因素的干扰下做出决定。针对一些问题，即使前沿的计算机科学也没能开发出永远不会犯错误的有效算法，有的情形似乎是任何算法都无法解决的。不过，尽管有的现实问题异常复杂，人们还没有开发出完善的算法，但是一代代计算机科学家一直在与这些难题斗争，并且在这个过程中得出了深刻而独到的见解。这些来之不易的真知灼见与我们对理的直觉认识并不一致，与数学家对周围世界的准确描述也迥然不同——数学家一心想要把这个世界变成整齐划一的线条。计算机科学告诉我们：不要总是考虑所有的可选方案；不必每次都追求很好结果；偶尔犯点儿错误；放下包袱，轻装前进；有的事情可以暂时放一放；相信自己的本能，不要过多思考；放松自己；采用抛硬币的方式；要体谅，但是不能忘记；忠于自我。用计算机科学的智慧指引自己的人生之路，这似乎是一条不错的建议。竟，与大多数建议不同的是，这条建议有据可依。