推荐系统之EE问题

推荐中大部分算法会根据用户已知兴趣对用户和视频进行匹配，从而选择个性化的推荐集合。例如在小视频推荐，用户喜欢看美女，就给他推美女视频。但是这样会存在以下几个问题，1. 如果美女是用户真实的兴趣点，那么一直推用户迟早会厌倦。2. 如果用户点美女只是因为平台给他推了这个视频，没有其他更感兴趣的类别可选，那么美女其实不是用户真实的兴趣点。3. 推荐系统是用户，作者，平台三方相互制衡的一个生态系统，作者发布新视频之后平台需要快速冷启推给用户，才能达到这个生态系统的正向流动。基于以上三点，我们在构建推荐系统的时候除了尽可能的利用已知兴趣exploit，还需要开发更多的新兴趣explore。

多臂老虎机MAB（Multi-Arm Bandit）

EE问题一般可通过MAB(Multi-Armed Bandit) 进行建模，如下所示所有 arm 就是每次决策中可作出的选择，拉下某个 arm 表示作出了相应的选择。

MAB示意图

数学上可表示为一个二元组 $<A, R>$ 。

1. $A$ 为一系列可能的动作, $R(r|a)$ 则表示给定动作下的奖赏的分布。
2. 每一时刻根据给定策略从 $A$ 选择动作 $a_t$ , 同时环境根据分布 $R(r|a)$ 生成奖赏 $r_t$
3. 目标是最大化奖赏之和 $\sum_{t=1}^T r_t$

如何在每一刻根据给定策略从A里面选择动作获取奖赏呢？

除去随机方法，下面要介绍的两种方法，UCB 和 Thompson sampling ，均是通过定义每个 arm 的收益的期望，然后选择收益期望最大的 arm。其中，UCB 是频率学派的思想，认为每个 arm 的收益期望是固定的，通过试验记录得到其历史收益状况，然后加上一个 bound 构成了收益期望；Thompson sampling 则是贝叶斯学派的思想，认为 arm 的收益期望服从一个特定的概率分布，通过试验记录更新分布的参数，然后从每个 arm 的分布中产生收益期望。

随机方法

朴素Bandit

先随机试验N次，每次选择收益最大的那个臂

Epsilon-Greedy

先生成一个（0，1）之间的随机数epsilon，随机从所有臂中选择一个，并以1-epsilon的概率选择最大收益的那个臂，更新rewards。

优点：能随时调整策略。
缺点：

ϵ 是个超参数，设置过大会导致决策随机性过大，设置过小则会导致探索性不足；
ϵ-greedy 策略运行一段时间后，对各个 arm 的收益情况有所了解，但没有利用这些信息，仍然不做任何区分地随机 exploration（会选择到明显较差的item）；
ϵ-greedy 策略运行一段时间后，但仍然花费固定的精力去 exploration，浪费了本应该更多进行 exploitation 机会。

针对第 2 个问题，可以在 ϵ-greedy 策略运行一段时间后，选择出收益最高的前 $n$ 个 arm，然后 exploration 时从这 $n$ 个 arm 中随机选择。
针对第 3 个问题，可以设置进行 exploration 的概率 ϵ 随着策略进行的次数而逐渐下降，比如说可以取对数形式 $\epsilon = \frac{1}{1 + \log(m+1)}$ , $m$ 表示目前进行了 $m$ 次的决策。

Thompson Sampling

TS是一种在线学习算法，通过不断观察数据来更新模型参数。它认为评判某个 arm 的优劣的指标不再是个定值，而是服从着某种假定的分布(先验)，通过观察到的历史记录去更新这个分布的参数(似然)，得到了新的分布参数(后验), 然后不断重复这个过程。当需要进行比较时，从分布中随机产生一个样本即可。

所以讲TS之前先复习下beta分布。beta分布可以看作一个概率的概率分布，当你不知道一个东西的具体概率是多少时，beta分布可以给出所有概率出现的可能性大小，也就是说可以用beta分布来模拟各种先验分布。beta 分布横轴为概率值，取值范围是 (0,1)，它有两个控制参数：α 和 β 。
1. α + β 的值越大，分布曲线越窄，也就是越集中；
2. α/(α + β) 的值是期望，它的值越大， beta 分布的中心越靠近 1。

假设每个老虎机都有一个吐钱的概率p符合beta(wins, lose)分布，每个臂都维护一个beta分布的参数，即wins, lose。每次试验后，选中一个臂，摇一下，有收益则该臂的wins增加1，否则该臂的lose增加1。每次选择臂的方式是：用每个臂现有的beta分布产生一个随机数b，选择所有臂产生的随机数中最大的那个臂去摇。

代码实现：

import numpy as np
np.argmax(pymc.rbeta(1 + successes, 1 + totals - successes))

UCB（Upper Confidence Bound）

假如能够对每个 arm 都进行足够多次的试验，根据大数定律，次数越多，这些试验结果统计得到的收益便会约接近各个 arm 真实的收益。由于观测次数有限，基于历史信息（当前老虎机已经探索的次数，吐钱的次数）计算出来吐钱的观测概率p' 和实际吐钱概率p存在一定的差值 ∆ ，即p' - ∆ <= p <= p' + ∆。UCB 的核心就在于如果预估这个误差(也就是 UCB 中的 B(bound))，然后将 arm 统计的收益加上其通过 UCB 方法计算出来的 bound 进行排序，选择最高的那个。

UCB1

UCB1 方法的理论基础是Hoeffding’s inequality，该不等式的定义如下：

假设 $X_1, X_2…X_n$ 是同一个分布产生的 $n$ 个独立变量，其均值为 $\overline{X} = \frac{1}{n}\sum_{i=1}^n X_i$ , 则如下公式成立 $p(|E[X] - \overline{X}| \le \delta) \ge 1 - 2e^{-2n\delta^2}$

更直观地说，该不等式表明了 $n$ 个独立同分布的变量的均值与该变量的真实期望的误差小于某个预设的阈值 $u$ 会以概率 $1 - e^{-2nu^2}$ 恒成立。

所以我们可以将 $X_1, X_2…X_n$ 看做某个 arm 在 $n$ 次试验中获得的收益，则通过上面的式子可以设定一个 $\delta$ 使得公式成立, 然后用 $\overline{X} + \delta$ 来近似真实的收益 $E(X)$ ；理论上也可用 $\overline{X} - \delta$ ，但是 UCB 方法会用上界，这也是 UCB 中 U(upper) 的含义。那么 $\delta$ 该选多大呢？

UCB1 方法认为 $\delta$ 如下公式，公式中的 $N$ 表示目前所有arm试验的总次数， $n$ 表示某个arm的实验次数，
$\delta = \sqrt{\frac{2\ln{N}}{n}}$

直观地看上面定义的 $\delta$ , 分子 $N$ 对所有的 arm 是相同的，分母的 $n$ 则表示某个 arm 目前为止试验的次数，如果这个值越小，那么 $\delta$ 便越大，相当于 exploration；而当各个 arm 的 n 相同时，实际上就是在比较各个 arm 的历史收益情况了。

代码实现：

import numpy as np
T = 1000  # T轮试验
N = 10  # N个老虎机

true_rewards = np.random.uniform(low=0, high=1, size=N)  # 每个老虎机真实的吐钱概率
estimated_rewards = np.zeros(N)  # 每个老虎机吐钱的观测概率，初始都为0
chosen_count = np.zeros(N)  # 每个老虎机当前已经探索的次数，初始都为0
total_reward = 0

# 计算delta
def calculate_delta(T, item):
    if chosen_count[item] == 0:
        return 1
    else:
        return np.sqrt(2 * np.log(T) / chosen_count[item])

# 计算每个老虎机的p+delta，同时做出选择
def UCB(t, N):
    upper_bound_probs = [estimated_rewards[item] + calculate_delta(t, item) for item in range(N)]
    item = np.argmax(upper_bound_probs)
    reward = np.random.binomial(n=1, p=true_rewards[item])
    return item, reward

for t in range(1, T):  # 依次进行T次试验
    # 选择一个老虎机，并得到是否吐钱的结果
    item, reward = UCB(t, N)
    total_reward += reward  # 一共有多少客人接受了推荐

    # 更新每个老虎机的吐钱概率
    estimated_rewards[item] = ((t - 1) * estimated_rewards[item] + reward) / t
    chosen_count[item] += 1

UCB2

从名字上基本就可以猜出 UCB2 是 UCB1 的改进，改进的地方是降低了 UCB1 的 regret 的上界，regret 指的是每次能获得的最大的收益与实际获得的收益的差距，略。

LinUCB

上面的 UCB1 和 UCB2 算法都是解决 Bernoulli Bandit 问题的，也就是假设每个 arm 的优劣是服从伯努利分布，而根据历史记录计算出的 $\overline {x}_j$ （获得收益的试验次数和总试验次数的比值）其实就是伯努利分布的参数。这样基于统计的方法很简单，但是问题也比较显著，因为 arm 的收益会跟多个因素有关（比如说某个 arm 在早上选择时没有收益，但是晚上就有了），利用这些信息可以预估得更准确；而基于统计的方法则忽略了这一点。区别于 Bernoulli Bandit，这类利用了上下文信息的问题就是上面提到的 Contextual Bandit 问题，而 LinUCB 就是要解决这个问题的。

小结

UCB 采用的是频率学派的思想，计算的收益值是历史收益加上一个 bound，可以认为历史收益是 Exploitation，而 bound 则是 ExplorationUCB 采用的是频率学派的思想，计算的收益值是历史收益加上一个 bound，可以认为历史收益是 Exploitation，而 bound 则是 Exploration。

Reference:

1.https://zhuanlan.zhihu.com/p/38875010
2.http://wulc.me/2019/01/05/EE(Exploitation%20Exploration)%20%E9%97%AE%E9%A2%98%E6%A6%82%E8%BF%B0/

[First Edition at 2020-06-21]