阿里在KDD 2018上开放了它们的方法:《Learning Tree-based Deep Model for Recommender Systems》, 我们来看下:

注:tdm的paper最好结合代码去理解。

介绍

在推荐系统设计中,为每个用户从整个语料(corpus)集中预测最好的候选集合,存在许多挑战。在海量corpus的系统中,一些推荐算法会失败。与corpus size成线性预测复杂度关系是不可接受的。部署这样的大规模推荐系统,预测每个用户所需要的计算量是受限的。除了精准度外,在用户体验上也应考虑推荐items的新颖度(novelty)。推荐结果中如果包含许多与用户的历史行为的同质items是不可接受的。

在处理海量corpus时,为了减少计算量,memory-based的CF方法在工业界常被广泛使用。作为CF家族的代表方法,item-based CF可以从非常大的corpus进行推荐,只需要很少的计算量,具体决取于预计算的item pairs间的相似度,以及使用用户历史行为作为触发器(triggers)来召回多个相似items。然而,这限制了候选集的范围,例如,只有与triggers相似的items可以被推荐。这阻止了推荐系统跳出它们的历史行为来探索潜在的其它用户兴趣,限制了召回结果的accuracy。实际上,推荐的新颖性(novelty)也是很重要的。另一个减小计算量的方法是,进行粗粒度推荐(coarsegrained recommendation)。例如,系统为用户推荐少量的item类目,并根据它选择所有相应的items,接着进行一个ranking stage。然而,对于大语料,计算问题仍然没解决。如果类目数很大,类目推荐本身也会遇到计算瓶颈。如果不这样做,一些类目将不可避免地包含过多items,使得后续的ranking计算行不通。另外,使用的类目通常不是为推荐问题专门设计的,它也会对推荐的accuracy有害。

在推荐系统的相关文献中,model-based的方法是一个很活跃的话题。像矩阵分解(MF)这样的模型,尝试将pairwise user-item偏好分解成user factors和item factors,接着为每个用户推荐它最喜欢的items。因子分解机(FM)进一步提出了一个统一模型,对于任意类型的输入数据,可以模仿不同的因子分解模型。在一些真实场景中,没有显式偏好,只有隐式用户反馈(例如:像点击 or 购买 这样的用户行为),Bayesian personalized ranking【29】给出了一个求解思路,它会将三元组中的偏好按局部顺序进行公式化,并将它应用到MF模型中。工业界,YouTube使用DNN来学习user embedding和item embeddings,其中,两种类型的embeddings会分别由其相对应的特征进行生成。在上述所有类型的方法中,user-item pair的偏好可以被公式化成,user vector表示与item vector表示间的内积(inner product)。预测阶段等同于检索用户向量在内积空间中的最近邻。对于向量搜索问题,像hashing或quantization[18]用于近似kNN搜索来确保检索的高效性。

然而,在user vector representations和item vector representations间的内积交互形式,严重限制了模型的能力。存在许多类型的其它更具表现力的交互形式,例如,用户历史行为和候选items间的cross-product特征在CTR预估上广泛被使用。最近的工作【13】提出了一种neural CF方法,它使用一个神经网络来替代内积,被用于建模user和item向量表示间的交互。该工作的试验结果表明,一个多层前馈神经网络,比固定内积方法的效果要好。DIN[34]指出,用户兴趣是分散的,一种基于attention机制的网络结构可以根据不同候选items生成不同的user vectors。除了上述工作外,其它像product NN[27]的方法也表明高级NN的效果。然而,这些类型的模型与user vector和item vector间的内积方法(利用高效的kNN搜索)不相一致,在大规模推荐系统中,它们不能被用于召回候选集。为了克服计算屏障,在大规模推荐中使用高级NN是个问题

为了解决上述挑战,我们提出了一个新的TDM(tree-based deep recommendation model). 树和基于树的方法在多分类问题中被广泛研究,其中,tree通常被用于划分样本(sample)/标签(label)空间,来减小计算代价。然而,研究者们涉足于推荐系统环境中使用树结构做为索引进行检索。实际上,层次化结构(hierarchical structure)的信息存在于许多领域。例如,在电商中,iPhone是细粒度item,而smartphone是粗粒度概念,iPhone属于smartphone。TDM方法会使用信息的层级,将推荐问题转化成一系列的层次化分类问题(hierarchical classification problems)。从简到难解决该问题,TDM可以同时提升accuracy和efficiency。该paper的主要贡献如下:

  • TDM是第一个这样的方法,使得在大规模语料中生成推荐的任意高级模型成为可能。受益于层次化树搜索,TDM的计算量只与corpus size成log关系。
  • TDM可以从大型数料中发现更精准的显著并有效的推荐结果,由于整个语料是探索式的,更有效的深度模型也可以帮助发现潜在兴趣。
  • 除了更高级的模型外,TDM也通过层次化搜索来提升推荐accuracy,它可以将一个大问题划分成更小的问题分而治之。
  • 作为索引的一种,为了更高效地检索,树结构可以朝着items和concepts的最优层次结构被学到,它可以帮助模型训练。我们使用一个tree learning方法,它可以对神经网络和树结构进行joint training。
  • 我们在两个大规模数据集上做了大量实验,结果展示TDM的效果要比现有方法好很多。

值得一提的是,tree-based方法也在语言模型中使用(hirearchical softmax),但它与TDM在思想和公式上都不同。在对下一个词的预测问题上,常用的softmax必须计算归一化项(normalization term)来获取任意单个词的概率,它非常耗时。Hierarchical softmax使用tree结构,下一个词的概率就被转换成沿着该tree path的节点概率乘积。这样的公式将下一个词概率的计算复杂度减小到关于语料size的log级别。然而,在推荐问题上,为这些最喜爱items搜索整个语料的目标,是一个检索问题。在hierarchical softmax tree中,父节点的最优化不能保证:最优的低级别节点在它们的子节点上(descendants),并且所有items仍需要被转换成发现最优解。为了解决该检索问题,我们提出了一个类似最大堆的树公式(max-heap like tree),并引入了DNN来建模该树,它为大规模推荐提供了一个有效的方法。以下部分展示了公式的不同之处,它在性能上的优越性。另外,hierarchical softmax采用了单层hidden layer网络来解决一个特定的NLP问题,而我们提出的TDM则实际上可使用任意网络结构。

提出的tree-based模型是一个通用解法,适用于所有类型的在线内容提供商。

2.系统架构

图1 Taobao展示广告(display advertising)推荐系统的系统架构

在本节,图1介绍了Taobao 展示广告推荐系统。在接受到一个用户的PV请求时,系统使用用户特征、上下文特征、以及item特征作为输入,会在matching server中从整个语料中(上百万)来生成一个相对较小的候选集合(通常百级别)。tree-based推荐模型在该stage发挥作用,并将候选集的size缩减了好多阶

有了数百个候选items,实时预测server会使用更昂贵但也更耗时的模型[11,34]来预测像CTR或转化率之类的指标。在通过策略排完序后,一些items会最终曝光给用户。

如上所述,提出的推荐模型的目标是,构建一个含数百个items的候选集。该stage是必须的,也很难。用户在生成的候选上是否感兴趣,给出了曝光质量的一个上界。然而,从整个语料中有效抽取候选是个难题。

3.tree-based Deep模型

在本部分,我们首先介绍在我们的tree-based模型中所使用的树结构。然后,介绍hierarchical softmax来展示为什么该公式不适合推荐。最后,我们给出了一个新的类max-heap tree公式,并展示了如何训练该tree-based模型。接着,引入DNN结构。最后,我们展示了如何构建和学习在tree-based模型中构建和学习该tree。

图2 tree-based deep模型架构。用户行为根据timestamp被划分成不同的时间窗口。在每个时间窗口中,item embeddings被平均加权,权重来自activation units。每个时间窗口的output沿着候选节点的embedding,被拼接成神经网络的输入。在经过三个带PReLU activation和batch normalization的fully-connected layers之后,使用一个二分类softmax来输入probability:用户是否对候选节点感兴趣。每个item和它对应的叶子节点共享相同的embedding。所有embeddings都是随机初始化的。

3.1 推荐所用树

一棵推荐树(recommendation tree)由一个包含N个节点的集合构成,其中,表示个孤立的非叶子节点或叶子节点。在N中的每个节点,除了根节点外,具有一个父节点、以及特定数目的子节点。特别的,在语料C中的每个item ,仅仅只对应于树中的一个叶子节点,这些非叶子节点是粗粒度概率。不失一般性,我们假设节点是根节点。一个关于树的示例如图2右下角所示,在其中,每个圆表示一个节点,节点的数字是在树中的索引。该树总共具有8个叶子节点,每个都对应于语料中的一个item。值得一提的是,给定的示例是一个完全二叉树,我们不会在我们的模型中强制完全二叉。

图2右下角

3.2 相关工作

有了树结构,我们首先引入hierachical softmax来帮助区分TDM。在hierachical softmax中,树中的每个叶子节点n,从根节点出发到该节点具有唯一编码。例如,如果我们假定:左分枝为1,右分枝为0, 那么图2中树的编码为110, 的编码为000。在hierachical softmax的公式中,下个词的概率通过上下文给定:

…(1)

其中:

  • 指的是节点n在第j层上的编码
  • w:指的是叶子节点n的编码
  • :是在节点n在第j层的父节点

通过上述的概率计算方式,hierarchical softmax可以避免softmax中的归一化项(语料中每个词都要遍历一次),从而解决概率计算问题。然而,为了发现最可能的叶子,该模型仍会遍历整个语料。从上到下沿着树路径(tree path)遍历每个层中最可能的节点,不能保证成功检索到最优的叶子。因此,hierarchical softmax的公式不适合大规模检索问题。另外,根据公式1, 树中的每个叶子节点以二分类的方式训练,来在两个子节点间做区分。但是如果两个节点是树中的邻居,它们很可能很相似。在推荐场景中,很可能该用户对两个子节点都感兴趣。hierarchical softmax主要会在最优解和次优解上建模,从全局上看会丢掉识别能力。如果使用贪婪定向搜索(greedy beam search)来检索这些最可能的叶子节点,一旦在树的上层做出坏的决策,模型在发现更好结果上会失败。YouTube的工作[7]也报告了他们已经尝试用hierachical softmax来学习user embeddings和item embeddings,而它比sampled-softmax[16]的方式效果要差

hierachical softmax的公式不适合于大规模推荐,我们提出了一种新的树模型。

3.3 Tree-based模型公式

为了解决top-k 最喜欢items检索的效率问题,我们提出了一个最大堆树(max-heap like tree)的概率公式。最大堆树是一个树结构。其中在第j层中的非叶子节点n,对于每个用户u来说,满足以下公式

…(2)

其中:

  • :是第j层上,用户u对节点n感兴趣的真实概率(ground truth probability)。
  • :是第j层指定layer的归一化项,用来确保在level上的概率和等于1。

等式(2)表明,一个父节点的真实偏好等于它的子节点的最大偏好,除以归一化项。注意,我们对该概率做细微修改,让u表示一个特定的用户状态(user state)。换句话说,一旦该用户有新行为,会从一个特定用户状态u转移到另一个状态u’。

我们的目标是,寻找具有最大偏好概率(largest preference probabilitiy)的k个叶子节点。假设,我们具有在树中每个节点n的真实概率,我们可以使用layer-wise的方式来检索k个节点的最大偏好概率,只有每一层的top k的子节点需要被探索。在这种方式下,top k个叶子节点可以被最终检索到。实际上,我们不需要知道在上述过程中每棵树节点的实际真实概率。我们需要知道的是每一层的概率顺序,来帮助发现在该层级上的top k个节点。基于这个观察,我们使用用户的隐式反馈数据和神经网络来训练每个层级(level)的识别器(discriminater),它可以告诉偏好概率的顺序。

假设用户u具有一个与叶子节点的交互(interaction),即,。这意味着:

其中:

  • 是一个u的正样本节点
  • m是叶子层级
  • 是同层级任意其它叶子节点

在任意层级j上,根据等式(2)的公式,我们假设:

其中:

  • 表示在级别j上的的父节点
  • : 在层级j上,除了外的任意节点

在上述分析的基础中,我们可以使用negative sampling来训练每个层级的顺序判别器(order discriminator)。细节上,与u有交互的叶子节点,它的父节点为u构成了在每个层级中的正样本集合。在每个层级上,随机选择若干负样本(除去正样本),构建了负样本集合。在图2中,绿色和红色节点给出了抽样示例。假设,给定一个用户和它的状态,目标节点是。接着,的父节点是正样本,这些在每个层级上随机抽取的红色节点,是负样本。这些样本接着被feed给二分类概率模型来获取层级(levels)上的顺序判别器(order discriminators)。我们使用一个全局DNN二分类模型,为所有层级使用不同输入来训练顺序判别器。可以使用高级的神经网络来提升模型能力。

假设是关于u的正负样本集合。似然函数为:

…(3)

其中:

  • 是给定u的节点n的预测label。
  • 是二分类概率模型的输出(它采用用户状态u以及抽样节点n作为输入)。

相应的loss函数为:

…(4)

其中:是给定u的节点n的ground truth label。3.4节将讲述如何根据loss函数来训练模型。

注意,提出的抽样方法与hierarchical softmax相当不同。对比在hierarchical softmax中使用的方法(它会让模型混淆最优和次优结果),我们的方法会为每个正节点的同层级随机选择负样本。这种方法让每一层的判别器是一个内部层级全局判别器(intra-level global)。每个层级的全局判别器(global discriminator)可以更独立的做出精准决策,不需要依赖于上层决策的好坏。全局判别能力对于hierarchical推荐方法非常重要。它可以确保:即使模型做出坏的决策,让低质量节点会漏进到上层中的候选集,通过该模型在下层也能选中那些相对更好的节点,而非非常差的节点

算法1

给定一棵推荐树、以及一个最优模型,详细的hierarchical预测算法在算法1中描述。检索过程是layer-wise和top-down的。假设,期望的候选item数是k。对于语料C,它具有size=,在最多个节点上遍历,可以获取在一个完全二叉树上最终的推荐集合。节点数需要在一个关于log(corpus size)级别上遍历,这样可以做出高级的二分概率模型。

我们提出的TDM方法不仅减少了预测时的计算量,也潜在地提升了推荐质量(对比起在所有叶子节点上的brute-force search)。由于corpus size可能很大,如果没有这棵树,训练一个模型来直接发现最优items是一个很难的问题。使用树的层次化(tree hierarchy),大规模推荐问题可以被划分成许多更小的问题。在树的高层中只存在很少节点,判别问题更容易些。由高层上做出的决策可以重新定义候选集,它可以帮助更低层级做出更好的决策。第5.4节中的实验结果,将展示提出的hierarchical retrieval方法的效果要好于brute-force search。

3.4 Deep模型

下面,我们引入deep模型。整个模型如图2所示。受ctr工作的启发[34],我们为树中的每个节点学习低维embeddings,并使用attention模块来为相关行为进行软搜索(softly searching)以求更用的user representation。为了利用包含timestamp信息的用户行为,我们设计了block-wise input layer来区别在不同时间窗口的行为。历史行为可以被划分成沿timeline的不同时间窗,在每个时间窗口中的item embeddings是平均加权的。Attention模块和下面介绍的网络可以极大增强模型能力,同时可以在不能够以内积形式表示的候选集上做出用户偏好。

树节点的embeddings和树结构本身是模型的一部分。为了最小化公式(4)的Loss,抽样节点和相应的特征可以被用于训练该网络。注意,我们只在图2中出于简洁性,展示了用户行为特征的使用,而其它像user profile的features或contextual feature,可以被使用,并无大碍。

3.5 树的构建和学习

推荐树是tree-based deep推荐模型的一个基础部件。不同于multiclass和multi-label分类任务,其中tree被用于划分样本或labels,我们的推荐树会对items进行索引以方便检索。在hierarchical softmax中,词的层次结构可以根据WordNet的专家知识构建。在推荐场景,并不是每个语料可以提供特有的专家知识。一个直觉上的选择是:使用hierarchical聚类方法,基于数据集中item共现或相似度来构建树。但聚类树可能相当不均衡,不利于训练和检索。给定pairwise item similarity,paper[2]的算法给出了一种方法来通过谱聚类将items递归分割成子集。然而,对于大规模语料来说谱聚类的扩展性不够(复杂度随corpus size成三次方增长)。在本节中,我们主要关注合理和可行的树构建和学习方法。

树的初始化。由于我们假设该树表示了用户兴趣的层次结构化(hierarchical)信息,很自然地以在相近位置组织相似items的方式来构建树。假设,在许多领域中类目信息是广泛提供的,我们直觉上提出一个方法来利用item的类目信息来构建初始的树。不失一般性,我们在本节中使用二叉树。

  • 首先,我们会对所有类目随机排序,以一个intra-category的随机顺序将属于相同类目的items放置在一起。如果一个item属于多个类目,出于唯一性,item被随机分配给其中之一。这种方式下,我们给出了一个ranked items的列表。
  • 第二,这些ranked items被递归均分为两个相同的部分,直到当前集合有且仅包含一个item,它可以自顶向底构建一个近似完全二叉树。上述类型的category-based初始化,可以比完全随机树获取更好的hierarchy。

树的学习。作为模型的一部分,每棵叶子节点的embedding可以在模型训练之后被学习得到。接着,我们使用学到的叶子节点的embedding向量来聚类一棵新的树。考虑到corpus size,我们使用k-means聚类算法。在每个step,items会根据它们的embedding vectors被聚类成两个子集。注意,两个子集会被调整成相等以得到一个更平衡的树。当只剩下一个item时,递归过程停止,结果产生一棵二叉树。在我们的实验中,使用单台机器,当语料size为400w时,它会花费一个小时来构建这样的一个聚类树。第5节的实验结果表明所给树学习算法有效率。

4.online serving

图3展示了提出方法的online serving系统。Input feature assembling和item retrieval被划分成两个异步的stages。每个用户行为(包含点击、购买以及加入购物车),会触发realtime feature server组装新的input features。一旦接收到PV请求时,user targeting server会使用预组装的features来从该树中检索候选。如算法1所述,检索是layer-wise的,训练的神经网络被用于计算:对于给定input features,一个节点是否被喜欢的概率

图3

5.实验研究

本部分会研究tree-based模型的效果。实验结果在MovieLens-20M和Taobao advertising dataset(称为UserBehavior数据集)。

  • MovieLens-20M: 包含了user-movie评分数据,带有timestamps。我们会处理隐式反馈问题,评分被二值化:4分以上为1. 另外,只有观看了至少10部电影的用户才会被保留。为了创建训练集、测试集、验证集,我们随机抽样了1000个用户做测试集,另1000用户做验证集,其余用户用于训练集。对于测试集和验证集,沿timeline的前一半user-movie观看记录被看成是已知行为,用于预测后一半
  • UserBehavior: 该数据集是taobao用户行为数据集的子集。我们随机选取了100w具有点击、购买、加入购物车、喜欢收藏的行为,在2017年11.25-12.03间。数据的组织与MovieLens非常相似,例如,一个user-item行为,包含了user ID, item ID, item category ID, 行为类型和timestamp。和MovieLens-20类似,只有至少有10个行为的用户会保留。10000用户会被机选中做为测试集,另一随机选中的10000用户是验证集。Item categories从taobao当前的商品类目的最底层类目得到。表1是两个数据集的主要统计:

表1

5.2 Metrics和比较

为了评估不同方法效果,我们使用Precision@M, Recall@M和F-Measure@M。

  • FM:由xLean项目提供的FM
  • BPR-MF: 由[10]提供的BPR-MF
  • Item-CF: Item-based CF,由Alibaba自己实现
  • Youtube product-DNN: Youtube的方法。训练时使用Sampled-softmax,在Alibaba深度学习平台上实现。预测时在内积空间中采用Exact kNN search。
  • TDM attention-DNN(tree-based模型,使用attention网络),如图2所示。树的初始化由3.5节所示,在实验期间保持不变。实现在github上

对于FM, BPR-MF和item-CF,我们会基于验证集调参,例如:在FM和BPR-MF的因子数和迭代数,在item-CF中的邻居数。FM和BPR-MF需要用户在测试集和验证集上也具有在训练集中的反馈。因些,我们会根据timeline添加在测试集和验证集中前一半的user-item交互,到训练集中。对于Youtube product-DNN和TDM attention-DNN,节点的embeddings的维度设置为25, 因为在我们的实验中一个更高维度并不会带来很大的效果提升。hidden unit数目分别设置为128, 64, 64. 根据timestamp,用户行为被划分成10个time windows。在Youtube product-DNN和TDM attention-DNN中,对于每个隐式反馈,我们为MovieLens-20M随机选择100个负样本, 为UserBehavior随机选择600个负样本。注意,TDM的负样本数据是所有层的求和。我们会为接近叶子的层级抽样更多的负样本。

5.3 结果比较

结果如表2所示:

表2

为了验证新颖性(novelty),一种常用的方法是:过滤掉在推荐集中的交互项【8,20】,例如,只有这些新的items可以被最后推荐。因而,在一个完全新的结果集上比较accuracy更重要。在该实验中,结果集的size可以被补足到M,如果在过滤后size小于M。在过滤完交互items后,表2的底部展示了TDM的attention-DNN效果要好于所有baseline一大截。

为了进一步评估不同方法的能力,我们通过将这些交互类目从结果中排除做实验。每个方法可以补足以满足size需求。确实,category-level novelty在Taobao推荐系统中是最重要的新颖性(novelty)指标。我们希望减小与用户交互项的推荐数目。由于MovieLens-20M只有20个类目,该实验只包含了UserBehavior数据集,结果如表3所示。以recall指标为例,我们观察到item-CF的recall只有1.06%,由于它的推荐结果可以有一半跳出用户的历史行为。Youtube product-DNN对比item-CF会获取更好的结果,由于它从整个语料探索用户的潜在兴趣。而TDM attention-DNN在recall上的效果比Youtube的inner product方式要好34.3%。这种巨大的提升对于推荐系统来说非常有意义,它证明了更高级的模型对于推荐问题来说有巨大的不同。

表3

5.4 经验分析

TDM的变种。为了自身比较,也评估了一些变种:

  • TDM product-DNN: 为了找出高级神经网络是否可以受益于TDM,我们测试了TDM product-DNN。TDM product-DNN使用与Youtube product-DNN相似的inner product方式。特别的,在图2中的attention模块会被移除,node embedding term也被从网络输入中被移除。node embedding和第三个fc layers的output(without PReLU和BN)的inner product会使用一个sigmoid activation来构成新的二分类器.
  • TDM DNN: 为了进一步验证由TDM attention-DNN的attention module带来的提升,我们会测试TDM DNN变种,它只会移除activation unit,例如:在图2中所有items的weights。
  • TDM attention-DNN-HS: 正如第3节提到的,hirearchical softmax方法并不适合推荐。我们会测试TDM attention-DNN-HS变种,例如,使用positive nodes的邻居作为negative samples,来替代随机选择的样本。相应的,在算法1的检索中,ranking indicator会发生变化:从单个node的变为 。Attention-DNN被当成网络结构进行使用.

实验结果如表2中虚线以下所示。TDM attention-DNN到TDM DNN的比较,在UserBehavior数据集上有10% recall提升,attention模块会有明显的提升。TDM product-DNN效果比TDM DNN、TDM attention-DNN要差,因为inner product的方法比神经网络的交互形式要差些。这些结果表明:在TDM中引入的高级模型可以极大提升推荐的效果。注意,对比起TDM attention-DNN,TDM attention-DNN-HS会获取更差的结果。因为hierarchical softmax的公式不能很好适应推荐问题。

树的角色。Tree是TDM的关键组件。它不仅扮演着检索时的索引角色,也会以从粗到细的层级结构形式来建模语料。第3.3节中提到的,直接做出细粒度推荐要比以层级结构方式更难。我们通过实验证明了这个观点。图4展示了layer-wise Recall@200的hierarchical tree search(算法1)和brute-force search。该实验在UserBehavior数据集上使用TDM product-DNN模型,因为它是唯一可以采用brute-force search的变种。在高层级上(8-9),burte-force search的效果只比tree search要稍微好一点点,因为节点数很小。一旦在一个层级上的节点数增长了,对比起burte-force search,tree search会获取更好的recall结果,因为tree search可以排除那些在高层级上的低质量结果,它可以减少在低层级上的问题的难度。该结果表明,在树结果中包含的hierarchy信息,可以帮助提升推荐的准确性。

图4

1.png

表4

tree learning。在3.5节中,我们提出了树的初始化和学习算法。表4给出了在initial tree和learnt tree间的比较结果。从结果看,我们可以发现,使用learnt tree结构的训练模型的效果要远好于只使用intial tree的训练模型。例如,learnt tree的recall指标从4.15%到4.82%,对比起在过滤交互类目的实验中的initial tree,它使用Youtube product-DNN: 3.09%, item-CF: 1.06%。为了进一步比较这两个tree,我们展示了TDM attention-DNN的test loss和recall曲线,训练迭代如图5所示。从图5(a)中,我们可以看到learnt tree结构的test loss变小。图5(a)和5(b)表明,模型会收敛到较好的结果。上述结果表明,tree-learning算法可以提升items的hierarchy,从而进一步提升训练和预测。

图5

5.5 Online效果

我们在taobao效果广告平台的真实流量上评估了提出的TDM的方法。实验在taobao app主页上的猜你喜欢(Guess What You Like)中进行实验。用于评估效果的两个指标是:CTR和RPM(每1000的回报率)。详细如下:

…(8)

在我们的广告系统中,广告主会对一些给定的ad clusters竞价。有将近1400w的clusters,每个ad cluster包含了上百或上千条相似的ads。该验验以ad cluster的粒度开展,以保持与现有系统的一致。比较方法有:LR作为baseline。由于系统中有许多stages,部署TDM online方法是一个巨大的项目,涉及到整个系统。我们完成了第一个TDM DNN版本,并评估了online流量。每个分桶具有5%的在线流量。值得一提的是,有许多在线同时运行推荐的方法。他们从不同的视角,产生的结果进行合并进入到下一stages。TDM只会替换它们中最有效的,保持其它模块不变。带有TDM的测试分桶的平均metric提升率,如表5所示。

如表5所示,TDM方法的CTR提升了2.1%。这项提升表明提出的方法可以为用户召回更多精准的结果。另一方法,RPM的metric增加了6.4%,这意味着TDM的方法也可以为taobao广告平台带来更多回报。

预测效果。TDM使得,在大规模推荐中与user和items交叉高级神经网络变得可行,它打开了一个全新视角。值得一提的是,尽管高级神经网络在inferring时需要更多的计算,但整个预测过程的复杂度不会大于,其中,k是所需结果的size,是corpus size,t是网络中单个feed-forward pass的复杂度。该复杂度的上界在当前CPU/GPU硬件环境下是可接受的,在单个检索中,用户侧特征可以跨不同的节点共享,一些计算可以根据模型设计被共享。在Taobao展示广告系统中,它实际上会采用TDM DNN模型,平均一次推荐需要6ms。这样的运行时间比接下来的ctr预测模型要短,不会是系统瓶颈。

6.结论

参考

阿里盒马团队在KDD 2018上开放了它们的方法:《Learning and Transferring IDs Representation in E-commerce》, 这个方法也很简单,我们来看下paper的主要内容部分:

3.4 联合嵌入Attribute IDs

通过探索在item ID和它的attribute IDs间的结构连接,我们提出了一个hirerarchical embedding模型来联合学习item ID和attribute IDs的低维表示。模型结构如图4所示,其中item ID是核心的交互单元,它与attibute IDs间通过虚线连接。

1.png

图4

首先,item IDs的共现也隐含了对应attribute IDs间的共现,它通过图4的实心键头表示。假设存在K个类型的IDs,并使 ,其中等于的item ID,是product ID,是store ID等。我们学习目标替换成:

…(7)

其中,以及是分别对应于类型(type)为k的context和target representations。对于类型k,是它的embedding vectors的维度,是它的字典size。注意,不同类型的IDs可以被嵌入到不同的维度上。标量的权重。假设每个item的贡献与相等,包含了个不同的items,成反比是合理的。更正式的,我们有:

…(8)

…(9)

…(10)

例如,表示每个刚好包含了一个item;而表示:product ID包含了10个不同的items

第二,item ID和attribute IDs间的结构连接意味着限制(constraints),例如:两个item IDs的向量应更接近,不仅是对于它们的共现,而且对于它们共享相同的product ID, store ID, brand ID或cate-level1 ID等。相反的,attribute IDs等价于包含在对应item IDs内的信息。以store ID为例,对于一个指定store ID的embedding vector,它可以看成是应该商店所售卖的所有item IDs的合适的总结(summary)。 相应的,我们定义了:

…(11)

其中,是一个转移矩阵,它会将embedding vector 转称到相同维度的embedding vector 上。接着,我们最大化下面的平均log概率:

…(12)

其中,是介于IDs间的约束强度,是在转移矩阵上的L2正则的强度。

我们的方法可以将item ID和它的attrbute IDs嵌入到一个语义空间中,它很有用。item ID的属性和它的attrbute IDs对于一个相对长的时间来说是稳定的,该jointly embedding model和学到的表示会每周更新一次。

3.5 Embedding User IDs

用户偏好受item IDs交互序列的影响,通过对交互的item IDs的embedding vectors做聚合来表示user IDs是合理的。有许多方法来聚合item embedding vectors,比如:Average, RNN等[26],本paper中使用的是平均方式(Average)。

由于Hema中的用户偏好变化很快,user IDs的embedding vectors也应进行频繁更新(比如:按天更新),来快速响应最新的偏好。不同于RNN模型,它需要训练过程并且计算开销很大,Average可以在很短的时间内学习和更新表示。

对于用户,假设表示交互序列,其中最近的T个item IDs以逆时序的方式排列。我们为用户u构建了embedding vector:

其中,的embedding vector。

3.6 模型学习

对该jointly embedding model进行优化等同于最大化(12)的log似然,它与log-uniform negative-sampling相近。为了解决该最优化问题,我们首先使用“Xavier” initialzation来初始化所有可训练参数。接着使用SGD算法和shuffled mini-batches到J上。参数的更新通过BP+Adam rule来完成。为了加速并行操作,在NVIDIA-GPU+tensorflow上训练。

模型的超参数设置如下:context window C=4; negative samples数 S=2; embedding dimensions为 ;constraints强度;L2 reg强度 ;batch size=128, 训练5个epochs。

#

参考

关于ALE (Arcade Learning Environment)的介绍来自于Marlos C. Machado发表的paper:《Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents》

1.介绍

ALE (电玩学习环境:Arcade Learning Environment): ALE提供了一个关于Atari 2600游戏的数百个游戏环境的接口,这些游戏每个都是不同的、很有趣。ALE提供了对reinforcement learning, model learning, model-based planning, imitation learning, transfer learning, 和 intrinsic motivation的研究挑战。更重要的是,它为这些问题提供了一个严格的testbed来评估和比较方法。我们使用AI技术(reinforcement learning/learning)通过开发和测试domain-independent agents来展示ALE。我们也提供了一个evaluation技术,在超过55个不同游戏上有结果。

#

略…

接口

ALE在Stella(一个开源的Atari 2600模拟器)上构建。它允许用户通过接收joystick动作、发送screen/RAM信息、并模拟平台的方式来与Atari 2600交互。ALE提供了一个游戏处理层(game-handling layer),它通过标记累积得分、以及游戏是否已经结束,可以将每个游戏转化成一个标准的增强学习问题。缺省的,每个observation包含了单个游戏屏幕(game screen: frame):一个关于7bit像素的2D数组,160 pixels宽 x 210 pixels高。action space包含了18个离散(discrete)的actions,它们通过操纵杆控制器(joystick controller)来定义。game-handling layer也指定了需要玩一个特定游戏的关于actions的最小集合。当运行时,该仿真器会每秒生成60帧,最高速度的仿真可以达到每秒6000帧。在每个time-step上的reward通过game basis来定义,通常通过在帧之间的得分(score/points)的不同来指定。一个episode会在reset命令后的第一帧(frame)处开始,当游戏结束时终止。game-handling layer也提供了在预定义帧数后终止episode的能力。user因此可以通过单个公共接口来访问数十个游戏,并可以很简单地增加新游戏。

图1 18个action

ALE也提供了保存(save)和恢复(restore)仿真器的状态(state)的功能。当发出一个save-state命令时,ALE会保存关于当前游戏所有相关数据,包括RAM、寄存器(registers)、地址计数器(address counters)的内容。restore-state命令会resets该游戏到之前saved state时的状态。这允许ALE作为一个生成模型来研究主题:planning、model-based RL。

图2 load/save

3.Benchmark结果

Planning 和 reinforcement learning是可以在ALE framework中研究的两个主要AI问题。在benchmark results中我们的目标是两者:第一,这些结果提供了一个对于传统技术的baseline performance,并确立了一个与更高级方法的比较点。第二,这些结果可以做经验上的validation。

3.1 RL

我们使用SARSA()来提供benchmark结果,这是一种model-free RL的传统技术。注意,在RL setting中,agent不会访问一个关于游戏动态性(game dynamics)的模型。在每个time-step上,agent会选择一个action并接收一个reward和一个observation,该agent的目标是:最大化它的累积回报(acumulated reward)。在这些实验中,我们会讨论:线性函数近似、replacing traces, e-greedy exploration。

3.1.1 特征构建

Basic:Basic方法来自于Naddaf’s BASS (2010),会对Atari 2600 screen上的颜色进行编码。Basic方法首先移除了图片背景色,它通过在每个像素位置的颜色频率存储在一个histogram中。每个游戏背景是离线预计算好的,使用从sample trajectories中收集到的18000个observations。sample trajectories根据一个人工提供(human-provided)的trajectory,取随机数目的steps、并且随机均匀选择actions的方式来生成。该screen接着被划分成16x14 tiles。Basic会为每个128种颜色、每个tiles生成一个binary feature,共28672个features。

BASS:与BASIC相似。首先,BASS的特征集是pairwise组合。第二,BASS使用一个更小的、 8色的encoding来确保pairwise组合数目保持可跟踪。

DISCO:DISCO方法的目标是检测在Atari 2600 screen中的对象。为了这样做,与Basic方法生成的sample trajectories相似,它会首先预处理来自sample trajectories的36000个observations。DISCO会执行背景减少steps。接着抽取的对象标记(label)成classes。在实际训练期间,DISCO会infer所检测对象的class label,并将它们的位置和速度使用tile coding进行编码。

LSH:LSH方法会将原始的Atari 2600 screens使用Locally sensitive hashing映射到关于binary features的一个小集合上。

RAM:RAM方法会使用整个不同的observation space。它直接将Atari 2600的1024位内存进行observes。RAM的每一位可以当成一个binary feature提供。

3.1.2 评估技术

我们首先构建两个集合:一个用于training、一个用于testing。我们使用training games来进行调参,testing games用于评估。我们的training set包含了5个游戏:Asterix, Beam Rider, Freeway, Seaquest 和 Space Invaders。参数搜索涉及到发现SARSA算法最适合的参数值:比如:learning-rate、exploration rate、discount factor、decay rate 。我们也会搜索特征生成参数的空间,例如:Bass agent的abstraction level等。我们的testing set通过从381个游戏中半随机选择。这些游戏中,128个游戏有它的wikipedia介绍页,具有单人模式、没有成人主题、可以在ALE中进行模拟。50个游戏被随机选中来形成test set。

在每个游戏上,每个方法的评估执行如下。一个episode从reset命令后的第一帧开始,当游戏结束条件被检测到、或者在5分钟后(即18000帧)玩后时结束。在episode期间,agent会每5帧进行acts,或者等价于gameplay的每秒12次。RL的实验(trial)包含了5000个training episodes,以及500个evalution episodes。agent的效果通过在evaluation episodes期间的平均得分进行measure。对于每个游戏,我们会在30个实验上报告我们的平均效果。

参考

前几天微软提出了一个xDeepFM算法:

介绍

传统交叉特征工程主要有三个缺点,以下部分来自paper:

  • 1.获取高质量特征代价高昂
  • 2.大规模预测系统(比如:推荐系统),存在大量原始特征(raw features),很难人工抽取所有交叉特征
  • 3.人工交叉特征不能泛化到在训练数据中未见过的交叉上

FM会将每个特征i嵌入到一个隐因子向量 上,pairwise型特征交叉可以被建模成隐向量的内积:。在本paper中,我们使用术语bit来表示在隐向量中的一个元素(比如:)。经典的FM可以被扩展到专门的高阶特征交叉上,但一个主要缺点是:会建模所有的特征交叉,包括有用组合和无用组合。无用组合会引入噪声、以及效果的下降。最近几年,DNNs越来越流行。利用DNNs可以学习复杂和可选择的特征交叉。[46]提出来FNN用于学习高阶特征交叉。它会使用对于field embedding的预训练FM,然后应用于DNN。[31]提出了PNN,它不依赖预训练的FM,而是在embedding layer和DNN layer之间引入了一个product layer。FNN和PNN的主要缺点是,它们主要更多关注高阶特征交叉,而非低阶交叉。Wide&Deep模型和DeepFM模型通过引入混合结构克服了上面的缺点,它包含了一个shallow组件以及一个deep组件,可以学到memorization和generalization。因而可以联合学习低阶和高阶特征交叉。

上面的所有模型都使用DNN来学习高阶特征交叉。然而,DNN可以以一个隐式的方式建模高阶特征交叉。由DNN学到的最终函数可以是任意形式,关于特征交叉的最大阶数(maximum degree)没有理论上的结论。另外,DNNs在bit-wise级别建模征交叉,这与FM框架不同(它会在vector-wise级别建模)。这样,在推荐系统的领域,其中DNN是否是用于表示高阶特征交叉的最有效模型,仍然是一个开放问题。在本paper中,我们提供了一个基于NN的模型,以显式、vector-wise的方式来学习特征交叉。我们的方法基于DCN(Deep&Cross Network)之上,该方法能有效捕获有限阶数(bounded degree)的特征交叉。然而,我们会在第2.3节讨论,DCN将带来一种特殊形式的交叉。我们设计了一种新的压缩交叉网络CIN(compressed interaction network)来替换在DCN中的cross network。CIN可以显式地学到特征交叉,交叉的阶数会随着网络depth增长。根据Wide&Deep模型和DeepFM模型的精神,我们会结合显式高阶交叉模块和隐式交叉模型,以及传统的FM模块,并将该联合模型命名为“eXtreme Deep Factorization Machine (xDeepFM)”。这种新模型无需人工特征工程,可以让数据科学家们从无聊的特征搜索中解放出来。总结一下,主要有三个贡献:

  • 提出了一种新模型xDeepFM,可以联合训练显式和隐式高阶特征交叉,无需人工特征工程
  • 设计了CIN来显式学习高阶特征交叉。我们展示了特征交叉的阶(degree)会在每一层增加,特征会在vector-wise级别进行交叉。
  • 我们在三个数据集中进行了实验,结果展示xDeepFM效果好于其它state-of-art模型

2.PRELIMINARIES

2.1 Embedding Layer

在CV或NLP领域,输入数据通常是图片或文本信号,它们空间相关(spatially correlated)或时序相关(temporally correlated),因而DNN可以被直接应用到dense结构的原始特征上。然而,在推荐系统中,输入特征是sparse、高维、没有明显地空间相关或时序相关。因此,multi-field类别形式被广泛使用。例如,一个输入实例为: [user_id=s02,gender=male,organization=msra,interests=comedy&rock]

通过field-aware one-hot进行编码成高维稀疏特征:

在原始特征输入上使用一个embedding layer,可以将它压缩到一个低维、dense、real-value vector上。如果field是一阶的(univalent),feature embedding被当成field embedding使用。以上述实例为例,特征(male)的embedding被当成field gender的embedding。如果field是多阶的(multivalent),feature embedding的求和被用于field embedding。embedding layer如图1所示。embedding layer的结果是一个wide concatenated vector:

其中,m表示fields的数目,表示一个field的embedding。尽管实例的feature长度可以是多变的,它们的embedding具有相同的长度 m x D, 其中D是field embedding的维数。

图1: field embedding layer。本例中embedding的维度是4

2.2 隐式高阶交叉

FNN, Deep&Cross,以及Wide&Deep的deep part会使用一个在field embedding vector e上的feed-forward神经网络来学习高阶特征交叉。forward process是:

…(1)

…(2)

其中,k是layer depth,是激活函数,是第k层的output。可视化结构与图2展示的非常像,但不包括FM layer或Product layer。该结构会以bit-wise的方式建模交叉。也就是说,相同field embedding vector中的元素也会相互影响。

PNN和DeepFM在上述结构上做了小修改。除了在embedding vector e上应用了DNNs外,它们在网络中添加了一个2-way interaction layer。因而,bit-wise和vector-wise的交叉都能在模型中包含。PNN和DeepFM中主要不同是,PNN会将product layer的输出连接到DNNs中,而DeepFM会直接将FM layer连接给output unit。

图2: DeepFM和PNN的架构。我们复用了符号,其中红色边表示weight-1 connections(没有参数),灰色边表示normal connections(网络参数)

2.3 显式高阶交叉

[40]提出的Cross Network(CrossNet)它的结构如图3所示:

图3:

它可以显式建模高阶特征交叉。不同于经典的fully-connected feed-forward network,它的hidden layers通过以下的cross操作进行计算:

…(3)

其中,是第k层的weights,bias以及output。对于CrossNet能学到一个特殊类型的高阶交叉这一点我们有争论,其中,CrossNet中的每个hidden layer是一个关于的标量乘积。

theorem 2.1: 考虑到一个k层cross network,第i+1层的定义为:。接着,cross network的output 是一个关于的标量乘积。

证明如下:

k=1时,根据矩阵乘法的结合律和分配律,我们具有:

…(4)

其中,标量实际上是关于的线性回归。其中,是关于的一个标量乘。假设标量乘适用于k=i。对于k=i+1, 我们可以有:

…(5)

其中,是一个标量。其中,仍是一个关于的标量乘。通过引入hypothesis,cross network的output 是一个关于的标量乘。

注意,并不意味着是与是线性关系的。系数是与敏感的。CrossNet可以非常有效地学到特征交叉(复杂度与一个DNN模型对比是微不足道的),然而,缺点是:

  • (1) CrossNet的输出受限于一个特定的形式,每个hidden layer是关于的一个标量乘
  • (2) 交叉是以bit-wise的方式进行

3.新模型

3.1 CIN

我们设计了一个新的cross network,命名为CIN(Compressed Interaction Network),具有如下注意事项:

  • (1) 交叉是在vector-wise级别上进行,而非bit-wise级别
  • (2) 高阶特征的交叉显式衡量
  • (3) 网络的复杂度不会随着交叉阶数进行指数增长

由于一个embedding vector被看成是一个关于vector-wise 交叉的unit,后续我们会将field embedding公式化为一个矩阵:,其中,假设表示在第k层的(embedding)feature vectors的数量。对于每一层,通过以下方式计算:

…(6)

其中是第h个feature vector的参数矩阵,表示Hadamard product,例如:。注意,通过在间的交叉产生,其中,特征交叉会被显式衡量,交叉的阶数会随着layer depth增长。CIN的结构与RNN非常相似,其中下一个hidden layer的outputs取决于最近一个(the last)的hidden layer和一个额外的input。我们在所有layers上都持有embedding vectors的结构,这样,即可在vector-wise级别上使用交叉。

有意思的是,等式(6)与CNN具有很强的关联。如图4a所示,我们引入了一个内部张量(intermediate tensor) ,其中,它是hidden layer和原始特征矩阵的外积(outer products:沿着每个embedding维度)。被看成是一个特殊类型的图片,看成是一个filter。我们如图4b所示跨沿着该embedding dimension(D)滑动该filter,获得一个hidden vector ,这在CV中通常被称为一个feature map。在CIN命名中所使用的术语”compressed”表示了第k个hidden layer会将 向量的隐空间压缩到向量中。

图4c提供了CIN的一个总览。假设T表示网络的深度。每个hidden layer 具有一个与output units的连接。我们首先在hidden layer的每个feature map上使用sum pooling:

…(7)

其中,。这样,我们就得到一个pooling vector:,对于第k个hidden layer相应的长度为。hidden layers的所有polling vectors在连接到output units之前会被concatenated:。如果我们直接使用CIN进行分类,output unit是在上的一个sigmoid节点:

…(8)

其中,是回归参数。

3.2 CIN详解

我们对CIN进行分析,研究了模型复杂度以及潜在的效果。

3.2.1 空间复杂度

在第k层的第h个feature map,包含了个参数,它与具有相同的size。因而,在第k层上具有个参数。考虑到对于output unit的当前最近(the last)的regression layer,它具有个参数,CIN的参数总数是 。注意,CIN与embedding dimension D相互独立。相反的,一个普通的T-layers DNN包含了个参数,参数的数目会随着embedding dimension D而增长。

通常,m和不会非常大,因而,的规模是可接受的。当有必要时,我们可以利用一个L阶的分解,使用两个小的矩阵以及来替换

…(9)

其中以及。出于简洁性,我们假设每个hidden layer都具有相同数目(为H)的feature maps。尽管L阶分解,CIN的空间复杂度从下降到。相反的,普通DNN的空间复杂度是,它对于field embedding的维度D是敏感的。

3.2.2 时间复杂度

计算tensor 的开销是O(mHD)。由于我们在第一个hidden layer上具有H个feature maps,计算一个T-layers CIN会花费时间。相反的,一个T-layer plain DNN,会花费时间。因此,CIN的主要缺点是在时间复杂度上。

3.2.3 多项式近似(Polynomial Approximation)

接下来,我们检查了CIN的高阶交叉属性。出于简洁性,我们假设,在hidden layers上的feature maps数目,等于fields m的数目。假设[m]表示小于或等于m的正整数集。在第1层上的第h个feature map,表示为,通过下式计算:

…(10)

因此,在第1层的每个feature map会使用个系数来建模pair-wise特征交叉。相似的,在第2层的第h个feature map为:

…(11)

注意,l和k相关的所有计算在前一个hidden layer已经完成。我们在等式(11)扩展的因子是为了清晰。我们可以观察到,在第二层的每个feature map会使用新参数来建模3-way交叉。

一个经典的k阶多项式具有系数。我们展示了CIN会逼近这类型多项式,根据一个feature maps链,只需要个参数。通过引入hypothesis,我们可以证明,在第k层的第h个feature map为:

…(12)

为了更好地演示,我们参考了[40]的注解。假设表示一个multi-index,其中。我们会从中忽略原始的上标,使用来表示它,因为对于最终展开的表达式,我们只关心来自第0层(等同于field embedding)的feature maps。现在,使用一个上标来表示向量操作,比如。假设表示一个multi-vector 多项式的阶数k:

…(13)

在该类中的每个向量多项式都具有个系数。接着,我们的CIN接似系数

…(14)

其中, 是一个multi-index,是索引()的所有排列。

3.3 与隐式网络的组合

在第2.2节,plain DNNs可以学到隐式高阶特征交叉。由于CIN和plain DNNs可以互补,一个直观的做法是,将这两种结构进行组合使模型更强。产生的模型与Wide&Deep和DeepFM非常像。结构如图5所示,我们将新模型命名为eXtreme Deep Factorization Machine(xDeepFM),一方面,它同时包含了低阶和高阶特征交叉;另一方面,它包含了隐式特征交叉和显式特征交叉。它产生的output unit如下:

…(15)

其中,\sigma为sigmoid函数,a是原始特征。分别是是plain DNN和CIN的outputs。和b是可学习的参数。对于二分类,loss函数为log loss:

…(16)

其中,N是训练实例的总数。Optimization过程是最小化下面的目标函数:

…(17)

其中表示正则项,表示参数集,包含linear part,CIN part,DNN part。

图5: xDeepFM的结构

3.3.1 与FM和DeepFM的关系

假设所有field是一阶的(univalent)。如图5所示,当depth和CIN part的feature maps同时设为1时,xDeepFM就是DeepFM的一个泛化,通过为FM layer学习线性回归权重实现(注意,在DeepFM中,FM layer的units直接与output unit相连,没有任何系数)。当我们进一步移去DNN part,并同时为该feature map使用一个constant sum filter(它简单采用输入求和,无需任何参数学习),接着xDeepFM就变成了传统的FM模型。

4.实验

实验主要回答下述问题:

  • (Q1) CIN在高阶特征交叉学习上是如何进行的?
  • (Q2) 对于推荐系统来说,将显式和隐式高阶特征交叉相组合是否是必要的?
  • (Q3) xDeepFM的网络设置如何影响效果?

4.1 实验设置

4.1.1 数据集

1. Criteo Dataset:ctr预测的benchmarking dataset,对外开放。给定一个用户和他访问的页面,目标是预测它点击一个给定广告的概率。

2. Dianping Dataset:收集了6个月的关于大众点评的用户check-in活动用于餐厅推荐实验。给定一个用户的profile,一个餐厅的相应属性,该用户最近三次访问POIs(point of interest),我们希望预测它访问该餐厅的概率。对于在一个用户的check-in样本中的每个餐厅,我们会通过POI流行度抽样出在3公里内的4个餐厅作为负样本。

3.Bing News Dataset.:Bing News是微软Bing搜索引擎的一部分。我们收集了在新闻阅读服务上连续5天的曝光日志。使用前3天数据用于训练和验证,后两天数据用于测试。

对于Criteo dataset和Dianping dataset,随机将样本划分为8:1:1进行训练、验证、测试。三个数据集的特性如表1所示。

表1:评估数据计的统计。

4.1.2 评估metrics

我们使用两种metrics:AUC和LogLoss。有时更依赖logloss,因为我们需要使用预测概率来估计一个排序系统带来的收益(比如常见的CTR x bid)

4.1.3 Baselines

我们比较了xDeepFM, LR, FM, DNN, PNN, Wide&Deep, DCN, DeepFM.

4.1.4 Reproducibility

使用tensorflow来实现模型。每个模型的超参数通过在validation set上进行grid-searching调参,然后选择最好的settings。

  • learning rate设置为0.001.
  • optimization方法使用Adam。
  • mini-batch size=4096.
  • 对于DNN, DCN, Wide&Deep, DeepFM和xDeepFM,使用L2正则,对应的
  • 对于PNN,使用dropout=0.5
  • 每层neurons数目的缺省setting为:
    • (1) DNN layers为400
    • (2) 对于Criteo dataset,CIN layers为200; 对于DIanping和Bing News datasets,CIN layers=100
  • 由于本文主要关注网络结构,所有field embedding的维度统一设为固定值=10.
  • 本试验在并行化在5块tesla K80 GPUs上跑.
  • 源码为: https://github.com/ Leavingseason/ xDeepFM

效果展示部分:

表3: depth列表示单模型中的最佳深度,分别表示(cross layers, DNN layers)

4.2 Q1: 单一Neural组件间的效果比较

我们想知道CIN单独是如何执行的。注意FM会显式衡量2阶特征交叉,DNN模型可以隐式衡量高阶特征交叉,CrossNet尝试使用较少参数来建模高阶特征交叉,CIN则会显式建模高阶特征交叉。由于它实际依赖于数据集,单一模型(individual model)间的比较优势没有理论保证。例如,如果实际数据集不需要高阶特征交叉,FM可能是最好的单一模型。对于该实验,我们并不期望哪个模型表现最好。

表2展示了单一模型在三个实际数据集上的效果。令人惊讶的是,CIN的表现都要好些。另一方面,结果表明,对于实际数据集,稀疏特征上的高阶交叉是必要的,可以证实:DNN,CrossNet, CIN的效果要远好于FM。另一方面,CIN是最好的单一模型,图中展示了CIN在建模高阶特征交叉上的效果。注意,一个k-layer的CIN可以建模k阶的特征交叉。有趣的是,在Bing News dataset上,它会采用5 layers的CIN来达到最佳结果。

表2: 不同数据集下的模型表现。Depth列表示每个模型最好的网络深度

4.3 Q2: 集成模型的效果

xDeepFM会将CIN和DNN集成一个end-to-end模型。而CIN和DNN能cover在特征交叉学习上两种不同的属性,我们感兴趣的是,是否确实有必要将两者组合在一起进行explicit和implicit的joint learning。这里,我们比较了一些比较强的baselines,如表3所示。另一个有意思的观察是,所有基于neural的模型并不需要非常深的网络结构来达到最佳效果。常见的depth超参数设置为2或3, xDeepFM的最佳深度是3,可以表示最多学习4阶的交叉。

4.4 Q3: 超参数学习

  • 1.hidden layers的数目
  • 2.每层的neurons数目
  • 3.激活函数

参考

google在2017年paper《Attention Is All You Need》提出了transformer,我们可以看下:

1.介绍

在序列建模(sequence modeling)和转换问题(transduction problems,比如:语言建模和机器翻译)上,RNN, LSTM和GRNN已经成为state-of-art的方法。大多数努力源自于recurrent语言模型和encoder-decoder架构的持续推动。

recurrent模型通常会沿着输入和输出序列的符号位置(symbol position)进行因子计算。在计算时对位置(position)进行排列,他们可以生成一个hidden states 的序列,它是关于前一hidden state 和位置t做为输入的一个函数。这种天然的序列特性排除了在训练样本中的并发性(这对于更长序列长度很重要),因为内存约束会限制在样本上进行batching。最近工作表明,因子分解tricks[18]和条件计算[26]可以在计算效率上进行有效提升,同时也会提升模型效果。然而,序列化计算的基本限制仍然存在。

Attention机制已经在许多任务中成为序列建模(sequence modeling)和转化模型(transduction model)的不可欠缺的一个部件,它可以在无需考虑input或output序列上的距离[2,16]的情况下来建模依赖(dependencies)。除了极少的cases外,几乎所有这样的attention机制都会与一个recurrent network一起使用。

在该工作中,我们提出了Transformer,这种模型结构可以避免recurrence,它完全依赖attention机制来抽取在input和output间的全局依赖性。Transformer允许更大的并行度(parallelization),在eight P100 GPUs上训练12小时后,在翻译质量上可以达到一种新的state-of-art效果。

2.背景

减小序列化计算开销的目标,也构成了Extended Neural GPU [20], ByteNet [15] and ConvS2S [8]的基础,它们都使用CNN作为基本构建块,对所有input和output positions并行计算hidden representations。在这些模型中,两个专门的input或output positions的相关信号所需要的ops数目,会随着positions间的距离而增长:这对于ConvS2S是线性的,对于ByteNet是成log关系。这使得很难学习在较远位置(distant positions)间的依赖[11]。在Transformer中,操作(operations)的数目可以减小到常数级别,虽然在有效识别率上会有损失的代价(因为会对attention-weighted positions进行平均),我们会使用第3.2节中的Multi-Head Attention来消除这现象。

self-attention,有时被称为”intra-attention”,是一种与单个序列上不同位置有关的attention机制,它的目的是计算该序列的一种表示(representation)。self-attention已经被成功用于许多任务,包括:阅读理解(reading comprehension)、抽象式摘要(abstractive summarization)、文字蕴含(textual entailment)、独立句子表示任务[4,22,23,19]。

end-to-end memory networks基于一个recurrent attention机制(而非基于sequence-aligned recurrence),已经展示出在单语言问答上和语言建模任务上很好的效果[28]。

据我们所知,Transformer是首个完全依赖于self-attention的转换模型(transduction model),它无需使用sequence-aligned RNNs或convolution,就可以计算input和output的表示(representations)。在以下部分,我们会描述Transformer、motivation self-attention、以及在模型上的优点[14,15],[8]。

3.模型结构

大多数比赛采用的神经序列转换模型(neural sequence transduction models)都有一个encoder-decoder结构[5,2,29]。这里,encoder会将一个关于符号表示的输入序列映射到一个连续表示的序列上。在给定z后,decoder接着生成一个关于符号(symbols)的output序列,一次一个元素。在每个step上,模型是自回归的(auto-regressive),当生成下一输出时,它会消费前面生成的符号作为额外输入。

Transformer会遵循这样的总体架构:它使用stacked self-attention、point-wise FC-layers的encoder-decoder,如图1的左右所示:

1.png

图1 Transformer模型结构

3.1 Encoder Stacks和Decoder Stacks

Encoder:encoder由一个N=6的相同层(identical layers)的stack组成。每一layer具有两个sub-layers。第1个是一个multi-head self-attention机制,第2个是一个简单的position-wise FC 前馈网络。我们在两个sub-layers的每一个上采用一个residual connection[10],后跟着layer nomalization[1]。也就是说:每一sub-layer的output是 ,其中Sublayer(x)是通过sub-layer自身实现的函数。为了促进这些residual connections,模型中的所有sub-layers以及embedding layers会生成维度 的outputs。

Decoder:该decoder也由一个N=6的相同层(identical layers)的stacks组成。除了包含在每个encoder layer中的两个sub-layers之外,decoder会插入第三个sub-layer,从而在encoder stack的output上执行multi-head attention。与encoder相似,我们在每个sub-layers周围采用residual connections,后跟layer normalization。同时我们在decoder stack中修改了self-attention sub-layer,来阻止position与后序位置有联系。这种masking机制,结合上output embeddings由一个位置偏移(offset by one position)的事实,可以确保对于位置i的预测只依赖于在位置小于i上的已知outputs。

3.2 Attention

attention函数可以被描述成:将一个query和一个key-value pairs集合映射到一个output上,其中:query, keys, values和output都是向量(vectors)。output由对values进行加权计算得到,其中为每个value分配的weight通过query和对应的key的一个兼容函数计算得到。

2.png

图2 (左) Scaled Dot-Product Attention (右) Multi-Head Attention,包含了并行运行的多个attention layers

3.2.1 归一化点乘Attention(Scaled Dot-Product Attention)

我们将这种特别的attention称为”Scaled Dot-Product Attention”(图2)。输入包含:querys、维度为的keys、以及维度为的values。我们会计算query和所有keys的点乘(dot products),每个除以,并使用一个softmax函数来获取在values上的weights。

实际上,我们会同时在一个queries集合上计算attention函数,并将它们打包成一个矩阵Q。keys和values也一起被加包成矩阵K和V。我们会计算矩阵的outputs:

…(1)

两种最常用的attention函数是:additive attention[2],dot-product(multiplicative) attention。dot-product attention等同于我们的算法,除了缩放因子。additive attention会使用一个单hidden layer的前馈网络来计算兼容函数。两者在理论复杂度上很相似,dot-product attention更快,空间效率更高,因为它使用高度优化的矩阵乘法代码来实现

如果值比较小,两种机制效果相似; 如果值很大,additive attention效果要好于dot-product attention。对于的大值我们表示怀疑,dot-product在幅度上增长更大,在具有极小梯度值的区域上使用softmax函数。为了消除该影响,我们将dot-product缩放至

3.2.2 Multi-Head Attention

我们不会使用维的keys、values和queries来执行单个attention函数,我们发现:使用学到的不同线性投影将queries、keys和values各自投影到维上是有好处的。在关于queries、keys和values的每一个投影版本上,我们会并行执行attention函数,生成维的output values。这些值被拼接在一起(concatenated),再进行投影,产生最后值,如图2所示。

Multi-head attention允许模型联合处理在不同位置处来自不同表示子空间的信息。使用单个attention head,求平均会禁止这样做。

其中,投影是参数矩阵:

在本工作中,我们使用h=8的并行attention layers或heads。对于每一者,我们会使用 。由于每个head的维度缩减,总的计算开销与具有完整维度的single-head attention相似。

3.2.3 在模型中Attention的应用

Transformer以三种不同的方式使用multi-head attention:

  • “encoder-decoder attention” layers中:queries来自前一decoder layer,memory keys和values来自encoder的output。这允许在decoder中的每个position会注意(attend)在输入序列中的所有位置。这种方式模仿了在seq2seq模型中典型的encoder-decoder attention机制[31,2,8]。
  • encoder中:encoder包含了self-attention layers。在一个self-attention layer中,所有的keys, values和queries来自相同的地方:在encoder中的前一layer的output。在encoder中每个position可以注意(attend)在encoder的前一layer中的所有位置。
  • decoder中:相似的,在decoder中self-attention layers允许在decoder中的每一position注意到在decoder中的所有positions,直到包含该position。我们需要阻止在decoder中的左侧信息流,来保留自回归(auto-regressive)属性。我们通过对softmax(它对应到无效连接)的输入的所有值进行掩码(masking out,设置为)来实现该scaled dot-product attention内部。见图2.

3.3 Position-wise前馈网络

除了attention sub-layers之外,在我们的encoder和decoder中的每一层,包含了一个FC前馈网络,它可以独自和等同地应用到每个position上。在两者间使用一个ReLU来包含两个线性转换。

…(2)

其中,线性转换在不同的positions上是相同的,在层与层间它们使用不同参数。另一种方式是,使用kernel size为1的两个convolutions。输入和输出的维度是,inner-layer具有维度

3.4 Embedding和softmax

与其它序列转换模型相似,我们使用学到的embeddings来将input tokens和output tokens转换成维的向量。我们也使用常见的学到的线性转换和softmax函数来将decoder output转换成要预测的下一token的概率。在我们的模型中,我们在两个embedding layers和pre-softmax线性转换间共享相同的权重矩阵,这与[24]相同。在embedding layers中,我们会使用乘以这些权重。

3.5 Positional Encoding

由于我们的模型不包含recurrence和convolution,为了利用序列的顺序,我们必须注意一些与相关性(relative)或tokens在序列中的绝对位置有关的信息。我们添加”positional encoding”到在encoder和decoder stacks的底部的input embeddings中。该positional encodings与该embeddings具有相同的维度,因而两者可以求和。positinal encodings有许多选择,可以采用学到(learned)或者固定(fixed)。

在本工作中,我们使用不同频率的sin和cosine函数:

其中,pos是position,i是维度。也就是说:positional encoding的每个维度对应于一个正弦曲线(sinusoid)。波长(wavelengths)形成了一个从的几何过程。我们选择该函数是因为:我们假设它允许该模型可以很容易学到通过相对位置来进行关注(attend),因为对于任意固定offset k,可以被表示成一个关于的线性函数。

我们也使用学到的positional embeddings进行实验,发现两者版本几乎生成相同的结果(见表3 第E行)。我们选择正弦曲线版本,是因为它可以允许模型对序列长度长于训练期遇到的长度进行推导。

4.为什么用self-attention

在本节中,我们比较了self-attention layers与recurrent layers、convolutional layers的多个方面(它们常用于将一个变长序列的符号表示映射到另一个等长的序列上,其中:),比如:在一个常用的序列转换encoder或decoder中的一个hidden layer。启发我们使用self-attention主要有三方面考虑

  • 1.每一layer的总体计算复杂度
  • 2.可以并行计算的计算量,通过所需序列操作(ops)的最小数目进行衡量
  • 3.在长范围依赖(long-range dependencies)间的路径长度。学习长范围依赖在许多序列转换任务中是一个关键挑战。影响该能力(学习这样的依赖)一个的关键因素是,forward和backward信号的路径长度必须在网络中可穿越(traverse)。在input和output序列中任意位置组合间的路径越短,学习长范围依赖就越容易[11]。这里,我们也比较了由不同layer types构成的网络上,在任意两个input和output positions间最大路径长度。

t1.png

表1

如表1所示,一个self-attention layer会使用常数数目的序列执行操作(sequentially executed operations)来连接所有positions;而一个recurrent layer需要O(n)个序列操作(sequential operations)。根据计算复杂度,当序列长度n比representation维度d要小时(通常大多数情况下,使用state-of-art模型的句子表示,比如:word-piece和byte-pair表示),self-attention layers要比recurrent layers快。为了提升非常长序列任务的计算性能,self-attention可以限制到只考虑在input序列中围绕各自output position为中心的一个size=r的邻居。这可以将最大路径长度增大到。我们在未来会计划研究该方法。

kernel宽度的单个convolutional layer,不会连接上input和output positions的所有pairs。在连续kernels的情况下,这样做需要一个 convolutional layers的stack;在扩大卷积(dilated convoluitons)的情况下需要,这会增加在网络中任意两个positions间的最长路径的长度。卷积层(convolutional layers)通常要比recurrent layers开销更大,会乘以一个因子k。然而,可分离卷积(Separable convolutions),将复杂度减小到。有了,然而,一个可分离卷积的复杂度等于一个self-attention layer和一个point-wise前馈layer,在我们的模型中采用该方法。

另一个好处是,self-attention可以生成更多可解释模型。我们从我们的模型中内省(inspect)出attention分布,并在附录部分讨论示例。单独的attention heads不仅可以很明确地学习执行不同的任务,出现在展示行为中的多个()还可以与句子的形态结构和语义结构相关。

5.训练

5.1 训练数据和Batching

我们在标准的WMT 2014 English-German dataset上进行训练,它包含了将近450w句子对(sentence pairs)。句子使用byte-pair encoding进行编码,它具有一个37000 tokens的共享的source-target词汇表。对于英译法,我们使用更大的WMT 2014-English-French数据集,它包含了36M句子,32000个word-piece词汇表。句子对(sentence pairs)通过近似的序列长度进行打包。每个training batch包含了一个句子对集合,它会近似包含25000个source tokens和25000个target tokens。

5.2 硬件与schedule

在8块nvidia P100 GPUs上进行模型训练。对于我们的base models,它使用paper上描述的超参数,每个training step会花费0.4s。我们会为base models训练10w个steps 或12小时。对于我们的大模型(表3底部描述),step time是1s。大模型会训练30000 steps(3.5天)。

5.3 Optimizer

我们使用Adam optimizer,。我们会根据训练过程调整learning rate,根据以下公式:

…(3)

这对应于为前warmup_steps阶段线性增加learning rate,然后之后与step_num的平方根成比例减小。我们使用的warmup_steps=4000.

6.结果

6.1 机器翻译

在WMT 2014 English-to-German翻译任务上,big transformer model(见表2: Transformer(big))的效果要比之前最好的模型(包括ensembles)要好2.0 BLEU,达到一个新的state-of-art BLEU分:28.4. 该模型的配置列在了表3的底部。训练会在8张P100 GPUs上训练3.5天。我们的base model胜过之前发布的所有模型和ensembles,训练开销只是其他模型的一小部分。

t2.png

表2:

在WMT 2014 English-to-French翻译任务上,我们的big model的BLEU得分为41.0, 比之前发布的single models都要好,训练开销只有之前state-of-art model的1/4. 对于English-to-French所训练的Transformer(big)模型,使用dropout rate为:,而非0.3。

对于base models,我们使用一个single model,它通过最后的5个checkpoint进行平均获得,每个checkpoint会有10分钟的时间间隔。对于big models,我们则对最后的20个checkpoints进行平均得到。我们使用的beam search的beam size为4, length penalty为 α = 0.6. 这些超参数会在实验之后选择。我们在推断(inference)期间设置最大的output length为: (input length+50),当可能时会提前终止。

表2归纳了我们的结果,并比较了与其它模型结构间的翻译质量和训练开销。我们估计了用于训练一个模型的浮点操作的数目,乘以训练时间,所使用的GPUs数目,以及每个GPU的持续的(sustained)单精度浮点能力(single-precision floating-point capacity)。

6.2 模型变种

为了评估Transformer中不同组件的重要性,我们以不同的方式区分我们的base model,并在数据集newstest2013上测量了在English-to-German翻译上的效果。我们使用前一节描述的beam serach,但没有进行checkpoint averaging。我们的结果在表3中。

t3.png

表3

在表3 rows(A),我们会使用不同的attention heads数目、attention key和value维度,来保持常数级的计算量,如3.2.2节所描述的。而single-head attention是0.9 BLEU,它比最佳setting要差,如果有太多heads质量也会下降。

在表3 rows(B),我们观察到减小attention key size 会伤害模型质量。这建议我们,决定兼容并不容易,一个dot-product更复杂的兼容函数可能会更有意义。进一步观察(C)和(D),模型越大越好,dropout在避免over-fitting上更有用。在row(E)上,我们使用已经学到的positional embedding[8]来替换了我们的sinusoidal positional encoding,结果与base model几乎相同。

7.结论

Transformer是首个完全基于attention的序列转换模型(sequence transduction model),它使用multi-headed self-attention来替换在encoder-decoder架构中常用的recurrent layers。

对于翻译任务,Transformer训练要比基于recurrent或convolutional layers的结构要快很多。在WMT 2014 English-to-German和WMT 2014 English-to-French翻译任务上,我们达到了一个新的state-of-the-art效果。

我们对attention-based模型的将来很激动,计划应用到其它任务上。我们计划将Transformer扩展到涉及输入输出形态的非文本问题,研究local, restricted attention mechanisms以有效处理大的inputs和outputs(比如:图片、音频、视频)。生成更少序列是另一个研究目标。

代码在:https://github.com/tensorflow/tensor2tensor

参考