推荐系统学习入门指导

关于推荐系统，如果忘掉所有的公式和代码，忘记所有的语言描述，脑海里就剩下几张图景，会是什么？

一张二维表格，一个拓扑图，一条时间线。

这三幅图景，是我看待推荐算法的三种视角，分享给大家便于理解。

想要学习推荐系统，除了具体的书籍和教程，更重要的是，要建立起自己的知识架构，慢慢地，往上填充具体的知识点，从而系统化地掌握某一块知识。

视角一：矩阵视角

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

用户对物品的评分等于相似用户对该物品评分的加权平均值，这就是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）算法。