hinton在2012 《Transforming Auto-encoders》中提出了胶囊“capsules”的概念。我们来看下这篇paper:

1.介绍

当前在图片中识别目标(objects)的方法效果很差,并且所使用的方法仍不够智能。一些最好的计算机视觉系统使用方向梯度直方图( histograms of oriented gradients)作为“visual words”,并使用一个天然空间金字塔(crude spatial pyramid)来将这些元素的局部分布进行建模。这样的方法无需精确知道目标在哪就可以正确识别目标(objects)——这种能力用于诊断人类大脑损伤。最好的人工神经网络使用手工编码的、权重共享的schemes(hand-coded weight-sharing schemes)来减小自由参数的数目,并通过对相同kernel的平移拷贝(transpated replicas)的局部池子(local pools)的激活(activities)做子抽样(subsampling)来达到局部平移不变性(local translational invariance)。该方法可以处理在图片中的变化(视角的变化引起),但它很明显不能处理识别任务,比如:脸部识别(facial identity recognition),这类任务需要知道高级部位间的精准局部关系(比如:鼻子和嘴)在经过使用卷积网络做subsampling的多个stages后,在这些姿态(poses)中的高级特征具有许多不确定性。这通常被看成是一个合理的特性,因为它相当于在受限范围内的姿态是不变的,但这使得计算精准的局部关系来说是不可行的。

该paper会讨论CNN尝试这样去做时会误入岐途。作为对在“neurons”的activities的视角不变性(它使用单个标量输入对重复的特征检测器的一个local pool的activities进行归纳)的替代,人工神经网络应使用局部”capsules”来执行对输入的一些相对复杂的内部计算,并接着封装这些计算结果到一个包含高度信息化输出的小向量中。每个capsule会学习识别在一定受限视角条件(viewing conditions)和变形(deformations)等范围内的一个隐式定义的可视化实体(visual entity),它会同时输出在该限定范围内的该实体概率、以及一个“实例参数(instantiation parameters)“的集合,它会包含该可视化实体的精准姿态(pose)、光线照明(lighting)、变形(deformation),与该实体的一个隐式定义的规范版本相关联。当该capsule正常工作时,可视化实体的概率是局部不变的(locally invariant)——随着实体在各种可能出现方式(在capsule覆盖的受限区域内)上移动,该概率不会改变。该实例参数是“等变化的(equivariant)”——随着视角条件(viewing condition)的改变,实体会在appearance manifold上进行移动,该实例参数会通过一个相应的量进行变化,因为他们表示该实体在appearance manifold上的本征坐标。

capsules的主要优点之一是:输出显式的实例参数。该方法提供了一种简单方式通过识别它们的部件(parts)来识别整体(wholes)。如果一个capsule通过学习以向量形式输出它的可视化实体的姿态(pose),那么该向量与该pose在计算机显卡(computer graphics)中的“天然表示(nature representations)”成线性相关,这里存在着一个简单且高度选择性的测试方法,来判断该可视化实体表示是否可以通过两个active capsules(A和B)进行表示,这两个capsules具有合理的局部关系(spatial relationship)来激活一个更高层级的capsule C。假设capsule A的pose outputs通过一个矩阵\(T_A\)来表示,该矩阵指定了在A的标准可视化实体(canonical visual entity)与通过capsule A发现的该实体的实际实例(actual instantiation)之间的坐标转换。如果我们使用part-whole坐标转换\(T_{AC}\)乘以\(T_A\),这样就会将A的标准可视化实体与C的标准可视化实体相关联,我们就可以得到\(T_C\)的一个预测。相似的,我们使用\(T_B\)和\(T_{BC}\)来获取另一个预测。如果这些预测是一个好的匹配,通过capsules A和B发现的实例(instantiations)会在合理的局部关系以便激活capsule C,并且该预测的平均值会告诉我们:通过C表示的更大的可视化实体是如何对应于C的标准可视化实体进行转换的。例如,如果A表示一张嘴(mouth),B表示一个鼻子(nose),他们可以为面部姿态(pose of face)做出预测。如果这些预测达成一致,嘴和鼻子就必须在合理的局部关系内来形成一个脸。关于这种执行形态识别(shape recognition)的方法,其中一个有意思的特性是,局部-整体关系(part-whole)的认识是视角不变性的(viewpoint-invariant),可以通过权重矩阵进行表示,然而,关于当前已观察目标、及它相对应部件(parts)的实例参数的认知是视角等变化的(viewpoint-equivariant),并且可以通过neural activities来表示。

为了获取这个的一个part-whole的结构,“capsules”会实现在该结构中最低层的部件(parts),来从像素强度(pixel intensities)上抽取显式的姿态参数。该paper展示了,如果该神经网络可以直接、非可视的方式访问该变换(direct, nonvisual access to transformations),这些capsules相当容易从成对的转换图片中学习得到。从人类视角上看,例如,一次扫视会引起关于该视网膜图片的一个纯变换(pure translation),皮质(cortex)可以不可见地访问关于眼部移动的信息。

2.学习第一层capsules

一旦像素强度被转换成一个active集合的outputs时,第一层capsules中的每个capsule会生成一个关于它的可视化实体的pose的显式表示,很容易看到,越大越复杂的可视化实体是如何通过使用active、低级capsules的关于poses预测的方式来识别的。但是,第一层capsules是从哪里来的?一个人工神经网络是如何学到将像素强度的表示(language)转换成关于姿态参数(pose parameters)的表示的?该paper提出的该问题会有一个很令人吃惊的简单答案,我们称之为“transforming auto-encoder”。通过使用简单的2D图片和capsules,我们解释了该思想,pose outputs是一个关于x和y的位置。后面我们会泛化到更复杂的姿态(poses)。

图1: 一个transforming auto-encoder的三个capsules,会建模平移(translations)。图中的每个capsule具有3个recognition units和4个generation units。在连接(connections)上的权重可以通过在实际outputs和target outputs之差进行BP学到

如图1所示,考虑该前馈神经网络。一旦它已经被学到,该网络就是确定的(deterministic),输入一张图片,进行平移shifts(\(\Delta x\)和\(\Delta y\)),它会输出shifted后的图片。该网络由多个独立的capsules组成,它们只会在最后一层进行交叉,一起合作生成期望得到的shifted后的图片。每个capsule具有自己的logistic “识别单元(recognition units)”,它们扮演着hidden layer的角色,来计算三个数(numbers):x, y, p,capsule会将它的输出发送给视觉系统的更高层。p是capsule的可视化实体出现在输入图片中的概率。capsule也具有它自己的“生成单元(generation units)”,可以被用于计算capsule对转换后图片的贡献。generation units的输入是\(x + \Delta x\)和\(y+\Delta y\),capsule的generation units对输出图片的贡献,会乘以p,因而 inactive capsules会无效。

为了让transforming auto-encoder生成正确的输出图片,通过每个active capsule计算得到的x和y值,会对应于它的可视化实体的实际x和y位置。并且我们不需要事先知道该可视化实体或它的坐标框架的原点(origin)。

图2: 左图:一个散点图. 其中纵轴表示其中一个capsule对于每张数字图片的x输出,横轴表示如果该图片在x方向上以(+3 或 -3)像素进行shift时该相同capsule的x输出。如果原始图片已经接近该capsule在x坐标可以表示的极限,在该方向上进一步shifting会造成capsule生成错误的答案,但如果对于该capsule为管辖区域外的数据,将它的概率设置为0, 这不会有影响。 右图:9个capsules(纵),10个generative(横) units,对应的outgoing weights

对于该transforming auto-encoder的简单效果演示,我们训练了一个带30个capsules的网络,每个都有10个recognition units和20个generation units。每个capsule会看到一张MNIST数字图片的整体。输入和输出图片都可以使用-2, -1, 0, +1, +2像素在x和y方向上随机进行shift,transforming auto-encoder会将生成的\(\Delta x\)和\(\Delta y\)看成是一个额外输入。图2展示了当输入图片进行shift后,该capsules会以合理的方式输出shift后的x和y值。图2展示了,capsules会学习带高度局部化投影域(projective fields)的generative units。recognition units的receptive fields噪声较多,局部化更少些。

图3 Top: 完全仿射变换,使用一个带有25个capsules的 transforming auto-encoder,每个capsule具有40个recognition units和40个generation units。顶部行展示了输入的图片;中间行展示了输出的图片,底部行展示了被正确变换的输出图片. Bottom:该transforming anto-encoder的前20个generation units,前7个capsules的output weights。

2.1 更复杂的2D转化

如是每个capsule会给出9个real-valued outputs,它们被看成是一个3x3矩阵A,一个transforming auto-encoder可以被训练来预测一个完整的2D仿射变换(affine transformation:平移translation, 旋转rotation, 缩放scaling,裁减shearing)。一个已知矩阵T会被用于capsule A的output上,来获得matrix TA。当预测目标输出图片时,TA的元素接着被当成genreation units的输入。

2.2 在3D视角上建模变化

图4 左:对于训练数据,输入、输出和目标的立体像对(stereo-pairs)。右:对于在训练期间未见过的汽车模型的input、output和target stereo-pairs

使用矩阵乘法来建模视角效果的一个主要潜在优点是,它很容易拷贝到3D上。我们的前置实验(见图4)使用计算机显卡来生成从不同视角上关于汽车的不同类型的立体图片。transforming autoencoder包含了900个capsules,每个具有两个layers(32,64)的RLRU(rectified linear recognition units)。capsules具有11x11像素的receptive fields,它由一个在96x96图片上的30x30 grid组成,两个相邻capsules间的stride为3个pixels。它们不是weight-sharing的。从该layer的64个recognition units中生成的每个capsule,3D方向上的特征(可以用于调参来检测)的一个3x3矩阵表示,同时隐式定义特征出现的概率。该3x3矩阵接着乘以真实的在源图片和目标图片间的转换矩阵,结果被feed给capsule的具有128个GRLU(generative rectified linear units)的单个layer上。该generation unit activities会乘以capsules的“特征出现(feature presence)”概率,结果被用于增加在重构图片(它以capsule的11x11 receptive field的中心为中心)上一个22x22 patch上的强度。由于该数据由图片的立体对组成,每个capsule必须同时在立体对的成员上查看一个11x11 patch,同时也会在重构的22x22 patch的每个成员上进行。

3.讨论

略。

参考

netflix在recsys 2018的paper《Calibrated Recommendations》提出了Calibrated的概念, 我们来看下:

抽要

当一个用户观看了70个爱情片(romance)和30个动作片(action)时,那么很合理的期望结果是:电影推荐的个性化列表中由70%的爱情片和30%的动作片组成。这是个很重要的特性,称为“校准(calibration)”,最近在机器学习的关于公平性(fairness)的背景下重新获得关注。在items推荐列表中,calibration可以保证:一个用户的多个(过往)兴趣领域,受它对应的占比影响。Calibration特别重要,因为推荐系统在离线环境下通常对accuracy(比如:ranking metrics)进行最优化,会很容易导致这样的现象:一个用户的兴趣过少,推荐会被用户的主兴趣”占满”——这可以通过“校正推荐(calibrated recommendations)”来阻止。为了这个目的,我们会描述用于量化calibration程度(degree)的指标,以及一种简单有效的re-ranking算法来对推荐系统的输出进行后处理(post-processing)。

1.介绍

推荐系统在许多不同应用领域提供了个性化的用户体验,包括:电商、社交网络、音乐视频流。

在本paper中,我们展示了:根据accuracy(例如:ranking指标)训练的推荐系统,很容易为一个用户生成集中在主要兴趣领域(main areas)上的items——当用户的兴趣领域越少时,items会趋向于未被充分表示(underrepresented)或者缺失(absent)。随着时间流逝,这样的不平衡推荐会让用户的兴趣领域越来越窄——这与”回音室(echo chambers)效应”或”过滤气泡(filter bubbles)效应”相似。该问题也会在以下情况中存在:一些用户共享相同的账号,其中:使用相同账号的少量活跃用户的兴趣会在推荐中“挤出”。我们会在第2节的一些思维实验(thought experiments)、以及第6节的真实数据实验中展示该效果。

Calibration在机器学习中是一个通用概念,最近在机器学习算法关于公平性(fairness)中开始流行起来。如果关于多个分类的预测比例与实际数据点的比例相一致,那么这个分类算法被称为”calibrated”。相类似的,在本paper中,calibrated recommendations的目标是:影响在推荐列表中一个用户的多种兴趣,以及它们合适的比例。为了这个目的,我们在第3节描绘了calibration degree的量化指标。在第4节,我们提出了一个算法,目标函数使它更接近calibrated,来对一个给定推荐的ranked list进行post-processing。等等

为了方便,我们会使用进行如下释义:

  • 与items交互的用户:观看了电影的用户
  • items类目(categories):genres

2.动机

在本节中,我们描述了一种思维实验,它演示了会造成推荐items列表变得不平衡(unbalanced)的核心机制。我们会使用三个steps开发,从最极端情况开始。

我们会考虑常用的离线环境(offline setting),其中数据集由历史的user-item交互组成,它们被分割成trainset和testset(例如:基于时间、或者随机划分);评估目标(evaluation objective)是:预测在testset中哪些items与用户交互时会达到最佳的accuracy,通常会根据ranking metrics进行量化。该setting的优点是很容易实现,并且可应用到用于CF的公开数据集上。

在我们的示例中,假设一个电影用户在离线训练数据中播放了70部爱情片和30部动作片:我们的objective是生成一个包含10个推荐电影的列表,可以让预测该用户的test-movies的概率最大化(例如:在offline test data中被该用户播放的held-out movies)。这会最大化推荐accuracy。出于简洁性,我们假设:两个genres是完全互斥的(例如:一个电影可以是动作片、或者是爱情片,但不能是动作爱情片)

2.1 分类不平衡(class imbalance)

在第一个以及最极端情况下,假设:我们只知道用户在genres上的偏好,但我们没有在每个genre内的单个电影的额外信息。在缺少任何额外信息的情况下,该问题与机器学习中的不平衡分类问题(imbalanced classification)相类似:通过预测majority class的label,总是会获得最好的预测accuray。在一个二分类问题中,已知有70%的数据点的label为+1的,而剩余30%数据点的label为-1,在缺少其它额外信息的情况下,为所有数据点预测label为+1总是最好的——因为会有70%的数据点是正确的。相反的,如果我们随机使用概率70%和30%(出现在数据中的概率)来预测label +1和label -1,我们期望的预测labels只有0.7 · 70% + 0.3 · 30% = 58%的数据点会是正确的。

回到我们的推荐示例:在缺少其它额外信息情况下,如果我们推荐100%的爱情片给用户(一部动作片也没有),在test data上会获得最好的accuracy。

我们的极端假设是:没有额外信息提供。在真实世界中,会有更多数据提供——然而,数据总是有限或带噪声的,因而,该效应在某种程度上仍会出现。注意,该问题与任何特定的机器学习模型无关。在第6节的真实数据中,我们会展示不平衡推荐的风险:当根据accuracy对推荐系统最优化时,用户只有很少兴趣的genres很容易被“挤出”,而用户兴趣的主要领域(main areas)则会被放大

该问题的另一个视角是,从有偏推荐(biases recommendations)的角度:在理想情况下,提供的数据是没有任何偏差的(biases),在有限数据上的朝着accuracy进行的训练会引入在推荐列表中的一个bias,例如,它会偏向(bias)于用户的主兴趣方向

相反的,做出更平衡(balanced)或校正(calibrated)的推荐的objective,会减少推荐的accuracy,这并不令人吃惊。

2.2 变化的电影概率

该节开发了一种略微更复杂些的思维实验(thought experiment):我们假设:

每个电影i具有一个不同的概率\(p(i \mid g)\),它表示用户u决定播放genre g电影的概率。

之前的示例中,我们已知:\(p(g_r \mid u)\)=0.7 (r: romance movies即爱情片),\(p(g_a \mid u)=0.3\) (a: action movies即动作片)。假设两个电影集合genres是相互排斥的,用户u播放在genre g上的电影i的概率可以通过以下得到:\(p(i \mid u) = p(i \mid g) \cdot p(g \mid u)\)。为了得到最佳预测accuracy,我们已经找到具有被该用户播放的最高概率\(p(i \mid u)\)的10部电影i。我们考虑下:最可能播放的动作片\(i_{g_a,1}\)(例如:在动作片中排序第1的),以及最可能播放的第10个爱情片\(i_{g_r,10}\),我们会获得:

\[\frac{p(i_{g_r,10} | u)}{p(i_{g_a,1} | u)} = \underbrace{\frac{p(i_{g_r,10} | g_r)}{p(i_{g_a,1} | g_a)}}_{\approx 1/2.1} \cdot \underbrace{\frac{p(g_r | u)}{p(g_a | u)}}_{=\frac{0.7}{0.3} \approx 2.33} \approx \frac{2.33}{2.1} > 1\]

…(1)

其中,值2.1通过MovieLens 20 Million数据集[13]确定。在该示例的变种中,第10部爱情片要比最好的动作片具有一个更大的播放概率。因此,根据accuracy,待推荐的最优的10个titles可以全是爱情片title(没有一部动作片)。

2.3 LDA

该示例受LDA的启发。LDA描述了一个用户会以一个2-step方式来选择一个电影:用户首先选择一个genre(topic),然后在该选中genre中选择一个电影(word)。提到LDA有三个原因。

首先,如果我们假设,真实用户选择一部电影会遵循2-step过程,那么LDA模型是合适的模型。当该LDA被训练时,它可以捕获每个用户兴趣的正确平衡(correct balance),以及正确的比例。因而,当遵循该生成过程时,会得到平衡的推荐,推荐列表会通过一次添加一个title的方式迭代式生成:首先,为用户u学到的genre分布\(p(g \mid u)\)中抽样一个genre g,接着根据genre g从学到的分布\(p(i \mid g)\)中抽样一个电影i。与根据\(p(i \mid u)\)进行ranking的电影相对比,Sampling出来的电影会产生更低的accuracy,其中: \(p(i \mid u) = \sum_g p(i \mid g) \cdot p(g \mid u)\)。原因是,具有较小概率值\(p(i \mid u)\)的电影i,会在接近推荐列表的top位置的被抽样到。相反的,ranking是deterministic的,并能保证:用户u喜欢具有最大概率\(p(i \mid u)\)的电影i,会在推荐列表的top,很明显:如果学到的概率\(p(i \mid u)\)被正确估计,那么可以在test data上达到最佳的accuracy。

3.Calibration指标

在本节中,我们描述了关于推荐电影列表的量化calibration degree的指标。我们考虑两个分布,两者都基于每个电影i的genres g分布\(p(g \mid i)\),假设如下:

  • \(p(g \mid u)\):用户u在过去播放过的电影集合H在genres g上的分布:
\[p(g | u) = \frac{\sum\limits_{i \in H} w_{u,i} \cdot p(g | i)}{\sum\limits_{i \in H} w_{u,i}}\]

…(2)

其中,\(w_{u,i}\)是电影i的weight,例如:用户u最近播放有多近。等式(7)有一个正则版本。

  • \(q(g \mid u)\):推荐给user u的电影列表I在genres g上的分布:
\[q(g | u) = \frac{\sum\limits_{i \in I} w_{r(i)} \cdot p(g | i)}{\sum\limits_{i \in I} w_{r(i)}}\]

…(3)

其中,I是推荐电影的集合。电影i的weight会因为它在推荐中的rank r(i)被表示为\(w_{r(i)}\)。可能选项包括在ranking指标中所使用的weighting schemes,比如:MRR和nDCG.

有许多方法来决定这两个分布\(q(g \mid u)\)和\(p(g \mid u)\)是否相似。为了说明这样的分布从有限数据中(由N个推荐电影和M个被该用户播放电影组合)估计得到,使用零假设:两个分布是相同的。这通常将一个独立检验转化成在两个随机变量上的多项分布:genres g,以及一个影响两个电影集合(I和H)的变量。给定:N或M可能实际很小,这对于exact tests是必需的(像多项检验和fisher test)。这些tests在实际上是不可计算的。一种计算高效的方法是:渐近检验(asymptotic tests),比如:G-test或\(x^2\)-test。

我们不会计算p值,我们会忽略有限数据的大小N和M的影响,直接计算分布\(p(g \mid u)\)和\(q(g \mid u)\)。为了该目的,我们会使用KL散度作为calibration metric \(C_{KL}(p, q)\):

\[C_{KL}(p, q) = KL(p || \hat{q}) = \sum\limits_{g} log \frac{p(g | u)}{\hat{q}(g | u)}\]

…(4)

其中,我们会使用\(p(g \mid u)\)作为target分布。如果\(q(g \mid u)\)与它相似,\(C_{KL}(p, q)\)会具有小值。给定,对于一个genre g,如果\(q(g \mid u)=0\)并且\(p(g \mid u) > 0\),则KL散度会背离(diverge),我们会使用下式替代:

\[\hat{q}(g | u ) = (1-\alpha) \cdot q(g | u) + \alpha \cdot p(g | u)\]

…(5)

其中,\(\alpha > 0\),\(\alpha\)值小,以便\(q \approx \hat{q}\)。在我们的实验中,我们会使用\(\alpha = 0.01\)。KL散度具有许多属性,正是在推荐中calibration degree的量化所需:

  • (1) 完美校正(perfect calibration)时,KL为0:\(p(g \mid u) = \hat{q}(g \mid u)\)
  • (2) 当\(p(g \mid u)\)很小时,对于在\(p(g \mid u)\)和\(\hat{q}(g \mid u)\)间的微小差异很敏感。例如,如果一个用户播放的genre只有2%的时间,推荐该genre 1%在KL散度上会被认为是一个较大的差异。比起(一个genre被播放50%,但推荐只有49%)的case差异要更大。
  • (3) 它喜欢更平均、并且更不极端的分布:如表1所示,如果一个用户播放一个genre 30%的时间,推荐31%该genre 会被认为要比29%要好。

这些属性确保了该用户很少播放的genres也可以在推荐列表中相应的比例被影响。作为KL散度的替代,你也可以使用其它f-散度,比如:在p和q间的Hellinger距离,\(C_H(p,q) = H(p,q) = \| \sqrt{p} - \sqrt{q} \|_2 / 2\),其中\(\| \cdot \|_2\)表示概率向量(跨geners)的2-norm。Hellinger距离在零值上是定义良好的;它也对p和q间的小差异敏感,并且当p很小时,degree会小于KL散度。

整体calibration metric C可以通过跨所有users进行\(C(p, q)\)平均。

4.Calibration方法

推荐的calibration是一个与list相关的特性(list-property)。由于许多推荐系统以用一种pointwise/pariwise的方式进行训练,在训练中可能不包括calibration。因而建议:对推荐系统的预测列表以post-processing方式进行re-rank,这也是机器学习中一种calibrating常用方法。为了决定N个推荐电影的最优集合\(I^*\),我们会使用最大间隔相关度(maximum marginal relevance):

\[I^* = \underset{I,|I|=N}{argmax} \lbrace (1-\lambda) \cdot s(I) - \lambda \cdot C_{KL} (p, q(I)) \rbrace\]

…(6)

其中,\(\lambda \in [0, 1]\)决定着两项间的trade-off:

  • (1) s(I):\(s(i)\)表示电影\(i \in I\)被推荐系统预测的scores ,其中:\(s(I) = \sum_{i \in I} s(i)\)。注意,你可以为每个电影的score使用一个单调转换。
  • (2) \(C_{KL}\):calibration metric(等式4),我们已经显式表示了在推荐电影I上的q依赖,它会在等式(6)进行优化

同时注意,更好的calibration会引起一个更低的calibration score,因此我们在最大化问题中必须使用它的负值。

在关注accuracy的推荐与calibration间的trade-off,可以通过等式(6)的\(\lambda\)进行控制。我们会考虑calibration作为推荐列表的一个重要属性,如第5节所示,它会需要一个相当大的值\(\lambda\)。

寻找N个推荐电影的最优集合\(I^*\)是一个组合优化问题,它是NP-hard的。在附录中,我们会描述该最优化问题的贪婪最优化(greedy optimization)等价于一个代理次模函数(surrogate submodular)函数的贪婪最优化。次模函数的贪婪最优化可以达到一个\((1-1/e)\)的最优化保证,其中e是欧拉数。贪婪最优化会从empty set开始,迭代式地每次添加一个电影i:在step n,当我们已经具有n-1个电影组成的集合\(I_{n-1}\),对于集合\(I_{n-1} \cup \lbrace i \rbrace\)可以最大化等式(6)的电影i被添加进行来获得\(I_n\)。该贪婪方法具有额外优点。

  • 首先,它会生成一个关于电影的有序列表(ordered/ranked list)。
  • 第二,该贪婪方法在每个step产生的list在相同size的lists间是\((1-1/e)\)最优的。

即使我们可以生成一个关于N部电影的ranked list,用户可能只会看到前n部(n<N)的推荐,比如:剩余电影只会在下滑后在视见区(view-port)变得可见。除此之外,用户可能会自顶向下扫描关于N部电影的list。在两种情况下,次模函数的greedy optimization会自动保证推荐列表中每个sub-list的前n部电影(n<N)是(1-1/e)最优的。

注意,该方法允许一个电影i根据可能的多个genres g进行加权,如等式(2)和(3)中所用的\(p(g \mid i)\)。再者,如果你根据多个不同的categories(例如:genres、subgenres、languages、movie-vs.-TV-show, etc)对推荐列表进行calibrate,会为每个category添加一个独立的calibration项 \(C_{KL}^{(category)}\),并使用期望的weight/importance \(\lambda^{(category)}\)。生成的多个次模函数的和(sum)仍是一个次模函数,因而最优化问题仍然有效。

5.相关概念

Calibration在机器学习中常被使用,主要在分类中,通常发现简单的post-processing方法很有效。在最近几年,calibration再获关注,特别是在机器学习的fairness中。

在推荐系统文献中,除了accuracy外还有许多指标(详见[21]),其中diversity与calibration比较接近。

5.1 Diversity

Diversity在许多papers中有定义,例如:最小冗余(minimal redundancy)或推荐items间的相似度,可以帮助避免推荐中100%都是爱情片:假设只有两种电影,最diverse的推荐为50%的爱情片和50%的动作片。如果有额外的电影类型,推荐的diversity可以通过推荐用户没观看过的其它genres来增加,比如:儿童片或记录片。Diversity不会保证将动作片的比例从0%增加到30%,从而影响用户的兴趣度。如果在accuracy和diversity之间的trade-off被选定,你可以获得well-calibrated推荐。这在实际中很难达到,因为该trade-off对于每个用户是不同的。这表明,diversity的目标并不使用合适比例来直接影响一个用户的多种兴趣。这与calibrated推荐有一个主要的不同之处。

第二个关键不同点是:diversity可以帮助用户逃脱可能的filter bubble现象,因为它可能包括用户未曾播放过的genres。而calibrated recommendations并没有提供这个重要特性。这驱使我们对calibrated推荐进行一个简单扩展,以便从用户过往兴趣之外的genres的电影可以被添加到推荐列表中:假设\(p_0(g)\)表示一个先验分布,对于所有genres g会使用正值,从而提升在推荐中的diversity——两个明显选择是:均匀分布(uniform distribution)、或所有用户在genre分布上的平均。这种diversity-promoting先验\(p_0(g)\)以及calibration target \(p(g \mid u)\)的加权平均:

\[\bar{p}(g|u) = \beta \cdot p_0(g) + (1-\beta) \cdot p(g | u)\]

…(7)

其中,参数\(\beta \in [0, 1]\),决定了在diversity和calibration间的trade-off。这种extended calibration probability \(\bar{p}(g \mid u)\)可以被用于替代\(p(g \mid u)\)。

在许多paper中,如果一个list只有少量的冗余度或者 在items相似度低,就认为是diverse的。已经提出的大多数方法会生成这样的diverse推荐,比如:[4,15,31,32],包括DPP(行列式点过程)【8,11】,次模最优化【1,2,19】。

第二条研究线是:在还未选择任意n-1个items ranked/displayed上(比如:一个浏览模型),对用户从推荐列表中选择第n个item的概率进行建模。该思想会产生ranking metric(称为:ERR),也被用于生成一个更diverse ranked list的方法中。

只有少量paper解决了该重要的issue:推荐会以适当比例影响用户的多种兴趣[9,25,26],我们会在下面讨论。

比例性的思想首先在[9]中关于搜索结果多样化中提出。在[9]中,提出的指标,称为DP,本质上是一个在分布\(p(g \mid u)\)和\(g(g \mid u)\)间的平方差的修改版本。当它满足calibration metrics的性质1时,它不会表现出其它两个性质:如表1所示,对于target proportions为:60%:40%,当两个genres中具有7:3会接收更不平衡的推荐,但会与均匀5:5的情况一样,得到相同的DP=1。假设:两者都脱离6:4的理想推荐(将某一电影放到另一个genre中),根据性质(3),5:5可以比7:3接收一个更好的calibration score。性质(2)也不会满足,因为当10部电影被评建时,对于1部电影是如何与target分布相背离的程度,DP=1——理想上,该得分对于target distribution 70%:30%会更糟糕,因为它比60%:40%更极端。注意,KL散度会满足表1的性质。在[9]中,生成一个proportional list的算法会使用用于在选举(election)之后坐位安排(seat assignment)的过程,因此,每个party的坐位会与它们收来的投票数(votes)成比例。他们为该过程(procedure)开发了一个概率化版本来解决items属于多个类目的问题,并发现该方法的效果要好于在实验中的原始实验。在完美比例不能达到的情况下,会发现具有某些偏差(deviations)的一个近似解,它们的算法必须将偏差(deviaitons)看成与现有metric不同,因为他们在概念上是无关的。关于该近似解是否服从在calibrated recommendations中所期望的属性是不明显的。

在[25]中,个性化多样性(personalized diversification)从次模化(submodularity)的角度解决。而他们在[25]中提出的一个次模目标函数(等式(2)),由一个log-sum项组成,与我们附录中的等式(8)相似,它与[25]中未描述的KL散度有关。在[25]中仍未讲明的是,该次模函数的实际目标是,推荐多个与它们的weights(例如:[25]中的CTR)成比例的item-categories。

[26]中提出的metric叫BinomDiv,是精心制作的,并且满足性质(2)和(3):例如:关于表1中的target proportions 60%:40%,7:3更极端的推荐是,比更平衡的5:5得到一个更差的分值。这对于proportionality是很重要的性质。它们的指标不满足性质1,然而,即使更放松,采用在perfect calibration情况下的相同固定值(替代0):如果\(p(g \mid u)=q(g \mid u)\),该指标可以采用不同值,取决于推荐列表的长度、以及genres \(p(g \mid u)\)的分布,见表1. 这有两个缺点:首先,metric的一个给定值,不能为提供一种该推荐是如何calibrate的感觉——对于一个特定用户,它只允许你根据不同推荐列表做出相对比较。第二,假如每个用户趋向于具有不同分布的兴趣/类目(interests/genres),该指标不能简单地跨用户平均的方式来获得一个聚合指标。为了评估,该指标会转化成一个z-score。我们也发现:当推荐电影的数目超过数百时,指标计算会遭受数值下溢(numerical underflow)——这在许多应用中会引起问题,比如:top10推荐,同时也有推荐数百items的场景,比如:Netflix主页。除此之外,我们注意到,增加一个先验(prior)的思想在[26]有提及。该算法会基于最大间隔相关度(maximum marginal relevance)[6]。这些指标可能不是次模的(submodular),然而,他们可能不存在一个最优保证。

5.2 公平性(Fairness)

在机器学习领域中,fairness的重要性越来越大,例如:[33]。Fairness是避免对在总体(polulation)中特定人或人群的歧视,例如,基于gender、race、age、等。它通常与总体中个人的scores或class labels有关。

在文献中,提出了许多公平性准则(fairness criteria),包括:calibration、等可能性(equalized odds)、机会均等(equal opportunity)、统计平等(statistical parity)。[12]中提出了一种post-processing方法,使用equalized odds作为fairness-metric。[28]提出了将fairness集成到training objective中。

在CF的内容中,[29]讨论了在user-base中的少量亚种族(sub-populations,例如:人口不均衡),以及更低活跃的亚种族(例如:提供更少评分的人)可能会收到更偏的推荐。除此之外,[29]还关注在rating prediction和RMSE,替代隐式反馈数据和ranking metrics的更相关场景。

在该paper中,我们会考虑fairness的一个完整概念:除了考虑人的fairness外,我们会考虑一个用户多种兴趣(various interests)上的公平性(fairness),目标是根据它相应的兴趣比例进行影响。在本节剩余部分,我们会描述,为什么calibration criteria对于fairness的非标准概念特别有用。

如[16]所示,calibration和equalized odds/equal opportunity不会被同时满足(精确,非近似)——除了两个特例:当机器学习模型做出perfect predictions(它们会被公平对待),或者当不同分组的用户具有相同的base rate时,例如:相同比例的positive classification-labels,它通常不会在真实中hold。假设一个用户通常使用不同比例播放genres(比如:70%爱情片,30%动作片),这两种genres(在fairness文献中被称为”groups”)的base rate很明显不同,对于在这两个genres中的电影的平均预测得分也不同。因此,fiarness criteria equalized odds、equal opportunity以及statistical parity不能立即应用到我们的context中。这驱使我们在推荐中将calibration作为一种合适的fairness criteria。

参考

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\),即:一个用户对于一个特定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

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

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

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

图1

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

为了消除redundancy问题。首先,我们引入了受[32,45]的启发法到policy layer,比如:对于任意用户的feed,单个的uploader可以贡献不超过n个items。而该规则有时很有效,我们的体验是它与底层推荐系统的交互相当贫乏(poorly)。由于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的函数。如果存在许多相似的items具有与\(q_i\)相近的值,它会在排序(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 设计需要

4.方法

4.1 DPP总览

4.2 Kernel参数化

4.3 训练方法

我们的训练集包含了将近4w的样本,它们从Youtube mobile主页feed上收集的某天数据中抽样得到。每个训练样本是单个主页feed曝光:单个实例,一个用户在youtube mobile主页上的,并被呈现一个关于推荐视频的有序列表。对于每个这样的曝光,我们有一个关于用户喜欢哪些视频的记录,我们表示为 set Y。我们注意到,使用这样的数据来训练模型存在一个partial-label bias,因为我们只观察到用户与那些被选中呈现给他们的视频的交互,而非随机均匀选中的视频。通常,我们会使用与过去训练pointwise模型相同类型的方式来解决该问题,比如:使用一个e-greedy exploration策略。

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

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似然作为一个目标函数的能力,

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

参考

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 i \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\)。

该方法会采用三个输入:

  • 一个候选item集合\(C_u\)
  • 一个分值向量(score vector) \(r_u\),它表示在\(C_u\)中的items的相关性
  • 一个半正定矩阵\(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变得更相似而减小。

参考

阿里在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。

实验

参考