新知一下
海量新知
5 9 9 1 0 9 9

推荐算法三视角

机器学习AI算法工程 | 机器学习入门与实战 2019/12/09 12:06

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

新知达人, 推荐算法三视角

视角一:矩阵视角

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

新知达人, 推荐算法三视角

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

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

新知达人, 推荐算法三视角

新知达人, 推荐算法三视角

新知达人, 推荐算法三视角

新知达人, 推荐算法三视角

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

新知达人, 推荐算法三视角

视角二:图视角

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

新知达人, 推荐算法三视角

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

新知达人, 推荐算法三视角

以前模型的输入形式有限,人们通过特征处理将数据组织成模型可以接受的形式;随着深度学习的发展,数据越来越倾向于保存其原有的形式,人们通过模型设计来学习有效的模式。在时间线的视角下,直接用深度模型结构建模序列,预测下一物品,形成了一个可以发挥想象力和燃烧算力的领域—— 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,我把自己认为推荐系统里经典且令人印象深刻的方法归在三种视角中—— 矩阵 时间线 。如果对你从偏算法的角度理解推荐系统有所助益,我就很开心了。

原文地址 https://zhuanlan.zhihu.com/p/95350982

更多“算法”相关内容

更多“算法”相关内容

新知精选

更多新知精选