深入理解推荐系统算法

深入理解推荐系统：召回

深入理解 YouTube 推荐系统算法

深入理解推荐系统：排序

去年 天池-安泰杯跨境电商智能算法大赛 是我初次接触推荐相关的比赛，通过比赛让我对推荐系统有了较为浅显的认识，赛后也是打算系统的学习这方面的内容，此后我也会将【推荐系统】作为一个系列板块进行更新，主打经典推荐算法的原理，相信每一篇都值得反复研究。

一、背景介绍

作为【推荐系统系列文章】的第一讲，我们将以 YouTube 在 2016 年发表的论文《Deep Neural Networks for YouTube Recommendations》为背景进行 YouTube 的深度神经网络推荐模型的介绍。在此这之前 YouTube 还有三篇介绍 YouTube 视频推荐的论文，如果将这四篇串在一起，也就组成了 YouTube 推荐系统不断发展改进的一个缩影。

2008 年：论文《Video Suggestion and Discovery for YouTube》是由 Shumeet Baluja，Shumeet Baluja 等人在 2008 年发表在 the International World Wide Web Conference Committee (IW3C2)上。文章花了大量篇幅讲了吸附算法（ADSORPTION），该算法的目的就是为了解决视频标签的扩散。所以就大胆推测当时 YouTube 推荐系统应该就是根据用户曾经看过的视频给用户推荐同类视频，也就是拥有相同标签的视频。

2010 年：论文《The YouTube Video Recommendation System》是由 Davidson J, Liebald B, Liu J 等人在 2010 年发表在第四届 ACM RecSys 上。当时 YouTube 推荐系统的核心算法就是基于 Item-CF 的协同过滤算法，换句话说就是对于一个用户当前场景下和历史兴趣中喜欢的视频，找出它们相关的视频，并从这些视频中过滤掉已经看过的，剩下就是可以用户极有可能喜欢看的视频。这里的视频相关性是用共同点击个数来描述的。

2013 年：论文《Label Partitioning For Sublinear Ranking》是由 Jason Weston，Jason Weston 等人在 2013 年发表在第三十届国际机器学习大会上。该论文将推荐问题变成了一个多分类的问题，并解决了在神经网络中如何从最后一层输出层中共找到概率最大的输出节点。

到了 2016 年，YouTube 开始迈向了以深度学习算法为主导的推荐系统阶段，虽然看似离 2020 比较久远，但这篇论文应该作为推荐系统入门必看论文，文中的推荐系统架构设计也是非常的经典，是很多推荐系统架构的基础。

YouTube 推荐系统的三大难点

1. 数据规模：YouTube 的用户和视频量级都是十亿级别的，需要分布式学习算法和高效的部署。
2. 新颖性：推荐系统需要及时对新上传的视频和用户的新行为作出响应。
3. 数据噪音：由于稀疏和外部因素影响，用户的历史行为很难预测。大部分 YouTube 视频只有隐式反馈（即用户对视频的观看行为），缺少显式反馈（即用户对视频的评分）。此外，视频的元信息不够有结构性。我们的算法需要对训练数据的这些因素稳健（robust）。

二、系统概览

YouTube 推荐系统整体架构 第一部分 召回网络：此阶段主要目的是从百万级的视频中检索出一小部分的视频用于之后的排序操作，这部分需要处理的数据量非常大，速度要求快，所有使用的模型和特征都不能太复杂。召回网络会根据用户的历史信息（比如用户的历史观看、搜索等）进行召回，这一阶段召回的视频满足用户泛化的兴趣，用户之间的相似度则通过粗略的特征来表示，如用户观看视频的 ID，搜索 query 和用户画像。

第二部分 排序网络：此阶段会使用更加丰富和精细的用户和视频特征，预测用户对召回的视频打分，然后根据分数进行排序，依次展示给用户。这部分最主要是能够精准的将视频推送给用户，所以需要更加复杂的模型和特征来提升推荐效果。

第三部分 线下评估：评估指标有 precision、recall、ranking loss 等，最终的效果还是需要线上做 A/B 测试，关注的指标包括：点击率、观看时间等；需要指出的是，线上线下有时候并不能保持一致的结果。

接下来一起看看 Matching 和 Ranking 的具体设计思路，同时会给出具体实现代码，帮助加深理解算法原理。在介绍召回模型前，先看看传统的召回思路。

三、Matching

3.1 传统召回思路

先离线计算好商品的 Embedding 以及用户的 Embedding，线上召回的时候，根据用户的 Embedding 去和所有商品的 Embedding 内积，找出 TopN。这种传统的方式需要解决以下几个问题：

• 商品的 Embedding 空间和用户的 Embedding 空间如何保证在同一个空间。
• 需要计算与所有商品的内积，存在性能问题。
• 诸如奇异值分解的方法，输入协同矩阵，特征比较单一。

3.2 问题建模

在召回阶段，YouTube 把推荐问题看成一个超大规模多分类问题，即 Softmax 分类。定义为基于特定的用户 和其上下文 ，在 时刻，将视频库 中指定的视频 划分为第 类的概率。公式如下：

其中 表示（用户，上下文）的高维 embedding， 表示每个候选视频的 embedding 向量。 表示第 个视频的 embedding 向量，这里每个视频都有一个 embeeding 向量表示。

至此，该 DNN 的目标是在给定用户历史行为与上下文的情况下，学习 user embedding 向量 ，作为输入送到 softmax classifier，用以生成初步候选集作为视频召回结果。

3.3 负类采样（重要性采样 softmax）

在每次计算中，softmax 的分母，都需要遍历视频库！ [公式] 中所有的视频，并且用户上下文向量与视频向量之间的点积，exp 等操作造成计算量过大，因此如何高效训练成为一个问题。其解决方法采用了负采样机制（sample negative classes ）提升训练速度，并使用重要性加权（importance weighting）的方式校正这个采样。对于每个样本，对真实标签和采样得到的负类，最小化其交叉熵损失函数。相比经典 Softmax，这有几百倍的速度提升。

3.4 召回模型网络结构

在做 NLP 任务时，如何将文本或者文本中的一字一句，表示成结构化的，计算机能够理解的形式是第一步。经常采用方法的就是 word2vec，就是将所有的 word 表示成低维稠密的 embedding 向量，最后将词的 embedding 向量喂给神经网络进行学习。

召回模型的网络结构 YouTube 的召回模型也受此启发，采用了 word embedding 的技巧来计算每一个视频的 embedding，然后将视频的 embedding，用户搜索视频的 embedding 分别计算 average，再加入用户的属性、视频质量等特征，采用两个完全相连的 ReLU 层和 softmax 函数来预测用户下一个看的视频是什么。

使用 DNN 的原因之一，在 DNN 中连续性变量和类别型变量都很容易输入到模型中，包括一些人口统计特征（Demographic features），对最终的效果起着十分重要的作用。用户的地域，设备等都可以作为 embedding 向量输入到 DNN 中去。简单的二值化特征（如性别）和数值型特征（如年龄）可以直接输入到 DNN 中，数值型需要经过归一化到[0,1]再输入到模型中。

（1）输入层

• 用户观看视频序列 ID：对视频 ID 的 embedding 向量进行 mean pooling，得到视频观看向量（watch vector）。
• 用户搜索视频序列 ID：对视频 ID 的 embedding 向量进行 mean pooling，得到视频搜索向量（search vector）。
• 用户地理特征和用户设备特征：均为一些离散特征，可以采用 embedding 方法或者直接采用 one-hot 方法（当离散维度较小时），得到用户的地理向量和设备向量
• Example Age：在推荐系统中很重要的一点是视频的新颖性，用户更倾向于观看新视频，但机器学习模型都是基于历史观看视频记录学习，所以在某种程度上，模型和业务是相悖的，所以文中构建了一个特征 example age，简单的可以理解为是视频的年龄，初始值设为 0，随着时间的增长，记录视频的年龄。加入之后效果十分明显，如图所示

• 人口属性特征：用于提供先验，使其对新用户也能做出合理的推荐。具体来说，对用户的地理区域和使用的设备进行 Embedding 并将特征进行拼接（concatenation）。

（2）MLP 层

使用常见的塔状设计，底层最宽，往上每层的神经元数目减半，直到 Softmax 输入层是 256 维（1024ReLU->512ReLU->256ReLU）。

（3）Softmax 层

深度神经网络的视频的 embedding 向量 和用户的 embedding 向量 ，召回任务预测用户 在 时刻观看的视频：

（4）输出层

输出层的维度和视频 ID 的 embeeding 向量维度一致，最终得到用户向量 。

将最后 softmax 层的输出矩阵的列向量当作 item embedding vector，而将 softmax 之前一层的值当作 user embedding vector

通过该网络结构的学习，最终可以得到所以视频的 embedding 向量 ，其维度为 pool_size ，其中 pool_size 为训练集视频资源的大小， 为 embedding 的维度。我们还可以得到所以用户的输出向量 ，其中每个用户向量的维度为 维，和视频的 embedding 向量维度一致。

3.5 召回优化

在线服务阶段，通过视频向量 和用户向量 进行相似度计算，为了满足时延要求，在进行实际的召回计算时采用的是最近邻查询的方式。对于每个用户向量 ，对视频库中的所有视频根据向量 做最近邻算法，得到 top-N 的视频作为召回结果。

3.6 样本选择和上下文选择

在有监督学习问题中，最重要的选择是 label 了，因为 label 决定了你做什么，决定了你的上限，而 feature 和 model 都是在逼近 label。我们的几个设计如下：

• 使用更广的数据源：不仅仅使用推荐场景的数据进行训练，其他场景比如搜索等的数据也要用到，这样也能为推荐场景提供一些 explore。
• 为每个用户生成固定数量训练样本：我们在实际中发现的一个 practical lessons，如果为每个用户固定样本数量上限，平等的对待每个用户，避免 loss 被少数 active 用户 domanate，能明显提升线上效果。
• 抛弃序列信息：我们在实现时尝试的是去掉序列信息，对过去观看视频/历史搜索 query 的 embedding 向量进行加权平均。这点其实违反直觉，可能原因是模型对负反馈没有很好的建模。
• 不对称的共同浏览（asymmetric co-watch）问题：所谓 asymmetric co-watch 值的是用户在浏览视频时候，往往都是序列式的，开始看一些比较流行的，逐渐找到细分的视频。下图所示图(a)是 hled-out 方式，利用 上下文信息 预估中间的一个视频；图(b)是 predicting next watch 的方式，则是利用 上文信息，预估下一次浏览的视频。我们发现图(b)的方式在线上 A/B test 中表现更佳。 而实际上，传统的协同过滤类的算法，都是隐含的采用图(a)的 held-out 方式，忽略了不对称的浏览模式。

四、Ranking

召回阶段已经给出了候选集，在排序阶段，其目的是对给定的小规模候选集进行精细化的排序。通常，排序阶段还涉及对多个不同召回源的视频进行有效集成，这给排序阶段增加了难度。

排序模型的网络结构 4.1 训练阶段

选择的基础模型是 DNN+weighted logistic regression。负样本是有曝光无点击的视频，正样本是有曝光有点击的视频，预测用户的观看时长。正样本记录了用户观看视频的时长，为了预测观看时长，专门设计了一个加权逻辑回归模型。（加入了观看时长这一衡量标准，也是为了用来解决噪声的，因为很多时候用户点击观看一个视频并不代表用户真的喜欢，满意这个内容）

这个模型是基于交叉熵损失函数的逻辑回归模型训练的。但是我们用观看时长对正样本做了加权，负样本都用单位权重（即不加权）。这样，我们通过逻辑回归学到的优势就是 ，其中 是样本数量， 是正样本数量， 是观看时长。假设正样本集很小，那么我们学到的优势就近似！ [公式] ， 是点击概率， 是观看时间的期望值。因为 很小，那么这个乘积就约等于！ [公式]。我们用指数函数 作为最终的激活函数来产生近似观看时长的估计值。

4.2 特征表示

我们的特征与分类和连续/序列特征的传统分类方法是不一样的，从两个维度对特征进行分析：

1. 取值数量：分为单值特征，比如当前待展示待打分的视频 ID；和多值特征，比如用户过去观看的 N 个视频 ID；
2. 特征描述内容：我们还根据它们描述项目的属性（“印象”）还是用户/上下文（“查询”）的属性来对特征进行分类。 每个请求计算一次查询特征，同时为每个已评分项目计算展现特征。

（1） 特征工程

虽然 DNN 隐含了特征工程，但是作者还是做了很多特征工程（个人认为，这说明网络模型并不是很适合这个数据，或者说这个网络结构不像 CNN 那样高效）。最重要的三方面特征如下：

1. 用户历史行为：用户之前和那些 items 有过交互，或者和相似的 items 的交互；
2. 上此观看时间：自上次观看同 channel 视频的时间，原理类似“注意力机制；
3. 之前视频已经被曝光给该用户的次数：如果一个视频之前展示过，用户没有观看，那么用户在下次展示的时候依旧不会观看的概率比较大，其原理类似“exploration”。

（2）离散特征 Embedding

和候选集生成一样生成，我们使用 embedding 来将稀疏离散特征映射到适合于神经网络的稠密矩阵形式。每个唯一的视频 ID 都对应一个单独学习出来的 embedding，它的维度大小和整个视频集 的 ID 个数的对数呈正比增加，即 log(unique(values))。这些视频是通过在训练之前扫描一次数据建立的简单查找表。 对视频集按照 ID 在点击展现中出现的频率进行倒序排列，仅保留频率最高的 topN 个 ID，其他的 ID 就被从视频集中去掉了。不在视频集中的值，简单的被 embedding 成值为 0 的向量。像在候选集生成阶段一样，多值离散特征映射成 embedding 之后，在输入网络之前需要做一下加和平均。

重要的是，离散特征对应的 ID 一样的时候，他们的底层 embedding 也是共享的。比如存在一个全局的 embedding 对应很多不同的特征（曝光的视频 ID，用户最后一次浏览的视频 ID，推荐系统的种子视频 ID 等等）。embedding 虽然是共享的，但是每个特征在训练的时候是单独输入到网络的，以便上层网络可以学习到每个特征的特殊表示。embedding 共享对于提升泛化能力、加速训练、减小内存占用是非常重要的。绝大多数参数模型是在这种高维 embedding 中的，例如，100 万个 ID 映射成 32 维的空间，其参数是完全连接的 2048 个单元宽网络参数的 7 倍多。

（3）连续特征归一化

神经网络对其输入的缩放和分布非常敏感，而诸如融合了决策树的模型对于各个特征的缩放是不会受什么影响的。我们发现连续特征的正确归一化对于收敛是至关重要的。一个符合 分布的特征 ，等价转化成！ [公式] ，用微积分使其均匀的分布在[0,1）区间上。在训练之前，扫描一次数据，用线性插值的方法，基于特征值的分位数近似的计算出该积分。

除了输入归一化的特征之外，我们还输入归一化特征！ [公式] 的平方、 的平方根，特