推荐算法三视角: 矩阵, 图, 时间线

张小磊

发布于 2020-04-20 15:43:16

6740

发布于 2020-04-20 15:43:16

文章被收录于专栏：机器学习与推荐算法机器学习与推荐算法

作者：九老师来源：知乎 https://www.zhihu.com/people/nphard-79

关于推荐系统，如果在忘掉所有的公式和代码，忘记所有的语言描述，脑海里就剩下几张图景，会是什么？一张二维表格，一个拓扑图，一条时间线。这三幅图景，是我看待推荐算法的三种视角。

视角一：矩阵视角

在脑中想象一个二维的表格，每一行代表一个用户，每一列代表一个物品，表格里的每一个点代表用户对物品的操作，这个操作可以是评分，点击，点赞。其中，有些格子记录了行为，有些格子是空的。到这里，我们就建立了基本的矩阵视角，推荐问题转化成了如何补上那些空格子。

用户对物品的评分等于相似用户对该物品评分的加权平均值，这就是user-base的协同过滤了。换一个方向，用户对物品的评分等于该用户对其他物品的评分按物品相似加权平均值，这就是item-base的协同过滤。度量用户之间的相似度，把矩阵的一行——对物品的评分向量作为该用户的表示向量，那么用户之间可以计算向量的距离，可以选择任何距离公式，如余弦距离，皮尔森距离。对于物品之间的相似度，换一个方向即可。

对于任何两个物品，可以计算它们的评分差值。具体来说，两个物品有一批共同的历史评分用户，也就是矩阵里两列有交集的行，每一行可以计算一个差值，将差值平均起来，作为两个物品的距离。和上面的距离不同的，这个差值可以想象成物理中的位移，带着符号的。推荐时，某用户对于某个物品的评分，等于某用户对其他物品评分加上这个位移，再进行平均得到的平均评分。和上面的item-base一样的，都是列向量计算相似度，只不过相似度由距离变成了位移。这就是著名的Slope-One算法。

物品直接的相似度，除了上面的启发式算法，能不能通过数据本身学习所得？这就诞生了SLIM(Sparse Linear Methods)方法。矩阵

是

评分矩阵，要学习一个

维的物品相似的矩阵

。

的每一行是用户的历史评分，

的每一列是每一个物品和该列对应物品的相似度，计算内积即为该用户对该列物品的评分，通过梯度下降训练来拟合真实评分。其中，

非负体现了相似度的物理意义；对角线限制为0避免对角线全都学习到1完美过拟合；添加L1正则产生稀疏的

，使得结果在大规模物品集上可用;

的每一列的学习都可以看作一个线性回归模型，训练时可以彼此相互独立，因而可以分布式学习。

在矩阵视角下，很自然可以进行矩阵分解。SVD矩阵分解将n个用户m个物品的大矩阵分解成三个矩阵相乘，中间的矩阵越靠近左上角的特征值越大，代表矩阵分解的主要成分，也就是说保留左上角的

维矩阵D，其余的都置为零，将原来的等于变为约等于。将蓝色和红色的矩阵合并，得到一个

维的矩阵，每一个行代表一个

维的用户向量，对于黄色矩阵保留其前

行（后面的不影响计算了），每一列代表一个物品向量，用户和物品向量的内积也就是矩阵相乘后对应矩阵的值，也就是空缺处的评分，将向量索引起来就可以推荐了。

要使用SVD分解，待分解矩阵要是稠密的，稀疏的评分矩阵要按照统计学方法填充，如填充均值。另外，SVD过拟合现象严重，泛化误差太大。在2006年Netflix Prize的百万推荐大奖赛上， Simon Funk 在博客公开FunkSVD算法。直接将评分矩阵分解成两个矩阵相乘，

维度的用户矩阵，每一行是用户的隐式向量表示，

维的物品矩阵，每一列是物品的隐式向量表示，用户和物品向量的内积即为预估的评分。那如何进行分解呢？随机初始化矩阵，使用均方误差作为loss，梯度下降进行学习。这个过程中还可以加入正则项，降低泛化误差。由FunkSVD开始，基于Matrix factor（MF）的方法大放异彩。

在MF的基础上，考虑推荐中的side information，如用户的年龄性别，物品的类目价格。用户和物品自身或属性称作一个field，field之间可以两两进行矩阵分解，这个被称作二阶项，类似BiasSVD考虑每一个field都有一个bias，这个被称作一阶项，再加上一个全局的bias项。这就是著名的Factorization Machines（FM）。

如果把上面介绍的SLIM和MF解结合起来，将物品的相似度矩阵

分解成

两个低维矩阵，用户对某物品的评分，等于他过去评分过的物品在

中对应的向量和

中该物品向量内积的和，这就是FISM算法。相比SLIM的稀疏处理，变为分解降维。最后再附上一张图，说明MF，SLIM和FISM之间的关系。

视角二：图视角

把用户和物品看作顶点，用户的评分在用户和物品之间建立起边，就得到了一个二部图；在二部图的基础上添加更多的顶点和边，形成一个更为复杂的图，辅助二部图的计算。在图的视角下，推荐问题转化成了在图上寻找高效的链接模式。

我们认为在同一个用户的历史行为中，那么两个物品之间有一条边，现在要计算两个物品之间的相似度，最朴素的思想就是数一数他们之间有多少条边。考虑每一条边权重不一样，边是通过用户建立的，用户的点击的物品越多，对应边的权重就越小。这就是Adamic/Adar算法的思想。

阿里著名的协同过滤推荐算法swing，寻找图中更加稳固的形状，共同评分过两个物品的用户集合中，每两个用户和这个两个物品形成了一个四边形(下图红边为一个swing结构)，统计有多少个这样的结构，每一个结构的权重是不同的，这个结构里两个用户共同评分过的物品的数量越多权重就越小。

从用户和物品的二部图出发进行构图，再结合隐因子模型(Latent Factor Model)，就进入了Graph-Embedding的领域。DeepWalk算法在图上随机游走深度优先遍历得到序列，然后和word2vec类似地使用Skip-Gram（A和B序列中相邻，用A的embedding作为特征最大化B的选中概率）进行训练。Node2Vec算法在DeepWalk的基础上，考虑随机游走的方式，引入深度优先和广度优先的权衡，能够得到更好的更灵活的顶点隐式表示。LINE算法考虑顶点的二阶相似，两个顶点有边为一阶相似，两个顶点有共同的邻居顶点为二阶相似，它虽不做随机游走，但可以看作是广度优先的采样。Graph-Embedding取得了顶点的embedding，计算相似度可以得到用户物品距离，物品物品距离，用于推荐。

GCN（图卷积）接收拓扑图作为网络输入，可以计算每一个顶点更好的表示，相比graph-embedding可以有监督地为推荐目标而训练。但GCN在运算时，每一层都要输入整个图，在推荐系统里，物品和用户都可以是百万级别以上，实际中无法使用。GraphSAGE通过RandomWalk采样，解决了这个问题，用在推荐领域就是PinSage算法。从某顶点出发，深度优先走k步，得到多个子图，组成一个batch进行训练，。然后按照采样的反方向做前向传播，这就是一个k层的图网络，下图是一个k为2的例子。

在用户和物品的二部图基础上，用户和用户根据社会关系建立起边来，这就是社会化推荐。

在用户和物品的二部图基础上，增加物品的属性作为顶点，建立新的边，就得到了一个异质信息网络。比如一个电影推荐系统，除了用户和电影外，还有导演，演员，电影类型，导演拍摄电影，电影属于某种类型，演员出演电影，导演与演员合作，诸如此类就能建立很多边。其中一类推荐算法叫做meta-path，通过专家经验人工挑选出一些图中路径，如用户->演员->电影，用户->导演->电影，这样的路径称之为meta-path，计算每一条meta-path的权重，将用户和物品间的所有meta-path联合计算评分。

视角三：时间线

把用户对物品的行为想象成一条时间线，我们已知当前时刻前用户的物品行为序列，推荐问题被转化成了预测下一个时刻用户发生行为的物品。

假设序列中下一个物品只与上一个物品有关，可以使用马尔科夫模型MC（Markov Chains），序列中相邻的物品间进行矩阵分解。结合上文提到的用户和物品间矩阵分解MF，用户，当前行为物品和下一个物品三者之间两两进行矩阵分解，将三个值加起来拟合评分，就得到了FPMC（Factorizing Personalized Markov Chains）算法。

Translation-based推荐在序列建模中引入Metric Learning（把行为关系和高维空间距离映射起来），用户

，当前行为物品

，下一个物品

三者向量化表示，训练使得它们满足

，推荐时只需拿到用户历史行为的物品向量加上用户向量得到下一个物品向量，然后在推荐集合中KNN寻找即可完成推荐。

以前模型的输入形式有限，人们通过特征处理将数据组织成模型可以接受的形式；随着深度学习的发展，数据越来越倾向于保存其原有的形式，人们通过模型设计来学习有效的模式。在时间线的视角下，直接用深度模型结构建模序列，预测下一物品，形成了一个可以发挥想象力和燃烧算力的领域——Sequential/Session-base推荐。在2016年的时候，RNN是处理序列问题的标配，它从NLP领域走来，诞生了GRU4Rec算法。受到NLP领域Char-CNN启发，CNN的结构也逐渐用于建模序列结构，Attention机制大火之后，RNN+Attention，CNN+Attention，RNN+CNN+Attention被枚举了一遍。随着google老师的BERT取得NLP领域巨大成就，Self-Attention以及多层的Transformer结构开始成为序列建模的常规配置。最近的文章里，图神经网络(GNN),Memory networks,变分自编码器(VAE)也成为了序列推荐领域的深度乐高积木。

在CTR预估领域，越来越多的模型直接将用户历史行为序列按照时间顺序排列，使用深度模型结构直接建模。

总结

其实如果要细数，还有一个视角叫做高维空间视角。用户和物品都是一个高维度空间里的点，空间里点之间的距离越近，代表着物品和物品越相关，用户对物品越偏好，推荐问题转化成了如何将用户和物品嵌入到高维空间里。典型的主题如Metric Learning。不过这个视角的正交性不好，深度学习席卷推荐系统后，embedding是个太常见的思路，前面很多的方法也都是最终把问题转化成了高维空间嵌入，如graph-embedding，Transition-base推荐。为了避免归类上的纠结；再加上任何一个深度网络作为Encoder把用户和物品embedding，都可以归在这个视角，没有那么多令人印象深刻的典型方法，就不做单独梳理了。

To My Best Knowledge，我把自己认为推荐系统里经典且令人印象深刻的方法归在三种视角中——矩阵，图，时间线。本来想谈谈认识的，写着写着写多了，变成了一篇梳理文章。如果对你从偏算法的角度理解推荐系统有所助益，我就很开心了。后面有所学习所得，也会持续更到这篇文章，感兴趣的收藏关注一下吧！