从Pinterest到阿里,再谈工业界的推荐系统

本文授权转载自公众号:硅谷程序汪

作者:王栋

不久前我曾写过一篇文章,“Pinterest推荐系统四年进化之路”,这些日子又看了别的推荐系统文章,顺便听了Related Pins团队马老师的讲座,对这个问题有了新的认识和大家分享。

这篇文章和技术相关,难免有理解不到位甚至错误的地方,还望各位朋友见谅并且指正。

在最下面我还提到了一篇阿里系的文章,对该文章有不少实践上的猜想和疑问,希望和了解的人多多交流。

Representation Learning

在讨论对Pinterest推荐系统新认识之前,我们先来看一个老问题Representation Learning on Network(网络表示学习)。

在图上有很多经典问题和应用,比方说在预测一个节点的类别,在人际关系网络中预测你的兴趣爱好,还有一类应用就是link prediction,可以通过link prediction对网络中的节点做推荐。

这时网络表示学习就派上用场了,人们通过分析网络节点,边,或者子图,对节点进行向量化,能够使复杂的网络信息变成结构化的多维特征,从而利用机器学习方法实现上面提到的一些应用。

2014年的时候受到Word2Vec解法Skip-gram的启发,人们开始把网络结构当做一个文档的集合,节点当做单词,然后从网络中通过随机游走产生句子,通过Word2Vec对节点向量化。这一思路先后在两篇文章中被详细介绍,DeepWalk和Node2Vec。其中Node2Vec的作者之一Jure Leskovec现在也是Pinterest的首席科学家。

Node2Vec的优化目标是对于任意图中节点,最大化它的邻居观测到的概率:

1

他采取的做法是对DeepWalk更广义程度上的抽象:biased-random walks。这个bias用来调节每次random walk是更像一个广度优先搜索(BFS),还是深度优先搜索(DFS)。对于极端情况,采用BFS的时候,每一个节点的观测被限制在度为1的邻居上,也就是下图的节点1,2,3。这种观测有助于提取网络structural的信息,两个拥有同样邻居的节点在向量化后距离很近。采用DFS的时候,我们不断走向其他节点,如下图的4,5,9。这种情况有助于提取网络homophily的信息,也就说两个相互连接通路较多的节点在向量化后距离很近。

2

Node2Vec通过两个参数来bias random walk是更像BFS还是DFS。一个参数叫做return parameter(p),当p越高,我们越不去对之前两步走过的节点进行取样,这样我们就可以对更多的节点进行采样。另一个参数叫做in-out parameter(q),用来控制我们向外走还是向内走,当q越大,我们越愿意访问离当前节点较远的节点。

以下是他们算法的伪代码:

3

Deep Learning to Related Pins

回归到Pinterest的应用场景,在我的文章“Pinterest推荐系统四年进化之路”里有介绍一部分Pinterest Related Pins来自于Session Co-occurence。其主要原因是只基于Pin和Board的关联图进行推荐的算法虽然有着很好的recall,但是他们不能区分Pin里面细微的主题,不能够根据用户在将Pin加入到一个Board时的上下文进行推荐,于此同时Board也容易随着用户的兴趣转移而变换主题。

就比方下面这张公狮子和母狮子的图,只基于Board Co-occurence得到的推荐如下:

4

但这一问题可以通过挖掘有时效性的用户行为得到解决,也就是Pin2Vec。该方法把用户Pin东西的行为当做文章,Pin当做单词,同样采用Skip-gram的方法对Pin进行向量化,一个抽象的图如下,具体操作可以参考Pinterest的工程师文章“Applying deep learning to Related Pins”:

5

采用分析用户Session的方法,我们对上面的Pin得到的Related Pins如下:

6

在上周听了马老师介绍Related Pins的时候,我突然发现其实这和Node2Vec也是相通的,同样基于Skip-gram模型,如果换一种角度来看其实Pinterest的做法也算是学习网络表示。

我们可以把Pinterest上每一个Pin当做一个节点,每当有用户保存了一个Pin A和另一个Pin B之后,就在Pin A和Pin B之间建立了一条边。对于这样一个有很多很多Pin和用户行为组成的网络,我们可以采用Node2Vec中提到的biased random walk方法对Pin进行向量化,从而优化相关Pin之间的距离。Pinterest之前的做法采用用户每一个Session中保存的Pin sequence当做句子进行向量化,其实等价于一个产生同样序列的random walk。

以下是我和Pinterest推荐团队交流后自己猜想的一些优劣势。

基于random walk将网络节点向量化其实可以更好地应用到更大的网络结构当中去,因为随机游走的方法针对度大的和度小的节点都能够产生足够多的序列,得到覆盖面比较高的向量。相比而言,Pinterest只根据用户行为产生序列则只能对度大的节点产生足够多的序列,进行向量化,覆盖面不高,最后只应用到比较流行的Pin上。

但是random walk的方法总的来说随机性比较大,Pinterest现在的解法,每走一步都能保证这一步前后的两个Pin在某种意义上是互相关联的,但是当随机游走多次之后,走过的边可能是不同用户在不同上下文产生的,所以序列首尾的关联性可能无法保证。如果我们只根据用户行为产生序列进行取样则可以极大程度上保证关联性。

所以,我们是不是可以结合biased random walk和现在Pinterest基于用户行为的取样在一起,在每次序列取样的时候,尽量偏向某一个用户的行为产生的边,这样可以在关联性和节点覆盖面上达到一个更好的平衡。不过Pinterest不同的Pin图像有上十亿种,所以覆盖不了所有的节点也是正常的。

我已经不在Pinterest工作了,但是感兴趣的小伙伴不妨试试。

Asymmetric Proximity

最后我想简要提一下非对称相似度的问题,在今年AAAI 2017的会议上,一群来自北大和阿里的牛人发表了这么一篇文章“Scalable Graph Embedding for Asymmetric Proximity”。他们的观点非常有道理,比方在下图中,传统的作法最后结果不管在无向图还是有向图中,节点的向量相似性是对称的,Sim(A,C) = Sim(C,A)。然而在实际应用过程中,可以明显看出由A到C和由C到A的关联性是很不一样的,举一个电商的例子,买跑步机的人很容易想到买一个垫子保护地板,但买垫子的人不一定会去买一个跑步机。

7

在应用网络表示向量化的结果解决实际问题的时候,我们常常可以采用一些节点特有的特征来进行优化,比方节点的度,其他标签等信息,但是北大和阿里的这帮人想让向量自己解决这一问题。

他们的做法其实并不复杂,就是将传统的一个节点向量变成了一个节点产生两个向量s与t,然后优化起始点为u到目标点v之间的关联度:

8

直接看他们的伪代码,针对每一个节点进行了若干次取样,每次取样得到一个节点u,并且优化v到u的关联性,然后随机取样k个节点,降低他们的关联性。他们在实现的时候采用了path sharing的做法,有效的降低了取样的次数。

9

如果只是到这里,他们的论文还只是一般吸引我,但是我看到他们说实验时候采用了淘宝的数据,大约有290 million的产品和18 billion条边,这样规模的工业界数据和实验结果是非常有说服力的,并且我觉得可以应用到Wish的产品推荐当中。

他们具体测试方法是用向量化的特征来选择每个店铺的每个分类Top 6展示产品,网络结构是像Pinterest上文中提到的Session Sequence那样生成的,最终他们的新方法有10%到15%的在线CTR提升,让人眼前一亮。

10

尾声…

单单看Node2Vec只是了解一个思路,但是结合Pinterest的Engineer Blog和阿里这篇Graph Embedding一起则令我受益匪浅。上文只是我个人怎么看基于用户行为推荐和网络表示学习之间的相似性,这里每一篇论文都不难,但是小技巧可以给不同的应用带来很大的提升。

还像往常一样,我在这里只是抛砖引玉,希望各位前辈多多指点交流。如果我的公众号里有更了解阿里淘宝那篇论文的同学,欢迎与我联系,对于这篇文章我还有很多疑惑,希望得到更多交流。

最后,在我把这篇文章给朋友浏览的时候,他们告诉我最近Jure又在Pinterest尝试新的方法,基于GraphSage,有谁知道效果如何欢迎留言给我。

本文授权转载自公众号:硅谷程序汪,作者:王栋

很抱歉,根据相关法律法规,本站暂时关闭评论,欢迎移步至品玩App发表您的评论
更多有趣好玩的内容 尽在品玩微信公众号
brand

PingWest品玩移动客户端