写点什么

图系列算法在转转推荐算法召回及粗排的实践

  • 2022 年 9 月 14 日
    北京
  • 本文字数:4028 字

    阅读完需:约 13 分钟

图系列算法在转转推荐算法召回及粗排的实践

一、转转推荐算法介绍

1.1 什么是推荐系统?

随着信息技术与互联网的飞速发展,借由互联网所传递的信息也在飞速地膨胀,人类从信息匮乏时代走向了信息过载时代,推荐系统开始在互联网技术中扮演不可或缺的角色。推荐系统帮助人们更高效地建立与信息的连接,节约信息筛选的时间,为用户匹配、探索兴趣,也让平台的高效分发成为可能。对于转转来说,推荐系统承担了为用户推荐商品与内容的重要角色,一方面链接了用户与商品的关系,为用户节约筛选心仪产品的时间,帮助用户在平台琳琅满目的商品中发现感兴趣的商品;另一方面帮助商家让自己的商品从海量商品中脱颖而出,推荐给合适的用户。在推荐系统中,推荐算法扮演了发动机的作用。

推荐算法的作用

1.2 转转推荐主要场景及流程

转转推荐主要场景

在转转 APP 中,推荐算法涉及的主要场景包括首页推荐、商详页推荐以及收藏夹推荐等等。用户进入 APP 后,在主页面下滑即进入首页推荐场景,该场景由算法推荐用户可能感兴趣的商品流,帮助用户进行商品的筛选和探索;当用户点击一个商品后,即进入商详页推荐,为用户推荐与主商品相似的更多商品以挑选;当用户收藏商品后,也会根据用户的收藏行为和历史兴趣,为用户推荐更多的商品。

推荐算法流程

推荐算法的主要流程如图所示,整个流程呈漏斗形,对商品库进行层层筛选,最后将推荐结果呈现给用户。

召回是推荐算法的第一阶段,根据用户和商品信息从海量的商品库中,快速筛选出用户可能感兴趣的商品集,传递给接下来的粗排及精排部分。由于面对的商品集合非常大,因此召回阶段对于性能要求高,需要用相对简单的模型及特征;

粗排则承接召回筛选过的商品,为用户推荐的候选集打分,并筛选出精排候选,作为一个承上启下的阶段,模型及特征的复杂度相对折中;

精排则通常只对少量商品进行排序,可以使用较多特征及复杂模型,对于推荐的准确度要求更高;

最后会根据业务特点及其他目标进行重排,在此不再赘述。

本次分享主要介绍图算法的原理以及在转转召回及粗排阶段的实践。

二、图算法原理介绍及转转实践

图是一种基础且常用的数据结构,也广泛存在于真实世界的多种场景中,例如社交网络中人与人的联系、生物中蛋白质的作用以及电商中用户与商品之间的关系等等。

在转转的场景中,通过对用户与商品关系的建图以及在此基础上的图表示学习,我们能够得到低维、稠密、实值的向量,能够表达节点之间内在的关系。

利用得到的向量,既可以作为排序层的预训练特征,也可以直接计算向量相似度,寻找相似的商品,并直接推荐给用户。

图结构以及对应的节点向量(引自 DeepWalk 论文)

2.1 经典 Graph Embedding 方法:DeepWalk

首先介绍经典的 Graph Embedding 方法——DeepWalk。

DeepWalk 的基本流程(引自阿里 EGES 论文)

DeepWalk 在电商场景应用的大体流程可以分为以下四个步骤:

  1. 获取用户原始行为序列,并根据一定规则进行切分(如点击间隔超过 1 小时)。

  2. 基于这些切分的用户序列,构建商品图结构。例如用户 A 依次产生了 D、A、B 的行为,则构建 D->A 的有向边、A->B 的有向边。将所有用户序列产生的商品共现对如(D,A)都建立有向边后,即建立起全局的商品图。

  3. 选取多个起始点(实际上可以以每个节点为起始点)进行随机游走,得到多条序列。

  4. 将重新生成的物品序列利用 word2vec 模型里的 skip-gram 算法进行图向量的训练和获取。

其中关键是第三步的随机游走过程,即如何选择下一个游走的节点。DeepWalk 定义节点 vi 到 vj 的转移概率如下:

P(vj∣vi)={Mij∑j∈N+(vi)Mij,vj∈N+(vi)0,eid∈ε

其中 N+(vi)是 vi 的所有出边集合,Mij 是节点 vi 到 vj 的边权重。

2.2 结构性与同质性:node2vec

图的 BFS 和 DFS 遍历(引自 node2vec 论文)

在 DeepWalk 的基础上,node2vec 改进了随机游走过程的游走概率,引入了两个超参数来平衡图的两类游走方式——广度优先 BFS 和深度优先 DFS。

node2vec 的节点转移概率

通过引入超参数 p 和 q,算法能够控制节点的游走倾向性。将节点的游走概率定义为πvx=αpq(t,x)·wvx,其中 wvx 是边 vx 的权重,αpq(t,x)定义如下:

αpq(t,x)={1p,dtx=01,dtx=11q,dtx=2

其中,dtx 指节点 t 到节点 x 的距离,超参数 p 被称为返回参数,p 越小,返回原节点的概率越大,游走偏向 BFS,更关注结构性相似;q 被称为进出参数,q 越小,则随机游走向更远节点的概率越大,游走偏向 DFS,更关注同质性相似。

同质性与结构性(引自 node2vec 论文)

在推荐系统中,同质性相似的物品体现在同品类、同属性或者经常被一同点击、购买的商品;而结构性相似的物品则体现在各品类的爆款、各品类的最佳凑单商品等趋势类似的商品。node2vec 相比 DeepWalk 拥有更强的灵活性,能够帮助我们根据应用场景的不同选择不同的游走策略,得到合理的向量表示。

2.3 融合辅助信息:EGES

回顾下 DeepWalk 一节中介绍的算法流程,能够发现一个问题:对于新商品或者用户交互较少的商品,很可能是孤立的节点或者节点权重很小,导致不能游走到该节点或游走到该节点的概率很低。如何解决这类冷启动问题?

阿里 2018 年提出的 EGES(Enhanced Graph Embedding with Side Information)在 skip-gram 的向量嵌入过程中,除了采用序列的 ID 类 embedding 之外,还引入了带权的辅助信息(side information)来缓解该问题。

EGES 到生成商品序列前的流程与 DeepWalk 介绍的一致,但是在最后的嵌入过程中,引入了如类别、品牌、所在城市等辅助信息的多个 embedding 共同训练。对于多个 embedding,最简单的融合方法即 average pooling,形式化定义如下:

Hv=1n+1∑s=0nWvs

利用以上公式即平均操作,将不同的辅助信息向量与原物品向量融合,其中 W0 代表原始物品的 embedding,W1...Wn 代表每种 side information 对应的 embedding。

但是在实际问题中,不同的辅助信息对于物品的贡献应有所不同,如一个购买了 iPhone 的用户,倾向于查看 MacBook 和 iPad,是因为品牌。引入加权形式的辅助信息利用,能够得到更准确的 embedding。

Hv=∑j=0neavjWvj∑j=0neavj

在 GES 模型的基础上,引入权重 a1...an,通过 Hidden Representation 层执行加权平均操作,并输入 softmax 层,通过反向传播求得权重。

通过 eaj 代替 aj,保持权重大于 0,分母则起到 normalize weights 的作用。

最后进行 skip-gram 的方式训练得到每个商品的 embedding 和 side infomation 及对应的权重。

阿里 EGES 的向量训练模型结构

2.4 辅助信息融入建图:转转召回实践

在转转的实际实践中,采用 EGES 的加强辅助信息融合方式遇到了一些困难,特别是辅助信息融合训练的性能问题。

融入辅助信息的有向带权商品图

因此,我们采取了影响图权重的方式来引入辅助信息。主要有以下步骤:

  1. 获取用户序列切分生成共现对,并同步获取相应商品的辅助信息

  2. 将全局共现对聚合,根据用户交互行为数目确定初始权重

  3. 根据节点间边的预先定义的几类辅助信息调整权重,例如同类或同价格区间即上调权重

  4. 进行 node2vec 随机游走过程并进行向量嵌入训练

通过辅助信息融入建图过程的方法,大大提高了训练速度,并减少了 embedding 参数量,在实际应用中向量的质量也能够满足需要。在 node2vec 参数上,可以通过调整同质性相似与结构性相似,来应用于详情页推荐场景与首页推荐场景。

得到商品向量即可进行向量相似度计算,从而进行商品的 item2item 推荐,或者利用用户交互过的商品进行 user2item2item 的推荐。

2.5 异构图表示:转转粗排实践

对于粗排来说,需要得到同空间内的用户向量及商品向量,利用内积操作,能够对于用户的召回候选集进行快速的打分和筛选。通常的粗排模型往往采用双塔模型,通过拆分用户塔和商品塔,可以使得向量产出由离线计算完成,线上则采用内积。可见,粗排的关键问题即是用户和商品的向量生成。那么能不能通过图算法来得到用户和商品的向量呢?答案是肯定的。

前几节介绍了 Graph Embedding 的原理以及一些改进的思路,和转转的召回实践,这些介绍中的图都为同构图,图中的节点都为商品。要同时得到用户和商品的向量,则需要将用户节点也加入到图中,构成异构图。

用户商品二部图生成无向带权图

具体的实现步骤如下:

  1. 获取用户行为序列,并切分为用户-商品二部图

  2. 根据二部图中的(用户,商品)共现对,建立无向带权图

  3. 在图中进行随机游走过程,得到形如 u1-i1-u2-i2...的序列

  4. 进行向量嵌入训练,得到用户及商品的向量

离线训练得到向量后,线上分别取得用户及商品向量,进行简单内积后即得商品打分。

三、总结

本次分享介绍了转转的主要场景及算法流程,并介绍了三种常见的图算法:

  • 经典的 Graph Embedding 方法 DeepWalk,是各类随机游走算法的基础

  • node2vec 在 DeepWalk 的基础上引入超参数控制游走倾向,学习结构性及同质性相似

  • EGES 则提出融合加权辅助信息,缓解节点冷启动的问题

介绍了上述图算法在转转推荐算法召回及粗排的实践。

图算法目前仍是工程和学术领域研究和实践的热点,除了本次分享介绍的方法,还有如随机游走类的 LINE、SDNE 以及图卷积类的 GAT、GraphSAGE 的方法,感兴趣的读者可以深入了解。图卷积算法也在转转有相应的落地和实践,有机会再向大家分享。谢谢!

参考资料

[1]Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014: 701-710.

[2]Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016: 855-864.

[3]Wang J, Huang P, Zhao H, et al. Billion-scale commodity embedding for e-commerce recommendation in alibaba[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 839-848.

[4]王喆:深度学习中不得不学习的 Graph Embedding 方法 https://zhuanlan.zhihu.com/p/64200072


> 转转研发中心及业界小伙伴们的技术学习交流平台,定期分享一线的实战经验及业界前沿的技术话题。> 关注公众号「转转技术」(综合性)、「大转转FE」(专注于FE)、「转转QA」(专注于QA),更多干货实践,欢迎交流分享~

发布于: 刚刚阅读数: 4
用户头像

还未添加个人签名 2019.04.30 加入

转转研发中心及业界小伙伴们的技术学习交流平台,定期分享一线的实战经验及业界前沿的技术话题。 关注公众号「转转技术」,各种干货实践,欢迎交流分享~

评论

发布
暂无评论
图系列算法在转转推荐算法召回及粗排的实践_深度学习_转转技术团队_InfoQ写作社区