tensorized DPP介绍

Reading time ~1 minute

criteo也开放了它们的dpp方法:《Tensorized Determinantal Point Processes for Recommendation》, 我们来看下:

摘要

DPP在机器学习中的关注度越来越高,因为它可以在组合集合上提供一种优雅的参数化模型。特别的,在DPP中的所需的参数数目只与ground truth(例如:item catalog)的size成平方关系,而items的数目增长是指数式的。最近一些研究表明,DPPs对于商品推荐和(basket completion)任务 来说是很高效的模型,因为他们可以同时在一个集合中解释diversity和quality。我们提出了一种增强的DPP模型:tensorized DPP,它特别适合于basket completion任务。我们利用来自张量分解(tensor factorization)的思想,以便将模型进行定制用在next-item basket completion任务上,其中next item会在该模型的一个额外维度中被捕获。我们在多个真实数据集上评估了该模型,并找出:tensorized DPP在许多settings中,比许多SOTA模型提供了更好的predictive quality。

1.介绍

在averge shooping basket中items数的增加,对于在线零售商来说是一个主要关注点。该问题存在许多处理策略。而本工作主要关注于:算法会生成一个items集合,它们能适合补全用户的当前shopping basket。

Basket analysis和completion是机器学习中非常老的任务。许多年来,关联规则挖掘(association rule mining)是SOTA的。尽管该算法具有不同变种,主要的准则是涉及到:通过统计在过往observations中的共现,来计算购买一个额外商品的条件概率。由于计算开销和健壮性,现代方法更喜欢i2i CF,或者使用LR基于二分类购买得分来预测一个用户是否会构买一个item。

标准CF方法必须被扩展到能正确捕获商品间的diversity。在basket completion中,需要插入一定形式的diversity,因为推荐过于相似的items给用户并不好。实践者经常通过添加constraints到items推荐集合中来缓和该问题。例如,当使用类目信息时,在裤子被添加到basket时可以强制推荐相匹配的鞋子,而如果按天然的共同出售(co-sale) patterns会导致其它裤子的推荐。在这种情况中,diversity推荐的出现不会通过学习算法直接驱动,但可以通过side information和专家知识。Ref【28】提出了一种有效的Bayesian方法来学习类目的权重,当类目已知时。

然而,不依赖额外信息直接学习合适的diversity更令人关注。不使用side information,直接从数据中的diversity的naive learning,会得到一个高的计算开销,因为可能集合的数目会随类目中items数目而指数增长。该issue是no-trivial的,即使当我们只想往已存在集合中添加一个item时,而当我们想添加超过一个item来达到最终推荐set的diversity时会更难。

【9, 10】使用基于DPPs的模型来解决该组合问题。DPPs是一个来自量子物理学的优雅的关于排斥(repulsion)的概率模型,在机器学习上被广泛使用[17]。它允许抽样一个diverse的点集,相似度(similarity)和流行度(popularity)会使用一个称为“kernel”半正定矩阵进行编码。关于marginalization和conditioning DPPs有很多高效算法提供。从实用角度,学习DPP kernel是个挑战,因为相关的likelihood是non-convex的,从items的observed sets中学到它是NP-hard的。

对于basket completion问题,天然地会考虑:那些转化成售买的baskets的sets。在该setting中,DPP通过一个size为的kernel matrix进行参数化,其中p是catalog(item目录表)的size。因而,参数的数目会随着p的二次方进行增长,计算复杂度、预测、抽样会随着p的三次方增长。由于学习一个full-rank的DPP是很难的,[10]提出了通过对kernel限制到low rank来对DPP正则化(regularization)。该regularization会在不伤害预测效果下提升generalization,并可以提供更diversity的推荐。在许多settings中,预测质量也会被提升,使得DPP对于建模baskets问题是一个理想的工具。再者,对比起full-rank DPP,low-rank假设也提供了更好的runtime效果

另外,由于DPP的定义,正如在Model部分所描述的,low-rank假设对于kernel来说,意味着任意可能的baskets会比那些概率为0的选中rank要具有更好的items。该方法对于大的baskets来说不可能,一些其它DPP kernel的正则化可能更合适。另外,由于DPP kernel的对称性,可以建模有序(ordered corrections)。然而,这些被添加到shooping basket中的items的order会在basket completion任务中扮演重要角色。

主要贡献:

  • 在kernel上修改了constraints来支持大的baskets;也就是说,对于大于kernel rank的sets来说,我们会阻止返回概率0
  • 我们通过在DPP kernel的行列式上添加一个logistic function,来修改在所有baskets上的概率。我们将训练过程适配成处理这种非线性,并在许多real-world basket数据集上评估了我们的模型
  • 通过使用tensor factorization,我们提出了一种新方式来对在目录中的集合间的kernel进行正则化。该方法也会导致增强预测质量
  • 我们展示了这种新模型,称之为”tensorfized DPP”,允许我们可以捕获ordered basket completion。也就是说,我们可以利用该信息,忽略掉items被添加到basket的顺序,来提升预测质量

另外,我们展示了这些思想的组合来提升预测质量,tensorized DPP建模的效果要好于SOTA模型一大截。

2.相关工作

3.模型

DPPs最初用来建模具有排斥效应(replusive effect)的粒子间的分布。最近,在利用这种排斥行为上的兴趣,已经导致DPP在机器学习界受到大量关注。数学上,离散DPPs是在离散点集上的分布,在我们的case中,点就是items,模型会为观察到的给定items集合分配一个概率。假设I表示一个items集合,L是与DPP相关的kernel matrix(它的entries会在items间对polularity和similarity进行编码)。观察到的set I的概率与主子矩阵(principal submatrix)L的行列式成正比:。因而,如果p表示在item catalog中的items数目,DPP是在上的概率measure(),而它只包含了的参数。kernel L会对items间的polularities和similarities进行编码,而对角条目表示item i的流行度,off-diagonal entry 表示item i和item j间的相似度。行列式从几何角度可以被看成是体积(volume),因此更diverse的sets趋向于具有更大的行列式。例如,选择items i和j的概率可以通过以下计算:

…(1)

等式(1)中我们可以看到:如果i和j更相似,他们被抽样在一起的可能性越低。entries 因此会决定kernel的排斥行为。例如,如果使用图片描述符来决定相似度,那么DPP会选择那些有区别的图片。另一方面,如果entries 使用之前观察到的sets学到,比如:电商购物篮[10],那么,“similarity” 会低些。由于共同购买的items可能具有某些diversity,DPPs对于建模包含购买items的baskets是一种天然选择。在搜索引擎场景、或者文档归纳应用中,kernel可以使用特征描述述 (例如:文本中的tf-idf)、以及一个关于每个item i的相关得分,比如:(它会喜欢相关items (值大),阻止相似items组成的lists)。

3.1 Logistic DPP

我们的目标是,寻找一个最可能一起购买的items集合。我们将该问题看成是一个分类问题,目标是预测:一个items的特定集合会生成一个转化(conversion),即:所有items都将被一起购买,这可以表示成。我们将class label Y建模成一个Bernoulli随机变量,它具有参数,其中是items集合,是如下定义的函数:

…(2)

我们使用一个DPP来建模函数

我们假设:存在一个隐空间,在该空间内diverse items很可能会被一起购买。与[10]相似,我们假设:在kernel matrix 上存在一个low-rank constraint,我们进行如下分解:

…(3)

其中,是一个隐矩阵,其中每个row vector i会编会item i的r个latent factors。D是一个对角阵(diagonal matrix),,表示每个item的intrinsic quality或popularity。在D上的平方指数确保了,我们总是具有一个合理的半正定kernel。我们接着定义:

注意,没有对角项,r的选择会限制observable set的cardinality,由于暗示着当。使用该term会确保,任意set的后续概率都是正的,但对于基数(cardinality)高于r的sets,它的cross-effects会更低。我们也看到,具有相似latent vectors的items,对比起具有不同latent vectors的items,被抽到的可能性会更小,由于相似vectors会生成一个具有更小体积(volume)的超平行体(parallelotope)。为了对概率归一化,并鼓励vectors间的分离,我们会在上使用一个logistic function:

…(5)

通常,logistic function的形式是:。然而,在我们的case中,行列式总是正的,因为L是半正定的,这会导致总是大于0.5 。通过构建,我们的公式允许我们获得一个介于0和1之间的概率。最终,是一个scaling参数,可以通过cross-validation被选中,这确保了指数不会爆炸,因于对角参数会近似为1.

Learning。为了学习matrix V,我们确保了历史数据 ,其中,是items集合,是label set,如果该set购买则为1, 否则为0。该训练数据允许我们通过最大化数据的log似然来学习矩阵V和D。为了这样做,我们首先对所有y写出点击概率:

…(6)

的log似然接着被写成:

根据[10],是一个item正则权重,它与item流行度成反比。矩阵V和D可以使用SGA来最大化log似然进行学习。GA的一个step需要计算一个对称矩阵(,其中I是gradient step的相应item set)的行列式,它可以使用 optimized CW-like algorithm算法来达到,复杂度为:,其中,f对应于在I中的items数目。用于学习所使用的最优化算法如算法1所示。

图片名称

算法1

3.3 Tensorized DPP

我们现在提出了对之前模型的一个修改版本,它更适合basket completion任务。为了这样做,对于basket completion场景,我们加强logistic DPP,其中我们对概率建模:用户将基于已经出现在shooping basket中的items来购买一个指定额外的item。我们使用一个tensor来表示它,目标是预测用户是否会基于basket来购买一个给定的candidate target item。该tensor的每个slice对应于一个candidate target item。在该setting中,对于在catalog p中的item (减去basket中已经存在的items),会存在越来越多的问题待解决。为每个待推荐的item学习一个kernel,每个item会与其它所有items相独立,在实际上是不可能的,会存在稀疏性问题。每个item只在baskets中的一小部分出现,因而每个kernel只会接受一小部分数据来学习。然而,所有items间并不完全相互独立。为了解决稀疏性问题,受RESCAL分解的启发,我们使用一个low-rank tensor。我们使用一个cubic tensor ,其中K的每个slice (标为:)是candidate item (low-rank) kernel。通过假设:tensor K是low-rank的,我们可以实现在每个item间学到参数的共享,以如下等式所示:

…(7)

其中,是item latent factors,它对所有candidates items是共用的,是一个candidate item指定的matrix,会建模每个candidate item间的latent components的交叉。为了对candidate items与已经在basket中的items间的自由度进行balance,我们进一步假设:是一个对角矩阵。因此,的对角向量会建模每个candidate item的latent factors,item的latent factors可以被看成是在每个latent factor上的产品的相关度。正如在matrix D的case,在上的平方指数(squared exponent)可以确保我们总是有一个合理的kernel。

图片名称

图1

图1展示了factorization的一个图示。candidate item 的概率与已经在basket中的items set I是相关的:

…(8)

因此,的log似然为:

其中,每个observation m与一个candidate item有关,是与一个observation相关的basket items的set。由于之前的描述,矩阵V, D,以及通过使用SGA最大化log似然学到。正如logistic DPP模型,gradient ascent的一个step需要计算对称矩阵 的逆和行列式,会产生的复杂度(I中items数目为f)。算法2描述了该算法。关于最优化算法的细节详见附录。

图片名称

算法2

泛化到高阶交叉。在basket completion应用中,尝试同时推荐多个items挺有意思的。这可以使用一个贪婪方法来完成。也就是说,我们首先使用一个初始产品(initial product)来补充basket,并将augmented basket看成是一个新的basket,接着补充它。一种更直接的方法是,更适合捕获items间的高阶交叉,这可以泛化等式(7)。我们提出了一种高阶版本的模型,将来会对该模型进行效果评估。假设:d是要推荐的items数目,。我们接着可以将kernel 定义为:

…(9)

其中,每个是一个对角矩阵。

3.3 预测

如前所述,从一个DPP中抽样可能是一个很难的问题,提出了许多解法[6,12]。尽管,在所有可能sets间抽样最好的set是个NP-hard问题,我们的目标是,寻找最好的item来补全basket。在这样的应用中,可以有效使用greedy方法,特别是我们的模型具有low-rank结构。另外,[10]提出了一种有效的方法来进行basket completion,涉及到对DPP进行conditioning,这在我们的logistic DPP模型有使用。

4.实验

5.实验结果

参考

facebook DLRM介绍

# 介绍facebook在2019在《Deep Learning Recommendation Model forPersonalization and Recommendation Systems》。# 摘要facebook开发了一种SOTA的深度学习推荐模型(DLRM)...… Continue reading

ali reranking模型介绍

Published on October 15, 2019

youtube MMoE排序系统

Published on October 11, 2019