论文：

论文地址：https://arxiv.org/abs/1803.02349

论文题目：《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》

一 、背景

我们在前面的airbnb那篇文章里面详细介绍了airbnb如何将list(房源)转化为低维的embedding，并运用这些得到的embedding运用到搜索任务的排序模型中，取得了不错的效果。在很多召回任务中，embedding被当作一个非常重要的特征去使用，例如，在youtube那边推荐系统论文中，将用户的embedding和视频的embedding训练出来后就可以直接计算相似度了，并用相似度计算的结果进行召回。

在淘宝的推荐中，主要面临着三个技术挑战，分别是可扩展性(scalability)、稀疏性(sparsity)、冷启动问题(cold start)。淘宝商城中的物品数量是十亿级别的，这么稀疏的情况下，迫切需要将这些高维稀疏的item转化为低维稠密低向量。同时，每天在淘宝上新的物品也是很多的，如果解决冷启动问题也是关键。基于以上考虑，淘宝提出了一种图嵌入(graph embedding)的方法来解决上面的三个问题。

在淘宝的推荐中，面临以下三个问题：

可扩展性(scalability)：一些现有的推荐系统方法，在小规模数据集上效果很好，但是在想淘宝这样的拥有十亿用户和二十亿商品的数据集上，表现得并不好。

稀疏性(sparsity)：用户仅与非常少的商品有过交互行为，这样的话很难精确训练一个推荐模型，也就是正负样本的比例过大。

冷启动(cold start)：在淘宝中，每个小时都有百万级别的新的商品上线，这些商品没有过用户行为，预测用户对这些商品的偏好是十分具有挑战性的。

为了解决上面的这些问题，淘宝也采用了业界常用的两阶段框架，第一阶段称为匹配阶段，也可以叫做召回阶段，从大规模的商品集中召回一个比较小的候选集。第二阶段是排序阶段，对召回的候选集进行精确排序，排序模型是一个深度神经网络模型。由于两个阶段的目标是不同的，从而导致了单独的技术解决方案。

前面提到了一般embedding都是运用在召回阶段的，youtube那篇文章就是向量召回的典范，因此本文的embedding策略也是着重于如何解决召回阶段的挑战，其中的核心任务是根据用户的行为计算所有物品之间的成对相似度。当然，有了物品之间的相似度，我们就可以进一步的得到召回的候选集并进行排序了。在以往，我们可以通过CF(协同过滤)的方法计算物品之间的相似度，回一下CF方法，我们通过jaccard方法计算了物品之间的相似度，并且根据这个相似度进行召回。但是协同过滤仅仅考虑了商品在交互矩阵中的共现性，相似度矩阵的计算要不断的进行更新，这也是一个比较棘手的问题。

除了CF方法外，还有运用图的随机游走策略来计算相似度。在之前的工作中，使用物品图中的随机游走策略，我们可以捕获项目之间的高阶相似性。因此，它优于基于CF的方法。但是，要得到几乎没有交互作用甚至没有交互作用的物品的准确embedding仍然是一个挑战。(我们将在下一篇文章中详细介绍随机游走，node2vec等embedding策略)。

因此，本文提出使用基于side information的图嵌入学习方法，称作Graph Embedding with Side information (GES)。这里的side information你可以理解为辅助信息，比如一个商品的品牌、店铺名、类别等等。使用side information来学习商品的embedding的话，同一个品牌或者类别的商品应当更相似。但是在淘宝中，有数以百计的side information，这些side information对于商品向量的贡献程度是不同的。考虑不同的side information对最终的item embedding的不同影响，这种方法称作Enhanced Graph Embedding with Side information (EGES)。

二 、模型结构

在第一章里面我们提到了GES和EGES，为了作为对比还介绍了一种BGE方法，所以总共需要介绍三种方法，分别是Base Graph Embedding (BGE)、Graph Embedding with Side information (GES)和Enhanced Graph Embedding with Side information (EGES)。

2.1 Base Graph Embedding (BGE)

BGE方法可以参考上面这张图，通过用户的点击序列构建item graph，并用random walk的方法构建序列，然后用skip-gram的方法训练出item embedding。

此外，从用户的行为中抽取出序列表示，我们需要注意到几点关键的地方。

一个是，如果使用用户的全部点击序列，那么对于这么多item，计算和空间成本将变得十分昂贵。

另一个是，用户的兴趣往往会随着时间而变化。 因此实际上，我们设置了一个时间窗口，并且仅在该窗口内选择用户的行为，这称为基于会话的用户行为。 根据经验，时间窗口的持续时间为一小时。这个跟我们之前session切分方式是一样的，切分的时间间隔一般是30min或者1h这样。就如同上面这张图中的u2，我们的session就切分为BE和DEF两部分。

根据上一步，我们得到了每个用户的session序列，接下来就是用这些session构建带权有向图了。如图中的B->E出现了一次，那么就会有一条从B指向E的带权边，同时边的权重为1。注意到，这里是用所有用户的session汇总起来得到一个有向带权图，并不是一个用户对应于一张图。

在实际应用中，需要对一些噪声信息进行过滤，主要有：

1）点击之后用户停留时间小于1s，这可能是用户的无意点击，需要过滤。

2）太过活跃的用户进行过滤，比如三个月内购买了1000件以上的商品，点击了3500个以上的商品。这是为了避免活跃用户对整个图造成过大对影响。

3）同一个ID，但是发生变化的商品需要过滤。

构建完带权有向图后，我们采用random walk的方法构建skip-gram所需要的“句子”。

其中是item i 到item j的权重，P(vj | vi)是转移的概率，N+是vi指向的所有item。

这样，我们就得到了要训练的序列：

接下来就是我们经典的skip-gram训练embedding的方法了：

这里应该是maxmize吧，极大似然法，让整个概率最大，后面的t是负采样得到的负样本。

2.2 Graph Embedding with Side information (GES)

上面的BGE方法，可以较好的学习到item embedding，但是冷启动问题无法很好的解决。基于此，提出了Graph Embedding with Side information方法。在电子商务中，side information是指商品的类别，商店，价格等，它在排序阶段被广泛用作关键特征，而在召回阶段却很少应用。我们可以通过在图嵌入中加入辅助信息来缓解冷启动问题。例如，优衣库（同一家商店）的两个帽衫（相同类别）可能看起来相似，并且喜欢尼康镜头的人也可能对佳能相机（相似类别和相似品牌）感兴趣。这意味着具有相似辅助信息的物品在嵌入空间中应该更靠近。

为了与之前的item embedding区分开，在加入side information之后，我们称得到的embedding为商品的aggregated embeddings。商品v的aggregated embeddings计作Hv。aggregated embeddings的计算公式如下：

其中，是item v的item embedding，是第s种side information的embedding，也就是将这些embedding作avg操作，然后得到aggregated embedding。

2.3 Enhanced Graph Embedding with Side information (EGES)

在GES中，aggregated embedding的计算就是所有的embedding简单的作平均，但是从现实中来看，每个side information 的embedding的重要性是不同的，比如商品的品牌就应该有更大的权重，比如一个用户喜欢购买苹果的产品，手机是iphone，电脑是mac，自然就能想到品牌应该占据更大的权重。

因此，需要对上面的公式进行改进，改为带权重的avg：

其中，是第j个side information的embedding的权重，但是我们为了让每个side information都有贡献，就取了e的指数次方，其实就是softmax来计算权重。

2.4 GES和EGES的训练方法

直接来看这个图，除了输入部分跟基本的skip-gram不一样，输出跟skip-gram是一样的，所以我们来解释一下输入部分。

输入部分就是我们之前说的带权avg操作，但是权重参数a是可学习的参数，这里可能论文提出的比较早，或许这里可以使用attention来操作一下。

损失函数：

其中，v是中心item，u是v的上下文的item，H跟Z分别代表他们的embedding，y是label。

前面说了a是学习的参数，主要是来源于论文中的一个公式：

这里可以看到a是需要学习的参数。

同样的其他的W的参数也是通过反向传播学习到：

三 、实验结果和冷启动问题

3.1 实验结果

当然，肯定是EGES效果最好。

3.2 冷启动问题

对于新加入的商品，我们使用其side information对应的embedding的均值来代替它的embedding，这样做的效果如下：

可以看到对于新加入的物品，用这种方法来代替它的embedding效果还是不错的。

side information的权重可视化：

可以看到，这种针对每一个item，本身的side information的权重都是不一样的，这也是因为权重参数a是训练出来的效果。