16. 冷启动问题（Cold-Start）+探索利用问题（EE) Bandit

问题定义：在众多备选方案选择中，选择利益最大的一个，这就需要推荐系统。推荐系统的使命就是在建立用户和物品之间的连接。建立连接可以理解成：为用户匹配到最佳的物品；但也有另一个理解就是，在某个时间某个位置为用户选择最好的物品。

问题策略定义：把推荐选择具体物品，上升到选择策略。如果后台算法中有三种策略：按照内容相似推荐，按照相似好友推荐，按照热门推荐。每次选择一种策略，确定了策略后，再选择策略中的物品，这样两个步骤。

问题举例定义：一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么想最大化收益该怎么整？这就是多臂赌博机问题(Multi-armed bandit problem,K-armed bandit problem, MAB)，简称 MAB 问题。有很多相似问题都属于 MAB 问题。只要是关于选择的问题，都可以简化成一个 MAB 问题。针对这个问题Bandit可以解决。

推荐系统里面有两个顽疾，一个是冷启动，一个是探索利用问题，冷启动问题好说，探索利用问题（EE 问题：Exploit－Explore）什么意思？利用Exploit意思就是：比较确定的兴趣，当然要用啊。好比说我们已经挣到的钱，当然要花啊。探索Explore的意思就是：不断探索用户新的兴趣才行，不然很快就会出现一模一样的反复推荐。就好比我们虽然有一点钱可以花了，但是还得继续搬砖挣钱啊，要不然，花完了就要喝西北风了。

16.1 Bandit 算法并不是指一个算法，而是一类算法。

现在就来介绍一下 Bandit 算法家族怎么解决这类选择问题。Bandit 算法的思想是：看看选择会带来多少遗憾，遗憾越少越好。在 MAB 问题里，用来量化选择好坏的指标就是累计遗憾，计算公式如图所示。

公式有两部分构成：一个是遗憾，一个是累积。求和符号内部就表示每次选择的遗憾多少。Wopt 就表示，每次都运气好，选择了最好的选择，该得到多少收益，WBi 就表示每一次实际选择得到的收益，两者之差就是“遗憾”的量化，在 T 次选择后，就有了累积遗憾。Bandit 算法的套路就是：小心翼翼地试，越确定某个选择好，就多选择它，越确定某个选择差，就越来越少选择它。

Bandit 算法中有几个关键元素：臂，回报，环境。

16.1.1 臂：是每次选择的候选项，好比就是老虎机，有几个选项就有几个臂；每次推荐要选择候选池，可能是具体物品，也可能是推荐策略，也可能是物品类别；

16.1.2 回报：就是选择一个臂之后得到的奖励，好比选择一个老虎机之后吐出来的金币；用户是否对推荐结果喜欢，喜欢了就是正面的回报，没有买账就是负面回报或者零回报；

16.1.3 环境：就是决定每个臂不同的那些因素，统称为环境。推荐系统面临的这个用户就是不可捉摸的环境。

16.2 最常用的几个 Bandit 算法

16.2.1 汤普森采样算法（简单粗暴）

推荐，它只要一行代码就可以实现，并且数学的基础最简单。每个臂是否产生收益，起决定作用的是背后有一个概率分布，产生收益的概率为 p。每次做选择时，让每个臂的概率分布各自独立产生一个随机数，按照这个随机数排序，输出产生最大随机数那个臂对应的物品。关键在于每个臂背后的概率分布，是一个贝塔分布，贝塔分布有 a 和 b 两个参数。

当 a+b 值越大，分布曲线就越窄，分布就越集中，这样的结果就是产生的随机数会容易靠近中心位置；

当 a/(a+b) 的值越大，分布的中心位置越靠近 1，反之就越靠近 0，这样产生的随机数也相应第更容易靠近 1 或0.

这和前面所讲的选择有什么关系呢？把贝塔分布的 a 参数看成是推荐后得到用户点击的次数，把分布的 b 参数看成是没有得到用户点击的次数。按照这个对应，再来叙述一下汤普森采样的过程。取出每一个候选对应的参数 a 和 b；为每个候选用 a 和 b 作为参数，用贝塔分布产生一个随机数，按照随机数排序，输出最大值对应的候选；观察用户反馈，如果用户点击则将对应候选的 a 加 1，否则 b 加 1；Python 实现汤普森采样就一行：

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

16.2.2.UCB 算法

UCB 算法全称是 Upper Confidence Bound，即置信区间上界。它也为每个臂评分，每次选择评分最高的候选臂输出，每次输出后观察用户反馈，回来更新候选臂的参数。

公式有两部分，加号前面是这个候选臂到目前的平均收益，反应了它的效果，后面的叫做 Bonus，本质上是均值的标准差，反应了候选臂效果的不确定性，，就是置信区间的上边界。t 是目前的总选择次数，Tjt 是每个臂被选择次数。如果一个候选的被选择次数很少，即 Tjt 很小，那么它的 Bonus 就会较大，在最后排序输出时有优势，候选的平均收益置信区间越宽，越不确定，越需要更多的选择机会。反之如果平均收益很大，就是说加号左边很大，也会在被选择时有优势。

以上相同点：（很重要，很重要，很重要）

以每个候选的平均收益为基准线进行选择； 对于被选择次数不足的照顾； 选择倾向的是那些确定收益较好的候选。（推荐系统需要考虑的）

16.2.3. Epsilon 贪婪算法

算法简单粗暴：先选一个 (0,1) 之间较小的数，叫做 Epsilon，每次以概率 Epsilon 做一件事：所有候选臂中随机选一个，以 1-Epsilon 的概率去选择平均收益最大的那个臂。

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

16.2.4. 效果对比

横坐标是模拟次数增加，可以看成随着时间推移，纵坐标就是累积遗憾，越高说明搞砸的次数越多。

和不顾用户反馈的（完全随机）和认准一个好的（朴素选择），以及大概率（epsilon）相比，UCB 算法和汤普森采样都显著优秀很多。

冷启动问题可以用 Bandit 算法来解决一部分

分类或者 Topic 来表示每个用户兴趣，我们可以通过几次试试验，来刻画出新用户心目中对每个 Topic 的感兴趣概率。如果用户对某个 Topic 感兴趣，就表示我们得到了收益，如果推给了它不感兴趣的 Topic，推荐系统就表示很遗憾 (regret) 了。当一个新用户来了，针对这个用户，我们用汤普森采样为每一个 Topic 采样一个随机数，排序后，输出采样值 Top N 的推荐 Item。注意，这里一次选择了 Top N 个候选臂。等着获取用户的反馈，没有反馈则更新对应 Topic 的 b 值，点击了则更新对应 Topic 的 a 值。

17 结合上下文的Bandit

上述的问题：置信区间会变窄，更准更稳妥，但是来来去去都是那几个，置信区间会变宽，比较冒风险。

yahoo对UCB，进行修改（加入选项的特征，之前选项臂与选项臂之间是没有联系），LinUCB收敛比 UCB 更快，也就是比 UCB 更快见效；各个候选臂之间参数是独立的，可以互相不影响地更新参数；由于参与计算的是特征，所以可以处理动态的推荐候选池，编辑可以增删文章。

举一个简单LinUCB的例子，假设现在两个用户，用户有一个特征就是性别，性别特征有两个维度，男，女。现在有四个商品要推荐给这两个用户，示意如下

两个用户就是 Bandit 算法要面对的上下文，表示成特征如下：.

每一次推荐时，用特征和每一个候选臂的参数去预估它的预期收益和置信区间。如用 xi×θj，这就是给男性用户推荐剃须刀，给女性用户推荐口红，再观察用户是否会点击，用点击信息去更新那个被推荐了的候选臂的参数。

特征好说，有一个重要的地方：对于商品的参数如何求？也就是这里的西塔θ，如何得到？

假如 D 是候选臂是候选臂在 m 次被选择中积累的特征，相当于就是 m 条样本，特征维度是 d，所以 D 是一个矩阵，维度是 m x d。这 m 次被选择，每次得到用户的点击或者没点击，把这个反馈信息记录为一个 m x 1 的向量，叫做 C。所以这个候选臂对应的参数就是 d x 1 的向量，d 就是特征维度数，记录为一个戴帽子的西塔，θ^。，参数和特征之间线性相乘就应该得到收益：

D 也知道，C 也知道，要求 θ，这就很简单了

由于数据稀疏，实际上求参数西塔时不会这样简单粗暴，而是采用岭回归的方法（岭回归主要用于当样本数小于特征数时，对回归参数进行修正），给原始特征矩阵加上一个单位对角矩阵后再参与计算：

每一个候选臂都像这样去更新它的参数，同时，得到参数后，在真正做选择时，用面对上下文的特征和候选臂的参数一起。如果 x 是上下文特征，则期望收益和置信上边界的计算方法分别是下面的样子。

西塔（带帽子）其实归根结底，观察用户的反馈，简单说就是“是否点击”，将观察的结果返回，结合对应的特征，按照刚才给出的公式，去重新计算这个候选臂的参数。

当然，LinUCB 以及所有的 Bandit 算法都有个缺点：同时处理的候选臂数量不能太多，不超过几百个最佳。因为每一次要计算每一个候选臂的期望收益和置信区间，一旦候选太多，计算代价将不可接受。LinUCB 只是一个推荐框架，可以将这个框架应用在很多地方，比如投放广告，为用户选择兴趣标签。

18 结合协同过滤的Bandit（COFIBA）

18.1 LinUCB存在什么问题？

Bandit的核心思想是，走一步看一步，很准的。但是候选臂如太多，比较麻烦。如果能用协同过滤对用户聚类，如此一来，物品的类簇数目相对于物品数就要大大减少。

例如，父母家庭成员给你安排了很多（非常多）相亲对象，如果每个都看一遍，太麻烦。这几个家庭成员，各分一派，有的看重相貌，有的看重性格，有的看重背景。你可能偏向其中一派，从一派中挑出分数最高的，去见她，回来说感受，同时大家一起调整，就越来越准了。这就是基于协同过滤的Bandi算法上的COFIBA算法。

18.2 COFIBA要点

18.2.1 在时刻 t，有一个用户来访问推荐系统，推荐系统需要从已有的候选池子中挑一个最佳的物品推荐给他，然后观察他的反馈，用观察到的反馈来更新挑选策略。

18.2.2 这里的每个物品都有一个特征向量，所以这里的 Bandit 算法是 context 相关的，只不过这里虽然是给每个用户维护一套参数，但实际上是由用户所在的聚类类簇一起决定结果的。

18.2.3 这里依然是用岭回归去拟合用户的权重向量，用于预测用户对每个物品的可能反馈（payoff），这一点和我们上一次介绍的 LinUCB 算法是一样的。

简单来说就是这样：

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