插一句:这个问题,我之前写过三篇相关的博客(有一篇竟然不知道怎么被不小心覆盖了。悲伤。。。),感兴趣的可以先参考: ● http://blog.csdn.net/allenalex/article/details/78220926 ● http://blog.csdn.net/allenalex/article/details/78242068 当然,这本书里的这一章节,对这个问题整理的非常好。推荐大家认真学习一遍。
推荐系统总的EE问题 直译过来就是“探索-利用”问题。 先直观理解: 探索:我要不要尝试新的(推个新物品怎么样?) 利用:现在推的这个东西还可以阿。要不要继续? 所谓EE均衡,就是在这两者之间达到某种平衡。
本章主要包括以下内容: 3.1节:简单介绍了EE均衡问题 3.2节:常见的EE方法 3.3节:讨论了推荐系统中的EE挑战 3.4节:处理EE挑战的主要思想
MAB的简单描述网上一搜一大把。这里不过多探讨。给出书中的一段较形式化的定义: 使用 θt 代表赌徒在t时刻摇臂前所获得的所有信息。 θt 可称之为t时刻的状态参数或者就叫做t时刻的状态。主要包括每个臂i到t时刻时的摇臂次数 γi 以及总奖励 αi 。 一个摇臂机制(bandit scheme,或者又叫EE机制(explore-exploit scheme)、策略)就是一个决策函数 π :它的输入时θt,输出是下次要摇的臂。摇臂机制可以是状态参数的一个确定性函数,也可以是一个随机函数。
MAB 主要可以分为以下三类: ● 贝叶斯方法(Bayesian methods ) ● 极大极小方法(minimax methods) ● 启发法(heuristic methods)
:(这块还没完全弄懂。主要是beta分布那块) 从贝叶斯的角度,可以把MAB问题定义为一个马尔科夫决策过程(MDP)。最优解可以通过动态规划解决。当然,尽管存在最优解,但要求解,计算复杂度非常高。 对MAB定义一个 β-二项式 MDP(Beta-binomial MDP):
状态 了最大化收益,赌徒需要估计每个臂的奖励概率。 设t时刻的状态 θt 表示赌徒在t时刻前基于实验数据所获得的知识。 对于每个臂,所知的信息用一个两个参数的贝塔分布表示。也就是: θt=(θ1t,...,θKt) 其中 θit 为t时刻i的状态: θit=(αit,γit) 也就是臂i用一个两个参数的beta分布表示。其中 γit 表示臂i到t时刻时的摇臂次数, αit 表示臂i到t是所获得的总收益。 分布满足: 平均值表示基于到目前为止所有数据,赌徒对奖励概率的一个经验估计。而方差衡量他的估计的不确定性。状态转换 赌徒通过摇臂i并观察它的输出可以获得关于臂i的更多输出。状态由θt转换为θ(t+1)。这里,对应是否获得收益(奖励),有两种可能的新状态: - 赌徒有 αit/γit 的概率获得奖励,状态由 θit=(αit,γit) 转换为状态 θi,t+1=(αit+1,γit+1) - 1. 没获得奖励的概率为1 - αit/γit , 状态转换为 θi,t+1=(αit,γit+1) 其他所有的臂j的状态保持不变;也就是 θj,t+1=θj,t ,这是经典老虎机问题(classical bandit problem)的一个重要特性。我们使用 p(θt+1|θt,i) 表示转换概率,表示摇臂i后状态由 θt 到 θt+1 的概率。因为在当前状态下转换的新状态只有两种,所以转换到其他其他状态的概率为0。 以上的状态转换遵循beta-二项式共轭(这个不太懂)。使用ci ∈ {0, 1}表示赌徒在摇臂i后是否获得收益。如果我们假定: 其中,pi为 奖励概率,那么, (pi|ci)∼Beta(αit+ci,γit+1) 奖励 奖励函数Ri(θt, θt+1)定义摇臂i从状态θt 到 θt+1 期望的奖励。经典的老虎机问题中,这个奖励函数定义非常简单:如果状态由 (αit, γit) 转换为 (αit + 1, γit + 1); 就换的一单位的奖励,否则 就是没有奖励。最优策略(Optimal Policy) 原文没有给出具体的算法。提到了一种‘Gittins index’,感兴趣的读者可以参考: 1) Gittins, J. C. 1979. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society. Series B (Methodological), 41(2), 148–77 2)Nino-Mora, Jos ˜ e. 2007. A (2 ´ /3)n3 fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain. INFORMS Journal on Computing, 19(4),596–606
此外,还有一段比较详细的讨论了最优解问题。有一定的理论深度,我也没有深入研读。感兴趣的读者可以参考原文。
关注UCB算法。
其中,3.12公式的前一项表示臂i当前奖励概率的一个估值,后一项表示估计的不确定性。 参考:Auer, P. 2002. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3, 397–422. 除此之外,还可以参考我的另一篇博文:http://blog.csdn.net/allenalex/article/details/78242068
有以下几种机制(方法):
epsilon-Greedy算法.这个方法,可以直接参考我的另一篇博文:http://blog.csdn.net/allenalex/article/details/78220926SoftMax; 首先定义一个称之为“温度”的参数–τ,每次摇臂i的概率为: 当τ很高的时候, ep^i/τ→1 ,那么每个臂被选中的概率就几乎一样。相反,如果 τ很低,则几乎总是选择奖励概率最大的那个臂。 下面这两种,本文见得比较少。不翻译整理了,直接贴出原文。通常,贝叶斯方法计算复杂度高,但是如果建模假设合理,性能相对更好。相反,极大极小值方法在最坏的情况下能够实现最好的性能,但是要平均要尝试的次数更多。实践中通常使用基于启发式的方法。启发式方法实现相对更简单,并且通过合适的调节,能够实现合理的性能。