本文分享的论文题目是《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》

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

在淘宝的推荐中，主要面临着三个技术挑战，分别是可扩展性(scalability)、稀疏性(sparsity)、冷启动问题(cold start)。本文提出了一种图嵌入(graph embedding)的方法来解决上面的三个问题，一起来看下吧。

值得一提的是，在本系列的第三十六篇：
https://www.jianshu.com/p/285978e29458，我们介绍了阿里另一篇来做item embedding的文章，大家不妨先回顾一下。最后我们会对比一下这两种方法的区别。

1、背景

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

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

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

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

为了解决上面的这些问题，淘宝也采用了业界常用的两阶段框架，第一阶段称为匹配阶段，也可以叫做召回阶段，从大规模的商品集中召回一个比较小的候选集。第二阶段是排序阶段，对召回的候选集进行精确排序。

在召回阶段，主要的方法是计算商品之间的相似性，从而根据用户的历史交互行为得到用户可能喜欢的相似商品。计算商品的相似性，可以采用协同过滤的方法，但是协同过滤仅仅考虑了商品在交互矩阵中的共现性；使用图嵌入(Base Graph Embedding (BGE))的方法，比如随机游走的方法，可以学习到比较好的商品之间的相似性，但是对于出现次数很少甚至没有用户交互过的商品，依然难以有效地学习。

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

接下来，我们就来介绍三种方法，分别是Base Graph Embedding (BGE)、Graph Embedding with Side information (GES)和Enhanced Graph Embedding with Side information (EGES)。

2、模型介绍

2.1 Base Graph Embedding (BGE)

Base Graph Embedding (BGE)的完整流程可以参考下图：

首先，从用户的行为中抽取出序列表示，这里有两个地方需要注意：
1）如果使用用户整个的行为历史序列，计算和空间存储资源耗费巨大
2）用户的兴趣在长时间内是会变化的，但是用户短时间内的兴趣是相同的
基于以上两点原因，需要对用户的历史行为序列进行切割／这里以一小时为间隔，若两个商品的交互时间超过1小时，就进行切分。如图中的U2，E和D的时间间隔大于1小时，所以将序列切割为BE和DEF。

接下来，将所有的到的序列表示称有向带权图，如图中的D->A出现了一次，那么就会有一条从D指向A的边，同时边的权重记为1。再强调一次，这里是用所有用户经上一步的到的序列汇总起来得到一个有向带权图，而非每个用户对应于一张图。

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

1）点击之后用户停留时间小于1s，这可能是用户的误点击，需要过滤。
2）太过活跃的用户进行过滤，比如三个月内购买了1000件以上的商品，点击了3500个以上的商品。
3）同一个ID，但是发生变化的商品需要过滤。

在得到有向带权图之后，基于随机游走的方法产生一批序列，商品转移概率基于边的权重M_ij：

得到的序列举例如下：

随后，我们便可以通过Skip-Gram的方法来学习每个商品的向量啦。使用负采样的方式，我们的优化目标是：

感觉论文里这个地方写错了啊，应该是maxmize。前面的v_j是正样本，后面的v_t是采样得到的负样本。

还有一点我觉得值得商榷的是，对于Skip-Gram来说，每个商品对应了两个embedding，如下图：

最终获得的是商品在InputMatrix中对应的embedding，当前商品通过InputMatrix得到其Hidden Representation，然后与其计算dot product的应该是outputMatrix中商品的对应的embedding，所以感觉这里的符号表示有点问题。

2.2 Graph Embedding with Side information (GES)

上面的Base方法，可以较好的学习到item embedding，但是冷启动问题无法很好的解决。基于此，提出了Graph Embedding with Side information方法。为了与之前的item embedding区分开，在加入Side information之后，我们称得到的embedding为商品的aggregated embeddings。商品v的aggregated embeddings计作H_v。

aggregated embeddings的计算公式如下：

其中，W⁰代表item embedding，W¹,Wⁿ代表每种Side information对应的embedding。

具体的流程我们在下一节再细讲，因为GES和EGES的原理都是相通的。

2.3 Enhanced Graph Embedding with Side information (EGES)

正如前文的例子，比如一个购买了iphone的用户，倾向于查看mac或者ipad，更多的是因为他们都是苹果的牌子。因此不同的side information在最终的aggregated embeddings中所占的权重应该是不同的，所以此时的aggregated embeddings计算公式如下:

2.3 GES和EGES的学习

GES和EGES的流程如图：

此时损失函数可以表示为：

这里的Z_u应该是商品u在OutputMatrix中对应的embedding，通过反向传播进行学习：

这里有一个需要注意的地方，自身item embedding和每种side information的权重，对每个商品来说是不同的，并非采用相同的权重，权重通过反向传播算法进行学习，具体表示为：

item embedding 和 side-information对应的embedding同样通过反向传播学习：

3、实验分析

3.1 实验结果

这里主要进行了两部分的实验，离线实验和在线实验。

对于离线实验，对比了不同模型的AUC，咱们这里不是有正样本和负样本嘛，使用学习到的embedding 计算dot-product之后，将样本排序，计算AUC，结果如下：

在线实验，对比了不同模型下推荐结果的CTR：

可以看到，都是EGES方法效果最好。

3.2 案例分析

可视化embedding结果

对于学习到的embedding，通过PCA降维的方式将其展示出来：

可以看到结果中，足球、羽毛球和网球相关的商品基本都聚集在了一起。

解决冷启动问题

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

可以看到，通过这样的方式计算得到冷启动商品的embedding，其相似商品结果是比较好的。

EGES中的权重

前面提到过，自身item embedding和每种side information的权重，对每个商品来说是不同的。这里我们展示了部分商品对应的权重。

4、对比总结

与本系列第三十六篇相比，主要有下面两个不同吧。

1、本文混合了所有用户的交互序列构建了有向带权图，进一步通过随机游走的方式生成新的序列；而第三十六篇中方法直接使用用户的交互序列。感觉这两种方式都是可行的。本文以淘宝推荐为基础，商品数量巨大，通过随机游走的方式可以生成更多的训练集；而第三十六篇中方法终，以盒马鲜生推荐为基础，商品数量并没有那么多。
2、两篇文章对不同的side information都进行了加权，本文的权重是通过模型训练得到的，而第三十六篇文章中权重是预先定义好的。