《Statistical Methods for Recommender Systems》阅读笔记--第三章（1）--EE问题

66 阅读 0 评论 44 点赞

我是靠谱客的博主懦弱小蜜蜂，这篇文章主要介绍《Statistical Methods for Recommender Systems》阅读笔记--第三章（1）--EE问题，现在分享给大家，希望可以做个参考。

     插一句：这个问题，我之前写过三篇相关的博客（有一篇竟然不知道怎么被不小心覆盖了。悲伤。。。），感兴趣的可以先参考：
   ● 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挑战的主要思想

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

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

MAB 主要可以分为以下三类：
    ● 贝叶斯方法（Bayesian methods ）
    ● 极大极小方法（minimax methods）
    ● 启发法（heuristic methods）

3.2.1.贝叶斯方法

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

状态了最大化收益，赌徒需要估计每个臂的奖励概率。设t时刻的状态 $θ_t$ 表示赌徒在t时刻前基于实验数据所获得的知识。对于每个臂，所知的信息用一个两个参数的贝塔分布表示。也就是：
$theta _t = (theta _{1t},...,theta _{Kt})$
其中 $theta _{it}$ 为t时刻i的状态：
$theta _{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为奖励概率，那么，
                    $(p_i|c_i)sim Beta(α_{it} + c_i, γ_{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

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

3.2.2 极大极小方法

关注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

3.2.3启发式bandit机制

有以下几种机制（方法）：

epsilon-Greedy算法.这个方法，可以直接参考我的另一篇博文：http://blog.csdn.net/allenalex/article/details/78220926
SoftMax; 首先定义一个称之为“温度”的参数–τ，每次摇臂i的概率为：

当τ很高的时候， $e^{hat p _i /τ }to 1$ ,那么每个臂被选中的概率就几乎一样。相反，如果 τ很低，则几乎总是选择奖励概率最大的那个臂。
下面这两种，本文见得比较少。不翻译整理了，直接贴出原文。