1700494672
算法之美：指导工作与生活的算法 [:1700494115]
1700494673
算法之美：指导工作与生活的算法 基廷斯指数
1700494674
1700494675
特例往往是通往宇宙奥秘的大门，这种情况在数学中也经常发生。20世纪70年代，联合利华公司请年轻的数学家约翰·基廷斯帮助他们优化药物试验。令人意想不到的是，基廷斯竟然解开了一道难住了一代数学家的难题。
1700494676
1700494677
基廷斯（牛津大学统计学教授）认真地思考了联合利华提出的问题：已知有几种不同的化合物，如何以最快的速度确定哪种化合物可能对哪种疾病有效？基廷斯把这个问题变成了尽可能简单的形式：有多个可选方案，每个可选方案得到回报的概率不同，可分配的精力（金钱或时间）是确定的。于是，这个问题变成了多臂老虎机问题的另外一个化身。
1700494678
1700494679
无论是追逐利润的制药公司，还是他们所在的医药行业，都经常需要面对探索与利用如何取舍的竞争需要。制药公司希望投入到研发部门的资金可以帮助他们发明新药，但是他们同时还希望现在正在帮助他们赚钱的生产线继续开足马力。医生在开处方时，肯定希望病人在现有条件下得到最好的治疗，但是他们也希望实验研究可以找到更有效的治疗手段。
1700494680
1700494681
显而易见，在这两种情况中，我们都无法确定相关的剩余时间到底是什么。从某种意义上讲，制药公司和医生一样，都对不确定的未来感兴趣。制药公司希望可以永远存在下去，而医药行业则希望取得突破，甚至希望在人们出生之前就可以向他们提供帮助。不过，他们对当前时间的重视程度更高：今天就把病人治愈，其价值高于让病人一周以后，甚至一年以后才康复，利润方面当然同样如此。经济学家把这种重现在、轻将来的概念称作“贴现”。
1700494682
1700494683
基廷斯在研究多臂老虎机问题时采用的就是这些术语，这是他与之前的研究人员不同的地方。在他的构想中，他的目标不是在固定时间段里追求最大回报，而是在时间无限长但是价值被打折扣的未来追逐最有利的结果。
1700494684
1700494685
这种贴现在我们自己的生活中并不鲜见。如果你准备在一座城市逗留10天，那么你在选择餐厅时就要记住逗留时间已经确定这个事实，但是，如果你居住在这座城市，时间就没有多大意义了。此时，你也许会想，时间越久，回报贬值的程度就越大：你更关心的是今天的晚餐，而不是明天的晚餐，并且对明天晚餐的关心程度又高于一年之后的晚餐。至于关心程度到底有多大差别，取决于你采用的“贴现函数”。基廷斯设置的条件是回报价值呈几何级数贬值，也就是说，每次去餐厅进餐的价值是上一次的分数倍。如果你认为每天被车撞的可能性为1%，那么在评估明天晚餐的价值时，就应该把它设定为今天晚餐价值的99%，因为你有可能根本没有机会享受明天的晚餐。
1700494686
1700494687
设定了这种几何贴现条件之后，基廷斯提出了这样一个策略：分别考察多臂老虎机的各个拉把，然后计算出各个拉把自己的价值。通过一个别出心裁的设想——贿赂，基廷斯完成了自己的研究，并且认为这个策略“至少可以给出一个效果不错的近似估计”。
1700494688
1700494689
在《交易还是不交易》（Deal or No Deal）这个热门电视节目中，参赛者要从26个箱子中选择一个。箱子里装有奖金，金额1美元~100万美元不等。随着游戏的进行，一位被称作银行家的神秘人物就会时不时出现。他愿意支付给参赛者金额不等的一笔钱，条件是参赛者不要打开他选中的那只箱子。参赛者需要做出选择，或者接受这笔实实在在的钱，或者选择装在箱子里的数额不确定的奖金。
1700494690
1700494691
基廷斯发现（尽管多年之后第一期《交易还是不交易》节目才播出），多臂老虎机问题与之并无区别。我们对每一台老虎机都知之甚少，甚至一无所知，但是它们都有某个保底回报率。如果摆在我们面前的不是老虎机，而是它的回报率，那么我们肯定不会去玩老虎机游戏。这个数字（基廷斯称之为“动态分配指数”，现在全世界都把它叫作“基廷斯指数”）告诉我们一条显而易见的赌博策略：一定要选择指数最高的那个拉把。[1]
1700494692
1700494693
事实上，基廷斯指数并不仅仅是一个效果不错的近似估计，还可以彻底解决回报按几何级数贴现的多臂老虎机问题。探索和利用之间的矛盾可以被转化成一个比较简单的任务：用一个数量使两者达成平衡并求这个数量的最大值。在说到自己的成就时，基廷斯非常谦虚，笑着说道：“这又不是费马大定理。”但是，他的这个定理让一大堆涉及探索与利用这个两难选择的问题得到了解决。
1700494694
1700494695
不过，即使知道以往的记录和贴现率，特定机器基廷斯指数的计算仍然非常复杂。但是，一旦我们知道某些特定条件下的基廷斯指数，我们就可以利用这些指数解决相同形式的任何问题。重要的是，由于每个拉把的基廷斯指数都是独立计算出来的，因此涉及的拉把个数不会产生任何影响。
1700494696
1700494697
下表给出了0~9次输赢所对应的基廷斯指数值，条件是回报以90%的比例递减。利用这些数值，可以解决日常生活中的多种多臂老虎机问题。例如，在这些条件下，你应该选择以往记录为1-1（即期望值为50%）的那台老虎机，而不选择记录为9-6（即期望值为60%）的那台机器。在下表中查询这两台机器对应的坐标就可以发现，了解得不多的那台机器的基廷斯指数为0.6346，而玩得比较多的那台机器得分仅为0.6300。问题解决了：这一次可以碰碰运气，大胆探索。
1700494698
1700494699
仔细观察表中的基廷斯指数，就会发现一些有意思的东西。首先，你会发现赢就留下这个原则在发挥作用：任选一排，从左向右看去，就会发现指数值一定在增长。如果在某个时候某个拉把是你的正确选择，而且你拉下那个拉把之后真的赢钱了，那么再次选择这个拉把就是一个明智的决定（沿着图表自左至右）。其次，你可以看出在什么情况下输就离开这个原则会误导你。先赢9次，然后输钱1次，对应的基廷斯指数为0.8695，仍然比表中的大多数指数高，因此你不要急于离开，至少再拉一次这个拉把。
1700494700
1700494701
表2-1 基廷斯指数值与输赢的关系
1700494702
1700494703
1700494704
1700494705
1700494706
注：在回报以90%的比例递减时的情况。
1700494707
1700494708
但是，该表最有意思的地方是左上角的那一格。0-0这个记录（表明我们对这个拉把一无所知）所对应的期望值是0.5000，但是基廷斯指数是0.7029。换句话说，一台你从来没有玩过的机器，比你玩了10次，其中有7次赢钱的机器更有吸引力！沿着对角线向右下方前进，就会发现1-1这个记录对应的指数是0.6346，记录2-2对应的是0.6010，等等。如果这个50%的赢钱率一直保持下去，基廷斯指数最终会驱近于0.5000，而经验证明，这台机器的确没有任何特别的地方，它最终会收走那些刺激我们进一步探索的“奖金”。但是，收敛过程进展非常缓慢，探索奖励的刺激作用非常大。的确，我们可以看到，即使第一次拉下拉把后输了钱，0-1这个记录所对应的基廷斯指数仍然高于50%。
1700494709
1700494710
我们还可以看出改变贴现率后探索与利用会发生什么样的变化。下表列出的内容与前表相同，不过条件是回报递减的比例不是90%，而是99%。在未来与现在的权重几乎相同时，相对于十拿九稳的事情而言，偶然发现的价值上升得更快。从这张表可以看出，从未测试过、记录为0-0的机器可以确保有86.99%的赢钱概率！
1700494711
1700494712
由此可见，基廷斯指数以一种正式、严谨的形式，证明了在有机会对探索结果加以利用时，我们应该倾向于选择未知的新事物。有一句古老的谚语说：“邻家芳草绿。”数学可以告诉我们其中的道理。尽管我们实际上认为未知事物可能差不多，甚至有可能更差，但是它也有可能更好。球队新球员没有经过检验，但是他的价值却高于能力似乎差不多的老手（至少在赛季初如此），原因正是我们对他知之甚少。探索行为本身就有价值，因为尝试新鲜事物可以增加我们发现最佳选择的机会。因此，不仅关注当前，同时还把未来纳入我们视野的做法，可以驱动我们不断尝试新鲜事物。
1700494713
1700494714
表2-2 基廷斯指数值与输赢的关系
1700494715
1700494716
1700494717
1700494718
1700494719
注：在回报以99%的比例递减时的情况。
1700494720
1700494721
因此，基廷斯指数为我们指出了一个轻而易举地解决多臂老虎机问题的方法。但是，这并不是说这个难题已经彻底得到解决，也不意味着基廷斯指数可以帮助我们处理日常生活中所有探索与利用的取舍问题。原因之一是基廷斯指数只有在某些强假设条件下才是最优策略。各种各样的行为经济学与行为心理学实验都不建议人们对未来奖励实行几何贴现（即每次拉动拉把的价值都是上一次的分数倍）的做法。此外，如果不同方案之间的转换需要付出成本，那么基廷斯指数就不再是最有效的策略。（邻居家的草地看起来可能真的更绿一些，但这并不是我们翻过篱笆的理由，更不用说通过二次抵押贷款把邻居家的房子买下来了。）更重要的是，在匆忙之间很难计算出基廷斯指数。如果随身携带一张指数表，你可以找到晚餐的最佳选择，但是你得到的好处可能还不足以弥补你需要付出的时间和精力。（“等一等，我可以解决这个问题。这家餐厅的好评率是29/35，另一家的好评是13/16，因此它们的基廷斯指数分别是……嘿，人呢？”）