本文是推荐算法实战系列第12篇文章。
前面文章包括：
- 推荐系统简介
- 特征工程
- embedding
- 精排
- 召回（1）：传统召回以及召回中的loss设计
- 召回（2）：word2vec召回、FM召回和双塔召回
- 召回（3）：图卷积
- 粗排
- 重排
- 多任务与多场景（1）
- 多任务与多场景（2）
本文介绍冷启动。
冷启动是指针对较少行为信息的新用户、新物料的推荐。推荐算法赖以存在的基础是用户-物料的交互信息，但是对于新用户、新物料，缺乏相应数据，算法陷入“巧妇难为无米之炊”的境地。很多经典的算法从原理上就不支持新用户、新物料。例如，Item2Vec对在训练集中未出现的物料无法获得其embedding；DIN/SIM要对用户行为序列做Attention，在新用户身上就没有了用武之地。
解决冷启动问题，有一些常规的经典的策略，比如：
- 给新用户推荐热门物料。
- 不依赖用户序列，重视基本属性（性别、年龄、物料的分类与标签等）。
本文介绍近年提出的一些新算法，包括，元学习、对比学习、迁移学习等。
1、Bandit算法
1.1、多臂老虎机
多臂老虎机（Marti-armed bandit，MAB）是一种赌博游戏。每台老虎机有多个手柄，拉动一根手柄，老虎机会吐出金币。每根手柄每次吐出金币的数目是随机的，但是遵循一个固定的概率分布，这个分布对赌徒未知。赌徒一共有N次尝试机会，他希望找到一个最优策略，使获得的金币数目最多。
MAB问题有几个要素：
- 老虎机
- 手柄
- 金币（反馈or收益）
- 概率分布未知（每个手柄的收益概率）
- 成本有限：N次尝试
- 目的：在给定N次尝试下，得到最大的收益（获取最多的金币）。
MAB问题的难点：
- 事先不知道收益的概率分布。
MAB问题与冷启动问题很相似：
- 新用户冷启动问题，每个新用户就是一台老虎机，每个兴趣大类就是老虎机的一个手柄。向用户展示某个兴趣类目下的物料，相当于拉动一根手柄。用户的反馈（比如点击）相当于老虎机的金币。我们希望有限次的曝光试探，使得用户正反馈最大化，相当于摸清了用户的兴趣分布。（备注：手柄数目有何限制？）
- 新物料冷启动问题，所有用户组成一台老虎机，新物料池中的每个新物料相当于一根手柄。曝光某个新物料相当于拉动一次手柄。我们希望通过有限次数的曝光探查，找到新品池中最优质的物料。
MAB问题的最优解是找到收益概率最大的手柄，由于我们没有任何先验知识，开始只能随机探查。但是随着数据的积累，我们应该对每个手柄的收益概率有更准确的估计。于是，这类问题的探查步骤通常分成两步：Explore和Exploit。
- Explore：先将每个手柄拉动n次，统计每个手柄的平均收益。
- Exploit：根据上一步的统计数据，找到平均收益最高的手柄，剩余的机会全部用来拉动收益最高的手柄。
上述算法的缺点在于第一步探索的次数n很难设置。n太少，估计的收益分布误差高；n太大，留给exploit步骤的剩余拉杆机会太少。 MAB算法优化的本质是如何在explore和exploit之间平衡。业界提出了很多进阶的算法。
Explore&Exploit是一类经典的算法，俗称EE，本文介绍的算法在很多场合都有应用。
1.2、Epsilon Greedy
针对上述问题，业界提出了Epsilon Greedy算法，不再严格区分为explore和exploit两阶段，而是explore和exploit交替进行。每一步先采样一个随机数c（可以按照平均采样），当c大于阈值epsilon时执行exploit，反之执行explore。
其伪代码如下：
Input: $\epsilon$ to dertermin whether to explore or exploit
Initialize $\bar R$ with all zeros. Loop N times:
c = UniformRandomNumber() // if c < $\epsilon$: // exlplore $\space \space $ a = choose one arm randomly else: $\space \space $ a = $argmax_i \bar R(i)$ Pull arm a and get reward ‘r’ update $ \bar R(a)$ with reward ‘r’ End Loop
Epsilon Greedy 的一种变体是Decay Epsilon Greedy，也就是让阈值 $\epsilon$随时间衰减。
- 前期阈值较大，算法有更多的机会去探索各个手柄的收益分布；
- 随着尝试的次数增多，统计出的收益分布误差下降，后期阈值较小，鼓励算法更多执行exploit赚钱更多收益。
1.3、UCB
上述算法只考虑了平均收益。但是，平均值有不确定性，为此有人提出了Upper Confidence Bound（UCB）算法。既考虑平均值，也要考虑平均值的置信度。
UCB算法认为，每次尝试时，应该选择收益上限最高的那个手柄。每个手柄的收益，可以认为是在平均值+/- confidence interval 附近。
第i根手柄的收益上限为：
\[UCB(i) = \bar R(i) + c \sqrt{\frac{2logN}{n_i}}\]（备注，confidence interval如何计算？）
- 第一项表示手柄i的平均收益。
- 第二项表示收益的不确定性。N是目前尝试的总次数，ni是第i跟手柄尝试的次数。不确定性越大，越值得探索。
- c表示“收益均值”与“收益潜力”之间的调节权重。和Decay espsilon greedy一样，c也随时间衰减。后期explore下降，exploit增加。
关于上限的计算，解释如下：
在数理统计中，已知n个样本时，可以统计出样本的均值$\bar x$和方差sd，那么我们对真实值95%置信区间的估计为：
\[[\bar x - 2 * sd(x), \bar x + 2 * sd(x)]\]UCB算法的一般形式为：
\[U(a_i) = \underbrace{\hat \mu_i}_{exploitation} + \underbrace{sd(\hat \mu_i)}_{exploration}\]计算置信区间的方法有很多种，其中一种根据Hoeffding’s inequality而来，最终经过简化，可以得到前述公式。演算细节略去。
UCB算法将explore和exploit两个步骤合二为一。
1.4、Probability Matching
PM的基本原理是选中某个手柄的概率与该手柄的收益指标成正比。在Boltzmann Exploration中，拉动第i根手柄的概率如下公式所示：
\[p(i) = \frac{exp(\frac{\bar R(i)}{\tau})}{\sum_{j=1}^{N}exp(\frac{\bar R(j)}{\tau})}\]- $\bar R(i)$ 是到目前为止，第i根手柄的平均收益。
- $\tau$是温度系数，用于平衡explore和exploit。它越大，上式越趋向于平均分布，从而鼓励explore；反之，越集中在平均收益最大的那个手柄，即鼓励exploit。
1.5、Bayesian Bandit
上述几种方法都是基于频率学派，根据试验统计出一个确定的数字刻画手柄的收益。
“贝叶斯学派”的观点认为，每个手柄的平均收益不是一个确定值，而是遵循某个概率分布的随机数字。 平均收益的概率分布可以根据Bayes公式进行推理。
\[后验概率 = \frac{似然函数 * 先验概率}{常数项}\]由于分母是常数项，可以去掉，得到：
\[后验概率 \propto (似然函数 * 先验概率 )\]也可以写成：
\[试验数据 + 先验概率分布 =》后验概率分布\]当我们有了后验概率时，从各手柄的平均收益的后验分布中，随机采样一个数字，选择采样数字最大的那个手柄。
作为知识储备，先介绍贝叶斯推断中的共轭分布和共轭先验。
如果两个分布（通常是先验分布和后验分布）的函数形式一样，只是参数不一样，则称他们为共轭分布。由于后验分布是由先验分布与似然函数相乘而得，共轭分布通常要与给定的似然函数相配套。对于给定的似然函数，如果某个先验分布与它相乘得到的后验分布是共轭分布，则称这个先验分布是这个似然函数的共轭先验。
最常见的共轭先验有：
- 对于二项分布（N重伯努利分布，例如抛N次硬币）来说，Beta分布是其共轭先验。
- 对于多项式分布（例如抛色子实验）来说，狄利克雷分布是其共轭先验。
当各个手柄的收益是二元变量，非0即1时，可以用伯努利分布来描述。多次拉杆试验可以用二项分布描述。此时，每根手柄的收益的均值，可以用二项分布的共轭先验Beta分布来描述。好处是，后验分布与先验分布形式相同，也是Beta分布，方便Bayes公式计算。
这种Bayes Bandit算法被称为Thompson Sampling。算法伪代码如下：
for k = 1… K do //初始化每个兴趣分类的beta分布参数。 $\space \space$ Initialize $\alpha_k \space and \space \beta_k $//比如初始化成1，先验分布退化成平均分布。 end for
for t = 1, … do //开始第k次尝试。
for k = 1,… K do //为每个兴趣分类采样一个随机数。 $\space \space \space \space \space$ Sample $x_k$ ~ beta($\alpha_k, \beta_k$) end for
Choose interest category as $c_t$ = argmax $x_k$ //选择随机数最大的兴趣分类
//从兴趣分类$c_t$中选择一个物料推荐给用户。
// $r_t$是用户反馈
$r_t = recommend(c_t)$ $(\alpha_{c_t}, \beta_{c_t}) = (\alpha_{c_t}, \beta_{c_t}) + (r_t, 1-r_t)$ //更新选中那个兴趣分类的beta参数，公式来自beta分布的性质。
end for
- 每个用户想象成一个老虎机，假设有K个兴趣分类，相当于每个用户有K个手柄。
- 每次采样一个兴趣分类，从中挑选一个物料推荐给用户，同时收集反馈，更新该兴趣分类的beta参数。
- 如何获取一个兴趣分类下的物料，方法多种多样，包括大数据统计，运营筛选等。
- 不断迭代更新每个兴趣分类的参数。最终得到每个兴趣分类比较准确的后验概率。
- （备注：所有用户共享同一套参数，无个性化。）
1.6、Contextual Bandit
上述几种方案有一个共同点，每个手柄的收益分布虽然对赌徒未知，但是它们是固定的，每个赌徒一样。基于这个假设发展出来的bandit算法称为context-free bandit。与之相反的另一类算法称为Contextual Bandit，认为每个手柄的收益不是固定的，而是与上下文有关。
LinUCB是一种著名的Contextual Bandit算法，被Yahoo用于新闻推荐。新闻推荐时效性强，不能等每篇新闻积累期足够的用户反馈再推荐。
Yahoo基于MAB解决这一问题，通过在线探索出优质新闻并立刻加以开发。每个新闻当做一个手柄，同时为增强个性化，每个手柄的收益并不固定，而是随着用户不同而变化。
推荐新闻a，即拉动手杆a的平均收益如下所示：
\[E(r_{t,a}|x_{t,a}) = \theta ^T_a x_{t,a}\]- $r_{t,a}$表示第t次推荐新闻a的收益。
- $x_{t,a}$表示第t次推荐新闻a的上下文，由当时的用户特征，物料特征，环境特征等组成的特征向量。向量维度为d。
- LunUCB中的Lin表示线性，即收益与特征的关系为线性。采取线性函数，主要是为了让置信区间有解析解，方便计算上限。
- $\theta_a \in R^d$是这个线性函数的权重，需要学习得到。每篇新闻a有自己的权重，需要根据其过往的交互历史单独训练出来。
接下来的问题是如何求解最优权重$\theta_a$。我们为新闻a收集的训练数据和label如下：
\[D_a = [x_{1, a}^T, ..., x_{m, a}^T] ^T, c_a = [r_1, r_2, ..., r_m]\]- m: 到目前为止，新闻a被推荐了m次，m条样本。
- $D_a$：每次推荐新闻a时，上下文组成的特征矩阵。
- $c_a$：每次推荐新闻a获得的真实收益，label。
为了求解a，我们拿真实收益$c_a$，和根据前述公式预测的收益做岭回归（Ridge Regression）( 备注：为何要用岭回归？)
\[loss_{ridge} = \frac{1}{2}[||c_a - D_a \theta _a||^2 + ||\theta_a||^2]\]对loss求导，可以得到最优权重：其中I是单位矩阵：
\[\begin{aligned} \theta_a &= A_a ^{-1}b_a \\ A_a &= D_a^T D_a + I_d \\ b_a &= D_a^Tc_a \end{aligned}\]根据矩阵相乘的性质，还可以写成：
\[\begin{aligned} A_a &= I_d + \sum_{i=1}^m x_{i,a} x_{i,a}^T \\ b_a &= \sum_{i=1}^m r_i x_{i,a} \end{aligned}\]求解出参数后，可以得到平均收益，接下来是求置信度。LinUCB的文献指出，新闻a的收益有不小于$1-\delta$的概率落在区间$[\mu_{a,t} - s_{a,t}, \mu_{a,t} + s_{a,t}]$之内。
\[\begin{aligned} \mu_{a,t} &= \theta_a^T x_{a,t} \\ s_{a,t} &= \alpha \sqrt{x_{t,a}^T A_a^{-1}x_{t,a}} \\ \alpha &= 1 + \sqrt{\frac{log\frac{2}{\delta}}{2}} \end{aligned}\]得到置信区间后，每次遍历候选新闻池，从中找到收益上限最高的新闻推荐出去。
LinUCB的伪代码如下：
for t = 1, … T do // 若干轮试验
for a $\in A^t$ do // 每轮试验遍历所有候选新闻。
make feature vector $x_{t,a}$ //特征向量。 if a is new then //初始化。
$A_a = I_dd$ //初始化成d*d的单位矩阵。 $b_a = 0_d$ //初始化成d维的全零向量。 else then load $A_a, B_a$ // 提取上次参数。 end if
$\theta_a = A_a^{-1}b_a$ //该篇新闻当下的最优权重。 $h_{t,a} = \theta_a^T x_{t,a} + \alpha \sqrt{x_{t,a}^T A_a^{-1}x_{t,a}}$ //当前收益上限。
end for // 选择收益上限最高的新闻推荐。 Choose best arm $a_t = argmax_{a \in {A^t}} h_{a,t} $ Observe rewart $r_t$ // //根据用户反馈，增量更新选中的新闻的参数。 $A_{a_t} = A_{a_t} + x_{t,a_t} x_{t,a_t}^T$ $b_{a_t} = b_{a_t} + r_t x_{t,a_t}$
end for
本文总访问量次