Bandit算法与推荐系统

作者 |陈开江

责编 | 何永灿

推荐系统里面有两个经典问题：EE和冷启动。前者涉及到平衡准确和多样，后者涉及到产品算法运营等一系列。Bandit算法是一种简单的在线学习算法，常常用于尝试解决这两个问题，本文为你介绍基础的Bandit算法及一系列升级版，以及对推荐系统这两个经典问题的思考。

为选择而生

我们会遇到很多选择的场景。上哪个大学，学什么专业，去哪家公司，中午吃什么等等。这些事情，都让选择困难症的我们头很大。那么，有算法能够很好地对付这些问题吗？

当然有！那就是Bandit算法。

Bandit算法来源于历史悠久的赌博学，它要解决的问题是这样的[1]：

一个赌徒，要去摇禁用词语，走进赌场一看，一排禁用词语，外表一模一样，但是每个禁用词语吐钱的概率可不一样，他不知道每个禁用词语吐钱的概率分布是什么，那么每次该选择哪个禁用词语可以做到最大化收益呢？这就是多臂赌博机问题（Multi-armed bandit problem, K-armed bandit problem, MAB）。

怎么解决这个问题呢？最好的办法是去试一试，不是盲目地试，而是有策略地快速试一试，这些策略就是Bandit算法。

这个多臂问题，推荐系统里很多问题都与它类似：

• 假设一个用户对不同类别的内容感兴趣程度不同，那么我们的推荐系统初次见到这个用户时，怎么快速地知道他对每类内容的感兴趣程度？这就是推荐系统的冷启动。

• 假设我们有若干广告库存，怎么知道该给每个用户展示哪个广告，从而获得最大的点击收益？是每次都挑效果最好那个么？那么新广告如何才有出头之日？

• 我们的算法工程师又想出了新的模型，有没有比A/B test更快的方法知道它和旧模型相比谁更靠谱？

• 如果只是推荐已知的用户感兴趣的物品，如何才能科学地冒险给他推荐一些新鲜的物品？

Bandit算法与推荐系统

在推荐系统领域里，有两个比较经典的问题常被人提起，一个是EE问题，另一个是用户冷启动问题。

什么是EE问题？又叫exploit－explore问题。exploit就是：对用户比较确定的兴趣，当然要利用开采迎合，好比说已经挣到的钱，当然要花；explore就是：光对着用户已知的兴趣使用，用户很快会腻，所以要不断探索用户新的兴趣才行，这就好比虽然有一点钱可以花了，但是还得继续搬砖挣钱，不然花完了就得喝西北风。

用户冷启动问题，也就是面对新用户时，如何能够通过若干次实验，猜出用户的大致兴趣。

我想，屏幕前的你已经想到了，推荐系统冷启动可以用Bandit算法来解决一部分。

这两个问题本质上都是如何选择用户感兴趣的主题进行推荐，比较符合Bandit算法背后的MAB问题。

比如，用Bandit算法解决冷启动的大致思路如下：用分类或者Topic来表示每个用户兴趣，也就是MAB问题中的臂（Arm），我们可以通过几次试验，来刻画出新用户心目中对每个Topic的感兴趣概率。这里，如果用户对某个Topic感兴趣（提供了显式反馈或隐式反馈），就表示我们得到了收益，如果推给了它不感兴趣的Topic，推荐系统就表示很遗憾（regret）了。如此经历“选择-观察-更新-选择”的循环，理论上是越来越逼近用户真正感兴趣的Topic的，

怎么选择Bandit算法？

现在来介绍一下Bandit算法怎么解决这类问题的。Bandit算法需要量化一个核心问题：错误的选择到底有多大的遗憾？能不能遗憾少一些？

王家卫在《一代宗师》里寄出一句台词：

人生要是无憾，那多无趣？

而我说：算法要是无憾，那应该是过拟合了。

所以说：怎么衡量不同Bandit算法在解决多臂问题上的效果？首先介绍一个概念，叫做累积遗憾（regret）[2]：

这个公式就是计算Bandit算法的累积遗憾，解释一下：

首先，这里我们讨论的每个臂的收益非0即1，也就是伯努利收益。

然后，每次选择后，计算和最佳的选择差了多少，然后把差距累加起来就是总的遗憾。

wB(i)是第i次试验时被选中臂的期望收益， w*是所有臂中的最佳那个，如果上帝提前告诉你，我们当然每次试验都选它，问题是上帝不告诉你，所以就有了Bandit算法，我们就有了这篇文章。

这个公式可以用来对比不同Bandit算法的效果：对同样的多臂问题，用不同的Bandit算法试验相同次数，看看谁的regret增长得慢。

那么到底不同的Bandit算法有哪些呢？

常用Bandit算法

Thompson sampling算法

Thompson sampling算法简单实用，因为它只有一行代码就可以实现[3]。简单介绍一下它的原理，要点如下：

• 假设每个臂是否产生收益，其背后有一个概率分布，产生收益的概率为p。

• 我们不断地试验，去估计出一个置信度较高的“概率p的概率分布”就能近似解决这个问题了。

• 怎么能估计“概率p的概率分布”呢？ 答案是假设概率p的概率分布符合beta(wins, lose)分布，它有两个参数: wins, lose。

• 每个臂都维护一个beta分布的参数。每次试验后，选中一个臂，摇一下，有收益则该臂的wins增加1，否则该臂的lose增加1。

• 每次选择臂的方式是：用每个臂现有的beta分布产生一个随机数b，选择所有臂产生的随机数中最大的那个臂去摇。

import numpy as np

import pymc

#wins 和 trials 是一个N维向量，N是赌博机的臂的个数，每个元素记录了

choice = np.argmax(pymc.rbeta(1 wins, 1 trials - wins))

wins[choice] = 1

trials = 1

UCB算法

UCB算法全称是Upper Confidence Bound（置信区间上界），它的算法步骤如下[4]：

• 初始化：先对每一个臂都试一遍；

• 按照如下公式计算每个臂的分数，然后选择分数最大的臂作为选择：

• 观察选择结果，更新t和Tjt。其中加号前面是这个臂到目前的收益均值，后面的叫做bonus，本质上是均值的标准差，t是目前的试验次数，Tjt是这个臂被试次数。

这个公式反映一个特点：均值越大，标准差越小，被选中的概率会越来越大，同时哪些被选次数较少的臂也会得到试验机会。

Epsilon-Greedy算法

这是一个朴素的Bandit算法，有点类似模拟退火的思想：

1. 选一个（0,1）之间较小的数作为epsilon；

2. 每次以概率epsilon做一件事：所有臂中随机选一个；

3. 每次以概率1-epsilon 选择截止到当前，平均收益最大的那个臂。

是不是简单粗暴？epsilon的值可以控制对Exploit和Explore的偏好程度。越接近0，越保守，只想花钱不想挣钱。

朴素Bandit算法

最朴素的Bandit算法就是：先随机试若干次，计算每个臂的平均收益，一直选均值最大那个臂。这个算法是人类在实际中最常采用的，不可否认，它还是比随机乱猜要好。

以上五个算法，我们用10000次模拟试验的方式对比了其效果如图4，实验代码来源[5]：

算法效果对比一目了然：UCB算法和Thompson采样算法显著优秀一些。

至于你实际上要选哪一种Bandit算法，你可以选一种Bandit算法来选Bandit算法。

UCB算法

UCB算法在做EE（Exploit-Explore）的时候表现不错，但它是上下文无关（context free）的Bandit算法，它只管埋头干活，根本不观察一下面对的都是些什么特点的arm，下次遇到相似特点但不一样的arm也帮不上什么忙。

UCB解决Multi-armed bandit问题的思路是：用置信区间。置信区间可以简单地理解为不确定性的程度，区间越宽，越不确定，反之亦反之。

每个item的回报均值都有个置信区间，随着试验次数增加，置信区间会变窄（逐渐确定了到底回报丰厚还是可怜）。每次选择前，都根据已经试验的结果重新估计每个Item的均值及置信区间。 选择置信区间上限最大的那个Item。

“选择置信区间上界最大的那个Item”这句话反映了几个意思：

• 如果Item置信区间很宽（被选次数很少，还不确定），那么它会倾向于被多次选择，这个是算法冒风险的部分；

• 如果Item置信区间很窄（备选次数很多，比较确定其好坏了），那么均值大的倾向于被多次选择，这个是算法保守稳妥的部分；

• UCB是一种乐观的算法，选择置信区间上界排序，如果时悲观保守的做法，是选择置信区间下界排序。

UCB算法加入特征信息

Yahoo!的科学家们在2010年发表了一篇论文[6]，给UCB引入了特征信息，同时还把改造后的UCB算法用在了Yahoo!的新闻推荐中，算法名叫LinUCB，刘鹏博士在《计算广告》一书中也有介绍LinUCB在计算广告中的应用[7]。

单纯的禁用词语回报情况就是禁用词语自己内部决定的，而在广告推荐领域，一个选择的回报，是由User和Item一起决定的，如果我们能用Feature来刻画User和Item这一对CP，在每次选择Item之前，通过Feature预估每一个arm（item）的期望回报及置信区间，选择的收益就可以通过Feature泛化到不同的Item上。

为UCB算法插上了特征的翅膀，这就是LinUCB最大的特色。

LinUCB算法做了一个假设：一个Item被选择后推送给一个User，其回报和相关Feature成线性关系，这里的“相关Feature”就是context，也是实际项目中发挥空间最大的部分。

于是试验过程就变成：用User和Item的特征预估回报及其置信区间，选择置信区间上界最大的Item推荐，观察回报后更新线性关系的参数，以此达到试验学习的目的。

LinUCB基本算法描述如下：

对照每一行解释一下（编号从1开始）：

• 设定一个参数\alpha，这个参数决定了我们Explore的程度；

• 开始试验迭代；

• 获取每一个arm的特征向量xa,t；

• 开始计算每一个arm的预估回报及其置信区间；

• 如果arm还从没有被试验过，那么：

• 用单位矩阵初始化Aa；

• 用0向量初始化ba；

• 处理完没被试验过的arm；

• 计算线性参数\theta；

• 用\theta和特征向量xa,t计算预估回报，同时加上置信区间宽度；

• 处理完每一个arm；

• 选择第10步中最大值对应的arm，观察真实的回报rt；

• 更新Aat；

• 更新bat；

• 算法结束。

注意到上面的第4步，给特征矩阵加了一个单位矩阵，这就是岭回归（ridge regression），岭回归主要用于当样本数小于特征数时，对回归参数进行修正［8］。

对于加了特征的Bandit问题，正符合这个特点：试验次数（样本）少于特征数。

每一次观察真实回报之后，要更新的不止是岭回归参数，还有每个arm的回报向量ba。

详解LinUCB的实现

根据论文给出的算法描述，其实很好写出LinUCB的代码[9]，麻烦的只是构建特征。

代码如下，一些必要的注释说明已经写在代码中。

class LinUCB:

def __init__(self):

self.alpha = 0.25

self.r1 = 1 # if worse -