论文引用: Wang, Jizhe , et al. “Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba.” 2018.
本文是淘宝发表在 KDD 2018 上的关于商品 embedding 生成的文章，主要为了解决商品推荐系统面临三个主要问题：可扩展性、稀疏性和冷启动问题。其中，可扩展性是指随着用户量和商品量的急剧扩张，推荐系统的负载也随之增加，影响可扩展性的要素包括模型的训练开销、模型存储开销和推理性能等；稀疏性是指大部分用户只消费过小部分的商品，同时很多商品也只被少量用户消费，对于这些用户/商品很难做精准的推荐；而冷启动问题主要是针对新上架的商品，缺少用户行为，跟稀疏性类似，都会导致商品难以通过协同行为来评估相似度或质量。
为了解决这三个挑战，业内通常使用两阶段的推荐策略：召回+排序，先基于用户消费历史从商品库中召回与这些历史相似/相关的商品，再基于用户偏好来对这些候选商品进行排序。其中，召回阶段的核心是商品之间的相似度评估模型。
传统的 CF 方法主要是基于商品共现统计来评估商品间的相似度，例如 ItemCF 等，而本文首先基于用户行为构建商品的有向图，通过随机游走生成商品序列，再训练模型从这些序列中抽取商品间的相似度，这种方式能够捕获更高级别的相似度，类似于 SimRank 与 ItemCF 的关系 $^{[1]}$。EGES 使用 word2vec 进行训练，生成每个商品的 embedding，这种方式存储和推理都相当高效。
EGES 模型的训练有如下三个关键步骤：
- 构建商品的有向图；
- 随机游走生成商品序列；
- 训练模型生成商品的 embedding；
下面分别展开讨论。
1 构建商品的有向图
首先是如何建图。基于图编码来抽取商品相似度，主要是为了能直接捕获更高阶的商品相似度。假设一个用户在一段时间内的兴趣变化不大，这段时间称为一个 session（文章里按 1 小时来划分 session），那么可以认为用户在一个 session 内消费的所有商品具有一定的相关性。我们把商品抽象成图中的点，按用户消费的时间顺序将一个 session 内的商品用有向边依次连接，如下图所示，边权设置为 1（或者基于一些交互特征的函数，如停留时长）；把所有用户的所有 session 生成的这些有向图进行合并，边权相加，就能得到全网的商品有向图，记为 $\mathcal{G}=(\mathbb{V}, \mathbb{E})$，其中，$\mathbb{V}$ 表示节点集合，也就是商品的集合；$\mathbb{E}$ 表示带权有向边集合，连接点 $i$ 到 $j$ 的有向边权表示所有用户先消费物品 $i$ 再消费物品 $j$ 的频率。
在实际业务中进行建图时，我们还需要识别出对业务无效的行为，从而排除一些无效的边。比如，用户误点行为，通常表现为详情页停留时间过短；非正常用户行为，通常表现为行为相对于整体过于活跃，很可能是一些机器行为；非正常商品行为，比如商品的信息经常发生修改，甚至与上架时完全不同。这些无效行为如果加入模型训练，反而会影响商品的相似度评估，因此要在一开始就识别并排除掉。
2 随机游走生成商品序列
有了商品有向图后，我们就需要应用 graph embedding 技术来将代表商品的点映射到低维向量空间，同时保留图中局部拓扑结构信息。本文使用的方法就是对图进行采样，先基于图的边权来决定从一个点到其每个邻居节点的转移概率，再基于 random walk 之类的游走算法，来得到采样的序列，最后应用 word2vec 算法，将这些序列看成句子，生成每个节点的 embedding。
下面详细讨论下如何生成采样序列的问题。前面提到了，我们在建图的时候，边权的设置可以是用户消费过一个商品后又消费另一个商品的频次，或者是频次的加权结果，很自然的想到，如果两点间的边权越大，我们采样序列中，它们同时出现的概率也应该越大，也就是这两个点间的转移概率应该越大。记节点 $i,j$ 之间的边权为 $m_{i,j}$，可以将转移概率定义为边权的线性函数：
其中，$N_+(v_i)$ 表示节点 $i$ 在图 $\mathcal{G}$ 中指向的邻居节点集合。基于这个转移概率函数，我们得到采样序列的流程如下：先随机选择一个起始节点，然后每次使用 alias method $^{[2]}$ 来采样序列的下一个节点，直到当前节点没有邻居节点，或者达到最大序列长度。
除了这种简单的转移函数，node2vec 算法 $^{[3]}$ 还提出了一种有偏的随机游走策略，通过引入两个超参数来决定游走是偏向于向远离初始点的方向探索，还是围绕初始点附近进行探索，因此更加灵活，但是初始化的效率比较低。
3 训练模型生成商品的 embedding
得到采样序列的集合后，我们就可以用 word2vec 中的 negtive sampling + skipgram 算法来生成每个节点的 embedding，目标是最大化所有序列中节点共现的概率：
其中，$\Phi:\mathbb{V}\rightarrow \mathbb{R}^d$ 表示将节点映射为 $d$ 维 embedding 的函数；$N_-(v_i)$ 表示对 $v_i$ 随机生成的负样本节点集合；$\sigma(\cdot)$ 表示 sigmoid 函数。
回顾 word2vec，我们是基于节点的 ID 把每个节点映射成一个 embedding，这种方式的缺点在于只能处理出现频次大于一定阈值的节点，但是在例如淘宝的场景中，大量的商品（特别是新商品）被消费的次数很少，因此无法为这些商品生成 embedding。
实际上，这些商品是有一些元数据信息（side information）的，比如品牌、类别、价格、描述、海报等，这些信息本身就能被用于评估商品间的相似度。为了使用这些信息，文章进一步对商品每个类别的 side information 都映射到与 ID embedding 同维度的向量空间，然后将商品 ID embedding 和所有 side information 的 embedding 求和，得到商品 $v$ 的最终表示 $H_v$，再送到 softmax 网络中进行训练，如下图所示，其中 SI 0 表示 ID 维度。
再进一步，商品不同类别的 embedding 信息含量是不同的，例如在评估 iPhone 和 iMac 的相似度时，品牌信息的重要性更高；而在评估女性衣服相似度的时候，款式和价格因素的影响更大，因此文章增加权重矩阵 $\boldsymbol{A}\in \mathbb{R}^{|V|\times (n+1)}$，即为每个商品每个类别的 embedding 都分配一个可学习的权重 $a_{v,i}$，然后计算商品 $v$ 的加权 embedding：
其中，$\boldsymbol{W}_{v,j}$ 表示商品 $v$ 第 $j$ 个类别的 side information 对应的 embedding。把 $H_v$ 看成是 $v$ 的 input vector，记 $Z_u$ 表示商品 $u$ 的 output vector（即 $v$ 在 softmax 层中的 embedding），用 label $y$ 表示 $u$ 是否是 $v$ 的上下文节点，则 EGES 的目标函数定义为：
再基于梯度反向传播就能对参数 $\boldsymbol{W}, A, Z$ 进行更新了。
4 模型上线和效果评估
上面讲完了 EGES 的训练过程，其实 embedding 的离线评估是很困难的。文章提出一种连接预测的方式，也就是把图中随机选一些有向边作为正例，随机构造一些不存在的有向边作为负例来测试模型。除了这种方式，还可以通过选择一些典型的 case 来将各维度的 embedding 进行可视化，或者召回相似列表，看看是否满足主观预期，但是这种方式可以用来理解和优化，不适合用于评估。
将模型上线时，一般是根据训练好的模型预计算并缓存所有商品的 embedding，并基于 faiss 等 ANN 检索器构建索引，同时缓存所有 side information 的 embedding；对于新商品，在入库时就需要基于其 side information 查询相应的 embedding，然后求平均 embedding 作为新商品的 embedding 并缓存；需要基于种子商品进行召回时，先查询种子商品的 embedding，在线请求 ANN 相似结果。如果线上召回想更快点，就离线算出所有商品的 topN 相似商品并缓存。
参考文献
[1] SimRank与视频相似度计算. 胡诚. https://guyuecanhui.github.io/2019/04/29/simrank/
[2] 加权随机采样. 胡诚. https://guyuecanhui.github.io/2020/12/05/weighted-sample/
[3] Grover, Aditya , and J. Leskovec . “node2vec: Scalable Feature Learning for Networks.” the 22nd ACM SIGKDD International Conference ACM, 2016.