深度模型（十二）：Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba

简介

互联网技术一直不断地在改变着商业，今天电子商务已经非常普及了。阿里作为中国最大的电子商务企业，使得全世界的消费者和企业在线上做生意。阿里拥有十亿的用户，2017年的总交易额（Gross Merchandise Volume）为37,670亿人民币，总收入为1,580亿人民币。2017年双十一购物节总交易额在1,680亿左右。其中，淘宝作为最大的C2C平台，贡献了75%的交易额。

淘宝拥有10亿用户，20亿的商品，如何帮助用户快速找到需要的和感兴趣的商品是一个关键问题。推荐系统成为解决这个问题的关键技术。例如淘宝APP的首页（图1）是通过推荐技术基于用户过去的行为而生成的，占总推荐量的40%。简单来说，推荐刺痛已经成为淘宝和阿里交易额和收入的关键因素。虽然学术和工业界有很多成功的推荐方法，比如协同过滤(CF)[9，11，16],基于内容的方法[2],基于深度学习的方法[5,6,22],这些方法的问题由于淘宝庞大的用户和商品数量而变的更加严重。

淘宝的推荐系统面对的主要问题有三点：

• 可扩展性（Scallability）:虽然很多推荐算法在小规模的数据上表现很好，比如在百万数量级的用户和物品，但这些方法没法扩展到10亿数量级的用户和商品上。
• 稀疏性（Sparsity）:用户一般只会与一小部分的商品有过交互，通过这些少量的交互信息，很难训练一个准确的推荐模型，这个问题通常被称为数据稀疏问题。
• 冷启动（Cold Start）: 淘宝每小时都有数以百万的新商品持续地上传到淘宝。这些商品都没有用户交互信息。这些新商品的推荐十分困难，这个问题通常被称为冷启动问题。

为了解决这些问题，我们设计了分为两阶段的推荐框架。第一个阶段称之为匹配(matching)阶段,第二阶段称之为排序(ranking)阶段。在匹配阶段我们生成一个候选集合，由与用户交互过的商品的相似商品组成。然后在排序阶段训练一个深度模型，基于用户喜好对候选集合内的商品进行排序。两个阶段面对的问题不一样，而且两个阶段的目标也不一样。

本文我们主要关注匹配阶段，核心任务是基于用户的行为计算商品间的相似度，有了相似度之后，就可以基于相似度生成候选集。为了完成这个任务，我们首先基于用户历史行为构建商品图，然后采用Dubbed Base Graph Embedding-最先进的图embedding方法[8,15,17]学习商品的embedding。最后通过商品embedding向量的点积计算物品间的相似度。基于协同过滤的方法也会计算物品间的相似度，但是它们[9,11,16]只会考虑用户的历史行为。我们的方法会在物品图中随机游走，捕捉物品间相似度，所以我们的方法优于CF方法。但是这个方法依然没有解决数据稀疏问题。因此，我们提出采用使用附加信息(side information)来加强embedding过程：Dubbed Graph Emebdding with Side information。例如，同一类的物品在嵌入空间内应该相距更近。通过这个方法，技术在很少甚至没有交互信息的情况下，我们也能获取商品的准确embedding.但是商品有上百种附加信息，比如类别、品牌、价格等等。直观感觉是不同的附加信息对商品的embedding应该有不同程度的贡献。因此我们又提出了一种加权机制：Dubbed Enhanced Graph Embedding with Side information(EGES).

总而言之，匹配阶段有三个重要部分：

• （1）基于淘宝多年的实践经验，我们设计一个高效的启发式方法，由10亿用户的行为历史构建出物品图
• （2）我们提出三中embedding方法：BGE(Base Graph Embedding)，GES(Graph Embedding with Side Information), EGES(Enhanced Graph Embedding with Side Information).我们通过离线的实验已经证明GES和EGES相对BGE和其他embeding方法更有效。
• （3）部署方面，我们在我们组XTensorflow（XTF）系统基础上开发了图embedding系统。结果显示我们的方法显著提高了淘宝APP的推荐效果，并且满足了双十一对模型训练效率以及服务性能的要求。

框架

这一节我们首先介绍一下图embedding的基础,然后介绍我们如何由用户的历史行为构建商品graph。最后我们研究所提出的embedding训练方法。

2.1 准备工作

这一小节我们首先整体介绍一下图embedding和最流行的方法之一：DeepWalk[15],基于这些知识我们提出我们匹配阶段的图embedding方法。给定一个图$G=(V,E)$,其中V和E分别表示节点和边的集合。图embedding的目标是对于集合中的每一个节点$v\in V$学习一个低维度的空间表示，表示空间为$R^d,d<<|V|$.换句话说，也就是我们的目标是学习一个映射函数$\Phi :V\to R^d$，将V中的每一个节点表示为一个维度为d的向量。

[13,14]提出word2vec算法，由语料中学习每个单词的embedding。收到word2vec的启发，Perozzi等提出了DeepWalk算法，学习图中每个节点的embedding[15].他们首先通过图中的随机游走产生节点序列，然后采用Skip-Gram算法学习每个节点的表示。为了保持图的拓扑结构，他们需要解决下面的最优化问题：

$$minimiz{e}_{\Phi }\sum _{v\in V}\sum _{c\in N(v)}-logPr(c|\Phi (v))$$

其中$N(v)$表示节点$v$的邻接节点，可以定义为与$v$的距离为1或2的节点。$Pr(c|\Phi (v))$表示给定节点$v$，存在邻接节点$c$的条件概率。

2.2 由用户行为创建商品Graph

实际中用户的历史行为是一些序列，如图2。基于CF的方法只考虑了商品的共现，但忽略了顺序信息，而顺序信息可以更准确的反应用户的偏好。然而不可能使用用户的全部历史行为，因为1)计算的空间和时间复杂度巨大，2）用户的兴趣点随时间会偏移。因此实际中，我们通常设置一个时间窗口，只使用用户在时间窗口内的行为历史。我们称之为基于会话的用户行为。时间窗口的经验值通常设置切一小时。

在获取了用户的基于会话的行为数据后，如果两个物品在行为数据中先后出现，则在物品间添加一条边。入图2中，物品D和A之间存在一条边，因为他们被用户U1先后访问。我们基于物品在所有用户行为序列中先后出现的次数，为没一条边赋予一个权重$e_{ij}$。

实际中，在提取用户行为序列之前，我们需要过滤掉无效的和异常的行为，降低噪音。目前下列行为被认为是噪音：

• 停留时长低于1秒的点击，可能是无心的点击，需要过滤掉
• 有一些过于活跃的用户，实际上是爬虫，需要过滤掉
• 商家在太傲持续的更新商品的详细信息。在极端的情况下，商品变成了完全不同的另一个商品，需要移除。

2.3 Base Graph Embedding

给定加权图$G=(V,E)$,$M$表示图的相邻矩阵，$M_{ij}$表示由$i$到$j$的边的权重。我们首先基于随机游走产生节点序列，然后采用Skip-Gram算法训练模型。随机游走的概率为：

$$P(v_j|v_i)=\{\begin{array}{ll}\frac{M_{ij}}{{\sum }_{j\in N_{+}(v_i)}{M}_{ij}},& v_j\in N_{+}(v_i)\\ 0,& e_{ij}\notin E\end{array}$$

其中$N_{+}(v_i)$表示出边的邻接节点集合。通过随机游走产生了一些序列，如图2©.

然后我们采用Skip-Gram算法[13,14]学习embedding，目标是最大化序列数据中两个节点共现的概率。等于以下目标：

m i n i m i z e Φ − l o g P r ( { v i − w , . . . , v i + w } \ v i ∣ Φ ( v i ) ) minimize_{\Phi} -logPr(\{v_{i-w},...,v_{i+w}\} \backslash v_i|\Phi(v_i)) minimizeΦ​−logPr({vi−w​,...,vi+w​}\vi​∣Φ(vi​))

其中$w$表示窗口大小。假设条件独立，得到:

P r ( { v i − w , . . . , v i + 2 \ v i ∣ Φ ( v i ) } ) = ∏ j = i − w , j ≠ i i + w P r ( v j ∣ Φ ( v i ) ) Pr(\{v_{i-w},...,v_{i+2}\backslash v_{i}|\Phi(v_i)\})=\prod_{j=i-w, j\ne i}^{i+w}Pr(v_j|\Phi(v_i)) Pr({vi−w​,...,vi+2​\vi​∣Φ(vi​)})=j=i−w,j​=i∏i+w​Pr(vj​∣Φ(vi​))

通过负采样[13,14], 可以转化为：

$$minimiz{e}_{\Phi }log\sigma (\Phi (v_j{)}^T\Phi (v_i)+\sum _{t\in N(v_i{)}^{\prime }}log\sigma (-\Phi (v_t{)}^T\Phi (v_i)))$$

其中$N(v_i{)}^{\prime }$表示$v_i$的负样本，$\sigma (x)=\frac{1}{1+e^{-x}}$.经验上，负样本越多，效果越好。

2.4 Graph Embedding with Side Information

2.3的算法并没有解决冷启动的问题。为了解决冷启问题，我们加入附加信息，包括商品的类型，商店，价格等等。这些信息广泛的用在排序阶段，而匹配阶段比较少用。我们可以在匹配阶段假如这些信息。例如喜欢Nikon镜头的或许也喜欢Canon的劲头（相似的商品类别和相似的品牌）。这意味着有着相似附加信息的商品在嵌入空间内应该距离相近。基于这个假设，我们提出GES算法，如图3.

为了表达的简洁，我们用$W$表示embedding矩阵或附加信息。$W_v^0$表示商品v的embedding.$W_v^s$表示节点v相关的第s类附加信息。对于有n类附加信息的商品v,有n+1个向量$W_v^0,...,W_v^n\in R^d$。其中d表示嵌入空间的维度。注意我们经验地将物品和附加信息的空间纬度设置为相等。

如图3，我们连接这n+1个embedding向量并添加一个平均pooling操作：

$$H_v=\frac{1}{n+1}\sum _{s=0}^n{W}_v^s$$

2.5 Enhanced Graph Embedding with Side Information

GES假设各种的附加信息对embedding的贡献相等，但这个假设并非实际情况。为了解决这个问题，我们提出EGES算法。对于商品v, $A\in R^{|v|\times (n+1)}$表示权重矩阵，其中$A_{ij}$表示j类附加信息对于第i个物品的权重。我们用$a_v^s$表示s类附加信息对物品v的权重，$a_v^0$表示物品v本身的权重。然后$H_v$定义如下：

$$H_v=\frac{{\sum }_{j=0}^n{e}^{a_v^j}{W}_v^j}{{\sum }_{j=0}^n{e}^{a_v^j}}$$

对于节点v和它的上下文借点u,我们用$Z_u\in R^d$表示embedding ,y表示标记。则EGES的目标函数为：

$$L(v,u,y)=-[ylog(\sigma (H_v^T{Z}_u))+(1-y)log(1-\sigma (H_v^t{Z}_u))]$$