当前位置:首页 » 机器学习电子书 » 正文

算法之美 - 电子书下载(高清版PDF格式+EPUB格式)

2523 人参与  2018年12月28日 00:12  分类 : 机器学习电子书  评论

算法之美-[美]布莱恩·克里斯汀 汤姆· 格里菲思

            在线阅读                   百度网盘下载(d14s)


image.png

书名:算法之美

作者:[美]布莱恩·克里斯汀 汤姆· 格里菲思

格式:EPUB, HTMLZ, PDF

书号:9787508686882

路径:点击打开

出版:中信出版集团

排序作者:格里菲思, 布莱恩·克里斯汀 汤姆·

排序书名:算法之美

日期:08 12月 2018

uuid:42a26798-68a1-450d-8144-333a370d573d

id:472

出版日期:5月 2018

修改日期:08 12月 2018

大小:4.20MB

语言:中文


假设你想租房子,正在旧金山四处寻找房源。旧金山可能是整个美国最难找房子的城市了。由于技术产业的蓬勃发展,再加上城市区划法律严格限制建造新住房,旧金山的房租已经与纽约不相上下,甚至比纽约还高。房源清单列出来几分钟,房子就会被人们一抢而空。通常情况下,只有第一个把定金支票塞到房东手里的人,才能拿到房子的钥匙。

理论上讲,认真调查、仔细斟酌是理性消费者的一大特征,但是旧金山的残酷市场并没有为他们留有权衡考虑的机会。在购物中心或者网上购物时,人们可以反复权衡再做出决定,但是将要入住旧金山的租客没有这个特权,他们必须迅速做出决定:要么舍弃其他所有可能的选择,就选定当前正在看的这套房子,要么掉头就走,再也不要回头。

简单起见,我们姑且假设,你唯一关心的就是尽最大可能增加挑中最理想公寓的机会。你的目标是把“看过的好房子被人挑走”与“还有好房子没来得及看”这两种遗憾的发生概率降至最低。于是,你立刻发现自己陷入了两难境地:如果没有衡量的标准,如何判断一套公寓是否是最合适的呢?如果你不先看一些公寓(这些公寓将被你放弃),又如何确定衡量标准?你收集的信息越多,越能在最合适的机会出现时准确地认出它,但是你已经与最合适的机会失之交臂的可能性也越高。

那么,到底该怎么办?如果收集信息的行为会危及结果,那么怎样才能在掌握足够多信息的基础上做出明智决定呢?这个令人极其为难的情境近乎于一个悖论。

在被问及此类问题时,大多数人凭直觉给出的回答可能大致如此:这需要在继续挑选与立刻下手之间达成某种平衡。也就是说,你必须先看足够多的房子,确定一个标准,然后接受符合这个标准的房子。事实上,平衡概念正是解决这类问题的关键。但是,大多数人根本无法确定这个平衡点在哪里。好消息是,这个平衡点已经被找出来了。

答案就是37%。

如果你希望选中最合适公寓的可能性达到最大,那么在看前37%的房子时不要做出任何决定(如果你准备花一个月的时间挑选房子,那么在前11天不要做出决定)。这段时间你是在为制定标准做准备,因此看房子时把银行卡放在家里吧。但是,过了这个时间点之后,你就要做好随时签约的准备(包括准备好定金等),一旦你对某套房子的满意程度超过之前看过的所有房子,就立刻下手。在继续挑选与立刻下手之间做出的这种妥协,并不仅仅是一种直觉,而是已经得到证明的最优解。

我们知道这个答案,是因为找房子问题属于数学上被称作“最优停止”(optimal stopping)的一类问题。37%法则明确了解决这些问题的一系列简单步骤(计算机科学称之为“算法”)。事实证明,找房子仅仅是最优停止问题在日常生活中的表现形式之一。在面临一连串选择时如何做出决定的难题,经常会改头换面,以不同的形式出现在我们的生活当中。在驶入停车位之前,需要绕整个停车场多少圈?在商业风险中何时套现脱身?在买房子或者停车时,何时是结束观望、做出决定的最佳时机?

在约会这个更加令人头疼的问题上,人们也经常要面对这样的难题。最优停止理论是一夫一妻婚姻制度催生的科学。

每天,人们都要面临最优停止问题的困扰(当然,诗人更愿意追逐的话题肯定是求婚带来的烦恼,而不是停车时的两难境地),有时甚至会因此而痛苦不堪。不过,我们大可不必如此,因为这类问题至少可以通过数学方法来解决。借助并不繁复的算法,我们不仅可以解决找房子的问题,生活中遭遇的所有最优停止问题都可以被妥善处理。

从本质上讲,我们身边经常出现因为租房子、停车、求婚而感到苦恼的人,这些人其实就是在自寻烦恼。他们需要的不是治疗师,而是一种算法。治疗师告诉他们要在冲动与多虑之间找到一个正确的、舒服的平衡点。

算法告诉他们这个平衡点就是37%。

由于我们生活在有限的时间和空间之中,因此所有人都会面临一系列特定的问题,诸如在一天或者十年里,哪些事必须做,哪些事应当放手?如何在尝试新的体验与从事自己喜爱的活动中取得平衡,才能生活得惬意自在、心满意足?

这些问题看起来似乎都是人类特有的,其实不然。半个多世纪以来,计算机科学家苦苦思考的问题(有很多已经得到妥善解决)与这些日常难题在本质上并无区别。例如,处理器在执行用户请求时应该如何分配自己的“注意力”,才能降低费用、节省时间?在什么情况下应该在不同任务之间来回切换?刚开始应该接受多少任务量?如何利用有限的存储资源取得最佳效果?应该收集更多数据,还是根据已收集的数据采取行动?对人类而言,如何把握今天可能不是一件易事,但是我们身边的计算机可以轻轻松松地把握每一毫秒。显然,计算机有很多值得我们借鉴的地方。

将算法与人类生活相提并论似乎是一件很奇怪的事。在很多人看来,“算法”这个词意味着神秘莫测的谋划与操作,与大数据、大政府、大企业有密切的联系,正在逐渐变成现代社会基础架构中一个越来越重要的部分。其实,算法指的就是解决问题的一系列步骤,其含义远不限于计算机,存在的历史也远远长于计算机。在计算机开始使用算法之前,人类早就将算法应用到生活当中了。

“算法”(algorithm)一词得名于波斯数学家花拉子密。公元9世纪,这位数学家写过一本书,讨论用纸笔解决数学问题的技巧。[书名为“al-Jabr wa’l-Muqabala”,其中的“al-jabr”就是后来“algebra”(代数)这个词的前身。]不过,最早的数学算法早于花拉子密。在巴格达附近出土的4000年前的苏美尔人泥板文献上,就刻有一幅长除法示意图。

任何受制于空间和时间限制的动态系统都是与一组基础的、不可避免的核心问题相背离的。这些问题本质上是计算性的,这使计算机不仅成为我们的工具,也成为我们的伙伴。其中我们可以得出三个简单的智慧道理。

首先,在某些案例中,计算机科学家和数学家已经确定了很好的算法方法,这些算法可以简单地转移到人类问题上。37%的规则,是最近最少使用算法处理满溢缓存的标准,以及作为探索指南的置信上限都是这方面的例子。

其次,即使你没有得到你想要的结果,但知道你正在使用最优算也是一种解脱。37%规则在63%的可能里会失败。用最近最少使用算法的标准来维护你的缓存并不保证你总能找到你想要的东西。事实上,也不会有特别的洞察力。用置信上限的方法来探索或利用权衡并不意味着你不会遗憾后悔,只是那些遗憾会随着你的生活慢慢积累起来。即使是最好的策略有时也会产生不好的结果,这就是计算机科学家要小心区分“过程”和“结果”的原因。“如果你遵循了最好的流程,那么你就已经尽了最大的努力,如果结果不顺心,你也不应该责备自己。”

结果会成为头条新闻(的确,是它们使我们生活的世界变成现在的样子),所以我们容易对结果念念不忘。但是过程是我们所能控制的。正如伯特兰·罗素所言:“看来我们必须考虑到客观公正的概率。”客观正确的行为可能是最幸运的。我将把这定义为最明智的行为。“我们可以希望变得幸运,但我们应该努力做到明智。”我们将其称之为计算克制。

最后,我们可以在容许和不容许直接解决方案的问题之间划出一条清晰的界限。如果你被困在一个棘手的问题

中,请记住,运用启发法、近似值和随机的策略可以帮助你找到可行的解决方案。在我们对计算机科学家的采访中,曾反复出现的一个主题是:有时“足够好”真的已经足够好了。更重要的是,意识到复杂性可以帮助我们选择问题:如果我们能够控制我们面对的情况,我们应该选择那些可以处理的问题。

但我们选择的不只是我们给自己安排的问题。我们也会选择我们给彼此安排的问题,无论是我们设计城市的方式还是我们问问题的方式。这就创造了横跨计算机科学和伦理学的惊人桥梁——以我们称之为计算性善意原则的形式。

在给本书安排采访时,我们中的两个人观察了一个悖论。平均而言,我们的面试者更有可能前来的预约时间是,比如“太平洋标准时间下周二下午1~2点”,而不是“在这一周任何方便的时间”。一开始,这似乎是荒谬的,就像那个著名的研究,平均而言,人们会捐更多的钱来拯救一只企鹅的生命,而不是8000只企鹅,或者人们报告称,更担心死于恐怖主义行为,而不是其他原因(也包括恐怖主义)。在采访问题中,人们似乎更喜欢受到约束的问题,即使这些约束要求严格,而不是完全开放的。对于他们来说,适应我们的偏好和约束似乎比根据他们自己的方式来计算出更好的选择要困难得多。计算机科学家们会在这里点头,并指出“验证”和“搜索”之间的复杂性差距,这就像你能听出一首听过的好歌曲和在现场写一首好歌曲之间的差距一样大。

尽管听起来很奇怪,但计算机科学隐含的原理之一便是,计算并不是好事:任何一种好的算法的指令都是把思考的劳动最小化。当我们与他人互动时,我们会向他们展示计算问题(不只是明确的要求和需求,而是隐含的挑战),例如在解释我们的意图、我们的信念和我们的喜好时。因此,对这些问题的计算性理解可以揭示人类相互作用的本质。我们可以通过构造问题来对其他人进行“计算性善意”,从而使深层的计算问题更容易。这很重要,因为许多问题,尤其是社会问题,就像我们所看到的那样,本质上是难以解决的。

考虑一下这个极为常见的情景。一群朋友站在一起,想决定要去哪里吃晚饭。他们每个人都有一些明显的偏好,尽管可能是弱的。但他们中没有人愿意明确表达这些偏好,因此他们用猜测和半暗示的方法来礼貌地应对社会危险源。

他们很可能会达成一项令所有人满意的决议,但是这个过程很容易出错。例如,大学毕业后的夏天,布莱恩和两个朋友去西班牙旅行。他们在飞行途中商定了旅行路线,有一点很清楚,他们没有时间去看之前研究和计划过的斗牛表演。三个人都试图安慰另外两人,就在这时,他们突然发现,事实上他们中没有一个人想要看斗牛。每一个人都只是在游戏中采用了他们所认为的其他人的热情程度,从而产生了其他人积极采取的热情程度。

同样,看似无害的语言比如“哦,我无所谓”或者“你今晚想做什么”实则含有黑暗的计算弱点,你应该三思。它表面上是善意的,却有两件令人震惊的事情。首先,它传递了认知责任:“这里有个问题,你要处理它。”其次,不要说出你的喜好,它会邀请其他人来模拟或想象它们。正如我们所看到的,对他人头脑的模拟是思维(或机器)所能面对的最大的计算挑战之一。

在这种情况下,计算善意和传统礼仪有分歧。礼貌地克制你的喜好会将推测性计算问题推给组内的其他人来解决。相反,礼貌地表达你的喜好(“我个人倾向于x。你认为是什么?”)有助于承担将团队带到问题解决办法上的认知负荷。

或者,你可以试着将你给别人选择的数量减少,而不是最大化,比如说,提供2~3家餐馆的选择,而不是10家。如果团队中的每个人都消除了他们最不喜欢的选项,那就会使任务变得更容易。如果你邀请某人出去吃午饭或安排会议,提出一个或两个他们可以接受或拒绝的具体建议,这会是一个好的起点。

这些行为都不一定是“有礼貌”的,但它们都能明显地降低交互作用的计算成本。

计算善意不仅是行为的原则,它也是一个设计原则。2003年,滑铁卢大学的计算机科学家杰弗里·夏利特研究了一个问题:如果在美国投入流通,多大的硬币面额能最大限度地减少硬币流通所需要的硬币数量。令人高兴的是,答案竟然是18分的面额,但夏利特在某种程度上没有通过计算性的考虑来制定政策建议。

目前,想要进行变化是非常简单的:对于任何给定的数量,只要尽可能多地使用25美分的硬币,然后尽可能多地使用10美分的硬币,以此类推,面额不断下降。例如,54美分是2个25美分,加4个1美分。有了18美分,这个简单的算法就不再是最佳的了:54美分最好是由3个18美分组成(没有25美分的硬币)。事实上,夏利特观察到,笨拙的面额会把改变的过程变成某种“至少和……旅行推销员问题同样困难的东西”。这个问题跟收银员关系密切。夏利特发现,如果将计算的易用性考虑在内,那么美国货币最好的供应量是只使用2美分或3美分的硬币。这不像18美分硬币这一结果那样令人兴奋,但长期看来几乎一样好,而且在计算上更具有善意。

更深层次的一点是,设计上的微妙变化可以从根本上改变对人类用户造成的认知问题。例如,建筑师和城市规划者对他们如何构建我们的环境有一些选择,这意味着他们可以选择如何构建我们必须解决的计算问题。

下面来考虑一个大型停车场,里面有各种不同的车道,这种车道经常出现在体育场馆和购物中心。你可以在一个车道上开车,看一个地点,然后决定让它去(希望是)前方一个更好的地方,但是,你没能找到这样的好运气,到达目的地之后沿着隔壁车道继续走。在开了一段路之后,你必须决定另一个停车位是否足够好,或者你将在第三条车道上搜索很远。

这里的算法视角不仅对司机有用,对建筑师也有用。将这些毛躁、混乱的决策问题与从目的地出发的单一线性路径做对比。在这种情况下,一个人简单地采用第一个可用的空间——没有博弈理论,没有分析,没有看完就跳走的规则。一些停车场就是这样的结构,从地面螺旋上升。它们的计算负载为零:人们简单地向前推进,直到第一个车位出现,然后接受它。无论对这种建设有什么其他可能的因素,我们都可以肯定地说,它对司机来说是一种认知上的人性化。

设计的主要目标之一应该是保护人们避免不必要的紧张、摩擦和精神劳动。(这不仅是一个抽象的问题,当商场的停车成为压力的来源时,购物者可能会花更少的钱,这样商场的回报就更少。)城市规划者和建筑师经常权衡不同的设计,考虑如何利用有限的空间、材料和金钱等资源。但是他们很少考虑他们的设计对使用者的计算资源增加负担的方式。认识到我们日常生活的算法基础(在这种情况下,是最优停止算法)不仅能让司机在特定的情况下做出最好的决定,而且还能鼓励规划者更仔细地考虑他们最开始迫使司机进入的问题。

还有一些其他例子,是在计算上更仁慈的设计。例如,考虑下餐厅座位政策问题。一些餐厅有一个“开放式座位”的政策,等待的顾客在那里徘徊,直到一张桌子被空出来,而第一个坐下来的人就会在这张桌子上用餐。其他人会记下你的名字,让你在酒吧喝一杯,当桌子准备好时再通知你。这些对稀缺共享资源管理的方法反映了计算机科学在“旋转”和“阻塞”之间的区别。当处理线程请求资源而无法获取时,计算机可以允许线程“自旋”——继续对资源进行永久检查,“它准备好了吗?”循环,或者它可以“阻塞”:停止那个线程,转换其他对象,然后在资源空闲的时候再回来。对于计算机科学家来说,这是一个实际的权衡:权衡在自旋中丢失的时间和在上下文切换中失去的时间。但在餐馆中,并非所有被交易的资源都是他们自己的。“旋转”的方式更快地填补了空桌子,但同时被损坏的中央处理器就是他们顾客的思想,被困在乏味且耗时间的警觉中。

作为一个类似示例,考虑一下公交站所带来的计算问题。如果有一个实时显示器提示说,下一辆车“10分钟后到达”,那么你就可以决定是否继续等待,而不是将公共汽车还没来的事实作为推论证据,一刻接一刻,然后不得不重新决定再决定。此外,你可以不再斜眼向下看路(旋转),在这10分钟你可以目视前方。(对于那些不能预测下一辆

公交车到达时间的城市来说,我们看到了贝叶斯法则甚至能让人知道最后一辆公共汽车什么时候离开的,这也是有用的代替。)这种计算善意的微妙举动,如果没有办法提供更多的话,也可以像对票价的补贴一样,对乘车有很大的帮助:可以把它当作一种认知补贴。

如果我们能善待他人,我们也可以善待自己。不只是计算善意,也包含更多的宽容,所有我们讨论过的算法和想法都将有助于解决这个问题。

理性决策的直观标准是仔细考虑所有可用的选项,并选择最好的选项。乍一看,电脑就像是这种方法的典范,只要它能得到完美的答案,就会不断地进行复杂的计算。但正如我们所见,这是一幅过时的图片,表明计算机做了些什么:这是一个简单的问题所能提供的奢侈品。在困难的情况下,最好的算法都是关于在最少的时间内做最合理的事情,这绝不是要仔细考虑每一个因素,并把每一次计算都算到最后。生活实在是太复杂了。

几乎在我们所考虑的每一个领域,我们越了解现实的因素(包括当面试求职者时,是否有不完整的信息,当试图解决探索或利用困境时,如何处理一个变化的世界,或者当我们试图把事情做好时,让某些任务依赖别人),就越有可能最终找到完美的解决方案,这需要不合理的长时间。事实上,人们几乎总是面临计算机科学面对的难题。在这些困难的情况下,有效的算法可以做出假设,倾向于更简单的解决方案体,将错误的成本与延迟成本进行权衡并开始冒险。

这些不是我们在不理性时做出的让步,它们是保持理性的手段。

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=1160

机器学电子书  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!