Explore & Exploit

推荐广告或推荐系统领域的EE问题:

  • Explore 探索用户兴趣,或者避免算法走入死胡同。
  • Exploit 确定了用户兴趣,然后推荐与之相关的内容。

对于固定流量来说,Exploit的这部分流量显然会产生收益,而Explore不一定能立刻就有收益。所以,如何分配E&E流量,最大化收益是值得研究的内容。

E&E一般常等同于多臂老虎机问题(Multi-armed bandit problem)进行解决。

累积后悔

累积后悔(Cumulative Expected Regret)可以来评估bandit算法,或其他一些在线学习算法。

多arm的回报可以看作一组真实的随机分布:$B=( R_i,\dots,R_K )$,其中,$K$代表arm。

设 $\mu_1,\dots,\mu_K$ 代表每个arm的平均回报,每一轮拉动一个arm得到一次回报。多arm问题等同于一个状态的马尔科夫问题。

设$T$轮之后的后悔度为 $\rho$,则可以表示如下:

其中,$\mu^*=\max_k( \mu_k )$ 是最大回报的平均数,$\hat{r_t}$ 是在t时获得的回报。

一个零后悔度的策略会使得 $\rho/T$在无限次选择arm后以概率1趋向于0。

Epsilon-Greedy

利用概率ε来探索,概率1-ε来开发。

Thompson sampling

认为每个arm服从一个beta分布,Thompson采样算法:

  • 每个arm都维护一个 beta 分布的参数,获取每个臂对应的参数 α 和 β,然后使用 beta 分布生成随机数。
  • 选取生成随机数最大的那个臂作为本次结果。
  • 观察用户反馈,如果用户点击则将对应臂的 α 加 1,否则 β 加 1。
choice = numpy.argmax(pymc.rbeta(1 + self.wins, 1 + self.trials - self.wins))

UCB

置信区间上界(Upper Confidence Bound)

在统计学中,对于一个未知量的估计,总能找到一种量化其置信度的方法。最普遍的分布正态分布 N(μ,δ),其中的μ就是估计量的期望,而δ则表示其不确定性(δ越大则表示越不可信)。

而UCB就是以arm均值 μ 的置信上限为来代表它的预估值:

其中,$\mu_i$ 是对期望的预估,$n_i$是尝试次数,可以看到对i的尝试越多,其预估值与置信上限的差值就越小。也就是越有置信度。

参考实现:https://github.com/jkomiyama/banditlib/blob/master/policy/policy_ucb.hpp

LinUCB

单纯的UCB回报是由arm本身决定的,而广告或推荐领域,应该是由user和item共同决定的。

所以,LinUCB对比UCB加入了user和item(arm)的特征,并且假设feature回报线性相关(所以是Linear UCB),通过feature预估每个arm的期望回报和置信区间,选择置信区间上界最大的arm,观察回报后更新线性关系的参数。这样看起来更加合理。

并且由于加入了特征,LinUCB比UCB收敛更快,在最终rank上有相关应用。

参考

  • 《计算广告学》刘鹏 6.3 探索与利用