推荐系统中的常用算法——基于Graph Embedding的GES和EGES

不念不忘少年蓝@ 2022-12-11 07:28 343阅读 0赞

# 1. 概述 #

相比较于基于Collaborative Filter算法，基于基础Graph Embedding模型可以根据用户的行为序列学习出item的embedding，利用item对应的Embedding可以方便计算item与item之间的相似度，并在实践中被证明是卓有成效的方法，在基于基础Graph Embedding模型，主要包括item2vec，node2vec，deepwalk等算法。

在使用基础Graph Embedding算法的前提是用户的行为序列，但是对于一些新的item或者用户很少有行为的item，即冷启动问题，基础的Graph Embedding算法很难学到对应item的embedding表示，为此，一些针对item冷启动的方法被提出，其中就包括GES和EGES算法。

GES和EGES是阿里在2018年提出的两个基于Graph Embedding的算法，其中GES全称为Graph Embedding with Side Information，EGES全称为Enhanced Graph Embedding with Side Information。为了解决冷启动的问题，GES和EGES在计算item embedding的过程中引入了side information。

# 2. 算法原理 #

## 2.1. side information ##

side information在推荐系统中有着重要的作用，不仅仅能应用在召回中用于处理冷启动问题，同时在排序阶段中也有广泛的应用。side information主要指的是与item相关的一些先验信息，对于商品而言，先验信息包括：类别，商店，价格等。

## 2.2. GES算法 ##

GES算法全称为Graph Embedding with Side Information，假设 W \\mathbf\{W\} W表示item或者side information的embedding矩阵，其中， W v 0 \\mathbf\{W\}\_v^0 Wv0表示item  v v v的embedding， W v s \\mathbf\{W\}\_v^s Wvs表示第 s s s个side information，item  v v v共有 n n n个side information，则对于item  v v v共有 n + 1 n+1 n\+1个向量：

W v 0 ， ⋯   , W v n ∈ R d \\mathbf\{W\}\_v^0，\\cdots ,\\mathbf\{W\}\_v^n\\in \\mathbb\{R\}^d Wv0，⋯,Wvn∈Rd

其中， d d d为embedding的维度。

对于item  v v v，使用average-pooling将这 n + 1 n+1 n\+1个向量聚合起来，得到item  v v v的向量表示：

H v = 1 n + 1 ∑ s = 0 n W v s \\mathbf\{H\}\_v=\\frac\{1\}\{n+1\}\\sum\_\{s=0\}^\{n\}\\mathbf\{W\}\_v^s Hv=n\+11s=0∑nWvs

## 2.3. EGES算法 ##

EGES算法全称为Enhanced Graph Embedding with Side Information，从其名字来看便可以知道，EGES是GES的增强版。在GES中，每一个向量，包括一个item的向量以及 n n n个side information的向量，这些向量的权重是一样的。从实际的情况来看，不同种类的side information对于最终的embedding的贡献是不一样的。因此EGES对GES中的向量做了加权的操作。

假设对于item  v v v，权重矩阵为 A ∈ R ∣ V ∣ × ( n + 1 ) \\mathbf\{A\}\\in\\mathbb\{R\}^\{\\left | V \\right |\\times \\left ( n+1 \\right )\} A∈R∣V∣×(n\+1)，其中， A i j \\mathbf\{A\}\_\{ij\} Aij表示第 i i i个item的第 j j j个side information的权重，为简单，记 a i j a\_i^j aij为 A i j \\mathbf\{A\}\_\{ij\} Aij， A i 0 \\mathbf\{A\}\_\{i0\} Ai0表示的是item  i i i本身向量的权重，记为 a i 0 a\_i^0 ai0。

对于item  v v v，加权平均后的结果为：

H v = ∑ j = 0 n e a v j W v j ∑ j = 0 n e a v j \\mathbf\{H\}\_v=\\frac\{\\sum \_\{j=0\}^ne^\{a\_v^j\}\\mathbf\{W\}\_v^j\}\{\\sum \_\{j=0\}^ne^\{a\_v^j\}\} Hv=∑j=0neavj∑j=0neavjWvj

其中，使用 e a v j e^\{a\_v^j\} eavj而不是 a v j a\_v^j avj是为了保证权重大于0。

## 2.4. GES和EGES的模型结构 ##

GES和EGES的模型结构如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center]  
其中，Dense Embeddings表示的是item向量以及 n n n个side information的向量。Hidden Representation即为如上公式中的 H v \\mathbf\{H\}\_v Hv。从上述过程来看，GES即为EGES模型的简化版本，即权重都为 1 n + 1 \\frac\{1\}\{n+1\} n\+11。

## 2.5. EGES中item向量的求解 ##

EGES算法的流程如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center 1]  
从EGES算法的流程中，笔者发现，其与DeepWalk的流程基本一致，不同的主要是两点：1）学习的参数不同，在DeepWalk中主要是item的向量表示，在EGES中不仅要学习item的向量 W 0 \\mathbf\{W\}^0 W0， n n n个side information的向量 W 1 , ⋯ W n \\mathbf\{W\}^1,\\cdots \\mathbf\{W\}^n W1,⋯Wn，还包括权重的矩阵 A \\mathbf\{A\} A；2）在DeepWalk中使用的是SkipGram，在EGES中使用的是WeightedSkipGram。

## 2.6. Weighted Skip-Gram ##

Weighted Skip-Gram算法的流程如下所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center 2]  
为了能够更好的理解上述的流程，我们需要先了解word2vec中Skip-Gram模型的具体流程，在词向量的求解过程中除了Skip-Gram还可以是CBOW模型，本文的重点是Skip-Gram模型，Skip-Gram模型的结构如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center 3]  
为讨论的方便，假设在Skip-Gram模型中，每个词的向量维度为 d d d，在词典 V V V中，中心词 w c w\_c wc的词向量为 v c ∈ R d v\_c\\in \\mathbb\{R\}^d vc∈Rd，背景词 w o w\_o wo的词向量为 u o ∈ R d u\_o\\in \\mathbb\{R\}^d uo∈Rd。给定中心词生成背景词的条件概率可以通过对向量内积做softmax运算而得到：

P ( w o ∣ w c ) = e x p ( u o T v c ) ∑ i ∈ V e x p ( u i T v c ) P\\left ( w\_o\\mid w\_c \\right )=\\frac\{exp\\left ( u\_o^Tv\_c \\right )\}\{\\sum \_\{i\\in V\}exp\\left ( u\_i^Tv\_c \\right )\} P(wo∣wc)=∑i∈Vexp(uiTvc)exp(uoTvc)

此时，对于整个文本可以得到如下的概率形式：

∏ t = 1 T ∏ − m ⩽ j ⩽ m , j ≠ 0 P ( w ( t + j ) ∣ w ( t ) ) \\prod\_\{t=1\}^\{T\}\\prod \_\{-m\\leqslant j\\leqslant m,j\\neq 0\}P\\left ( w^\{\\left ( t+j \\right )\}\\mid w^\{\\left ( t \\right )\} \\right ) t=1∏T−m⩽j⩽m,j=0∏P(w(t\+j)∣w(t))

语言模型中的目标是要使得上述的概率最大，通过log似然，可以得到如下的损失函数：

− ∏ t = 1 T ∏ − m ⩽ j ⩽ m , j ≠ 0 l o g    P ( w ( t + j ) ∣ w ( t ) ) -\\prod\_\{t=1\}^\{T\}\\prod \_\{-m\\leqslant j\\leqslant m,j\\neq 0\}log\\; P\\left ( w^\{\\left ( t+j \\right )\}\\mid w^\{\\left ( t \\right )\} \\right ) −t=1∏T−m⩽j⩽m,j=0∏logP(w(t\+j)∣w(t))

对于 l o g    P ( w o ∣ w c ) log\\; P\\left ( w\_o\\mid w\_c \\right ) logP(wo∣wc)，有：

l o g    P ( w o ∣ w c ) = u o T v c − l o g ( ∑ i ∈ V e x p ( u i T v c ) ) log\\; P\\left ( w\_o\\mid w\_c \\right )=u\_o^Tv\_c-log\\left ( \\sum \_\{i\\in V\}exp\\left ( u\_i^Tv\_c \\right ) \\right ) logP(wo∣wc)=uoTvc−log(i∈V∑exp(uiTvc))

为了能够对其中的参数求解，可以使用梯度下降法求解，此时需要对损失函数求导，以 ∂ l o g    P ( w o ∣ w c ) ∂ v c \\frac\{\\partial log\\; P\\left ( w\_o\\mid w\_c \\right )\}\{\\partial v\_c\} ∂vc∂logP(wo∣wc)为例：

∂ l o g    P ( w o ∣ w c ) ∂ v c = u o − ∑ j ∈ V P ( w j ∣ w c ) ⋅ u j \\frac\{\\partial log\\; P\\left ( w\_o\\mid w\_c \\right )\}\{\\partial v\_c\}=u\_o-\\sum \_\{j\\in V\}P\\left ( w\_j\\mid w\_c \\right )\\cdot u\_j ∂vc∂logP(wo∣wc)=uo−j∈V∑P(wj∣wc)⋅uj

从上述的公式发现，每次的求导数的过程中，都需要对整个词典中的词计算，如果词典较大，那么每次更新时的计算成本就比较大，为降低计算成本，近似的训练方法被提出，负采样（Negative Sampling）便是其中的一种近似计算方法。

对于上述给定的中心词 w c w\_c wc，给定一个背景窗口，假设背景词 w o w\_o wo出现在 w c w\_c wc的背景窗口中的事件概率为：

P ( D = 1 ∣ w c , w o ) = σ ( u o T v c ) P\\left ( D=1\\mid w\_c,w\_o \\right )=\\sigma \\left ( u\_o^Tv\_c \\right ) P(D=1∣wc,wo)=σ(uoTvc)

对于给定的长度为 T T T的文本，假设时间步 t t t的词为 w ( t ) w^\{\\left ( t \\right )\} w(t)且背景窗口大小为 m m m，此时联合概率为：

∏ t = 1 T ∏ − m ⩽ j ⩽ m , j ≠ 0 P ( D = 1 ∣ w ( t ) , w ( t + j ) ) \\prod\_\{t=1\}^\{T\}\\prod \_\{-m\\leqslant j\\leqslant m,j\\neq 0\}P\\left ( D=1\\mid w^\{\\left ( t \\right )\},w^\{\\left ( t+j \\right )\} \\right ) t=1∏T−m⩽j⩽m,j=0∏P(D=1∣w(t),w(t\+j))

此时模型中仅考虑了正样本，通过采样 K K K个未出现在该背景窗口中的词，此时的联合概率为：

其中， P ( w ( t + j ) ∣ w ( t ) ) P\\left ( w^\{\\left ( t+j \\right )\}\\mid w^\{\\left ( t \\right )\} \\right ) P(w(t\+j)∣w(t))可以表示为：

P ( w ( t + j ) ∣ w ( t ) ) = P ( D = 1 ∣ w ( t ) , w ( t + j ) ) ⋅ ∏ k = 1 K P ( D = 0 ∣ w ( t ) , w k ) P\\left ( w^\{\\left ( t+j \\right )\}\\mid w^\{\\left ( t \\right )\} \\right )=P\\left ( D=1\\mid w^\{\\left ( t \\right )\},w^\{\\left ( t+j \\right )\} \\right )\\cdot \\prod\_\{k=1\}^\{K\}P\\left ( D=0\\mid w^\{\\left ( t \\right )\},w\_k \\right ) P(w(t\+j)∣w(t))=P(D=1∣w(t),w(t\+j))⋅k=1∏KP(D=0∣w(t),wk)

可以验证，此时计算不再与词典大小相关，而是与负采样的参数 K K K相关，以上便是Skip-Gram模型以及负采样的相关内容。

对于采样到的样本 u u u，其对应的向量为 Z u \\mathbf\{Z\}\_u Zu，由上述的理论可以得到：

L ( v , u , y ) = − \[ y l o g ( σ ( H v T Z u ) ) + ( 1 − y ) l o g ( 1 − σ ( H v T Z u ) ) \] \\mathfrak\{L\}\\left ( v,u,y \\right )=-\\left \[ ylog\\left ( \\sigma \\left ( \\mathbf\{H\}\_v^T\\mathbf\{Z\}\_u \\right ) \\right )+\\left ( 1-y \\right )log\\left ( 1-\\sigma \\left ( \\mathbf\{H\}\_v^T\\mathbf\{Z\}\_u \\right ) \\right ) \\right \] L(v,u,y)=−\[ylog(σ(HvTZu))\+(1−y)log(1−σ(HvTZu))\]

可以得到如下的导数：

∂ L ∂ Z u = ( σ ( H v T Z u ) − y ) H v \\frac\{\\partial \\mathfrak\{L\}\}\{\\partial \\mathbf\{Z\}\_u\}=\\left ( \\sigma \\left ( \\mathbf\{H\}\_v^T\\mathbf\{Z\}\_u \\right )-y \\right )\\mathbf\{H\}\_v ∂Zu∂L=(σ(HvTZu)−y)Hv

∂ L ∂ a v s = ( σ ( H v T Z u ) − y ) Z u ( ∑ j = 0 n e a v j ) e a v s W v s − e a v s ∑ j = 0 n e a v j W v j ( ∑ j = 0 n e a v j ) 2 \\frac\{\\partial \\mathfrak\{L\}\}\{\\partial a\_v^s\}=\\left ( \\sigma \\left ( \\mathbf\{H\}\_v^T\\mathbf\{Z\}\_u \\right )-y \\right )\\mathbf\{Z\}\_u\\frac\{\\left ( \\sum\_\{j=0\}^\{n\}e^\{a\_v^j\} \\right )e^\{a\_v^s\}\\mathbf\{W\}\_v^s-e^\{a\_v^s\}\\sum\_\{j=0\}^\{n\}e^\{a\_v^j\}\\mathbf\{W\}\_v^j\}\{\\left ( \\sum\_\{j=0\}^\{n\}e^\{a\_v^j\} \\right )^2\} ∂avs∂L=(σ(HvTZu)−y)Zu(∑j=0neavj)2(∑j=0neavj)eavsWvs−eavs∑j=0neavjWvj

∂ L ∂ W v s = e a v s ∑ j = 0 n e a v j ( σ ( H v T Z u ) − y ) Z u \\frac\{\\partial \\mathfrak\{L\}\}\{\\partial \\mathbf\{W\}\_v^s\}=\\frac\{e^\{a\_v^s\}\}\{\\sum\_\{j=0\}^\{n\}e^\{a\_v^j\}\}\\left ( \\sigma \\left ( \\mathbf\{H\}\_v^T\\mathbf\{Z\}\_u \\right )-y \\right )\\mathbf\{Z\}\_u ∂Wvs∂L=∑j=0neavjeavs(σ(HvTZu)−y)Zu

# 参考文献 #

*  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.
 *  [\[Graph Embedding\]阿里超大规模商品Embedding策略EGES][Graph Embedding_Embedding_EGES]
 *  [Graph Embedding在淘宝推荐系统中的应用][Graph Embedding]
 *  [NLP之—word2vec算法skip-gram原理详解][NLP_word2vec_skip-gram]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/a7d8b1359025417baa60be741458470c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/67dc1d36113a4d3c93c39d067844028c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/59f374250bf845ae8898d852437f185c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvb2dsZTE5ODkwMTAy_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/2842a62a44cb493281cb251b750e5bb8.png
[Graph Embedding_Embedding_EGES]: https://zhuanlan.zhihu.com/p/133870768
[Graph Embedding]: https://zhuanlan.zhihu.com/p/70198918
[NLP_word2vec_skip-gram]: https://blog.csdn.net/weixin_41843918/article/details/90312339