一、MIND [2019]

《Multi-Interest Network with Dynamic Routing for Recommendation at Tmall》

1. 天猫是中国最大的 Business-To-Customer: B2C 电商平台，它在线提供十亿规模的商品，服务于十亿规模的用户。2018 年 11 月 11 日，著名的天猫全球购物节，商品交易总额（Gross Merchandise Volume: GMV）大约为 2130 亿元，较 2017 年同期增长 26.9% 。随着用户和商品的不断增长，帮助每个用户找到他 / 她可能感兴趣的商品变得越来越重要。近年来，天猫在开发个性化推荐系统方面付出了巨大的努力，极大地促进了用户体验的优化以及商业价值的提升。例如，占天猫总流量一半左右的移动天猫 App 首页（如下图左图所示），就部署了推荐系统来展示个性化商品，从而满足客户的个性化需求。

   由于拥有十亿规模的用户和 item，天猫的推荐流程分为 matching 阶段和 ranking 阶段两个阶段。matching 阶段负责检索与用户兴趣相关的数千个候选 item，然后 ranking 阶段负责预测用户与这些候选 item 交互的精确概率。对于这两个阶段，为了支持对满足用户兴趣的 item 的高效检索，建模用户兴趣并得到捕获用户兴趣的用户 representation 至关重要。然而，由于用户兴趣的多样性（ diversity ），在天猫上建模用户兴趣并非易事。平均而言，十亿级用户访问天猫，每个用户每天与数百种商品进行交互。交互的商品往往隶属不同的类目，暗示了用户兴趣的多样性。例如，如下图右图所示，不同用户的兴趣是不同的，同一用户也可能对不同的 item 感兴趣。因此，捕获用户多样化兴趣（diverse interests）的能力对天猫的推荐系统而言至关重要。

   注：下图中，左图的虚线矩形区域是天猫的十亿规模用户的个性化区域；右图是两个用户和不同类目商品的交互。

   

   现有的推荐算法以不同的方式建模和表示用户兴趣：

   • 基于协同过滤的方法通过历史交互 item 或潜在因子来表示用户兴趣，这些方法存在数据稀疏问题、或者计算复杂度太高的问题。

   • 基于深度学习的方法通常用低维 embedding 向量表示用户兴趣。例如，为 YouTube 视频推荐提出的深度神经网络（YouTubeDNN）通过一个固定长度的向量来表示每个用户，该向量是由用户历史行为转换而来。这可能是建模多样化兴趣的瓶颈，因为它的维度必须很高，从而表达天猫上的、大量的兴趣画像。

     深度兴趣网络（Deep Interest Network: DIN）通过注意力机制来捕获用户兴趣的多样性，使得用户在不同目标 item 上的用户 representation 不同。然而，注意力机制的采纳也使得具有十亿级 item 的大规模应用在计算上受到限制，因为它需要重新计算每个目标 item 的用户 representation ，使得 DIN 仅适用于 ranking 阶段。

   论文 《Multi-Interest Network with Dynamic Routing for Recommendation at Tmall》 关注于在 matching 阶段对用户的多样化兴趣进行建模的问题。为了克服现有方法的局限性，论文提出了具有动态路由的多兴趣网络（Multi-Interest Network with Dynamic routing: MIND） 。MIND 用于工业级推荐系统在 matching 阶段学习反映用户的多样化兴趣的 representation 。

   为了推断用户 representation 向量，论文设计了一个称为多兴趣提取器层（multi-interest extractor layer），它利用动态路由将用户的历史行为自适应地聚合到用户 representation 中。动态路由的过程可以视为软聚类 （soft-clustering），它将用户的历史行为分为几个簇。每个历史行为簇进一步用于推断对应于一个特定兴趣的用户 representation 向量。这样，对于特定的用户，MIND 输出多个 represenation 向量，它们共同代表了用户的多样化兴趣。用户 representation 向量只需要计算一次，就可以用于 matching 阶段从而在十亿级 item 中检索相关 item。总而言之，这项工作的主要贡献：

   • 为了从用户行为中捕获用户的不同兴趣，论文设计了多兴趣提取器层，该层利用动态路由自适应地将用户的历史行为聚合为用户 representation 向量。

   • 通过使用多兴趣提取器层、以及新提出的标签感知注意力层（label-aware attention layer）所产出的用户 representation 向量，论文为个性化推荐任务构建了一个深度神经网络。与现有的方法相比，MIND 在多个公共数据集和一个来自天猫的工业数据集上表现出优越的性能。

   • 为了在天猫部署 MIND 从而服务于十亿级用户，论文构建了一个系统来实现数据集采集、模型训练、以及在线 serving 的整个 pipeline。部署的系统显著提高了移动天猫 App 首页的点击率（ click-through rate: CTR）。目前MIND 已经在 Mobile Tmall App 首页上部署从而处理主要的在线流量。

2. 相关工作：

   • 深度学习推荐：受深度学习在计算机视觉和自然语言处理中成功应用的启发，人们投入了大量努力来开发基于深度学习的推荐算法。除了 《Deep neural networks for youtube recommendations》 和 《Deep interest network for click-through rate prediction》 之外，各种类型的深度模型也得到了极大的关注。

     • 神经协同过滤（Neural Collaborative Filtering: NCF）、DeepFM、和深度矩阵分解（Deep Matrix Factorization Model: DMF）构建了一个由若干 MLP 组成的神经网络，从而对用户和 item 之间的交互进行建模。

     • 《Personalized top-n sequential recommendation via convolutional sequence embedding》 通过提供一个统一且灵活的网络来捕获更多特征，为 top-N 序列推荐提供了一个新颖的解决方案。

   • 用户 Representation：将用户表示为向量是推荐系统中常见的做法。

     传统方法将用户感兴趣的 item、用户感兴趣的关键词、用户感兴趣的主题拼接起来，从而构成用户偏好向量。随着 distributed representation learning 的出现，通过神经网络获取 user embedding 得到了广泛的应用。

     • 《Learning user and product distributed representations using a sequence model for sentiment analysis》 使用 RNN-GRU 从时间有序的 review documents 中学习 user embedding。

     • 《User embedding for scholarly microblog recommendation》 从 word embedding 向量中学习 user embedding 向量，并将其应用于推荐学术微博（scholarly microblog）。

     • 《Modelling Context with User Embeddings for Sarcasm Detection in Social Media》 提出了一种新的、基于卷积神经网络的模型，该模型显式地学习和利用 user embedding 以及从话语（utterances）中获得的特征。

   • 胶囊网络（Capsule Network）：”胶囊” 的概念表示一组神经元组装而成的向量，它由 Hinton 在 2011 年首次提出。动态路由（ dynamic routing）用于学习胶囊之间连接的权重，该学习方法不是基于反向传播，而是基于 Expectation-Maximization: EM 算法，从而克服几个缺陷并获得更好的准确性。与传统神经网络的这两个主要区别（由一组神经元组成、通过 EM 算法学习）使得胶囊网络能够对部分和整体之间的关系进行编码，这在计算机视觉和自然语言处理方面是先进的。SegCaps 证明，胶囊可以比传统的 CNN 更好地建模对象的空间关系。

     《Investigating Capsule Networks with Dynamic Routing for Text Classification》 研究了用于文本分类的胶囊网络，并提出了三种提高性能的策略。

1.1 模型

1. 工业推荐系统 matching 阶段的目标是为每个用户 $u\in \mathcal{U}$$u\in \mathcal U$ 从十亿规模的 item 库 $\mathcal{I}$$\mathcal I$ 中检索仅包含数千个item 的item 子集，其中该子集中每个 item 都和用户的兴趣相关。

   为了实现该目标，我们收集用户历史行为数据从而构建 matching 模型。具体而言，每个样本都可以用一个元组 $({\mathcal{I}}_u,{\mathcal{P}}_u,{\mathcal{F}}_i)$$(\mathcal I_u,\mathcal P_u,\mathcal F_i)$ ，其中：

   • ${\mathcal{I}}_u$$\mathcal I_u$ 表示用户 $u$$u$ 交互的 item 集合，也称作用户行为。

   • ${\mathcal{P}}_u$$\mathcal P_u$ 为用户 $u$$u$ 的基础画像，如性别、年龄。

   • ${\mathcal{F}}_i$$\mathcal F_i$ 为target item $i$$i$ 的特征，如 item id、category id 。

     注意：target item $i$$i$ 不一定隶属于 ${\mathcal{I}}_u$$\mathcal I_u$ ，即用户 $u$$u$ 不一定在 target item $i$$i$ 上有过互动行为。

   MIND 的核心任务是学习将原始特征映射到用户representation 的函数，即：

   $${\mathcal{V}}_u=f_{\text{user}}({\mathcal{I}}_u,{\mathcal{P}}_u)$$

   其中 ${\mathcal{V}}_u=\{{\overrightarrow{\mathbf{v}}}_u^{(1)},\cdots ,{\overrightarrow{\mathbf{v}}}_u^{(K)}\}$$\mathcal V_u=\left\{\mathbf{\vec v}_u^{(1)},\cdots,\mathbf{\vec v}_u^{(K)}\right\}$ 为用户 $u$$u$ 的 $K$$K$ 个 representation 向量，向量维度为 $d$$d$ 。当 $K=1$$K=1$ 时，每个用户仅使用单个representation 向量，就像 YouTube DNN 一样。

   此外，通过 embedding 函数获得 target item $i$$i$ 的 representation 向量为：

   $${\overrightarrow{\mathbf{e}}}_i=f_{\text{item}}({\mathcal{F}}_i)$$

   其中 ${\overrightarrow{\mathbf{e}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec e}_i\in \mathbb R^{d }$ 表示item $i$$i$ 的 representation 向量。$f_{\text{user}},f_{\text{item}}$$f_{\text{user}},f_{\text{item}}$ 的详细信息在后文说明。

   当学习了用户 representation 向量、 item representation 向量之后，在线 serving 时根据评分函数检索 top N 候选item：

   $$f_{\text{score}}({\mathcal{V}}_u,{\overrightarrow{\mathbf{e}}}_i)=\underset{1\le k\le K}{max}{\overrightarrow{\mathbf{e}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_u^{(k)}$$

   其中 $N$$N$ 时在 matching 阶段要检索的、预定义的item 数。注意：$f_{\text{score}}$$f_{\text{score}}$ 仅用于serving 阶段，而不用于训练阶段。

2. 如下图所示，MIND 将用户行为序列、用户画像、label item 等特征作为输入，然后输出用户 representation 从而用于推荐系统的 matching 阶段来检索 item。

   MIND 主要由以下部分组成：

   • Embedding&Pooling Layer：来自输入层的 id 特征通过 embedding 层转换为 embedding ，然后每个 item 的各种id embedding 由池化层进一步取平均。

   • Multi-Interest Extractor Layer：用户行为 embedding 被馈入多兴趣提取器层从而产生兴趣胶囊。通过将兴趣胶囊和用户画像 embedding 拼接，然后经过几个 ReLU 的全连接层进行转换，可以得到用户 representation 向量。

   • Label-aware Attention Layer：在训练过程中引入一个额外的标签感知注意力层，从而指导训练过程。

   最后在serving 过程中，用户的多个 representation 向量用于通过最近邻检索来检索item 。

   

3. Embedding&Pooling Layer： MIND 的输入包含三组：用户画像 ${\mathcal{P}}_u$$\mathcal P_u$、用户行为 ${\mathcal{I}}_u$$\mathcal I_u$、label item ${\mathcal{F}}_i$$\mathcal F_i$ ，每组输入包含几个具有极高维数的 categorical id 特征。例如，item id 的数量约为数十亿个，因此我们采用了广泛使用的 embedding 技术将这些 ID 特征嵌入到低维稠密向量（也称作 embedding 向量）中，从而显著减少了参数数量并简化了学习过程。

   • 对于来自用户画像 ${\mathcal{P}}_u$$\mathcal P_u$ 的 id 特征（性别、年龄等），对相应的 embedding 进行拼接从而构成用户画像 embedding ${\overrightarrow{\mathbf{p}}}_u$$\mathbf{\vec p}_u$ 。

   • 对于 item 的item id 以及其它 categorical id（如品牌 id、店铺id 等），这些 id 被证明有助于 label item ${\mathcal{F}}_i$$\mathcal F_i$ 的冷启动，相应的 embedding 会进一步通过均值池化层从而形成 label item embedding ${\overrightarrow{\mathbf{e}}}_i$$\mathbf{\vec e}_i$ ，即 $f_{\text{item}}$$f_{\text{item}}$ 函数。

   • 对于来自用户行为 ${\mathcal{I}}_u$$\mathcal I_u$ 的 item，收集相应的 item embedding 从而形成用户行为 embedding ${\mathcal{E}}_u=\{{\overrightarrow{\mathbf{e}}}_i\mid i\in {\mathcal{I}}_u\}$$\mathcal E_u=\left\{\mathbf{\vec e}_i\mid i\in \mathcal I_u\right\}$ ，这些 embedding 构成了用户行为 embedding 矩阵 ${\mathbf{E}}_u$$\mathbf E_u$。

1.1.1 Multi-Interest Extractor Layer

1. 我们认为，用一个 representation 向量表示用户兴趣可能是捕获用户的多样化兴趣的瓶颈，因为我们必须将与用户的多样化兴趣相关的所有信息压缩到一个representation 向量中。因此，关于用户的不同兴趣的所有信息都被混合在一起，从而导致在 matching 阶段的 item 检索不准确。

   相反，我们采用多个representation 向量分别表达用户的不同兴趣。通过这种方式，我们可以在 matching 阶段分别考虑用户的多样化兴趣，从而可以更准确地检索各个方面的兴趣。

   为了学习多个 representation 向量，我们利用聚类过程将用户的历史行为分组为几个簇（cluster）。我们预期来自同一个簇的 item 将密切相关，并且共同代表了用户在某个特定方面的兴趣。这里，我们设计了多兴趣提取器层（multi-interest extractor layer），从而用于聚类历史行为，并得到结果聚类的representation 向量。

   由于多兴趣提取器层的设计受到最近提出的、用于胶囊网络（capsule network）中 representation learning 的动态路由（dynamic routing）的启发，因此我们首先回顾基础知识。

2. 动态路由（Dynamic Routing）：我们简单介绍用于胶囊网络表示学习的动态路由，这是一种以向量表示的、新型的神经元。

   假设我们有两层胶囊，分别将第一层胶囊和第二层胶囊称作低层胶囊（low-level capsule）、高层胶囊（high-level capsule）。动态路由的目标是以迭代的方式在给定低层胶囊值的情况下计算高层胶囊值。

   在每次迭代中，给定低层胶囊 $i\in \{1,2,\cdots ,m\}$$i\in \{1,2,\cdots,m\}$ 对应的值 $\{{\overrightarrow{\mathbf{c}}}_1^{(l)},\cdots ,{\overrightarrow{\mathbf{c}}}_m^{(l)}\}$$\left\{\mathbf{\vec c}_1^{(l)},\cdots,\mathbf{\vec c}_m^{(l)}\right\}$ 、以及高层胶囊 $j\in \{1,2,\cdots ,n\}$$j\in \{1,2,\cdots,n\}$ 对应的值 $\{{\overrightarrow{\mathbf{c}}}_1^{(h)},\cdots ,{\overrightarrow{\mathbf{c}}}_n^{(h)}\}$$\left\{\mathbf{\vec c}_1^{(h)},\cdots,\mathbf{\vec c}_n^{(h)}\right\}$ ，其中 ${\overrightarrow{\mathbf{c}}}_i^{(l)}\in {\mathbb{R}}^{N_l},{\overrightarrow{\mathbf{c}}}_j^{(h)}\in {\mathbb{R}}^{N_h}$$\mathbf{\vec c}_i^{(l)}\in \mathbb R^{N_l },\mathbf{\vec c}_j^{(h)}\in \mathbb R^{N_h }$ ，$N_l,N_h$$N_l, N_h$ 分别为低层 value vector 和高层 value vector 的维度。

   则低层胶囊 $i$$i$ 和高层胶囊 $j$$j$ 之间的 routing logit $b_{i,j}$$b_{i,j}$ 为：

   $$b_{i,j}={\left({\overrightarrow{\mathbf{c}}}_j^{(h)}\right)}^{\mathrm{\top }}{\mathbf{S}}_{i,j}{\overrightarrow{\mathbf{c}}}_i^{(l)}$$

   其中 ${\mathbf{S}}_{i,j}\in {\mathbb{R}}^{N_h\times N_l}$$\mathbf S_{i,j}\in \mathbb R^{N_h\times N_l}$ 为待学习的双线性映射矩阵。

   当计算好routing logit之后，高层胶囊 $j$$j$ 的 value vector 更新为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{z}}}_j^{(h)}=\sum _{i=1}^m{w}_{i,j}{\mathbf{S}}_{i,j}{\overrightarrow{\mathbf{c}}}_i^{(l)},w_{i,j}=\frac{\exp (b_{i,j})}{\sum _{k=1}^m\text{exp}(b_{i,k})}\\ {\overrightarrow{\mathbf{c}}}_j^{(h)}=\text{squash}\left({\overrightarrow{\mathbf{z}}}_j^{(h)}\right)=\frac{{\Vert {\overrightarrow{\mathbf{z}}}_j^{(h)}\Vert }^2}{1+{\Vert {\overrightarrow{\mathbf{z}}}_j^{(h)}\Vert }^2}\times \frac{{\overrightarrow{\mathbf{z}}}_j^{(h)}}{\Vert {\overrightarrow{\mathbf{z}}}_j^{(h)}\Vert }\end{array}$$

   其中：

   • ${\overrightarrow{\mathbf{z}}}_j^{(h)}$$\mathbf{\vec z}_j^{(h)}$ 为所有低层胶囊值向量的加权和。加权和的权重 $w_{i,j}$$w_{i,j}$ 表示低层胶囊 $i$$i$ 和高层胶囊 $j$$j$ 的权重，是通过对 routing logit 进行 softmax 来计算的。

   • 非线性的 squash 函数用于获得高层胶囊的值向量。

   另外，$b_{i,j}$$b_{i,j}$ 的值将被初始化为零。

   整个路由过程通常需要 3 轮迭代才会收敛。路由结束后，高层胶囊的值向量 ${\overrightarrow{\mathbf{c}}}_j^{(h)}$$\mathbf{\vec c}_j^{(h)}$ 通常会固定不变，并且可以用于下一层 layer 的输入。

3. B2I 动态路由：简而言之胶囊是一种由向量表示的神经元，而不是普通神经网络中标量表示的神经元。我们期待基于向量的胶囊能够代表实体的不同属性，其中向量的方向代表一种属性、向量的长度代表该属性存在的概率。

   相应地，多兴趣提取器层的目标是学习用于表达用户兴趣、以及是否存在相应兴趣的 representation。胶囊和兴趣representation 之间的语义联系促使我们将行为/兴趣 representation 视为行为/兴趣胶囊，并采用动态路由从行为胶囊（behavior capsule）中学习兴趣胶囊（interest capsule）。

   然而，针对图像数据提出的原始路由算法并不能用于直接处理用户行为数据。因此，我们提出了 Behavior-to-Interest:B2I 动态路由，用于将用户的行为自适应地聚合到兴趣representation 向量中，这和原始路由算法在三个方面有所不同：

   • 共享双线性映射矩阵：基于两方面的考虑，我们将每对低层胶囊和高层胶囊 pair 对之间使用固定的双线性映射矩阵 $\mathbf{S}$$\mathbf S$ ，而不是在原始动态路由中独立的双线性映射矩阵：

     • 一方面，用户行为序列的长度是可变的，天猫用户的行为序列长度从几十到几百，因此使用共享的双线性映射矩阵更为泛化（generalizable）。

     • 另一方面，我们希望兴趣胶囊位于相同的向量空间中，而不同的双线性映射矩阵会将兴趣胶囊映射到不同的向量空间中。

     因此，routing logit 计算为：

     $$b_{i,j}={\overrightarrow{\mathbf{u}}}_j^{\mathrm{\top }}\mathbf{S}{\overrightarrow{\mathbf{e}}}_i,i\in {\mathcal{I}}_u,j\in \{1,2,\cdots ,K\}$$

     其中：

     • ${\overrightarrow{\mathbf{e}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec e}_i \in \mathbb R^d$ 为behavior item $i$$i$ 的 embedding。

     • ${\overrightarrow{\mathbf{u}}}_j\in {\mathbb{R}}^d$$\mathbf{\vec u}_j \in \mathbb R^d$ 为 interest capsule $j$$j$ 的向量，一共有 $K$$K$ 个兴趣。

     • 双线性映射矩阵 $\mathbf{S}\in {\mathbb{R}}^{d\times d}$$\mathbf S\in \mathbb R^{d\times d}$ 在每对行为胶囊和兴趣胶囊pair 对之间共享。

   • 随机初始化 routing logit ：由于使用了共享的双线性映射矩阵 $\mathbf{S}$$\mathbf S$，将 routing logit 初始化为零导致所有用户具有相同的初始兴趣胶囊。然后在随后的每一轮迭代中，不同用户之间在当前轮次具有相同的兴趣胶囊。（注：不同迭代步之间的取值不同，但是同一迭代步之内的取值都相同）。

     为了缓解这种现象，我们从高斯分布 $\mathcal{N}(0,{\sigma }^2)$$\mathcal N(0,\sigma^2)$ 中抽样一个随机矩阵作为初始 routing logit ，使得初始兴趣胶囊彼此不同。这和著名的 K-Means 聚类算法的随机初始化类似。

   • 动态兴趣数量：由于不同用户的兴趣数量可能不同，因此我们引入了一种启发式规则，用于针对不同用户自适应地调整 $K$$K$ 的值。

     具体而言，用户 $u$$u$ 的 $K$$K$ 值通过以下公式计算：

     $$K_u^{\prime }=max(1,min(K,{\log }_2(|{\mathcal{I}}_u|)))$$

     这种调整兴趣数量的策略可以为那些兴趣较少的用户节省一些资源，包括计算资源、内存资源。

4. B2I Dynamic Routing 算法：

   • 输入：

     • 用户 $u$$u$ 的行为embedding 集合 $\{{\overrightarrow{\mathbf{e}}}_i\mid i\in {\mathcal{I}}_u\}$$\left\{\mathbf{\vec e}_i\mid i\in \mathcal I_u\right\}$

     • 迭代轮次 $r$$r$

     • 兴趣胶囊数量 $K$$K$

   • 输出：用户 $u$$u$ 的兴趣胶囊集合 $\{{\overrightarrow{\mathbf{u}}}_j\mid j=1,\cdots ,K_u^{\prime }\}$$\left\{\mathbf{\vec u}_j\mid j=1,\cdots,K_u^\prime \right\}$

   • 算法步骤：

     • 计算自适应的兴趣胶囊数量：

       $$K_u^{\prime }=max(1,min(K,{\log }_2(|{\mathcal{I}}_u|)))$$

     • 对于所有的行为胶囊 $i$$i$ 和兴趣胶囊 $j$$j$ ，随机初始化 $b_{i,j}\sim \mathcal{N}(0,{\sigma }^2)$$b_{i,j}\sim \mathcal N(0,\sigma^2)$

     • 迭代 $k=1,2,\cdots ,r$$k=1,2,\cdots,r$，迭代步骤为：

       • 对于所有行为胶囊 $i$$i$ ：$w_{i,j}=\text{softmax}(b_{i,j})$$w_{i,j} = \text{softmax}(b_{i,j})$

       • 对于所有兴趣胶囊 $j$$j$ ：${\overrightarrow{\mathbf{z}}}_j=\sum _{i\in {\mathcal{I}}_u}{w}_{i,j}\mathbf{S}{\overrightarrow{\mathbf{e}}}_i$$\mathbf{\vec z}_j =\sum_{i\in \mathcal I_u} w_{i,j}\mathbf S \mathbf{\vec e}_i$

       • 对于所有兴趣胶囊 $j$$j$ ：${\overrightarrow{\mathbf{u}}}_j=\text{squash}\left({\overrightarrow{\mathbf{z}}}_j\right)=\frac{{\Vert {\overrightarrow{\mathbf{z}}}_j\Vert }^2}{1+{\Vert {\overrightarrow{\mathbf{z}}}_j\Vert }^2}\times \frac{{\overrightarrow{\mathbf{z}}}_j}{\Vert {\overrightarrow{\mathbf{z}}}_j\Vert }$$\mathbf{\vec u}_j = \text{squash}\left(\mathbf{\vec z}_j \right)=\frac{\left\|\mathbf{\vec z}_j \right\|^2}{1+\left\|\mathbf{\vec z}_j \right\|^2}\times \frac{\mathbf{\vec z}_j }{\left\|\mathbf{\vec z}_j \right\|}$

       • 对于所有的行为胶囊 $i$$i$ 和兴趣胶囊 $j$$j$ ：$b_{i,j}=b_{i,j}+{\overrightarrow{\mathbf{u}}}_j^{\mathrm{\top }}\mathbf{S}{\overrightarrow{\mathbf{e}}}_i$$b_{i,j} = b_{i,j} + \mathbf{\vec u}_j ^\top \mathbf S \mathbf{\vec e}_i$

     • 返回 $\{{\overrightarrow{\mathbf{u}}}_j\mid j=1,\cdots ,K_u^{\prime }\}$$\left\{\mathbf{\vec u}_j\mid j=1,\cdots,K_u^\prime \right\}$

   注：本质上它是在给定 $m$$m$ 行为胶囊的前提下找到 $K$$K$ 个兴趣胶囊，使得：

   a. 兴趣胶囊 $j$$j$ 是所有行为胶囊的加权和。

   b. 行为胶囊 $i$$i$ 对所有兴趣胶囊的权重是由兴趣胶囊进行 softmax 得到。

   这类似于二部图上的消息传递机制，因此迭代若干轮之后就会收敛。

   这里 $K$$K$ 的选择是个难点：太小则不足以捕获用户多样化兴趣，太大则计算复杂度太高并引入噪音的兴趣胶囊。

   注二：这里使用胶囊网络来进行聚类，本质是一个聚类过程。

1.1.2 Label-aware Attention Layer

1. 通过多兴趣抽取层，我们从用户的行为 embedding 中生成了多个兴趣胶囊。不同的兴趣胶囊代表了用户兴趣的不同方面，而且相关的兴趣胶囊用于评估用户对特定 item 的偏好。因此，在训练过程中我们基于 scaled dot-product attention 设计了标签感知注意力层（label-aware attention layer）。

   具体而言，对于一个目标 item：

   • 首先，我们计算每个兴趣胶囊和目标item embedding 之间的相似性。

   • 然后，我们计算兴趣胶囊的加权和作为针对目标 item 的用户 representation 向量，其中每个兴趣胶囊的权重由相应的相似性来确定。

2. 在标签感知注意力层中，label item 是 query，兴趣胶囊同时作为 key 和 value。用户 $u$$u$ 关于 item $i$$i$ 的 representation 为：

   $${\overrightarrow{\mathbf{v}}}_u(i)=\text{attention}({\overrightarrow{\mathbf{e}}}_i,{\mathbf{V}}_u,{\mathbf{V}}_u)={\mathbf{V}}_u\text{softmax}\left(\text{pow}({\mathbf{V}}_u^{\mathrm{\top }}{\overrightarrow{\mathbf{e}}}_i,p)\right)$$

   其中：

   • pow() 函数表示逐元素的指数函数。

   • p 是一个超参数作为指数函数的指数项，它用于调整注意力分布：

     • 当 $p$$p$ 接近于零时，每个兴趣胶囊倾向于收到均匀分布的注意力。

     • 当 $p$$p$ 大于1 时，随着 $p$$p$ 的增加，具有较大 dot-product 的兴趣胶囊将获得越来越大的权重。

     • 考虑极端情况下当 $p$$p$ 为正无穷时，注意力机制将成为一种硬注意力（hard attention）：选择注意力最大的兴趣胶囊并忽略其它兴趣胶囊。

       这意味着挑选和目标 item 最相似的兴趣来作为标签感知的兴趣representation 。此时无需进行复杂的 attention 计算，直接利用最近邻检索来获取。

     在我们的实验中，我们发现 hard attention 可以加快收敛速度。

1.1.3 其它

1. Training：得到用户 representation 向量 ${\overrightarrow{\mathbf{v}}}_u(i)$$\mathbf{\vec v}_u(i)$ 以及 label item embedding ${\overrightarrow{\mathbf{e}}}_i$$\mathbf{\vec e}_i$ 之后，我们计算用户 $u$$u$ 和 label item $i$$i$ 交互的概率为：

   $$\text{Pr}(i\mid u)=\text{Pr}({\overrightarrow{\mathbf{e}}}_i\mid {\overrightarrow{\mathbf{v}}}_u(i))=\frac{\exp ({\overrightarrow{\mathbf{v}}}_u(i{)}^{\mathrm{\top }}{\overrightarrow{\mathbf{e}}}_i)}{\sum _{j\in \mathcal{I}}\exp ({\overrightarrow{\mathbf{v}}}_u(i{)}^{\mathrm{\top }}{\overrightarrow{\mathbf{e}}}_j)}$$

   训练 MIND 的目标函数为：

   $$\mathcal{L}=\sum _{(u,i)\in \mathcal{D}}\log \text{Pr}(i\mid u)$$

   其中 $\mathcal{D}$$\mathcal D$ 是包含所有 user-item 交互的训练数据的集合。

   注意，这里通过 softmax 函数变为一个多分类问题，因此没有负样本的概率。在多分类问题中，不存在负样本，只有二分类问题存在负样本。

   由于 item 规模在数十亿级，因此 $\text{Pr}(i\mid u)$$\text{Pr}(i\mid u)$ 的分母计算量太大导致无法实现，因此我们采用采样的 softmax 技术（sampled softmax technique）。

2. 我们使用 Adam 优化器来训练 MIND 。

3. Serving：除了标签感知注意力层之外的 MIND 网络即为用户 representation 映射函数 $f_{\text{user}}$$f_{\text{user}}$ 。在 serving 期间：

   • 用户的行为序列和用户画像馈入 $f_{\text{user}}$$f_{\text{user}}$ 函数，从而为每个用户生成多个 representation 向量。

   • 然后，我们使用这些 representation 向量通过最近邻方法检索 top N 个 item ，从而构成推荐系统 matching 阶段的最终候选 item 集。

   注意：

   • 当用户有新的行为时，这将改变用户的行为序列以及相应的用户 representation 向量，因此 MIND 对于 mathcing 阶段拥有实时个性化的能力。

   • 每个用户有 $K_u^{\prime }$$K_u^\prime$ 个兴趣胶囊，$\{{\overrightarrow{\mathbf{u}}}_j\mid j=1,\cdots ,K_u^{\prime }\}$$\left\{\mathbf{\vec u}_j\mid j=1,\cdots,K_u^\prime \right\}$ ，这里会针对每个兴趣胶囊进行检索然后合并。

4. 部署：天猫上 MIND 的实现和部署如下所示：

   • 当用户启动天猫 APP 时，推荐请求发送到天猫个性化平台 （Tmall Personality Platform），该服务器集群集成了很多插件模块并提供天猫在线推荐服务。

   • 天猫个性化平台检索用户的近期行为，并将其发送到用户兴趣提取器（User Interest Extractor），后者是实现 MIND 的主要模块，用于将用户行为转换为多用户兴趣（multiple user interest）。

   • 随后，召回引擎（Recall Engine）将搜索和用户兴趣的 embedding 向量最邻近的 item。由不同兴趣触发的item 将融合为候选 item，并根据它们与用户兴趣的相似性进行排序。

     由于基于MIND 服务的有效性，通过用户兴趣提取器和召回引擎从数十亿个item 库中选择数千个候选 item 的整个过程可以在不到 15ms 的时间内完成。

   • Ranking Service 对这些候选item 中的top 1000个 item进行打分（在item 数量和延迟时间之间进行权衡），该服务通过一系列特征来预测 CTR。

   • 最后天猫个性化平台完成推荐列表，并向用户展示推荐结果。

   用户兴趣提取器和 Ranking Service 都是在Model Training Platform 上使用 100个 GPU进行训练，训练可以在8 个小时内完成。得益于Model Training Platform 的出色性能，深度模型天级更新。

   

5. 这里我们对 MIND 和两种现有方法之间的关系做一些说明，说明它们的相似之处和不同之处。

   • YouTube DNN：MIND 和 YouTube DNN 都利用深度神经网络对行为数据进行建模从而生成用户 representation。这些 representation 用于工业推荐系统 matching 阶段的大规模item 检索。

     但是，YouTube DNN 使用一个向量来代表用户，而 MIND 使用多个向量。当用户兴趣数量 K=1 时，MIND 会退化为 YouTube DNN，因此MIND 可以视为 YouTube DNN 的推广。

   • DIN：在捕获用户的多样化兴趣方面，MIND 和 DIN 具有相同的目标。但是，这两种方法在实现目标的方式和适用性方面有所不同。

     • 为了处理多样化兴趣，DIN 在 item-level 应用了注意力机制；而 MIND 使用动态路由生成兴趣胶囊，并在 interest-level 考虑了多样性。（interest 比 item 更高一个 level ）。

     • 此外，DIN 重点聚焦于 ranking 阶段，因为它处理上千个item；而 MIND 作用于 matching 阶段，处理数十亿个 item 。

6. 未来方向：

   • 第一个方向是融合有关用户行为序列的更多信息，如行为时间等。

   • 第二个方向是优化动态路由的初始化方案，参考K-means++ 初始化方案，从而实现更好的用户representation。

1.2 实验

1.2.1 离线评估

1. 这里我们在多个数据集上离线评估了MIND 和现有方法的推荐准确率。

2. 数据集：

   • Amazon Books 数据集：它是电商推荐领域中使用最广的公共数据集之一。我们仅保留至少评论 10 次的 item、以及至少评论10 个 item 的用户。

   • Tmall Data数据集：它是从 Mobile Tmall App 中随机采样的 200 万天猫用户，并获得这些用户在10 天内的历史行为。我们保留至少600 个用户点击的 item。

   这些数据集的统计信息如下表所示：

   

3. 评估指标：我们选择next item prediction 问题（即预测用户的下一个交互）来评估方法的性能，因为这是推荐系统mathcing 阶段的核心任务。

   我们将每个数据集的 user-item 交互数据按照 19:1 的比例随机划分为训练集、测试集。然后对于每个用户，我们将用户交互的、测试集中的 item 作为目标 item，该 item 之前所有交互的item 作为用户历史行为。我们根据用户历史行为来预测目标 item 。

   我们采用命中率（hit rate）作为衡量推荐效果的主要指标，定义为：

   $$\text{HitRate@N}=\frac{\sum _{(u,i)\in {\mathcal{D}}_{\text{test}}}I(\text{target item occurs in top N})}{|{\mathcal{D}}_{\text{test}}|}$$

   其中：

   • ${\mathcal{D}}_{\text{test}}$$\mathcal D_{\text{test}}$ 表示由用户和target item $(u,i)$$(u,i)$ 组成的测试集。

   • $I(\cdot )$$I(\cdot)$ 为示性函数，$I(\text{true})=1,I(\text{false})=0$$I(\text{true})=1, I(\text{false}) = 0$ 。

   • target item occurs in top N 表示目标 item 是否在预估多分类概率中的 top N。由于模型采用 softmax 输出层，因此可以考虑目标 item 的输出概率在所有 item 输出概率中的位置。

   我们在每个数据集上对 embedding 向量维度 $d$$d$ 、用户兴趣数 $K$$K$ 进行超参数调优，并使用最佳超参数对每种方法进行测试以便进行公平的比较。

4. baseline 方法：

   • WALS：即加权最小二乘法（Weighted Alternating Least Square）。它是一种经典的矩阵分解算法，用于将 user-item 交互矩阵分解为用户的隐藏因子（hidden factor）和item 的隐藏因子 。然后基于用户的隐藏因子和target item 的隐藏因子之间的相似性进行推荐。

   • YouTube DNN：它是用于工业推荐系统的最成功的深度学习方法之一。

   • MaxMF：它引入了一种高度可扩展的方法来学习非线性潜在因子分解，从而对用户的多个兴趣进行建模。

5. 实验结果如下表所示，我们给出了不同方法在两个数据集上 N=10,50,100 的命中率结果。其中：黑体表示最佳性能；HP 表示性能最佳的超参数， K 表示兴趣数量，d 表示 embedding 维度；括号中的百分比表示相对于 YouTube DNN 的相对提升。

   可以看到：

   • 矩阵分解方法 WALS 被其它方法击败，这表明深度学习方法对于改进推荐系统matching 阶段的强大作用。

   • 但是，即使没有使用深度学习方法，MaxMF 的性能也要比 WALS 好得多。这可以用以下事实来解释：MaxMF 将标准MF 泛化为非线性模型，并对于每个用户采用了多个representation 向量。

     • 可以观察到：采用用户的多个representation 向量的方法（MaxMF-K-interest、MIND-K-interest） 通常要比其它方法（WALS、YouTube DNN、MIND-1-interest）表现更好。

       因此，事实证明：使用用户的多个representation 向量是一种对用户的不同兴趣进行建模、并提高推荐准确性的有效方法。

     • 此外，我们可以观察到，由于天猫的用户倾向于表现出更多的兴趣，因此由于用户的多个representation 向量引入的改善对于 TmallData 更为显著。

     • 多样性的增加也可以通过每个数据集的最佳 K 值来反映，其中 TmallData 的最佳 K 大于 Amazon Books 的最佳 K 值。

   • 和 YouTube DNN 相比，MIND-1-interest 的提高表明：动态路由是一种比均值池化更好的池化策略。

   • 对比 MaxMF 和 MIND-K-interest 的结果，这验证了通过动态路由从用户行为中提取多个兴趣优于在 MaxMF 中使用非线性建模策略。这可以归结于两点：

     • 多兴趣提取器层利用聚类过程生成兴趣的representation，从而实现用户的更精确的representation。

     • 标签感知注意力层使 target item 在用户的多个representation 向量上分配注意力，从而使得用户兴趣和 target item 之间的匹配更加准确。

   

6. 这里我们在 Amazon Books 上进行两个实验，从而研究多兴趣提取器层和标签感知注意力层中超参数的影响。

   • routing logit 的初始化：多兴趣提取器层采用的 routing logit 的随机初始化和 K-means 质心的初始化相似，其中初始聚类中心的分布对于最终聚类结果的影响很大。由于 routing logit 是根据高斯分布 $\mathcal{N}(0,{\sigma }^2)$$\mathcal N(0,\sigma^2)$ 初始化的，因此我们担心 $\sigma$$\sigma$ 的不同取值可能导致不同的收敛性从而影响性能。为了研究 $\sigma$$\sigma$ 的影响，我们使用了三个不同的 $\sigma$$\sigma$ （0.1, 1, 5 ）来初始化 routing logit $b_{i,j}$$b_{i,j}$ 。

     实验结果如下图所示。可以看到：不同 $\sigma$$\sigma$ 的每条曲线几乎都重叠。该结果表明：MIND 对于 $\sigma$$\sigma$ 的取值具有鲁棒性。因此我们在实际应用中选择 $\sigma =1$$\sigma=1$ 是合理的。

     

   • 标签感知注意力层的幂次：如前所示，标签感知注意力中的幂次 $p$$p$ 控制每个兴趣在组合的标签感知兴趣表示（label-aware interest representation）中所占的比例。为了研究 $p$$p$ 的影响，我们比较了 当 $p$$p$ 从 $0\to \mathrm{\infty }$$0\rightarrow \infty$ 时 MIND 的性能变化。

     实验结果如下图所示。可以看到：

     • p=0 时的性能相对而言要差很多。原因是当 $p=0$$p=0$ 时每个兴趣都具有相同的注意力，因此组合的兴趣表示（combined interest representation）等于没有参考label 时的兴趣representation 均值。

     • 当 $p\ge 1$$p\ge 1$ 时，注意力得分与兴趣 representation 向量和目标item 的 embedding 之间相似度成比例，这使得组合的兴趣 representation 为所有兴趣 representation的加权和。

     • 另外，随着 $p$$p$ 的增加性能会变得更好，因为和目标item 相似度更高的兴趣 representation 获得了更大的注意力。

     • 最后，当 $p=\mathrm{\infty }$$p=\infty$ 时变成了 hard attention scheme。此时和目标item 最相似的兴趣 representation 将主导组合的兴趣 representation，从而使得 MIND 收敛得更快并且表现最好。

     

1.2.2 在线评估

1. 我们在线部署MIND 来处理天猫首页上的实际流量从而进行在线实验，为期一周。为了公平地进行比较，在matching 阶段部署的所有方法后续都使用相同的 ranking 过程。我们评估指标是最终的 CTR 效果指标。

2. baseline 方法：

   • item-based CF：它是服务于在线主流量的基本 matching 方法。

   • YouTube DNN：它是著名的基于深度学习的 matching 方法。

3. 我们将所有对比方法部署在 A/B test 框架中，每种方法检索一千个候选item，然后将候选item 送入ranking 阶段以进行最终推荐。

   实验结果如下图所示，我们得出以下结论：

   • MIND 优于 item-based CF 和 YouTube DNN，这表明MIND 产生了更好的用户 representation。

   • 通过长期的实践优化，item-based CF 的效果要比 YouTube DNN 更好，而 MIND-1-interest 也超越了 YouTube DNN。

   • 一个非常明显的趋势是：随着兴趣数量从 1 增加到 5，MIND 的性能会变好。当兴趣数量达到5 时，MIND 性能达到峰值，随后继续增加 K 值则CTR 保持不变。例如， K=7 相对于 K=5 带来的提升几乎可以忽略。

     因此对于天猫用户来讲，最佳的用户兴趣数量是 5~7 ，这表明了用户兴趣的平均多样化程度。

   • 具有动态兴趣数的 MIND 与 K=7 的 MIND 性能相当。因此动态兴趣数机制不会带来 CTR 收益，但是在实验过程中我们发现该方案可以降低 serving 的成本，这有利于大规模的 service （如天猫），并且在实践中更易于采用。

   总而言之，在线实验证明了 MIND 可以实现更好的解决方案，从而为具有不同兴趣的用户建模，并且可以显著提高整个推荐系统的效果。

   

1.2.3 Case Study

1. 耦合系数（coupling coefficient）：行为胶囊和兴趣胶囊之间的耦合系数可以衡量行为对于兴趣的隶属程度。这里我们将这些耦合系数可视化，从而表明兴趣提取过程是可解释的。

   下图给出了从天猫每日活跃用户中随机选择的两个用户相关的耦合系数，每一行对应一个兴趣胶囊、每一列对应一个行为。每一类行为在相应的兴趣上具有最大的耦合系数。注意：这两个用户具有不同粒度的兴趣。

   可以看到：

   • 用户 C（上部）已经和 4 类商品（耳机、小吃、手提包、衣服）进行了交互，每类商品在一个兴趣胶囊上具有最大的耦合系数，并形成了相应的兴趣。

   • 用户 D（下部）仅对衣服感兴趣，但是可以从行为中解析到 3 个细粒度的兴趣（毛衣、大衣、羽绒服）。

   从这些结果中我们可以看到：用户行为的每个类别被聚类在一起，并形成了相应的兴趣representation 向量。

   

2. item 分布：在serving 阶段，和用户兴趣相似的 item 将通过最近邻搜索来被检索到。我们根据兴趣检索的 item 和对应兴趣的相似度，从而可视化相似度的分布。

   下图给出了用户 C 检索的 item 的结果。其中：上面的四个轴显示了基于 MIND 的四个兴趣召回的item；最下面的轴显示了基于 YouTube DNN 召回的 item。

   item 根据它们和兴趣的相似性在轴的相应位置上。我们已经通过 min-max 归一化将相似性缩放到 0.0 ~1.0 之间，并四舍五入到最近的 0.05 。

   图中每个点都是由该区域内item 组成，因此每个点的大小表示具有相应相似度的item 数。 我们还给出了从所有候选item 中随机选择的一些 item。

   不出所料：MIND 召回的 item 和相应的兴趣密切相关；而 YouTube DNN 召回的 item 类别相差很大，并且与用户行为的相似性较低。