An Empirical Evaluation of Thompson Sampling
概述
汤普森抽样（以下简称TS）是EE方法的一种，所以提到TS不得不介绍一下EE。
EE全称Explore & Exploit，假设在一个广告系统中尝试选择一个最佳的广告展现给用户，那么Explore指选择一个之前没有被（或者很少被）展现的广告来观察用户是否喜欢、而Exploit指在已经被大量用户验证过的广告中选择一个最好的展现给用户。
所以可以看到Exploit是一个近似于贪心算法的方法，这个方法可以得到一个局部的最优解但是很可能会失去全局最优解因为最优的结果可能还没有被用户访问到；Explore则一直尝试新的解以便于找到最佳的答案，但是很可能会浪费大量的机会用于展示不良的解。所以很明显单纯的Exploit或者Explore都不是一个合理的方法，一个合理的方法应当是综合考虑了Explore & Exploit在成本与收益中取得一个最佳的trade off，解决这类问题的方法被称之为EE方法。
TS就是一种非常有效的EE方法，而且神奇的是这个方法的原理非常的简单。同时考虑到现实问题中大量的情况都可以近似看作为相互独立的事件，所以实现起来更加的容易。
方法
TS用贝叶斯估计去解释比较容易理解：首先假设变量$c \in Context$表示上下文信息、$a \in Action$表示需要预估的动作、$r$表示执行一个动作之后得到的reward（譬如CTR预估中，可以将reward建模为是否点击）、$\theta$表示概率分布参数，那么观测数据$D = {(c, a, r)}$。那么最佳的动作动作服从分布：
\[Action = \max_{a'} E(r|a', x, \theta)P(\theta|D)\]那么接下来的问题就是如何估计 $P(\theta|D)$ ，根据贝叶斯公式：
\[P(\theta|D) \thicksim P(D|\theta)P(\theta)\]其中$P(\theta)$是$\theta$的先验分布，$P(D|\theta)$是观测到的结果。如果$P(\theta)$与$P(D|\theta)$满足共轭分布的约束，那么迭代训练过程就可以简化为根据每次增量的数据计算$P(\theta|D)$得到分布可以作为下一次输入的$P(\theta)$。
那么在现实的问题中，大部分情况下$P(D\theta)$都满足二项分布（也就是N次独立伯努利试验），这在常见的推荐、广告等算法中都是成立的。那么自然的就可以选择Beta分布作为$\theta$的概率分布。
那么我们可以带入一个实际的场景中：
假设$\alpha, \beta$是Beta分布的先验参数分别表示正样本和负样本的先验估计数量，计数器$Pos$表示正样本数量、$Neg$表示负样本数量（注意：$\alpha$ $\beta$ 和计数器不一定需要是样本数量，这里这样写仅仅是为了易于理解。），共有$K$个动作可以选择，那么迭代算法：
1
2
3
4
5
6
7
8
9
for t = 1...T
for i = 1..K
从Beta(Pos(i) + alpha(i), Neg(i) + beta(i))分布中抽样一个参数theta(i)
- 将所有theta排序后选择最大的一个，对应的i就是选择的动作
- 观察选择i之后的反馈结果
if r == 1
Pos(i) ++
else
Neg(i) ++
以上算法用代码实现起来非常简单一行代码即可，但是其实验效果确非常的好，不得不说这是一个数学上的胜利。至于为何更新Beta分布参数那一步如此之简单需要简单计算一下Beta分布和二项分布的公式，网上资料很多这里就不赘述了。
以上方法可以推广到一个更加一般的场景下，其泛化为一个框架之后表示如下：
1
2
3
4
5
for t = 1...T
从P(theta|Data)中抽样出一个theta_t
选择一个行为at_t = argmax(a) E(r|x_t, a_t, theta_t)
获得Reward：r
D = D + (x_t, a_t, r_t)
得到以上这个泛化的框架之后，就可以在其上应用很多其他的扩展了，比如大家都会非常关心的带上下文的TS。
支持上下文的TS
原始TS中没有上下文信息，也就是抽样完全是根据先验概率来的而忽略了用户、物品、场景等等的信息。而显然的，补充这些信息一定会更好的改善EE的效果。原文中提出了一种在LR实现的CTR预估模型上应用TS框架之后的算法，并在实际的线上环境中分别试验了几种EE方法（TS / LinUCB / e-greedy等）。
首先假设LR的参数$w_i$满足$N(m_i, q_i^{-1})$其中$i \in {1, d}$，初始化$m_i = 0, q_i = \lambda$其中$\lambda$是正则化系数。输入的特征为$x \in R^d$，用户反馈为$y \in {0, 1}$表示是否点击，$n$表示训练数据个数。那么损失函数可以表示为：
\[w = argmin \frac{1}{2} \sum_{i=1}^{d}q_i(w_i - m_i)^2 + \sum_{j=1}^{n}log(1 + e^{-y_jw^Tx_j})\]更新参数$m$和$q$：（Laplace Approximation）
\[m_i = w_i\] \[q_i = q_i + \sum_{j=1}^{n}x_{ij}^2p_j(1 - p_j)\] \[p_j = \frac{1}{1 + e^{-w^Tx_j}}\]其中$x_{ij}$表示第$j$个训练数据中的第$i$个特征。
在线预测时从$N(m, q)$中抽样出一个$w$然后求出点击率预估最高的结果即可。以上训练过程完全是Copy论文中的结果，因为我对Laplace Approximation完全不了解，所以也不是非常的理解$q$的更新公式是如何计算出来的。后续学习之后补上。
不过从直观角度上说$m$表示的是Exploit状态下的$w$的结果，而$q$表示Explore的强度。$q$越大Explore的强度越大，所以某种程度上说这个训练过程实际上会训练出每个特征的Explore强度。这个强度在预测的时候可以乘上一个系数$\sigma$来控制Exploit / Explore的偏向性。
以上优化过程我相信和最大后验估计有一些关系，尤其是当假设参数的先验分布是正态分布的时候，不过我还没有理清楚其中的一些关系。
总结
上下文无关的TS算法非常容易的实现尤其是做了独立假设和$beta$分布假设之后。应用上下文的信息之后，假设$w$满足正态分布那么本文给出了在LR模型下其学习和预测的过程，实现起来也不是很困难。
以上框架仍然具有巨大的优化空间，尤其是在结合了上下文之后。在此我提出一下带上下文的EE可以优化的方向：
- 考虑某些用户、物品是不需要Explore或者Explore的Cost异常的高，那么这类因素应当考虑到模型的建模中
- 以上方法如果将模型推广到更加复杂的模型中会比较麻烦，另外一种方法是在一个已有的算法（或者对于NN就是一个网络结构），加入特征维度（本文中的$q$）以及特征向量（解决上一个问题）两个因子，通过BP方法训练得到网络参数和EE参数最后在预测阶段用同样的抽样方法来进行EE。这种方法将会极大的扩展EE方法的适用场景但是方法目前还没有看到有什么成果。