Learning and Transferring IDs Representation in E-commerce, KDD 2018

Abstract

该工作来自阿里，主要关注了如何学习ID的表示，从而在电商场景中用于推荐。在电商场景中ID包括user ID, item ID, product ID, store ID, brand ID, category ID等，传统的one-hot编码高维稀疏，并且无法反映ID之间的关联性（如同类或异类），本文提出了一种基于embedding的方法学习ID的表示，通过采集用户行为的ID序列，结合ID之间结构化的联系，将所有类型的ID嵌入到一个统一的低维空间用于之后的任务：（1）计算商品之间相似度（2）从观察到的商品迁移到未见过的商品（3）迁移到不同的领域（4）在不同任务中迁移。该模型在阿里旗下盒马鲜生业务中得到了有效的验证。

Introduction

传统方法将ID视为atomic units，用序号或one-hot编码表示。这些表示方式简洁、鲁棒，在统计模型中得到广泛的应用。然而这些表示方式具有以下两种局限：（1）特征维度高带来的稀疏问题，存储空间与ID数呈指数关系（2）无法反映ID之间的联系（如同类或异类）。在one-hot编码中任意两个item ID之间的距离是相同的，无论它们之间是否相似。而如果将item ID和store ID视为异类，由于二者处于不同的空间无法衡量。

目前embedding的技术从NLP领域的word2vec掀起，在诸多领域中得到了广泛的应用。word2vec将所有的word嵌入到统一的低维空间中，能够得到不同word之间句法和语义上的关系。item2vec通过建模item IDs在序列中co-occurrence，将item ID嵌入低维空间，用于提高搜索和电商中推荐的准确度。

本文基于item2vec提出一种embedding-based的框架，对于所有类型的ID学习并迁移其低维表示。除了使用用户的隐式反馈，还考虑了item ID与其他类型ID之间的结构化联系。通过这些联系，item ID序列表达的信息可以传播其他类型的ID中，同时学习得到所有类型ID的表示。所有类型的ID都将嵌入到同一个低维空间，这样就便于计算ID之间的相似度，判断其同类/异类。便于实际生产环境中部署、迁移学到的表示。

• Measuring Items Similarity
  • 通过计算embedding向量的余弦相似度，相比item-based CF召回率更高。
• Transferring from seen items to unseen items
  • 解决物品冷启动问题。使用已有的item ID的表示得到新item ID的表示。
• Transferring across different domains
  • Taobao to Hema
• Transferring across different tasks
  • store IDs learned by our approach can be transferred to this new task

Hema是一个online-to-offline(O2O)的平台，主要商品是生鲜，所以商品会经常更新，有很多新商品出现。并且Hema每天都会产生大量新用户，对于个性化推荐是一个极大的挑战。在传统的推荐系统中，用于计算user对于item的CTR。然而在该场景下，由于user-item对的数目巨大（$10^{15} -10^{20}$1015−1020）。在本文中，推荐框架分为以下四部分：

• Preparation user-to-trigger (u2t) 偏好度和trigger-to-item (t2i) 匹配度通过离线计算得到，存储在key-key-value数据库中用于在线提取。
• Matching 每次用户访问，首先根据user ID提取triggers。然后基于triggers得到推荐物品候选列表。
• Filtering 删除重复商品以及无效商品，例如已经卖完的商品
• Ranking 使用一个综合的分数（preference score, matching score,etc）对候选商品排序

其中候选集合的大小和计算的次数可以通过触发的数量来控制，整个系统非常灵活。触发的类型包括访问item，categories等。

模型

Skip-gram on User’s Interactive Sequences

在电商场景下，我们可以通过不同的交互会话得到item ID序列，其表明了用户的隐式反馈。我们将序列看作文档，skip-gram模型能够得到ID表示用于预测给定item ID得到其在序列中邻近的item ID。给定的一个item ID的序列 $\{ item_1,..., item_i,...,item_N\}${item1​,...,itemi​,...,itemN​},skip-gram模型的目标是最大化平均对数概率
$\frac{1}{N} \sum_{n=1}^{N} \sum_{-C\leq j \leq C}^{1 \leq n+j \leq N,j\neq 0} {\rm{log}} \ p(item_{n+j} | item_n)$N1​n=1∑N​−C≤j≤C∑1≤n+j≤N,j̸​=0​log p(itemn+j​∣itemn​)
C是上下文窗口的长度

其中在基本的skip-gram模型中，$p(item_j|item_i)$p(itemj​∣itemi​) 由softmax函数定义
$p(item_j|item_i) = \frac{{\rm exp}(\mathbf{e'}_j^{\rm T} \mathbf{e}_i)}{\sum_{d=1}^{D} {\rm exp}(\mathbf{e'}_d^{\rm T} \mathbf{e}_i)}$p(itemj​∣itemi​)=∑d=1D​exp(e′dT​ei​)exp(e′jT​ei​)​
其中$\mathbf{e'}$e′ 和$\mathbf{e}$e分别为context representation和target representation。D是item ID字典的大小。

Log-uniform Negative-sampling

对$ {\rm{log}} \ p(item_{n+j} | item_n)$ 求导的计算复杂度与D成正比，当D非常大时难以计算。需要采用负采样，将softmax函数替代为
$p(item_j | item_i) = \sigma(\mathbf{e'}_j^{\rm T} \mathbf{e}_i) \prod_{s=1}^{S} \sigma(\mathbf{e'}_s^{\rm T} \mathbf{e}_i))$p(itemj​∣itemi​)=σ(e′jT​ei​)s=1∏S​σ(e′sT​ei​))
其中 $\sigma(x) = \frac{1}{1+exp(-x)}$σ(x)=1+exp(−x)1​ 为sigmoid函数，S是负样本数目

NCE需要采样和噪声分布的数值概率，而负采样只需要采样。对于在所有item ID的上下文中都出现的item ID，其提供不了有效的信息，使用log-uniform负采样进行平衡。负样本从Zipfian分布得到。某个item ID出现的概率与其在所有ID中的序号成反比。为了加速负采样过程，首先对item根据频率进行降序排序为[0，D-1]的序号。我们采用zipfian分布估计
$p(\rm index) = \frac{\rm {log(index + 2) - log(index +1)}}{log(D +1)}$p(index)=log(D+1)log(index+2)−log(index+1)​
累计分布为
$F（x） = p(x\leq index) \\ = \sum_{i=0}^{index}{ \frac{\rm {log(index + 2) - log(index +1)}}{log(D +1)}} \\ = \frac{\rm {log(index +2）}}{\rm log(\mathit D +1)}$F（x）=p(x≤index)=i=0∑index​log(D+1)log(index+2)−log(index+1)​=log(D+1)log(index+2）​
设 $F(x) =r$F(x)=r 其中r是在[0,1)均匀分布中得到的随机值，那么可得
$index = (D+1)^r -2$index=(D+1)r−2

IDs and Their Structural Connections

ID分为两组：

（1）item ID和属性IDs

​ item ID，product ID，brand ID，cate-level1 ID，cate-level2 ID，cate-level3 ID

（2）user ID

联合训练itemID和属性IDs

本文提出一种分层的embedding模型联合学习item ID和属性IDs的低维表示。如下图所示，item ID是交互的核心单元，与属性IDs的联系用虚线表示。item ID的共现也表明了属性ID的共现，用实箭头表示。

假设第一类ID共有K种，$\rm IDs(item_i) = [id_1(item_i),...,id_k(item_i),...,id_K(item_i)]$IDs(itemi​)=[id1​(itemi​),...,idk​(itemi​),...,idK​(itemi​)] 其中 $\rm id_1(item_i) = item_i,id_2(item_i) = product ID,id_3(item_i) = store ID$id1​(itemi​)=itemi​,id2​(itemi​)=productID,id3​(itemi​)=storeID，则有

其中 ${\bf e}'_{\cdot k} \in {\bf E}'_k( R ^{m_k \ D_k} )$e⋅k′​∈Ek′​(Rmk​ Dk​)

${\bf E}'_k$Ek′​ 和 ${\bf E}_k$Ek​ 分别为第k个类型ID的上下文矩阵和目标矩阵

$p({\rm item}_i |{\rm IDs(item}_i ) = \sigma (\sum_{k=2}^{K}w_{ik}{\bf e}_{i1}^{\rm T}{\bf M}_k{\bf e}_{ik})$p(itemi​∣IDs(itemi​)=σ(k=2∑K​wik​ei1T​Mk​eik​)
其中 ${\bf M}_k \subset R^{m_1 \times m_k } (k=2,...,K)$Mk​⊂Rm1​×mk​(k=2,...,K) 是一个矩阵用于从embedding向量 ${\bf e}_{i1}$ei1​ 转移到 ${\bf e}_{ik}$eik​。最终最大化目标函数：

实验设置

计算物品相似度-TopN推荐

对于每个用户u，其有过行为的商品列表为 $SEED(u)$SEED(u) ，遍历$SEED(u)$SEED(u)，取其中每个商品top-N相似度的商品，构成候选推荐商品列表。

实验结果表明，该方法召回率比item-based CF更高。

embedding从已有item迁移到新item

许多已有的推荐算法无法解决物品冷启动问题，如item-based CF、item2vec；在本文中使用估计新item的embedding向量来解决冷启动问题。

basic idea：新item ID所连接的IDs通常有历史记录，例如对于一个新item，其product在某个地方有销售过，这个商场还卖了其他东西。因此我们可以根据新item ID连接的IDs构造一个近似的embedding向量。由于 $\sigma$σ 是一个单调递增函数，所以有：

最大化目标函数将使得 $p(item_i | IDs(item_i)) \to 1$p(itemi​∣IDs(itemi​))→1 则可得

其中只考虑有历史数据的 $ id_k$。构造得到

${\mathbf e}_{i1} \approx \sum_{k=2}^{K} w_{ik}\mathbf{e}_{ik}^{{\rm T}} {\mathbf M}_{k}^{\rm T}$ei1​≈k=2∑K​wik​eikT​MkT​

这个trick值得关注：当两个向量的乘积非常大，则将二者近似相等。

跨领域迁移

从Taobao迁移到Hema，解决新用户的个性化推荐问题（用户冷启动）。假设 $U^s$Us是源领域的用户集合，$U^t$Ut是目标领域的用户集合。$U^i$Ui是它们的交集。

1. 首先 $U^s$Us 由用户在Taobao有过行为的item IDs的embedding聚合得到。
2. $U^i$Ui中的用户通过k-means根据embedding相似度分成1000组
3. 对于每一组，流行度topN的Hema items被选为推荐集合
4. $U^s \backslash U^t$Us\Ut（属于s但不属于t）的新用户根据用户向量和组的中心距离被分配到最相似的组
5. 将分配到的组所对应的推荐集合返回

本质上该方法类似user-based CF，找到新用户最相似的用户，然后推荐其相关的商品。

其中聚合item向量的方式有简单平均和加权平均两种。在加权平均方式中，对于item不同行为具有不同的权重，如购买行为比点击行为权重高。

跨任务迁移

销售预测在电商决策中非常重要，可以帮助管理人力分配，现金流，资源等，例如优化商品配送。在本文中考虑的问题是预测每个商店第二天每30分钟的配送需求。该预测结果可以指导配送人员数量的预先分配。

我们使用学习得到的store ID向量来表示store而不用one-hot编码，将历史销售数据和embedding向量作为输入，多个全连接层+非线性**函数得到高阶表示。
$\mathbf{h}_i = a(\mathbf{W}_i \mathbf{h}_{i-1} + \mathbf{b}_i)$hi​=a(Wi​hi−1​+bi​)
最后使用线性回归预测配送需求 $\hat{y}_i$y^​i​：
$\hat{y}_i = \mathbf{w}^{{\rm T}} \mathbf{h}_N + b$y^​i​=wThN​+b
在实验中使用了5层的全连接层，每层大小为128。衡量指标为RMAE，$y_i$yi​ 为实际配送需求。
${\rm RMAE} = \frac{\sum_{i=1}^{N}| y_i - \hat y_i |}{\sum_{i=1}^{N} y_i}$RMAE=∑i=1N​yi​∑i=1N​∣yi​−y^​i​∣​