听到“算法”（algorithm）一词，第一反应可能跟计算机有关，但其含义远不限于计算机，存在的历史也远远长于计算机。”算法“一词得名于波斯数学家花剌子密。公元9世纪，这位数学家写过一本书，讨论用纸笔解决数学问题的技巧。［书名为“al-Jabr wa’l-Muqabala”，其中的“al-jabr”就是后来“algebra”（代数）这个词的前身。］
尤瓦尔·赫拉利在《未来简史》中写道：“算法指的是进行计算、解决问题、做出决定的一套有条理的步骤。 人类有99%的决定，包括关于配偶、事业和住处的重要抉择，都是由各种进化而成的算法来处理，我们把这些算法称为感觉、情感和欲望"。
《算法之美》讲的正是在我们日常的生活和工作中，对我们有指导意义的算法。
一、
最优停止理论：如何选择停止观望的时机？
最优停止问题的权威教科书开宗明义地指出：“最优停止理论关注的是如何选择时机以执行特定行动的问题。”
是冲动早早停止观望，还是多虑继续观望？这需要达成某种平衡，平衡概念正是解决这类问题的关键，但是大多数人根本无法确定这个平衡点在哪里？
算法告诉我们”37%法则“正是我们要的答案。
“37%法则”源于所谓的“秘书问题”—最优停止问题中最著名的一类难题。秘书招聘效果最佳的做法是接受所谓的“摸清情况再行动准则”（look-then-leap rule）：事先设定一个“观察”期，在这段时间里，无论人选多么优秀，都不要接受他（也就是说，你的任务就是考察目标，收集数据）。“观察”期结束之后，就进入了“行动”期。此时，一旦出现令之前最优秀申请人相形见绌的人选，就立即出手，再也不要犹豫了。随着秘书职位申请人数不断增加，观察与行动之间的分界线正好处在全部申请人37%的位置，从而得出了37%法则：在考察前37%的申请人时，不要接受任何人的申请；然后，只要任何一名申请人比前面所有人选都优秀，就要毫不犹豫地选择他。
经典秘书问题的前提条件是，即时表态一定会被接受，而迟滞表态肯定会遭到拒绝，这样看来，秘书问题最基本同时也最令人难以置信的前提条件—严格的连续性，即有进无退的单向行进，正好是时间自身属性的一个体现。就此而言，最优停止问题的这个显性前提正好就是使其充满活力的隐性前提。这个前提迫使我们基于还没亲眼看到的可能结果做出决定，迫使我们在采取最优策略之后仍然愿意接受非常高的失败率。我们永远没有二次选择的机会。我们有可能得到类似的选择机会，但是绝不会得到完全相同的选择机会。犹豫不决（不作为）与行为一样不可改变。困在单行线上的驾车者与空间的相互关系就是我们与第四维度的关系：我们的生命真的只有一次。
我们只能知道孰优孰劣，但是无法了解彼此之间的确切差距。正因为如此，“观望”阶段是不可避免的。在前期阶段，我们冒着与优秀人选失之交臂的危险，不断调整我们的期望值与权衡标准。数学家把这种最优停止问题称作“无信息博弈”。全信息的意义在于我们无须观望就可以直接出手。此时，我们可以运用阈值准则，一旦发现某位申请者的分数高于某个值，就立刻接受她，而不需要先考察一批候选人并确定阈值。
买房子、卖房子、找工作、找停车位等等问题，均可以看做是一个最优停止问题。
二、
探索和利用：要最新的还是要最好的？
直觉告诉我们，生活就是在新鲜事物和传统事物之间、在最新的和最棒的之间、在勇于冒险和安于现状之间取得平衡。
罗伯特·波西格在他于1974年出版的经典著作《禅与摩托车维修艺术》中对“有什么新鲜事吗？”这句寒暄语进行了公开谴责。他说：“只要认真地研究这个问题的话，得到的答案肯定是一堆琐碎的跟风事物，等到了明天它们就会失去新鲜劲儿。”他认为另一个问题就要好得多：“最好的是什么？”
50多年来，计算机科学家一直埋头钻研，希望可以在要最新的还是要最好的之间找到这个平衡点，他们的研究甚至还有一个专门的名称：探索与利用的取舍。
英语为“explore”（探索）和“exploit”（利用）这两个词赋予了截然相反的含义，但是在计算机科学家眼中，它们有很多具体的中性含义。简单地说，探索的意思是收集信息，而利用则指利用所拥有的信息，以产生一个好的结果。
你到底应该花费精力去探索新的信息，还是专注于从已有的信息中获得收获？关键是时间和度的问题。随着时间的推移，即使探索有所发现，我们可以认真品味这些新发现的机会也已经所剩无几，因此探索的价值随之降低。与之相反，利用的价值随着时间的推移反而会不断上升。利用好剩余时间就是正确的应对之策。
“基廷斯指数（Gittins Index）”为解决探索与利用的取舍的问题提供了方案。
他说，当你计划出去吃一顿饭的时候，明天那顿应该比今天这顿要贬值一点 —— 因为你明天可能会离开这里，吃不上那顿饭。具体贬值多少，取决于你预期还能停留多长时间。基于这一点，他提出了一个非常复杂的解决方案，最后结果是给每个选项计算了一个指数，现在被称为“基廷斯指数（Gittins Index）”。
“时间贬值率”会极大影响基廷斯指数，总的说来，未来可期并可能有惊喜，则鼓励尝试新事物；当下优秀稳定而未来不可知，则鼓励坚持老事物。
我们希望每一天都活在当下，可是从现实的数学角度，你预期停留的时间越长，探索新事物的价值就越高，基廷斯指数也越高。
一般而言，我们对理性的直觉认识常常来源于利用，而不是探索。当我们谈论决策过程时，我们通常只关注某个决定的即时回报——如果你把每一个决定都当作人生的最后一个决定，那么只有利用才是有意义的。但在一生中，你会做出很多决定。实际上，在做很多决定时，理性的做法是强调探索的重要性，重视新的东西而不是最好的东西，重视令人为之兴奋的东西，而不是一味追求安全，重视随机选择，而不是深思熟虑的决定。在人生早期，更应该如此。如果我们把期限设定为人的一生，这就意味着年轻人应该多探索，到了后期就要专注于收获。
斯坦福大学心理学教授劳拉·卡斯滕森通过自己的研究，对人们在衰老这个问题上的成见提出了质疑。她特别研究了人们的社会关系随着年龄增长而发生变化的过程与原因。这种变化有一个明晰的基本模式：人们社交网络的规模（即与他们保持社交关系的人数）几乎总是随着时间的推移而减少。不过，卡斯滕森的研究表明，我们应该改变对这个现象的看法。卡斯滕森认为，老年人的社会关系越来越简单，是他们主观选择的结果。由此可见，社交偏好的这些差异与年龄本身无关，而是与人们对决策过程中剩余时间的认知有关。
基廷斯指数以一种正式、严谨的形式，证明了在有机会对探索结果加以利用时，我们应该倾向于选择未知的新事物。
如果你认为基廷斯指数太复杂，或者你所处的情况并没有表现出几何贴现的特征，那么你还有另一个选择—关注遗憾。自黎子良、罗宾斯之后，研究人员在过去几十年里一直致力于寻找可以确保遗憾最少化的算法。在他们提出的算法当中，最受欢迎的就是上限置信区间算法。上限置信区间算法所采用的原理有一个绰号——“面对不确定性时的乐观主义”。
三、
排序问题
1955年，詹姆斯·霍斯肯在第一篇公开发表的关于排序的科学论文中写道：“为了降低单位产出的成本，人们通常会增加他们的业务规模。”这是任何一名商科学生都很熟悉的规模经济。但是，在排序这个问题中，规模往往会招致灾难：如果扩大排序的规模，“排序的单位成本就会不降反升”。排序往往呈现非常明显的规模不经济现象，这与普通人认为大批量处理问题有诸多好处的直觉正好相反。
这是排序理论的第一个，也是最基本的深刻见解：规模越大，难度越大。
据统计，世界上计算机资源的很大一部分被用于排序，难怪排序对于处理几乎任何类型的信息来说都是至关重要的。排序的主要原因之一是将内容变成方便人眼观察的形式，这意味着排序也是人类信息体验的关键。
信息处理开始于19世纪的美国人口普查，是由赫尔曼·霍尔瑞斯及后来的IBM公司根据实体打孔卡排序设备开创形成的。
当我们知道被排序的不仅是信息，其实还有人，因此学会排序有助于理解人类可以和谐相处，偶尔才会拳脚相向的原因。所谓社会，就是我们维持的另外一种更重要、规模更大的秩序。
但是，要回答如何排序、哪种排序方法效果最佳这个问题，就需要先弄明白另外一个问题：如何计分？
计算机科学有一种专门用来测量算法最坏情况的速记法，即所谓的“大O”符号。大O符号有一个非常奇怪的特点——设计这个符号的目的就是用来表示不精确性。也就是说，大O符号的目的不是使用分钟和秒钟来表示算法的性能，而是方便我们讨论问题规模和程序运行时间之间的关系。由于大O符号故意剔除了细枝末节的内容，所以展示给我们的是将问题分成不同大类的概略情况。
假设你准备邀请n名客人出席晚宴。在客人到来之前，打扫房间的时间与来客人数没有任何关系。这类问题最简单，被称为“O（1）”，也被称为“常数时间”。接下来，烤肉在所有客人面前传递一圈所需的时间将是“O（n）”，也被称为“线性时间”——客人增加一倍，菜传递一圈所需的时间就会增加一倍。假设客人到来之后，你要与每个人热烈拥抱，情况又会怎么样？第一个到达你家的客人与你拥抱，第二个客人需要拥抱两次，第三个客人要拥抱三次。此时，拥抱一共发生了多少次？这种情况属于“O（n² ）”，也称“平方时间”。如果没增加一位客人都会让你的工作加倍，那么就会有“指数时间”，记做“O(2的n次方)。
假设你希望将杂乱无序的藏书按照字母顺序进行分类排序。那么你会很自然地想到一个方法，于是你在书架前巡视，看到有两本书颠倒了先后次序，就把它们调换过来（例如，将品钦的小说放在华莱士后面）。在将品钦放到华莱士前面之后，你继续巡视。走到书架最后端之后，你就会回过头来，从书架最前端重新开始。如果从头走到尾，都没有看到有哪两本书次序不对，就说明你完成了这项工作。 这就是冒泡排序，它会把我们带进平方时间。
你可能会采取另外一种方法，即把所有的书都从书架上拿下来，然后一本一本放到合适的位置。你把第一本书放在书架中间，然后拿第二本书和第一本比较，根据比较结果把它插到第一本的右边或者左边。在放第三本书时，你先从左到右浏览书架，然后把它放到合适的位置。你不断重复这个过程，渐渐地所有的书都被按次序放到书架上，直到你最终完成这项工作。 计算机科学家们给这种方法起了一个非常贴切的名称——“插入排序”
插入排序比冒泡排序更直观，但实际上它不比冒泡排序快多少，但仍然是处于平方时间。是否有打破平方时间的算法，答案是肯定的，就是分治算法。
1945年，约翰·冯·诺伊曼为了展示存储程序计算机的威力，编写了一个程序。在这个程序的最终结论中，就包含有比较的概念。为两张牌排序很简单，把较小的那张牌放在上面就可以了。如果有两叠牌，每叠包含两张排好序的牌，我们可以很容易地将这四张牌整理成排好序的一叠牌。重复几次，就可以整理出越来越多且排好序的牌垛。很快，你就可以把完整的一副牌整理得井然有序。在最后一次合并时，你可以通过与交错式洗牌非常相似的手法，将扑克牌整理出你需要的次序。 这种方法现在被称作“合并排序”，是计算机科学中的传奇算法之一。正如1997年的一篇论文所指出的：“合并排序在排序历史中的重要地位与排序在计算历史中的重要地位旗鼓相当。¤” 合并排序威力巨大，是因为它的复杂程度位于线性时间和平方时间之间。具体来说，O（n log n）被称为“线性对数”时间。
从某种非常重要的意义上看，合并排序算法给出的O（n log n）线性对数时间肯定是我们可以得到的最佳效果。已经有人证明，如果通过一系列面对面直接比较的方法对n个事物进行完全排序，比较的次数不可能少于O（n log n）。这是一条普世法则，是不可能违背的。 但是，严格说来，这条法则并不能平息排序问题上的所有争议。有的时候我们并不需要完全排序，有的时候根本不需要逐项比较也能完成排序工作。正是因为有这两个原因，实践中的粗略排序速度也可以比线性对数时间快。桶排序算法非常漂亮地展现了这个特点 。在桶排序中，排序对象按照排序类别分成若干组，类别之间更精细的排序问题，在分组时不予考虑，留待后面解决。(在计算机科学中，"桶“这个术语表示一组未排序的数据）。
排序是搜索的准备工作，而排序与搜索之间的取舍是最重要的取舍问题之一，其基本原理是：人们投入精力为物品排序是一种先发制人的措施，目的是保证以后无须在搜索上投入精力。平衡点应该如何确定，取决于当时情况的具体参数，但是，如果认为排序的价值仅仅是为未来的搜索提供支持，那么你会有一个令人吃惊的发现：混乱无序也无伤大雅！随着计算机搜索成本的降低，排序的价值也随之降低。
排序问题在体育比赛，动物世界的啄食顺序和优势等级，以及比如船舶海上通行权之类的问题得以应用。船舶海上通行权在理论上需要遵循一套极其复杂的惯例，但是在实践中，到底哪条船应该给另一方让路是由“总吨位法则”这条简单易行的原则决定的。
四、
缓存问题
1946年，亚瑟·伯克斯、赫尔曼·戈德斯坦和约翰·冯·诺依曼在普林斯顿高级研究所展开合作，为他们所谓的“电子记忆器官”起草了一个设计方案。他们写道，在一个理想的世界里，机器当然可以有无限量的快速储存能力，但在实践中这是不可能的。（现在仍然不可能。）于是，这三个人退而求其次，提出了“分级存储器体系，每一级的存储能力都超过以前，但是读取速度有所减慢”。
在1962年超级计算机阿特拉斯在英国曼彻斯特问世以前，计算领域的这种“分级存储”概念一直停留在理论层面。
阿特拉斯问世之后不久，剑桥大学数学家莫里斯·威尔克斯意识到，这种体积较小、速度较快的存储器不仅可以为我们处理数据、将处理好的数据存回主存储器提供了一个非常方便的场所，还可以用来有意地保留稍后可能需要使用的信息片段，为后期类似的需要做好准备，从而极大地加速机器的操作。如果所需要的数据仍然保留在工作存储器中，就不必再到主存储器中装载这些数据了。威尔克斯认为，这种体积较小的存储器“可以自动收集并保存来自速度较慢的主内存的数据，为后期使用做好准备，从而免除了再次访问主存储器带来的麻烦”。20世纪60年代末，威尔克斯的提议在IBM 360/85超级计算机中得以实现，人们称之为“缓存”。
我们知道，IBM在20世纪60年代率先推动缓存系统的部署应用。不出意料，它也是早期缓存算法开创性研究的发源地，也许他们取得的任何一项成果都没有拉斯洛·贝莱迪的算法重要。贝莱迪于1966年发表的那篇缓存算法论文是随后15年里被引用最多的计算机科学研究成果。这篇论文解释道，缓存管理的目标是尽可能减少“页面错误”或“缓存缺失”。所谓缓存缺失，是指无法在缓存中找到所需数据，因此只能到较慢的主存中查找的现象。贝莱迪在文中写道，从本质上讲，最优缓存清理策略就是在缓存已满时，将未来最长时间内不会再次使用的数据从缓存中清理出去。今天，为了表示敬意，人们把那个无所不知、有先见之明，而且可以在分析未来情况基础上执行最优缓存策略的那个假想算法称作贝莱迪算法。
我们可以尝试随机清理算法，将新数据添加到缓存中，并随机覆盖旧数据。随机清理是早期高速缓存理论得出的一个令人吃惊的结果，虽然远非完美，但是效果也还不错。这也可能是一种巧合，因为只要有一个缓存，无论你如何维护，都可以提升系统的效率。不管怎么说，你经常使用的内容通常还会很快回到缓存中。另一种简单的策略叫作先进先出（FIFO）。这种算法总是清理或覆盖在缓存中保存时间最久的内容（与玛莎·斯图尔特问的“我已拥有它多长时间了”这个问题有异曲同工之妙）。第三种方法是最近最少使用（LRU），即将闲置不用时间最长的内容清理掉（与之相对应的斯图尔特的问题是“上次穿它或使用它是什么时候的事”）。
贝莱迪在若干情形下对随机清理、先进先出和最近最少使用的几个变体进行了比较，结果发现最近最少使用法始终表现出最接近未卜先知的效果。最近最少使用法的高效性得益于计算机科学家所谓的“时间局部性”：如果一个程序曾经调用过某个信息，那么在不久的将来它可能会再次调用这个信息。
如果你能创建一个网页内容缓存，其实际地理位置更接近那些有需要的人，你就可以更快地为他们提供页面服务。互联网上的大部分流量现在都是由“内容分配网络”来处理的，这些网络利用遍布世界各地的电脑维护流行网站的拷贝。因此，在用户请求使用这些页面时，他们可以从附近的一台计算机获取数据，而不必跨越千山万水，连接到原始服务器上。
最近，亚马逊获得了一项创新的专利，使它奉行的这条原则得到了进一步发展。在媒体看来，这项“可预期包裹配送”专利似乎可以帮助亚马逊在你下单之前就把商品送到你的手上。有人下订单时，商品就已经在他附近的大街上了。预测个人购买行为是有挑战性的，但是当预测数千人的购买行为时，大数定律就会生效。
迄今为止，我们见过的所有家居管理建议中，必不可少的一个“常客”就是“物以类聚”这个存放概念。也许没有人会像野口由纪夫那样直言不讳地反对这条建议。他说：“我必须强调，在我的方法中，一个基本原则就是不能把文件根据内容分组。”一旦认识到野口文件归档系统是最近最少使用原则的一个实例，我们就知道它不仅是一种有效策略，实际上还是最优策略。
1987年，卡内基-梅隆大学的心理学家、计算机科学家约翰·安德森为了解大学图书馆的信息检索系统，查阅了大量资料。他的目标，或者说他自认为的目标，是弄清楚信息检索系统的设计是否可以从人类记忆研究那里获取灵感。结果，他发现现实正好相反：信息科学有可能为人类大脑研究填补某些空白。在安德森对人类记忆的新描述中，其核心思想是，需要解决的可能不是存储问题，而是如何组织的问题。他认为，大脑的记忆能力基本上是无限的，但我们在大脑中搜索的时间是有限的。安德森把大脑比喻成图书馆，不过这个图书馆只有一个无限长的书架，也就是说，是一个美国国会图书馆级别的野口文件归档系统。你可以在那个书架上放无数本书，但是，书的位置越靠近前面，就越容易被找到。
如果记忆面临的基本问题真的是一个组织管理的问题，而不是存储问题，那么我们在衰老影响心智能力这个问题上的看法就应该改变。最近，图宾根大学的迈克尔·瑞姆斯卡率领一组心理学家和语言学家完成了一项研究，结果发现，所谓的“认知能力衰退”（滞后和检索错误）可能并不表明搜索过程变慢或者搜索能力退化，而是我们所面对的信息量不断变大所带来的一个不可避免的后果（至少是原因之一）。不管衰老还会带来什么样的难题，年长的大脑必须管理数量更多的记忆存储，因此，它其实每天都在解决更复杂的计算问题。面对反应速度更快的年轻人，老年人可以不屑一顾地说：“这是因为你什么都不知道！”
五、
时间调度理论：要事先行
“科学管理理论”提出者弗雷德里奇•泰勒，利用他的同事亨利•甘特的创意（甘特图），将调度编程一种研究对象，他们富裕它视觉和概念的形式。但是，甘特图没有解决一个基本问题，到底怎样安排日程是最好的？直到几十年之后的1954年，兰德公司的数学家塞尔默·约翰逊在他发表的一篇论文里才第一个暗示这一问题可以被解决。约翰逊的研究揭示了更深层次的两点内容：第一，时序安排可以通过算法表达；第二，存在最优时序安排方案。这引发了一项庞大的研究，为大量假定工厂中不同数量和种类的机器运行提供策略。
约翰逊的理论是基于最小化双机共同工作时间来降低总时间，在单机调度的情况下，如果我们要完成所有工作，那么所有的安排都应该用同样长的时间完成，与先后顺序无关。因此，单机调度的第一堂课是：明确你的目标。我们只有知道如何保持得分才能宣布哪种安排最好。由此产生以下几种研究理论：
1）如果你要降低最大延迟时间，那么最佳策略就是你先从截止日期最近的任务开始，再以此类推逐渐执行。这一策略被直观地称为最早到期日原则。
2）将完成时间总和最小化可以引申出一个非常简单的优化算法——最短加工时间：总是先做能最快完成的任务。事实上，在面对不确定性时，最短加工时间的加权版本是一种最通用的调度策略。它提供了一个简单的时间管理方法：每接到一件新工作时，通过其将耗费的时间来对其进行重要性的划分。如果该重要性高于当前正在执行的任务，就切换到新任务，不然就坚持当前任务。
计算机科学能给我们提供用单机调度的运用不同度量标准的最优算法，但选择哪种度量标准就取决于自己。这为我们提供了一种激进的方法来重新思考“拖延”这一时间管理的经典问题。我们通常认为拖延是一种错误的算法，但如果它正好相反呢？如果它是一个错误问题的最佳解决方案呢？
重点不只是要把事情做好，更重要的是把权值更高的事情做好-在每一时刻做好最重要的工作，这听起来像是治愈拖延症的一个行之有效的方法，但仅仅这样还不够。
优先反转和优先继承理论表明，想把事情做好的热情不足以避免调度上的陷阱，光有把重要事情做好的热情也不够，要承诺坚持做你所能做的最重要的事情。
有时候，最重要的事情要等不重要的事情完成之后才能进行。当某个任务在另一个任务完成之前无法启动时，调度理论家称之为“优先约束”。
六、
贝叶斯法则，预测未来
谷歌的研究部主任彼得·诺维德曾进行过一次题为“数据的不合理有效性”的著名演讲，该演讲深究了“数十亿琐碎的数据点最终如何能被理解”。媒体不断告诉我们，我们生活在一个“大数据时代”，计算机可以筛选这数十亿的数据点并发现一些肉眼看不到的细节。但跟日常生活联系最密切的问题往往是另一种极端。我们的生活充满“小数据”，我们就像看到柏林墙的戈特一样，也就是通过一个单一的观察，做一个推论。
以中彩票或赌博为例。
贝叶斯的关键见解是，试图使用我们看到的中奖和未中奖彩票来分析彩票来源于整体彩票池的方法，本质上是在倒推。他说，要做到这一点，我们需要先用假设向前推理。换句话说，我们首先需要确定，如果各种可能场景都成真的情况下，我们中奖的可能性有多少。这个被现代统计学家称为“可能性”的概率给了我们解决问题所需要的信息。
他表示，如果我们提前真的不知道彩票的情况，然后当我们第一次买的三张彩票中的一张彩票中奖了，我们可以推测奖池里彩票的总中奖比例为2/3。如果我们买三张彩票，都中奖了，那我们可以推测总中奖比例正好是4/5。事实上，如果买n张彩票共w张中奖，那么中奖率就是中奖数加1，除以所购买的数目加2，即。 这种令人难以置信的简单的方法估计概率的简单方法被称为拉普拉斯定律，它很容易就能适用于任何你需要通过历史事件来评估概率的情况。拉普拉斯定律的精髓就在于无论我们有一个单独的数据点或数以百万计的数据，它都同样适用。
描述这种关系的数学公式，将我们先前持有的观念和我们眼前的证据结合起来，就形成了后来的贝叶斯法则。有点儿讽刺的是，真正重要的工作却是由拉普拉斯完成的。它提供了一个非常简单的解决方案来如何处理现有的信念与观察到的证据：将它们的概率相乘。每个假设的概率都是真实可能的，这就是所谓的先验概率，或者简称为“先验”。贝叶斯法则总是需要一些先验，即使它只是一个猜测。
理查德•戈特三世在1969年针对柏林墙倒塌的预测时设想，他到达柏林墙时的那一刻并不特殊，如果有任何一个时刻都有同样的可能性，那么平均来讲，他的到来应该是在一个精确的中间点。如果我们假设我们到达的中间点有精确的时间，那么对于它在未来还可以持续多久的最佳猜测就变得很明显：确切地说就是它已经存在的时间。这个简单的推理，被戈特称为“哥白尼原则”，因为哥白尼400年前曾经问道：我们在哪？
哥白尼原则是应用贝叶斯法则无信息先验的结果，应用贝叶斯法则，我们首先需要给每个现象的持续时间分配一个先验概率。在认识到哥白尼原则是无信息先验基础上的贝叶斯法则之后，就可以回答很多关于其有效性的问题。哥白尼原则在我们什么都不知道的情况下似乎是合理的、准确的，如在1969年看到的柏林墙，我们不确定什么时间范畴是合适的。同时，在我们对某一对象的确有所了解时，就会感觉这是完全错误的。预测一个90岁的人能活到180岁是不合理的，这恰恰是因为我们关于人类寿命已经了解了很多——在这种情况下，我们就可以预测得更好。我们给贝叶斯法则带来的先验信息越丰富，我们便能从中得到越有用的预测。
真实世界的先验。从广义上将，世界上有两种类型的事物：倾向于（或围绕）某种“自然”价值的事物，以及与之相反的事物。
比如人的寿命，属于前一类，遵循所谓的“正态分布”，或称为“高斯分布”，以及被称为“钟形曲线”。城市人口的分布可能就符合“幂律分布”，或称为“无标度分布”。贝叶斯法则告诉我们，在基于有限证据进行预测时，很少有事情是和好的先验一样重要的，也就是说良好的预测要有良好的直觉，要知道何时再处理一个正态分布，何时在处理一个幂律分布。事实证明，贝叶斯法则为我们处理这些情况各提供了一个简单但显著不同的预测经验法则。
对于任何幂律分布，贝叶斯法则表明，一个合适的预测策略就是相乘法则：将迄今观察到的数量乘以一些常数。对于无信息先验，这个常数一般是2。而将正态分布作为贝叶斯法则的先验时，我们将运用平均法则：使用分布的“自然”平均数作为指导。
正态分布的东西似乎太长了，最后必然会很快结束。但幂律分布的东西存在的时间越长，你可以预测它继续下去的时间就越长。 在这两个极端之间，生活中实际上还有第三种事物：那些不具有更大或更小可能性结束的事物，只因为他们已经持续存在了一段时间。有时候事情是简单的、不变的。丹麦数学家瓦格纳·厄兰研究了这种现象，他将独立事件之间的间隔形式化并推导出带有他名字的函数：厄兰分布。厄兰分布给出了第三种预测法则——相加法则：总是预测事物只会再持续一个常量。
结论：这三个非常不同的最佳预测模式——相乘法则、平均法则和相加法则都是通过将贝叶斯法则应用到幂律、正态和厄兰分布上得出结果的。
七、
过度拟合，不要想太多
从根本上说，过度拟合就是对数据的一种偶像崇拜，产生的原因是将重心放在我们能够测量的数据而不是真正重要的问题上。
举例来讲，过度拟合解释了我们具有讽刺意味的味觉。如果按照进化论来说，味蕾的整个功能都是为了防止我们吃坏掉的东西，那么为什么我们最喜欢吃的食物都被认为是对我们的健康有害的呢？答案是，味觉是我们身体的健康指标。脂肪、糖和盐是重要的营养物质，在长达几十万年的时间里，食用含有这些物质的食物是持续性饮食的一个合理方法。 但当我们能够改善所食用的食物时，这种关系就被打破了。我们现在可以把脂肪和糖添加到食物中去，但这些食物的量已经超出我们身体可承受的健康范围，但是我们还是只喜欢吃那些食物，而不是吃蔬菜、谷物和肉类这些构成人类正常饮食习惯的食物。换句话说，我们可以过度拟合食物的味道。过度拟合的问题也出现在运动健身和培训当中，再比如在应试教育中，学生技能偏向考试技巧，说明开始对考试本身这个机制出现过度拟合。
机器学习的研究已经得出了一些具体的策略以检测过度拟合，而最重要的问题之一就是所谓的交叉验证。
从统计的观点来看，过度拟合是我们对看到的实际数据太过敏感的体现。那么，解决方案也是直截了当的：我们必须平衡我们的愿望，找到我们应该使用的对抗复杂性的模型进行分析。 在几个相互竞争的模型中选择一种方法就是奥卡姆的剃刀原理，它表明，所有的事情都是平等的，最简单的假设可能就是最正确的那个。
在20世纪60年代，苏联数学家安德烈·季霍诺夫给出了一种答案：引入一个额外项来计算惩罚更复杂的解决方案。如果我们引入复杂性惩罚，那么更复杂的模型需要做的不仅是做得更好，更重要的是解释数据以证明其更大复杂性的合理性。计算机科学家将这个原则——使用约束来惩罚模型的复杂性，称为正则化。
那么这些复杂性惩罚是什么呢？1996年，生物统计学家罗伯特·蒂什拉尼开发“套索算法”，通过对模型中各因素总和的惩罚，将这种下行压力放到因素的总权重上，套索算法将驱使它们降为零，只有对结果又很大影响的因素才保留。同一类原则复杂度惩罚原则也同样出现在自然界中。例如，新陈代谢的负担对生物体的复杂度起到刹车作用，对过度精细的机体运行引入热量惩罚机制，以免进化成更复杂的大脑，因为从进化论的角度，一个更复杂的大脑无法提供足够的报酬。
如果我们观察生物（包括人类）的进化方式，我们会注意到一些有趣的现象：变化发生得很缓慢。这意味着，现代生物的属性不仅受制于它们目前所处的环境，也由它们过去的历史共同塑造而成。过度拟合的概念给我们提供了一个能在进化的压力下看到其长处的机会。虽然交叉神经纤维和改变用途的颌骨似乎已经是最理想的安排，但至少我们应该认识到，我们并不一定要让进化去完全优化生物，以适应生态环境的每一点改变，这样做会使其对环境的变化极其敏感。另一方面，必须利用现有的材料，施加一种有用的约束。这使得它很难引起生物体结构的急剧变化，更难拟合。作为一个物种，受制于过去，就使我们不能完全地调整以适应目前所知的情况，但这有助于我们在未知的未来保持身体强健。
在机器学习中，缓慢移动的有点最明显出现在一种称为早期停止的正则化技术中。在各种机器学习任务中，正则化的有效性表明，我们可以通过有意识地思考和少做一些事情来做出更好的决定。如果我们最先想到的因素可能是最重要的因素，那么如果思考的量超过某一个度的话，就不仅是浪费时间和努力，它将会让我们找到更糟糕的解决方案。早期停止为理性的论证而不是一味地推理提供了基础。
如果你有很高的不确定性和有限的数据，那么务必提前停止。如果你不清楚你的工作将如何被评估，以及由谁来评估，那么你就不值得花额外的时间来对你自己（或者其他人）的特质做出所谓完美的判断。不确定性越大，你所能衡量的东西和真正重要的东西之间的差距就越大，你就越应该注意过度拟合的风险，也就是说，你越喜欢简单，就应该越早停下来。
八、
松弛，顺其自然
正如计算机科学家在过去几十年里所发现的那样，无论我们的计算机处理速度有多快，我们如何巧妙地对它们进行编程，一个问题的完美解决方案都是不存在的。事实上，没有人能像计算机科学家那样理解，在面对看似无法控制的挑战时，你既不应该永远辛苦工作，也不应该放弃，但我们将会看到第三种尝试。
"约束优化“问题：如何找到一组变量的最佳排列，并给出特定的规则和积分法。这就是”旅行推销员问题“，到目前为止还没有得到解决的问题。如果，如何最好地解决那些最佳答案似乎遥不可及的问题，如何学会放松。
在计算机科学中最简单的放松形式之一就是约束松弛。在这项技术中，研究人员消除了一些问题的约束，并着手解决他们希望得到解决的问题。然后，在他们取得一定的进展之后，他们试图再将约束添加进去。也就是说，在把问题带回现实之前，他们会让问题暂时更容易处理。
旅行推销员问题，就像寻找最佳座位安排的问题一样，是一种特殊的最优化问题，称为“离散优化”，即在解决方案中没有平滑的连续统一体。推销员要么到这个镇子，要么到那个镇，你要么在5号桌，要么在6号桌。两者之间没有灰色地带。
有很多方法可以对一个问题进行松弛，我们已经看到了三个最重要的问题。首先，约束松弛，简单地消除一些约束，在回到现实之前，先在更宽松的问题上取得进展。第二，持续松弛，将离散的或二进制的选择变成连续体：当决定是选冰红茶还是柠檬水时，先想象一个50：50的“阿诺德·帕尔默”混合，然后再向上或向下延展。第三，拉格朗日松弛，把不可能的变成仅仅是惩罚，要学会扭曲规则的艺术（或打破规则，并接受后果）。例如，摇滚乐队在决定将哪些歌曲放入一个有限的专辑中时，就要面对计算机科学家称之为的“背包问题”——将一组不同大小和重要性的项目装进一个有限的集合中的难题。在严格的公式中，背包问题是众所周知的棘手问题，但这并不妨碍我们松弛的摇滚明星们做决定。正如几个著名的例子所证明的那样，有时候稍微超过城市的宵禁，并付出相应的惩罚，好过把节目限制在适当的时间内。事实上，即使你没有违规，你也可以想象它具有启发性。
九、随机性 十、网络连接 十一、博弈论 （略）
