0%

推荐算法整理

发表于 更新于 分类于

推荐系统整体架构图

基于内容的推荐

基于内容的推荐是基础的推荐策略。如果你浏览或购买过某种类型的内容，则给你推荐这种类型下的其他内容。

以电影推荐为例。比如你之前看过《盗梦空间》，则系统会关联数据库中盗梦空间的信息。系统会推荐克里斯托弗 · 诺兰导演的其他作品，比如《致命魔术》；系统会推荐主演里昂纳多的其他作品，比如《第十一小时》。

如果这个电影系统的数据被很好地分类，那么推荐系统也会给用户推荐这个分类下的其他作品。盗梦空间如果被归为科幻作品，那么可能会推荐其他科幻作品，比如《星际迷航》。

基于内容的推荐好处在于易于理解，但是坏处是推荐方式比较依赖于完整的内容知识库的建立。如果内容格式化比较差，那么基于内容的推荐就无法实行。同时如果用户留下的数据比较少，则推荐效果很差，因为无法扩展。

基于标签的推荐

标签系统相对于之前的用户维度和产品维度的推荐，从结构上讲，其实更易于理解一些，也更容易直接干预结果一些。关于 tag 和分类，基本上是互联网有信息架构以来就有的经典设计结构。内容有标签，用户也会因为用户行为被打上标签。通过标签去关联内容。

需要计算用户 u 对物品 i 的兴趣，公式如下（可以和基于物品的协同过滤仔细对比）：

这里 N(u.,i) 表示用户 u 和物品 i 共有的标签，wuk 使用用户 u 和标签 k 的关联度，rki 表示标签 k 和物品 i 的关联性分数，示例如下：

标签查找的方法这里有很大可以发挥的空间，比如，通过知识库进行处理，或者语义分析处理。而对于一些设计之初就有标签概念的网站， 就比较容易，比如豆瓣和知乎。对于知乎而言，公共编辑的标签是天然的标签内容，对于知乎的用户而言，浏览回答关注等行为则是天然的用户标签素材。

基于协同过滤的推荐

协同过滤算法(collaborative filtering, CF) ,是一种基于类别的推荐算法。其实可以用一句谚语来解释协同过滤算法:物以类聚,人以群分。协同过滤最核心的理念就是找出爱好相同的人或者属性相似的物。这里有一个潜在设定就是,爱好相同的人他们对特定产品的偏好性是近似的。这样的场景在我们的生活中也有很多体现,例如两个人 A 和 B,平时都喜欢吃相似口味的菜,突然餐厅今天出了一道新的菜品, A 觉得这道新菜的味道不错,那么 B 喜欢这道菜的概率一定也很大,因为 A 和 B 在平日里都有相似的饮食偏好。

基本架构图：

  1. 基于内容的协同过滤 (ItemCF）ICF (item based)

协同过滤（Collaborative Filtering）与传统的基于内容过滤直接分析内容进行推荐不同，协同过滤会分析系统已有数据，并结合用户表现的数据，对该指定用户对此信息的喜好程度预测。

基于内容的协同过滤（item-based CF），通过用户对不同内容的评分来评测内容之间的相似性，基于内容之间的相似性做出推荐；最典型的例子是著名的 “啤酒加尿布”，就是通过分析知道啤酒和尿布经常被美国爸爸们一起购买，于是在尿布边上推荐啤酒，增加了啤酒销量。

需要计算用户 u 对物品 j 的兴趣，公式如下：

这里 N(u) 表示用户有关联的商品的集合，wji 表示物品 j 和 i 的相似度，rui 表示用户 u 对物品 i 的打分，示例如下：

这里还有两个问题没有仔细描述，如何打分，如何计算相似度。

打分的话需要根据业务计算，如果有打分系统最好，没有打分系统，则需要根据用户对这个物品的行为得到一个分数。

计算相似度除了之前我们提到的余弦公式，还可以根据其他的业务数据。比如对于网易云音乐而言，两首歌越多的被加入两个歌单，可以认为两首歌越相似。对于亚马逊而言，两个商品越多的被同时购买，则认为两个商品相似。这里其实是需要根据产品的具体情况进行调整。

  • 思想：

    给用户推荐和他之前喜欢的物品相似的物品。

  • 推荐步骤：
  1. 计算物品的相似度。
  2. 根据物品的相似度和用户的历史行为给用户生成推荐列表。
  • 优缺点：

性能：适用于物品数明显小于用户数的场合, 如果物品很多 (网页), 计算物品相似度矩阵代价很大。
领域：长尾物品丰富, 用户个性化需求强烈的领域。
实时性：用户有新行为, 一定会导致推荐结果的实时变化。
冷启动：新用户只要对一个物品产生行为, 就可以给他推荐和该物品相关的其他物品。但没有办法在不离线更新物品相似度表的情况下将新物品推荐给用户。
推荐理由：利用用户的历史行为给用户做推荐解释, 可以令用户比较信服。

  1. 基于用户的协同过滤 （UserCF）UCF (user based)

基于用户的协同过滤（user-based CF），通过用户对不同内容的行为，来评测用户之间的相似性，基于用户之间的相似性做出推荐。这部分推荐本质上是给相似的用户推荐其他用户喜欢的内容，一句话概括就是：和你类似的人还喜欢下列内容。

需要计算用户 u 对物品 i 的兴趣，公式如下（可以和基于物品的协同过滤仔细对比）：

这里 N(i) 表示对物品 i 有过行为的用户集合，wuv 使用用户 u 和用户 v 的相似度，rvi 表示用户 v 对物品 i 的打分，示例如下：

同样的，这里计算相似度如果用到余弦公式，其实最主要的是选好维度。对于音乐而言，可能是每首歌都作为一个维度，对于电商而言，也可以是每个商品都是一个维度。当然，用一些可理解的用户标签作为维度也是可以的。

  • 思想：

    给用户推荐和他兴趣相似的其他用户喜欢的物品。

  • 推荐步骤：

    1.找到和目标用户兴趣相似的用户集合。 2.找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户。

  • 优缺点：

性能：适用于用户较少的场合, 如果用户很多, 计算用户相似度矩阵代价很大。
领域：时效性较强，社会性较强，用户个性化不太明显的领域。
实时性：用户有新行为，不一定造成推荐结果的立即变化。
冷启动：在新用户对很少的物品产生行为后, 不能立即对他进行个性化推荐, 因为用户相似度表是每隔一段时间离线计算的。
新物品上线后一段时间, 一旦有用户对物品产生行为, 就可以将新物品推荐给和对它产生行为的用户兴趣相似的其他用户。
推荐理由：很难提供令用户信服的推荐解释。

基于用户和物品画像的推荐






基于矩阵分解的推荐

网络中的信息量呈现指数式增长，随之带来了信息过载问题。推荐系统是大数据时代下应运而生的产物，目前已广泛应用于电商、社交、短视频等领域。本文将针对推荐系统中基于隐语义模型的矩阵分解技术来进行讨论。

目录

  1. 评分矩阵、奇异值分解与 Funk-SVD
  2. 随机梯度下降法
  3. 基于 Funk-SVD 的改进算法
  4. 因子分解机
  5. 与 DNN 的结合
  6. 矩阵分解的优缺点
  7. 总结
    参考文献
    作者简介
  1. 评分矩阵、奇异值分解与 Funk-SVD

对于一个推荐系统，其用户数据可以整理成一个 user-item 矩阵。矩阵中每一行代表一个用户，而每一列则代表一个物品。若用户对物品有过评分，则矩阵中处在用户对应的行与物品对应的列交叉的位置表示用户对物品的评分值。这个 user-item 矩阵被称为评分矩阵。

上图即为评分矩阵的一个例子。其中的？表示用户还没有对物品做出评价，而推荐系统最终的目标就是对于任意一个用户，预测出所有未评分物品的分值，并按分值从高到低的顺序将对应的物品推荐给用户。

说到矩阵分解技术，首先想到的往往是特征值分解（eigendecomposition）与奇异值分解（Singular value decomposition，SVD）。

对于特征值分解，由于其只能作用于方阵，因此并不适合分解评分矩阵这个场景。

而对于奇异值分解，其具体描述为：假设矩阵 M 是一个 mn 的矩阵，则一定存在一个分解 ，其中 U 是 mm 的正交矩阵，V 是 nn 的正交矩阵，Σ 是 mn 的对角阵，可以说是完美契合分解评分矩阵这个需求。其中，对角阵 Σ 还有一个特殊的性质，它的所有元素都非负，且依次减小。这个减小也特别快，在很多情况下，前 10% 的和就占了全部元素之和的 99% 以上，这就是说我们可以使用最大的 k 个值和对应大小的 U、V 矩阵来近似描述原始的评分矩阵。

于是我们马上能得到一个解决方案：对原始评分矩阵 M 做奇异值分解，得到 U、V 及 Σ，取 Σ 中较大的 k 类作为隐含特征，则此时 M(mn) 被分解成 U(mk) Σ(kk)V(kn)，接下来就可以直接使用矩阵乘法来完成对原始评分矩阵的填充。但是实际上，这种方法存在一个致命的缺陷——奇异值分解要求矩阵是稠密的。也就是说 SVD 不允许待分解矩阵中存在空白的部分，这一开始就与我们的问题所冲突了。

当然，也可以想办法对缺失值先进行简单的填充，例如使用全局平均值。然而，即使有了补全策略，在实际应用场景下，user 和 item 的数目往往是成千上万的，面对这样的规模传统 SVD 算法 O(n^3) 的时间复杂度显然是吃不消的。因此，直接使用传统 SVD 算法并不是一个好的选择。（达观数据 周颢钰）

既然传统 SVD 在实际应用场景中面临着稀疏性问题和效率问题，那么有没有办法避开稀疏问题，同时提高运算效率呢？

实际上早在 06 年，Simon Funk 就提出了 Funk-SVD 算法，其主要思路是将原始评分矩阵 M（mn）分解成两个矩阵 P（mk）和 Q（k*n），同时仅考察原始评分矩阵中有评分的项分解结果是否准确，而判别标准则是均方差。

即对于矩阵 M(mn)，我们想办法将其分解为 P(mk)、Q(k*n)，此时对于原始矩阵中有评分的位置 MUI 来说，其在分解后矩阵中对应的值就是

那么对于整个评分矩阵而言，总的损失就是

只要我们能想办法最小化上面的损失 SSE，就能以最小的扰动完成对原始评分矩阵的分解，在这之后只需要用计算 M’ 的方式来完成对原始评分矩阵的填充即可。（达观数据 周颢钰）

这种方法被称之为隐语义模型（Latent factor model，LFM），其算法意义层面的解释为通过隐含特征（latent factor）将 user 兴趣与 item 特征联系起来。

对于原始评分矩阵 R，我们假定一共有三类隐含特征，于是将矩阵 R（34）分解成用户特征矩阵 P（33）与物品特征矩阵 Q（3*4）。考察 user1 对 item1 的评分，可以认为 user1 对三类隐含特征 class1、class2、class3 的感兴趣程度分别为 P11、P12、P13，而这三类隐含特征与 item1 相关程度则分别为 Q11、Q21、Q31。

回到上面的式子

可以发现用户 U 对物品 I 最终的评分就是由各个隐含特征维度下 U 对 I 感兴趣程度的和，这里 U 对 I 的感兴趣程度则是由 U 对当前隐含特征的感兴趣程度乘上 I 与当前隐含特征相关程度来表示的。

于是，现在的问题就变成了如何求出使得 SSE 最小的矩阵 P 和 Q。

  1. 随机梯度下降法

在求解上文中提到的这类无约束最优化问题时，梯度下降法（Gradient Descent）是最常采用的方法之一，其核心思想非常简单，沿梯度下降的方向逐步迭代。梯度是一个向量，表示的是一个函数在该点处沿梯度的方向变化最快，变化率最大，而梯度下降的方向就是指的负梯度方向。

根据梯度下降法的定义，其迭代最终必然会终止于一阶导数（对于多元函数来说则是一阶偏导数）为零的点，即驻点。对于可导函数来说，其极值点一定是驻点，而驻点并不一定是极值点，还可能是鞍点。另一方面，极值点也不一定是最值点。下面举几个简单的例子。

上图为函数 。从图中可以看出，函数唯一的驻点 （0，0）为其最小值点。

上图为函数 。其一阶导数为 ，从而可知其同样有唯一驻点（0，0）。从图中可以看出，函数并没有极值点。

上图为函数 。从图像中可以看出，函数一共有三个驻点，包括两个极小值点和一个极大值点，其中位于最左边的极小值点是函数的最小值点。

上图为函数 。其中点 （0，0，0）为其若干个鞍点中的一个。

从上面几幅函数图像中可以看出梯度下降法在求解最小值时具有一定的局限性，用一句话概括就是，目标函数必须是凸函数。关于凸函数的判定，对于一元函数来说，一般是求二阶导数，若其二阶导数非负，就称之为凸函数。对于多元函数来说判定方法类似，只是从判断一元函数的单个二阶导数是否非负，变成了判断所有变量的二阶偏导数构成的黑塞矩阵（Hessian Matrix）是否为半正定矩阵。判断一个矩阵是否半正定可以判断所有特征值是否非负，或者判断所有主子式是否非负。

回到上面 funk-svd 的最优化问题上来。经过一番紧张刺激的计算之后，可以很遗憾地发现，我们最终的目标函数是非凸的。这就意味着单纯使用梯度下降法可能会找到极大值、极小值或者鞍点。这三类点的稳定性按从小到大排列依次是极大值、鞍点、极小值，考虑实际运算中，浮点数运算都会有一定的误差，因此最终结果很大几率会落入极小值点，同时也有落入鞍点的概率，而对于极大值点，除非初始值就是极大值，否在几乎不可能到达极大值点。

为了从鞍点和极小值点中脱出，在梯度下降法的基础上衍生出了各式各样的改进算法，例如动态调整步长（即学习率），利用上一次结果的动量法，以及随机梯度下降法
（Stochastic Gradient Descent， SGD）等等。实际上，这些优化算法在当前最火热的深度学习中也占据着一席之地，例如 adagrad、RMSprop，Adam 等等。而本文则将主要介绍一下随机梯度下降法。（达观数据 周颢钰）

随机梯度下降法主要是用来解决求和形式的优化问题，与上面需要优化的目标函数一致。其思想也很简单，既然对于求和式中每一项求梯度很麻烦，那么干脆就随机选其中一项计算梯度当作总的梯度来使用好了。

具体应用到上文中的目标函数

SSE 是关于 P 和 Q 的多元函数，当随机选定 U 和 I 之后，需要枚举所有的 k，并且对

以及 求偏导数。整个式子中仅有 这一项与之相关，通过链式法则可知

在实际的运算中，为了 P 和 Q 中所有的值都能得到更新，一般是按照在线学习的方式选择评分矩阵中有分数的点对应的 U、I 来进行迭代。

值得一提的是，上面所说的各种优化都无法保证一定能找到最优解。有论文指出，单纯判断驻点是否是局部最优解就是一个 NPC 问题，但是也有论文指出 SGD 的解能大概率接近局部最优甚至全局最优。

另外，相比于利用了黑塞矩阵的牛顿迭代法，梯度下降法在方向上的选择也不是最优的。牛顿法相当于考虑了梯度的梯度，所以相对更快。而由于其线性逼近的特性，梯度下降法在极值点附近可能出现震荡，相比之下牛顿法就没有这个问题。但是在实际应用中，计算黑塞矩阵的代价是非常大的，在这里梯度下降法的优势就凸显出来了。因此，牛顿法往往应用于一些较为简单的模型，如逻辑回归。而对于稍微复杂一些的模型，梯度下降法及其各种进化版本则更受青睐。（达观数据 周颢钰）

  1. 基于 Funk-SVD 的改进算法

到这一步为止，我们已经能通过 SGD 找到一组分解方案了，然而对于填充矩阵的 FunkSVD 算法本身而言，目前这个形式是否过于简单了一些呢？

实际上，在 Funk-SVD 被提出之后，出现了一大批改进算法。本文将介绍其中某些经典的改进思路。

(1) 正则化

对于所有机器学习算法而言，过拟合一直是需要重视的一个问题，而加入正则化项则是防止过拟合的经典处理方法。对于上面的 Funk-SVD 算法而言，具体做法就是在损失函数后面加入一个 L2 正则项，即

其中，λ 为正则化系数，而整个求解过程依然可以使用随机梯度下降来完成。

(2) 偏置

考察式子

可以发现这个式子表明用户 U 对物品 I 的评分全部是由 U 和 I 之间的联系带来的，然而实际上，有很多性质是用户或者物品所独有的。比如某个用户非常严苛，不论对什么物品给出的分数都很低，这仅仅与用户自身有关。又比如某个物品非常精美，所有用户都会给出较高的分数，这也仅仅与物品自身有关。因此，只通过用户与物品之间的联系来预测评分是不合理的，同时也需要考虑到用户和物品自身的属性。于是，评分预测的公式也需要进行修正。不妨设整个评分矩阵的平均分为 σ，用户 U 和物品 I 的偏置分别为 和 ，那么此时的评分计算方法就变成了

同时，误差 E 除了由于 M‘计算方式带来的变化之外，也同样需要加入 U 和 I 偏置的正则项，因此最终的误差函数变成了

(3) 隐式反馈

对于实际的应用场景中，经常有这样一种情况：用户点击查看了某一个物品，但是最终没有给出评分。实际上，对于用户点击查看物品这个行为，排除误操作的情况，在其余的情况下可以认为用户被物品的描述，例如贴图或者文字描述等所吸引。这些信息我们称之为隐式反馈。事实上，一个推荐系统中有明确评分的数据是很少的，这类隐式数据才占了大头。

可以发现，在我们上面的算法当中，并没有运用到这部分数据。于是对于评分的方法，我们可以在显式兴趣 + 偏置的基础上再添加隐式兴趣，即

其中 N(U) 表示为用户 U 提供了隐式反馈的物品的集合。这就是 svd++ 算法。

此时的损失函数也同样需要加上隐式兴趣的正则项，即

(4) 对偶算法

在上面的 svd++ 中，我们是基于用户角度来考虑问题的，很明显我们同样可以基于物品的角度来考虑问题。具体来说就是

其中 N(I) 表示为物品 I 提供了隐式反馈的用户的集合。类似地，在损失函数中也需要加上隐式兴趣的正则项。

在实际运用中，可以将原始的 svd++ 得到的结果与对偶算法得到的结果进行融合，使得预测更加准确。然而相比起物品的数目，用户的数目往往是要高出几个量级的，因此对偶算法在储存空间和运算时间的开销上都将远高于原始的 svd++，如何在效率和准确度之间找到平衡也是一个需要思考的问题。（达观数据 周颢钰）

  1. 因子分解机

矩阵分解的思想除了直接应用在分解评分矩阵上之外，其思想也能用在其他地方，接下来介绍的因子分解机（Factorization Machine，FM）就是一个例子。

对于经典的逻辑回归算法，其 sigmoid 函数中的项实际上是一个线性回归

在这里我们认为各个特征之间是相互独立的，而事实上往往有些特征之间是相互关联、相互影响的。因此，就有必要想办法捕捉这些特征之间的相互影响。简单起见，先只捕捉二阶的关系，即特征之间两两之间的相互影响。具体反映到回归公式上，即为

然而在实际场景中，数据往往是非常稀疏的，这就导致模型很难学到后面的二阶权重。受到矩阵分解技术的启发，如果把所有的二阶特征按顺序整理成一个矩阵，那么对于这个矩阵我们可以想办法将其进行矩阵分解，从而将二阶权重表示成隐向量乘积的形式。此时，回归的式子就变成了

具体来说就是使用

来描述 ，对于 w 而言，其中可学习的项就对应了评分矩阵中有分值的项，而其他由于数据稀疏导致难以学习的项就相当于评分矩阵中的未评分项。这样一来，不仅解决了数据稀疏性带来的二阶权重学习问题，同时对于参数规模，也从 级别降到了 O(kn) 级别。

  1. 与 DNN 的结合

深度学习无疑是近几年来最热门的机器学习技术。注意到隐语义模型中，隐含特征与深度学习中的 embedding 实际上是一回事，那么是否有可能借助 DNN 来帮助我们完成矩阵分解的工作呢？

实际上，在 YouTube 的文章《Deep neural networks for YouTube recommendations》中，就已经有了相关技术的应用。

上图是 YouTube 初排模型的图示。具体的流程为首先通过 nlp 技术，如 word2vec，预训练出所有物品的向量 I 表示。然后对于每一条用户对物品的点击，将用户的历史点击、历史搜索、地理位置信息等信息经过各自的 embedding 操作，拼接起来作为输入，经过 MLP 训练后得到用户的向量表示 U，而最终则是通过 softmax 函数来校验 U*I 的结果是否准确。

相比于传统的矩阵分解算法，使用 DNN 能为模型带来非线性的部分，提高拟合能力。另一方面，还可以很方便地加入各式各样的特征，提高模型的准确度。

  1. 矩阵分解的优缺点

矩阵分解有如下优点：

  1. 能将高维的矩阵映射成两个低维矩阵的乘积，很好地解决了数据稀疏的问题；
  2. 具体实现和求解都很简洁，预测的精度也比较好；
  3. 模型的可扩展性也非常优秀，其基本思想也能广泛运用于各种场景中。

相对的，矩阵分解的缺点则有：

  1. 可解释性很差，其隐空间中的维度无法与现实中的概念对应起来；
  2. 训练速度慢，不过可以通过离线训练来弥补这个缺点；
  3. 实际推荐场景中往往只关心 topn 结果的准确性，此时考察全局的均方差显然是不准确的。

参考：
https://drivingc.com/p/5c7b26d24b0f2b6c1e4c6914
https://plushunter.github.io/2017/03/07/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97%EF%BC%8813%EF%BC%89%EF%BC%9A%E6%8E%A8%E8%8D%90%E7%B3%BB%E7%BB%9F%EF%BC%883%EF%BC%89%E2%80%94%E2%80%94%E7%9F%A9%E9%98%B5%E5%88%86%E8%A7%A3%E6%8A%80%E6%9C%AF/

基于 icf+als 矩阵分解+gbdt 的推荐

现在 recall 是 icf als 矩阵分解 rank 是 smart gbdt

可以先后验 ctr 后验 staytime 做 ab ，再先验 ctr (模型) 后验 staytime

基于 Word embedding + xgb 的推荐

基于 fm+lr 的推荐

基于 GBDT+LR 的推荐

基于 ItemToVector 的推荐

基于 ffm+wide&deep ->deepfm 的推荐

迭代步骤

1、埋点数据

2、模型迭代
现在 recall 是 icf als 矩阵分解 rank 是 smart gbdt

比如典型的召回路有：基于用户兴趣标签的召回；基于协同过滤的召回；基于热点的召回；基于地域的召回；基于 Topic 的召回；基于命名实体的召回等等，除此外还有很多其它类型的召回路

排序升级为 XGB 排序

召回升级为 fm，用户特征存在 Redis，item 特征存在 faiss，向量之间做乘积
开发工具为 TF
作者张俊林

3、特征工程
那么特征交叉又该如何做呢？表征特征之间的关联，最直接的方法是构造组合特征。样本中特征之间的关联信息在 one-hot 编码和浅层模型（比如 LR、SVM）中是难以做到的。目前工业界主要有一下集中方法来表示特征交叉：

人工特征工程（数据分析 + 人工构造）
通过模型表示组合特征（深度学习 DSN，FM/FFM 等方法）

4、流式计算
基于 flink 的实时推荐