[转载：搜狐新闻推荐算法原理]
导读
在当前这个移动互联网时代，各种信息内容爆炸，面对海量数据，用户希望在有限的时间和空间内，找到自己感兴趣的内容，这就是推荐需要解决的问题。接下来主要讲解新闻推荐的算法原理。
01.新闻推荐算法架构
新闻算法的核心主要分为两个阶段：召回阶段（retrieval）和排序阶段（ranking）。之所以分为两个阶段，主要是从性能考虑。召回阶段面临的是百万级别甚至千万级别的文章，单篇文章的性能开销必须要小；而排序阶段的算法则非常消耗资源，不可能对所有文章都算一遍，也没有必要这样做，因为一般来说通不过召回粗选的文章，大部分在排序阶段排名也会很低。
召回阶段，根据用户的历史行为和短期行为，分析用户的兴趣偏好，从千万级的文章库中挑选出一个小的候选集（通常几百到几千篇文章），这些候选集都是用户感兴趣的内容集合。
排序阶段，在召回集的基础上进行更加精准的个性化计算，给每篇文章进行精确打分，这个分值就是文章与用户的个性化匹配分值，利用该分值进行排序，进而从几千篇文章中选出用户最感兴趣的几篇或者几十篇少量高质量内容。
推荐算法的核心部分两个阶段组成如图所示，大致包含：
（1）用户画像：包含用户的人口属性（性别，学历等）、历史行为、短期行为、兴趣内容和个人偏好等多个维度的数据，是给用户做个性化推荐的基础。
（2）特征工程：包含文章的类别属性、主题属性、关键词信息、内容分析、人群偏好和统计特征等比较全面的描述和度量，是新闻内容和质量分析的基础，也是做好用户与文章个性化匹配的基础。
（3）召回算法：包含多个通道的召回模型，例如协同过滤（itemcf、usercf等）、主题模型、内容召回、矩阵分解等。
（4）排序算法：对多个通道召回的内容进行统一的打分排序，选出最优的少量结果，这里常用的模型有lr、gbdt、fm以及DNN的一些模型。
除此之外，推荐系统一般还要有一个rerank的过程，要兼顾推荐结果的多样性、新鲜度、惊喜度以及部分的人工的产品逻辑等多个维度，更能够满足用户个性化的需求。
02.新闻推荐算法原理
召回最重要的要求是性能要好，一般不超过30ms。
召回策略的种类有很多，我们主要用的是倒排的思路：离线维护一个倒排索引，这个倒排的key可以是分类，topic，关键词，媒体来源等文章属性；也可以是协同过滤计算的结果，排序时需要考虑点击率、时效性、相关性等。线上召回可以迅速从倒排中根据用户的画像标签对内容进行截断召回，高效地从很大的内容库中筛选和用户比较匹配的一小部分内容。
基于内容的召回
基于内容的召回（content-base），是根据文章内容本身的语义特征或者字面特征做召回，这类特征通常有关键词，topic，分类，媒体来源等。
基于协同过滤召回
协同过滤算法（CF）的原理是汇总所有用户（user）和文章（item）的行为，利用集体智慧进行推荐。主要分为两大类，User-CF和Item-CF。
User-CF，就像朋友推荐，比如通过用户点击的文章进行分析，发现用户A和用户B很相似，就可以把A点击文章而用户B还未点击的，推荐给用户B，这里重点是找出用户的朋友，即相似用户。
Item-CF，分析每篇文章的点击行为，可以得出所有文章之间的相似度，找出与当前点击的文章最相似的N篇文章推荐给用户。
协同过滤通常能推荐出很多有惊喜的结果，而且只依赖用户行为不需要对内容做深入分析；但是这种推荐需要大量的用户行为数据并且很难给出合理的解释。
基于矩阵分解召回
协同过滤的核心是相似度计算，比较依赖用户行为，而在实际应用中，一方面，用户行为矩阵比较稀疏，计算结果不稳定，另一方面如果用户u没有对文章i的相似度得分，那么这个协同结果差异会很大。而这些问题在矩阵分解中可以得到很好的解决。
矩阵分解，直观上就是把稀疏的用户评分矩阵近似的分解成两个小矩阵的乘积，在推荐计算时不再使用大矩阵而是使用分解得到的两个小矩阵。
常用的矩阵分解算法有SVD、SVD++、timeSVD++以及Spark自带的SparkALS等，学习过程基本相同，大致如下：
（1）准备好用户文章评分矩阵，点击曝光数据模拟评分（1、0）
（2）随机初始化来构造矩阵U和V
（3）用U和V计算预测后的分数，然后计算与实际分数的误差
（4）按照梯度下降方式更新U和V的元素值
（5）重复步骤3和4直到到达停止条件
最后会生成user_weight user_vector和doc_weight doc_vector的模型文件，在召回计算的时候使用user向量矩阵和doc向量矩阵做内积，排序取topN。
矩阵分解相比CF预测精度更高，但其缺点也很明显，推荐结果的解释性不好而且受限于矩阵维度。
基于热点召回
热点召回一般用来做兜底，但是热点不能单纯的按ctr排序，因为文章的曝光不同，ctr不具有可比性，通常的做法有威尔逊置信区间、贝叶斯平滑、时间衰减等。
我们把推荐问题建模成一个“超大规模分类”问题，即在时刻T和上下文C的情况下，为用户U在文章库V中精准的预测出文章I的类别，这里召回已经帮我们解决了超大规模的问题，而排序的核心就是拟合一个用户对内容满意度的函数y=Fun(U, I, C)，这个函数需要输入的就是这三个维度的特征：用户信息U、文章信息I和上下文信息C。
特征
特征对于排序模型来说非常重要，好的特征能够提升模型的性能，更能帮我们理解用户数据、文章内容数据的特点，这对进一步改善模型、算法都有着重要作用。我们常用的几类推荐特征：
相关性特征，可以理解为语义特征或者字面特征，用于描述用户和内容是否匹配。比较常见的匹配有；分类匹配、topic匹配、关键词匹配、媒体来源匹配等。
上下文特征，包括用户的位置，时间，移动设备，联网状态等，这些就是bias特征，也能由此构建一些匹配特征。
热度特征，包括文章的ctr、分类热度、topic热度等，这种内容热度信息不仅在推荐特征中起着重要作用，而且在用户冷启动的时候也非常有效。
挖掘类特征，例如协同特征，聚类特征等，这类特征并非考虑用户的历史，而是根据用户点击行为分析不同用户的相似性，比如点击相似、兴趣相似或者属于同一个类簇，从而获取到新颖的结果，扩展了模型的探索能力，也能有效的解决越推越窄的问题。
模型
推荐系统中比较典型的几种模型，也是近几年推荐算法模型发展的趋势：
LR
LR是线性分类模型，要求输入线性独立特征。
LR可以视作单层节点的“DNN” ，是一种宽而不深的结构，所有的特征直接作用在最后的结果上。模型优点是简单、可控性好、可解释性强，但是效果的好坏直接取决于特征工程的程度，需要非常精细的连续型、离散型等特征以及对应的特征组合，而这种特征组合是需要人工进行转换的，十分耗费人力并且随着特征的增加，这种组合复杂度越来越高，增加特征变得异常困难。
GBDT
GBDT是一种迭代的决策树算法，它由多棵决策树组成，所有的树结论累加起来作为最终答案。它能自动发现多种有区分性的特征以及特征组合，并省去了复杂特征预处理逻辑。之前Facebook实现了GBDT+LR的模型，相比单纯的LR或者GBDT都有不错的提升。
GBDT+LR模型虽然特征泛化能力良好，但是记忆能力比较差，通常需要增加高维特征来增强推荐的记忆能力，包括UserID、各种标签等特征。
FM & FFM
由于GBDT是不支持高维稀疏特征的，如果将高维特征加到LR中，一方面需要人工组合高维特征，这种复杂度、难度以及准确度是显而易见的，另一方面模型维度和计算复杂度都是剧烈增加。所以后面有了FM&FFM模型。FM可以看作是带特征交叉的LR：
相比一般的线性模型，FM考虑了特征间的关联，在多项式模型中，特征xi和xj的组合用xixj表示，这一部分就是FM模型多出来的特征组合，从NN的角度考虑：
FM模型覆盖了LR的宽模型结构，同时也引入了交叉特征，增加了模型的非线性和泛化能力，提升了模型容量，能够捕捉更多额外的信息，对于像新闻推荐这样复杂的场景能有更好的预测能力。
FFM模型中引入域（Field）的概念，把n个特征归属到f个field里，得到nf个隐向量的二次项：
所以FFM可以看作是带多个域（Field）的FM，FM是只有一个域（Field）的FFM，其中，fj是第j个特征所属的field。如果隐向量的长度为k，那么FFM的二次参数有nfk个，远多于FM的nk个。另外，由于隐向量与field相关，FFM二次项是不能简化的，其预测复杂度是O(kn^2)。因此，性能往往是制约FFM大规模应用的因素，如果规模不是很大，而且特征比较稀疏的场景下，FFM有很好的效果。
在实际应用中，FM比FFM更广泛一些，是对性能和效果的一些折中，比较常用的像dmlc下的FM，支持全量和增量的分布式计算，比较适合新闻推荐中场景和兴趣多变而且很多稀疏特征的情况。
DNN
随着推荐场景的多样化，复杂度也随之增加，上面提到的几个浅层网络模型对于更多的隐层信息无法捕获以及更多的稀疏特征表达不够充分，DNN的方式逐步成为一种趋势。但是单纯的DNN模型对ctr的提升并不一定会有明显的提升，而且单一的DNN本身也有一些瓶颈。如果用户是一个非活跃用户时，由于自身于item之间的交互很少，根据用户行为得到的特征向量也会异常稀疏，而DNN在处理这类问题时会过度泛化，导致推荐结果与用户相关较差。为了更好的解决这类问题，通常会用DNN+具有记忆能力的模型，相互补充。
wide & deep
该模型是谷歌在2016年发布的用于分类和回归的模型，并成功应用于google play的应用推荐中。随后该模型速度被普及开来，尤其在新闻推荐中，能取得不错的效果。wide & deep模型的核心思想是结合线性模型的记忆能力和DNN模型的泛化能力，在训练中同时优化2个模型的参数，达到整体模型的预测能力最优，从而避免了线性模型无法学习训练集中未出现的特征组合以及神经网络过度泛化的问题
wide端对应的线性模型，输入特征可以是连续特征，也可以是稀疏的离散特征，离散特征之间进行进行交叉后可以构成更高维的特征，通过L1正则化能够很快收敛到有效的特征组合中。
deep端对应的是DNN模型，每个特征对应一个低维的稠密向量，我们称之为特征的embedding，DNN能够通过反向传播调整隐藏层的权重，并且更新特征的embedding
在实际的新闻推荐场景中，wide model侧主要包含文章分类id、topic id、曝光位置以及其他部分离散特征，主要为了提高模型的记忆能力；deep model侧主要包含离散特征和部分连续特征，例如UserID、DocId、用户位置、分类ID、关键词ID以及各种统计类特征离散化结果，这些特征通常需要embedding向量然后拼接进行信息融合。
总结
本文以新闻推荐为例，第一部分讲解了推荐算法的架构，主要包含召回和排序两个阶段；第二部分重点介绍了召回算法以及常用排序模型的原理和实现。在新闻推荐领域，排序模型逐步趋向DNN，但是单纯的模型更替意义不大，需要在特征工程、模型架构、多样性、冷启动、多策略召回以及多目标学习中做更多的尝试，更好地解决用户的个性化需求才是我们技术的立身之本。
