youtube也开放了它们的diversity方法:《Practical Diversified Recommendations on YouTube with Determinantal Point Processes》, 我们来看下：

介绍

在线推荐服务通常以feed一个有序的item列表的方式来呈现内容给用户浏览。比如：youtube mobile主页、Facebook news feed。挑选和排序k个items的集合的目标是，最大化该set的效用(utility)。通常times recommenders会基于item的质量的排序来这样做——为每个item i分配一个pointwise的质量分\(q_i\)，并通过对该score进行排序(sorting)。然而，这通常是次优的，因为pointwise estimator会忽略items间的关联性。例如，给定一个已经在页面上被展示过的篮球视频，再展示另一个篮球视频可能会收效更小。相似视频会趋向于具有相近的质量分，这个问题会加剧。不幸的是，即使我们构建一个好的set-wise estimator，对每种可能的ranked list的排列进行打分的代价高昂。

本paper中，我们使用一种称为DPP的机器学习模型，它是一种排斥(repulsion)的概率模型，用于对推荐items进行diversity。DPP的一个关键点是：它可以有效地对一整个items list进行有效打分，而非每个进行单独打分，使得可以更好地解释item关联性。

在成熟的推荐系统中实现一个DPP-based的解决方案是non-trivial的。首先，DPP的训练方法在一些通用的推荐系统中[3,12,14,20,21,26,27]非常不同。第二，对已经存在的推荐系统集成DPP optimization是很复杂的。一种选择是，使用set-wise的推荐重组整个基础，但这会抛弃在已经存在的pointwise estimators上的大量投入。作为替代，我们使用DPP在已经存在的基础顶层作为last-layer model。这允许许多底层的系统组件可以独立演进。更特别的，对于一个大规模推荐系统，我们使用两个inputs来构建一个DPP：

• 1) 从一个DNN来构建pointwise estimators[9]，它会给我们一个关于item质量分\(q_i\)的高精度估计
• 2) pairwise item distances \(D_{ij}\)会以一个稀疏语义embedding space中计算（比如：[19]）

从这些输入中，我们可以构建一个DPP，并将它应用到在feed上的top n items上。我们的方法可以让研究团队继续独立开发\(q_i\)和\(D_{ij}\)的estimators、以及开发一个set-wise scoring系统。因此，我们可以达到diversification的目标，并能在大规模预测系统中利用上现有投入的系统。在Youtube上的经验结果表明，会增加short-term和long-term的用户满意度。

2.相关工作

当前推荐研究主要关注：提升pointwise estimate \(q_i\)（quanlity），即：一个用户对于一个特定item有多喜欢。

该研究线开始于20年前的UCF和ICF，接着是MF。在我们的系统中，我们从DNN中获得这些pointwise estimates，其中：一个用户的偏好特征可以组合上item features来一起估计用户有多喜欢该内容。

在这些改进的过程中，对于推荐结果的新颖性（novelty）和多样性（diversity）也得到了很大的研究【16，24，29，39，41，43，45】。相似的，在信息检索系统上，关于diversitication已经取得了较大的研究。【6，8，10，11，15，33，35，40，42】。考虑到所有这些文献，研究者已经提出了许多diversification概念。这里我们关于内容多样性总结并对比了两种不同的视角。

2.1 帮助探索的多样化

首先，多样化（diversification）有时被看成是一种帮助探索（exploration）的方法；它展示给用户更多样化的内容，可以：

• (A)帮助它们发现新的兴趣主题
• (B)帮助推荐系统发现更多与用户相关的东西

为了发现用户兴趣，信息检索有一个分支研究是，使用分类(taxonomy)来解决用户意图上的二义性(ambiguity)。例如，[2]中的IA-Select使用一个taxonomy来发现一个ambiguous query，接着最大化用户选择至少一个返回结果的概率。。。。

2.2 实用服务的多样化

关于多样化的的一种不同视角是，多样性直接控制着utility服务——通过合适的多样化曝光，可以最大化feed的utility。从该角度看，diversity更与交互关联，增加多样性意味着：使用用户更可能同时喜欢的items替换掉冗余(redundant)的视频曝光。这些新视频通常具有更低的个体得分（individual scores），但会产生一个更好的总体页面收益。

简洁的说，一种达到多样性的方式是：避免冗余项，它对于推荐系统特别重要。例如，在2005 Ziegler[45]中，使用一种贪婪算法利用books的taxonomy来最小化推荐items间的相似度。输出(output)接着使用一个利用一个多样化因子的非多样化的结果列表(non-diversitified result list)进行合并。在另一个信息检索的研究中，Carbonell和Goldstein提出了最大间隔相关度（MMR:maxinal marginal relevance）的方法。该方法涉及迭代式地一次选择一个item。一个item的score与它的相关度减去一个penalty项（用于衡量之前与选中items的相似度）成比例。其它关于redundancy的显式概念在【32】有研究，它使用一个关pairwise相似度上的decay函数。最近，Nassif【30】描述了一种使用次模优化的方式来对音乐推荐多样化。Lin[25]描述了一种使用次模函数来执行文档归纳的多样性。[38]描述了一种次模最大化的方式来选择items序列，[37]描述了使用次模多样性来基于category来进行top items re-rank。我们的目标与本质上相当相似，但使用了一个不同的优化技术。另外，我们不会将item idversity作为一个优先目标；我们的目标是：通过多性化信息提供给整个推荐系统，来尝试增加正向的用户交互数。你可以想像，这里表述的模型上的迭代用于表示一个个性化的diversity概念。被推荐内容的feed也是该方案的一个context，因为用户通常并不会寻找一个特定的item，在一个session过程中与多个items交互。

冗余的概念可以进一步划分成两个独立的相关性概念：替代（substitutes）和补足（complements）。这些概念已经被许多推荐系统所采用。在一个电商推荐应用中，用户做出一个购买决策之前，提供在考虑中的candidates的substitutes可能会更有用；而在用户做出购买行为之后，可以提供补全(complements)的商品。

2.3 相关工作

总之，许多研究者在我们的工作之前已经开始研究：如何在推荐和搜索结果中提升diversity。一些研究者同时处理许多这些diversity概念。例如，Vargas[39]解决了覆盖度与冗余性，以及推荐列表的size。我们关心的是在实践中在一个大规模推荐系统中能运行良好的技术。diversity的概念足够灵活，它可以随时间演化。因此，我们不会选择纠缠taxonomic或topic-coverage方法，因为他们需要一些关于diversity的显式表示（例如：在用户意图或topic ocverage上的一个显式猜测）。

相反的，我们提出了一种使用DPP（determinantal point processes）方法。DPP是一种set-wise的推荐模型，它只需要提供两种显式的、天然的element：一个item对于某个用户有多好，以及items pair间有多相似。

3.背景

3.1 Youtube主页feed

图1 基础的serving scheme

在Youtube mobile主页feed上生成视频推荐的整体架构如图1所示。该系统由三个阶段组成：

• (1) 候选生成（candidata generation）：feed items从一个大的catalogue中选中
• (2) 排序（ranking）：它会对feed items进行排序
• (3) 机制（policy）：它会强加一些商业需求（比如：需要在页面的某些特定位置出现一些内容）

第(1)和(2)阶段都会大量使用DNN。

candidate generation受用户在系统中之前行为的影响。ranking阶段则趋向于对相似的视频给出相近的utility预测，这会经常导致feeds具有重复的内容以及非常相似的视频。

为了消除冗余（redundancy）问题。首先，我们引入了受[32,45]的启发法到policy layer，比如：对于任意用户的feed，单个up主的内容不超过n个items。而该规则有时很有效，我们的经验：这种方式与底层推荐系统的交互相当少。

• 由于candidate generation和ranking layers不知道该启发法（heuristic），他们会浪费掉那些不会被呈现items的空间，做出次优的预测。
• 再者，由于前两个layers会随时间演进，我们需要重新调整heuristics的参数——该任务代价相当高昂，因此实践中不会这么做去很频繁地维持该规则效果。

最终，实际上，多种heuristics类型间的交互，会生成一种很难理解的推荐算法。另外从结果看：系统是次优的，很难演进。

3.2 定义

为了更精准些，我们假设：

一个用户与在一个给定feed中的items中所观察到的交互表示成一个二元向量y：

\[y=[0,1,0,1,1,0,0,\cdots]\]

其中：可以理解的是，用户通常不会检查整个feed流，但会从较低数目的索引开始。

我们的目标是，最大化用户交互数：

\[G'=\sum\limits_{u \sim Users} \sum\limits_{i \sim Items} y_{ui}\]

…(1)

为了训练来自之前交互的模型，我们尝试选择模型参数来最大化对feed items进行reranking的累积增益:

\[G = \sum\limits_{u \sim Users} \sum\limits_{i \sim Items} \frac{y_{ui}}{j}\]

…(2)

其中：j是模型分配给一个item的新rank。

该quantity会随着rank我们对交互进行的越高而增加。(实践中，我们会最小化\(j y_{ui}\)，而非最大化\(\frac{y_{ui}}{j}\)，但两个表达式具有相似的optima) 在下面的讨论中，我们出于简洁性会抛弃u下标，尽管所有值都应假设对于每个user biasis是不同的

我们进一步假设，使用一些黑盒估计y的quality：

\[q_i \approx P(y_i = 1 | \ features \ of \ item \ i)\]

…(3)

明显的ranking policy是根据q对items进行sort。注意，尽管\(q_i\)是一个只有单个item的函数。如果存在许多具有与\(q_i\)相近值的相似items，它们会在排序(rank)时会相互挨着，这会导致用户放弃继续下刷feed。我们的最终目标是：最大化feed的总utility，我们可以调用两个items，等同于当：

\[P(y_i=1, y_j=1) < P(y_i=1) P(y_j=1)\]

…(4)

换句话说，当一起出现时，它们是负相关的——说明其中之一是冗余的。如果在feed中存在相似的items，那么通过q进行sorting不再是最优的policy。

假设我们提供了黑盒item distances：

\[D_{ij} = distance(item \ i, item \ j) \in [0, \infty)\]

…(5)

这些距离被假设成是“无标定的（uncalibrated）”，换句话说，他们无需直接与等式(4)相关。例如，如果问题中的items是新闻文章，D可以是一个在每篇文章中tokenized words的Jaccard distance。现在的目标是，基于q、D、y生成一个ranking policy, 比起通过q简单排序，它可以达到一个关于G的更小值。这可以很理想地与现有基础设施集成和演进。

3.3 设计需要

如果item similarity（如等式4定义）存在于dataset中，并且dataset足够大，那么我们的目标可以通过多种不同的方法来达成。我们喜欢这样的方法：

• 1）能很好满足已存在的逻辑框架：基于已观测的事件来构建机器学习estimators
• 2）可以优雅地在复杂性上随时间进行扩展
• 3）不需要巨大变更就可以应用到已存在的系统和专家意见上

启发法【45】可能会有效但并不理想。例如：假设强制一个规则：在n个相邻的items内，任意两个items必须满足\(D_{ij} < \tau\)。会引起多个问题：

• 1) 该规则运作与q独立。这意味着，高得分的items会与低得分的items具有相同条件。在应用该策略后，对q的accuracy进行独立提升会失去效果
• 2）参数n和\(\tau\)可以通过grid search进行暴力搜索，但额外的复杂性变得相当高，因为训练时间随参数数目指数级增长。
• 3）在一定程度上包含q之外，如何扩展该规则并随时间做出增量提升，这一点并不明显。

一个重要点是：该启发法会隐式地将冗余问题（redundancy problem）看成是一个与最大化utility具有不同的目标。事实上，它建议：该hypothesis会提升diversity，并可能减少utility（至少在短期内），因为它会丢掉那些具有高分q的items。相反的，我们提出的方法会考虑：items的pairs上的utility（通过等式4描述的anti-correlation），因而，使用utility本身能更好地调整的特定items。

当然，基于上述的anti-correlation会定义一个启发法是可能的，比如“在相同的feed中不允许这样的两个items：\(\frac{P(y_i=1, y_j=1)}{P(y_i=1)P(y_j=1)}\)在x以下”。然而，如上所述，该规则不能说明q，可能需要频繁地对参数x进行re-tuning，并且即使有常规的调整，对于精准捕获我们期望的行为也不够灵活，我们会引入DPPs到系统中，作为多样性推荐的方式。

我们会在policy layer之前插入DPPs，但在point-wise scoring layer之后（如图2）所示。这允许我们以一个十分复杂的pointwise scorer进行研究，并确保遵守商业策略（business policies）。

图2 新的serving schema

4.方法

4.1 DPP总览

我们首先回顾下DPPs（deternminantal point processes）的总览。在一个集合\(S=\lbrace 1, 2, \cdots, N \rbrace\)（例如：在一个用户的Youtube移动首页feed中的N个视频的集合）上的一个point process P是一个概率分布（S的所有子集）。也就是说：

\(\forall S \subseteq S\)，P会分配一些概率P(S)，并且\(\sum_{S \subseteq S} = 1\)

DPPs表示一个概率分布族（family），它的参数可调，以便一个subset的概率P(S)与在S中的items的quality以及这些items的diversity的一个组合measure成比例。这样，发现set \(max_{S:\mid S \mid = k} P(S)\)是从一个N个items的更大池中选择关于k个items的high-quality和diverse的subset的一种方式。

如第2节所述，存在许多合理的measures，可以解释：item quality和diversity，比如：MMR方法（maximal marginal relevance）。使用DPPs的优点有两块：

• 1） DPPs在推荐任务中可以胜过MMR
• 2）一个DPP是一个概率模型（probalilistic model）

后一点意味着，我们可以利用概率operations算法的优点，比如：边缘化（marginalization）、调节（conditioning）、采样（sampling）。这些operations与构建一个系统的目标对齐得很好，可以很优雅地随时间在复杂度上可扩展。

我们现在描述，如何我们使用一个DPP来建模用户行为。对于一个有N items的feed，长度为N的binary vector y，表示用户与哪个视频交互。假设：Y表示这些items的index set（例如：对于y=[0, 1, 0, 0, 1, 1]，我们有\(Y = \lbrace 2, 5, 6 \rbrace\)）。接着我们假设，一个用户u的行为是通过一个具有概率分布P的DPP建模，以如下方式：\(Y \sim P_u\)。也就是说，互交的视频集合Y，表示由一个user-specific DPP定义的概率分布中抽取得到。

尽管一个DPP定义了一个在指数数目集合（所有\(2^N\)的子集有\(S=\lbrace 1,2, \cdots, N \rbrace\)）上的概率分布，它可以通过一个\(N \times N\)的半正定kernel matrix进行密集参数化（compactly），我们称它为L。更具体的，一个DPP的概率可以写成一个关于L子矩阵的行列式：

\[P(Y) = \frac{det(L_Y)}{\sum_{Y' \subseteq S} det(L_{Y'})}\]

…(6)

其中：

• \(L_{Y}\)是L限制了只有它的行、列，通过Y进行index（例如：\(Y=\lbrace 2,5,6 \rbrace\)，对应的矩阵\(L_Y\)是size 3X3）。

注意，等式(6)的分母简化为一个规范术语(normalizing term)，它可以被写成和有效计算成一个简单的行列式：

\[\sum_{Y \subseteq S} det(L_Y) = det(L + I)\]

…(7)

其中，I是单位矩阵。

为了看到\(det(L_Y)\)如何定义一个关于items集合的quality和diversity的balanced measure，它可以帮助以如下方式理解L的entries：

• 1）一个对角entry \(L_{ii}\)是一个关于item i的quanlity的measurement
• 2）一个非对角（off-diagonal）元素\(L_{ij}\)：是一个关于item i和item j间的相似度的归一化measurement

有了这些直觉，我们考虑一个\(\mid Y \mid = 2\)的case。如果\(Y=\lbrace 1,2 \rbrace\)，接着：

\[L_y = \left[ \begin{array}{cc} L_{11}&L_{12}\\ L_{21}&L_{22} \end{array} \right]\]

该submatrix的行列式为：\(det(L_Y) = L_{11}L_{22} - L_{12}L_{21}\)。因此，它是一个item quanlities乘积减去归一化item相似度（scaled item similarities）的乘积。该行列式表达式对于更大子矩阵来说更复杂，但直觉上是相似的。

在以下的章节，我们讨论在L从系统输入的多种构建方式，比如：pointwise item quanlity scores，q，第3.2节描述。

4.2 Kernel参数化

当前部署如图2所示，diversification发现在pipeline的相对靠后，因此一个典型的输入set size是：N=100. 对于这些N个视频中的每一个，我们具有两个主要的输入特征（input features）：

• 一个个性化quanlity score q
• 一个sparse embedding \(\phi\)，从视频的主题内容中提取出

这些features完全由独立的子系统生成。通过将我们的diversification系统叠加到它们的top上，我们可以利用这些子系统的持续提升。

对于DPPs初始引入，我们首先使用一个相对简单的参数，关于\(N \times N\)的DPP kernel matrix L：

\[L_{ii} = q_i^2 \\ L_{ij} = \alpha q_i q_j exp(-\frac{D_{ij}}{2\sigma^2}), for \ i \neq j\]

…(9) (10)

每个\(D_{ij}\)通过\(\phi_i\)和\(\phi_j\)计算得到；第5节描述了准确的embedding \(\phi\)和distance function。\(\alpha\)和\(\sigma\)是自由变量。注意，该公式等同于一个标准（高斯）radial basis function（RBF） kernel，其中\(\alpha=1\)。

• 对于更小值，\(\alpha \in [0, 1)\)，矩阵的非对角是按比例缩小的，它必须对应于：所有items会更多样化。
• 对于更大值\(\alpha>1\)，矩阵的非对角部分是按比例放大的，这会具有反作用：所有items会更相似。

随着\(\alpha\)的变大，小集合（small sets）的概率会增长，而大集合（large sets）的概率会收缩（shrinks）。因而，一个大的\(\alpha\)对于在以下setting中的用户行为来说是个较好的满足，其中：它们在feed中只与一个相对小的视频子集进行交互（\(\mid Y \mid 很小\)）。

对于我们来说，使用大的\(\alpha\)很有价值，因为：如第4.3节所示，它提供了一个对真实用户数据的较好fit。然而，存在一个技术要求：允许\(\alpha > 1\)。回顾等式6，当有一个合适的DPP时，kernal matrix L必须是半正定的（PSD）。PSD条件确保了所有子矩阵的行列式是非负的。这很重要，因为：一个set Y的概率与\(det(L_Y)\)成比例，负的“概率”没有意义。如果我们允许\(\alpha > 1\)，这会潜在做出L是非-PSD的。实际上，我们通过将任何non-PSD matrix的投影进行简化来解决该问题：一个大的\(\alpha\)值会造成返回任何PSD matrices的空间。（投影是简单的：我们计算L的特征分解并将任意负特征值替代为0）

4.3 训练方法

我们的训练集包含了将近4w的样本，它们从Youtube mobile主页feed上收集的某天数据中抽样得到。每个训练样本是单个homepage的feed曝光：一个用户的单个实例，对应于用户访问了youtube mobile主页，并被呈现出一个关于推荐视频的有序列表。

对于每个这样的曝光，我们有一个关于用户喜欢哪些视频的记录，我们表示为 set Y。我们注意到，使用这样的数据来训练模型存在一个partial-label bias，因为我们只观察到用户与那些被选中呈现给他们的视频的交互，而非随机均匀选中的视频。通常，我们会使用与过去训练pointwise模型相同类型的方式来解决该问题，比如：使用一个e-greedy exploration策略。

对于前面章节中描述的basic kernel，存在两个参数：\(\alpha\)和\(\sigma\)，因此我们可以做一个grid search来找来能使等式(2)中的累积增益最大化的值。图3展示了\(\alpha\)和\(\sigma\)的多种选择所获得的累积增益。颜色越暗，结果越糟糕。

图3

有意思的是，你可以观察到，在右上角象限中的灾难性悬崖（catastrophic clif），以及随后的高原。必须对训练样本使用DPP kernels来变为增加non-PSD。记住，随着\(\alpha\)增长，L的非对角阵也会增长，这会增加一个non-PSD L的机率。由于非对角阵一定程度上会随\(\sigma\)增加，对于许多训练样本来说，大的\(\alpha, \sigma\)组合会导致non-PSD矩阵。直觉上，看起来整个右上角会具有低累积增益值，而非：低的值会集中在观察带上。然而，记住，我们会将任意non-PSD矩阵投影回PSD空间上。该投影分别对于\(\alpha\)和\(\sigma\)来说都是非线性的，因此，在投影后的矩阵的quanlity，不会期望与我们关于这些参数的直觉强相关。整体上，我们发现，具有最高的累积增益会在\(\sigma\)的中间区间、以及\(\alpha\)的上半区间达到。由这些参数产生的L kernels更可能是PSD，因此，只有一个偶然的训练样本的kernel需要投影。

4.4 Deep Gramian Kernels

正如之前所讨论，通过启发法使用DPP的一个主要好处是，DPP允许我们构建一个在复杂度上可以随时间优雅扩展的系统。启发法的复杂度扩展性很差，因为必须在参数上做grid search来调参，因此，训练一个启发法的runtime与参数数目成指数关系。在本节中，使用DPP，我们可以超越grid search，使用许多参数来高效训练一个模型。

可以以多种方式来学习DPP kernel matrices。这些工作通常是为了最大化训练数据的log似然。更具体的，假设：

• L的参数是：一些长度为r的vector w
• 我们具有M个训练样本，每个包含了：
  • 1）一个关于N个items的集合
  • 2) 用户与之交互的这些items的子集Y

假设：L(w)是N x N的kernel matrix，通过参数w进行索引。接着训练数据的log似然是：

\[LogLike(w) = \sum\limits_{j=1}^M log(P_{L(w)}(Y_j)) \\ = \sum\limits_{j=1}^M [log(det(L(w)_{Y_j})) - log(det(L(w) + I))]\]

其中：

• \(Y_j\)是来自与用户交互的训练样本j的items的子集。使用log似然作为一个目标函数的能力，允许我们使用比grid search更复杂的方法（并且更有效）来学习DPP参数。

我们然后通过使用在LogLike上的gradient descent，开始探索学习一个kernel，它具有许多参数，比如：前面提过的\(\alpha\)和\(\sigma\)。我们仍会使用输入\(\phi\) embeddings来区别视频内容。对于个性化视频的quality scores来说（非scalar score \(q_i\)），我们可以从已经存在的基础设施中获得quanlity scores \(q_i\)的整个vector，因此我们使用该vector来更通用地做出我们的模型。（vector \(q_i\)的每个entry一定程度上会捕获：对于一个用户做出一个好的视频选择），我们从input data中学到的full kernel \(L(\phi, q)\)可以通过下面方式进行表示：

\[L_{i,j} = f(q_i) g(\phi_i)^T g(\phi_i)^T g(\phi_j) f(q_j) + \sigma 1_{i,j}\]

…(13)

其中，f和g是neural network中的独立stacks。（\(\sigma\)可以简化为一个正则参数，我们可以固定在某个小值上）注意，quantity \(f(q_i)\)是一个scalar，其中\(g(\phi_i)\)是一个vector。计算f的neural network相当浅层，而g的network则更穿梭，在空间中有效的re-embeded \(\phi\)，会更能描述视频的utility correlation（如图4）。我们可以注意，不同于早前讨论的basic kernel parameterization，其中\(\alpha\)的大值会产生non-PSD L，这种更复杂的参数化实际会保证总是无需投影即可生成PSD矩阵。这遵循事实：L的该特定构造会使它是一个Gramian矩阵，并且所有这样的矩阵都是PSD的。

为了学习neural network的所有参数来计算f和g，我们会使用tensorflow来根据等式(11）进行最优化LogLike。产生的deep DPP models在线上实验会有utility提升（如表1的Deep DPPs所示）。然而，对比非多样性的baseline，这样的更深模型会大体上对ranking进行改变，二级业务指标会被极大影响，需要进行额外调参。

4.5 DPP的高效ranking

在本节中，我们描述了在serving时如何使用4.3节/4.4节学到的DPP参数。也就是说，当一个用户访问Youtube移动端主页时，DPP是如何决定哪些videos会在推荐feed的top展示的？对于任意给定的用户，Youtube系统基础设施的底层会将个性化质量得分(personalized quality scores) q和N个视频集合的视频embedding vectors \(\phi\)发送给DPP layer。我们会根据scores、embeddings、以及之前学到的参数来构建一个DPP kernel L。我们接着将window size \(k << N\)固定，并请求DPP来选取一个关于k个视频的高概率集合。我们将这些视频放置一feed的顶部，接着再次询问DPP来从剩余N-k个未见过的视频中选选一个关于k个视频的高概率集合。这些视频会变为在feed中的next k个视频。我们会重复该过程，直到我们对N个视频的整个feed排好序(ordered)。

使用stride size=k来构建数据的子窗口(sub-windows)背后的思想是，两个相似items间的排斥（repulsion）会随它们在feed中的距离越近而增加。也就是说，相似的video 1和video 100不如相似的video 1和video 2带给用户更差的体验。实际上，对一个包含了N=上百个视频的feed进行排序(ordering)，我们会使用k为十几个视频的sub-windows。

当我们“请求DPP来获取一个关于k个视频的高概率集合”时，我们实际要做的是，请求size-k 集合Y，它们会具有用户与这k个items的每一个交互的最高概率。这对应于以下的最大化问题：

\[\underset{Y:|Y|=k}{max} det(L_Y)\]

…(14)

如[18]所示，该最大化是NP-hard的。在实际中，尽管一个标准的次模最大化贪婪算法[31]看起来可以近似较好地求解该问题。该贪婪算法从\(Y=\emptyset\)（空集）开始，接着运行k次迭代，每次迭代添加一个video到Y中。在第i轮迭代选中的video是video v，当被添加到当前选中集合中时它会产生最大的行列式值（determinant value）:

\[max_{v \in remaining videos} det(L_{Y \cup v})\]

…(15)

除了简洁外，该贪婪算法的一个额外优点是，如果我们跟踪贪婪选中视频的order，会发现在相对应的用户feed的size-k window中，给出的视频的天然顺序(natural order)。

<>

算法1

算法1总结了本节的ranking算法。在后续章节你会看到，该ranking会帮助我们发现更容易消费的内容。

5.实验结果

首先，我们描述了一些基本的比较baseline。在最终达到DPPs之前，我们会尝试三种diversification的heuristics：

• 模糊去重（Fuzzy deduping）：不允许任意视频i，它与已在feed中的video j间的距离在一个阀值\(\tau\)之下：\(D_{ij} < \tau\)
• 滑动窗口（sliding window）：允许每m个items最多有n个在distance阀值\(\tau\)之下
• 平滑分罚项（smooth score penalty）：当正在为position n+1进行选择video v时，对quanlity scores进行re-scale来解释对于已经被选中的videos 1到n间的相似度

\[q_{new,v} = q_{original, v} * e^{-b (\phi_v \cdot \phi_{previous})}\]

…(16)

其中：

\[\phi_{previous} = \sum\limits_{k=0}^n a^{n-k-1} \phi_k\]

…(17)

其中，q是我们排序的quality score，a和b是free parameters，\(\phi\)是embedding vector。

如表1所示，所有这些尝试都会产生一个less useful的移动端主页feed，通过对从主页开始的long sessions的用户数进行measure。

表1

当使用DPPs进行实验时，我们首先使用4.2节描述的kernel L，并评估多个embeddings和distance functions（dense和sparse audio embeddings, frame embeddings，thumbnail image embeddings, document text embedding等）。我们发现，使用Jaccard distance来计算等式10中的\(D_{ij}\)会很有效，并应用到包含item tokens的sparse vectors \(\phi\)上。（例如，Saturday Night Live video “Olive Grarden-SNL”具有tokens “snl”、”olive garden”、”saturday night”、”night live”以及”sketch”等）。在youtube移动主页推荐上的真实线上实验可以看到，对于我们的用户有显著的提升。如表1所示，在satisfied homepage watchers metric上有+0.63%的提升，我们也可以看到在overall watch time上有+0.52%的提升，它对于baseline来说是个相当大的jump。由于在mobile上的成功，通过DPPs进行多样化已经被部署到所有surfaces上，包括：TV、desktop、Live streams。（注意：deep Gramian DPPs每看起来在”satisfied homepage watchers”指标上提升非常大，它还没有被部署）。正如之前所述，这些deeper models对比起非多样化的baseline，在ranking的变更上足够大，二级商业指标开始受到影响，需要额外调参）

有意思的是，对于一些参数选择，我们可以看到在homepage上直接交互的损失（losses），但从整个丫点看我们可以有一个整体的收益（overall win）。图5展示了来自homepage的view time上的百分比提升。这意味着，用户会发现内容足够吸引人，它会导致从homepage开始的一个更长的session。另外，我们也观察到，会在相关视频栏（related videos panel：它位于当前正播放视频的一侧panel，提供其它相关视频）上增加activity，包括：CTR、播放数（number of views）、总播放时间（amount of total view time），尽管事实上我们只影响了在homepage feed上的视频。这种可累积性（cumulatively），意味着对比以往方式，用户会更多他们喜欢的视频。

图5

另外，我们也能从多样性的用户feeds中观察到一个long-term的”learning effect”【17】。也就是说，随着时间的延伸，多样性会导致用户更愿意返回并享受我们提供的服务。在们通过运行两个long-term holdback实验的集合来对该effect进行评估。在第一个holdback条件中，用户不会获得DPP-diversified feeds，但该部分用户流量子集会随每天变动（这些用户通常会曝fkhtgcdiversified feed，除了在他们在该holdback set中结束的很少几天rare day）。在第二个holdback条件中，一个consistent的用户集合不会看到DPP-diversified feeds。我们接着观察，DPP多样性是否会产生一个在用户体验上的long-term提升：当对比control groups时，通过观察在两个holdbacks间的差异来得到。如图6所示，通过这两个holdback groups，用户从homepage上观看至少一个视频的数目会增加：使用diversified feeds曝光的用户更容易找到他们在youtube主页上感兴趣的视频。因此，我们可以看到，diversified feeds会导致在立即项（immediate term）上增加用户满意度，该effect会随时间变得更显著。

图6

参考

• 1.http://jgillenw.com/cikm2018.pdf

hulu在NIPS 2018上开放了它们的方法:《Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity》, 来解决推荐多样性问题。我们来看下：

摘要

DPP是一种优雅的概率模型。然而，为DPP进行最大后验推断（MAP：maximum a posteriori inference），在许多应用中扮演着一个重要角色，这是一个NP-hard问题。流行的贪婪算法贪心法计算开销很大，很难用于大规模实时场景。为了克服计算挑战，在本paper中，我们提出了一种新算法，可以极快加速DPP的贪婪后验推断（greedy MAP inference）。另外，我们的算法也会应用到以下场景：在结果序列中，只需要在附近很少的items上进行多样性排斥。我们应用该算法来生成相关性和多样性推荐。实验结果表明，我们提出的算法要比state-of-the-art的其它方法要快，并在一些公开数据集上提供了一个更好的relevance-diversity trade-off，同时也在online A/B test上要好。

1.介绍

行列式点过程（DPP： determinantal point process）首先在[33]中介绍用来给出在热平衡(thermal equilibrium)中的费米子系统的分布。除了在量子物理学和随机矩阵上的早期应用，它也可以被应用到多种机器学习任务上，比如：多人姿态估计（multiple person pose estimation）、图片搜索、文档归纳、视频归纳、产品推荐、tweet timeline生成。对比其它概率模型（比如：图形模型），DPP的一个主要优点是，对于不同类型的推断（包含：conditioning和sampling），它遵循多项式时间算法（polynomial-time algorithms）。

上述推断的一个例外是：最大后验推断(MAP)(例如：寻找具有最高概率的items集合)，它是一个NP-hard问题。因此，具有较低计算复杂度的近似推断方法（approximate inference）更受欢迎。paper[17]提出了针对DPP的一种近似最优的MAP推断（inference）。然而，该算法是一个基于梯度的方法，它在每次迭代上评估梯度时具有较高的计算复杂度，使得它对于大规模实时应用来说不实际。另一个方法是广泛使用的贪心法（greedy algorithm），事实证明：DPP中的log概率是次模的（submodular）。尽管它具有相对较弱的理论保证，但它仍被广泛使用，因为它在经验上对效果有前景。贪心法（greedy algorithm）[17,32]的已知实现具有\(O(M^4)\)的复杂度，其中M是items的总数目。Han et al.的最近工作[20]通过引入一些近似可以将复杂度降到\(O(M^3)\)，但会牺牲accuracy。在本paper中，我们提出了关于该w贪心法的一种准确（exact）实现，它具有\(O(M^3)\)的复杂度，它经验上比近似算法[20]要更快。

DPP的基本特性是：它会为那些相互比较多样化（diverse）的items集合分配更高的概率。在一些应用中，选择的items是以序列方式展示的，在少量相邻items间会有负作用（negative interactions）。例如，当推荐一个关于items的长序列给用户时，每个时候只有少量序列会捕获用户的注意力。在这种场景下，要求离得较远的items相互间更多样(diverse)些是没必要的。我们会为这种情况开发快速算法。

本文贡献。在本paper中，我们提出了一种新算法，它能极大加速DPP的greedy MAP inference。通过增量更新Cholesky因子，我们的算法可以将计算复杂度降至\(O(M^3)\)，运行\((O(N^2 M))\)的时间来返回N个items，使它在大规模实时场景中变得可用。据我们所知，这是首个具有很低时间复杂度的greedy Map inferenece for DPP的准确实现(exact implementation)。

另外，我们也将该算法应用到以下场景：只需要在一个滑动窗口中保证多样性。假设window size为：\(w < N\)，复杂度可以减小到\(O(w N M)\)。这个特性使得它很适合用于以下场景，即：在一个短的滑动窗口内保证多样性。

注：

• M：items的总数目
• N：最终返回N个items结果
• w：window size

最后，我们将提出的算法应用到推荐任务上。推荐多样化的items可以给用户探索的机会来发现新items 和 意外发现的items，也使得该服务可以发现用户的新兴趣。正如实验结果所示，在公开数据集和online A/B test上，对比起其它已知的方法，DPP-based方法在相关性和多样性的trade-off上更好。

2.背景

概念。

• 集合使用大写字母表示，比如：Z。
• \(\#Z\)表示Z中的元素数。
• 向量和矩阵分别通过粗体小写字母和粗体大写字母表示。
• \((\cdot)^{\top}\)表示向量或矩阵的转置。
• \(\langle x,y \rangle\)是向量x和y的内积。
• 给定子集X和Y，\(L_{X,Y}\)是L的sub-matrix，通过行中的X和列中的Y索引。

出于简洁，我们假设:

• \(L_{X,X} = L_X, L_{X,\lbrace i \rbrace}=L_{X,i}\)，
• 以及\(L_{\lbrace i \rbrace, X} = L_{i,X}\)。
• \(det(L)\)是L的行列式，惯例上\(det(L_\emptyset)=1\)。

2.1 DPP

DPP是一个优雅的概率模型，它可以表示负作用（negative interactions）[30]。正式的，对于一个离散集合\(Z=\lbrace 1,2,...,M \rbrace\)，一个DPP的\(P\)表示在Z的所有子集集合（共\(2^Z\)种）上的一个概率度量(probability measure)。当P会为空集给出非零概率时，存在一个矩阵\(L \in R^{M \times M}\)，对于所有子集\(Y \subseteq Z\)，Y的概率为：

\[P(Y) \propto det(L_Y)\]

…(1)

其中：L是一个实数型(real)、半正定(positive semidefinite (PSD）)的kernel matrix，它通过Z的元素进行索引。在该分布下，许多类型的推断（inference）任务（比如：marginalization, conditioning，sampling）可以在多项式时间内执行，除了后验推断（MAP inference）外：

\[Y_{map} = \underset{y \subseteq Z}{argmax} \ det(L_Y)\]

在一些应用中，我们需要引入一个在Y上的基数约束，让它返回具有最大概率的固定size的一个集合，这会为k-DPP产生MAP inference。

除了在第一节介绍的DPP在MAP inference上的工作外，一些其它工作也提出了抽取样本并返回最高概率的样本。在[16]中，一种快速抽样算法，它具有复杂度\(O(N^2 M)\)，其中提供了L的特征分解(eigendecomposition)。尽管[16]中的更新规则与我们的工作相似，但有两个主要的不同之处使得我们的方法更高效。首先，[16]的L的特征分解具有时间复杂度\(O(M^3)\)。当我们只需要返回较少数目的items时，该计算开销主宰着运行时开销。通过对比，我们的方法只需要\(O(N^2 M)\)的复杂度来返回N个items。第二，DPP的抽样方法通常需要执行多个样本试验来达到贪婪算法的可比的经验式性能，它会进一步增加了计算复杂度。

2.2 贪婪次模最大化(Greedy Submodular Maximization)

一个集合函数是在\(2^Z\)上定义的一个实数函数。如果一个集合函数f的边际增益(marginal gains)是非增的（no-increasing），例如：对于任意的\(i \in Z\)和任意的\(X \subseteq Y \subseteq Z \setminus \lbrace i \rbrace\)，当新增一项i时，满足：

\[f(X \cup \lbrace i \rbrace) - f(X) \geq f(Y \cup \lbrace i \rbrace) - f(Y)\]

其中：

• f是次模函数(submodular)

在DPP中的log概率函数\(f(Y)=log det(L_Y)\)是次模函数(submodular)，在[17]中有介绍。次模最大化（submodular maximization）对应是：寻找能让一个次模函数最大化的一个集合。DPP的MAP inference是一个次模最大化过程。

次模函数最大化通常是NP-hard的。一个流行的近似方法是基于贪心法[37]。初始化为\(\emptyset\)，在每次迭代中，如果增加一个item能最大化边际增益(marginal gain):

\[j = \underset{i \in Z \backslash Y_g}{argmax} \ f(Y_g \cup \lbrace i \rbrace) - f(Y_g)\]

那么它就会被添加到\(Y_g\)中，直到最大边际增益(maximal marginal gain)为负 或者 违反了基数约束。当f是单调的（monotone），例如：\(f(X) \leq f(Y)\)对于任意的\(X \subseteq Y\)，贪心算法会遵循一个\((1-1/e)\)的近似保证，它服从一个基数约束[37]。对于通用的无约束的次模最大化(no constraints)，一个修改版的贪心算法会保证(1/2)近似。尽管这些理论保证，在DPP中广泛使用的贪心算法是因为它的经验上的性能保障(promising empirical performance)。

2.3 推荐多样性

提升推荐多样性在机器学习中是一个活跃的领域。对于该问题，有一些方法在相关度和差异度间达到了较好的平衡【11,9,51,8,21】。然而，这些方法只使用了成对差异（pairwise dissimilarity）来描述整个列表（list）的总的多样性，并不会捕获在items间的一些复杂关系（例如：一个item的特性可以通过其它两者的线性组合来描述）。一些尝试构建新的推荐系统的其它工作，提出通过学习过程来提升多样性【3，43，48】，但这会使得算法变得更不通用、更不适合于直接集成到已经存在的推荐系统中。

在【52，2，12，45，4，44】中提出的一些工作，定义了基于类目信息（taxonomy information）的相似矩阵。然而，语义型类目信息（semantic taxonomy information）并不总是有提供，基于它们来定义相似度可能不可靠。一些其它工作提出基于解释（explanation）[50]、聚类(clustering)[7,5,31]、特征空间（feature space）[40]、或覆盖(coverage)[47,39]来定义多样性指标（diversity metric）。

本文中，我们使用DPP模型以及我们提出的算法来最优化在相关度和多样性间的权衡。不同于之前已经存在的成对差异（pairwise dissimilarities）的技术，我们的方法会在整个子集的特征空间（feature space）中定义多样性。注意，我们的方法本质上与推荐中DPP-based的方法不同。在[18,34,14,15]中，他们提出了在购物篮（shopping basket）中推荐商品，核心是学习DPP的kernel matrix来描述items间的关系。作为对比，我们的目标是通过MAP inference来生成一个相关度和多样性推荐列表。

本paper中考虑的diversity不同于在[1,38]中的聚合多样性（aggregate diversity）。增加聚合多样性可以提升长尾items，而提升多样性则会在每个推荐列表中更偏好于多样性的items。

3.Fast Greedy MAP Inference

在本节中，我们提出了一种对于DPP的greedy Map inference算法的快速实现。在每轮迭代中，item j满足：

\[j = \underset{i \in Z \backslash Y_g}{argmax} \ log det(L_{Y_g \cup \lbrace i \rbrace}) - log det(L_{Y_g})\]

…(1)

那么该item就会被添加到已经选中的item set \(Y_g\)中。由于L是一个半正定矩阵（PSD matrix），所有主子式都是半正定的（PSD）。假设\(det(L_{Y_g}) > 0\)，\(L_{Y_g}\)的柯列斯基分解(Cholesky decomposition)提供如下：

\[L_{Y_g} = V V^{\top}\]

其中：

• V是一个可逆下三角矩阵

对于任意\(i \in Z \backslash Y_g\)，\(L_{Y_g \cup \lbrace i \rbrace}\)的柯列斯基分解(Cholesky decomposition)可以定为：

\[L_{Y_g \cup \lbrace i \rbrace} = \begin{bmatrix} L_{Y_g} & L_{Y_{g,i}} \\ L_{i,Y_g} & L_{ii} \\ \end{bmatrix} = \begin{bmatrix} V & 0 \\ c_i & d_i \\ \end{bmatrix} \begin{bmatrix} V & 0 \\ c_i & d_i \\ \end{bmatrix}^{\top}\]

…(2)

其中，行向量\(c_i\)和标量\(d_i \geq 0\)满足：

\[V_{c_i}^{\top} = L_{Y_{g,i}}\]

…(3)

\[d_i^2 = L_{ii} - \| c_i \|_2^2\]

…(4)

另外，根据等式(2), 它可以为：

\[det(L_{Y_g \cup \lbrace i \rbrace}) = det(VV^{\top}) \cdot d_i^2 = det(L_{Y_g}) \cdot d_i^2\]

…(5)

因此，等式(1)等于：

\[j = \underset{i \in Z \backslash Y_g}{argmax} \ log(d_i^2)\]

…(6)

一旦等式(6)被求解，我们可以根据等式(2)，进一步，\(L_{Y_g \cup \lbrace j \rbrace}\)的Cholesky decomposition变成是：

\[L_{Y_g \cup \lbrace j \rbrace} = \begin{bmatrix} V & 0 \\ c_j & d_j \\ \end{bmatrix} \begin{bmatrix} V & 0 \\ c_j & d_j \\ \end{bmatrix}^{\top}\]

…(7)

其中，\(c_j\)和\(d_j\)是已经提供的。当一个新item被添加到\(Y_g\)之后，\(L_{Y_g}\)的Cholesky因子可以被有效更新。

对于每个item i，\(c_i\)和\(d_i\)可以被增量更新。在等式(6)被求解后，将\(c_i'\)和\(d_i'\)定义成\(i \in Z \backslash (Y_g \cup \lbrace j \rbrace)\)的新向量和标量。根据等式(3)和等式(7)，我们有：

\[\begin{bmatrix} V & 0 \\ c_i & d_i \\ \end{bmatrix} c_i'^T = L_{Y_g \cup \lbrace j \rbrace, i} = \begin{bmatrix} L_{Y_{g,i}} \\ L_{ji} \\ \end{bmatrix}\]

…(8)

通过将等式(3)和等式(8)组合，我们可以对\(c_i\)和\(d_i^2\)进行更新，有：

\[c_i' = \begin{bmatrix} c_i & (L_{ji}- \langle c_j,c_i\rangle) / d_j \end{bmatrix} \doteq \begin{bmatrix} c_i & e_i \end{bmatrix}\]

等式(4)意味着：

\[d_i'^2 = L_{ii} - \| c_i' \|_2^2 = L_{ii} - \| c_i \|_2^2 - e_i^2 = d_i^2 - e_i^2\]

…(9)

最初，\(Y_g = \emptyset\), 等式(5)意味着: \(d_i^2 = det(L_{ii}) = L_{ii}\)。完整算法会在算法1中有总结。对于无约束的MAP inference来说停止条件（stopping criteria）是\(e_j^2 < 1\)，或者\(\#Y_g > N\)（当使用基数约束时）。对于后者，我们引入了一个很小的数\(\epsilon > 0\)，并为\(1/d_j\)的数值稳定值将\(d_j^2 < \epsilon\)设置为停止条件（stopping criteria）。

算法1

在k次迭代中，对于每个item \(i \in Z \backslash Y_g\)，更新\(c_i\)和\(d_i\)涉及到两个长度为k的向量内积，总复杂度为\(O(kM)\)。因此，算法1对于无约束MAP inference会在\(O(M^3)\)运行，并返回N个items。注意，对于\(c_i\)和\(d_i\)通过额外的\(O(NM)\)（或者对于无约束情况下的\(O(M^2)\)）空间来达成。

4.带滑动窗口的多样性

在一些应用中，选中的items集合会以序列的方式展示，只需要在一个滑动窗口内控制多样性。窗口大小（window size）为w。我们将等式（1）修改为：

\[j = \underset{i \in Z \backslash Y_g}{argmax} \ log det(L_{Y_g^w \cup \lbrace i \rbrace}) - log det(L_{Y_g^w})\]

…(10)

其中，\(Y_g^w \subseteq Y_g\)包含了 w-1 个最新添加的items。当\(\#Y_g \geq w\)时，方法[32]的一种简单修改版本可以在复杂度\(O(w^2 M)\)上求解等式(1)。我们应用我们的算法到该场景下，以便等式(10)可以在\(O(wM)\)时间上求解。

在第3节中，当\(V, c_i, d_i\)可提供时，我们展示了如何有效选择一个新item。对于等式(10)，V是\(L_{Y_g^w}\)是Cholesky因子。在等式(10)求解后，我们可以相似地去为\(L_{Y_g^w \cup \lbrace i \rbrace}\)更新\(V, c_i, d_i\)。当在\(Y_g^w\)中的items数目是w-1时，为了更新\(Y_g^w\)，我们也需要移除在\(Y_g^w\)中最早添加的items。当最早添加的item被移除时，对于更新\(V,c_i, d_i\)的详细推导，会在补充材料中给出。

算法2

完整算法如Algorithm 2所示。第10-21行展示了在最早item被移除后，如何适当去更新\(V, c_i, d_i\)。在第k次迭代中，其中\(k \geq w\)，更新V、所有的\(c_i\)、\(d_i\)各需要O(W^2)、O(wM)、O(M)时间。算法2需要总复杂度\(O(w N M)\)来返回\(N \geq w\)个items。数值稳定性会在补充材料中讨论。

5.提升推荐多样性

在本节中，我们描述了一个DPP-based方法来为用户推荐相关和多样的items。对于一个用户u，profile item set \(P_u\)被定义成用户喜欢的items集合。基于\(P_u\)，推荐系统会为该用户推荐items \(R_u\)。

该方法会采用三个输入：

• \(C_u\)：表示一个候选item集合
• \(r_u\)：指的是一个分值向量（score vector) ，它表示在\(C_u\)中的items的相关性（relevance）
• \(S\)：一个半正定矩阵，表示每个items pair的相似度

前两个输入可以通过许多传统的推荐算法的内部结果中获得。第三个输入（相似矩阵S），可以基于items的属性、与用户的交互关系、或者两者组合来获得。该方法可以看成是对items相关度及它们的相似度的一个ranking算法。

为了在推荐任务上应用DPP模型，我们需要构建kernel matrix。在[30]中所示，kernel matrix可以写成一个格拉姆矩阵(Gram matrix): \(L=B^T B\)，其中B的列可以是表示items的向量(vectors)。我们可以将每个列向量\(B_i\)通过\(r_i \geq 0\)（item score）和一个\(f_i \in R^D\)（具有\(\| f_i \|_2 = 1\)的归一化向量）的两者乘积的方式来构建。kernel L的条目可以被写成是：

\[L_{ij} = \langle B_i,B_j \rangle = \langle r_i f_i, r_j f_j \rangle = r_i r_j \langle f_i, f_j \rangle\]

…(11)

我们可以将** \(\langle f_i, f_j \rangle\) ** 看成是item i和item j间的相似度的度量，例如：\(\langle f_i, f_j \rangle = S_{ij}\)。因此，user u的kernel matrix可以被写成是：

\[L = Diag(r_u) \cdot S \cdot Diag(r_u)\]

其中：

• \(Diag(r_u)\)是对角阵（diagonal matrix），它的对角向量（diagonal vector）是\(r_u\)。

\(R_u\)的log概率是：

\[log det(L_{R_u}) = \sum\limits_{i \in R^u} log(r_{u,i}^2) + log det(S_{R_u})\]

…(12)

当\(R^u\)的item representations是正交时（即相似度为0)，等式(12)的第二项是最大化的，因而它可以提升多样性。它很清楚地展示了，DPP模型是如何解释被推荐items的相关度和多样性。

[11,51,8]中的一些好特性（nice feature）是，它们涉及一个可调参数，它会允许用户来调节在相关度和多样性间的trade-off。根据等式(12)，原始的DPP模型不会提供这样一个机制。我们会修改\(R_u\)的log概率为：

\[log P(R_u) \propto \theta \cdot \sum\limits_{i \in R^u} r_{u,i} + (1-\theta) \cdot log det(S_{R_u})\]

其中\(\theta \in [0, 1]\)。这对应于一个使用以下kernel的DPP：

\[L' = Diag(exp(\alpha r_u)) \cdot S \cdot Diag(exp(\alpha r_u))\]

其中\(\alpha = \theta / (2(1-\theta))\)。我们也会获得log概率的边际增益（marginal gain）：

\[log P(R_u \cup \lbrace i \rbrace) - log P(R_u) \propto \theta \cdot r_{u,i} + (1-\theta) \cdot (log det(S_{R_u \cup \lbrace i \rbrace}) - log det(S_{R_u}))\]

…(13)

接着，算法1和算法2可以轻易修改成：使用kernel matrix S来最大化等式(13)。

注意，对于推荐任务，我们需要相似度\(S_{i,j} \in [0, 1]\)，其中0意味着最大的多样性(diverse)，1意味着最相似（similar）。当归一化向量\(\langle f_i, f_j \rangle\)的内积可以采用负值。在极端情况下，最多样的对（most diverse pair) \(f_i = -f_j\)，但相应的子矩阵（sub-matrix）的行列式为0, 这与\(f_i = f_j\)相同。为了保证非负性（nonnegativity），当将S保持为一个半正定矩阵时，我们会采用一个线性映射，比如：

\[S_{ij} = \frac{1+\langle f_i,f_j \rangle}{2} = \langle \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ f_i \end{bmatrix}, \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ f_i \end{bmatrix} \rangle \in [0, 1]\]

6.实验结果

在本节，我们会在人造数据集和真实推荐任务上评估和比较提出的算法。算法实现使用Python（向量化vectorization）来实现。实验在2.2GHz Intel Core i7和16GB RAM上进行。

6.1 人造数据集（Synthetic Dataset）

在本节，我们会评估算法1在DPP MAP inference上的效果。我们根据[20]来设置实验。kernel matrix的条目满足等式(11)，其中：

\(r_i = exp(0.01 x_i + 0.2)\)，它使用从正态分布\(N(0,1)\)上抽取的\(x_i \in R\)，以及\(f_i \in R^D\)（其中：D与总的item size M相同，），以及从\(N(0,1)\)独立同分布（i.i.d.）的方式抽取的条目，以及接着进行归一化。

我们提出的faster exact algorithm (FaX)会与带有lazy评估[36]的Schur complement、以及faster approximate algorithm (ApX) [20]进行比较。

…

图1

6.2 短序列推荐

在本节，我们会评估：在以下两个公开数据集上，推荐items的短序列给用户的效果。

• Netflix Prize：该数据集包含了用户的电影评分。
• Million Song Dataset：该数据集包含了用户播放歌曲的数目。

对于每个数据集，我们通过为每个用户随机选择一个交互item的方式来构建测试集，接着使用剩余数据来进行训练。我们在[24]上采用一个item-based推荐算法[24]来学习一个item-item的PSD相似度矩阵S。对于每个用户：

• profile set \(P_u\)包含了在训练集中的交互items，
• 候选集\(C_u\)通过在\(P_u\)中的每个item的50个最相似items进行union得到。
• 两个数据集的\(\#C_u\)的中位数(median)分别是735(netflix）和811(song).

对于在\(C_u\)中的任意item，相关分是对在\(P_u\)中所有items的聚合相似度。有了S和\(C_u\)，分值向量(score vector) \(r_u\)，算法会推荐\(N=20\)个items。

推荐的效果指标包含了MRR (平均倒数排名：mean reciprocal rank)、ILAD(intra-list average distance)、ILMD（intra-list minimal distance）。它们的定义如下：

\[MRR = \underset{u \in U}{mean} P_u^{-1} \\ ILAD = mean_{u \in U} \underset{i,j \in R_u, i \neq j}{mean} (1-S_{ij}) \\ ILMD = \underset{u in U}{mean} \underset{i,j \in R_u, i \neq j}{min} (1-S_{ij})\]

其中，U是所有用户的集合，\(p_u\)是在测试集中关于items的最小排序位置。

• MRR会测度相关度
• ILAD和ILMD会度量多样性(diversity)

我们也会在附录中比较指标PW recall（popularity weighted recall）. 对于这些指标来说，越高越好。

我们的DPP-based算法(DPP)，会与MMR(最大化相关性：maximal marginal relevance)、MSD（最大化多样性：maxsum diversification）、entropy regularizer (Entropy)、基于覆盖的算法（Cover）进行比较。他们涉及到一个可调参数来调节相关性和多样性间的trade-off。对于Cover，参数为\(\gamma \in [0,1]\)，它定义了饱和函数\(f(t) = t^{\gamma}\)。

在第一个实验中，我们在Netflix数据集上测试了DPP的参数\(\theta \in [0,1]\)的trade-off影响。结果如图2所示。随着\(\theta\)的增加，MRR一开始会逐渐提升，当\(\theta \approx 0.7\)时达到最佳值，接着略微减小。ILAD和ILMD会随\(\theta\)的递增而单调递减。当\(\theta=1\)时，DPP会返回最高相关分值的items。因此，需要考虑采用适度的多样性，从而达到最佳效果。

图2

在第2个实验中，为了区分参数的多种trade-off，会比较在相关度和多样性间的效果trade-off，如图3所示。不同算法选择的参数几乎具有相近范围的MRR。可以看到，Cover在Netflix Prize上效果最好，但在Song数据集上最差。在其它算法间，DPP则具有最好的relevance-diversity trade-off效果。如表1所示。MMR, DSP，DPP要比Entropy和Cover快。因为DPP的运行99%概率要小于2ms，它可以用于实时场景。

表1

图3

我们在一个电影推荐系统中在线进行A/B test，并运行了4周。对于每个用户，候选电影的相关得分通过一个在线打分模型来生成。离线矩阵因子算法【26】每天会进行训练来生成电影表示，它可以用于计算相似度。对于控制组（control group），5%的users会被随机选中，然后展示给最高相关得分的N=8部电影。对于对照组(treatment group)，另一5%的随机users会通过一个fine-tuned的trade-off参数控制的DPP来生成N部电影。两个在线指标：观看标题数和观看时长（分钟）的提升，如表2所示。结果展示了与使用MMR的另一随机选中的users的对比。可以看到，DPP要比没有多样性算法的系统、以及使用MMR的系统上效果要好。

表2

6.3 长序列推荐

在这部分，我们会评估算法2的效果，来为用户推荐items的长序列。对于每个数据集，我们通过为每个用户随机选择5个交互items来构建测试集(test set），并使用剩余部分来进行训练。每个长序列包含了N=100个items。我们选择window size \(w=100\)以便在序列中的每w个后续items是多样化的。总的来说，如果每次一个用户可以只看到序列的一小部分，w可以是这部分大小(portion size)的阶。其它设置与前一节一致。

效果指标包含了nDCG(normalized discounted cumulative gain)、ILALD(intra-list average local distance)、ILMLD（intra-list minimal local distance）。后两者的定义为：

\[ILALD = mean_{u \in U} mean_{i,j \in R^u, i \neq j,d_{ij} \leq w} (1-S_{ij}), \\ ILMLD = mean_{u \in U} min_{i,j \in R^u, i \neq j, d_{ij} \leq w} (1 - S_{ij})\]

其中，\(d_{ij}\)是在\(R_u\)中item i和j的位置距离。相似的，指标越高越好。为了做出一个公平对比，我们会修改在MMR和MSD中的多样性项（diversity terms），以便它们只考虑最近添加的w-1个items。Entropy 和 Cover是不可测的，因为他们不适合该场景。通过调节多个trade-off参数，我们可以在图4中看到MMR, MSD, DPP的相关性和多样性的trade-off效果。不同算法选中的参数与nDCG具有近似相同的范围。我们可以看到，DPP的效果在relevance-diversity上的trade-off要最好。我们也会在补充材料中比较的PW Recall的指标。

图4

7.结论

在本paper中，我们介绍了一种DPP greedy MAP inference的fast和exact实现。我们的算法的时间复杂度\(O(M^3)\)，它大大低于state-of-art exact实现。我们提出的加速技术可以应用于在目标函数中PSD矩阵的log行列式的其它问题，比如entropy regularizer。我们也会将我们的快速算法应用到以下场景：只需要在一个滑动窗口中多样化。实验展示了我们的算法要比state-of-art算法要快，我们提出的方法在推荐任务上提供了更好的relevance-diversity的trade-off。

附录

博主注

为什么DPP会对quality和diversity进行balance?

DPP如何平衡取出的子集的quality和diversity？Kulesza and Taskar在《机器学习中的DPP》[29 3.1节]提供的分解给出了一个更直观的理解：

建模问题的一个非常重要的实际关注点是可解释性；实践者必须以一种直觉的方式来理解模型参数。DPP kernel的entries不全是透明的，他们可以看成是相似度的度量——受DPP的primary qualitative characterization的作为多样化过程（diversitying）影响。

对于任意半正定矩阵(PSD)，DPP kernel L可以被分解成一个格兰姆矩阵（Gramian matrix）：\(L=B^T B\)，其中B的每一列(column)表示真实集(ground set)中N个items之一。接着，将每一列\(B_i\)写成是一个质量项(quality terms: \(q_i \in R^+\)，标量) 和一个归一化多样性特征（normalized diversity features: \(\phi_i \in R^D, \| \phi_i \| = 1\)）（当D=N时足够对任意DPP进行分解，单独保留D是因为实际上我们希望使用高维的特征向量）的乘积。依次会将L分解成质量项和归一化多样性特征:

\[L_{ij} = B_i^T B_j = q_i \phi_i^T \phi_j q_j\]

我们可以认为\(q_i \in R^+\)是一个item i内在“好坏（goodness）”的度量，\(\phi_i^T \phi_j)\in [-1,1]\)是item i和item j间相似度的一个带符号的measure。我们使用以下的公式来表示相似度：

\[S_{ij} = \phi_i^T \phi_j) = \frac{L_{ij}}{\sqrt{L_ii L_jj}}\]

对于向量\(\phi_i (S_{ij} = \phi_i^T \phi_j)\)的Gramian矩阵S，被称为多样性模型（diversity model）；q被称为质量模型（quality model）。

L的这种分解有两个主要优点。第一，隐式强制了约束：L必须是正定的，可以潜在简化学习。第二，它允许我们独立建模quality和diversity，接着将它们组合成一个统一的模型。实际上：

\[P_L(Y) \propto (\prod\limits_{i \in Y} q_i^2) det(S_Y)\]

其中，第一项会随着选中items的quality的增加而增加，第二项会随着选中diversity的增加而增加。我们将q称为quality model，将S或\(\phi\)称为diversity model。如果没有diversity model，我们会选中高质量的items，但我们会趋向于选中相似的高质量items。如果没有qulity model，我们会获得一个非常diverse的集合，但可能不会包含在Y集合中最重要的items，反而会关注低质量的异类。通过两个models的组合我们可以达到一个更平衡的结果。

从几何空间上看，\(L_y\)的行列式等于：通过对于\(i \in Y\)的vectors \(\q_i \phi_i\)展开的平行六面体的square volume。表示item i的vector的幅值为\(q_i\)，方向是\(\phi_i\)。上图清楚地表示了以这种方式分解的DPPs是如何天然做到high quality和high diversity两个目标间的balance。更进一步，我们几乎总是假设：我们的模型可被分解成：quality和diversity组件。

DPP几何：(a) 一个subset Y的概率是由\(q_i \phi_i\)展开的volume的square (b) 随着item i的quality \(q_i\)增加，包含item i的集合的概率也增加 (c) 随着item i和j变得越相似，\(\phi_i^T \phi_j\)会增加，同时包含i和j的集合的概率会减小

---

它提供了将一个关于子集Y的概率分解成：它的元素(elements)的质量(quality)和它们的多样性（diversity）的乘积。Y的概率等于 按vectors \(q_i \phi_i\)逐个平方：一个子集的概率会随着它的items的质量（quality）增加而增加，会随着两个items变得更相似而减小。

参考

• 1.https://papers.nips.cc/paper/7805-fast-greedy-map-inference-for-determinantal-point-process-to-improve-recommendation-diversity.pdf
• 2.行列式点过程
• 3.https://vimeo.com/240776466
• 4.Learning and Enforcing Diversity with Determinantal Point Processes

阿里在KDD 2018上开放了它们的方法:《Deep Interest Evolution Network for Click-Through Rate Prediction》, 我们来看下：

背景

2.相关工作

由于deep learning在特征表示和特征组合上具有很强的能力，最近的CTR模型已经从传统的线性或非线性模型转换成深度模型。大多数深度模型都使用embedding和多层感知器（MLP）的结构。基于这种基本范式，越来越多的模型关注特征交叉：Wide&Deep，deepFM，PNN。然而这些方法不能很明显地影响数据背后的兴趣。DIN引入了一个attention机制来为给定目标item激活局部的历史行为，可以成功捕获用户兴趣的多性化特性。然而，DIN在捕获序列行为间的依赖关系上很弱。

在许多应用领域，user-item交互会随时间顺序进行记录。许多最近研究表明，该信息可以被用于构建更加丰富的独立用户模型，并能发现额外的行为模式。在推荐系统中，TDSSM(song.2016)会联合优化长期用户兴趣和短期用户兴趣来提升推荐质量；DREAM(Yu et.al 2016)使用RNN的结构来探索每个用户和它的历史购买item全局序列行为的动态表示。He和McAuley(2016)会构建视觉感知(visually-aware)推荐系统，它可以使产品与用户的兴趣和社群的兴趣更匹配。Zhang et al.(2014)基于用户兴趣序列来衡量用户的相似度，并提升协同过滤推荐的效果。Parsana et al.(2018)通过使用关于recurrent网络的大规模的event embedding和attentional output来提升native ads的ctr预测。ATRank(Zhou et al.2018a)使用基于attention的序列框架来建模异种行为。对比起序列独立（sequence-independent）的方法，这些方法可以极大提升预测的accuracy。

然而，这些传统的RNN-based模型有些问题。一方面，它们中的大多数会直接将序列结构(sequential structure)的hidden states看成是隐兴趣(latent interests)，而这些hidden states对于兴趣表示来说缺乏特别的监控。另一方面，大多数已经存在的RNN-based框型可以连续地、等价地处理邻近行为(adjacent behaviors)间的依赖。正如我们所知，并非所有的用户行为在它的每个邻近行为上是严格有依赖关系的。对于任意的target item，这些模型只可以获取一个固定的兴趣演进轨迹（interest evolving track），因此这些模型可能会受兴趣漂移的干扰。

为了将序列结构的hidden states来有效表示隐兴趣，我们需要为hidden states引入额外的监控。DARNN(Ren et al.2018)使用click-level的序列化预测，它会在每次广告被曝光给用户时建模点击行为。除了点击行为，可以进一步引入ranking信息。在推荐系统中，ranking loss在ranking任务（Rendel 2009; Hidasi 2017）上被广泛使用。与其它ranking losses相类似，我们为兴趣学习提出了一个auxiliary loss。在每一step上，auxiliary loss会使用连贯的点击item，而非无点击item来监控兴趣表示的学习。

对于捕获与target item相关的兴趣演化过程，我们需要更灵活的序列学习框架。在AQ领域，DMN+(xiong 2016)使用attention-based GRU （AGRU）来处理输入facts的位置和顺序。在AGRU中，update gate的vector可以通过attention score来进行简单替换。该替换会忽略在update gates的所有维度间的不同之处，其中update gates包含了从前一序列转换而来的丰富信息。受在QA中使用的新的序列结构的启发，我们提出了使用attentional gate的GRU (AUGRU)来派生活在兴趣演化中的相关兴趣。不同于AGRU，在AUGRU中的attention score扮演着从update gate中计算得到的信息。update gate和attention score的组合，可以更专注、更敏感地推进演化过程。

3.DIEN

在本节中，我们会详细介绍了DIEN. 首先，我们回顾了基础的DeepCTR模型，称为BaseModel。接着全面展示DIEN结构，并引入相应的技术来捕获兴趣以及建模兴趣演化过程。

3.1 BaseModel

特征表示：在我们的在线广告展示系统中，我们使用了4种类型的特征类别：User Profile, User Behavior, Ad, Context。注意ad也就是item。对于生成阶段（generation），在本paper中我们将ad称为target item。特征的每个类型(category)都有多个fields:

• User Profile的fields有gender、age等；
• User Behavior的fields是一个关于用户访问过的goods_id的列表；
• Ad的fields有：ad_id, shop_id等；
• Context的fields有：time等。

每个field中的特征可以被编码成one-hot vector，例如：User Profile的类别型特征（如：性别(female:女性)）可以编码成[0, 1]。关于上述4种类型的特征的不同fields的one-hot vector进行拼接(concat)构成：\(x_p, x_b, x_a, x_c\)。在sequential CTR模型中，值得注意的是，每个field包含了一个行为列表，每个行为对应一个one-hot vector，它可以通过\(x_b = [b_1; b_2; \cdots; b_t] \in R^{K \times T}, b_t \in \lbrace 0, 1 \rbrace ^K\)进行表示，其中，\(b_t\)被编码成one-hot vector，并表示第t个行为，T是用户的历史行为的数目，K是用户可点击的商品总数。

BaseModel的结构：大多数deep CTR模型可以基于embedding&MLR来构建。基本的结构有：

• embedding
• MLP

Loss function：deep CTR模型常使用的loss function是负log似然函数，它会使用target item的label来监控整体的预测：

\[L_{target} = -\frac{1}{N} \sum\limits_{(x,y) \in D}^N (y log p(x) + (1-y) log(1-p(x)))\]

…(1)

其中，\(x=[x_p, x_a, x_c, x_b] \in D\)，D是size=N的训练集。\(y \in \lbrace 0, 1 \rbrace\)表示用户是否会点击target item。p(x)是网络的output，它是用户点击target item的预测概率。

3.2 DIEN

在许多电商平台中的在线展示广告，用户不会很显确地展示它们的意图，因此捕获用户兴趣和他们的动态性对于CTR预测很重要。DIEN致力于捕获用户兴趣，并建模兴趣演化过程。如图1所示，DIEN由许多部分组成:

• 首先，所有类别(categories)的特征都使用embedding layer进行转换
• 接着，DIEN会使用两个step来捕获兴趣演化：兴趣抽取层（interest extractor layer）会基于行为序列抽取兴趣序列；兴趣演化层（interest evolving layer）会建模与target item相关的兴趣演化过程
• 接着，最终兴趣的表示会和ad、user profile、context的embedding vectors进行拼接(concatenated)。concatenated vector被feed到MLP中来进行最终预测。

在本节其余部分，我们会引入关于DIEN两个核心的模块详细介绍。

图1: DIEN的结构。在behavior layer上，behaviors会按时间顺序，embedding layer会将one-hot representation \(b[t]\)转换成embedding vector \(e[t]\)。接着，interest extractor layer会使用auxiliary loss来抽取每个interest state h[t]。在interest evolving layer上，AUGRU会建模与target item相关的interest evolving process。final interest state \(h'[T]\)和其余feature的embedding vectors拼接在一起，并feed到MLR中进行最终的CTR预估。

Interest Extractor Layer：在电商系统中，用户行为是隐兴趣的携带者，在用户发生该行为后兴趣会发生变更。在该interest extractor layer上，我们会从序列形用户行为上抽到一系列表兴趣状态。

用户在电商系统中的点击行为是很丰富的，其中历史行为序列的长度在一个较短周期内（比如：两周）会很长。出于效率和性能的权衡，我们会采用GRU来建模行为间的依赖，其中GRU的输入可以通过它们的出现时间顺序排列的行为。GRU可以克服RNN的梯度消失问题，它比LSTM更快（1997），它对于电商系统更适合。GRU的公式如下所示：

\[u_t = \sigma(W^u i_t + U^u h_{t-1} + b^u), & (2) \\ r_t = \sigma(W^r i_t + U^r h_{t-1} + b^r), & (3) \\ \cap{h}_t = tanh(W^h i_t + r_t \odot U^h h_{t-1} + b^h), & (4) \\ h_t = (1-u_t) \odot h_{t-1} + u_t \odot \cap{h}_t, & (5)\]

其中，\(\sigma\)是sigmoid激活函数，\(\odot\)是element-wise乘法，\(W^u,W^r,W^h \in R^{n_H \times n_I}\), \(U^z, U^r, U^h \in n_H \times n_H\)，其中\(n_H\)是hidden size，\(n_I\)是input size。\(i_t\)是GRU的input，\(i_t = e_b[t]\)表示第t个行为，\(h_t\)是第t个hidden states。

然而，hidden state \(h_t\)只捕获行为间的依赖，不能有效表示兴趣。随着target item的点击行为通过最终兴趣触发，在\(L_{target}\)中使用的label只包含了ground truth，它可以监控最终兴趣的预测，而历史的state \(h_t(t < T)\)不能包含合适的监控（supervision）。正如我们所知，每个step上的兴趣状态(interest state)会直接导致连续的行为(consecutive behavior)。因此，我们提出了auxiliary loss，它使用行为\(b_{t+1}\)来监控interest state \(h_t\)的学习。除了使用真实的下一行为作为正例外，我们也会从未点击的item集合中抽样作为负例。有N对(pairs)行为embedding序列：\(\lbrace e_b^i, \hat{e}_b^i \rbrace \in D_B, i \in 1, 2, \cdots, N\)，其中\(e_b^i \in R^{T \times n_E}\)表示了点击行为序列，\(\hat{e}_b^i \in R^{T \times n_E}\)表示负样本序列。T是历史行为的数目，\(n_E\)是embedding的维度，\(e_b^i[t] \in G\)表示用户i点击的第t个item的embedding vector，G是整个item set。\(\hat{e}_b^i[t] \in G - e_b^i[t]\)表示item的embedding，它会从item set（除去用户i在第t个step点击的item）中抽样。auxiliary loss可以公式化为：

\[L_{aux} = -\frac{1}{N} (\sum\limits_{i=1}^N \sum\limits_t log sigma(h_t^i, e_b^i[t+1]) + log(1-sigma(h_t^i, \hat{e}_b^i[t+1])))\]

其中，\(\sigma(x_1,x_2) = \frac{1}{exp(-[x_1, x_2])}\)是sigmoid激活函数，\(h_t^i\)表示对于用户i的GRU的第t个hidden state。全局loss（global loss）为：

\[L = L_{target} + \alpha * L_{aux}\]

…(7)

其中，\(\alpha\)是hyper-parameter，它可以对interest representation和CTR prediction进行balance。

有了auxiliary loss的帮助，每个hidden state \(h_t\)是足够表示用户在发生行为\(i_t\)后的interest state。所有T个interest points的concat \([h_1, h_2, \cdots, h_T]\)组成了interest sequence，兴趣演化层（interest evolving layer）可以建模演化的兴趣。

总之，auxiliary loss的介绍具有以下优点：从interest learning的角色看，auxiliary loss的引入可以帮助GRU的每个hidden state表示interest。对于GRU的optimization，当GRU建模长历史行序列(long history behavior sequence)时，auxiliary loss会减小BP的难度。最后，auxiliary loss会给出更多语义信息来学习embedding layer，它会导至一个更好的embedding matrix。

Interest Evolving Layer

由于从外部环境和内部认知的联合影响，不同类型的用户兴趣会随时间演进。例如，对于衣服的兴趣，随着流行趋势和用户品味的变化，用户对衣服的偏好也会演进。用户在衣服上兴趣的演进过程会直接决定着对候选衣服的CTR预测。建模该演进过程的优点如下：

• Interest evloving module可以为最终的interest表示提供更多的相关历史信息
• 根据兴趣演进趋势来预测target item的CTR更好

注意，在演化期间兴趣有两个特性：

• 由于兴趣多样性，兴趣会漂移。在行为上的兴趣漂移的效果是用户可能在一段时间内对许多书（books）感兴趣，在另一段时间内可能又需要衣服(clothes)。
• 尽管兴趣可以相互影响，每个兴趣都具有它自己的evolving process，例如：books和clothes的evolving process几乎独立。我们只关注那些与target item相关的evloving process。

在第一阶段，有了auxiliary loss的帮助，我们可以获得interest sequence的丰富表示。通过分析interest evloving的特性，我们会组合attention机制的local activation能力，以及来自GRU的sequential learning能力来建模interest evolving。GRU的每个step的local activation可以增强相对兴趣的效果，并减弱来自interest drifting的干扰，这对于建模与target item相关的interest evolving process很有用。

与等式(2-5)的公式相似，我们使用\(i_t^'\)和\(h_t^'\)来表示在interest evolving module上的input和hidden state，其中第二个GRU的input是在Interest Extractor Layer所对应的interest state：\(i_t^' = h_t\)。最后的hidden state \(h_T^'\)表示final interest state。

在interest evolving module中使用的attention function可以公式化成：

\[a_t = \frac{exp(h_t W e_a)}{\sum_{j=1}^T exp(h_j W e_a)}\]

…(8)

其中：

• \(e_a\)是在category ad中fields的embedding vectors的concat
• \(W \in R^{n_H \times n_A}\)中，\(n_H\)是hidden state的维度，\(n_A\)是广告(ad)的embedding vector的维度。
• Attention score可以影响在advertisement \(e_a\)和input \(h_t\)间的关系，并且强相关性会导致一个大的attention score。

接着，我们会引入一些方法来将attention机制和GRU进行组合，来建模interest evolution的过程。

• \(带attentional input的GRU （AIGRU）\)：为了激活在interest evolution间的相对兴趣，我们提出了一个naive方法，称为：”GRU with attentional input(AIGRU)”。AIGRU会使用attention score来影响interest evolving layer的输入。如等式(9)所示：

\[i_t^' = h_t * a_t\]

…(9)

其中，\(h_t\)是在interest extractor layer上的第t个hidden state，\(i_t'\)是第二个GRU的input，它用于interest evolving，其中“*”表示scalar-vector product。在AIGRU中，相关度低的interest的scale可以通过attention score减小。理想情况下，相关度低的interest的输入值可以被减小到0. 然而，AIGRU并不会很好运作。因为zero input可能改变GRU的hidden state，因此，相关度低的interests也会影响interest evolving的学习。

• Attention based GRU（AGRU）

在QA(question answering)领域，attention based GRU(AGRU)首先被提出来[Xiong, 2016]。通过将attention机制的信息进行embedding修改GRU架构后，AGRU可以有效地在复杂queries中抽取关键信息。受QA系统的启发，我们将AGRU移植用来在interest evolving期间捕获相关兴趣。详细的，AGRU使用attention score来替代GRU的update gate，并直接变更hidden state。正式的：

\[h_t^' = (1-a_t) * h_{t-1}^' + a_t * \bar{h}_t^'\]

…(10)

其中，\(h_t^', h_{t-1}^', \bar{h}_t^'\)是AGRU的hidden state。

在interest evolving场景中，AGRU会利用attention score来直接控制hidden state的更新。AGRU会弱化在interest evolving期间相关度低兴趣的影响。attention的embedding会嵌入到GRU中来提升attention机制的影响，并帮助AGRU克服AIGRU的缺点。

• GRU with attentional update gate (AUGRU)

尽管AGRU可以使用attention score来直接控制hidden state的更新，它会使用一个scalar(attention score \(a_t\)）来替代一个vector（update gate \(u_t\)），其中它会忽略不同维度间的不同影响。我们提出了GRU with attentional update gate (AUGRU)来无缝组合attention机制和GRU：

\[\bar{u}_t^' = a_t * u_t^'\]

…(11)

\[h_t^' = (1 - \bar{u}_t^') \prod h_{t-1}^' + \bar{u}_t^' \prod \bar{h}_t^'\]

…(12)

其中，\(u_t^'\)是AUGRU的original update gate，\(\bar{u}_t^'\)是我们专为AUGRU设计的attentional update gate，\(h_t^', h_{t-1}^', \bar{h}_t^'\)是AUGRU的hidden states。

在AUGRU中，我们会保留update gate的original dimensional信息，它会决定每个维度的重要性。基于不同的信息，我们会使用attention score \(a_t\)来将update gate的所有维度进行缩放，这会导致低相关度的兴趣会在hidden state上影响小。AUGRU会更有效地避免来自interest drifting的干扰，并将相关兴趣更平滑地推向evolve。

实验

略

参考

• 1.Deep Interest Evolution Network for Click-Through Rate Prediction

阿里在KDD 2018上开放了它们的方法:《Deep Interest Network for Click-Through Rate Prediction》, 我们来看下：

背景

在电商网站上，比如：阿里巴巴，广告是天然的商品。在本paper的剩余部分，如果没有特别声明，我们会将广告(ads)看成是商品。图1展示了在Alibaba的展示广告系统的运行过程，它包含了两个主要stages：

• i) 匹配阶段（matching）：它会通过类似CF的方法生成与正访问用户相关的候选广告列表
• ii) 排序阶段（ranking）：它会为每个给定广告预测ctr，接着选择topN个排序后广告

图1

每天，有上亿用户访问是电商网络，留给我们大量用户行为数据。值得一提是，带有丰富历史行为的用户包含了多样化的兴趣。例如，一个年轻母亲最近浏览的商品包含：羊毛大衣、T恤、耳环、大手提包、皮手袋、婴儿衣。这些行为数据给了我们一些关于它的购物兴趣的线索。当她访问电商网站时，系统会将合适的广告展示给她，例如，一个新的手提包。很明显，展示广告只会匹配（matches）或者激活（activates）她的部分兴趣。总之，具有丰富用户行为数据的用户兴趣很多样（diverse），可能会受特定广告的局部影响（locally activated）。我们会在paper后展示利用这些特性来构建ctr模型。

4. DIN

不同于竞价排名搜索(sponsored search)，用户进入展示广告系统无需显式的意愿。当构建ctr模型时，需要有效方法来从历史行为中抽取用户兴趣。描述users和ads的特征是在CTR模型中的基本元素。合理充分利用这些特征，以及从它们中挖掘信息很关键。

4.1 特征表示

在工业界CTR预测任务中的数据大多数以多分组类别型（multi-group catgorial)形式存在，例如： [weekday=Friday, gender=Female,visited_cate_ids={Bag,Book}, ad_cate_id=Book], 它通常通过encoding[4,19,21]被转换成高级稀疏二值特征。数学上，第i个特征组(feature group)的编码向量可以使用公式化表示：\(t_i \in R^{K_i}\)。\(K_i\)表示特征组i的维度，这意味着特征组i包含了\(K_i\)个唯一的ids。\(t_i[j]\)是\(t_i\)第j个元素，并且满足\(t_i[j] \in \lbrace 0, 1 \rbrace\)。\(\sum\limits_{j=1}^{K_i} t_i[j]=k\)。k=1的向量\(t_i\)指的是one-hot encoding，而k>1表示multi-hot encoding。接着，一个实例可以以group-wise的形式被表示成：\(x = [t_1^T,t_2^T,, ..., t_M^T]^T\)，其中M是特征组的数目，\(\sum\limits_{i=1}^M K_i = K\)，其中K是整个特征空间的维度。在该方法下，上述实例会有4个分组的特征，如下所示：

\[\underbrace{[0,0,0,0,1,0,0]}_{weekday=Friday} \underbrace{[0,1]}_{gender=Female} \underbrace{[0, .., 1, ..., 1,...,0]}_{visited\_cate\_ids=\lbrace Bag,Book \rbrace} \underbrace{[0,..,1,..,0]}_{ad\_cate\_id=Book}\]

我们系统中用到的整个特征集在表1中描述。它由4个类别组成，用户行为特征通常使用multi-hot encoding向量并包含了关于用户兴趣的丰富的信息。注意，在我们的setting中，没有组合特征（combination features）。我们会使用DNN来捕捉特征的交叉。

4.2 Base Model (Embedding & MLP)

图2a

大多数流行的模型结构[3,4,21]共享一个相似的Embedding&MLP范式，我们称之为base model，如图2左侧所示。它包含了许多部件：

Embedding layer。由于输入是高维二值向量，embedding layer被用于将他们转换成低维dense表示。对于\(t_i\)第i个feature group，假设 \(W_i = [w_1^i, ..., w_j^i, ..., w_{K_i}^i,] \in R^{D \times K_i}\)表示第i个embedding字典，其中\(w_j^i \in R^D\)是一个具有维度为D的embedding vector。Embedding操作会遵循查表机制，如图2所示。

• 如果\(t_i\)是one-hot vector，其中第j个元素\(t_i[j]=1\)，\(t_i\)的embedded表示是一个单一embedding vector \(v_i = w_j^i\)
• 如果\(t_i\)是multi-hot vector，其中对于\(j \in \lbrace i_1,i_2, ..., i_k \rbrace\)有\(t_i[j]=1\)，\(t_i\)的embedded表示是一个embedding vectors列表：\(\lbrace e_{i=1}, e_{i=2}, ..., e_{i_k} \rbrace= \lbrace w_{i_1}^i, w_{i_2}^i, ... w_{i_k}^i \rbrace\)。

Pooling layer和Concat layer。注意，不同用户具有不同数目的行为。因而对于multi-hot行为特征向量\(t_i\)，它的非零值数目会各有不同，从而造成相应的embedding vectors的长度是个变量。由于Fully-connected网络只能处理定长输入。常见的做法[3,4]是将embedding vectors的列表通过一个pooling layer来获得一个固定长度的向量：

\[e_i = pooling(e_{i_1}, e_{i_2}, ..., e_{i_k})\]

…(1)

两种最常用的pooling layers是：sum pooling和average pooling。它可以使用element-wise sum/average操作到embedding vectors列表中。

embedding和pooling layers操作两者都会以group-wise方式将原始稀疏特征映射到多个固定长度表示向量中。接着所有向量被拼接(concatenated)在一起来获得该样本的整个表示向量(overall representation vector)。

MLP。给定拼接后的dense representation vector，FC layers会被用于自动学习特征组合。最近开发的方法[4,5,10]集中于设计MLP的结构来更好的进行信息抽取。

Loss。base model的目标函数为负log似然函数：

\[L = - \frac{1}{N} \sum\limits_{(x,y)\in S} (y logp(x) + (1-y) log(1-p(x)))\]

…(2)

其中S是size N的训练集，x是网络输入，\(y \in \lbrace 0, 1 \rbrace\)是label，p(x)是在softmax layer后的网络输出，它表示样本x被点击的预测概率。

4.3 DIN结构

在表1的所有这些特征中，用户行为特征十分重要，它在电商应用场景中对于建模用户兴趣时扮演重要角色。

表1

Base model可以获取关于用户兴趣的固定长度的表示向量，它通过将所有embedding vectors在用户行为feature group上进行pooling，如等式(1)所示。该表示向量对于一个给定的用户来说保持相同，具有有限维度的用户表示向量在表现用户的多样化兴趣时会是一个瓶颈。为了让它可行，一种简单的方法是扩展embedding vector的维度，但很不幸的是这将极剧地增加学习参数的size。这会导致在有限数据下的overfitting，并增加了计算和存储的负担，这对于一个工业界在线系统是不可接受的。

是否存在一种更优雅的方式，在一个向量中使用有限维来表示用户的多样化兴趣？用户兴趣的局部活跃性（local activation characteristic）给了我们启发，我们设计了一个新模型，称为DIN（Deep interest network）。想像下，当一个年轻母亲访问了电商网站，她找到了展示的新手提包，并点击了它。我们仔细分析下点击行为的驱动力。通过对这位年轻母亲的历史行为进行软搜索（soft-searching），并发现她最近浏览过手提袋(tote bag)和皮手袋（leather handbag）相似的商品，展示广告点刚好与她的兴趣相关。换句话说，行为相关的展示广告可以对点击行为做出重大贡献。DIN在局部活跃兴趣对于给定广告的表示（representation）上有一定注意力（pay attention to），来模仿该过程。DIN不需要使用相同的向量来表示所有用户的多样化兴趣，它会考虑到历史行为与候选广告间的相关度，自适应地计算用户兴趣的向量表示。这种representation vector会随广告的不同而改变。

图2b

图2的右侧展示了DIN的结构。对比起base model，DIN引入了新设计和局部激活单元(local activation unit)，其它的结构完全相同。特别的，activation units可以应用到用户行为特征上，它会执行一个加权求和平均（weighted sum pooling）来自适应地计算：在给定一个候选广告A时的用户表示（user representation \(v_U\)），如公式（3)：

\[v_U(A) = f(v_A, e_1, e_2, ..., e_H) = \sum\limits_{j=1}^{H} a(e_j, v_A) e_j = \sum\limits_{j=1}^H w_j e_j\]

…(3)

其中：

• \(\lbrace e_1, e_2, ..., e_H\rbrace\)是用户u的行为的embedding vectors列表，它的长度为H
• \(v_A\)是广告A的embedding vector。
• \(v_U(A)\)会随着不同的广告而变化。
• \(a(\cdot)\)是一个feed-forward网络，它的输出作为activation weight，如图2所示。

除了两个input embedding vectors外，\(a(\cdot)\)会添加它们的外积（output product）来feed到后续网络中，这对于帮助相关度建模来说是显式可知的。

等式(3)的局部激活单元与NMT任务[1]中的attention方法的思想一致。然而，不同于传统的attention方法，在等式(3)中没有\(\sum\limits_i w_i=1\)的限制，从而可以存储用户兴趣的强度(intensity)。也就是说，在\(a(\cdot)\)的output上进行softmax归一化会被取消。做为替代，\(\sum_i w_i\)的值被看成是：在某种程度上，对活跃用户兴趣的强度的一个近似。例如，如果一个用户的历史行为包含了90%的衣服类，10%电子类。给定两个候选广告（T-shirt和phone），T-shirt会激活大多数那些属于衣服（clothes）的历史行为，并可能给出一个比手机(phone)的\(v_U\)更大值。传统的attention方法通过对 \(a(\cdot)\)的output进行归一化会丢掉在\(v_U\)在数值范围上的辩识度。

我们以序列的方式尝试了LSTM来建模用户历史行为数据，但结果展示并没有提升。不同于在NLP任务中语法限制下的文本，我们的用户历史行为序列可能包含多个并发兴趣（concurrent interests）。在这些兴趣上快速跳过和突然结束，会造成用户行为序列数据看起来有噪声。一个可能的方向是，设计特殊结构来以序列方式建模这样的数据。我们会在后续进行研究。

5.训练技术

在Alibaba的广告系统中，商品和用户的数目规模达到上亿。实际上，训练具有大规模稀疏输入特征的工业界深度网络，十分具有挑战性。在本部分，我们引入了两个实际中很有用的重要技术。

5.1 Mini-batch Aware正则化

训练工业界网络，overfitting是很严峻的挑战。例如，除了细粒度特征外，比如：商品id(goods_ids)这样的特征维度有60亿维（包含了表1描述的关于用户的visited_goods_ids，以及关于ad的goods_id），在训练期间，如果没有正则化（regularization），模型性能在第一个epoch之后会快速下降，如6.5节的图4的黑绿线所示。在训练具有稀疏输入和数亿参数的网络时，直接使用传统的正则化方法（l2和l1正则化）并不实际。以l2正则为例：只有出现在每个mini-batch上的非零稀疏特征，需要在SGD的场景下基于无需正则化的最优化方法被更新。然而，当添加l2正则时，它需要为每个mini-batch的所有参数之上计算l2-norm，这会导致严重的计算开销，当参数扩展至数亿时是不可接受的。

在本paper中，我们引入了一种有效的mini-batch aware regularizer，它只需要计算出现在每个mini-batch上的稀疏特征参数的l2-norm，这使得计算是可行的。事实上，对于CTR预测模型来说，embedding字典贡献了大多数参数，并带来了严重的计算开销。假设\(W \in R^{D \times K}\)表示整个embedding字典的参数，其中D是embedding vector的维度，K是feature space的维度。我们通过抽样（samples）扩展了在W上的l2正则：

\[L_2(W) = \|W\|_2^2 = \sum\limits_{j=1}^K \|w_j\|_2^2 = \sum\limits_{(x,y) \in S} \sum\limits_{j=1}^{K} \frac{I(x_j \neq 0 )}{n_j} \|W_j\|_2^2\]

…(4)

其中：

• \(w_j \in R^D\)是第j维的embedding vector
• \(I(x_j \neq 0)\)表示实例x是否具有特征id j
• \(n_j\)表示特征id j在所有样本中的出现次数

等式(4)可以以mini-batch aware的方式被转换成公式(5)：

\[L_2(W) = \sum\limits_{j=1}^{K} \sum\limits_{m=1}^{B} \sum\limits_{(x,y) \in B_m} \frac{I(x_j \neq 0)}{n_j} \|W_j \|_2^2\]

…(5)

其中:

• B表示mini-batch的数目
• \(B_m\)表示第m个mini-batch

假设\(\alpha_{mj} = \max\limits_{(x,y) \in B_m} I(x_j \neq 0)\)表示是否存在至少一个实例在mini-batch \(B_m\)上具有特征id j。那么等式(5)可以近似为：

\[L_2(W) \approx \sum\limits_{j=1}^K \sum\limits_{m=1}^B \frac{\alpha_{mj}}{n_j} \| w_j \|_2^2\]

…(6)

这种方式下，我们对一个近似的mini-batch aware版本的l2正则进行求导。对于第m个mini-batch，对于特征j的各embedding weights的梯度：

\[w_j \leftarrow w_j - \eta [ \frac{1}{|B_m| }\sum\limits_{(x,y) \in B_m} \frac{\partial L(p(x),y)}{\partial w_j} + \lambda \frac{\alpha_{mj}}{n_j} w_j]\]

…(7)

其中，只有出现在第m个mini-batch特征参数参与正则计算。

5.2 数据自适应激活函数（Data Adaptive Activation Function）

PReLU[12]是一种常用的activation函数：

\[f(s) = \begin{cases} s, & \text{if s > 0} \\ \alpha s, & \text{if s $\leq$ 0} \end{cases} = p(s) \cdot s + (1-p(s)) \cdot \alpha s\]

…(8)

其中，s是activation函数\(f(\cdot)\)输入的某一维，\(p(s)=I(s>0)\)是一个指示函数（indicator function），它控制着\(f(s)\)在两个通道\(f(s)=s\)和\(f(s)=\alpha s\)间的切换。\(\alpha\)是一个可学习参数。这里我们将\(p(s)\)看成是控制函数。

图3

图3的左侧画出了关于PReLU的控制函数。PReLU会采用一个在0值处的硬修正点（hard rectified point），当每个layer的输入遵循不同的分布时它可能并不适合。考虑这一点，我们设计了一种新的data adaptive activation function，称为Dice：

\[f(s) = p(s) \cdot s + (1-p(s)) \cdot \alpha s, p(s)= \frac{1} {1 + e^{-\frac{s-E[s]}{\sqrt{Var[s]+\epsilon}}}}\]

…(9)

控制函数会在图3的右键进行绘制。在训练阶段，\(E[s]\)和\(Var[s]\)是在每个mini-batch中输入的均值(mean)和方差(variance)。在测试阶段，\(E[s]\)和\(Var[s]\)通过在数据上E[s]和Var[s]的移动平均来计算。\(\epsilon\)是一个小的常数，在我们的实践中可以被设置成\(10^{-8}\)。

Dice可以被看成是PReLu的一种泛化。Dice的关键思想是，会根据输入数据的分布自适应调整修正点（rectified point），它们的值被置成输入的平均(mean)。另外，Dice会平滑控制着在两个通道间的切换。当\(E[s]=0\)和\(Var[s]=0\)时，Dice会退化成PReLU.

6. 实验

在本节中，我们进行实验，包含数据集、评估指标、实验设置、模型比较、以及对应的分析。实验会在关于用户行为的两个公共数据集上进行，同时也会在alibaba的展示广告系统中收集到的数据集上进行，效果会与state-of-the-art的CTR预估方法进行比较。两个公共数据集和实验代码在github上有提供。

6.1 数据集和实验设定

Amazon数据集: Amazon数据集包含了产品评论和元数据，可以用于benchmark数据集[13,18,23]。我们在一个称为“电子产品（electronics）”的子集上展开实验，它包含了192403个用户，63001个商品，801个类目，以及1689188个样本。在该数据集上的用户行为很丰富，对于每个用户和每个商品超过5个评论。特征包含：goods_id, cate_id, 用户评论的goods_id_list和cate_id_list。假设一个用户的所有行为是\((b_1, b_2, ..., b_k, ..., b_n)\)，任务是：通过利用前k个评论的商品，预测第(k+1)个评论的商品。会为每个用户使用k=1,2,…,n-2来生成训练数据集。在测试集上，我们给定前n-1个评论的商品预测最后一个。对于所有模型，我们使用SGD作为optimizier，使用指数衰减，它的learning rate从1开始，衰减率设置为0.1.mini-batch设置为32.

MovieLens Dataset：MovieLens数据[11]包含了138493个用户，27278个电影，21个类目和20000263个样本。为了让ctr预测任务更合适，我们将它转成一个二分类数据。原始的用户对电影评分是[0,5]间的连续值，我们将4和5以上的样本标记为正样本（positive），其余为负样本。我们基于userID将数据划分成训练和测试数据集。在138493个用户中，其中10w被随机选到训练集上，其余38493为测试集。任务是基于用户行为预测用户是否会对一个给定的电影给出3以上的评分。特征包括：movie_id, movie_cate_id以及用户评分列表movie_id_list，movie_cate_id_list。我们使用与Amazon数据集相同的optimizer，learning rate和mini-batch size。

Alibaba数据集：我们从Alibaba的在线展示广告系统中收集了真实流量日志，两种的样本用于训练集、其余用户测试集。训练集和测试集的size各自大约为20亿、0.14亿。 对于所有deep模型，所有16个组的特征的embedding vector的维度为12. MLP的Layers设置为 192 x 200 x 80 x 2. 由于数据量很大，我们将mini-batch size设置为5000,并使用Adam作为Optimizier。我们使用指数衰减，它的learning rate初始为0.001,接着decay rate设置为 0.9.

上述数据集相关的统计数据如表2所示。

表2

6.2 算法比较

• LR: 较弱baseline
• BaseModel: 如第4.2节所示，BaseModel采用Embedding&MLP架构。作为较强baseline
• WideDeep:
• PNN:
• DeepFM:

6.3 指标

在CTR预测领域，AUC是广泛使用的指标。它可以测量使用预估CTR对所有ads排序的好坏（包括intra-user和inter-user顺序）。用户加权AUC在[7,13]中引入，它通过在用户上对AUC进行平均，来测量intra-user序的好坏，在展示广告系统中会展示出与在线效果更相关。在实验中我们采用该指标。出于简洁性，我们仍将它看成是AUC。计算如下：

\(AUC = \frac{\sum\limits_{i=1}^n \#impression_i \times AUC_i}{ \sum\limits_{i=1}^n \#impression_i}\) …(10)

其中n是用户数，\(\#impression_i\)和\(AUC_i\)是impression数，AUC对应于第i个用户。

另外，我们根据[25]来介绍RelaImpr指标来测量模型的相对提升。对于一个随机猜测器（random guesser），AUC的值为0.5. 因此，RelaImpr按如下定义：

\[RelaImpr = (\frac{AUC(measured model) - 0.5} {AUC(base model) - 0.5}) \times 100%\]

…(11)

6.4 在Amazon数据集和MovieLens数据集上的结果比较

6.7

6.8 DIN可视化

最后，我们结合案例研究来展示DIN在Alibaba数据集上的内部结果。我们首先确认了局部激活单元（local activation unit）的有效性。图5展示了用户行为各自对应一个候选广告上的激活强度（activation intensity）。正如我们所预料到的，与候选广告具有高相关性的权重更高。

图5

我们接着将学到的embedding vectors进行可视化。还是以之前的年轻母亲为例，我们为该用户随机选择9个类型（dress、sport shoes、bags、等）以及每个类目下的100个商品作为候选广告。图6展示了通过DIN学到的商品embedding vectors的可视化，它使用t-SNE进行表示，相同形状对应相同的类目。我们可以看到，相同类目的商品几乎属于一个聚类，这很明显展示了DIN embeddings的聚类特性。另外，我们通过预测值对候选广告进行着色。图6是这位妈妈在embedding空间上的兴趣密度分布的一个热度图。它展示了DIN可以在候选集的embedding space上，为一个特定用户捕获它的多样化兴趣，从而构成一个多模态兴趣密度分布。

图6

7.结论

在本paper中，我们关注CTR预测任务在电商展示广告场景下的建模。在传统deep CTR模型上使用固定长度的表示（representation）对于捕获用户兴趣多样性(diversity)来说是个瓶颈。为了提升模型的表现力，设计了一种称为DIN的新方法，来激活相关的用户行为，从而为用户兴趣在不同的广告上获取一个自适应表示向量。另外，我们引入了两种新技术来帮助训练工业界深度网络，从而进一步提升DIN的效果。他们可以很方便地泛到到其它工业界deep learning任务上。DIN现在已经在Alibaba中在线展示广告系统上部署。

参考

• 1.Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba

阿里在KDD 2018上开放了它们的方法:《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》, 我们来看下：

介绍

互联网技术持续改变着商业版图，电商变得无处不在。Alibaba blala，10亿用户，2017 GMV是37670亿rmb，2017收入是1580亿rmb。blala。

淘宝有10亿users和2亿items，最重要的问题是，如何帮助用户快速发现需要和感兴趣的items。推荐系统对于达成这个目标来说至关重要。例如，淘宝移动APP的主页（图1），会基于用户过去的行为结合推荐技术生成，贡献了40%的总推荐流量。再者，在淘宝上，收入和流量的大头都来自推荐。简言之，推荐是taobao和alibaba的GMV和收入的核心引擎。尽管在学术界和工业界大多数推荐方法都能获得成功（例如：CF，基于内容的方法，基于deeplearning的方法），但是在淘宝，这些方法面对的问题变得更严峻，因为有海量的用户和海量的items存在。

图1: 虚线框的区域对于淘宝10亿用户来说是个性化的。为了更好的用户体验，吸引人的图片和方案描述也同样是生成的。注意，Taobao移动端主页贡献了40%的总推荐流量

这里淘宝推荐系统有三个主要的技术挑战：

• 可扩展性(Scalability)：尽量许多已经存在的推荐方法可以在小规模数据集上能很好工作(例如：数百万的users和items)，但它们通常会在淘宝的海量数据集上试验失败。
• 稀疏性(Sparsity)：由于用户趋向于只与小部分的items交互，特别是当users或items只有少量交互时，很难训练一个精准的推荐模型。这通常被称为“sparsity”问题。
• 冷启动(cold start)：在淘宝，数百万的新items会在每小时持续被上传。这些items没有用户行为。处理这些items、或者预测用户对这些items的偏好是个挑战，这被称为“cold start”问题。

为了解决这些挑战，我们在淘宝技术平台上设计了two-stage推荐框架。第一阶段称为matching，第二阶段为ranking。在matching阶段，我们会生成一个候选集，它的items会与用户接触过的每个item具有相似性；接着在ranking阶段，我们会训练一个深度神经网络模型，它会为每个用户根据他的偏好对候选items进行排序。由于上述挑战的存在，在两个阶段都会面临不同的问题。另外，每个阶段的目标不同，会导致技术解决方案的不同。

在本paper中，我们主要关注如何解决在matching阶段的挑战，其中，核心任务是，基于用户行为，计算所有items的两两（pairwise）相似度。在获取items的pairwise相似度后，我们可以生成一个items候选集合，进一步在ranking阶段使用。为了达到该目的，我们提出了根据用户行为历史构建一个item graph，接着使用state-of-art的graph embedding方法[8,15,17]来学习每个item的embedding，这被称为BGE（Base Graph Embedding）。在这种方式下，我们可以基于items的embeddings向量进行点乘来计算候选items集合的相似度。注意，在之前的工作中，基于CF的方法来计算这些相似度。然而，基于CF的方法只考虑了在用户行为历史上的items的共现率。在我们的工作中，会在item graph中使用random walk，来捕获items间的高维相似性。这样，它比基于CF的方法要好。然而，为少量或者没有交互行为的items学到精准的embeddings仍是个挑战。为了减轻该问题，我们提供了使用side information来增强embedding过程，这被称为使用Side information的Graph Embedding（Graph Embedding with Side information (GES)）。例如，属于相似的类目或品牌的items在embedding space空间应更接近。在这种方式下，即使items只有少数互交或没有交互，我们也可以获取精确的items embedding。然而在淘宝，有许多种类型的side information。比如类目（category）、品牌（brand）、或价格（price）等，直觉上不同的side information对于学习items的embeddings的贡献也不一样。因而，我们进一步提出了一种加权机制来使用，这被称为Enhanced Graph Embedding with Side information（EGES）。

总之，matching阶段有三个重要的部分：

• (1) 基于在淘宝这些年的实践，我们设计了一个有效的启发式方法，基于在淘宝上10亿多用户的行为历史来构建item graph。
• (2) 我们提供了BGE，GES和EGES，来学习在淘宝上20亿items的embeddings。我们进行离线实验来演示：GES和EGES与BGE、以及其它embedding方法对比的效果。
• (3) 为了部署十亿级users和items的方法，我们基于baobao XTensorflow（XTF）平台来构建graph embedding systems。我们展示了提出的框架可以极大提升在taobao移动端app上的推荐效果，同时能满足在双十一节上的训练效率和实时服务。

paper的其余部分组织如下：第2节介绍三种embedding方法。第3节介绍离线和在线实验结果。第4节介绍在taobao上的系统部署。第5节回顾相关工作。第6节收尾。

2.框架

这一节，首先引入graph embedding的基础，接着详述如何从用户行为历史上构建item graph。最后，我们研究了在淘宝上进行学习items embeddings的方法。

2.1 前提条件

本节，我们会给出一个关于graph embedding的总览，会采用一个很流行的方法：DeepWalk；在此基础上，我们提出了在matching阶段我们的graph embedding方法。给定一个graph：\(G = (V, E)\)，其中V和E分别表示节点集合和边集合。Graph embedding会为空间\(R^d\)上的每个节点\(v \in V\)学习一个低维表示，其中\(d \ll \mid V \mid\)。换句话说，我们的目的是，学习一个映射函数：\(\Phi: V \rightarrow R^d\)，（即：在V中的每个节点表示成一个d维向量）。

在[13,14]中，提出了word2vec来学习在语料中的每个词的embedding。受word2vec的启发，Perozzi等提出了DeepWalk来学习在graph中每个节点的embedding。首先通过运行在graph中的random walk来生成节点序列，接着应用Skip-Gram算法来学习在graph中的每个节点表示。为了维持该graph的拓朴结构，他们需要解决以下的优化问题：

\[minimize_{\Phi} \sum\limits_{v \in V} \sum\limits_{c \in N(v)} -log Pr(c | \Phi(v))\]

…(1)

其中，\(N(v)\)是节点v的邻节点，可以被定义为从v开始在一跳或两跳内的节点。\(Pr(c \mid \Phi(v))\)定义了给定一个节点v后，具有上下文节点c的条件概率。

在本节的其它部分，我们首先会介绍如何从用户行为中构建item graph，接着提供了基于DeepWalk的graph embedding方法来生成在taobao上20亿item上的低维表示。

2.2 根据用户行为构建item graph

图2: 淘宝graph embedding总览： a) **用户行为序列：用户u1对应一个session，u2和u3分别各对应一个session；这些序列被用于构建item graph；b) 有向加权item graph（weighted directed item graph）\(G=(V,E)\); **c)在item graph上由random walk生成的序列； d) **使用Skip-Gram生成embedding

在本节，我们详述了从用户行为构建item graph。现实中，在淘宝上一个用户的行为趋向于如图2(a)所示的序列。之前基于CF的方法只考虑了items的共现，但忽略了顺序信息（可以更精准地影响用户的偏好）。然而，不可能使用一个用户的整个历史，因为：

• 1.计算开销和存储开销会非常大
• 2.一个用户的兴趣趋向于随时间漂移

因此，实际上，我们设置了一个时间窗口，只选择用户在该窗口内的行为。这被称为是基于session的用户行为（session-based）。经验上，该时间窗口的区间是一个小时。

如果我们获取基于session的用户行为，如果两个items它们连续出现，会通过一个有向边进行连接，例如：图2(b)的item D和item A是连接的，因为在图2(a)中用户\(u_1\)顺序访问了item D和A。通过利用在淘宝上所有用户的协同行为，我们会为每条边\(e_{ij}\)基于在所有用户行为的行连接items中的出现总数分配一个权重。特别的，在所有用户行为历史中，该边的权重等于item i转向item j的频次。这种方法中，构建的item graph可以基于所有用户行为表示不同items间的相似度。

实际上，在我们抽取了用户行为序列之前，我们需要过滤一些非法数据和异常行为来为我们的方法消除噪声。下述行为会被我们的系统认定为噪声：

• 如果在一次点击后的停留时长少于1秒，该点击可能是无意识的，需要被移除。
• 在淘宝中有许多”过度活跃(over-active)”用户，它们实际上是有害用户（spam users）。根据我们在淘宝上的时长观察，如果在三个月内，单个用户购买1000个items或者他/她的总点击数超过3500个items，该用户非常可能是一个spam user。我们需要过滤掉这些用户的行为。
• 淘宝零售商们（Retailers）会保持更新一个商品(commodity)的详情。极端情况下，在淘宝上的一个商品可能在一连串更新后，虽然相同的id，但很可能变成了不同的item。因而，这种item也会根据id进行移除。

2.3 基于图的Embedding（BGE）

在我们获取weighted directed item graph后，表示\(G=(V,E)\)。我们采用DeepWalk来学习在图G中的每个节点的embedding。假设M表示G的邻近矩阵（adjacency matrix），\(M_{ij}\)表示从节点i指向节点j的加权边。我们首先基于随机游走生成节点序列，接着在这些序列上运行Skip-Gram算法。随机游走的转移概率定义如下：

\[P(v_j | v_i) = \begin{cases} \frac{M_{ij}}{\sum\limits_{j \in N_{+}(v_i)} M_{ij}}, & v_j \in N_{+}(v_i) \\ 0, & e_{ij} \notin E \end{cases}\]

…(2)

其中，\(N_{+}(v_i)\)表示出链（outlink）的邻节点集合，例如，从\(v_i\)出发指向在\(N_{+}(v_i)\)所有节点的边。通过运行随机游走，我们可以生成如图2(c)所示的许多序列。

接着，我们使用Skip-Gram算法来学习embeddings，它会最大化在获取序列上的两个节点间的共现概率。这会生成以下的优化问题：

\[minimize_{\Phi} - log Pr (\lbrace v_{i-w}, ..., v_{i+w} \rbrace \backslash v_i | \Phi(v_i))\]

…(3)

其中，w是在序列中上下文节点的window size。使用独立假设，我们具有：

\[Pr (\lbrace v_{i-w}, ..., v_{i+w} \rbrace \backslash v_i | \Phi(v_i)) = \prod_{j=i-w, j \neq i}^{i+w} Pr(v_j | \Phi(v_i))\]

…(4)

应用negative sampling，等式4可以转换成：

\[minimize log \sigma (\Phi(v_j)^T \Phi(v_i)) + \sum_{t \in N_(v_i)'} log \sigma(- \Phi(v_t)^T \Phi(v_i))\]

…(5)

其中，\(V(v_i)'\)是对于\(v_i\)的负采样，\(\sigma()\)是sigmoid函数。经验上，\(\mid N(v_i)' \mid\)越大，获得的结果越好。

2.4 使用Side Information的GE（GES）

通过应用2.3节的embedding方法，我们可以学到在淘宝上的所有items的embedding，来捕获在用户行为序列上的更高阶相似度，这种特性会被基于CF的方法忽略。然而，对于“冷启动（cold-start）”的items，学到精准的embeddings仍然是个挑战。

为了解决冷启动问题，我们提出了增强式BGE，它会使用side information来与冷启动items做绑定。在商业推荐系统的场景中，side information常指关于一个item的：类目(category)，shop(商名)，价格(price)等，它们常被当成是ranking阶段的关键特征而广泛使用，但很少用于matching阶段。我们可以通过将side information合并到graph embedding中来缓合cold-start问题。例如，优衣库(UNIQLO：相同店)的两款卫衣（相同类目）可能很相似，一个喜欢Nikon镜头的用户，也可能对Canon相机感兴趣（相似类目和相似品牌）。这意味着这些具有相似的side information的items也可在embedding空间中更接近。基于这个猜想，我们提出了如图3的GES方法。

图3: GES和EGES的总框架。SI表示side information，其中”SI 0”表示item自身。惯例上，1）对于items和不同的SIs，稀疏特征趋向于one-hot-encoder vectors。 2) Dense embeddings是items和相应的SI的表示 3) hidden representation是一个item和它相应的SI的聚合embedding

为了清晰些，我们对概念做了精微调整。我们使用W来表示items或者side information的embedding matrix。特别的，\(W_v^0\)表示item v的embedding，\(W_v^S\)表示绑定到item v上的第s个类型的side information的embedding。接着，对于item v，使用n种类型的side information，我们具有n+1个向量\(w_v^0, ..., W_v^n \in R^d\)，其中，d是embedding的维度。注意，item embeddings和side information embeddings的维度，经验上设置为相同的值。

如图3所示，为了合并side information，我们为item v将n+1个embedding vectors进行拼接，增加一个layer，使用average-pooling操作来将所有与item v的embeddings进行聚合，它是：

\[H_v = \frac{1}{n+1} \sum_{s=0}^n W_v^s\]

…(6)

其中，\(H_v\)是item v的聚合embeddings。这种方法中，我们将side information以这样的方式合并，从而使具有相近side information的items可以在embedding空间内更接近。这会为cold-start items的embeddings更精准些，并且提升了在线和离线的效果。（见第3节）

2.5 增强型EGS（EGES）

尽管GES可以获得收益，但在embedding过程中集成不同类型的side information时，仍存在一个问题。等式(6)中，不同类型的side information对最终的embedding的贡献是相等的，在现实中这不可能。例如，一个购买了IPhone的用户，趋向于会浏览Macbook或者Ipad，因为品牌都是”Apple”；而一个购买了多个不同品牌衣服的用户，出于便利和更低价格，还会在相同的淘宝店上继续购买。因此，不同类型的side information对于在用户行为中的共现items的贡献各不相同。

为了解决该问题，我们提出了EGES方法来聚合不同类型的side information。该框架与GES相同（见图3）。不同之处是，当embeddings聚合时，不同类型的side information具有不同贡献。 因而，我们提出了一个加权平均的average layer来聚合与items相关的side information的embeddings。给定一个item v，假设\(A \in R^{\mid V \mid \times (n+1)}\)是权重矩阵（weight matrix），条目\(A_{ij}\)是第i个item、第j个类型side information的权重。注意，\(A_{*0}\)，即A的首列，表示item v的权限自身。出于简洁性，我们使用\(a_v^s\)来表示关于第v个item的第s个类型的side information的权重，\(a_v^0\)表示item v自身的权重。加权平均层（weighted average layer）会结合不同的side information，定义如下：

\[H_v = \frac{\sum\limits_{j=0}^{n} e^{a_v^j} W_v^j} {\sum\limits_{j=0}^n e^{a_v^j}}\]

…(7)

其中，我们使用\(e^{a_v^j}\)来替代\(a_v^j\)，以确保每个side information的贡献大于0, \(\sum_{j=0}^n e^{a_v^j}\)被用于归一化不同类型side information的embeddings的相关权重。

在训练数据中，对于节点v和它的上下文节点u（即output），我们使用\(Z_u \in R^d\)来表示它的embedding，y来表示label。接着，EGES的目标函数变为：

\[L(v, u, y) = - [ y log(\sigma(H_v^T Z_u)) + (1-y)log(1-\sigma(H_v^T Z_u))]\]

…(8)

为了求解它，梯度求导如下：

\[\frac{\partial L}{Z_u}=(\sigma(H_v^T Z_u) -y) H_v\]

…(9)

对于第s个side information：

\[\frac{\partial L} {\partial a_v^s} = \frac{\partial L} {\partial H_v} \frac{\partial H_v} {\partial a_v^s} \\ = (\sigma(H_v^T Z_u) -y) Z_u \frac{(\sum\limits_{j=0}^n e^{a_v^j}) e^{a_v^s} W_v^s - e^{a_v^s} \sum\limits_{j=0}^n e^{a_v^j} W_v^j} { (\sum\limits_{j=0}^n e^{a_v^j})^2}\]

…(10)

\[\frac{\partial L} {\partial W_v^s} = \frac{\partial L} {\partial H_v} \frac{\partial L} {\partial W_v^s} \\ = \frac{e^{a_v^s}}{\sum\limits_{j=0}^n e^{a_v^j}} (\sigma(H_v^T Z_u) -y ) Z_u\]

…(11)

EGES的伪代码如算法1如示，加权Skip-Gram updater的伪代码如算法2所示。最终每个item的隐表示通过等式(7)来计算：

算法一：

算法二：

3.实验

本节中，我们引入大量实验来演示这些方法的效果。首先通过链接预测任务评估方法，然后是在Taobao移动端APP上的在线实验。最终，我们提出一些真实case来进一步深入这些方法。

3.1 离线评估

链接预测（Link Prediction）。链接预测任务被用于离线实验，因为它是在网络中的一个基础问题。给定移除某些边的一个网络，预测任务是预测这些链接的出现概率。根据在[30]中相似的实验设置，1/3的边被随机选中及移除，在测试集中作为ground truth，图中剩余的边作为训练集。在测试集中，相同数目的没有边连接的节点对（node pairs）会被随机选中作为负样本。为了评估链接预测的效果，使用AUC得分作为metric。

数据集：我们使用两个数据集来进行链接预测任务。第一个是Amazon Electronics数据集。第二个从Taobao移动端APP抽取。两个数据集都包含了不同类型的side information。对于Amazon数据集，item graph可以从“共同购买（co-purchasing）”的关系中被构建（在提供的数据中由also_bought表示），使用了三种类型的side information，例如：类目（category），子类目(sub-category)以及品牌。对于Taobao数据集，item graph通过第2.2节的方法购建。注意，为了效率和效果，在Taobao真实生产环境中，使用了12种类型的side information，包括：零售商（retailer）, 品牌（brand）, 购买级别（purchase level）, 年代（age）, 适用性别（gender）, 风格（style）, 等等。这些类型的side information根据这些年在taobao的实际经验很有用。两个数据集的统计如表1所示。我们可以看到两个数据集的稀疏性大于99%。

表1

比较方法。引入了4种方法进行实验：BGE, LINE, GES和EGES。LINE在[17]中被提出，它可以捕获在graph embedding中的第一阶和第二阶的邻近关系。我们使用由作者提供的实现，使用第一阶和第二阶邻近（LINE(1st)和LINE(2nd)）来运行它。我们实现了其它三种方法。所有这些方法的embedding维度都设置为160.对于我们的BGE、GES和EGES，随机游走的长度为10, 每个节点的walks数目为20, 上下文窗口为5.

表2

结果分析。结果如表2所示。我们可以看到GES和EGES的AUC效果在两个数据集上都要好于BGE、LINE(1st)和LINE(2st)。另换，稀疏性问题也通过合并side information而缓合。当比较Amazon和Taobao的效果时，我们可以看到，在taobao数据集上的效果增益更大。我们将它归功于在Taobao数据集上使用了更多类型的有效的、有信息量的side information。当比较GES和EGES时，我们可以看到，在Amazon上的效果收益比在Taobao上的要大。这可能归功于Taobao的效果已经非常好了，比如：0.97.因而，EGES的提升不显著。在Amazon dataset上，EGES在AUC上的效果要好于GES。基于这些结果，我们可以观察到合并side information对于graph embedding非常有效，准确率可以通过对多个side information的mebeddings进行加权聚合而提升。

图4 2017年11月连续7天内不同方法的在线CTR

3.2 在线A/B test

我们在一个A/B testing框架下进行在线实验。实验的目标是在Taobao APP主页上的CTR。我们实现了上述的graph embedding方法，接着为每个item生成多个相似的items作为推荐候选。最终在Taobao主页（见图1）上的推荐结果，由基于一个DNN模型的ranking引擎生成。在实验中，我们在ranking上使用相同的方法对候选排序。如上所述，相似items的质量直接影响着推荐结果。因而，推荐效果（例如：CTR）可以受matching阶段不同的方法而影响。我们在A/B test框架上部署了4个方法。并对2017年11月中的7天的结果进行展示（如图4）。注意，“Base”表示一个item-based CF的方法，在graph embedding方法部署之前，它被广泛用于淘宝上。它会根据item的共现以及用户投票权重，计算两个items间的相似度。该相似度可以很好地进行调参、并很适合淘宝电商。

从图4我们可以看到，EGES和GES在CTR上的效果要好于BGE、以及Base方法，这展示了在graph embedding上合并side information的效果。另外，Base的CTR要大于BGE。这意味着，经过良好调参的CF-based方法可以战胜简单的embedding方法，因为在实际中会大量使用人工经验的策略。另一方面，EGES会一直胜过GES，它在3.1节的离线实验中一致。这进一步演示了，side information的加权聚合要胜过平均聚合。

3.2 案例研究

在本节中，我们提出了一些在taobao的真实案例，来展示这些方法的效果。这些case会检查三个方面：

• 1.通过EGES的embedding可视化
• 2.冷启动items
• 3.在EGES中的权重

3.3.1 可视化

在本部分，我们会将由EGES学到的items的embeddings进行可视化。我们使用由tensorflow提供的可视化工具。结果如图7所示。从图7(a)，我们可以看到不同类目（categories）的鞋子会在不同的聚类中。这里一种颜色表示一个类目，比如：羽毛球，乒乓球，足球。它演示了学到的合并side information的embeddings的效果。例如，具有相似side information的items在embedding空间中应更接近。从图7(b)看到，我们进一步分析三种鞋子的embeddings：羽毛球，乒乓球，足球。在embedding空间中，羽毛球和乒乓球相互很接近，而足球更更远些。这可以被解释成：在中国，喜欢羽毛球的人很多也喜欢打乒乓球。然而，喜欢足球的人与喜欢户内运动（羽毛球和乒乓球）的人则相当不同。推荐羽毛球鞋给这些观看过乒乓球鞋的人效果要好于推足球鞋的。

3.3.2 冷启动items

图5: 冷启动item的相似items。展示了top4相似的items。注意：这里的”cat”表示category.

在本部分，我们展示了冷启动item的embeddings质量。对于在淘宝上刚更新的一个新item，不能马上在item graph中没法学到embedding，之前基于CF的方法也不能处理冷启动问题。然而，我们可以将一个冷启动item使用它的side information的average embeddings进行表示。接着，我们基于两个items的embeddings的点乘计算，从已经存在的items中检索最相似的items。结果如图5所示。我们可以看到，对于两个冷启动items来说，尽管缺失用户行为，但可以利用不同的side information来有效学到它们的embeddings，在top相似的items上。在图中，我们为每个相似的item注释上：连接到冷启动item上的side information的类型。我们可以看到，items的所属商店（shops）是用于衡量两个items相似度上非常重要的信息，它也会在下面部分使和每个side information的权重进行对齐。

图6: 不同items的不同side information的weights. 这里的”Item”表示一个item本身的embedding

3.3.3 在EGES中的权重

我们会为不同的items作不同类型side information权重可视化。每个在不同类目上的8个items会被选中，与这些items相关的所有side information的权重会从学到的weight matrix A中抽取。结果如图6所示，其中，每一行记录了一个item的结果。可以观察到许多注意点：

• 1.不同items的weight分布很不同，它们会与我们的猜假一致，不同的side information对于最终的表示来说贡献是不同的。
• 2.在所有items中，”Item”的权重，表示了item自身的embeddings，会一直大于其它的side information的权重。必须承认的是，一个item自身的embedding仍然是用户行为的主要源，其中side information提供了额外的提示来推断用户行为。
• 3.除了”Item”外，”Shop”的权重会一直大于其它side information的权重。这与淘宝的用户行为相一致，也就是说，用户可能出于便利或更低价格因素，趋向于购买在相同店内的items。

图7: 随机选中的鞋子的一个集合的embedding可视化。item embeddings通过PCA被投影到一个2D平面上。不同颜色表示不同的categories。相同category中的Item被一起分组。

4.系统部署和操作

本节中介绍graph embedding方法在淘宝的实现和部署。首先给出对淘宝整个推荐平台的一个大体介绍，接着详述与embedding方法相关的模块。

图8: 淘宝推荐平台的架构

在图8中，我们展示了推荐平台的架构。该平台包含了两个子系统：online和offline。对于online子系统，主要组件是TPP（Taobao Personality Platform:淘宝个性化平台）和RSP（Ranking Service Platform: 排序服务平台）。一个典型的workflow如下所示：

• 当用户加载淘宝移动APP时，TPP会抽取用户最新的信息，并从离线子系统中检索一个items候选集，它们会接着被fed进RSP。RSP会使用一个fine-tuned DNN模型对items候选集进行排序，接着返回相应的排序结果给TPP。
• 当用户在淘宝内浏览时，它们的行为会被收集和存储成离线子系统中的日志。

offline子系统的workflow，包含了graph embedding的实现和部署，如下描述：

• 包含用户行为的日志会被检索。item graph会基于用户行为进行构建。实际上，我们会选择最近三个月的日志。在生成基于session的用户行为序列之前，会对数据进行anti-spam。留下的日志包含了6000亿条目。item graph会根据2.2节的方法进行构建。
• 为了运行我们的graph embedding方法，会采用两种实际方法：1) 整个graph划分成许多个sub-graphs，它们可以通过Taobao的ODPs（Open Data Processing Service）分布式平台进行处理。每个subgraph有将近5000w个节点。2)为了生成random walk序列，我们在ODPs中使用基于迭代的分布式图框架。通过random walk生成的序列总是将近1500亿。
• 为了实现该embedding算法，在我们的XTF平台上使用了100个GPU。在部署平台上，使用1500亿样本，在离线子系统中的所有模块，包含日志检索、anti-spam、item图构建、通过random walk生成序列、embedding、item-to-item相似度计算以及map生成，执行过程小于6个小时。这样，我们的推荐服务可以在非常短时间内响应用户最近行为。

参考

• 1.Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba