#

tmall在《Multi-Interest Network with Dynamic Routing for Recommendation at Tmall》开放了它们的召回算法。在matching stage上,提出了Multi-Interest Network with Dynamic routing (MIND)来处理用户的多样化兴趣。特别的,还基于capsule routing机制设计了一个multi-interest extractor layer,用于聚类历史行为和抽取多样化兴趣。另外,我们还开发了一种称为”label-aware attention”的技术来帮助学习具有多个向量的用户表示 。目前的效果要好于state-of-the-art的其它推荐方法。并在天猫APP的移动端主页上部署,会处理主要的在线流量。

1.介绍

tmall APP的主页如图1(左)所示,它占据着tmall APP的半数流量,并会部署RS来展示个性化的商品来满足客户个性化需求。

图1

由于数十亿规模的users和items,tmall的推荐过程设计包括两部分:matching stage和ranking stage。对于这两阶段,建模用户兴趣和发现可以捕获用户兴趣的用户表示(user representation)非常重要,以便能支持对items的高效检索来满足用户兴趣。然而,由于用户的多样化兴趣的存在,在tmall上建模用户兴趣是很有意义的(non-trivial)。平均上,数十亿用户访问tmall,每个用户每天会与成百上千个商品交互。交互的商品趋向于属于不同类目,可以表示用户兴趣的多样性。例如,如图1(右)所示,不同用户根据它们的兴趣来说是不同的,相同的用户也可能对不同类型的items感兴趣。因此,捕获用户的多样化兴趣的能力变得十分重要。

已经存在的推荐算法会以不同方式建模和表示用户兴趣。CF-based方法可以通过历史交互items[22]或隐因子[17]来表示用户兴趣,可以承受稀疏性问题或计算需要。deep learning-based方法通常以低维embedding vectors来表示用户兴趣。例如,youtube DNN[7]从用户过往行为中转换得到固定长度的vector,它对于建模多样化兴趣可能是个瓶颈,因为在tmall上,它的维度必须很大,以便能表示海量的interest profiles。DIN[31]使用attention机制,使得单个用户对于不同的items会有不同用户表示,这样可以捕获多样化的用户兴趣。然而,采用attention机制也使得它对于海量items的大规模应用来说是在计算上是不可行的,因为它需要为每个item重新计算用户表示(user representation),这使得DIN只适用于ranking stage。

在本paper中,我们主要关注在matching stage上为用户建模多样化兴趣的问题。为了克服已存在方法的限制,我们提出了MIND来学习用户表示,它可以在matching stage上影响用户的多样化兴趣。为了infer用户表示向量,我们设计了一个新的layer,它称为“multi-interest extract layer”,该layer会利用“dynamic routing”[21]机制来自适应地将用户历史行为聚合成用户表示(user repesentation)。dynamic routing的过程被看成是软聚类(soft-clustering),它会将用户的历史行为聚合成许多聚类(clusters)。每个历史行为的cluster会进一步根据一个特定兴趣,被用于infer用户表示的向量。这种方式下,对于一个特定用户,MIND会输出多个表示向量,它们表示共同表示用户的多样化的兴趣。用户表示向量只会被计算一次,并被用于matching stage来从海量items中检索相关items。该方法的主要贡献有:

  • 1.为了捕获用户行为的多样化兴趣,我们设计了multi-interest extractor layer,它可以利用dyniamic routing来自适应地将用户历史行为聚合成用户表示向量。
  • 2.通过使用由multi-interest extractor layer和一个新提出的label-aware attention layer生成的用户表示向量(vectors),我们构建一个DNN来做个性化推荐。对比已存在的方法,MIND在多个公开数据集上和天猫上的效果要好一些。
  • 3.为了在tmall上部署MIND,我们构建了一个系统来实现整个pipline,包括:data collecting、model training和online serving。部署的系统可以极大提升Tmall APP的ctr。

2.相关工作

深度学习推荐。受CV和 NLP的deep learning的成功启发,我们尝试了许多deep learning-based的推荐算法。除了[7,31],还有许多其它deep模型。NCF[11]、DeepFM[9]、DMF[27]会构建由许多MLP组成的神经网络来建模users和items间的交互。[23]提供一种可捕获许多特征的united and flexible network来解决top-N序列推荐。

User Representation。在推荐系统中,将users表示为vectors很常见。传统的方法会将用户偏好组合成由感兴趣的items[4,12,22]、keywords[5,8]和topics[29]的vectors。随着分布式表示学习的出现,user embeddings可以通过NN获得。[6]使用RNN-GRU来从时序阅读文档中学习user embeddings。[30]从word embedding vectors中学习user embedding vectors,并将它们应用于推荐学术微博上。[2]提出了一种新的CNN-based模型来显式学习和利用user embeddings。

Capsule Network。“胶囊(Capsule)”的概念,对一小部分neurons组合输出一整个vector,首次由2011年Hinton[13]提出。用于替代BP,dynamic routing[21]被用于学习capsules间连接的权重,通过利用EM算法[14]来克服多种缺陷并达到较好的accuracy。它与CNN有两个主要不同之处,使得capsule networks可以编码在part和whole间的关系,这在CV和NLP中是很先进的。SegCaps[18]证明,capsules可以成功建模目标的局部关系(spatial),比传统CNNs要好。[28]研究了文本分类的capsule网络,并提出了3种策略来增强效果。

3.方法

3.1 问题公式化

工业界RS的matching stage的目标,从海量item池子I中,为每个用户检索一个items子集,使得该子集包含数千个items,每个item与用户兴趣相关。为了达到该目标,由RS生成的历史数据收集来构建一个matching模型。特别的,每个实例可以通过一个tuple 进行表示,其中:

  • 表示与用户u交互的items集合(也称为:用户行为(user behavior))
  • 是用户u的基础profiles(比如:gender和age)
  • 是target item的特征(比如:item id和category id)

MIND的核心任务是,学习一个函数,来将原始特征(raw features)映射到用户表示上,它可以公式化为:

…(1)

其中,表示用户u的表示向量,d是维度,K是表示向量的数目。当K=1时,只使用一个表示向量,如同Youtube DNN一样。另外,target item i的表示向量通过一个embedding function获取:

…(2)

其中,表示item i的表示向量,的细节会在”Embedding &Pooling Layer”这节详述。

当学习到用户表示向量和item表示向量,top N候选items会根据打分函数进行检索:

…(3)

其中,N是在matching stage中检索出的items的预定义数目。

3.2 Embedding & Pooling Layer

图2 MIND总览。MIND会使用用户行为、用户profile特征作为输入,输出用户表示向量(vectors)以便在matching stage时做item检索。input layer的ID特征通过embedding layer被转换成embeddings,每个item的embeddings(item_id, cat_id, brand_id都会有embedding)会进一步通过一个pooling layer进行平均。用户行为embeddings被feed给multi-interest extractor layer,它会生成interest capsules。通过将interest capsules与user profile embedding进行拼接,并通过一些ReLU layers将concatenated capsules进行转换,可以获得用户表示向量(vectors)。在训练期间,一个额外的label-aware attention layer被引入到指导训练过程。在serving时,多个用户表示向量通过一个ANN查询方式被用于检索items。

如图2所示,MIND的输入包含了三个groups:user profile ,user behavior ,label item 。每个group包含了许多类别型特征(categorical id features),这些id features具有极高的维度。例如,item ids的数目是数十亿的,因而,我们会采用广泛使用的embedding技术来将这些id features嵌入到低维dense vectors(a.k.a embeddings)中,这会极大减小参数数目,并减缓学习过程。对于来自的id features(gender、age等),相应的embeddings会进行拼接(concatenated)来形成user profile embedding 。对于item ids、以及其它类别型ids(brand id, shop id等),对于来自的冷启动items[25],它已经被证明是有用的[25],相应的embeddings会进一步通过一个average pooling layer来形成label item embedding 。最后,对于来自user behavior 的items,相应的item embeddings被组合来形成user behavior embedding

3.3 Multi-Interest Extractor Layer

我们认为,通过一个表示向量来表示用户兴趣,这对于捕获用户多样化兴趣是个瓶颈,因为我们必须将与用户的多样化兴趣相关的所有信息压缩到一个表示向量中。因而,关于用户的多样化兴趣的所有信息,是混合在一起的,对于matching stage来说这会造成错误的item检索。作为替代,我们采用多个表示向量来单独表示用户的不同兴趣。通过该方法,用户的多样化兴趣在matching stage中会被单独对待,对于每个方面的兴趣,使得item检索更精准。

为了学习多种表示向量,我们会使用聚类过程来将用户的历史行为group成一些clusters。在一个cluster中的items被认为是相互更接近的,可以表示用户兴趣的某个特定方面。这里,我们会设计multi-interest extractor layer来对历史行为进行聚类和并对生成的聚类进行inferring表示向量。由于multi-interest extractor layer的设计受最近提出的dynamic routing[13,14,21]的启发,我们首先回顾必要的基础,以便使该paper可以自圆其说。

3.3.1 Dynamic Routing

我们简短介绍capsules表征学习的dynamic routing[21],这是表示向量的一种新的neural units形式。假设我们有两层capsules,我们将第一层看成是low-level capsules,将第二层的capsules看成是high-level capsules。dynamic routing的目标是,给定low-level capsules,以迭代方式计算high-level capsules的值。在每轮迭代中,给定的low-level capsules ,它相应的向量为:

high-level capsules ,它相应的向量为:

在low-level capsule i和high level capsule j之间的routing logit ,可以通过以下公式计算(注:hinton paper中的在此处被展开,即hinton paper中的):

…(4)

其中,表示要学习的bilinear mapping matrix。T表示transpose。

有了routing logits,对于high-level capsule j的候选向量(candidate vector),可以(注:即hinton paper中的耦合系数):

…(5)

其中,表示连接low-level capsule i和high-level capsule j的权重,可以通过在routing logits上执行softmax计算得到:

…(6)

最后,使用一个非线性”squash”函数来获得high-level capsules的vectors:

…(7)

的值被初始化为0, routing process通常会重复三次以便收敛。当routing完成时,high-level capsule的值是确定的,可以被当作是next layers的inputs。

3.3.2 B2I Dynamic Routing

简单来说,capsule是一种新型neuron,它由一个vector表示,而非在普通神经网络中使用的一个标量(scalar)。vector-based capsule被认为是能够表示一个实体的不同属性,在其中,一个capsule的方向(orientation)可以表示一个属性(property),capsule的长度被用于表示该属性存在的概率(probability)。相应的,multi-interest extractor layer的目标是,为用户兴趣的属性(properties)通过学习得到表示(representations)以及学习是否存在相应的兴趣(representations)。在胶囊(capsules)和兴趣表示(interest representations)间的语义关联启发我们将行为/兴趣表示(behavior/interest representations)看成是行为/兴趣胶囊(behavior/interest capsules),并使用dynamic routing来从behavior capsules中学习interest capsules。然而,原始routing算法是为图像数据而提出的,并不能直接应用到处理用户行为数据上。因此,我们提出了Behavior-to-Interest(B2I) dynamic routing来自适应地将用户行为聚合到兴趣表示向量(interest representation vectors)中,它与原始的routing算法有三个不同之处:

1.Shared bilinear mapping matrix.

对于在原始dynimic routing中的每个(low-level capsules, high-level capsules) pair,由于两方面的考虑,我们使用固定的bilinear mapping matrix S来替换一个单独的bilinear mapping matrix。一方面,用户行为是变长的,对tmall用户来说,范围从几十到几百不等,因而,使用定长的bilinear mapping matrix是概括性的。另一方面,我们希望interest capsules位于相同的向量空间中,但不同的bilinear mapping matrice会将interest capsules映射到不同的向量空间上。从而,routing logit可以通过以下公式计算:

…(8)

其中:

  • 表示behavior item i的embedding
  • 表示interest capsule j的向量。
  • bilinear mapping matrix 是跨每个(behavior capsules, interest capsules) pairs间共享的。

2.随机初始化routing logits

由于使用共享的bilinear mapping matrix S,将routing logits初始化到0可能会导致相同初始化的interest capsules。接着,后续的迭代可能会陷入这样的情形,不同的interest capsules在所有时刻都会相同。为了消除该现象,我们会使用高斯分布来抽样一个random matrix来初始化routing logits,使得初始的interest capsules相互间都不同,这与K-means聚类算法相类似。

3.动态兴趣数(Dynamic interest number)

由于不同用户的interest capsules的数目会有不同,我们引入一个启发式规则来为不同用户自适应调整K值。特别的,用户u的K值可以通过下式进行计算(注:表示用户行为item数):

…(9)

对于那些具有更少兴趣的users,调整interest capsules数目的策略,可以节省一些资源(包括计算资源和内存资源)。

整个dynamic routing过程如算法1所示。

a1.png

算法1

3.4 Label-aware Attention Layer

通过multi-interest extractor layer,从用户的行为embeddings可以生成许多的interest capsules。不同的interest capsules表示用户兴趣的不同方面,相关的interest capsule被用于评估在指定items上的用户偏好。因而,在训练期间,我们设计了一个label-aware attention layer,它基于缩放点积注意力(scaled dot-product attention)[24]机制,可以让target item选择要使用哪个interest capsule。特别的,对于一个target item,我们会计算每个interest capsule和target item embedding间的兼容性(compatibilities),并计算一个关于interest capsules的加权求和来当成是该target item的用户表示向量,其中,一个interest capsule的权重由相应的兼容性(compatibility)所决定。在label-aware attention中,label是query,interest capsules是keys和values,如图2所示。user u对于item i的output vector,可以计算如下:

其中:

  • pow表示element-wise指数操作符(exponentiation oprator),pow(x,y)表示x的y次幂;
  • p是一个可调参数,用于调节attention分布。当p接近0时,每个interest capsule趋向于接收偶数(even)attention。当p大于1时,随着p的增加,该值会大于点乘,会接受越来越多的权重。考虑到极限的情况,当p无穷大时,attention机制会变成一种hard attention,它会选中具有最大attention的值,并忽略其它。在我们的实验中,我们发现:使用hard attention会导致更快的收敛。

其它:

  • 表示target item i的embedding
  • :用户u的表示向量,共由K个interest capsules组成
  • :user u对于item i的output vector

3.5 Training & Serving

有了user vector 和label item embedding ,我们可以计算user u和label item i间的概率:

…(10)

接着,对于训练MIND的整个目标函数为:

…(11)

其中,D是包含user-item交互的训练数据集。由于items数目的规模为数十亿,(10)的分母的sum操作在计算上是不可行的。因而,我们使用sampled softmax技术[7]来使目标函数可追踪,并使用Adam optimizer来训练MIND。

在训练后,除了label-aware attention layer外的MIND网络可以被用于user representation mapping函数:。在serving时,用户的行为序列和user profile会feed给函数,为用户生成多个表示向量。接着,这些表示向量通过一个近似最近邻(ANN)方法[15]被用于检索top N个items。对于matching stage,具有与user representation vectors最高相似度的这些items,可以被检索并组合候选items的最终集合。请注意,当一个用户具有新动作时,他的行为序列、以及相应的user representation vectors也会被更改,因而,MIND可以在matching stage上用于实时个性化召回。

3.6 与已存在方法的联系

这里,我们比较了MIND与其它两种已存在方法的关系,展示了相似之处和不同之处。

Youtube DNN. MIND和Youtube DNN都使用深度神经网络来建模用户行为数据并生成用户表示,都被用于在matching stage上检索海量item。然而,Youtube DNN只使用一个vector来表示一个用户,而MIND使用多个vectors。当在算法1中K的值为1时,MIND退化成Youtube DNN,而MIND可以看成是Youtube DNN的泛化(generalization)。

DIN. DIN可以捕获用户的多样化兴趣,MIND和DIN具有相似的目标。然而,这两种方法在达成该目标以及应用上各不相同。为了处理多样化兴趣,DIN会在item级别使用一个attention机制,而MIND使用dynamic routing来生成interest capsules,并在interest level考虑多样性。再者,DIN关注在ranking stage处理上千的items,而MIND会解耦inferring用户表示和衡量user-item兼容性,使它应用于在matching stage上海量items的召回。

4.实验

4.1 离线评估

4.2 超参数分析

4.3 在线实验

通过部署MIND在tmall主页上处理真实流量持续一周,我们开展在线实验。为了公平比较,所有方法在matching stage阶段进行部署,并采用相同的ranking过程。我们使用CTR来衡量online serving流量的效果。

有两种baseline方法进行在线实验。一个是item-based CF,它服务在线流量中的matching算法占居主要地位。另一个是Youtube DNN。我们在一个A/B test框架中部署了所有要比较的方法,它们feed给ranking stage并给出最终推荐。

4.png

图4

实验结果如图4所示。很明显MIND的效果要好于item-based CF和youtube DNN,这表示MIND生成了一个更好的user representation。另外,我们做出了以下观察:

  • 1) 通过长期实践的优化,item-based CF的效果要好于YouTube DNN,它也超过具有单个兴趣的MIND算法。
  • 2) 另一个显著的趋势是,MIND的效果会随着抽取的兴趣数的增加而变好(从1到5)。
  • 3) 当抽取的兴趣数为5时,MIND的效果达到峰值,这之后,CTR保持数据,兴趣数达到7的提升可以忽略。
  • 4) 使用动态兴趣数(dynamic interest number)的MIND与具有7个兴趣的MIND效果相当。

从上述观察来看,我们可以做出一些结论。

  • 首先,对于Tmall,用户兴趣的最优数目是5-7, 这可以表示用户兴趣的平均多样性(diversity)。
  • 第二,动态兴趣数机制并不能带来CTR增益,但在实验期间,我们意识到该scheme可以减少serving的开销,这有利于tmall这样的大规模服务,在实际上更易接受。

总之,在线实验验证了MIND对于建模多样化兴趣的效果,并能极大提升整体RS。

4.4 案例研究

4.4.1 耦合系数

在behavior capsules和interest capsules间的耦合系数,可以量化行为和兴趣级的等级关系。在这一节,我们将这些耦合系数可视化,来展示兴趣抽取过程的可解释性。

5.png

图5

图5展示了从tmall日活用户中随机抽取的两个用户相关的耦合系数,每一行对应于一个interest capsule,每一列对应于一个behavior。它展示了用户C(上)与4个类别的商品(耳机(headphones)、小吃(snacks)、手提包(handbags)、衣服(clothes))有交互,每个商品都在一个interest capsule上具有最大解耦系数,并形成了相应的兴趣。而用户D(下)只在衣服上(clothes)有兴趣,因而,从行为中看到该用户具有3个细粒度的兴趣(毛衣(sweaters)、大衣(overcoats)、羽绒衣(down jackets))。关于该结果,我们证实了user behaviors的每个类都可以聚类在一起,并形成相应的兴趣表示向量。

4.4.2 item分布

7.png

图6

在serving时,与user兴趣相似的items通过最近邻搜索进行检索。我们基于相应兴趣的相似度,对这些通过单个兴趣召回的items的分布进行可视化。图6展示了图5中提到的相同用户(user C)的item分布。该分布分别通过两种方法获取,其中上面的轴4展示了基于MIND通过4个兴趣召回的items,而最下面的轴展示了基于Youtube DNN的结果。items根据它们与兴趣的相似度分散在轴上,通过最大最小归一化法归一化到0~1, 并围绕在0.5附近。上面的一个点指的是在一定范围内的组成的items,因而每个点的大小(size)表示了在相应相似度中items数目。我们也展示了从所有候选中随机选中的一些items。正如所预料的,通过MIND召回的items与对应的兴趣强相关,而Youtube DNN则会与items的类目更宽泛些,它们与用户行为具有较低相似度。

5.系统部署

7.png

图7

当用户加载Tmall APP时,推荐请求会被发送给Tmall Personality Platform,该server集群会将一大堆插件式模块进行集成,并作为在线推荐进行服务。用户最近的行为会通过Tmall Personality Platform进行检索到,并将它发送给User Interest Extractor,它是实现MIND的主模块,用于将用户行为转换成多个user interests。接着,Recall Engine会搜索与user interests最近的embedding vectors相关的items。由不同兴趣触发的items会被合成候选items,并通过用户兴趣的相似度进行排序。从海量item池中选择上千个候选items的整个过程通过User Interest Extractor和Recall Engine来完成,整个过程小于15ms,由于基于MIND的serving的高效性,在items范围和系统响应时间间的tradeoff,这些候选items的top 1000可以通过Ranking Service(它会使用一堆特征来预测ctr)进行打分。最终,Tmall个性化平台会完成最终展示给用户的推荐结果item列表。User Interest Extractor和Ranking Service在Model Training Platform上会使用100 GPUs进行训练,训练过程会执行8个小时。受益于Model Training Platform的高性能,用于预测服务的深度网络会每天更新一次,可以保证最新的商品被计算和被曝光。

参考

hinton在《Dynamic Routing Between Capsules》中提出了“dynamic routing”的概念。我们来看下这篇paper:

abstract

一个capsule是一组neurons,它的activity vector表示了一个特定类型的实体(entity)(比如:一个object或一个object part)的实例参数()。我们使用activity vector的长度(length)来表示实体存在的概率,使用它的方向(orientation)表示实体参数。在一个层级上的Active capsules通过转移矩阵为高级capsules的实例参数做出预测。当多个预测达到一致时,一个更高级别的capsule会变成active态。我们会展示:当训练完后,多层capsule系统会在MNIST上达到state-of-art的效果,它在识别高度重叠的数字上要比CNN要好。为了达到这样的结果,我们使用了一个迭代式routing-by-agreement机制:一个更低层级的capsule会偏向于将它的output发送到更高层级的capsules上,它的activity vectors会与来自低层级capsule的预测做一个大的点积。

1.介绍

人类视觉会通过使用一个关于注视点(fixation points)的细致判别序列,忽略掉不相关细节,来确保只有一小部分的光学阵列(optic array)在最高分辨率上被处理。内省(Introspection)对于理解以下情况效果很差:关于某个场景的知识有多少是来自该注视点序列,以及我们从单个fixation能得到多少知识。但在本paper中,我们将假设,比起单个已被识别的目标和它的属性,单个fixation会带给我们更多。我们假设,我们的multi-layer可视化系统会在每个fixation上创建一个类parse tree结构,我们会忽略:这些单个fixation parse trees是如何协调的。

parse trees通常会通过动态内存分配即时构建。然而,根据【hinton 2000】,我们假设:对于单个fixation,一个parse tree可以从一个确定的multi-layer神经网络(比如: 雕塑从一块岩石中中雕刻出)中雕刻出。每个layer将被划分成许多被称为“capsules”的neurons小分组,在parse tree中每个node会对应一个active capsule。通过使用一个迭代路由过程(iterative routing process),每个active capsule会选择在layer中的一个capsule,作为它在树中的父节点(parent)。对于一个可视化系统中越高层级,该迭代过程会解决将部件分配到整体(assigning parts to wholes)的问题。

在一个active capsule中的neurons的activities,可以表示出现在该图片中一个特定实体(entity)的多种属性。这些属性可能包含许多不同类型的实例参数,比如:pose(位置、大小、方向),deformation(变型)、velocity(速率)、albedo(反射率)、hue(色彩)、texture(纹理)等。一个非常特别的属性是,在图片中实例化实体(instantiated entity)的存在(existence)。表示存在的一个很明显的方式是,通过使用一个独立的logistic unit,它的输出是该实体存在的概率。在本paper中,我们会探索一个有意思的方法,它会使用实例参数向量的整体长度(overall length)来表示实体的存在,并强制向量的方向(orientation)来表示实体的属性。我们会确保:一个capsule的向量输出(vector output)的长度不能超过1,通过使用一个非线性(non-linearity)函数来确保向量在方向保持不变、在幅值上进行缩放。

事实上,一个capsule的输出就是一个向量,使得它可以使用一个很强大的dynamic routing机制,来确保capsule的输出发送到上层(layer above)的一个合适的父胶囊(parent)上。首先,该output会被路由到所有可能的父胶囊上,但它会通过总和为1的耦合系数进行缩减。对于某个capsule的每个可能的父胶囊,该capsule通过将它的output乘以一个权重矩阵计算得到一个“预测向量(prediction vector)”。如果该预测向量与某一父胶囊的输出具有一个大的点积(scalar product,注:标量积、点积、内积、向量的积 dot product = scalar product),那么这就存在一个自顶向下的反馈(top-down feedback):该feedback会增大与该父胶囊的耦合系数(coupling coefficient),而对于其它父胶囊该系数则会降低。这样就增大了该capsule对该父胶囊的贡献,并进一步增大该capsule的预测向量与父胶囊的输出间的点积。这种类型的”routing-by-agreement”远比原始版本的通过max-pooling实现的routing机制要更有效的多。我们会进一步展示,我们的dynamic routing机制是实现该“解释消除(explaining away)”的一种有效方法,解释消除对于将高度重叠的目标进行分割是必须的。

CNN会使用所学到的特征检测器的平移副本(translated replicas)。这允许他们将在一个图片中某一位置获得的较好权重值(good weight values)的知识平移到另一位置上。这在图片解释中被证明是相当有用的。尽管我们使用vector-output capsules来替换CNNs的scalar-output feature detectors、以及使用routing-by-agreement来替代max-pooling,我们仍希望跨空间的复用学到的知识。为了达到该目标,我们让除了capsules的最后一层之外的所有层都是conv的。有了CNNs,我们可以让更高层级的capsules覆盖该图片的更大区域。不同于max-pooling,我们不会丢掉关于该实体在该区域内的准确位置信息。对于低级别的capsules,位置信息是由active capsule所进行“基于位置的编码(place-coded)”。随着结构的上升,在某个capsule的output vector的实值元素(real-valued components)中,越来越多的位置信息是”rate-coded”。从place-coding到rate-coding的转换,加上更高层capsules可以以更多自由度来表示更复杂实体,表明capsules的维度应随着结构的上升而增加

2.一个capsule的inputs和outputs向量是如何计算的

有许多可能的方式来实现capsules的通用思想。该paper的目的并不是探索整个实现空间,而是提供一种可以运转良好的简单实现,并且能用上dynamic routing。

我们希望:一个capsule的output vector的长度用来表示:通过该capsule表示的实体在当前输入中出现的概率。因此,我们使用一个非线性的“压扁(squashing)”函数,来确保短向量长度收缩到几乎为0,长向量收缩到长度在1以下。我们将它留给判别式学习,以便充分利用这种非线性。

…(1)

其中:

  • 是capsule j的向量输出
  • 是它的总输入(total input)

对于除了第一层外的其它层capsules,一个capsule的总输入是一个在所有“预测向量(prediction vectors)”的加权求和。这些预测向量来自于下层(layer below)的capsules,通过将在下层(layer below)中的一个capsule的输出乘以一个加权矩阵得到:

…(2)

其中,是耦和系数,它通过迭代式dynamic routing过程决定

在capsule i和在上层(layer above)中的所有capsules间的耦和系数,总和为1, 通过一个”routing softmax”来决定,该softmax的intial logits 是关于capsule i与capsule j相耦合的log先验概率

…(3)

该log先验(priors)可以同时与所有其它权重一起通过判别式学习学到。他们取决于两个capsules的位置(location)和类型(type),但不会依赖于当前输入图片。接着通过对每个在上层(layer above)中capsule j的当前输出,以及由capsule i做出的预测的一致性(agreement)进行measure,以对初始化的耦合系数进行迭代式地提升。

该agreement就是简单的点积。该agreement就好像被看成是:它是一个log似然,并且在为capsule i连接到更高层级capsules上的所有耦合系数计算新值之前,被添加到initial logit 中。

在conv capsule layers上,每个capsule会将一个关于向量的local grid,并为grid中每个成员、以及对于每种类型的capsule使用不同的转换矩阵,输出到上层(layer above)中每种类型的capsule。

算法1 routing算法

3.数字存在性的margin loss

我们正使用实例向量的长度来表示一个capsule实体存在的概率。我们希望,对于数字类别k,当且仅当该数字出现在该图片上时,顶层(top-level) capsule会具有一个长的实例向量。为了允许多个数字,对于每个数字胶囊(digit capsule)k,我们使用一个独立的margin loss,

…(4)

其中:

  • 表示某个数字分类k出现
  • 会对于没出现的数字类别会降权(down-weighting) loss,从所有digit capsules的activity vectors的长度进行收缩(shrinking),从而停止初始化学习(initial learning)。 我们使用

total loss可以简单认为是所有数字胶囊的losses求和。

4.CapsNet架构

图1 一个具有3 layers的简单CapsNet。该模型会与CNN (Chang 2015)进行比较。在DigitCaps中的每个capsule的activity vector的长度,表示每个数字类别(class)的一个实例的出现,并被用于计算分类loss。是一个在PrimaryCapsules中每个间的权重矩阵。

一个简单的CapsNet结构如图1所示。该结构是浅层的,只有两个卷积层和一个FC layer

第一层Conv1具有256个9x9的conv kernels,它的stride=1, 并使用ReLU activation。该layer会将像素强度转化到局部特征检测器的activities,接着被用于primary capsules的输入。

primary capsules是最低层的多维实体,从一个倒转图的角度看,将primary capsules激活(activating)对应于将渲染过程进行反转(inverting)。比起将实例部件(instantiated parts)组装成熟悉的整体的方式,这是一种非常不同类型的计算,capsules的设计很擅长这种计算。

第二层(PrimaryCapsules)是一个convolutional capsule layer,它使用32 channels的conv 8D capsules(例如:每个primary capsule包含了8个conv units,它具有9x9 kernel以及stride=2)。每个primary capsule的输出会看到所有256 x 81 Conv units,它们的receptive fields与capsule中心位置重叠。在总的PrimaryCapsules中,有个capsule outputs(每个output是一个8D vector),在 grid中的每个capsule会相互共享它们的权重。你可以将PrimaryCapsules看成是Conv layer,其中等式1看成是它的block非线性函数

最后一层(DigitsCaps)对于每个digit类具有一个16D的capsule,这些capsules的每一个会接受来自在layer below中的所有capsules的输入。

我们会在两个连续的capsule layers间(比如:PrimaryCapsules和DigitCaps)进行路由(routing),由于Conv1的输出是1维的,在它的空间上没有方向取得一致(agree)。因此,在Conv1和PrimaryCapsules间不会使用routing。所有的routing logits()被初始化为0。因此,初始化时,一个capsule的output()会被等概率的()发送到所有的父胶囊(parent capsules())上,我们会使用Adam optimizer及tensorflow中的初始参数,包含exponentially decaying learning rate来最小化等式(4)的margin losses的和。

4.1 重构成一个正则方法

我们使用一个额外的reconstruction loss来支持digit capsules将输入数字的实例参数进行编码(encode)。在训练期间,除了正确digit capsule的activity vector外,我们会遮住所有其它digit capsule的vector。接着,我们使用该activity vector来重构输入图片。digit capsule的输出被feed给一个decoder(它由3个FC layer组成,会如图2所示建模像素强度)。我们会对logitsic units的输出和像素强度间的微分平方和做最小化。我们使用乘0.0005将该reconstruction loss缩放,以便它在训练期间不会主导着margin loss。如图3所示,来自CapsNet的16D output的reconstructions是健壮的,它只保留重要细节。

图2 Decoder结构,用于将来自DigitCaps layer的representation重构成一个数字. 图片和Sigmoid layer的output间的欧氏矩离(euclidean distance),在训练期间最小化。在训练期间,我们使用true label来重构target。

图3 一个使用3个routing迭代的CapsNet的样本MNIST test重构。(l,p,r)表示label,prediction和reconstruction。

5.Capsules on MNIST

我们在28x28 MNIST图片集上(它们会在每个方向上shift两个像素,并使用zero padding)执行训练。没有使用其它的数据扩增/变形(augmentation/deformation)。对于训练集和测试集,dataset分别具有60K和10K的图片。

我们使用单一模型进行测试,没有使用任何模型平均方法(model averaging)。Wan 2013使用ensembling、并将数据进行旋转和缩放进行数据扩充,达到了0.21%的test error。如果不使用这两者,仅能达到0.39%。我们在一个3 layer网络上获得了一个较低的test error (0.25%), 该结果之前只能在更深的网络上才能达到。表1展示了不同CapsNet设置在MNIST上的test error,并展示了routing和reconstruction regularizer的重要性。通过增强在capsule vector中的pose encoding,添加reconstruction regularizer可以增强routing的效果。

表1 CapsNet分类的test arruracy。

baseline是一个标准的CNN,它具有(256, 256, 128)三通道的三层conv layer。每个具有5x5 kernels,stride=1。最后的conv layers会通过size为328、129的两个FC layers。最后的FC layer会使用dropout、连接到一个10分类的softmax layer上,并使用cross entropy loss。baseline也会使用Adam optimizer在2-pixel shifted MNIST上训练。baseline被设计成:计算开销接近CapsNet,在MNIST上达到最好的效果。在参数数目上,baseline具有35.4M,而CapsNet具有8.2M参数,不使用reconstruction subnetwork会有6.8M参数。

5.1 一个capsule表示的独立维度(individual dimensions)

由于我们会将单个数字的encoding进行传递,并将其它数字置为0, 一个digit capsule的维度应学到:以该类的数字被实例化的方式跨越变种空间。这些变种(variations)包括笔划粗细、倾斜、宽度。他们也包含了特定数字的变种,比如:数字2的尾部长度. 我们可以看到,可以使用decoder网络来表示独立维度(individual dimensions)。在为正确的digit capsule计算activity后,我们可以feed一个该activity vector的扰动版本给decoder网络,并观察扰动是如何影响reconstruction的。这些扰动的示例如图4所示。我们发现,该capsule的某一维度(out of 16)几乎总是表示该数字的宽度。一些维度表示全局变种的组合,而其它维度则表示在该数字的一个局部上的变种。例如,对于数字6的上半部的长度,以及下半部圈的size,使用不同维度。

图4

5.2 仿射变换的健壮性

实验表明,对比一个传统的卷积网络,对于每个类,每个DigitCaps capsule会学到一个更健壮的表示。由于在手写数字上的倾斜、旋转、样式等上存在天然的变种,训练好的CapsNet必须对于训练数据的仿射变换有一定的健壮性。

为了测试CapsNet对于仿射变换的健壮性,我们在一个padded和translated MNIST训练集上训练了一个CapsNet和一个传统的CNN(maxpooling和dropout)。在该数据集上,每个样本是一个MNIST数字,随机放置在一个40x40像素的黑色背景上。我们接着在affNIST数据集上测试该网络,在该数据集上每个样本是一个随机进行小的仿射变换的MNIST数字。我们的模型不会使用仿射变换进行训练,而是使用在标准MNIST中可见的平移和自然变换。一个使用early stopping并且训练不够的CapsNet,可以在expanded MNIST测试集上达到99.23% accuracy,并在affNIST测试集上达到79%的accuracy。一个传统的CNN可以在expanded MNIST达到99.22%相近的accuracy,在affnist测试集上达到66%。

6.高度重叠数字的分割

dynamic routing可以被看成是一个并行注意力(parallel attention)机制,它允许在一个level上的每个capsule会留意一些在level below上的active capsules, 并忽略其它。这使得该模型可以识别在图片中的多个物体(objects),即使物体(objects)有重叠。Hinton 2000提出了分割和识别高度重叠数字的任务,其它的(Goodfellow 2013等)已经在相同领域测试了他们的网络。routing-by-aggrement使它可以使用一个关于物体形状的先验来帮助分割(segmentation)。

6.1 MultiMNIST数据集

我们通过将一个数字置于另一个不同数字之上,来生成了MultiMNIST训练集和测试集。每个数字会在每个方向上shift最多4个像素生成一张36x36的图片。考虑到在28x28图片中的一个数字被限定在一个20x20的box中,两个数字的bounding box平均有80%部分有重合。对于在MNIST数据集中的每个数字,我们生成了1K的MultiMNIST样本。因此,训练集的size是60M,测试集size为10M。

6.2 MultiMNIST结果

我们的3 layer CapsNet模型,重新使用MultiMNIST训练数据进行训练,它会比我们的baseline CNN模型达到更高的测试分类accuracy。我们在高度重合数字对上达到相同的分类错误率5%,而Ba 2014的sequential attention模型在一个更简单的任务上(更低重合度)才能达到。在测试图片上,它由来自测试集的成对图片组成,我们将由capsules网络生成的两个最可能active digit capsules作为分类。在reconstruction期间,我们一次选中一个数字,并使用所选数字对应的capsule的activity vector来重构所选数字的图片(我们知道该图片,因为我们使用它来生成组合图片)。与我们的MNIST模型唯一的不同之处是,对于learning rate,我们增加了decay step的周期大于10x,因为训练数据集更大。

图5

重构(reconstructions)如图5所示,它展示了CapsNet可以将该图片划分成两个原始的数字。由于该分割(segmentation)并不在像素级别,我们观察到:模型可以正确处理重合(同时出现在两个数字中的一个像素),从而解释所有的像素。每个数字的position和style在DigitCaps中被编码。decoder已经学到了给定该encoding,来重构一个数字。事实上,尽管有重叠它仍能够重构数字,展示了每个digit capsule可以从PrimaryCapsules layer接收到的投票中选择style和position。

我们将两个最可能的active DigitCaps capsules进行编码,一次一个,来获取两个图片。接着,通过使用非零强度给每个数字来分配像素,我们可以为每个数字获得segmentation的结果。

7.其它数据集

我们使用7个模型的ensemble,每个模型通过在24x24 patches的图片上进行3个routing迭代,还在CIFAR10上测试了我们的capsule模型,并达到了10.6%的error。每个模型具有和MNIST上的简单模型相同的架构,除了使用三种颜色channels、以及使用64个不同类型的primary capsule外。我们也发现,它可以为routing softmaxes帮助引入一个“none-of-the-above”类型,因为我们不能期望具有10个capsules的最后一层来解释图片中的everything。当首次应用到CIFAR10时(zeiler 2013),标准CNN达到10.6% test error。

Capsules与生成模型存在同样的一个缺点是,它可能解释在图片中的任何东西,因此,对比起在dynamic routing中使用一个额外的“孤类(opphan category)”时,当建模杂乱东西(clutter)时它会更好。在CIFAR-10中,背景更多变化,从而不能以一个合理size的网络来建模,这可以帮助解释为什么会有更差的效果。

我们也在smallNORB上测试了与MNIST相同的网络构架,它可以达到2.7%的test error rate,这基本上是state-of-the-art的效果。

另外,我们也在SVHN上训练了一个更小的网络。达到4.3%的test error。

参考

阿里在2019又发布了一篇关于tdm(新的称为JTM)的paper:《Joint Optimization of Tree-based Index and Deep Model for Recommender Systems》, 我们来看下:

介绍

为了打破内积形式的限制,并使得任意的关于用户偏好的高级模型对于从整个语料中检索候选的方式在计算上变得可行,之前提出的TDM使用树结构作为index,可以极大提升推荐的accuracy。TDM使用一个树结构来组织items,树中的每个leaf node对应于一个item。TDM假设:每个user-node偏好是指在所有子节点的偏好中具有最大值的节点,就如同一个max-heap一样。在训练阶段,每个user-node偏好的预测模型用于拟合这种类max-heap的偏好分布。与vector kNN-based搜索(index结构需要内积形式)不同的是,在TDM中对偏好建模的形式没有任何限制。在预测时,由训练模型给出的偏好得分,会被用于在tree index中执行layer-wise beam search来检索候选items。在树索引中的beam search的复杂度是log(corpus size),在模型结构上没有限制,这使得高级用户偏好模型在推荐中检索候选变得可行。

index结构在kNN-based搜索、tree-based方法中扮演着不同的角色。在kNN搜索中,user和item的向量表示会首先通过学习得到,接着建立vector search index。而在tree-based方法中,tree-index的结构(hierarchy)也会影响检索模型的训练。因此,如果对tree index和用户偏好模型进行联合训练是一个重要的问题。tree-based方法在学术上也是一个活跃的话题。在已经存在的tree-based方法中,会学到tree结构,以便在在样本/标签空间(sample/label space)中得到一个更好的结构(hierarchy)。然而,在tree-learning阶段,sample/label划分任务的目标与最终目标(比如:精准推荐)并不完全一致。index learning与prediction模型训练间的不一致,会导致整个系统达到一个次优的状态。为了解决该挑战,更好地将tree index和用户偏好预测相协调,我们的工作聚焦于:通过对一个统一的偏好measure进行最优化,来开发一种同时学习树层级结构(tree hierearchy)和用户偏好预测模型。该paper的主要贡献可以归纳为:

  • 我们提出了一种joint optimization框架,为tree-based推荐学习树结构和用户偏好预测模型,其中,会对一个统一的performance measure(比如:用户偏好的accuracy)进行最优化
  • 我们演示了提出的树结构学习算法,它等同于二分图(bipartite graph)的加权最大化matching问题,并给出了一个近似算法来学习树结构
  • 我们提出了一种新方法,它可以更好利用tree index来生成层次化用户偏好(hierarchical user representation),它可以帮助学到更精准的用户偏好预测模型。
  • 我们展示了树结构学习和层次化用户表示两者可以同时提升推荐accuracy。这两个模块可以相互提升,来达到更大的效果提升。

本paper的其余部分如下方式组织:

  • 在第2节,我们会比较一些大规模推荐方法来展示不同
  • 在第3节,我们首先给出一个TDM之前工作的简短介绍,接着详细描述joint learning
  • 在第4节,离线对比和在线A/B test实验结果对比
  • 在第5节,结论

2.相关工作

  • Youtube DNN
  • Yahoo news RNN
  • Label Partitioning for Sublinear Ranking (LPSR)
  • Partitioned Label Trees (Parabel)
  • Multi-label Random Forest (MLRF)
  • FastXML

3.joint optimization

在本节中,我们首先给出了一个TDM的简单回顾。TDM使用一个tree hierarchy作为index,并允许高级深度模型作为用户偏好预测模型。接着,我们提出了关于tree-based index和deep模型的joint learning框架。它会选择性在一个全局loss function下最优化index和预测模型。提出了一个greedy-based tree learning算法来最优化index。在最后一个子节,我们会指定用于模型训练中的层次化用户偏好表示。

3.1 tree-based深度推荐模型

推荐系统需要返回给用户感兴趣的一个items候选集合。实际上,如何从一个大的item库中有效做出检索是个大挑战。TDM使用一棵树作为index,并提出了在该tree上的一个类max-heap的概率公式,其中对于每个非叶子节点n在level l上的用户偏好为:

…(1)

其中:

  • 是用户u喜欢节点n的ground truth概率。
  • 是一个layer归一化项

上述公式意味着:在一个节点上的ground truth的user-node概率,等于它的子节点的最大user-node概率除以一个归一化项。因此,在level l上的top-k节点,必须被包含在在level(l-1)的top-k节点的子节点中,在不损失accuracy的前提下,top-k的leaf items的检索必须被限制在每个layer的top-k节点上。基于这一点,TDM将推荐任务转换成一个层次化检索问题(hierarchical retrieval problem)。通过一个自顶向下的过程,候选items可以从粗到细被逐渐选中。TDM的候选生成过程如图1所示。

图1: Tree-based deep推荐模型 (a) 用户偏好预测模型。我们首先以层次化的方式在对应的layers上的节点上对用户行为进行抽象。接着,用户行为抽象和目标节点(target node)、以及与其它特征(比如:user profile)一起被用于模型的输入。 (b) 树结构(tree hierarchy)。每个item首先会通过一个投影函数分配到一个不同的leaf node上。在leaf level上的红色节点(items)会被选中作为候选集

在corpus中的每个item被分配到树层次结构(tree hierarchy)上的一个的leaf node上。non-leaf nodes可以被看成是一个关于子节点的更粗粒度的抽象。在检索时,为了进行打分,用户信息与节点组合在一起,首先会被向量化成一个用户偏好表示,作为深度神经网络M(例如:FC networks)的输入。接着,用户对该节点感兴趣的概率值通过模型M返回,如图1(a)所示。而对于检索top-k个items(leaf nodes)来说,会以level-by-level的方式执行一个自顶向下的(top-down)beam search策略,如图1(b)所示。在level l中,只有在level l-1上带有top-k概率的子节点被打分和排序来选择k个候选节点。该过程会一直持续,直到达到k个leaf items。

有了tree index,一个用户请求的整体检索复杂度,会从线性降到log(corpus size),而对于偏好模型结构没有任何限制。这使得TDM会打破用户偏好建模的内积形式的限制,它通过引入vector kNN search index和特有的高级深度模型来检索整个corpus的候选,这可以极大提升推荐的accuracy。

3.2 Joint Optimization框架

根据检索过程,TDM的推荐accuracy会通过用户偏好模型M和tree index T的质量(quality)来决定。给定n个关于正例训练数据pairs(它表示user 对target item 感兴趣),决定着模型M会为用户选择哪些non-leaf nodes来达到。为了替换之前单独学习M和T的方式,我们提出了一个全局loss函数来对M和T进行jointly learn。正如我们在实验中所见,对M和T进行jointly optimizing可以提升最终的推荐accuracy。

表示:给定一个user-item pair ,用户u在leaf node 上的偏好概率。其中:是一个投影函数,它将一个item投影到在T上的一个leaf node上。注意,投影函数实际决定着在树中的item的层次结构,如图1(b)所示。模型M被用于估计和输出user-node偏好,其中为模型参数。如果pair 是一个正样本,根据多分类设置,我们具有ground truth偏好

根据max-heap特性,所有的祖先节点(ancestor nodes)的用户偏好概率(注:每一层都有,构成一条路径),例如 应该为1,在其中是在level j上从一个节点到它的祖先节点(ancestor node)投影是在T上的最大level。为了拟合这样一个user-node偏好分布,全局loss函数被公式化成:

…(2)

其中:n为训练样本正例数,我们将在所有正训练样本上对预测的user-node偏好的负log概率进行求和,它们的祖先user-node pairs作为global empirical loss。

算法1

由于对投影函数最优化是一个组合最优化(combinational optimization),它几乎不可能使用基于梯度的算法来同时优化。为了解决它,我们提出了如算法1所示的joint learning framework。它可以根据用户偏好模型和tree hierarchy交替(alternativel)对loss function (2)进行最优化。在模型训练和树学习中,training loss的一致性,可以促进框架的收敛。实际上,如果模型训练和树学习两者可以同时减小(2)的值,算法1确实会收敛,因为是一个递减序列,最低界为0在模型训练中,是为了为每一layer学习一个user-node偏好模型。受益于tree hierarchy,被转换成学习user-node偏好分布,因此可以使用任意的高级深度模型,它们可以通过流行的最优化算法:SGD、Adam等求解。在归一化用户偏好设定中,由于节点数会随着node level指数增加,使用NCE估计,通过sampling策略来避免计算归一化项。树学习的任务是为了在给定时求解,它是一个组合优化问题。实际上,给定树结构,等于发现在corpus C中items与T中的leaf nodes间的最优匹配。更进一步,我们有:

推论1: 本质上是一个分配问题(assignment problem):在一个加权二分图中发现一个最大加权匹配。

证明:假设第k项item 被分配到第m个leaf node ,比如:,以下的加权值可以被计算:

…(3)

其中:

  • 包含了所有正样本抽样对(u,c)
  • 是target item c

如果我们将在T中的leaf nodes和在corpus C中的items看成是顶点(vertices),将leaf nodes和items间的完全连接(full connection)看成是边(edges),我们可以构建一个加权二分图V,是在间边的权重。更进一步,我们可以学到,每个在items和leaf nodes间的assignment ,等于一个关于V的matching。给定一个assignment ,total loss(2)可以通过下式计算:

其中是corpus size。因此,等于寻找V的最大加权匹配(maximum weighted matching)。

对于分配问题,传统算法(比如:经典的匈牙利算法)很难应用于大语料上,因为它们具有很高复杂度。即使对于最简单的贪婪算法,它们会使用最大加权矩阵来贪婪地选择未分配对,该矩阵是一个大的权重矩阵,需要事先计算和存储,这是不可接受的。为了克服该问题,我们提出了一个segmented tree learning算法。

我们不会将items直接分配给leaf nodes,作为替代,我们会自顶向下每隔d个levels会分配items。给定投影函数,我们将从level s到level d的部分权重,表示为:

我们首先会根据投影函数来发现一个分配(assignment)来最大化该投影函数等价于分配所有items到level d的节点上。对于一个具有最大level 的完整二叉树T,每个level d上的节点,会分配不超过的items。这是一个最大匹配问题,可以使用一个贪婪算法进行有效求解,因为如果d选得够好,对于每个item可能位置的数目会极大减小(比如:d=7, 数目为)。接着,每个item c对应在level d()上的祖先节点保持不变,我们接着相继最大化next d levels,递归直到每个item被分配到一个叶子节点后停止。提出的算法在算法2中详细介绍。

算法2

算法2中的第5行,我们使用一个greedy算法,它使用再平衡策略(rebalance strategy)来求解这个子问题(sub-problem)。每个item 会首先将最大权重被分配给在level l中的子节点。接着,为了保证每个子节点的分配不超过个items,会使用一个rebalance过程。为了提升tree learning的稳定性,以及促进整个框架的收敛,对于那些具有超过items的节点,我们优先将在level l中具有相同的assignment的这些节点,保持使用前一轮迭代(比如:)。被分配给该节点的其它items会以权重的降序进行排序,items的超出部分,会根据每个item权重的降序,被移到仍有富余空间的其它节点上。算法2会帮助我们避免存储单个大的权重矩阵。另外,每个子任务可以并行运行,进一步提升效率

3.3 层次化用户偏好表示

如3.1节所示,TDM是一个层次化检索模型,用来从粗到细的方式层次化地生成候选items。在检索时,会通过用户偏好预测模型M贯穿tree index执行一个自顶向下的(top-down)beam search。因此,在每个level中的M任务是异构的(heterogeneous)。基于此,一个关于M的特定层输入(layer-specific input),必须提升推荐的accuracy。

一系列相关工作表明【9,19,22,35,37-39】,用户的历史行为在预测用户兴趣时扮演着重要角色。另外,由于在用户行为中的每个item是一个one-hot ID特征,在deep model输入的生成上,常见的方法是首先将每个item嵌入到一个连续的特征空间上。一个non-leaf node是一个在tree hierarchy中它的子节点的一个抽象。给定一个用户行为序列,其中是用户交互的第i个item,我们提出使用与target node、以及其它可能特征(比如:user profile)一起来生成M在layer l的input,来预测user-node偏好,如图1(a)所示。在这种方式中,用户交互的items的祖先节点被当成抽象的用户行为使用。训练M时,在对应的layer上,我们使用该抽象来替换原始的user-behavior序列。总之,层次化用户偏好表示带给我们两个优点:

  • 层的独立性(layer independence):对于不同layers来说,在layers间共享item embeddings,会像用户偏好的预测模型那样,在训练M时会带来在一些噪声(noises),因为对于不同layers来说targets是不同的。解决该问题的一个显式方法是,对于每一layer,将一个item与一个独立的embedding相绑定来生成M的输入。然而,这会极大增加参数的数目,使得系统很难优化和应用。我们提出的抽象用户行为会使用相应layer上的node embeddings来生成M的input,在训练时达到layer independence,无需增加参数的数目
  • 精准描述(Precise description):M会以层次化方式贯穿tree index来生成候选items。随着所检索的level的增加,在每一level上的候选节点会以从粗到细的方式描述最终的推荐items,直到达到leaf level。提出的层次化用户偏好表示(hierarchical user representations)会抓住检索过程的本质,并在相应layer的nodes上给出一个关于用户行为的精准描述,这可以提升用户偏好的预测,通过减少因太过详细或太过粗粒度描述而引入的混淆(confusion)。例如,在upper layers中M的任务是粗粒度选择一个候选集,用户行为也会在训练和预测时在相同的upper layers上使用均匀的node embeddings进行粗粒度描述

参考

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通过一个矩阵来表示,该矩阵指定了在A的标准可视化实体(canonical visual entity)与通过capsule A发现的该实体的实际实例(actual instantiation)之间的坐标转换。如果我们使用part-whole坐标转换乘以,这样就会将A的标准可视化实体与C的标准可视化实体相关联,我们就可以得到的一个预测。相似的,我们使用来获取另一个预测。如果这些预测是一个好的匹配,通过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(),它会输出shifted后的图片。该网络由多个独立的capsules组成,它们只会在最后一层进行交叉,一起合作生成期望得到的shifted后的图片。每个capsule具有自己的logistic “识别单元(recognition units)”,它们扮演着hidden layer的角色,来计算三个数(numbers):x, y, p,capsule会将它的输出发送给视觉系统的更高层。p是capsule的可视化实体出现在输入图片中的概率。capsule也具有它自己的“生成单元(generation units)”,可以被用于计算capsule对转换后图片的贡献。generation units的输入是,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会将生成的看成是一个额外输入。图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.讨论

略。

参考

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)。尽管它具有相对较弱的理论保证,但它仍被广泛使用,因为它在经验上对效果有前景。贪婪算法(reedy algorithm)[17,32]的己知实现具有的复杂度,其中M是items的总数目。Han et al.的最近工作[20]通过引入一些近似可以将复杂度降到,但会牺牲accuracy。在本paper中,我们提出了关于该贪婪算法的一种准确(exact)实现,它具有的复杂度,它经验上比近似算法[20]要更快

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

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

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

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

2.背景

概念。

  • 集合使用大写字母表示,比如:Z。
  • 表示Z中的元素数。
  • 向量和矩阵分别通过粗体小写字母和粗体大写字母表示。
  • 表示向量或矩阵的转置。
  • 是向量x和y的内积。
  • 给定子集X和Y,是L的子矩阵,通过行中的X和列中的Y索引。

出于简洁,我们假设:

  • 以及
  • 是L的行列式,惯例上

2.1 DPP

DPP是一个优雅的概率模型,它可以表示负作用(negative interactions)[30]。正式的,一个DPP的表示:对于一个离散集合,在(Z的所有子集集合)上的一个概率度量(probability measure)。当P会为空集给出非零概率时,存在一个矩阵,对于所有子集,Y的概率为:

…(1)

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

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

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

下一节为博主注:

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

DPP如何平衡取出的子集的quality和diversity?Kulesza and Taskar[29 3.1节]提供的分解给出了一个更直观的理解:对于任意半正定矩阵(PSD),DPP kernel L可以被分解成一个格兰姆矩阵(Gramian matrix):,其中B的每一列(column)表示真实集(ground set)中N个items之一。依次会将L分解成质量项(quality terms: ) 和归一化多样性特征():

对于向量的Gramian矩阵S,被称为多样性模型(diversity model);q被称为质量模型(quality model)。

可以将2.1中的(1)式改写成:

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

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

一个集合函数是在上定义的一个实数函数。如果一个集合函数f的边际增益(marginal gains)是非增的(no-increasing),例如:对于任意的和任意的,当新增一项i时,满足:

其中,f是次模函数(submodular)。在DPP中的log概率函数也是次模函数(submodular),在[17]中有介绍。次模最大化(submodular maximization)对应是:寻找能让一个次模函数最大化的一个集合。DPP的MAP inference是一个次模最大化过程。

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

那么它就会被添加到中,直到最大边际增益(maximal marginal gain)为负 或者 违反了基数约束。当f是单调的(monotone),例如:对于任意的,贪婪算法会遵循一个的近似保证,它服从一个基数约束[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满足:

…(1)

那么该item就会被添加到已经选中的item set 中。由于L是一个半正定矩阵(PSD matrix),所有主子式都是半正定的(PSD)。假设的柯列斯基分解(Cholesky decomposition)提供如下:

其中V是一个可逆下三角矩阵。对于任意的柯列斯基分解(Cholesky decomposition)可以定为:

…(2)

其中,行向量和标量满足:

…(3)

…(4)

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

…(5)

因此,等式(1)等于:

…(6)

一旦等式(6)被求解,根据等式(2),的Cholesky decomposition变成是:

…(7)

其中,是已经提供的。当一个新item被添加到之后,的Cholesky因子可以被有效更新。

对于每个item i,可以被增量更新。在等式(6)被求解后,将定义成的新向量和标量。根据等式(3)和等式(7),我们有:

…(8)

通过将等式(3)和等式(8)组合,我们可以对进行更新,有:

等式(4)意味着:

…(9)

最初,, 等式(5)意味着: 。完整算法会在算法1中有总结。对于无约束的MAP inference来说停止条件(stopping criteria),或者(当使用基数约束时)。对于后者,我们引入了一个很小的数,并为的数值稳定值将设置为停止条件(stopping criteria)

算法1

在k次迭代中,对于每个item ,更新涉及到两个长度为k的向量内积,总复杂度为。因此,算法1对于无约束MAP inference会在运行,并返回N个items。注意,对于通过额外的(或者对于无约束情况下的)空间来达成。

4.带滑动窗口的多样性

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

…(10)

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

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

算法2

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

5.提升推荐多样性

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

该方法会采用三个输入:

  • 一个候选item集合
  • 一个分值向量(score vector) ,它表示在中的items的相关性
  • 一个半正定矩阵表示每个items pair的相似度。

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

为了在推荐任务上应用DPP模型,我们需要构建kernel matrix。在[30]中所示,kernel matrix可以写成一个格拉姆矩阵(Gram matrix): ,其中B的列可以是表示items的向量(vectors)。我们可以将每个列向量通过(item score)和一个(具有的归一化向量)的两者乘积的方式来构建。kernel L的条目可以被写成是:

…(11)

我们可以将看成是item i和item j间的相似度的度量,例如:。因此,user u的kernel matrix可以被写成是:

其中,是对角阵(diagonal matrix),它的对角向量(diagonal vector)是的log概率是:

…(12)

的item表示是正交时,等式(12)的第二项是最大化的,因而它可以提升多样性。它很清楚地展示了,DPP模型是如何解释被推荐items的相关度和多样性。

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

其中。这对应于一个使用以下kernel的DPP:

其中。我们也会获得log概率的边际增益(marginal gain):

…(13)

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

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

6.实验结果

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

6.1 人造数据集(Synthetic Dataset)

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

,它使用从正态分布上抽取的,以及(其中:D与总的item size M相同,),以及从独立同分布(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 包含了在训练集中的交互items,
  • 候选集通过在中的每个item的50个最相似items进行union得到。
  • 两个数据集的的中位数(median)分别是735(netflix)和811(song).

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

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

其中,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,参数为,它定义了饱和函数

在第一个实验中,我们在Netflix数据集上测试了DPP的参数的trade-off影响。结果如图2所示。随着的增加,MRR一开始会逐渐提升,当时达到最佳值,接着略微减小。ILAD和ILMD会随的递增而单调递减。当时,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个后续items是多样化的。总的来说,如果每次一个用户可以只看到序列的一小部分,w可以是这部分大小(portion size)的阶。其它设置与前一节一致。

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

其中,是在中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实现。我们的算法的时间复杂度,它大大低于state-of-art exact实现。我们提出的加速技术可以应用于在目标函数中PSD矩阵的log行列式的其它问题,比如entropy regularizer。我们也会将我们的快速算法应用到以下场景:只需要在一个滑动窗口中多样化。实验展示了我们的算法要比state-of-art算法要快,我们提出的方法在推荐任务上提供了更好的relevance-diversity的trade-off。

参考