敞开生长之旅！这是我参加「日新计划 2 月更文挑战」的第 19 天，点击检查活动详情

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}$ 表明item或许side information的embedding矩阵，其间， $Wv0\mathbf{W}_v^0$ 表明item $v$ 的embedding， $Wvs\mathbf{W}_v^s$ 表明第 $s$ 个side information，item $v$ 共有 $n$ 个side information，则关于item $v$ 共有 $n + 1$ 个向量：

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

其间， $d$ 为embedding的维度。

关于item $v$ ，运用average-pooling将这 $n + 1$ 个向量聚合起来，得到item $v$ 的向量表明：

Hv=1n+1∑s=0nWvs\mathbf{H}_v=\frac{1}{n+1}\sum_{s=0}^{n}\mathbf{W}_v^s

2.3. EGES算法

EGES算法全称为Enhanced Graph Embedding with Side Information，从其姓名来看便能够知道，EGES是GES的增强版。在GES中，每一个向量，包含一个item的向量以及 $n$ 个side information的向量，这些向量的权重是相同的。从实践的状况来看，不同种类的side information关于最终的embedding的贡献是不相同的。因而EGES对GES中的向量做了加权的操作。

假定关于item $v$ ，权重矩阵为 $A∈R∣V∣(n+1)\mathbf{A}\in\mathbb{R}^{\left | V \right |\times \left ( n+1 \right )}$ ，其间， $Aij\mathbf{A}_{ij}$ 表明第 $i$ 个item的第 $j$ 个side information的权重，为简单，记 $a_i^j$ 为 $Aij\mathbf{A}_{ij}$ ， $Ai0\mathbf{A}_{i0}$ 表明的是item $i$ 自身向量的权重，记为 $a_i^0$ 。

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

Hv=∑j=0neavjWvj∑j=0neavj\mathbf{H}_v=\frac{\sum _{j=0}^ne^{a_v^j}\mathbf{W}_v^j}{\sum _{j=0}^ne^{a_v^j}}

其间，运用 $e^{a_v^j}$ 而不是 $a_v^j$ 是为了保证权重大于0。

2.4. GES和EGES的模型结构

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

其间，Dense Embeddings表明的是item向量以及 $n$ 个side information的向量。Hidden Representation即为如上公式中的 $Hv\mathbf{H}_v$ 。从上述过程来看，GES即为EGES模型的简化版别，即权重都为 $1n+1\frac{1}{n+1}$ 。

2.5. EGES中item向量的求解

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

从EGES算法的流程中，笔者发现，其与DeepWalk的流程根本一致，不同的首要是两点：1）学习的参数不同，在DeepWalk中首要是item的向量表明，在EGES中不只要学习item的向量 $W0\mathbf{W}^0$ ， $n$ 个side information的向量 $W1,⋯Wn\mathbf{W}^1,\cdots \mathbf{W}^n$ ，还包含权重的矩阵 $A\mathbf{A}$ ；2）在DeepWalk中运用的是SkipGram，在EGES中运用的是WeightedSkipGram。

2.6. Weighted Skip-Gram

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

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

为评论的便利，假定在Skip-Gram模型中，每个词的向量维度为 $d$ ，在词典 $V$ 中，中心词 $w_c$ 的词向量为 $vc∈Rdv_c\in \mathbb{R}^d$ ，布景词 $w_o$ 的词向量为 $uo∈Rdu_o\in \mathbb{R}^d$ 。给定中心词生成布景词的条件概率能够经过对向量内积做softmax运算而得到：

P(wo∣wc)=exp(uoTvc)∑i∈Vexp(uiTvc)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 )}

此刻，关于整个文本能够得到如下的概率形式：

∏t=1T∏−m⩽j⩽m,j≠0P(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 )

语言模型中的方针是要使得上述的概率最大，经过log似然，能够得到如下的损失函数：

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 )

关于 $P(wo∣wc)log\; P\left ( w_o\mid w_c \right )$ ，有：

P(wo∣wc)=uoTvc−log(∑i∈Vexp(uiTvc))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 )

为了能够对其间的参数求解，能够运用梯度下降法求解，此刻需求对损失函数求导，以 $P(wo∣wc)∂vc\frac{\partial log\; P\left ( w_o\mid w_c \right )}{\partial v_c}$ 为例：

P(wo∣wc)∂vc=uo−∑j∈VP(wj∣wc)⋅uj\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

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

关于上述给定的中心词 $w_c$ ，给定一个布景窗口，假定布景词 $w_o$ 出现在 $w_c$ 的布景窗口中的事件概率为：

P(D=1∣wc,wo)=(uoTvc)P\left ( D=1\mid w_c,w_o \right )=\sigma \left ( u_o^Tv_c \right )

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

∏t=1T∏−m⩽j⩽m,j≠0P(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 )

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

∏t=1T∏−m⩽j⩽m,j≠0P(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 )

其间， $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(D=1∣w(t),w(t+j))⋅∏k=1KP(D=0∣w(t),wk)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 )

能够验证，此刻核算不再与词典大小相关，而是与负采样的参数 $K$ 相关，以上就是Skip-Gram模型以及负采样的相关内容。

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

L(v,u,y)=−[ylog((HvTZu))+(1−y)log(1−(HvTZu))]\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∂Zu=((HvTZu)−y)Hv\frac{\partial \mathfrak{L}}{\partial \mathbf{Z}_u}=\left ( \sigma \left ( \mathbf{H}_v^T\mathbf{Z}_u \right )-y \right )\mathbf{H}_v

∂L∂avs=((HvTZu)−y)Zu(∑j=0neavj)eavsWvs−eavs∑j=0neavjWvj(∑j=0neavj)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}

∂L∂Wvs=eavs∑j=0neavj((HvTZu)−y)Zu\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

参考文献

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在淘宝推荐体系中的应用
NLP之—word2vec算法skip-gram原理详解