专治选择综合征——Bandit算法

2018 年 1 月 2 日 AI100 陈开江

作者 | 陈开江

责编 | 何永灿

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

什么是Bandit算法

为选择而生

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

当然有！那就是Bandit算法。

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

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

图1 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]：

图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]：

初始化：先对每一个臂都试一遍；
按照如下公式计算每个臂的分数，然后选择分数最大的臂作为选择：

图3 UCB算法

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

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

Epsilon-Greedy算法

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

选一个（0,1）之间较小的数作为epsilon；
每次以概率epsilon做一件事：所有臂中随机选一个；
每次以概率1-epsilon 选择截止到当前，平均收益最大的那个臂。

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

朴素Bandit算法

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

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

图4 五种Bandit算法模拟试验的效果图

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

至于你实际上要选哪一种Bandit算法，你可以选一种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最大的特色。

图5 应用LinUCB算法的Yahoo!首页

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

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

LinUCB基本算法描述如下：

图6 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 -> 0.7, 0.8

self.r0 = 0 # if worse, -19, -21

# dimension of user features = d

self.d = 6

# Aa : collection of matrix to compute disjoint part for each article a, d*d

self.Aa = {}

# AaI : store the inverse of all Aa matrix

self.AaI = {}

# ba : collection of vectors to compute disjoin part, d*1

self.ba = {}

self.a_max = 0

self.theta = {}

self.x = None

self.xT = None

# linUCB

def set_articles(self, art):

# init collection of matrix/vector Aa, Ba, ba

for key in art:

self.Aa[key] = np.identity(self.d)

self.ba[key] = np.zeros((self.d, 1))

self.AaI[key] = np.identity(self.d)

self.theta[key] = np.zeros((self.d, 1))

# 这里更新参数时没有传入更新哪个arm，因为在上一次recommend的时候缓存了被选的那个arm，所以此处不用传入

# 另外，update操作不用阻塞recommend，可以异步执行

def update(self, reward):

if reward == -1:

pass

elif reward == 1 or reward == 0:

if reward == 1:

r = self.r1

else:

r = self.r0

self.Aa[self.a_max] += np.dot(self.x, self.xT)

self.ba[self.a_max] += r * self.x

self.AaI[self.a_max] = linalg.solve(self.Aa[self.a_max], np.identity(self.d))

self.theta[self.a_max] = np.dot(self.AaI[self.a_max], self.ba[self.a_max])

else:

# error

pass

# 预估每个arm的回报期望及置信区间

def recommend(self, timestamp, user_features, articles):

xaT = np.array([user_features])

xa = np.transpose(xaT)

art_max = -1

old_pa = 0

# 获取在update阶段已经更新过的AaI(求逆结果)

AaI_tmp = np.array([self.AaI[article] for article in articles])

theta_tmp = np.array([self.theta[article] for article in articles])

art_max = articles[np.argmax(np.dot(xaT, theta_tmp) + self.alpha * np.sqrt(np.dot(np.dot(xaT, AaI_tmp), xa)))]

# 缓存选择结果，用于update

self.x = xa

self.xT = xaT

# article index with largest UCB

self.a_max = art_max

return self.a_max

怎么构建特征

LinUCB算法有一个很重要的步骤，就是给User和Item构建特征，也就是刻画context。在原始论文里，Item是文章，其中专门介绍了它们怎么构建特征的，也甚是精妙。容我慢慢表来。

原始用户特征

人口统计学：性别特征（2类），年龄特征（离散成10个区间）。

地域信息：遍布全球的大都市，美国各个州。

行为类别：代表用户历史行为的1000个类别取值。

原始文章特征

URL类别：根据文章来源分成了几十个类别。

编辑打标签：编辑人工给内容从几十个话题标签中挑选出来的原始特征向量都要归一化成单位向量。

还要对原始特征降维，以及模型要能刻画一些非线性的关系。

用Logistic Regression去拟合用户对文章的点击历史，其中的线性回归部分为：

拟合得到参数矩阵W，可以将原始用户特征（1000多维）投射到文章的原始特征空间（80多维），投射计算方式：

这是第一次降维，把原始1000多维降到80多维。

然后，用投射后的80多维特征对用户聚类，得到5个类簇，文章页同样聚类成5个簇，再加上常数1，用户和文章各自被表示成6维向量。

Yahoo!的科学家们之所以选定为6维，因为数据表明它的效果最好[10]，并且这大大降低了计算复杂度和存储空间。

我们实际上可以考虑三类特征：U（用户），A（广告或文章），C（所在页面的一些信息）。

前面说了，特征构建很有发挥空间，算法工程师们尽情去挥洒汗水吧。

总结一下LinUCB算法，有以下优点：

由于加入了特征，所以收敛比UCB更快（论文有证明）；
特征构建是效果的关键，也是工程上最麻烦和值的发挥的地方；
由于参与计算的是特征，所以可以处理动态的推荐候选池，编辑可以增删文章；
特征降维很有必要，关系到计算效率。

Bandit算法与协同过滤

协同过滤背后的哲学

推荐系统里面，传统经典的算法肯定离不开协同过滤。协同过滤背后的思想简单深刻，在万物互联的今天，协同过滤的威力更加强大。协同过滤看上去是一种算法，不如说是一种方法论，不是机器在给你推荐，而是“集体智慧”在给你推荐。

它的基本假设就是“物以类聚，人以群分”，你的圈子决定了你能见到的物品。这个假设很靠谱，却隐藏了一些重要的问题：作为用户的我们还可能看到新的东西吗？还可能有惊喜吗？还可能有圈子之间的更迭流动吗？这些问题的背后其实就是在前面提到过的EE问题（Exploit & Explore）。我们关注推荐的准确率，但是我们也应该关注推荐系统的演进发展，因为“推荐系统不止眼前的Exploit，还有远方的Explore”。

做Explore的方法有很多，Bandit算法是其中的一种流派。前面也介绍过几种Bandit算法，基本上就是估计置信区间的做法，然后按照置信区间的上界来进行推荐，以UCB、LinUCB为代表。

作为要寻找诗和远方的Bandit浪漫派算法，能不能和协同过滤这种正统算法结合起来呢？事实上已经有人这么尝试过了，叫做COFIBA算法，具体在题目为Collaborative Filtering Bandits[11]和Online Clustering of Bandits[12]）的两篇文章中有详细的描述，它就是Bandit和协同过滤的结合算法，两篇文章的区别是后者只对用户聚类（即只考虑了User-based的协同过滤），而前者采用了协同聚类（co-clustering，可以理解为item-based和user-based两种协同方式在同时进行），后者是前者的一个特殊情况。下面详细介绍一下这种结合算法。

Bandit结合协同过滤

很多推荐场景中都有这两个规律：

相似的用户对同一个物品的反馈可能是一样的。也就是对一个聚类用户群体推荐同一个Item，他们可能都喜欢，也可能都不喜欢，同样地，同一个用户会对相似的物品反馈相同。这是属于协同过滤可以解决的问题；
在使用推荐系统过程中，用户的决策是动态进行的，尤其是新用户。这就导致无法提前为用户准备好推荐候选，只能“走一步看一步”，是一个动态的推荐过程。

每一个推荐候选Item，都可以根据用户对其偏好不同（payoff不同）将用户聚类成不同的群体，一个群体来集体预测这个Item的可能的收益，这就有了协同的效果，然后再实时观察真实反馈回来更新用户的个人参数，这就有了Bandit的思想在里面。

举个例子，如果你父母给你安排了很多相亲对象，要不要见面去相一下？那需要提前看看每一个相亲对象的资料，每次大家都分成好几派，有说好的，有说再看看的，也有说不行的；你自己也会是其中一派的一员，每次都是你所属的那一派给你集体打分，因为他们是和你“三观一致的人”，“诚不欺我”；这样从一堆资料中挑出分数最高的那个人，你出去见TA，回来后把实际感觉说给大家听，同时自己心里的标准也有些调整，重新给剩下的其它对象打分，打完分再去见，周而复始……

以上就是协同过滤和Bandit结合的思想。

另外，如果要推荐的候选Item较多，还需要对Item进行聚类，这样就不用按照每一个Item对User聚类，而是按照每一个Item的类簇对User聚类，如此以来，Item的类簇数相对于Item数要大大减少。

COFIBA算法

基于这些思想，有人提出了算法COFIBA（读作coffee bar）[13]，简要描述如下：

在时刻t，用户来访问推荐系统，推荐系统需要从已有的候选池子中挑一个最佳的物品推荐给他，然后观察他的反馈，用观察到的反馈来更新挑选策略。这里的每个物品都有一个特征向量，所以这里的Bandit算法是context相关的。这里依然是用岭回归去拟合用户的权重向量，用于预测用户对每个物品的可能反馈（payoff），这一点和linUCB算法是一样的。

图7 COFIBA算法描述

对比LinUCB算法，COFIBA算法的不同有两个：

基于用户聚类挑选最佳的Item（相似用户集体决策的Bandit）。
基于用户的反馈情况调整User和Item的聚类（协同过滤部分）。

整体算法过程如下：

核心步骤是，针对某个用户i，在每一轮试验时做以下事情：

首先计算该用户的Bandit参数W（和LinUCB相同），但是这个参数并不直接参与到Bandit的选择决策中（和LinUCB不同），而是用来更新用户聚类的；
遍历候选Item，每一个Item表示成一个context向量了。
每一个Item都对应一套用户聚类结果，所以遍历到每一个Item时判断当前用户在当前Item下属于哪个类簇，然后把对应类簇中每个用户的M矩阵(对应LinUCB里面的A矩阵)，b向量（payoff向量，对应linUCB里面的b向量）聚合起来，从而针对这个类簇求解一个岭回归参数（类似LinUCB里面单独针对每个用户所做），同时计算其payoff预测值和置信上边界。
每个Item都得到一个payoff预测值及置信区间上界，挑出那个上边界最大的Item推出去（和LinUCB相同）。
观察用户的真实反馈，然后更新用户自己的M矩阵和b向量（更新个人的，对应类簇里其他的不更新）。

以上是COFIBA算法的一次决策过程。在收到用户真实反馈之后，还有两个计算过程：

更新User聚类
更新Item聚类

如何更新User和Item的聚类呢？见图8：

图8 User和Item聚类更新描述

解释一下图8。

a. 这里有6个User，8个Item，初始化时，User和Item的类簇个数都是1。

b1. 在某一轮试验时，推荐系统面对的用户是4。推荐过程就是遍历1～8每个Item，然后看看对应每个Item时，User4在哪个类簇中，把对应类簇中的用户聚合起来为这个Item预测payoff和CB。这里假设最终Item5胜出，被推荐出去了。

b2. 在时刻t，Item有3个类簇，需要更新的用户聚类是Item5对应的User4所在类簇。更新方式：看看该类簇里面除了User4之外的用户，对Item5的payoff是不是和user4相近，如果是，则保持原来的连接边，否则删除原来的连接边。删除边之后重新构建聚类结果。这里假设重新构建后原来User4所在的类簇分裂成了两个类簇：{4,5}和{6}。

C更新完用户类簇后，Item5对应的类簇也要更新。更新方式是：对于每一个和Item5（被推荐出的那个Item）还存在连接边的Item j，都去构造一个User的近邻集合N，这个集合的用户对Item j有相近的payoff，然后看看N是不是和刚刚更新后的User4所在的类簇相同，是的话，保留Item5和Item j之间的连接边，否则删除。这里假设Item 3和Item 5之间的连接边被删除。Item3独立后给他初始化了一个聚类结果：所有用户还是一个类簇。

简单来说就是这样：

User-based协同过滤来选择要推荐的Item，选择时用了LinUCB的思想；
根据用户的反馈，调整User-based和Item-based的聚类结果；
Item-based的聚类变化又改变了User的聚类；
不断根据用户实时动态的反馈来划分User-Item矩阵。

总结

Exploit-Explore这一对矛盾一直客观存在，Bandit算法是公认的一种比较好的解决EE问题的方案。除了Bandit算法之外，还有一些其他的explore的办法，比如：在推荐时，随机地去掉一些用户历史行为（特征）。

解决Explore，势必就是要冒险，势必要走向未知，而这显然就是会伤害用户体验的：明知道用户肯定喜欢A，你还偏偏以某个小概率给推荐非A。

实际上，很少有公司会采用这些理性的办法做Explore，反而更愿意用一些盲目主观的方式。究其原因，可能是因为：

互联网产品生命周期短，而Explore又是为了提升长期利益的，所以没有动力做；
用户使用互联网产品时间越来越碎片化，Explore的时间长，难以体现出Explore 的价值；
同质化互联网产品多，用户选择多，稍有不慎，用户用脚投票，分分钟弃你于不顾；
已经成规模的平台，红利杠杠的，其实是没有动力做Explore的。

基于这些，我们如果想在自己的推荐系统中引入Explore机制，需要注意以下几点：

用于Explore的Item要保证其本身质量，纵使用户不感兴趣，也不至于引起其反感；
Explore本身的产品需要精心设计，让用户有耐心陪你玩儿；
深度思考，这样才不会做出脑残的产品，产品不会早早夭折，才有可能让Explore机制有用武之地。

参考文献：

[1] https://en.wikipedia.org/wiki/Multi-armed_bandit

[2]http://nbviewer.jupyter.org/github/CamDavidsonPilon/Probabilistic-Programming-and-Bayesian-Methods-for-Hackers/blob/master/Chapter6_Priorities/Chapter6.ipynb#

[3] https://en.wikipedia.org/wiki/Thompson_sampling

[4] http://hunch.net/~coms-4771/lecture20.pdf

[5] https://gist.github.com/anonymous/211b599b7 bef958e50af

[6] http://www.research.rutgers.edu/~lihong/pub/Li10Contextual.pdf

[7] 《计算广告：互联网商业变现的市场与技术》p253, 刘鹏，王超著

[8] https://en.wikipedia.org/wiki/Tikhonov_regularization

[9]https://github.com/Fengrui/HybridLinUCB-python/blob/master/policy_hybrid.py

[10] http://www.gatsby.ucl.ac.uk/~chuwei/paper/isp781-chu.pdf

[11] http://arxiv.org/abs/1401.8257

[12] http://arxiv.org/abs/1502.03473

[13] https://github.com/qw2ky/CoLinUCB_Revised/blob/master/COFIBA.py