1 前言
互联网技术和大数据技术的迅猛发展正在时刻改变我们的生活，视频网站、资讯app、电商网站等每天都有大量的活跃用户在不断的产生海量的用户行为，同时，每天又都产生大量的新增PGC或者UGC内容（如小说、资讯文章、短视频等）。
从推荐系统的角度来看，系统每时每刻都面临大量的新旧用户、新旧物品和大量的用户行为数据，对于用户，我们需要对要用户进行建模，去刻画用户的肖像和兴趣，然而我们常常面对的情况是用户的行为是稀疏的，而且可能存在比例不一的新用户，如何给新用户推荐，是推荐系统中的一个著名问题，即冷启动问题，给新用户展示哪些item决定了用户的第一感和体验；同时在推荐过程中，我们需要考虑给新item展示的机会，比如给一个喜欢科幻电影的user推荐一些非科幻类型的电影，提高推荐的多样性，这就是推荐系统中另外一个问题，即探索和利用的问题。
2 冷启动和EE问题
推荐系统需要根据历史的用户行为和兴趣偏好预测用户未来的行为和兴趣，因此历史用户行为某种程度上成为推荐推荐的重要先决条件。实际过程中，我们面对大量的新用户，这些用户我们并不知道他们的profile，对于这些用户，常用的冷启动的算法包括根据已有的个人静态信息（年龄、性别、地理位置、移动设备型号等）为用户进行推荐。然而实际情况下，我们很难在系统中直接获取这些用户信息。给新用户推荐的item，由于成本较高（用户不感兴趣就再也不来了），我们需要保证item要足够热门，要保证足够的多样性，同时尽量保证可区分。
与用户的冷启动相对应的，则是item的冷启动，当一个新物品加入站内，如何快速的展现的用户。特别是在某些场景下，推荐列表是给用户展示的唯一列表，那么显而易见，只能在推荐列表中尝试给用户推荐新物品。对于CF算法来说，无论是基于领域还是基于模型，如果想要这个新物品被推荐出来，显然我们需要获得用户对这个物品的行为数据。一个最简单的做法就是在推荐列表中随机给用户展示新物品，但是这样显然不太个性化。一个较好的做法是将新物品推荐给曾经喜欢过与新物品相似物品的用户。由于新item没有用户行为，因此物品相似度只能从item自身出发，包括根据item的内容信息挖掘出item的向量表示，通过向量相似度来刻画物品相似度，还可以利用topic model挖掘出item的主题分布等等。
推荐系统需要考虑对用户兴趣的不断探索和细化，同时也需要尽可能的扩大展示物品的多样性和宽度。比如极端情况下给用户展示物品的场景只有推荐列表，同时我们需要尽可能优化的ctr，那么给冷启动用户我们该如何选择物品，如何快速的探测出用户的兴趣？
举例来说，对于一个热爱足球的足球迷我们该如何选择给他推荐的物品？比较简单的方式我们可以可以根据ctr排序，给冷启动用户推荐最热门、点击率最高的物品，给他推荐点击率最高的足球相关物品，显然这样做会保证我们推荐结果的ctr会比较高，但是这样做会减少我们推荐结果的覆盖率，降低推荐结果的多样性，以致于推荐物品候选集也会收敛，出现反复推荐。比如对于资讯来说，用户看到的资讯都是点击率较高的搞笑类，但是显然“搞笑”并不能刻画的兴趣。而这也就是我们必须得不断探索用户兴趣，扩大推荐结果多样性的原因。
简单来看这其实是一个选择问题，即探索（exploration）和利用（exploitation）问题。接下来本文接下来将详述EE问题和某些已有算法。
3 多臂老虎机模型和UCB算法
当你走进一家赌场，面对20个一模一样的老虎机，你并不知道它们吐钱的概率。假设你的成本是1000元，每摇一次的成本是2元，那么你在总共500次摇臂的机会下，该如何最大化你的收益呢？ 这就是多臂老虎机问题(Multi-armed bandit problem, K-armed bandit problem, MAB)。
一个简单的做法就是每台老虎机我们都摇10次，余下的300次都选择成功率最高的那台。但是显然我们耗费了200次机会来探索，而且我们仍然无法保证实验成功率最高的那台老虎机就是真实成功率最高的。大家也可以猜到，如果我们有足够多的探索机会，那么我们几乎可以选择出成功率最高的老虎机。很遗憾，我们没有足够的探索机会，对应到我们的推荐问题中就是任何的用户展示pv都是珍贵的，况且实际情况的“老虎机”远远不止20台，而且还存在不断新加入的情况，这就导致获取每个item收益率的成本太大。
我们使用累计遗憾（collect regret）来衡量策略的优劣：
t表示当前轮数，
表示平均最大收益，
表示 第t轮的实际收益。累计遗憾公式表明了实际累计收益和理想最佳收益的差值。为了简单起见，我们假设每台机器的收益为伯努利收益，即收益要么是0，要么是1。对应到推荐系统中，老虎机即对应我们的物品（item），每次摇臂即认为是该物品的一次展示，我们可以用是否点击来表示收益，点击(win)的收益就是1，没有点击(lose)的收益就是0。
解决bandit问题的算法众多，一般分为基于semi-uniform的策略、probability matching 策略、pricing策略等。这里只列举若干个策略，具体大家可以参考(https://en.wikipedia.org/wiki/Multi-armed_bandit)。
Epsilon-greedy策略：每次试验都以
的概率选择前面试验中平均收益最佳的item，以
的概率等概率随机选择其他item，该策略简单，而且可以通过
Epsilon-first策略：该策略探索和利用交叉选择，总试验次数为N，探索次数为
，探索阶段也是等概率随机选择所有item，利用阶段也是选择平均收益最好的机器。
Epsilon-decreasing策略：与Epsilon-greedy策略近似，不同地方在于
随着试验的进行会不断减少。
UCB（Upper Confidence Bound）算法
在推荐系统中，通常量化一个物品的收益率（或者说点击率）是使用点击数/展示数，例如点击为10，展示数为8，则估计的点击率为80%，在展示数达到10000后，其表现ctr是否还能达到80%呢？ 显然是不可能的。而这就是统计学中的置信度问题，计算点击率的置信区间的方法也有很多，比如威尔逊置信空间（https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval#Wilson_score_interval）。
UCB算法步骤包括：首先对所有item的尝试一下，然后每次选择以下值最大的那个item:
，其中
是物品
到目前的收益均值，
本质上是均值的标准差。t是目前的试验次数，
是这个item被试的次数。
这个公式表明随着每个物品试验次数的增加，其置信区间就越窄，收益概率就越能确定。如果收益均值越大，则被选中的机会就越大（exploit），如果收益均值越小，其被选中的概率也就越少，同时哪些被选次数较少的item也会得到试验机会，起到了explore的作用。
Probability-matching策略表明一台机器的选择次数应当与它是最佳收益item的概率相同。其中Thompson采样就是一种Probability-matching策略算法，该算法也是一个的在线学习算法，即通过不断的观察数据来更新模型参数。
Thompson采样
Thompson采样假设每个item的收益率为p，那么如何来估计一个item的收益概率p呢？直接用试验结果的收益概率p是否合理呢？ 比如一个item给用户展示了20次，用户点击了16次，那么我们可以认为这个item的收益率是80%吗？而这显然是不合理的，因为我们首先需要考虑的就是这个收益率的置信度，20次试验得出的结果置信度小于试验了10000次试验的置信度，其次可能我们的经验表明所有item的平均收益率只有10%。
Thompson采样使用Beta分布来描述收益率的分布（分布的分布： https://en.wikipedia.org/wiki/Beta_distribution），我们通过不断的试验来估计一个置信度较高的基于概率p的概率分布。假设概率p的概率分布符合Beta(wins, lose)，beta分布有两个参数wins和lose，每个item都维护了beta分布的参数，每次试验都选择一个item，有点击则wins增加1，否则lose增加1。每次选择item的方式则是：用每个item的beta分布产生一个随机数，选择所有item产生的随机数中的最大的那个item。Beta分布概率密度函数如下：
举例来说，推荐系统需要试探新用户的兴趣，假设我们用内容类别来表示每个用户的兴趣，通过几次展示和反馈来获取用户的兴趣。针对一个新用户，使用Thompson算法为每一个类别采样一个随机数，排序后，输出采样值top N 的推荐item。获取用户的反馈，比如点击。没有反馈则更新对应类别的lose值，点击了则更新对应类别的wins值。
4 LinUCB算法
回到推荐列表的场景，推荐系统为用户推荐物品。user和item都可以用一系列特征表示。用户特征包括用户的统计历史行为、人口学属性信息；物品特征包括描述信息、类别信息等等。在这种场景下，探索和利用也必须是个体用户级别上实施，因为不同用户看到相同的物品的反馈差异较大。
LinUCB算法是一种基于上下文特征（用户特征、物品特征）的UCB算法，基于特征进行探索和利用。该算法结合上下文特征，选择给用户的推荐物品，同时利用用户反馈及时修正选择策略，以达到最大化收益（提升点击率）的目标。
使用互斥线性模型的LinUCB
LinUCB算法假设推荐item的每次展现收益（是否点击）是和上下文特征成线性关系的，即：
其中
表示用户特征和物品特征的合集，
表示第t次尝试的收益，a表示item，
表示物品a的位置系数向量。可以看出各个item的模型参数是相互独立的（互斥）。
设（d*m）表示为m个训练上下文，
表示每个上下文的实际收益，对训练数据
使用岭回归训练出的物品a的参数为：
其中
表示d*d的单位矩阵。其中在置信度
下，模型收益与期望收益满足：
其中
，
。
上述等式给出了物品a期望收益的一个UCB，因此也就引申出了UCB的选择策略，对于第t次试验，选择以下式中最大值的物品，
其中
。上述模型中预期收益
的标准差
。
以上为互斥线性模型LinUCB的基本算法流程，其中结合上述内容，第一行
参数控制了explore的程度，即
越大，置信区间上限也就越大，也就加大了explore的程度；4-7行对于新物品，使用单位阵和0l向量进行参数初始化；8-9行计算item a的置信区间上限；11行选择最优item；12-13行更新选择item的模型参数。
思想上LinUCB算法类似于对召回结果重排序的方法，也是考虑用户和item的特征，来计算出收益最大的item，不同的是LinUCB借鉴了UCB的置信区间的方法来平衡exploit和explore问题，同时从LinUCB算法是一个在线的学习算法，与一般离线算法需要离线训练不同，LinUCB随着每次展示和反馈会不断优化我们的模型参数和收益。
关于LinUCB算法的介绍请参考论文http://rob.schapire.net/papers/www10.pdf 。
5 CLUB算法
CLUB(online clustering bandits)算法假设将全部用户划分成若干个用户群，每个用户群对相同推荐内容的反馈是一致的，同时自适应的调整用户群。与liner bandit一样，CLUB算法也是根据特征计算收益，不同的是CLUB算法中相同群体用户共享相同的参数向量，即第i个用户对item a的收益为：
其中表示第i个user，
表示第i个user所属的用户群编号，
表示每个用户群的参数向量，x表示上文下特征，
表示噪声项。
该算法在时刻t，对于用户i，维护一个向量
的估计值
。与liner bandit算法相似，
根据收益反馈不断更新。与LinUCB算法类似的，
可以根据协方差矩阵
（d*d维，初始化为单位阵）的逆和向量
（d维向量，初始化为0向量）计算得出。除此之外，算法需要维护一个无向图
，每个节点表示一个user。算法首先从完全图开始，根据
表示时刻t的用户划分群。显然初始状态下的演化逐步移除节点之间的边。定义第t时刻的用户群个数为
，
，……
表示时刻t的用户划分群。显然初始状态下
=1，
(全部用户)。
在每个时刻t（1，2，……），用户
，相关上下文特征向量集合为
，用户
所属的群为
。CLUB算法根据收益选择item的式如下：
其中
是通过同用户群内各个节点通过最小方差逼近拟合计算得出的聚合权重向量，CB为
向量的置信区间上限。
CLUB算法观察到item的收益
后，更新协方差矩阵
，更新
；虽然不会更新其他节点的M和b，但是会隐式的影响下一轮的聚合权重向量
；接下来判断节点
与相邻节点的参数向量（
）距离，如果足够大，则将该边移除。
CLUB算法的完整流程如下：
其中
控制探索的程度，
是用户关系是否删除的控制参数。上述算法流程包含了删除关系边的条件，其中
是t时刻前历史上i用户被选中的次数。
CLUB算法首先提出了基于协同概念的bandit算法，即每次用户预测对item收益是由这个所属的群体的聚合权重向量参数所决定的，同时根据个人反馈更新个人参数，个人参数又隐式的影响群体参数和用户群体的划分。据CLUB算法论文介绍，在一些公共数据集中，取得了比LinUCB更好的效果，关于CLUB算法的更多细节请参考https://arxiv.org/abs/1401.8257。
6 结束语
本文简单介绍了推荐系统中一直存在的两大问题：冷启动和EE问题，并简单阐述了业界解决这两大问题的一些常见解决方法和算法。正如前文所说，EE问题某种程度中一直以矛盾共同体存在，在实际场景中，需要平衡两者。
