阿里在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进行粗粒度描述

参考

microsoft在开放了inner product快速计算的方法:《Speeding Up the Xbox Recommender System Using a Euclidean Transformation for Inner-Product Spaces》。主要解决inner product top-k search问题,我们来看下:

介绍

在线服务数据的大量增长,对于更好的信息过滤信息提出了新的风险与挑战。在推荐系统中,包括:

  • (1) item目录(catalog)
  • (2) users
  • (3) 用户反馈(ratings)

推荐系统的目标是,为每个用户找到一个限定集合的items,它们具有最可能的机会被消费。现代推荐系统有两个主要部分。第一部分:学习阶段,基于user feedback的离线模型学习。第二部分:检索阶段,对每个用户(在线)推荐items。该paper主要在第二阶段,推荐系统基于MF。特别的,对一个用户的推荐,我们引入了一个新方法来在运行时长(running time)和结果质量间做权衡。

MF是CF中最流行的方法。该方法要比其它近邻方法要好。在MF模型中,users和items通过latent feature vectors表示。Bayesian MF模型是Xbox推荐系统的核心,它每天会为数百万的用户提供游戏、电影、音乐推荐服务。在该系统中,users和items通过的低维向量表示。用户u通过向量表示,item i通过表示,它们间的匹配质量(match quaity)通过两个向量间的内积来表示。内积越高表示该用户越愿意消费该item。

检索问题:理想的,给定一个用户u,它由向量表示,所有item vectors 都会被检索。对于每个这样的item vector ,会计算它的匹配质量,items根据它们的匹配质量进行排序。在该列表中具有最高匹配质量的该items接着会被选中来形成最终的推荐列表。然而,在有限搜索时间内,items的catalog通常因为太大而不能对所有内积进行穷举计算。

Xbox的catalog包含了上百万的items。如果使用线性扫描,每个推荐都需要数百万内积计算。user vectors会吸收上下文信息,这些信息只在用户有行为时(engagement)提供。因而,user vector的计算是实时(online)的。结果是,推荐的items列表的检索只能在线(online)执行,不能离线预计算。该任务构成了在online servers引入的单个最大密集计算任务。因此,该过程需要有个快速的替代方案。

我们的贡献:该paper展示了如何来极大地加速推荐检索过程。该最优化item-user match检索与一个近似搜索相关:对与user vector检索高内积(high inner product)的items,但没必要检索最高的。该方法会由多个构建块组成。首先,我们定义了一个新的转换(transformation),它将内积问题转换成一个Euclidean最近邻问题(第3节)。作为一个预处理过程,该转换会被应用到item vectors上。在item检索期间,另一个转换会被应用到user vector上。在转换后空间中的具有最小欧氏距离(Euclidean distance)的item会被检索到。为了加快最近邻搜索,会使用PCA-Tree数据结构与一个新的邻近增强法(neighborhood boosting scheme)(第4节)。

为了演示提出方法的效果,它被应用到一个Xbox推荐数据集上,以及公开的Yahoo Music dataset上。实验表明,在推荐质量推化以及检索时间提升的trade-off曲线(第5节)。另外,time-accuracy trade-offs由两个baseline方法组成,基于LSH和对于在MF近似推荐上的当前state-of-art方法。我们展示了我们的方法具有更高的加速。

概念:我们使用小写字母表示scalars,粗体小写字母表示vector,粗体大写字母表示matrix。例如,x是scalar,x是vector,X是matrix。给定一个向量表示在维度i上的measure,具有:。norm通过来表示;欧氏空间中,。我们通过来表示x和y间的内积dot product (inner product)。最终,我们使用来表示一个标量a与一个向量x进行拼接。

3.简化搜索问题(REDUCIBLE SEARCH PROBLEMS)

该paper的一个关键贡献是,在search problem间进行有效的简化。在该部分,我们对search problem的概念进行公式化,并展示了在已知变种间的有效简化。

我们将search problem定义为:

定义1:

一个search problem 包含了一个关于n个items的实例集合,一个query ,以及一个search function:

函数s用于:对于一个给定query q,检索在I中的某一item的索引。我们的目标是,对items使用 进行预处理,以便每个query都能有效得到结果。预处理函数g可以涉及到一个从某一domain到另一domain的转换,以便转换后的search problem可以在一个不同的domain上执行。以下的定义对search problems间的概念的简化做了公式化:

定义二

一个search problem 被简化成一个search problem ,其中,如果存在函数,那么:

该简化不会对g和h的运行时长做任何限制。注意,g只当成一个预处理step运行,而h会被应用到query时。这提出了一个要求:h必须有的运行时间。我们将该问题公式化为:

定义三

我们会说:,g和h的运行时间分别为

对于在中的一个query vector,我们会在该paper中考虑三个search problem:

  • MIP:在中的n个vectors上的最大内积(maximum inner product)。为
  • NN:在中n个vectors的最近邻(nearest neighbor),为()
  • MCS:在中n个向量的最大cosine相似度。()

它们的正式定义如下:

实例(Instance):一个包含n个item向量的矩阵 ,其中; 因此

查询(Query):一个vector ;

目标(objective):根据以下公式进行检索index:

其中i表示Y的第i列。

下一节展示了这三个问题间是如何进行转换的,可以使用:

来达成上述目标。

3.1 保序转换(Order Preserving Transformations)

当对三个向量进行一个内积比较时,vectors x、间不支持三角不等式(triangle inequality),因为这是在MIP中的情况。许多高效的搜索数据结构依赖于三角不等式,如果MIP可以被转换成使用欧氏距离的NN,这些数据结构立马变得可用。我们的第一个定理论声明是,通过使用比原始问题多一维Euclidian metric,MIP可以被简化到NN。

定理1

证明

假设:

对输入(input)预处理:

在query时:。因为:

我们有:

最终,和x是与index i相互独立的:

定理1是基础。在余下章节,我们会表述它的特性以及相关转换。

如果知道转化后的在一个mainifold上,如上,我们期望通过使用反向化简来恢复Y。然而,在常见case中,该transformation只可能通过再增加一维:

定理2

证明

输入的预处理:

在查询时:

我们有:

最终:

MIP搜索可以被嵌入到一个MCS search中,通过增加1维来实现:

定理3

证明

预处理(preprocessing)和查询转换(query transformation)与定理1相同。输入的预处理为:

,假设:

在query时:

最终:

然而,MCS可以通过归一化向量来简化MIP查询:

定理4

证明

输入预处理:

在query时:

最终:

我们的最终结果表明,一个NN search可以被转换成一个MCS search,通过增加1维来实现:

定理5

证明

与定理1中的简化相同。输入的预处理为:,以及

在query时:

加上定理1:

接下来,我们利用定理1来加速在Xbox中和其它基于MF的推荐系统的检索。

4.我们的方法

我们的解决方案基于两个部分:

1.将问题简化到一个Euclidian search problem 2.使用一个PCA-Tree来求解它。

简化过程(reduction)与定理1的定义非常相似,但会使用一个额外的平移(shift)和旋转(rotation),因此,MIP search problem会被简化到NN search,所有的vectors与它们的主成分(pricipal components)相对齐。

4.1 简化

我们首先根据定理1定义了第一个简化函数。假设:,以及:

…(2)

其中,当应用到Y上时,给定元素。这会将MIP化简到NN。由于NN在输入空间中(input space)对于平移(shift)和旋转(rotations)是不变的,我们可以使用PCA rotation来构成(compose)该转换(transformations),并且可保证一个等价的search problem。

我们对数据进行mean-center并进行rotate:假设是在第一次化简后的均值,并且是一个使用沿着它的列进行复制的矩阵。该中心数据矩阵的SVD为:

其中,数据项(data items)出现在的列中。矩阵W是一个的矩阵。的每一列定义了一个正交单位长度的特征向量(eigenvector),因此,每个定义了一个超平面,每个被投影到它上面。矩阵W是一个旋转矩阵,它会将这些vectors对齐到它的主成分(principal components)上。我们定义了中心旋转(centered rotation)作为我们的第二个转换:

…(3)

其成分(composition)为:

…(4)

仍定义了一个从MIP到NN的简化(reduction)。使用,为我们给出了一个关于输入向量的转换后集合,可以在其上执行一个Euclidian search。另外,在该转换后,该点会被旋转,因而它们的成分(compoments)会减小方差的阶数(order of variance)。接着,我们会使用一个PCA-Tree数据结构来索引在中的转换后的item vectors。我们将上述逻辑表述在算法1中。

算法1

4.2

参考

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的sub-matrix,通过行中的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的抽样方法通常需要执行多个样本试验来达到贪婪算法的可比的经验式性能,它会进一步增加了计算复杂度。

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。

附录

博主注

为什么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):,其中B的每一列(column)表示真实集(ground set)中N个items之一。接着,将每一列写成是一个质量项(quality terms: ,标量) 和一个归一化多样性特征(normalized diversity features: )(当D=N时足够对任意DPP进行分解,单独保留D是因为实际上我们希望使用高维的特征向量)的乘积。依次会将L分解成质量项和归一化多样性特征:

我们可以认为是一个item i内在“好坏(goodness)”的度量,是item i和item j间相似度的一个带符号的measure。我们使用以下的公式来表示相似度:

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

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

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

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

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


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

参考

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

背景

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

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

1.png

图1

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

4. DIN

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

4.1 特征表示

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

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

4.2 Base Model (Embedding & MLP)

2a.png

图2a

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

Embedding layer。由于输入是高维二值向量,embedding layer被用于将他们转换成低维dense表示。对于第i个feature group,假设 表示第i个embedding字典,其中是一个具有维度为D的embedding vector。Embedding操作会遵循查表机制,如图2所示。

  • 如果是one-hot vector,其中第j个元素的embedded表示是一个单一embedding vector
  • 如果是multi-hot vector,其中对于的embedded表示是一个embedding vectors列表:

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

…(1)

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

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

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

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

…(2)

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

4.3 DIN结构

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

t1.png

表1

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

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

2b.png

图2b

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

…(3)

其中:

  • 是用户u的行为的embedding vectors列表,它的长度为H
  • 是广告A的embedding vector。
  • 会随着不同的广告而变化。
  • 是一个feed-forward网络,它的输出作为activation weight,如图2所示。

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

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

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

5.训练技术

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

5.1 Mini-batch Aware正则化

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

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

…(4)

其中:

  • 是第j维的embedding vector
  • 表示实例x是否具有特征id j
  • 表示特征id j在所有样本中的出现次数

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

…(5)

其中:

  • B表示mini-batch的数目
  • 表示第m个mini-batch

假设表示是否存在至少一个实例在mini-batch 上具有特征id j。那么等式(5)可以近似为:

…(6)

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

…(7)

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

5.2 数据自适应激活函数(Data Adaptive Activation Function)

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

…(8)

其中,s是activation函数输入的某一维,是一个指示函数(indicator function),它控制着在两个通道间的切换。是一个可学习参数。这里我们将看成是控制函数。

3.png

图3

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

…(9)

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

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

6. 实验

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

6.1 数据集和实验设定

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

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

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

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

t2.png

表2

6.2 算法比较

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

6.3 指标

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

…(10)

其中n是用户数,是impression数,AUC对应于第i个用户。

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

…(11)

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

6.7

6.8 DIN可视化

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

图5

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

图6

7.结论

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

参考