《StatisticalMethodsforRecommenderSystems》阅读笔记第三章（1）EE问题

     插一句&＃xff1a;这个问题&＃xff0c;我之前写过三篇相关的博客&＃xff08;有一篇竟然不知道怎么被不小心覆盖了。悲伤。。。&＃xff09;&＃xff0c;感兴趣的可以先参考&＃xff1a;
   ● http://blog.csdn.net/allenalex/article/details/78220926
   ● http://blog.csdn.net/allenalex/article/details/78242068
   当然&＃xff0c;这本书里的这一章节&＃xff0c;对这个问题整理的非常好。推荐大家认真学习一遍。

推荐系统总的EE问题
直译过来就是“探索-利用”问题。
先直观理解&＃xff1a;
   探索&＃xff1a;我要不要尝试新的&＃xff08;推个新物品怎么样?)
    利用&＃xff1a;现在推的这个东西还可以阿。要不要继续&＃xff1f;
所谓EE均衡&＃xff0c;就是在这两者之间达到某种平衡。

本章主要包括以下内容&＃xff1a;
   3.1节&＃xff1a;简单介绍了EE均衡问题
   3.2节&＃xff1a;常见的EE方法
   3.3节&＃xff1a;讨论了推荐系统中的EE挑战
   3.4节&＃xff1a;处理EE挑战的主要思想

3.2 Multiarmed Bandit Problem (MAB,多臂老虎机问题)

    MAB的简单描述网上一搜一大把。这里不过多探讨。给出书中的一段较形式化的定义&＃xff1a;
使用 θt代表赌徒在t时刻摇臂前所获得的所有信息。θt可称之为t时刻的状态参数或者就叫做t时刻的状态。主要包括每个臂i到t时刻时的摇臂次数γi 以及总奖励αi。 一个摇臂机制&＃xff08;bandit scheme&＃xff0c;或者又叫EE机制&＃xff08;explore-exploit scheme&＃xff09;、策略&＃xff09;就是一个决策函数π：它的输入时θt,输出是下次要摇的臂。摇臂机制可以是状态参数的一个确定性函数&＃xff0c;也可以是一个随机函数。

MAB 主要可以分为以下三类&＃xff1a;
    ● 贝叶斯方法&＃xff08;Bayesian methods &＃xff09;
    ● 极大极小方法&＃xff08;minimax methods&＃xff09;
    ● 启发法&＃xff08;heuristic methods&＃xff09;

3.2.1.贝叶斯方法

&＃xff1a;&＃xff08;这块还没完全弄懂。主要是beta分布那块&＃xff09;
   从贝叶斯的角度&＃xff0c;可以把MAB问题定义为一个马尔科夫决策过程(MDP)。最优解可以通过动态规划解决。当然&＃xff0c;尽管存在最优解&＃xff0c;但要求解&＃xff0c;计算复杂度非常高。
   对MAB定义一个 β-二项式 MDP&＃xff08;Beta-binomial MDP&＃xff09;:

• 状态 了最大化收益&＃xff0c;赌徒需要估计每个臂的奖励概率。 设t时刻的状态θt 表示赌徒在t时刻前基于实验数据所获得的知识。 对于每个臂&＃xff0c;所知的信息用一个两个参数的贝塔分布表示。也就是&＃xff1a;
               θt&＃61;(θ1t,...,θKt)
  其中θit 为t时刻i的状态&＃xff1a;
                  θit&＃61;(αit,γit)
  也就是臂i用一个两个参数的beta分布表示。其中γit 表示臂i到t时刻时的摇臂次数&＃xff0c;αit 表示臂i到t是所获得的总收益。
  分布满足&＃xff1a;
  
  平均值表示基于到目前为止所有数据&＃xff0c;赌徒对奖励概率的一个经验估计。而方差衡量他的估计的不确定性。
• 状态转换 赌徒通过摇臂i并观察它的输出可以获得关于臂i的更多输出。状态由θt转换为θ(t&＃43;1)。这里&＃xff0c;对应是否获得收益&＃xff08;奖励&＃xff09;&＃xff0c;有两种可能的新状态&＃xff1a;
                 - 赌徒有αit/γit 的概率获得奖励&＃xff0c;状态由θit&＃61;(αit,γit) 转换为状态θi,t&＃43;1&＃61;(αit&＃43;1,γit&＃43;1)
                 - 1. 没获得奖励的概率为1 - αit/γit&＃xff0c; 状态转换为θi,t&＃43;1&＃61;(αit,γit&＃43;1)
      其他所有的臂j的状态保持不变&＃xff1b;也就是θj,t&＃43;1&＃61;θj,t&＃xff0c;这是经典老虎机问题&＃xff08;classical bandit problem&＃xff09;的一个重要特性。我们使用p(θt&＃43;1|θt,i)表示转换概率&＃xff0c;表示摇臂i后状态由θt到θt&＃43;1的概率。因为在当前状态下转换的新状态只有两种&＃xff0c;所以转换到其他其他状态的概率为0。
          以上的状态转换遵循beta-二项式共轭&＃xff08;这个不太懂&＃xff09;。使用ci ∈ {0, 1}表示赌徒在摇臂i后是否获得收益。如果我们假定&＃xff1a;
  
  其中&＃xff0c;pi为 奖励概率&＃xff0c;那么&＃xff0c;
                     (pi|ci)∼Beta(αit&＃43;ci,γit&＃43;1)
• 奖励 奖励函数Ri(θt, θt&＃43;1)定义摇臂i从状态θt 到 θt&＃43;1 期望的奖励。经典的老虎机问题中&＃xff0c;这个奖励函数定义非常简单&＃xff1a;如果状态由 (αit, γit) 转换为 (αit &＃43; 1, γit &＃43; 1); 就换的一单位的奖励&＃xff0c;否则 就是没有奖励。

• 最优策略&＃xff08;Optimal Policy&＃xff09; 原文没有给出具体的算法。提到了一种‘Gittins index’&＃xff0c;感兴趣的读者可以参考&＃xff1a;
  1&＃xff09; Gittins, J. C. 1979. Bandit processes and dynamic allocation indices. Journal of the
  Royal Statistical Society. Series B (Methodological), 41(2), 148–77
  2&＃xff09;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

  此外&＃xff0c;还有一段比较详细的讨论了最优解问题。有一定的理论深度&＃xff0c;我也没有深入研读。感兴趣的读者可以参考原文。

3.2.2 极大极小方法

关注UCB算法。

其中&＃xff0c;3.12公式的前一项表示臂i当前奖励概率的一个估值&＃xff0c;后一项表示估计的不确定性。
参考&＃xff1a;Auer, P. 2002. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3, 397–422.
除此之外&＃xff0c;还可以参考我的另一篇博文&＃xff1a;http://blog.csdn.net/allenalex/article/details/78242068

3.2.3启发式bandit机制

有以下几种机制&＃xff08;方法&＃xff09;&＃xff1a;

• epsilon-Greedy算法.这个方法&＃xff0c;可以直接参考我的另一篇博文&＃xff1a;http://blog.csdn.net/allenalex/article/details/78220926
• SoftMax; 首先定义一个称之为“温度”的参数–τ&＃xff0c;每次摇臂i的概率为&＃xff1a;
  
  当τ很高的时候&＃xff0c;ep^i/τ→1,那么每个臂被选中的概率就几乎一样。相反&＃xff0c;如果 τ很低&＃xff0c;则几乎总是选择奖励概率最大的那个臂。
  下面这两种&＃xff0c;本文见得比较少。不翻译整理了&＃xff0c;直接贴出原文。
• 
• 

评论&＃xff08;原文&＃xff09;

    通常&＃xff0c;贝叶斯方法计算复杂度高&＃xff0c;但是如果建模假设合理&＃xff0c;性能相对更好。相反&＃xff0c;极大极小值方法在最坏的情况下能够实现最好的性能&＃xff0c;但是要平均要尝试的次数更多。实践中通常使用基于启发式的方法。启发式方法实现相对更简单&＃xff0c;并且通过合适的调节&＃xff0c;能够实现合理的性能。