推荐系统-多臂赌博机
  • Jul 13, 2019
  • 7 minutes read

多臂赌博机

多臂赌博机问题(Multi-armed bandit problem, K-armed bandit problem, MAB)，简称MAB问题。

推荐系统有两个顽疾，一个是冷启动，一个探索利用问题，后者又称为EE问题，Exploit-Explore问题。针对这两个问题，Bandit算法可以有效解决。

Bandit算法是一类算法。核心思想是：看看选择会带来多少遗憾，遗憾越少越好。在MAB问题里，用来量化选择好坏的指标就是累积遗憾，计算公式如下：

$$ R_T = \sum_{i=1}^{T}(W_{opt} - W_{B(i)}) = TW^* - \sum_{i=1}^{T}W_{B(i)} $$

公式由两部分组成，一个是遗憾，一个是累积，求和符号内部就表示每次选择的遗憾多少。W_opt表示每次都运气好，选择了最好的选择，该得到多少收益，W_B(i)就表示每一次实际选择得到的收益，两者之差就是遗憾的量化，在T次选择后，就有了累积遗憾。

为了简化MAB问题，每个臂收益不是0，就是1，也就是伯努利收益。该公式可以用来对比不同Bandit算法的效果：对同样的多臂问题，用不同的Bandit是算法模拟试验相同次数，比比看哪个Bandit算法的累积遗憾增长的慢，谁就是效果较好的算法。

关键元素：

  1. 臂：是每次推荐的候选项，如具体物品，推荐策略，物品类别
  2. 回报：选择一个臂之后得到的奖励，用户是否对推荐结果喜欢
  3. 环境：决定每个臂不同的那些元素，推荐系统面临的这个用户就是不可捉摸的环境

常见算法

  1. 完全随机：不顾用户反馈的做法
  2. 朴素选择：认准一个效果好的，一直推荐
  3. Epsilon贪婪算法：每次以小概率尝试新的，大概率选择效果好的
  4. UCB：每次都会给予机会较少的候选一些倾向
  5. 汤普森采样：用贝塔分布管理每一个候选的效果

汤普森采样

原理：　假设每个臂是否产生收益，起决定作用的是背后的一个概率分布，产生收益的概率为Ｐ

贝塔分布有a和b两个参数，这两个参数决定了分布的形状和位置：

  1. 曲线很窄，而且靠近１：ａ/(ａ+b)的值越大，分布的中心位置越靠近１
  2. 曲线很窄，而且靠近０：ａ/(ａ+b)的值越小，分布的中心位置越靠近０
  3. 曲线很宽：a+b值越大，分布曲线就越窄，分布就越集中，产生的随机数会容易靠近中心位置，反之，曲线就越宽

汤普森采样过程：

  1. 取出每一个候选对应的参数a和b
  2. 为每个候选用a和b作为参数，用贝塔分布产生一个随机数
  3. 按照随机数排序，输出最大值对应的候选
  4. 观察用户反馈，如果用户点击则将对应候选的a加１，否则b加１

注意：实际上在推荐系统中，要为每一个用户都保存一套参数，ｍ:候选数，n:用户数，参数数：2mn.　Python实现代码：

choice = numpy.argmax(pymc.rbete(1 + self.wins, 1 + self.trials - self.wins))

UCB算法

Upper Confidence Bound，即置信区间上界。同样为每个臂评分，每次选择评分最高的候选臂输出，每次输出后观察用户反馈，然后更新候选臂参数。

每个臂的评分公式为：

$$ \bar{x_j}(t) + \sqrt{\frac{2\ln t}{T_{j,t}}} $$

公式有两个部分组成：

  1. 加号前面是这个候选臂到目前的平均收益，反应了它的效果
  2. 后面的叫做Bonus，本质上是均值的标准差，反映了候选臂效果的不确定性，就是置信区间的上界，t是目前的总选择次数，T_jt是每个臂被选择的次数

算法过程：

  1. 每个候选的汇报均值都有个置信区间，随着试验次数增加，置信区间会变窄，相当于逐渐确定了到底回报丰厚还是可怜
  2. 每次选择前，都根据已经实验的结果重新估计每个候选的均值及置信区间
  3. 选择置信区间上界最大的那个候选

这个评分公式和汤普森采样是一样的思想：

  1. 以每个候选的平均收益为基准线进行选择
  2. 对于被选择次数不足的给予照顾
  3. 选择倾向的是那些确定收益较好的候选

Epsilon贪婪算法

算法过程：

  1. 先选择一个(0,1)之间较小的数，叫做Epsilon
  2. 每次以概率Epsilon的概率在所有候选臂中随机选择一个，以1-Epsilon的概率去选择平均收益最大的那个臂

Epsilon的值可以控制对探索和利用的权衡程度，这个值越接近０，在探索上就越保守。

朴素的做法

先试几次，等每个臂都统计到收益之后，就一直选择均值最大的那个臂。

###　冷启动问题

数据不足就是冷启动问题，解决的大致思路：

  1. 针对一个新用户，使用汤普森采样为每一个Topic采样一个随机数排序后，输出采样Top N的推荐Item，注意，一次选择了Top N个候选臂
  2. 等着获取用户的反馈，没有反馈则更新对应的Topic的b值，点击了则更新对应Topic的a值

结合上下文信息的Bandit算法

上面的Bandit算法有一个特点：完全没有使用候选臂的特征信息。问题是只能对当前已有的这些候选臂进行选择，对于新加入的候选臂只能从０开始积累数据，而不能借助已有的候选泛化作用。

改进的UCB算法LinUCB

UCB置信区间可以简单理解为不确定的程度，区间越宽，越不确定，反之就很确定。与传统的UCB算法相比，最大的改进就是加入了特征信息，每次估算每个候选的置信区间，不再仅仅根据实验，而是根据特征信息来估算。

LinUCB算法最重要的步骤，就是给用户和物品构建特征，也就是刻画上下文。

简单版本LinUCB

让每一个候选臂之间完全互相无关，参数不共享。LinUCB认为，参数和特征之间线性相乘就应该得到收益：

$$ D_{m \times d} \times \hat{\theta}_{d \times 1} = C_{ m \times 1} $$

已知D和C，求解theta：

$$ \hat{\theta}_{d \times 1} = (D_{m \times d}^T)^{-1} \times C_{m \times 1} $$

岭回归(Ridge Regression)主要用于当样本数小于特征数时，对回归参数进行修正，对于加了特征的Bandit问题，正好符合这个特点：试验次数（样本数量）少于特征数。因此给原始矩阵加上一个单位对角矩阵后再参与计算：

$$ \hat{\theta}_{d \times 1} = (D_{m \times d}^T D_{m \times d} + I_{d \times d})^{-1} \times D_{m \times d}^T C_{m \times 1} $$

如果x是上下文特征，则期望收益和置信上边界计算公式：

期望收益：

$$ \hat{r} = x_{d \times 1}^T \hat{\theta}_{d \times 1} $$

置信区间上边界：

$$ \hat{b} = \alpha \sqrt{x_{d \times 1}^T (D_{m \times d}^T D_{m \times d} + I_{d \times d})^{-1} x_{d \times 1})} $$

每次选择时给每一个候选臂都计算这两个值，相加之后选择最大的候选臂输出。

LinUCB特点：

  1. 会考虑上下文因素，比如是用户特征、物品特征和场景特征一起考虑
  2. 每一个候选臂针对这些特征各自维护一个参数向量，各自更新，互不干扰
  3. 每次选择时用各自的参数去计算期望收益和置信区间，然后按照置信区间上边界最大的输出结果
  4. 返回用户的反馈，即是否点击，结合对应的特征，按照上面的公式，去重新计算这个候选臂的参数

当LinUCB的特征向量始终取1，每个候选臂的参数是收益均值的时候，LinUCB就是UCB。

高级版本LinUCB

与简单版本相比，高级版本认为一部分特征对应的参数在所有候选臂之间是共享的，就是无论哪个候选臂被选中，都会去更新这部分参数。

步骤：

  1. 对用户特征和物品特征向量进行归一化处理，变成单位向量
  2. 将用户特征向量做第一次降维处理为与物品特征一样的A维空间向量，利用用户特征和物品特征以及用户的点积行为去你和一个矩阵W，直观上理解是能够把用户特征映射到物品特征上
  3. 用投射后的A维用户特征向量进行聚类，得到B个类，物品也同样聚类为B个类，再加上常数1，用户和物品各自被表示成B+1维向量
  4. 接下来应用简单版本的LinUCB就行

总结

LinUCB优点：

  1. 由于加入了特征，收益收敛比UCB更快
  2. 各个候选臂之间参数是独立的，可以互相不影响地更新参数
  3. 由于参与计算的是特征，所以可以处理动态的推荐候选池，编辑可以增删文章

LinUCB缺点：

同时处理的候选臂数量不能太多，不超过几百个最佳，因为每一次要计算每一个候选臂的期望收益和置信区间，一旦候选太多，计算代价将不可接受。

如何将Bandit算法与协同过滤结合使用

协同过滤核心就是“物以类聚，人以群分”。

信息茧房：推荐的物品局限在了部分圈子中，看不到新奇的物品。

COFIBA算法

与LinUCB相比，COFIBA不同点有两个：

  1. 基于用户聚类挑选最佳的物品，即相似用户集体动态决策
  2. 基于用户的反馈情况调整用户和物品的聚类结果

简单过程：

  1. 用协同过滤来少选可以参与决策的用代表，用LinUCB算法来实际进行选择
  2. 根据用户的反馈，调整基于用户和基于物品的聚类结果，即对物品和用户的群体代表做换届选举
  3. 基于物品的聚类如果变化，又进一步改变了用户的聚类结果
  4. 不断根据用户实时动态的反馈来调整用户的决策参数，从而重新划分聚类结果矩阵

总结

  1. Bandit是一种不太常用在推荐系统的算法，究其原因，是它能同时处理的物品数量不能太多
  2. 针对冷启动和EE问题，Bandit算法简单好用，值得一试
  3. COFIBA算法是把协同过滤思想引入到了Bandit算法中，不再是用户独立决策，而是用户所在群体共同决策推荐结果。

MAB问题思维导图

本文是《推荐系统三十六式》的读书笔记，仅限个人学习，请勿用作商业用途，谢谢。

Note: Cover Picture

  • RS
    • Previous
    推荐系统-模型融合
    Next
    推荐系统-深度学习