《Scala机器学习》一一2.3　探索与利用问题

本节书摘来自华章计算机《Scala机器学习》一书中的第2章，第2.3节,作者：[美]　亚历克斯·科兹洛夫（Alex Kozlov），更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.3　探索与利用问题

探索（exploration）与利用（exploitation）的应用很广，从资金分配到研究自动驾驶汽车项目都在使用，但它最初也是源于**问题。该问题的经典形式是一个多臂**机（*）问题，即假设有一个或多个手臂的**机，按次序以未知概率来拉动每个手臂，以此来表示独立同分布的回报。在这种简化模型中不断独立地重复。假设多个手臂间的回报是独立的。其目标是最大化回报（比如赢钱的金额），同时还要最小化学习成本（即在小于最优获胜率的情况下拉动手臂的次数）。假设已经给定了一个手臂选择策略，显然需要在寻找一个能得到最优回报的手臂与利用已知最好手臂之间做出权衡。

其中Si是N次试验中选择的第i个臂。多臂**机问题在20世纪30年代被广泛研究，而在本世纪初，随着金融和互联网广告技术领域的出现，它再次受到关注。通常由于问题的随机性，使pseudo-regret的期望界好于N的平方根。pseudo-regret可以控制到以log N为界（Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems by Sebastien Bubeck and Nicolo Cesa-Bianchi，http://arxiv.org/pdf/1204.5721.pdf）。
在实践中最常用的策略是策略，这种策略选择最优的手臂的概率是（1―），而选择另一个手臂概率为。这种方法可能会在那些根本不带来回报的手臂上花费大量的资源。UCB策略优化了策略，通过预估最大回报的手臂，然后再加上回报估计的某些标准偏差。这个方法需要在每一轮中再次计算最佳手臂，并且需要近似估计均值和标准偏差。另外，UCB必须在每轮中重新计算估计值，这可能会带来扩展性问题。
最后来介绍Thompson采样策略。它使用一个固定的随机采样，该采样服从-伯努利后验估计，并且赋给下一个能给出最小期望后悔（regret）的手臂。这种数据可以避免参数重新计算。尽管需要假设具体的数，但下图仍对这些模型的性能进行了有效比较：

图2-4　当K＝5时，单臂*和不同策略的情形下，对采用不同研究-利用策略的模拟结果
图2-4显示了不同策略的仿真结果（http://engineering.richrelevance.com/recommenda-tions-thompson-sampling）。随机策略仅仅是随机地分配手臂，对应于纯粹的探索（explora-tion）模式。朴素策略是随机达到特定的阈值，再转成利用（exploitation）模式。Upper Confidence Bound（UCB）模式使用95%的置信区间，而UCB1是UCB的修改版，它考虑了分布的对数正态性。最后是Thompson策略，它通过实际的后验分布给出一个随机抽样来优化后悔值。
探索和利用模型对初始条件和异常值非常敏感，特别是在低响应的情形下。这已经在基本卡死的臂上进行过了大量的试验。
另一种增强的策略是基于额外的信息（如位置）来估计更好的先验，或者根据这些额外的信息限制手臂集，以便探索K。但这些会涉及更专业的领域（如个性化或在线广告）。