推荐系统中的探索和利用

1.探索和利用（EE）问题

探索与利用（Exploration and Exploitation）问题简称 EE 问题，是计算广告和推荐系统里最常见的两大问题之一（另外一个是冷启动问题）。EE 问题中的利用（Exploitation），表示对用户比较确定的兴趣，要利用开采迎合；而探索（Exploration）则表示光对着用户已知的兴趣使用，用户很快会腻，所以要不断探索用户新的兴趣才行。

之所以会有 EE 问题，是因为给用户推荐物品本身就是一个选择的问题，从选择什么物品推荐上升到最根本的推荐策略的选择，不同的策略起到的效果是不一样的。一个极端表现就是总是按照已知用户兴趣来推荐，会让用户觉得总是重复推荐类似的东西，没有惊喜感，而如果完全随意地给用户推荐各种东西，推荐的多样性是有了，但可能大部分物品是用户不喜欢的，让用户觉得推荐得不准确。可以看出，这两种极端的选择策略本身就是矛盾的，因此实践中应以平衡推荐系统的准确性和多样性为标准来进行选择，如何能够来衡量呢？最常用的就是利用 Bandit 算法。

2.Bandit 算法原理

Bandit 算法是解决 EE 问题的一类有效算法，并不是指一个算法。Bandit 算法来源于历史悠久的赌博学，它要解决的问题是这样的：一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么每次该选择哪个老虎机可以做到最大化收益呢？这就是多臂老虎机问题（Multi-armed bandit problem, K-armed bandit problem, MAB），因此 EE 问题也常被称为 MAB 问题。

Bandit 算法需要量化一个核心问题：错误的选择到底有多大的遗憾？能不能遗憾少一些？所以我们便有了衡量 Bandit 算法的一个指标——累积遗憾 (regret)：

$$R_{A}(T) \overset{def} = E \left [ \sum_{t=1}^T r_{t,a_t^*}\right] – E\left[ \sum_{t=1}^T r_{t,a_t}\right]$$

其中，$r_{t, a_t^*}$表示第 t 轮最优的那个 arm 所获得的收益，而 $r_{t, a_t}$表示第 t 轮实际选择的 arm 所获的收益，每次都会计算当前选择的 arm 获取的收益与最优 arm 期望最大收益之间的差距，把每次差距累加起来就是总的遗憾。

Bandit 常用的算法如下：

朴素 Bandit 算法

朴素算法 Bandit 算法也是一种贪心算法，其思想是：

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

Epsilon-Greedy 算法

这也是一个朴素的 bandit 算法：

1. 选一个 (0, 1) 之间较小的数作为 epsilon；
2. 每次以 epsilon 的概率随机选取一个臂（用于探索）；
3. 每次以 1-epsilon 的概率选取当前平均收益收益最大的那个臂（用于利用）。

epsilon 的值可以控制对 Exploit 和 Explore 的偏好程度，越接近 0，越保守；越接近于 1，越冒险。epsilon 可以是固定的，也可以设定为逐渐衰减的，类似于模拟退火。

UCB 算法

UCB 算法全称是 Upper Confidence Bound(置信区间上界)，从名称上可以看出，UCB 解决 Multi-armed bandit 问题主要是借助置信区间的概念。置信区间可以简单地理解为不确定性的程度，区间越宽，越不确定，反之亦反之。

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

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

• 如果 Item 置信区间很宽（被选次数很少，还不确定），那么它会倾向于被多次选择，这个是算法冒风险的部分；
• 如果 Item 置信区间很窄（备选次数很多，比较确定其好坏了），那么均值大的倾向于被多次选择，这个是算法保守稳妥的部分；
• UCB 是一种乐观的算法，选择置信区间上界排序，如果是悲观保守的做法，是选择置信区间下界排序。

UCB 算法步骤如下：

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

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

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

   其中，其中加号前面是这个臂到目前的收益均值，后面的叫做 bonus，本质上是均值的标准差，t 是目前的试验次数，$T_{jt} $是这个臂被试次数；

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

3. 观察选择结果，更新 $t$ 和 $T_{jt}$。

Thompson sampling 算法

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

1. 假设每个臂是否产生收益，其背后有一个概率分布，产生收益的概率为 p。
2. 我们不断地试验，去估计出一个置信度较高的 “概率 p 的概率分布” 就能近似解决这个问题了。
3. 怎么能估计 “概率 p 的概率分布” 呢？ 答案是假设概率 p 的概率分布符合 beta(wins, lose) 分布，它有两个参数: wins, lose。
4. 每个臂都维护一个 beta 分布的参数。每次试验后，选中一个臂，摇一下，有收益则该臂的 wins 增加 1，否则该臂的 lose 增加 1。
5. 每次选择臂的方式是：用每个臂现有的 beta 分布产生一个随机数 b，选择所有臂产生的随机数中最大的那个臂去摇。

3.Bandit 算法代码实现

对比不同的 Bandit 的算法的效果：

4.Bandit 算法在推荐系统中的应用

1. 冷启动探索

   对于新用户，因为没有行为可参考，所以他的兴趣是未知的，这个时候就可以利用 Bandit 算法进行用户兴趣探索，新用户的兴趣就是一个个老虎机的摇臂，在不知道每个摇臂的中奖概率的情况下，需要去逐一试验，这个过程也可以看作是用户画像、用户标签的冷启动探索，在实际应用中，要考虑三个关键点：

   • 用于冷启动选择的标签集合数量要有限制，且互相独立尽可能覆盖内容广；
   • 标签索引的内容库要单独准备，保证高质量；
   • 为每一个用户都保存 bandit 算法参数，互相不共享。

2. 兴趣探索

   兴趣探索和冷启动探索类似，只是兴趣探索并不是针对新用户的，而且通常也已经获知用户的一部分兴趣。这个过程其实是一种用户画像的迭代，主要是为了探索更加精细的以及之前不曾表现出的偏好特征。我们依然把兴趣看作是多臂老虎机，首要要保证已知的老虎机能够获得较好的收益，然后分出一部分本金去探索新的老虎机，直到使最终的收益最大化。放在推荐系统中，通常的做法是大部分给用户推荐已知的他感兴趣的内容，小部分是去试探新的兴趣，而收益最大化则可以用点击、加购、购买等量化指标来衡量。

   用户画像迭代的其实是探索过程，其目的有两个：

   • 更加精细化刻画用户的兴趣；
   • 防止陷入用户短期兴趣不能自拔。

3. LinUCB，引入特征的 UCB

   UCB 算法在做解决 EE 问题的时候表现不错，但它是上下文无关（context-free）的 Bandit 算法没有充分利用推荐场景的上下文信息，为所有用户的选择展现商品的策略都是相同的，忽略了用户作为一个个活生生的个性本身的兴趣点、偏好、购买力等因素，因为同一个商品在不同的用户、不同的情景下接受程度是不同的。故在实际的推荐系统中，context-free 的 MAB 算法基本都不会被采用。雅虎的科学家们在 2010 年发表了一篇论文¹，给 UCB 引入了特征信息，称为 LinUCB，在雅虎的新闻推荐中就用到了改造后的 LinUCB。

   单纯的老虎机回报情况就是老虎机自己内部决定的，而在广告和推荐领域，一个选择的回报，是由 User 和 Item 一起决定的。LinUCB 算法做了一个假设：一个 Item 被选择后推送给一个 User，其回报和相关 Feature 成线性关系， 如果我们能用 Feature 来刻画 User 和 Item，在每次选择 Item 之前，通过 Feature 预估每一个 Item 对 User 的期望回报及置信区间，然后选择置信区间上界最大的 Item 推荐，观察回报后再更新线性关系的参数，以此达到试验学习的目的。这样做，选择的收益就可以通过相关 Feature 泛化到不同的 Item 上，这里的 “相关 Feature” 就是 context，也是实际项目中发挥空间最大的部分。

   LinUCB 算法可以将当前用户的特征、物品特征构成所有的相关特征，然后根据每个臂维护的特征系数，计算出预估收益。由于加入了特征，所以收敛速度比 UCB 更快。

   LinUCB 有两个版本：Disjoint 和 Hybrid，Disjoint 表示不同臂之间的不相关，也就是说参数不共享，Hybrid 表示臂之间共享一些参数。 本文仅提及 Disjoint LinUCB。

   特征构建

   LinUCB 论文中提到了如何构建特征，做法也很巧妙，非常值得学习。

   整个特征构建过程包括三部分，先构建原始特征，然后降维，再聚类形成向量化表示，具体过程如下：

   1）构建原始特征

   原始用户特征：

   • 人口统计学：性别特征（2 类），年龄特征（离散成 10 个区间）。
   • 地域信息：遍布全球的大都市，美国各个州。
   • 行为类别：代表用户历史行为的 1000 个类别取值。

   原始文章特征：

   • URL 类别：根据文章来源分成了几十个类别。
   • 编辑打标签：编辑人工给内容从几十个话题标签中挑选出来的原始特征向量都要归一化成单位向量。

   2）对原始特征降维

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

   $$\phi_u^TW\phi_a$$

   其中，$\phi_u$和 $\phi_a$分别表示用户和文章的特征向量，W 是需要优化的参数矩阵。

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

   $$\psi_u \overset{def}= \phi_u^TW $$

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

   3）聚类并完成低维向量化

   然后，用投射后的 80 多维特征对用户聚类，得到 5 个类簇，文章页同样聚类成 5 个簇，再加上常数 1，用户和文章各自被表示成 6 维向量。雅虎的科学家们之所以选定为 6 维，因为数据表明它的效果最好，并且这大大降低了计算复杂度和存储空间。

   算法描述

   LinUCB 基本算法描述如下：

   

   每一行的解释：

   0）设定一个参数 $\alpha$，这个参数决定了我们探索的程度；

   1）开始试验迭代；

   2）获取每一个 arm 的特征向量 $x_{a,t}$；

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

   4）如果当前 arm 还从没有被试验过，那么：

   5）用单位矩阵初始化 $A_a$；

   6）用 0 向量初始化 $b_a$；

   7）处理完没被试验过的 arm；

   8）计算线性参数 $\theta$；

   9）用 $\theta$和特征向量 $x_{a,t}$计算预估回报，同时加上置信区间宽度；

   10）处理完每一个 arm；

   11）选择第 10 步中最大值对应的 arm，观察真实的回报 $r_t$；

   12）更新 $A_{a_{t}}$；

   13）更新 $b_{a_{t}}$；

   14）算法结束。

   LinUCB 代码

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

   import numpy as np     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 disjoint 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] = np.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

   Hybrid 版本的 LinUCB 代码可参考：🔗 Hybird-LinUCB Code

   LinUCB 优点

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

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

4. COFIBA，协同过滤结合 Bandit

   COFIBA（读如 coffee bar）实际上是协同过滤结合 Bandit 演化出的一种算法，协同过滤的基本假设就是 “物以类聚，人以群分”，你的圈子决定了你能见到的物品。虽然这个假设很靠谱，却也使得推荐很容易局限在 “圈内”，新的东西不容易进入圈子，也就没有了惊喜感。而且协同过滤对于新用户，有着难以避免的冷启动问题，所以自然有人想到与 Bandit 算法结合，协同过滤负责利用，达到较好的准确率，Bandit 负责探索。

   COFIBA 算法，在标题为 Collaborative Filtering Bandits²和 Online Clustering of Bandits³的两篇文章中有详细的描述，两篇文章的区别是后者只对用户聚类（即只考虑了 User-based 的协同过滤），而前者采用了协同聚类（co-clustering，可以理解为 item-based 和 user-based 两种协同方式在同时进行），后者是前者的一个特殊情况。下面详细介绍一下这种结合算法。

   基本思路

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

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

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

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

   算法描述

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

   

   整体算法过程如下：

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

   1）首先计算该用户的 Bandit 参数 W（和 LinUCB 相同），但是这个参数并不直接参与到 Bandit 的选择决策中（和 LinUCB 不同），而是用来更新用户聚类的；

   2）遍历候选 Item，每一个 Item 表示成一个 context 向量了。

   3）每一个 Item 都对应一套用户聚类结果，所以遍历到每一个 Item 时判断当前用户在当前 Item 下属于哪个类簇，然后把对应类簇中每个用户的 M 矩阵（对应 LinUCB 里面的 A 矩阵），b 向量（payoff 向量，对应 LinUCB 里面的 b 向量）聚合起来，从而针对这个类簇求解一个岭回归参数（类似 LinUCB 里面单独针对每个用户所做），同时计算其 payoff 预测值和置信上边界。

   4）每个 Item 都得到一个 payoff 预测值及置信区间上界，挑出那个上边界最大的 Item 推出去（和 LinUCB 相同）。

   5）观察用户的真实反馈，然后更新用户自己的 M 矩阵和 b 向量（更新个人的，对应类簇里其他的不更新）。

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

   • 更新 User 聚类
   • 更新 Item 聚类

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

   

   上图所示的是过程为：

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

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

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

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

   COFIBA 代码

   COFIBA 的代码可参考：🔗COFIBA Code

   COFIBA 总结

   简单来说就是这样：

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

5.EE 的其他实践

在工业界真正的应用实践中，Bandit 算法不一定好用， 因此很少有公司直接使用理性 Bandit 算法，取而代之的是一些具有发散性的策略或者一些小技巧，相比而言用更加盲目主观进行探索，基本原则是适当地降低整体的相关性，增加探索的比例。

比如下面几个：

• 人群算法：UserCF、用户聚类

  这个和上面提到的 COFIBA 类似，在应用协同过滤的时候，可以找一些相关性不是那么强的人群聚类以实现发散性的探索拓展；

• 兴趣探索：相似话题、搭配推荐

  利用相似性进行跨越式的关联扩展，比如 A 与 B 相似，B 与 C 相似，则可从 A 扩展到 C，但其实 A 到 C 之间的相似性差一点，这样跨过一个或多个相似关联进行推荐，可以降低相关性，提高探索能力；

• Graph Walking

  这也是一个经典做法，通常会与 Embedding 相结合，具体可参考🔖 推荐系统的中 EMBEDDING 的应用实践.DeepWalk，Graph Walking 的过程是：先利用多个用户的行为序列可以构建出一个 Item 图，然后进行随机游走（Random Walk）产生大量的 Item 序列，最后利用这些序列进行 Embedding 学习。因为随机游走的随机性，因此利用 Graph Walking 也能增加探索能力；

• 平衡个性化推荐和热门推荐比例

  这个很容易理解，在最终的推荐中，除了包含个性化推荐筛选出的一些 Item，还可以适当地加入一些热门推荐，利用热门推荐来实现探索；

• 随机丢弃用户行为历史

  推荐系统的模型并不是越准确越好，有时候为了能够让模型学习更加发散一点，故意丢弃一些用户行为数据。这是一个非常取巧的手段，但在工业界性价比很高；

• 随机扰动模型参数

  这个方法和上一方法类似，不过上一方法是在模型学习前，这一方法是在模型学习后，当模型学习好之后，对参数稍微进行一些扰动，其目的也是能让模型预测更有发散性，增加探索能力。

6.EE 带来的现实问题

探索还是利用，本身矛盾，经过上面的讲解我们似乎觉得只要使用简单技术手段就能实现它们之间平衡，并且还能在探索的同时实现收益最大化。然而在真实世界这个大环境中，事情往往并不简单，有很多因素会影响我们的决策，到底是追求眼前的苟且（当前收益）还是远方的田野（长远生态），还需要从更多的角度去看待问题⁵：

• 探索伤害用户体验，可能会导致用户流失

  不确定性虽然可能会给用户带来一些惊喜感，但也可能会给用户带来非常不好的体验，极可能导致用户流失。因此，很多公司在产品开始阶段是不会做 EE 探索的。

• 探索带来的长期受益（留存率）评估周期长，KPI 压力大

  不同于评估点击率或者购买金额等指标，上线某些策略后可以很快的看到指标的变化。而探索带来的长期收益如留存率，评估周期很长，甚至在很多策略累积的影响下，并不好评估某些指标的上升和下降就一定和探索有关系。因此，在进行探索策略的实施时，很容易受到部门 KPI 的压力，从而失去动力进一步探索研究，最终导致推荐越来越窄，缺乏惊喜度。

• 如何平衡实时兴趣和长期兴趣？

  要区分出短期兴趣和长期兴趣，比如某用户送别人礼物，搜索并浏览了一些包，短时推荐一些包可以，但从长期数据来看，其实该用户更喜欢数码产品，不能因为最近用户浏览包多，之后就一直推荐包，导致看什么就推荐什么，容易引起用户反感。推荐要向前看也要向后看，平衡实时兴趣和长期兴趣。

• 如何平衡短期产品体验和长期系统生态？

  短期产品体验很重要，但也要考虑到长期的生态平衡，不能只为了某一个指标的提升而不折手段，导致系统生态被破坏，影响到长期收益。因此要多维度地看待整个生态，避免为了短期效益而导致劣币驱逐良币，要根据产品的定位去平衡大众口味和小众需求，除了大众用户喜欢的快餐文化，更要保留有深度的优质作者，建立产品的价值观和愿景，维持整个系统生态的健康。

7.参考资料