1.介绍

对于词(words)的分布式组成语义的算法开发是一个长期存在的开放性难题。最近几年的算法有:将word vectors映射到sentence vectors(包括recursive networks, recurrent networks, convolutional networks,以及recursive-convolutional方法)。所有的这些方法会生成句子表示,传给一个监督式任务,依赖一个class label来对组成权重(composition weights)做BP算法。因而,这些方法能学到高质量句子表示,但只能对自己的特定任务进行调整。paragraph vector是另一种方法,它通过引入一个分布式句子索引作为模型的一部分,以非监督式学习进行句子表示。

本文中,我们考虑了另一种loss function,可以用于任何组成操作(composition operator)上。考虑以下的问题:是否存在一个任务,它对应的loss允许我们学习高度泛化的句子表示?受使用word vector学习的启发,我们提出了一个目标函数,它从句子级别上抽象了skip-gram模型。也就是说,它不再使用单个word来预测它的上下文,我们会encode一个句子。因而,任何组成操作(composition operator)都适用于一个句子编码器(sentence encoder),只是目标函数被修改了而已。图1展示了该模型,我们会调用我们的skip-thoughts模型和向量。

图1: skip-thoughts模型。给定一个tuple(),表示book中的第i个句子,被编码并尝试重构前一个句子和下一个句子。在本例中,输入的句子三元组:I got back home. I could see the cat on the steps. This was strange. 未绑定箭头被连接到encoder output上。颜色表示哪个component共享参数。(与skip-gram有点像)

表1: BookCorpus dataset的统计信息

我们的模型依赖于一个关于连续文本的训练语料。我们选择使用一个小说集合BookCorpus dataset来训练我们的模型。这些书由未出版的作者编写。该dataset具有6种不同的种类:Romance, Fantasy, Science fiction , Teen等。表1高亮了该语料的统计。伴随着故事,书包含着对话,感情(emotion)和广泛的字符交叉。另外,训练集的量很大,不会偏向于任何特定领域或应用。表2展示了该语料中句子的最近邻。该结果展示了skip-thought vectors精确地捕获了编码后的句子的语义和结构。

表2: 在每个样本中,第一个句子是一个query,而第二个句子是它的最近邻。通过从语料中随机抽取5w个句子中,通过计算cosine相似度进行最近邻分数排序。

我们以新的setting评估了我们的向量:在学到skip-thoughts后,冻结模型,使用encoder作为一个泛化的特征抽取器(generic feature extractor)以用于特定任务。在我们的实验中,我们考虑了8个任务:句义相关性,段落检测,图像句子排序以及其它5个标准的分类benchmarks。在这些实验中,我们抽取了skip-thought向量,并训练了线性模型来评估它的表示(representations),没有任何额外的参数fine-tuning。结果说明,skip-thoughts提出的泛化表示对所有任务都很robust。

一个难点是,这样的实验会构建一个足够大的词汇表来编码句子。例如,一个从wikipedia文章中的句子可能包含了与我们的词汇表高度不一样的名词。为了解决这个问题,我们学到了一个mapping:从一个模型传递给另一个模型。通过使用cbow模型预训练好的word2vec表示,我们学到了这样的一个线性映射:将在word2vec空间中的一个词映射到encoder词汇表空间中的一个词上。学到的该mapping会使用所有单词,它们共享相同的词汇表。在训练后,出现在word2vec中的任何word,可以在encoder word embedding空间中获得一个vector。

2.方法

2.1 引入skip-ghought vectors

我们使用encoder-decoder模型框架来对待skip-thoughts。也就是说,一个encoder会将words映射到一个句子向量(sentence vector)上,一个decoder会用于生成周围的句子。在该setting中,一个encoder被用于将一个英文句子映射到一个向量。decoder接着根据该向量来生成一个关于源英文句子(source sentence)的翻译(translation)。已经探索了许多encoder-decoder pair选择,包括:ConvNet-RNN,RNN-RNN,LSTM-LSTM。源句子表示(source sentence representation)也可以通过使用一个attention机制来动态变化,用于说明任何时候只有相关的才用于翻译(translation)。在我们的模型中,我们使用一个带GRU activations的RNN encoder,以及一个conditional GRU的RNN decoder。该模型组合近似等同于神经机器翻译中的RNN encoder-decoder【11】。GRU展示了在序列建模任务中效果比LSTM要好,并且更简单。GRU units只有两个gates,不需要使用一个cell。而我们的模型则使用RNN,只要能在它之上进行BP算法,任何encoder和decoder可以被使用。

假设我们给定了一个句子的tuple:。假设表示了句子中的第t个word,表示它的word embedding。我们将模型描述成三部分:encoder,decoder,目标函数。

Encoder:假设是句子中的words,其中N表示在句子中的words数目。在每个step中,encoder会产生一个hidden state:,它可以解释成序列的表示(representation)。hidden state:可以表示整个句子。

为了encode一个句子,我们对下面的等式进行迭代(这里去掉了下标i):

… (1)

… (2)

… (3)

…(4)

其中 是在时间t提出的状态更新,是update gate,是reset gate()表示一个component-wise product。两个update gates会采用0到1间的值。

Decoder: decoder是一个神经语言模型,它的条件是encoder output 。该计算与encoder相似,除了我们引入了矩阵,以及C,它们被用于偏置由句子向量计算得到的update gate,reset gate和hidden state。一个decoder会被用于下一个句子,而第二个decoder被用于前一句子。Separate参数被用于每个decoder,除了词汇矩阵V,它的权重矩阵会连接decoder的hidden state,以便计算在词上的一个分布。我们在下一个句子上描述decoder,通过一个在前一句子上的类似计算得到。假设表示decoder在时间t的hidden state。对下面的等式进行迭代(丢掉下标i+1):

…(5)

…(6)

…(7)

…(8)

给定,单词的概率给出了前(t-1) words,encoder vector为:

…(9)

其中,表示V的行,对应于word 。对于前面句子可以做一个类似的计算。

目标函数。给定一个tuple ,目标优化为:

…(10)

总的目标函数是对所有这样的training tuples进行求和。

2.2 词汇表膨胀

现在,我们会描述如何将我们的encoder的词汇表扩展到那些在训练期间未见过的词上。假设我们有个被训练的模型引入了词表示(word representations),假设表示了RNN的词向量空间。我们假设词汇表更大。我们的目标是构建一个mapping f: ,它由一个矩阵W进行参数化,比如:,其中。受[15]的启发,它会学到在词空间转移之间的线性映射,我们为矩阵W求解一个非正则的L2线性回归loss。这样,对于编码中的句子,任何来自的词可以被映射到

3 实验

在我们的实验中,我们在BookCorpus dataset上评估了我们的encoder作为一个通用的feature extractor的性能。实验setup如下:

  • 使用学到的encoder作为一个feature extractor,抽取所有句子的skip-thought vectors
  • 如果该任务涉及到计算句子对(pairs of sentences)之间的分数,会计算pairs间的component-wise features。
  • 在抽取的features上训练一个线性分类器,在skip-thoughts模型中没有任何额外的fine-tuning或者backpropagation。

我们限定在线性分类器主要出于两个原因。第一个是为了直接评估计算向量的representation quality。如果使用非线性模型可能会获得额外的性能增益,但这超出了我们的目标。再者,它可以允许更好地分析学到的representations的优点和缺点。第二个原因是,重现(reproducibility)很简单。

3.1 训练细节

为了引入skip-thought vectors,我们在我们的book corpus上训练了两个独立的模型。一个是带有2400维的unidirectional encoder,它常被称为uni-skip。另一个是一个bidirectional model,forward和backward每个各1200维。该模型包含了两个encoder,它们具有不同的参数:一个encoder会给出正确顺序的句子,另一个会给出逆序的句子。输出接着被拼接形成一个2400维的向量。我们将该模型称为bi-skip。对于训练,我们会初始化所有的recurrent矩阵:进行正交初始化。non-recurrent weights则从一个[-0.1, 0.1]的均匀分布上进行初始化。使用mini-batches的size=128, 如果参数向量的norm超过10, 梯度会被裁减(clip)。我们使用Adam算法进行optimization。模型会被训练两周。另外作为一个额外的试验,我们使用一个组合模型导出了试验结果,包含了uni-skip和bi-skip,会生成4800维的向量。我们称该模型为combine-skip。

在被模型被训练后,我们接着使用词汇扩展,将word embedding映射到RNN encoder空间上。会使用公开提供的CBOW word vectors[2]。被训练的skip-thought会有一个词汇size=20000个词。在从CBOW模型中移除多个word样本后,会产生一个词汇size=930911个词。这样,即使被训练的skip-thoughts模型具有20000个词,在词汇表扩展后,我们可以对930991个可能的词进行成功编码。

由于我们的目标是将skip-thoughts作为一个通用的feature extractor进行评估,我们将文本预处理保持最低水平。当编码新句子时,除了基本的tokenization,不会有额外的预处理。这样做可以测试我们的vectors的健壮性。作为一个额外的baseline,我们也会考虑来自uni-skip模型学到的word vectors的平均(mean)。我们将该baseline称为bow。这会决定着在BookCorpus上训练的标准baseline的效果。

3.2 语义相关性

3.3 段落检测

3.4 Image-sentence ranking

3.5 Classification benchmarks

3.6 skip-thoughts可视化

t-sne.

参考

Convolutional Neural Networks for Sentence Classification

我们来看下yahoo的《Product Recommendations at Scale》中提出的prod2vec方法:

1.介绍

世界上许多人在每天都会浏览email收件箱,大多数时间会与它们的通讯录进行联系,还有一部分时间用于账单确认,读取新信息,以及跟踪购买( tracking purchases)。为了对这种流量进行商业化,email客户端通常会在原生email内容的边上以图片的形式展示广告。说服用户切出”email模式”(即连续处理邮件任务),进入一个新模式让人们愿意去点广告是个挑战。通过有效的个性化和定向(targeting),目标是为单个用户发现与他最匹配的广告展示给他,因而广告需要高度相关,以克服用户只关注email任务的倾向。除了获得财务收益外,为每个消费者的口味量身定制的广告也能改善用户体验,可以增加用户的忠诚度和用户粘性。

对于广告定向(ad targeting),收件箱emails仍未被充分进行explored & exploited。最新研究表明,只有10%的收件量表示是人类生成(非机器生成)的emails。这之外的90%流量中,超过22%表示与在线电商有关。假设整体流量中大部分是有商业目的的,定向广告的一种流行形式是电邮重定位(MRT: mail retargeting),其中,广告主会对之前从特定商业网站(web domain)上接收过邮件的用户进行定向。这些电子邮件对于广告定向来说很重要,它们会给出用户感兴趣的相应商品的一个大图(broad picture)进行展示。最新paper[14]利用聚类方法来生成MRT规则,展示了这样的规则比由人类专家生成的要更精准。

图一:Yahoo Mail中的商品推荐

然而,为了超出MRT规则之外,用户和商业网站的交互,广告商需要更多数据(比如:购买过的商品名和价格,通常是email邮件的一部分)。email客户端与商业网络能很好结合,对电子邮件格式进行标准化,产生的schemas通过schema.org社区进行维护。越来越多的商业网站使用标准schemas,email客户端可以提供更个性化的用户通知,比如:包裹跟踪(package tracking)和 航班详情(flight details)。另外,email receipt extraction带来了赚钱机会,基于客户的购买历史将商品广告带给用户。有了从多个商业email domain上的购买数据,比起其它基于单一商业email domain来说,可以更好地将email provider放置到在唯一的位置上,以便能构建更好的推荐系统。特别的,不同于商业网站可以做出这样的推荐:“买了X的顾客,也会买Y”,email providers可以做出这样的推荐:“从生产商V1处购买了X的顾客,也会从生产商V2处购买Y”,允许更强大和更有效的定向解决方案。

在本paper中,我们为Yahoo Mail提供了一种end-to-end的商品广告开发方案。工作包含了开发一个商品级别的购买预测算法,能扩展到数百万的用户和商品。出于该目的,我们提出了一种方法,使用一个神经语言模型,将它应用到用户购买时间序列上,从而将商品嵌入到real-valued,低维的向量空间中。作为结果,具有相近上下文的商品(它们相邻近的购买行为)可以映射到在embedding空间中更接近的地方。关于下一个要购买的商品,为了做出有意义和更多样的建议,我们会进一步将商品向量进行聚类,并建模聚类间的转移概率。来自可能的聚类在向量空间中更接近的商品,会被用于形成最终推荐。

商品预测模型会使用一个大规模的购买数据集进行训练,由2900w用户的2.8亿购买行为组成,涉及210w个唯一的商品。该模型会在一个held-out month上进行评估,其中,我们在收益率(yield rate)上测试了推荐的有效性。另外,我们会评估一些baseline方法,包含展示流行商品给所有用户,以不同用户分组(称为:分群(cohorts),由用户性别、年龄、地域)展示流行商品,以及展示在一个用户最近购买商品之后历史最常购买的商品。为了减轻冷启动问题,在用户的分群(cohort)中的流行商品会被用于补足那些早期没有购买行为的用户的推荐。

3.方法

本节中,我们描述了该商品推荐任务的方法论。为了解决该任务,我们提出了从历史日志中使用自然语言模型学习在低维空间中的表示。商品推荐可以通过最简单的最近邻搜索得到。

更特别的,给定从N个用户中获取的email receipt日志的一个集合S,其中用户的日志为 被定义成一个关于M个receipts的连续序列,每个email recept 包含了个购买的商品,我们的目标是发现每个商品p的D维实数表示,以便相似的商品可以在向量空间中更近的位置。

我们提供了一些方法来学习商品表示。首先提出了prod2vec方法,它会考虑所有已经购买的商品。接着提出了新的bagged-prod2vec方法,它会考虑在email receipts中一起罗列被购买的一些商品,它们会产生更好、更有用的商品表示。最终,我们会利用上学到的representations来分别表示一个prod2prod和user2prod的推荐模型。

3.1 低维商品embeddings

图二:prod2vec skip-gram模型

prod2vec:prod2vec模型会将一个购买序列看成是一个“句子”,在这个序列中的商品看成是“词”。详见图2, 更特殊的,prod2vec使用skip-gram模型来学习商品表示,通过以下的最大化目标函数:

…(3.1)

其中,来自相同email receipt的商品可以是任意顺序。概率表示:给定当前商品,观察到一个邻近商品的概率,使用softmax函数进行定义如下:

…(3.2)

其中,。。。。

图3: bagged-prod2vec模型更新

bagged-prod2vec:为了对多个商品同时购买的行为做出解释,我们提出了一个修改版本的skip-gram模型,它引入了一个概念:购物袋(shopping bag)。如图3所示,该模型会在email receipts级别进行操作,而非在商品级别。通过对email序列s上的一个修改版目标函数进行最大化,来学习商品向量表示:

…(3.3)

商品是从邻近的email receipt 上观察到商品的概率,,给定从第m个email receipt的第k-th个商品,到一个商品的概率:

每个P的定义使用softmax(3.2)。注意在(3.3)中的第三个求和会随着receipts进行,因而,从相同的email receipt中得到的items在训练期间不会相互预测。另外,为了捕获商品购买的时序特性(temporal aspects),我们提出了使用有向语言模型,我们只使用未来的商品(future product)作为上下文。该修改版允许我们学习商品embeddings来预测将来的购买行为。

learning:该模型使用SGA( stochastic gradient ascent)进行最优化,很适合大规模问题。然而,在(3.1)和(3.3)中的梯度计算,很适合词汇size P,实际任务中,计算开销会随着P的增大而变得很昂贵,很容易达到上百万的商品。另一方面,我们使用negative sampling方法,它能显著减小计算复杂度。

3.2 prod-2-prod预测模型

在学习了低维商品表示后,我们考虑了来预测下一商品的购买概率的一些方法。

prod2vec-topK:给定一个购买商品,该方法会为所有在词汇表中的商品计算cosine相似度,并推荐最相似商品的top K

prod2vec-cluster:为了能做出更多样化(diverse)的推荐,我们考虑将相似商品分组成聚类,从与之前购买商品相关的聚类中推荐商品。我们应用K-means聚类算法来在hadoop FS上实现,将商品基于cosine相似度进行聚类。我们假设:在从聚类上进行一个购买后、再从任意第C个聚类中进行一次购买的行为,符合一个多项式分布(multinomial distribution),其中是从聚类中进行一次购买后、接着从聚类中进行一次购买的概率。为了估计参数,对于每个i和j,我们采用一个最大似然方法:

…(3.4)

  • count of ci purchases: c_i购买的数目
  • # of times ci purchase was followed by cj: c_i购买后跟c_j的次数

为了给一个购买过的商品p推荐一个新商品,我们首先标识了p属于哪个聚类(例如: )。接着,我们会对所有聚类,通过值进行排序,然后考虑取与聚类top相关的聚类中的top个商品。最后,从top聚类中的商品通过与p计算cosine相似度进行重排序,取top K进行推荐。

3.3 User-to-product预测模型

除了prod2prod预测外,大多数推荐引擎允许user-to-product方式的预测,为一个用户进行推荐通常会考虑历史购买、或(和)兴趣,使用其它数据源:用户在线行为、社交行为等。在本节中,我们提出了一个新方法来同时学习商品的向量表示、以及给定一个用户,发现在joint embedding space发现K个最近商品的用户推荐。

user2vec:受paragraph2vec算法的启发,user2vec模型会同时学习商品和用户的特征表示,它会将用户当成是一个“全局上下文”。这样的模型如图4所示。训练数据集来自于用户购买序列S,它会包含和其它已购商品(通过购买时间序排列),,其中表示用户购买的items数目。在训练期间,用户向量会被更新,来预测从他的email receipts中的商品,其中,学到的product vectors会预测在上下文中的其它商品。出于表示的简洁性,在下面,我们会表示no-bagged版本的模型,注意,使用bagged版本进行扩展也很方便。

图4: 对用户的User embeddings,进行产品预测

更特殊的,user2vec的目标函数是,最大化所有购买序列的集合S上的似然:

…(3.5)

其中,c是第n个用户的购买序列上下文长度。被定义为使用一个softmax函数:

…(3.6)

其中的输出向量表示,是商品上下文的平均向量表示,包含了相应的,定义如下:

…(3.7)

其中,是p的输入向量表示。相似的,概率定义如下:

…(3.8)

其中的输出向量表示,是用户的所有商品平均输入向量表示的平均:

…(3.9)

user2vec模型的一个主要优点是,商品推荐是基于该用户的购买历史进行量身定制的。然而,缺点是,该需要需要非常频繁地进行更新,不同于product-to-product方法,它可以长期是相关的,而user-to-product推荐需要经常变化来对最近购买行为做出解释。

4.实验及其它

略,详见paper.

4.4 推荐预测商品

我们对推荐商品给用户进行实验,比较以下算法:

  • 1) prod2vec-topK:使用数据集进行训练,其中,商品向量通过对购买序列s通过极大似然估计进行学习。给定一个商品,通过向量空间计算cosine相似度选择topK个相似商品。
  • 2) bagged-prod2vec-topK:使用进行训练,其中商品向量通过email序列s通过极大似然估计进行学习。对于给定商品,通过选择在结合向量空间计算cosine相似度选择topK个相似商品。
  • 3) bagged-prod2vec-cluster: 与bagged-prod2vec模型的训练类似,接着将商品向量聚类成C个聚类,并计算它们间的转移概率。接着标识出属于哪个聚类(例如:),我们根据的转移概率对各聚类进行排序,取出top个聚类,然后聚出这些top聚类的商品通过计算与的cosine相似度进行排序,其中每个聚类的top 被用于推荐()。 bagged-prod2vec-cluster与 bagged-prod2vec的预测结果如表2所示。可以看到聚类方法多样性更好。
  • 4) user2vec:使用进行训练,其中商品向量和用户向量通过极大似然估计进行学习。给定一个用户,通过计算用户向量与所有商品向量的cosine相似度,检索出top K近邻商品。
  • 5) co-purchase:对于每个购买pair:,计算频率,其中,商品在商品之后立即购买。接着,给商品的推荐通过频率进行排序,取topK商品。

表2: 潜水呼吸管(cressi supernova dry snorkel)的商品推荐

在第天之前,由于用户具有多个商品的购买行为,为了在这一天选择最好的K个商品,各种独立的预测( separate predictions)必须达成一致。为了达到该目的,我们提出了时间衰减的推荐评分scoring,在根据最高得分选择top K个商品之后使用。更特别的,给定用户在天前的商品购买行为以及它们的时间戳(timestamps):,对于每个商品,我们会根据相似得分检索top K个推荐,产生集合,其中sim表示cosine相似度。接着,我们为每个推荐商品计算一个衰减得分(decayed score):

其中是当前天与产生推荐的商品购买时间的差,其中是衰减因子。最终,按照衰减评分降序,并取topK个商品作为第天的推荐。

表1:通过bagged-prod2vec模型生成的商品推荐示例

训练细节:神经语言模型会使用一台96GB RAM内存的24core机器。embedding space的维度被设置成d=300, 上下文neighborhood size为5. 最后每个向量更新中使用10 negative samples。与[24]的方法相似,最频繁的商品和用户在训练期间会进行子抽样(subsampled)。为了展示该语言模型的效果,表1给出了使用bagged-prod2vec推荐的样例,可以看到邻居商品与query商品高度相关。(例如:“despicable me 卑鄙的我(动画电影)”,该模型会检索到相似卡通片)

评估细节: 与流行商品的accruracy如何测量类似,我们假设每个用户有一个K=20不同商品推荐。对于天的预测,会基于先前天的购买进行预测,我们不会考虑在该天期间发生的购买行为来更新第天的预测。

结果:我们评估了decay factors不同值所对应的prod2vec表现。 在图9中,我们展示了在测试数据(往前看1,3,7,15,30天)上的预测准确率。初始的prod2vec预测会基于在训练数据集最后用户购买。该结果展示了不同预测对于产生推荐准确率提升的预测的折扣,decay factor=0.9是一个最优选择。

9.png

图9: 不同decay值的prod2vec accuracy

参考

关于fastText,有两篇paper需要看下,见下面的参考。如果你的目的是用来训练词向量,可以查看paper 1. 如果是用来进行文本分类,参考paper 2.

第1为《Enriching Word Vectors with Subword Information》:使用subword的信息来增强词向量。

对于常规的一些词向量模型,它们将词汇表中每个词表示成一个不同的向量,在训练中会忽略词形。这对于一些大词汇量、许多罕见字、且词形丰富的语言来说(比如:Turkish语 或 Finnish语),是个很大限制,很难使用这些模型训练到较好的词级别(word-level)的向量。fastText是一种基于skip-gram模型的新扩展,它会使用subword的信息,将每个词被表示成一个字符级n-gram词袋(a bag of character n-grams)。每个向量表示与每个字符级n-gram相关联,而词(word)则可以看成是这些n-gram向量表示的求和(sum)。fastText在大语料上训练很快。

1.介绍

在NLP领域学习词的连续表示(continuous representations)已经有一段历史了(rumelhart et al., 1988)。这些表示通常来自于大型无标记语料来使用共现统计获得(Deerwester et al., 1990)。大部分工作称为“分布式语义(distributional semantics)”,已经研究了这些方法的属性(turney et al.,2010..)。在神经网络社区,Collobert和Weston(2008)提出了使用一个前馈网络来学习word embeddings,它通过基于一个词的左前两词和右后两词来预测中心词。最近,Mikolov(2013b)提出了一种简单的log-bilinear模型来高效学习大规模语料的连续表示。

通过一个不同的向量(distinct vector)来表示词汇表中的每个词,不需要参数共享。特别的,它们忽略了词的内部结构,对于词型丰富的语言( morphologically rich languages)来说,比如Turkish语 和 Finnish语,这是个重要的限制。这些语言包含了许多罕见词,使得很难学习很好的word-level representations。在本paper中,我们提出了为character n-grams学习词表示,并将words表示成n-gram vectors的求和(sum)。我们的主要贡献是对Mikolov的skip-gram做了一个扩展,让它能解释subword information。我们在五种语言上(它们具有不同的词型)评估了该模型,展示了我们的方法的好处。

2.相关工作

形态学词表示(Morphological word representations): 最近几年提出了不少方法,将形态学信息插入到词向量中。为了更好地建模罕见字,Alexandrescu和Kirchhoff(2006)引入了因子化的自然语言模型,其中词被表示成关于特征的集合。这些特征可以包含形态学信息,该技术被成功应用于形态学丰富的语言中,比如:Turkish(Sak 2010)。最近,一些相关的工作提出了不同复合函数来从词素(morphemes)生成词表示。这些不同的方法依赖于词的一个形态学解耦,但我们的方法不会。相似的,Chen(2015)介绍了一个方法来联合学习中文词和字符的embeddings。Soricut(2015)提出了将形态相似的词限制到具有相似表示。Soricut(2015)描述了一个方法来学习形态学转移的向量表示,允许通过应用规则来获取对未登陆词的表示。Cotterell(2015)则在形态学标注的数据上学习词表示。与我们的方法最接近的是Schutze(1993),它通过SVD来学习字符级4-grams的表示,并通过对4-gram representations进行求和来生成词表示。

NLP的字符级特征(Character level features):与我们工作相关的另一个研究领域是,NLP的字符级模型,它直接从字符序列中学习表示。这种模型的最高级方法是RNN,应用到语言建模(Mikolov 2012)、文本归一化(Chrupala, 2014),、词性标注(Ling.2015)、parsing(Ballesterors.2015)。该模型的另一个家族是在字符上训练的CNN,它可以被应用到:词性标注(Santos,2014)、情感分析(dos Santos.2014)、文本分类(zhang.2015)、语言建模(Kim.2016)。(Sperr.2013)提出了基于受限波尔茨曼机的语言模型,其中词被编码成字符级别n-grams的一个集合。最后,在机器翻译中的最近工作也提出了使用subword units来获取罕见词的表示。(Sennrich.2016)

3.模型

本节中,我们提出了一个模型来学习representations来解释词形。

1.1 通用模型

先简单回顾下(Mikolov et al.,2013b)提出的continuous skip-gram模型,给定一个size=W的词汇表,其中词通过它的索引进行表示 ,目标是为每个词w学习一个向量表示。受分布式假设的启发,这些表示被训练来预测在一个给定词的上下文中出现的词。更正式的,给定一个大型训练语料,一个词序列: ,它的skip-gram模型的目标函数是最大化log似然:

其中,上下文表示在词周围词的索引集合,给定,预测观察到的概率。使用一个scoring函数s,可以将(word,context)pair映射到一个R空间的分值上:

该问题也可分解为多个二分类问题,目标是预测对应的是否出现。对于位置t的词,以及上下文c,我们可以得到negative log-likelihood:

其中是一个从词汇表抽样出的负样本集合。logistic loss函数,我们可以获得相应的目标函数:

和上下文词采用标量积:$ s(w_t,w_c)=u_{w_t}^{T}v_{w_c} $

1.2 Subword模型

由于每个词会使用一个不同的向量表示,skip-gram模型会忽视词的内部结构。在本部分,我们接着提出一个不同的scoring函数 s,将subword信息考虑进行。给定一个词w,我们定义在w上出现的n-gram集合为:$ G_w\subset{1,…,G} $.我们将一个向量表示与每个n-gram g相关联。我们可以通过对这些n-gram的向量进行求和来表示一个词。我们获得一个scoring函数:

对于词w,它的n-gram集合中总是包含着它,也可以为每个词学到一个向量表示。n-gram集合也是词汇表的一个超集(superset)。需要注意的是,对于共享相同的字序列(sequence of characters)的一个词和一个n-gram,会分配不同的向量给它们。例如,单词”as”和出现在词”paste”中的bigram “as”,会分配给不同的向量。这种简单模型允许在不同的词之间共享representations,从而对一些罕见词学到可靠的向量表示。

1.3 n-gram字典

上述模型很简单,并在的定义上留下了设计选择的空间。在本paper中,我们采用了一个非常简单的scheme:所有n-gram的长度在[3,6]范围内. 可以使用n-gram的不同集合,例如前缀和后缀。同时,也添加一个特殊字符做为词的开头和结尾,这样就可以区分前缀和后缀。

为了限定模型的内存,使用一个hashing函数,将n-gram映射到[1,K]上。下面,我们使用的K等于200w。在结尾处,一个词可以被表示成在词典中的索引,以及它的n-gram的hash值。为了提升模型效率,我们不会使用n-gram来表示在词汇表中最频繁的P个词。P的选择需要权衡,值越小表示计算代价越高,但性能越好。当P=W时,我们的模型就是skip-gram模型。

1.4 试验

数据集和baseline:将新模型与word2vec的cbow和skip-gram相比较。数据集:5种语言的Wikipedia数据。三种size:小(50M tokens),中(200M tokens),完整。训练使用的epoch为:5.

其它参数:negative-sample: 5, rejection threshold: $ 10^{-4} $, window-size: 5, min-count:5.

  • 小数据集:100维, 中数据集:200维,完整数据集:300维.
  • skip-gram baseline learning-rate: 0.025; CBOW: 0.05, 新模型:0.05

对于英文语料,新模型的训练速度比skip-gram慢1.5倍。

人肉相似度判断

评估向量的质量:计算人肉判断(human judgement)与向量表示之间的cosine相似度之间的Spearman rank相关系数

使用的数据集:

  • 英文:使用 WS353 (Finkelstein et al.2001)以及 RW (Luong et al.2013)
  • 德文:Gur65, Gur350,ZG222(Gurevych, 2005; Zesch and Gurevych, 2006)
  • 法文:RG65(Joubarne and Inkpen, 2011)
  • 西班牙文:WS353(Hassan and Mihalcea, 2009)

这些数据集中的一些词不会在训练数据中出现,对于CBOW方法和skip-gram baseline方法,我们不能获取这些词的向量表示。因此,我们决定排序包含这些词的pairs进行评测。我们在表1中上报了OOV比率。需要注意,我们的方法和baseline共享着相同的词汇表,因此,在相同训练集中的不同方法的结果是可以比较的。另一方面,不同训练语料上的结果是不可比较的,因为词汇表并不相同(具有不同的OOV rates)。

表1:

我们注意到,使用subword信息的新模型的效果在大多数数据集上的效果要好。我们也观察到,字符n-grams的效果,在德文上远比英文、西班牙文上好。一点也不令人吃惊,因为德文的字形更丰富。数据集越小,区别越重要。在RW英文数据集(罕见词数据集)上,新方法效要比baseline要好。

词类比任务(Word analogy)

使用Mikolov et al.(2013a)提出的:句法:syntactic(en-syn),以及语义:semantic(en-sem)来评测,数据集使用cs-all(Svoboda and Brychcin (2016), for Czech, 捷克文)。一些包含words的questions不会在训练语料中出来,我们会排除这些questions,并上报oov rate。所有的方法在相同数据上进行训练,因此可比较。我们上报了表1中的不同模型。我们观察到,字形(morphological)信息对于syntactic任务有极大的帮助,新方法在en-syn上效果要比baseline好。相反的,它在小数据集的semantic任务上,效果有所下降。第二,对于捷克文,一个字形丰富的语言,使用subword信息可以很强地提升效果(对比baseline)。

2.高效文本分类tricks

Mikolov等在中提到了多种高效文本分类的tricks,并提出了fastText。它的分类速度快,又不失精准。在标准多核CPU上训练,超过10亿词上只需要10分钟左右;而对50w的句子,在312K个分类上进行分类,1分钟之内即可完成。听上去有些小激动。

对应paper的研究主要是基于:有名标签预测(namely tag prediction), 情感分析(sentiment analysis),这两个领域做出的。

2.1 模型架构

baseline: 对于句子分类,简单又有效的baseline为:BOW向量 + 一个线性分类器(LR或SVM)。

线性分类器不会共享特征和分类间的参数。对于输出空间很大,但某些类上的训练样本很少的上下文上,这种方法的泛化能力受限。常用的解决方法是,将线性分类器分解为低秩矩阵(Schutze, 1992; Mikolov et al., 2013),或者使用多层神经网络(Collobert and Weston, 2008;Zhang et al., 2015)

图3展示了简单线性模型的秩约束(rank constraint)。第一个权重矩阵A,是一个在words上的look-up table。词向量被平均成一个文本向量,然后输入(feed)到一个线性分类器。文本向量是一个隐变量,它可以尽可能被复用。该架构与Mikolov提出的CBOW模型相似,中间的word被一个label所取代。我们使用softmax函数f来计算在预定义分类上的概率分布。对于N个文档的集合,目标是在这些类上最小化负log-likelihood:

其中xn是第n个文档的归一化的bag of features,yn是label,A和B是权重矩阵。该模型可以在多核CPU上使用SGD和一个线性衰减的learning_rate进行异步训练。

Hierarchical softmax

由于类的数目相当大,计算线性分类器的开销很大。计算复杂度是O(kh),其中k是类的个数,h是文本向量的维度。为了在运行时提升,可以使用基于Huffman树的Hierarchical softmax,具体可以详见另一篇。在训练期,它的计算复杂度下降到O(hlog2(k)).

当在测试阶段时,当查询最可能的分类时,Hierarchical softmax也很有优势。每个节点与一个概率相关,该概率表示从根节点到该节点上路径的概率。如果节点的深度为l+1,相应的父节点为:n1, n2, …, nl,概率为:

这意味着一个节点的概率总是比它的父节点要低。搜索某一深度的该树时,以及在叶子间跟踪最大概率,允许我们抛弃掉所有小概率的分枝。实际上,我们观察到在测试时,复杂度降到O(hlog2(k))。该方法会进一步扩展到使用binary heap来计算top T个target,开销为O(log(T))。

N-gram features

BOW与词序无关,显式采用该顺序的计算开销通常很大。作为替代,我们使用bag-of-n-grams作为额外的特征来捕获一些关于局部词序的部分信息(partial information)。这在惯例上很有效(Wang and Manning, 2012).

我们使用hashing trick(Weinberger et al., 2009),以及Mikolov et al.(2011)中相同的hashing function,以及10M的bins(如果我们只使用bigrams,否则可能100M),来维持一个快速的、内存高效的n-gram映射。

2.2 实验评测

fastText在两个不同的任务上进行评测。首先,会比较在情感分析(sentiment analysis)问题上的文本分类器。模型的实现可以使用Vowpal Wabbit library,但实际上使用的定制版本要比它快2-5x倍。

情感分析(Sentiment analysis)

数据集与baseline。使用8份由Zhang et al. (2015)提供的相同的数据集以及评测约定。使用Zhang et al. (2015)提供的n-gram和TF-IDF做为baselines。以及Zhang and LeCun (2015)提出的字符级卷积模型(char-CNN), (Xiao and Cho, 2016)提出的字符级卷积RNN模型(char-CRNN), Conneau et al. (2016)提出的极深卷积网络(VDCNN)。我们另外采用了Tang et al. (2015)的评测约定,上报了我们的方法以及他们的两种方法 (Conv-GRNN 和 LSTM-GRNN).

结果:使用10个隐单元,fastText迭代5轮(epochs),learning_rate为{0.05, 0.1, 0.25, 0.5}。在该任务上,添加bigram信息可以提升1-4%的效果。整体的accuracy比char-CNN和char-CRNN稍好一些,比VDCNN略差些。注意,可以使用更多的n-gram可以(略微)提升accuracy,例如:使用trigrams,在Sogou语料上的效果可以提升到97.1%。最终,下图展示了我们的方法与Tang et al. (2015)的比较。在验证集上调整超参数,并观察到:使用n-gram为5-gram时,会达到最佳性能。不同于Tang的方法,fastText不会使用pre-trained word-embeddings,据说在accuarcy上可以有1%的提升。

在训练时间上: char-CNN 和 VDCNN在NVIDIA Tesla K40 GPU训练,fastText的模型在使用20线程的CPU上训练。对于char-CNN,使用最新的CUDA实现,可以有10x的速度提升。fastText则可以在1分钟内完成训练。。。

标签预测

数据集和baselines: 采用YFCC100M数据集(Thomee et al., 2016),包含了100M的图片,带说明(captions),标题(titles),以及标签(tags)。我们只关注title和caption(不使用图片)来预测tags。将出现次数少于100次的words/tags进行移除,将数据分割成训练集/验证集/测试集。训练集包含大于9000W的样本(1.5B的tokens),验证集93W的样本,测试集54W的样本。词汇表的size为30W左右,有31W左右是唯一的tags。我们发布了一个脚本来重新创建该数据集。

我们使用一个基于频率的方法作为baseline,来预测最频繁的标签。我们也比较了Tagspace(Weston et al.,2014)的方法,它与我们的模型相类似,但基于Wsabie model of Weston et al. (2011)。Tagspace模型使用卷积进行描述,我们使用它的线性版本作为baseline。

结果与训练时间:上表为fastText与baseline的比较。比较了fastText 5轮的迭代,与两种隐层size(50, 100)的Tagspace算法。两种模型的隐层size都是小值时,在accuracy上效果相似,但如果增加bigram,会有极大的提升。在测试时,tagspace需要为所有类计算分值,这会相当慢,当类数目很大时(本例中为:300K),fastText的inference则会很快!

参考

0.介绍

Yoon Kim在《Convolutional Neural Networks for Sentence Classification》介绍了使用CNN来做句子分类的任务。下面基于对该paper的理解,简单地做个介绍:

1.模型架构

图1. 对于一个语句,使用双通道的模型架构

$ x_i \in R^k $ 为句子中第i个词的k维词向量。句子长度为n(不足补齐: pad),表示成:

… (1)

其中:

$ \oplus $为串联操作符(concatenation operator)。 $ x_{i:i+j} $ 表示 $ x_i $至$ x_{i+j} $的串联。

卷积(convolution)操作符涉及到一个过滤器(filter): $ w \in R^{h \times k} $,它可以应用于一个含h个词的窗口,来生成一个新的特征。例如,可以由一个词窗口$ x_{i:i+h-1}$来生成一个特征$c_i$

…(2)

这里 $ b \in R^{n-h+1} $是一个bias项,f是一个非线性函数(例如:假设函数tangent)。将filter应用在每个可能的句子中的词窗口:$ {x_{1:h}, x_{2:h+1},…,x_{n-h+1:n}} $来生成一个特征图(feature map)

…(3)

其中$ c \in R^{n-h+1}$,我们接着在该feature map上应用一个max-over-time pooling操作,并采用最大值$ \hat{c} = max \{ c \} $作为该指定filter相应的特征。该思路用来捕获最重要的特征——对于每个feature map取最大值得到。该pooling scheme天然就可以处理不同的句子长度。

我们接着描述该过程,通过从一个filter上抽取一个feature。该模型使用多个filters(具有不同的窗口size)来获得多个feature。这些特征构成了倒数第二层(penultimate layer),并被传到一个fully connected softmax layer,它的输出为在label上的概率分布。

在另一个模型变种中,我们试验了具有两个词向量的通道(channels)——一个保持static throughout training,另一个通过backpropagation进行 fine-tuned。在多通道的架构上,如图1所示,每个filter被应用于多个channel。被添加的结果用来计算等式(2)式中的$c_i$。该模型和单个channel的架构相似。

2.1 Regularization

对于Regularization,我们在倒数处二层(penultimate layer)使用dropout,使用一个关于权重向量的l2-norm的约束(constraint)。通过进行随机dropout, Dropout可以阻止隐单元的相互适应现象(co-adaptation)——这样,在前向传播(forward-backpropagation)期间将比例为p的隐单元置为0. 也就是说,给定倒数第二层(penultimate layer):$ z = [\hat{c}_1, …, \hat{c}_m] $(注意:这里有m个filter),做为替换,不再使用:

…(4)

对于在前向传播(forward propagation)中的输出单元y,dropout使用:

…(5)

其中$ \circ $是element-wise乘法操作,$ r \in R^{m}$是一个关于Bernoulli随机变量的’masking’向量,它具有概率p的部分为1。梯度通过后向传播,只通过unmasked的单元。在测试时,学到的weight向量通过p进行归一化,例如:$ \hat{w} = pw $,其中$ \hat{w} $被用来(没有dropout)对未见过的句子(unseen sentences)进行打分。我们又额外增加权重向量的l2-norms约束,通过对w进行rescaling,使得:$ {||w ||}_{2}$,在经历一个梯度下降的step后,将永远$ {||w ||}_2 > s $。

数据集

  • MR: 电影评论(Movie Reviews)。分类检测正负语义。(Pang and Lee, 2005)
  • SST-1: Stanford Sentiment Treebank——MR的扩展,具有train/dev/test splits,提供了细粒度标签(very positive, positive, neutral, negative, very negative)。 Socher et al. (2013)
  • SST-2: 类似SST-1. 移除了neutral评论,增加了binary labels
  • Subj:Subjectivity数据集,分类任务:将句子分类成:subjective or objective。(Pang and Lee, 2004).
  • TREC: TREC question数据集——将一个question分类成6个问题类型(该问题是关于:person, location, numeric information, etc.) (Li and Roth, 2002)
  • CR: 多种商品的顾客评价(Customer reviews)。预测positive/negative 评论。(Hu and Liu, 2004).
  • MPQA:MPQA数据集的意见极性检测(Opinion polarity detection)。 (Wiebe et al., 2005).

3.1 超参数和训练

对于所有数据集,统一使用:

  • ReLU
  • filter window(h)为:3, 4, 5
  • 每个window具有100个feature map
  • dropout rate (p)为:0.5
  • l2 constraint (s)为:3
  • mini-batch size为:50

这些值的选择在 SST-2 dev set上通过grid search找到。

我们不执行任意的指定数据集的调整,而是在dev sets上做early-stopping。对于没有标签dev set的数据集,我们随机选对10%的训练数据作为dev set。训练过程通过在shuffled mini-batchs数据上,使用Adadelta update rule(Zeiler, 2012),以及SGD来完成。

3.2 Pre-trained词向量

从非监督神经语言模型中获取词向量进行初始化,这种方法很流行。我们使用word2vec对Google News的1000亿个词进行训练。这些向量具有300维,使用CBOW架构,不在pre-trained词向量中的词则随机初始化。

3.3 模型变种

  • CNN-rand: 作为baseline模型,所有的词都是随机初始化,接着在训练中进行修改。
  • CNN-static: 使用来自word2vec的pre-trained vector的model。所有的词(包括随机初始化的未登陆词)保持static,只有模型中的其它参数是通过学习得到。
  • CNN-non-static: 与上面的方法相似,但对于每个任务,pre-trained vectors都会进行微调(fine-tuned)。
  • CNN-multichannel: 模型具有两个词向量集合。每个向量集都看成是一个’channel’,每个filter都会作用于两个channel,但梯度的后向传播只通过其中一个channel进行。这里模型可以fine-tune一个向量集,让另一个保持static。两个channel都通过word2vec进行初始化

为了对上述变种vs.其它随机因子进行比较,我们消除了其它源的随机性——CV-fold任务,未登陆词向量的初始化,CNN参数的初始化——在每个数据集上对它们保持统一。

4.结果

表2: CNN模型vs.其它方法。其它方法详见paper解释.

结果如表2所示。baseline model是CNN-rand:全随机初始化词,表现并不理想。通过使用pre-trained vector,会获得效果的提升。使用CNN-static的效果很显著,比起其它更复杂的深度学习模型(使用pooling或parse tree等),结果也有得一拼。这些结果说明了pre-trained vector很好、很通用(‘universal’)的feature extractors,并且可以跨数据集使用。对pre-trained vector进行微调(finetuning),可以为每个任务获得更进一步的提升(CNN-non-static)。

4.1 Multichannel vs. Single Channel Model

我们原先以为multichannel架构会阻止overfitting的发生(通过确保学到的vector与原先的值偏离太远),会比single channel效果更好,尤其是在小数据集的情况下。然而,结果参半,需要更进一步对fine-tuning过程进行正则化(regularizing)。例如,对于no-static部分使用一个额外的channel,你可以保持一个single channel,并可以额外的维度,它们允许在训练过程中进行修改。

表3: top 4个邻近词——基于consine相似度——static channel(左列)中的向量,在SST-2数据集上,在训练后的multichannel模型中的non-static channel(右侧)中的finetuned vector。

4.2 static vs. Non-static表示

正如single channel non-static model的情况,multichannel模型能够对 non-static channel进行微调(fine-tune),来使要处理任务更具指定性。例如:good在word2vec中与bad最相似,推测起来是因为它们在句子结构(syntactically)上(大至)是相等的。但对于在SST-2数据集上进行微调的non-static channel中的词向量,不再有表3中的情况。相似的,在表示语义上,good与nice更接近(比起good与great),这的确可以反映在学到的向量中。

对于不在pre-trained vector中的token(随机初始化),进行fine-tuning可以使这些token学到更有意义的表示(representation):该网络可以学到:感叹号(exclamation marks)与感情表达有关,逗号与连接词有关。

4.3 进一步观察

  • Kalchbrenner et al. (2014),使用一个 CNN得到更糟的结果,本质上与single model的架构一致。例如,它们的Max-TDNN(Time Delay Neural Network)使用随机初始化的词,在SST-1上获得了37.4%,而我们的模型则为45.0%。我们将这种差异归因于:我们的CNN具有更大的容量(多个filter widths和feature maps)。
  • Dropout被证明是一种很好的regularizer, 它很容易使用一个更大的网络,只需dropout去进行regularize即可。Dropout可以增加2-4%的效果提升
  • 当随机初始化的词不在word2vec中时,通过从U[-a,a]中抽样每一维,可以获得微小的提升,其中选中的a,可以使随机初始化的向量具有与pre-trained vector具有相似的variance。在初始化过程,使用更复杂的方法来反映(mirror)pre-trained vectors的分布,来获得提升是挺吸引人的一件事。
  • 我们试验了另一个公共的词向量(由Collobert et al. (2011) on Wikipedia训练得到),发现word2vec可以获得更好的效果提升。这一点不是很清楚:是否是因为o Mikolov et al. (2013)的架构,还是因为google news 1000亿词的数据集的原因。

5.结论

本文描述了在word2vec上构建CNN的一些试验。只需很少的超参数的调参,一个简单的CNN具有一层的卷积层,就可以得到令人吃惊的效果。本文的结果也有效验证了在Deep NLP中pre-trained word vector相当重要。

参考

Convolutional Neural Networks for Sentence Classification

介绍

在解析XGBoost的源码之前,我们先理解下陈天奇在paper《XGBoost: A Scalable Tree Boosting System》一文中提到的一些概念。

XGBoost的可扩展性(scalability)归因于一些重要的系统优化和算法优化。这些优化包括:

  • 一种新的tree-learning算法(a novel tree learning algorithm):用于处理稀疏数据(sparse data)
  • 一种理论正确的加权分位数略图过程(a theoretically justified weighted quantile sketch procedure):用于处理在近似的tree-learning中实例权重

由于XGBoost的并行化和分布式计算,使得learning过程比其它模型实现要快。更重要地,XGBoost实现了核外计算(out-of-core computation: 基于外存),使得数据科学家们可以在pc机上处理上亿的训练实例。最终,会把这些技术结合起来实现一个end-to-end的系统,可以扩展到集群上。

主要内容:

  • 1.设计和建立了一个高度可扩展的end-to-end tree boosting系统
  • 2.提出了一种理论正确的加权分位数略图过程(theoretically justified weighted quantile sketch procedure),用于高效地进行预计算
  • 3.介绍了一种新的稀疏感知算法(sparsity-aware algorithm),用于并行化tree learning
  • 4.提出了一种高效的内存感知块结构(cache-aware block structure),用于核外(out-of-core)tree learning

2.tree-boosting回顾

XGBoost的方法源自于Friedman的二阶方法。XGBoost在正则化目标函数上做了最小的改进。

2.1 正则化目标函数

对于一个含n个训练样本,m个features的结定数据集:$ D = {(x_i,y_i)} (|D|=n, x_i \in R^m, y_i \in R) $,所使用的tree ensemble model使用K次求和函数来预测输出:

…… (1)

其中,$ F = {f(x)=w_{q(x)}},满足(q: R^m \rightarrow T, w \in R^T) $,是回归树(CART)的空间。q表示每棵树的结构,它会将一个训练样本实例映射到相对应的叶子索引上。T是树中的叶子数每个$ f_k $对应于一个独立的树结构q和叶子权重w。与决策树不同的是,每棵回归树包含了在每个叶子上的一个连续分值,我们使用$ w_i $来表示第i个叶子上的分值。对于一个给定样本实例,我们会使用树上的决策规则(由q给定)来将它分类到叶子上,并通过将相应叶子上的分值(由w给定)做求和,计算最终的预测值。为了在该模型中学到这些函数集合,我们会对下面的正则化目标函数做最小化:

……(2)

其中:$ \Omega(f) = \gamma T + \frac{1}{2}\lambda||\omega||^2 $

其中,$l$是一个可微凸loss函数(differentiable convex loss function),可以计算预测值$\hat{y_i}$与目标值$y_i$间的微分。第二项$ \Omega $会惩罚模型的复杂度。正则项可以对最终学到的权重进行平滑,避免overfitting。相类似的正则化技术也用在RGF模型(正则贪婪树)上。XGBoost的目标函数与相应的学习算法比RGF简单,更容易并行化。当正则参数设置为0时,目标函数就相当于传统的gradient tree boosting方法。

2.2 Gradient Tree Boosting

等式(2)中的tree ensemble模型将函数作为参数,不能使用在欧拉空间中的传统优化方法进行优化。模型以一种叠加的方式进行训练。正式地,$ \hat{y_i}^{(t)} $为第i个实例在第t次迭代时的预测,我们需要添加$ f_t $,然后最小化下面的目标函数:

这意味着,我们贪婪地添加$ f_t $,根据等式(2)尽可能地提升模型。使用二阶近似可以快速优化目标函数。

其中,$ g_i = \partial_{\hat{y}^{(t-1)}} l(y_i,\hat{y}^{(t-1)}) $ ,$ h_i = {\partial}_{\hat{y}^{(t-1)}}^{2} l(y_i, \hat{y}^{(t-1)}) $分别是loss function上的一阶梯度和二阶梯度。我们可以移除常数项,从而获得如下所示的在t次迭代时的简化版目标函数

……(3)

我们定义$ I_j= \{ i | q(x_i)=j \} $是叶子j的实例集合。将(3)式进行重写,并展开$ \Omega $项:

……(4)

对于一个确定的结构q(x),我们可以计算最优的权重 $ w_j^{\ast} $:

……(5)

代入(5)计算得到对应的loss最优解为:

……(6)

等式(6)可以作为一个得分函数(scoring function)来衡量一棵树结构q的质量(quality)。该分值类似于决策树里的不纯度(impurity score),只不过它从一个更宽范围的目标函数求导得到。图2展示了该分值是如何被计算的。

图2:结构得分(structure score)计算。我们只需要在每个叶子上对梯度和二阶梯度统计求和,然后应用得分公式(scoring formula)来获得质量分(quality score)。

通常,不可能枚举所有可能的树结构q。而贪婪算法会从单个叶子出发,迭代添加分枝到树中。假设$ I_L $和$ I_R $是一次划分(split)后的左节点和右节点所对应的实例集合。$ I=I_L \bigcup I_R $,接着,在split之后的loss reduction为:

……(7)

该式通常在实际中用于评估split的候选(split candidates)。

2.3 Shrinkage和列子抽样(column subsampling)

除了2.1节所提到的正则化目标函数外,还会使用两种额外的技术来进一步阻止overfitting。第一种技术是Friedman介绍的Shrinkage。Shrinkage会在每一步tree boosting时,会将新加入的weights通过一个因子$ \eta $进行缩放。与随机优化中的learning rate相类似,对于用于提升模型的新增树(future trees),shrinkage可以减少每棵单独的树、以及叶子空间(leaves space)的影响。第二个技术是列特征子抽样(column feature subsampling)。该技术也会在RandomForest中使用,在商业软件TreeNet中的gradient boosting也有实现,但开源包中没实现。根据用户的反馈,比起传统的行子抽样(row sub-sampling:同样也支持),使用列子抽样可以阻止overfitting。列子抽样的使用可以加速并行算法的计算(后面会描述)。

3.Split Finding算法

3.1 Basic Exact Greedy Algorithm

tree learning的其中一个关键问题是,找到等式(7)的最好划分(best split)。为了达到这个目标,split finding算法会在所有特征(features)上,枚举所有可能的划分(splits)。我们称它为“完全贪婪算法(exact greedy algorithm)”。许多单机版tree-boosting实现中,包括scikit-learn,R’s gbm以及单机版的XGBoost,都支持完全贪婪算法(exact greedy algorithm)。该算法如算法1所示。它会对连续型特征(continuous features)枚举所有可能的split。为了更高效,该算法必须首先根据特征值对数据进行排序,以有序的方式访问数据来枚举等式(7)中的结构得分(structure score)的梯度统计(gradient statistics)。

[算法1]

3.2 近似算法

完全贪婪算法(exact greedy algorithm)很强大,因为它会贪婪地枚举所有可能的划分点。然而,当数据不能整个装载到内存中时,它就变得低效。在分布式设置中也存在相同的问题。为了在两种设置中支持高效地gradient tree boosting计算,需要一种近似算法。

我们总结了一个近似框架(approximate framework),重组了在文献[17,2,22]中提出的思想,如算法2所示。为了进行总结(summarize),该算法会首先根据特征分布的百分位数(percentiles of feature distribution),提出候选划分点(candidate splitting points)。接着,该算法将连续型特征映射到由这些候选点划分的分桶(buckets)中,聚合统计信息,基于该聚合统计找到在建议(proposal)间的最优解

[算法2]

该算法有两个变种,取决于给定的建议(proposal)。全局变种(global variant)会在树构建的初始阶段,建议所有的候选划分,并在所有的层级(level)上使用相同的建议。局部变种(local variant)则在每次划分后重新建议(re-proposes)。比起局部法,全局法需要更少的建议步骤。然而,对于全局建议,通常需要更多的候选点,因为在每次划分之后,不需要重新定义候选。局部建议会在每次划分后重新定义候选,对于更深的树更合适。图3展示了在Higgs boson数据集上不同算法的比较。我们发现,局部建议确实需要更少的候选。如果两者的候选一样多,全局建议比局部建议会更精确。

图3: 在Higgs 10M数据集上的Test AUC收敛比较. eps参数对应于在近似略图(approximate sketch)上的accuracy。这大约可以在proposal中转换成1/eps buckets。我们发现local proposals需要更少的buckets,因为它会重新定义划分候选(split candidates)

大多数分布式tree learning近似算法都遵循该框架。显著的,也可以直接构建近似的梯度统计直方图(approximate histograms of gradient statistics)。也可以使用二分策略(binning strategies)来替代分位数(quantile)。分位数策略(quantile strategy)可以从分布式(distributable)和重计算(recomputable)中受益,详见下一节。从图3中可知,我们发现:给定合理的近似级别(approximation level),分位数策略(quantile strategy)可以获得与exact greedy算法相同的准确率。

对于单机设置,我们的系统高效地支持exact greedy;对于单机和分布式设置,也同时支持带local和global proposal方法的近似算法。用户可以根据需要自由选择。

3.3 加权分位数略图(Weighted Quantile Sketch)

在近似算法中很重要的一步是,提出候选划分点。通常,一个特征的百分位数可以被用来让候选在数据上进行均匀地分布。我们用一个multi-set: $ D_k={(x_{1k}, h_1),(x_{2k},h_2),…(x_{nk},h_n)} $,来表示每个训练实例的第k个特征值以及它的二阶梯度统计。我们可以定义一个排序函数(rank functions):$ r_k=R \rightarrow [0,+\infty) $:

……(8)

它表示相应第k个特征上的输入值小于z的实例的占比。它的目标是,找好候选划分点 $ {s_{k1}, s_{k2}, …, s_{kl}} $,例如:

……(9)

其中$ \epsilon $是近似因子(approximation factor)。直觉上,这意味着大约是 $ \frac{1}{\epsilon} $个候选点。这里,每个数据点通过$h_i$加权。为什么$h_i$可以表示权重呢?我们可以重写(3)式:

它就是真正的加权squared loss,labels为$g_i/h_i $,权重为$h_i$。对于大数据集来说,要找到满足该原则(criteria)的候选集是不容易的。当每个样本实例都具有相同的权重时,有一种已经存在的算法可以解决该问题:分位数略图(quantile sketch)。因而,大多数已存在的近似算法,或者会重新排序来对数据的一个随机子集进行排序(有一定的失败率),或者是启发式的(heuristics),没有理论保障。

为了解决该问题,XGBoost引入了一种新的分布式加权分位数略图算法(distributed weighted quantile sketch algorithm),使用一种可推导证明的有理论保证的方式,来处理加权数据。总的思想是,提出了一个数据结构,它支持merge和prune操作,每个操作证明是可维持在一个固定的准确度级别。算法的详细描述在这里

3.4 稀疏感知的划分查找(sparsity-aware Split Finding)

在许多现实问题中,输入x是稀疏的。有多种可能的情况造成稀疏:

  • 1)数据中的missing values
  • 2)统计中常见的零条目
  • 3)特征工程:比如one-hot encoding

图4: 带缺省方向的树结构。当在split时相应的feature缺失时,一个样本可以被归类到缺省方向上

让算法意识到数据中的稀疏模式很重要。为了这么做,我们提出了在每个树节点上增加一个缺省的方向(default direction),如图4所示。当稀疏矩阵x中的值缺失时,样本实例被归类到缺省方向上。在每个分枝上,缺省方向有两种选择。最优的缺省方向可以从数据中学到。如算法3所示。关键的改进点是:只访问非缺失的条目$I_k$。上述算法会将未出现值(non-presence)当成是一个missing value,学到最好的方向来处理missing values。当未出现值对应于一个用户指定值时,应用相同的算法,可以通过将枚举(enumeration)限定到一致的解上。

[算法3]

据我们所知,大多数已存在的tree learning算法,或者只对dense data进行优化,或者需要指定函数来处理受限的情况:比如对类别编码(categorical encoding)。XGBoost以统一的方式处理稀疏模式。更重要的是,我们的方法充分使用稀疏性,它的计算复杂度与在输入中的未缺失条目(non-missing entries)的数目成线性关系。图5展示了在Allstate-10K数据集上稀疏感知和naive实现间的比较。我们发现,稀疏感知算法比naive版本要快50倍。这证实了稀疏感知算法的重要性。

图5: 稀疏感知算法(sparsity aware algorithm)在Allstate-10K上的影响。数据集很稀疏,主要因为one-hot编码。稀疏感知算法比naive版本(不会考虑稀疏性)要快50倍。

4.系统设计

4.1 用于并行学习的Column Block

tree learning最耗时的部分,是以有序方式获得数据。为了减少排序的开销,我们提出了将数据存储到内存单元(in-memory units)中,它们被称为“块(block)”。每个块中的数据,以压缩列(CSC)格式存储。每列由相应的特征值进行排序。输入数据的布局,在训练前只需要计算一次,在后续迭代中可复用。

在exact greedy algorithm中,我们将整个数据集存储到单个块中,通过对预排序的条目进行线性扫描的方式,来运行split search算法。我们会对所有叶子共同进行split finding算法,因而,在块上的一次扫描,将收集到在所有叶分枝上的划分候选的统计信息。图6展示了,我们如何将一个数据集转成该格式,并找到使用该块结构的最优划分(optimal split)。

图6: 用于并行学习的块结构。块中的每个列通过相应的特征值(feature value)进行排序。在块中的某列上进行一次线性扫描,足够枚举所有的划分点

当使用近似算法时,块结构也有用。这种情况下,可以使用多个块,每个块对应于数据集中行的子集。不同的块可以跨机器分布,或者以out-of-core设置的方式存储在磁盘中。使用排序过的结构,quantile finding步骤会在排好序的列上进行一次线性扫描(linear scan)。这对于局部建议算法(local proposal algorithms)特别有用,局部法的候选集通常在每次划分时生成。在直方图聚合(histogram aggregation)上进行二分查找,也变为一个线性时间的merge style算法。

为每列收集统计信息可以并行化,给定一个并行化算法来处理split finding。更重要的是,列块(column block)结构也支持列子抽样(column subsampling),它可以很容易地在一个块中选择列的一个子集

时间复杂度分析

d为树的最大深度,K为树的总树目。对于exact greedy algorithm,原始的稀疏感知算法的时间复杂度:

这里,我们使用 来表示在训练数据中未缺失条目(non-missing entries)的数目。另一方面,块结构上的tree boosting的开销为:

这里, 是一次预处理开销(one time preprocessing cost),可以分期(be amortized)。该分析展示了块结构可以帮助节省一个额外的$ log n $因子,其中当n非常大时就很大。对于近似算法,使用二分查找的原始算法时间复杂度为:

这里的q是在数据集中建议候选的数目。其中,q通常为32~100之间,log因子仍会引入间接开销。使用块结构,我们可以将时间减小到:

其中B是在每个块中的行的最大数。同样的,我们可以在计算中节约额外的log q因子。

4.2 内存感知访问(Cache-aware Access)

建议的块结构(the proposed block structure)可以帮助优化split finding的计算复杂度,新算法需要通过行索引(row index)间接取得梯度统计(gradient statistics),因为这些值是以特征的顺序被访问的。这是非连续内存访问(non-continuous memory)操作。枚举划分(split enumeration)的naive实现,在累加(accumulation)与非连续内存读取操作(non-continuous memory fetch)间(详见图8),引入了立即读写依存(immediate read/write dependency)。当梯度统计(gradient statistics)不能装载进CPU cache里,或者cache miss发生时,会减慢split finding。

图8: 短范围内的数据依赖模式,由于cache miss,可引起停转(stall)

对于exact greedy algorithm,我们通过内存感知预取(cache-aware prefetching)算法来减缓该问题。特别的,我们在每个thread上分配一个internal buffer,获取gradient statistics存到该buffer中,接着以一种mini-batch的方式来执行累计(accumulation)。这种预取法将直接读/写依存,改变成一种更长的依存,当行的数目很大时可以帮助减少运行时开销。图7给出了在Higgs数据集和Allstate数据集上cache-aware vs. no cache-aware 的比较。当数据集很大时,我们发现exact greedy algorithm的cache-aware实现比naive版本的实现要快两倍。

图7: 在exact greedy algorithm中,cache-aware prefetching的影响。我们发现,cache-miss会在大数据集(1000w实例)上影响性能。使用cache-aware prefetching,可以提升数据集很大时的性能。

对于近似算法,我们通过选择一个合适的块大小(correct block size)来解决该问题。我们将块大小(block size)定义为在一个块中包含样本的最大数目,它会影响梯度统计的cache存储开销(cache storage cost)。选择一个过小的block size会导致每个thread会小负载(small workload)运行,并引起低效的并行化(inefficient parallelization)。在另一方面,过大的block size会导致cache miss,梯度统计将不能装载到CPU cache中。block size的好的选择会平衡两者。我们比较了在两个数据集上的block size的选择。结果如图9所示。结果展示选择在每个块上有$ 2^{16} $个样本时,会对cache property和parallelization做很好的平衡

图9: 在近似算法中,block size的影响。我们发现,过小的块会引起并行化很低效,过大的块由于cache miss会让训练慢下来

4.3 Out-of-core计算

XGBoost的其中一个目标是,充分利用机器资源来达到可扩展的learning(scalable learning)。除了处理器和内存外,很重要的一点是,使用磁盘空间来处理不能完全装载进主存的数据。为了达到out-of-core计算,我们将数据划分成多个块,将每个块存到磁盘上。然而,这不能整体解决该问题,因为磁盘读(disk reading)会花费大多计算时间。减小开销和增加磁盘IO吞吐量很重要。我们主要使用两种技术来提升out-of-core计算。

块压缩(Block Compression) 块通过列(column)进行压缩,当加载进主存时可以由一个独立的线程即时解压(decompressed on the fly)。它会使用磁盘读开销来获得一些解压时的计算。我们使用一个通用目的的压缩算法来计算特征值。对于行索引(row index),我们从块的起始索引处开始抽取行索引,使用一个16bit的整数来存储每个偏移(offset)。这需要每个块有$ 2^{16} $个训练样本,这证明是一个好的设置。在我们测试的大多数数据集中,我们达到大约26% ~ 29%的压缩率。

块分片(Block Sharding) 第二个技术是,在多个磁盘上以一种可选的方式共享数据。一个pre-fetcher thread被分配到每个磁盘上,取到数据,并装载进一个in-memory buffer中。训练线程(training thread)接着从每个bufer中选择性读取数据。当提供多个磁盘时,这可以帮助增加磁盘读(disk reading)的吞吐量。

表1: 主要的tree boosting实现比较

参考

XGBoost: A Scalable Tree Boosting System