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^{hk} $,它可以应用于一个含h个词(word)的窗口(window),来生成一个新的特征(feature)。例如,可以由一个词窗口$ 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:结构分计算。我们只需要在每个叶子上对梯度和二阶梯度统计求和,然后应用得分公式(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

本文主要是结合Jinhui Yuan等人在LightLDA的paper的理解。对于Gibbs sampling可以参见PRML第11章。

1.介绍

主题模型(TM: topic models)使用广泛,许多公司开发了大规模的LDA工具包实现,以适应海量的语料。互联网级别的语料更复杂,为捕获长尾的语义信息(否则将丢失这些主题信息),需要大容量(high-capacity)的主题参数空间,有成千上万的主题数和很大的词汇量。

为应对大规模数据及模型可扩展性,LightLDA实现了一种分布式数据并行策略的LDA(将文档通过workers进行分割,共享所有主题参数)。当然,你也可以使用SparseLDA和AliasLDA的sampler进行算法加速,来进一步降低运行时长。使用1000台机器,就可以使用LDA模型从10亿级别的文档中infer出具有100亿的参数。这个结果是惊人的,但开销很大:例如,一个1000台机器的集群将花费上百万美金(这还不算电费和维护费用)。另外,你可以租用云平台,这样每台机器每小时也要>=1美元,每个月的开销也要>=70w美元。这对于大多说研究者来说是不可行的。

LightLDA提出了一种花费更小的方法来解决这种大规模ML问题,在10台机器级别就能解决该问题。在三个级别上处理该问题:

  • 1.以data-paralled 和 model-paralled方式实现分布式LDA inference:数据和模型会被分区(partitioned),接着跨机器进行流传输(streamed),以便在集群内更有效地利用内存和网络资源。
  • 2.开发了一个Metropolis-Hastings sampler,对每个word/token,允许O(1)的采样时间,这可以在时间上产生一个高收敛率,可以击败当前state-of-art的samplers。
  • 3.使用了一种不同的数据结构,利用海量语料,可以展示高频头部词,也可以展示低频长尾词,以不同的方式存储,有效利用资源,没有性能损失。

使用开源的Petuun framework,我们生成了一种即快又省内存(compute-and memory eficient)的分布式LDA实现:LightLDA。对于上亿的文档(2000亿tokens),它有1万亿的模型参数(1m的主题 x 1m的词汇量),只需要8台标准机器(与云平台常用计算实例配置类似),在180小时内,或者24台机器60小时。对于参数的size,我们的结果是:比文本数据集上大两阶。对于数据的size(data size)至少相当或者比其它大1阶。对于吞吐量(throughput),我们的系统可以在每20-core机器上,每小时采样5000w文档(平均长度为200 tokens)。而PLDA+每机器每小时使用collasped Gibbs sampler只能达到1200个文档;YahooLDA在每8-core机器每小时200w文档。

#

LDA实现分布variational- 和 sampling-based inference算法。LightLDA只关注sampling-based的方法。因为它可以产生非常稀疏的更新,使它们很适合设置很大的主题数K。

最新的large-scale LDA实现需要使用很大的工业级的集群,使用成百上千的CPU core。这些实现需要大集群的原因是:它们使用了SparseLDA inference算法或者 更慢的原始collapsed Gibbs sampler inference算法。这些情况下,inference算法本身是一个限制因素。我们通过开发了一种新的O(1)-per-token Metropolis-Hastings sampler来处理这个瓶颈,它比SparseLDA sampler几乎快一阶——它允许我们在小集群上处理大语料。我们注意到:最新的AliasLDA也提供了一个解法来解决SparseLDA的瓶颈。然而,另一方面,AliasLDA的计算复杂度为O(Kd),因此,并不擅长处理更长的文档(比如网页),因为doc-topic表在初始迭代时是dense的,因此Kd会很大;更一方面,AliasLDA的paper只描述了一种单机实现,它的分布式和可扩展性是不清楚的(特别是考虑到AliasLDA的高空间复杂度,对于每个词的alias table需要O(K))。在本paper中,我们展示了Metropolis-Hastings sampler在单机上在各指标上均快于AliasLDA,这使我们不再考虑使用AliasLDA。

上述提到的large-scala LDA本质上分为:data-parallelism(在机器之间分割文档) vs. model-parallelism(在机器上分割word-topic分布)。YahooLDA[1]和基于parameter-server的实现[11],将word-topic看成是全局共享的,在这种inference算法上,关于如何跨机器进行物理排序word-topic分布是不可知的。更重要的, 它们在token topic索引$ z_{di} $上以文档为中心的方式调度inference计算,因此将它们看成是data-parallel-only的实现。结论是,我们即不希望yahooLDA的实现,也不希望基于parameter-server的实现,来处理非常大的主题模型(1万亿参数)。一旦整个语料在足够多的机器上传输,每台机器的本地文档只有一小部分参与LDA模型,因此,每台机器需要的内存不会太大。这样的设计,如果没有大的计算集群,根本不能处理大的主题模型。

另一方面,PLDA+和Peacock会额外根据词$ w_{di}$ 将token topic indicators $ z_{di} $ 进行分组(group);这是有好处的。因为它会减小word-topic分布(在每个worker机器上持有)的比例——可以有效地在top个data-parallelism上进行model-parallelism。特别的,采用一种grid-like model-paralled分区策略,需要让训练数据、LDA模型和worker机器进行通信(对比我们的设计,这需要额外的开销)。另一点要注意的是在PLDA+的设计中的pipeline,只需要workers在内存中持有模型的一小部分;然而,这样的系统使用了一个过时的,很慢的Gibbs sampler,它们的数据分布和调度对于极大的数据和模型来说不合适。特别的,它的word-bundling策略依靠一个关于训练数据的倒排索引表示,会是文档内存的两倍(这几乎不可承受,因为内存在large-scale LDA中很昂贵)。LightLDA采用了一种不同的data-and-model-paralled策略来最大化地减小内存和CPU开销:我们将word-topic分布以一种结构感知的model-parallel方式进行切分(slice),我们在workers上将文档块固定,所需要的模型参数通过一种异步有界的data-paralled scheme(a bounded-asynchronous data-parallel scheme)传输给它们。这允许我们可以在一个10亿级的文档上,只需要8台机器就可以训练一个1万亿参数的LDA模型。当增加额外的机器时可以获取线性加速。

3.结构感知的模型并行(Structure-Aware Model Parallelism for LDA)

当训练LDA,使用10w个主题可以极大提升所学到的模型——一个原因是,非常大的语料常包含许多小的,但很合适的主题(长尾主题:long tail),当模型只有上千个主题时常检测不到。然而,对于一个达到上百万的主题模型,这会导致word-topic分布包含万亿的参数,因为互联网大语料可以很轻易的包含上百万的唯一词汇。LDA模型在实际中是很稀疏的(许多参数为0),一个上万亿参数的模型比最新的结果要大两阶【12,1,21,11】;事实上,一些已经存在的分布式实现不会扩展到这么大的模型,因为模型需要通过workers进行划分——例如,系统设计需要假设一个worker’s的文档将从不会达到模型的一小部分,但这在一些语料上是不实际的。除了通过worker机器上进行分区外(所有最新的分布式LDA实现都以这种方式),我们必须同时以一种保守的方式对模型进行分区,以确保workers不会耗尽内存。这就是结构感知的model-parallelism。

在我们的model-parallel策略中,我们简单回顾下LDA模型来确定下相关术语。假设在语料中每个文档按以下方式生成:

  • $ \phi_{k} ~ Dirichlet(\beta) $: 为每个主题k抽取词分布$ \phi_{k} $
  • $ \theta_d ~ Dirichlet(\alpha) $:为每个文档d抽取主题分布$theta_d $
  • $ n_d ~ Poisson(\gamma) $:对于每个文档d,抽取长度$n_d$(例如:它包含的tokens数目)
  • 对于每个token $ i \in { 1,2, \cdot, n_d } $:
    • $z_{di} ~ Multinomial(\theta_{di}) $: 抽取token的主题
    • $w_{di} ~ Multinomial(\phi_{z_{di}})$:抽取token的词

对于标准的collapsed Gibbs sampler for LDA,以如下方式表述:除了token的topic indicator $z_{di}$ 外,所有变量都被analytically integrated out,我们只需要根据Gibbs sample $ z_{di} $:

…(1)

其中w是$w_{di}$的简写,$ \hat{\beta} := \sum_{w}\beta_{w}$, $n_{kd}^{-di}$是文档d中分配给主题k的token数(除了token $z_{di}$),$n_{kw}^{-di}$是词w(跨所有文档)被分配给主题k的token数(除了token $z_{di}$)。为了避免昂贵的重新计算开销,这些counts(也被称为是“充分统计(sufficient statistics)”)可以缓存成tables,当一个token topic indicator $z_{di}$更改时会发生更新。特别的,所有count $n_{kd}$的集合口头上指的是document-topic table(作为$\theta_d$的sufficient statistics),而所有counts $n_{kw}$的集合则指的是word-topic table(作为$phi_{k}$的sufficient statistics)。

最小情况下,任何分布式LDA实现必须将token topic indicators $z_{di} $、doc-topic table$n_{kd}$(即data),word-topic table $n_{kw}$(即model)进行分区(partition)。当一个LDA sampler正在采样一个token topic indicator $z_{di}$时,它需要看下在word-topic table(即document)中的第$n_{kw_{di}}$行(row)。然而,原始的分区策略会导致一些机器获取word-topic table的一大块:假设我们按顺序对每个文档的tokens进行抽样,那么该worker必须将根据文档中的词汇看到在word-topic table中的所有行。使用快速的Metropolis-Hastings sampler,每个worker可以每秒抽样成千上万的文档(假设每个文档有成百上千个token);更进一步,我们经验上观察到上百万的文档(web-scale语料会更大)足够激活整个word-topic table。这样,原始的序列只描述了word-topic table在每个worker上进出时的快速交换(swap),会生成一个过高的网络通信开销。

我们的结构感知的model-paralled方法打算解决在fast LDA sampling和每个worker上受限内存空间之间的矛盾;这受到块坐标下降算法(block coordinate descent algorithms)的启发。数据块在运行LDA sampler前生成,我们注意到,在每个块上实例化词汇表中的词汇开销很小。该信息绘作为meta-data绑定到块(block)上。如图1所示,当我们加载一个数据块(和它的meta-data)到本地内存(红色的正方形)时,我们从块中的本地词汇(local words)选择一小部分词集合(图中的V1)。这词集足够小,根据在word-topic table中的第$\n.,w_{di}$行,可以存储在worker上的本地内存中——我们将这些行集合称为一个模型切片(“model slice”)。我们的系统会通过网络获取(fetch)model slice,sampler则只对块中的这些tokens进行抽样,它们可以被获取到的切片覆盖到;所有的其它tokens将不会接触到。这种方式下,系统只需要在本地内存中维护一个瘦模型切片(thin model slice),在当前数据块中对所有文档可复用。一旦由slice所覆盖的所有tokens被抽样到,系统会通过网络获取(fetch)下一个model slice(称为V2),对由它覆盖到的tokens进行抽样处理。这种方式(类似于TCP/IP协议或图像处理中的滑动窗口),系统会处理一个数据块中的所有tokens,在从磁盘中加载下一个块之前,一次一个slice。这种和磁盘交互的块交换(swapping of blocks)可以进行核外执行(out-of-core execution).

图1: LDA中的: Structure-aware model parallelism

除了可以让worker保持低内存需求外,结构感知的模型并行(structure-aware model parallelism)可以以如下方式缓和网络开销瓶颈:

  • 1.workers不会移到下一个model slice,直到当前slice上相应的所有tokens都被抽样到,我们不需要对模型应用caching和eviction策略。
  • 2.因为data-model切片是静态的、不可变更的(static and unchanging),我们将它们的加载(loading:从磁盘中读取数据块,从中心parameter server获取模型)进行pipeling,来隐藏网络通信延迟。

最后要注意一点,structure-aware model parallel策略会“发送模型给数据:(sends the model to the data)”,而非相反。这受两点启发:

  • 1.数据(the data)(包含tokens $w_{di}$和相应的topic indicators $ z_{di} $)比模型(the model)更大(模型有万亿参数)
  • 2.sampler收敛,模型会更加稀疏(这样可以减少网络通信),而数据的大小仍然是常数。

我们观察到其它分布式LDA的设计采用的是“发送数据给模型(send data to model)”的策略,这会开销更大。

4.LDA的Fast Sampling算法

structure-aware model-parallelism的目的是:在小集群上,从十亿级别的文档中学到非常大的,上万亿参数的LDA模型;更进一步,bounded-asynchronous data-parallel schemes可使用parameter servers来减小网络同步和通信的开销。然而,这些还不能让大的LDA模型快速地进行训练;这激发了我们更大的贡献:一种新的LDA sampling算法,它比最新的算法(SparseLDA和AliasLDA)收敛地更快。为了解释我们的算法,先简单回顾下SparseLDA和AliasLDA的机制。

SparseLDA

SparseLDA使用这样的观测:

  • 1.大多数文档只有少量的主题
  • 2.大多数词汇只参与少量的主题

这表现为doc-topic和word-topic table同时具有稀疏性(sparsity),其中SparseLDA通过将 collapsed Gibbs sampler的条件概率(等式1)分解三个terms:

…(2)

第一部分为r,第二部分为s,第三部分为t。当Gibbs sampler接近收敛时,第二项s和第三项t会变得很稀疏(因为文档和词被安排到少量的主题上)。SparseLDA首先抽样三个项r,s,t中的其中之一,根据它们在k个可能结果上的概率求和,接着,SparseLDA会其于选中的r,s,t中的某项来抽样主题k。如果s或t被选中,那么抽样的主题k会各自花费$O(K_d)$或$O(K_w)$的时间,其中$K_d$是文档d所包含的主题数,而$K_w$是词w所属的主题数。折算下来SparseLDA的抽样复杂度为$O(K_d+K_w)$,而对于标准的collapsed Gibbs sampler只有O(K)。

AliasLDA

AliasLDA提出了另一种的Gibbs sampling probability分解:

…(3)

第一项为u,第二项为v,AliasLDA会预先为第二项v计算一个alias table,它允许在O(1)时间内通过Metropolis-Hastings被抽样到。通过在许多tokens上复用该table,构建该表需要O(K)的开销,折算下来每个token需要O(1)的开销。第一项u是稀疏的(在$K_d$上线性,即在文档d上的当前主题数),可以在$O(K_d)$时间内被计算。

4.1 Metropolis-Hastings sampling

我们看到,折算成每个token所需要的抽样时间,SparseLDA和AliasLDA达到了$O(K_d+K_w)$和$O(K_d)$。这样的加速抽样是很重要的,因为我们可以简化;原始的collapsed Gibbs sampler (Eq. 1)对于每个token需要O(K)的计算开销,这在K=100w个主题上明显是棘手的。SparseLDA减小了sampling的复杂度,通过利用稀疏性,而AliasLDA则利用alias方法以及Metropolis-Hastings算法。LightLDA sampler也使用Metropolis-Hastings,但对于合适的分布式设计有新的见解,这对于高性能表现来说相当重要。我们展示了sampling过程可以被加速,更进一步,使用设计良好的proposal distribution q(·)给true LDA posterior p(·)。

一个A well-designed proposal q(·)可以以两种方式加速sampling过程:

  • 1.从q(·)中抽取样本,比从p(·)中抽取样本更便宜
  • 2.Markov chain可以快速混合(只需要一少部分step)

这涉及到如何为p(·)构建一个良好的q(·)?如果q(·)与p(·)非常相似,那么构建的Markov chain会快速混合——然而,从q(·)中抽样的开销会和从p(·)的抽样一样昂贵。相反地,如果q(·)与p(·)非常不同,我们可以从中抽样的开销会更小——但这种构建的Markov chain的mix会过慢,需要许多步才会收敛。为了理解这种trade-off,需要考虑下面的临界情况:

  • 均匀分布Proposal(Uniform Distribution Proposal): 假设我们选择了q(·)作为均匀分布。MH算法会提出:下一状态 t ~ Uni f(1,…,K) ,并接受$min(1, \frac{p(t)}{p(s)}$的概率的状态。很明显,从一个均匀分布中进行sampling是开销很小的,可以在O(1)时间内完成;然而,均匀分布是非稀疏的,因此与p(·)会相当远,它需要多步的MH来进行mix。

  • 完全条件分布Proposal(Full Conditional Distribution Proposa):我们可以选择p(·)作为proposal分布q(·)。MH算法提出了下一步t的概率为p(t),接受$ min{1, \frac{(p(t))p(s)}{p(s)p(t)}=1 $;例如:算法会接受所有的proposals。从q(·)中抽样很明显开销与p(·)一样多,但mixing很很快,因为所有的proposals都被接受了。

4.2 因子分解(Factorization)的Cheap Proposals

为了设计一个开销很小的MH算法,它具有高的mixing rate,我们采用了一个因子分解的策略(a factorized strategy):我们只构建了一个O(1) proposals的集合,选在它们之间做交替选择。为了构建这样的proposals,我们从关于token topic indicator $z_{di}$的真实条件概率(true conditional probability)开始:

…(4)

观察到,它可以分解成两项:

…(5)

第一项为doc-proposal,第二项为word-proposal。即使我们利用这两项的稀疏性,从该条件概率中抽样的开销至少要$ O(min(K_d,K_w)) $——我们是否可以做的更好呢?我们观察到,第一项是依赖文档的(document-dependent),也词汇独立的(word-independent),而第二项是文档独立的(document-independent)、依赖词汇的(word-dependent)。更进一步,它直觉上可看到,最可能的主题是从doc-dependent项和word-dependent项上那些高概率的部分;然而,单独的项可以作为一个好的proposal q——但如果p在主题k上具有高概率,那么这一项也可在k上具有高概率(倒过来不正确)。重要的是,alias方法(在AliasLDA中使用的)可以应用于两项,减少从这样的proposal中抽样的开销至:分摊下来,每token的时间复杂度O(1)。下面分别讨论下两种proposal。

Word-Proposal for Metropolis-Hastings

将$p_w$定义成word-proposal分布:

…(6)

状态转移s->t的接受概率(aceptance probability)为:

…(7)

假设$\pi_w := \frac{p(t)p_w(s)}{p(s)p_w(t)}$,我们可以展示成:

…(8)

一旦$t ~ p_w(t)$被抽样到,接受概率可以在O(1)时间内被计算,只要我们根据所在的sufficient statistics n。在抽样期间。直觉上,$\pi_w$是很高的(相对于topic s),不论何时proposed topic t在文档中内很流行,或者对于词w来流行。因为word-proposal趋向于提出主题t,对于词w很流行,使用word-proposal将会探索p(k)的状态空间。为了在O(1)内抽样$p_w$,我们使用类似于[10]的alias table。如图2所示,alias方法的基本思想是,将一个非均匀的分布转化成一个均匀的分布(例如:alias table)。因为alias table会在MH sampling中复用,转称的开销可以分摊到O(1).

尽管alias方法具有O(1)的分摊时间复杂度,它的空间复杂度仍然很高,因为每个词的proposal分布的alias table会存储2K个值:每个二元(bin)的分割点和分割点上的alias value。如果我们需要存储许多词的alias table,这是禁止的。我们的见解是:alias table可以稀疏化,我们可以通过将$p_w=\frac{n_{kw}}{n_k+\beta}+\frac{\beta_w}{\n_k+\beta}$开始。接着抽取两项中的其中之一,我们使用一个预先构建的alias table(从$n_{kw}$中创建,指向于词w)中选中一个主题,它是稀疏的。如果我们抽取第二项,我们也用一个预先构建的alias table(从$n_k$中创建,对于所有词w是共用的,可为所有V个词分摊)来选中一个主题,它是dense的。这种方式下,我们将构建词w的alias table所需的时间复杂度和空间复杂度减小到:$O(K_w)$(词w所参与的主题数)

Doc-Proposal for Metropolis Hastings

将$p_d$定义成doc-proposal分布:

…(9)

s->t状态转移的接受概率为:

…(10)

假设$\pi_d := \frac{p(t)p_d(s)}{p(s)p_d(t)}$,我们可以展示为:

…(11)

至于word-proposal,我们看到:doc-proposal满足,在任何时候主题t(相对于主题s)在文档d内是流行的,或者对于词w。我们将$p_d(k) \propto \frac{n_{kd}}{n_d+\alpha}+\frac{\alpha_k}{n_k+\alpha}$分解成类似于word-proposal的结构,当我们选择第一项时,我们不需要显式构建alias table——这是因为document token topic indicators $z_{di}$可当成是一个alias table。特别的,第一项$n_{kd}$会统计主题k在文档d内的次数,换句话说:

…(12)

其中[·]是一个指示函数。这暗示着,对于未归一化的概率分布$n_{kd}$来说,数组$z_{di}$是一个alias table,因此我们可以简化为:通过一个整数j非均匀地从{1,2,…,nd}中抽取一个整数$n_{kd}$,并设置为:$z_{di}=z_{dj}$。图3使用了一个toy example来展示该过程。因而,我们可以下结论:doc-proposal可以在O(1)的非分摊时间中被抽样(因为我们不需要构建一个alias table)。

4.3 结合proposals提升Mixing

不管doc-proposal,还是word-proposal,可以被独立用于LDA中一种有效的MH算法,实例上,许多MH-steps(为每个token重复抽样)需要生成合适的mixing。只需一少部分的MH-steps,单独使用word-proposal可以支持word-topic分布中的稀疏性(例如:每个词都属于很少的主题),但会在document-topic分布中引起很低的稀疏性(例如:每个文档包含了多个主题)。相反地,单独使用doc-proposal,只需要少量的MH-step就会导致在document-topic分布上的稀疏性,同时产生非稀疏的word-topic分布。因此,这种proposal可以很快地对tokens进行抽样,它们需要许多MH-steps来进行很好的混合(mix)。

快速Metropolis-Hastings mixing的关键是,一个proposal分布可以快速探索状态空间,并达到具有高概率(the models)的所有状态。word-proposal的$p_w(k)$擅长于proposing自己的模式(会在少量主题上产生词的聚集),并同样为doc-proposal $p_d(k)$进行proposing。如图4所示,单独使用word-proposal或doc-proposal,一些模式(modes)将从不会被快速探索到。

当仍然维持较高的sampling效率时,我们如何来达到一个更好的mixing rate?如果我们看一下$p(k) \propto p_w(k) x p_d(k) $,我们会看到:对于p(k)会很高(例如:一个mode),我们需要:$p_w(k)$或$p_d(k)$要足够大——但不需要同时满足。然而,我们的解决方案是:将doc-proposal和word-proposal结合成一个“cycle proposal”:

…(13)

对于每个token,通过我们构建一个MH序列,

5.对头部词(Power-Law Words)采用混合数据结构

即使是data-model分区,当对于非常大的主题数的LDA时,内存大小仍然是一个障碍。LDA模型,或者是word-topic table$ n_{kw} $,是V X K的矩阵,交且一个naive dense representation版本,会需要过高的内存——例如,对于本试验中所使用的V=K=100w,考虑32-bit的整数条件,模型需要4T字节的size。即使用合理的配置高的机器,128G的RAM,也只能需要32台机器来在内存中存储矩阵——实际上,实际的使用可能会更高,因为存在其它系统开销(比如:cache, alias tables, buffers, parameter server)。

一个常用的解决方法是,将sparse数据结构转换成:hash maps。在稀疏存储背后的原理是,文档词汇会遵循长尾分布(power-law)图5所示。有两个暗示:

  • 1)在移除stop-words如果看,所有有意义的词汇的词汇几乎会超出32-bit integer的范围(2,147,483,647);这在150亿文档和3w亿tokens,只保留300词频上的web-scale语料上测试时,会超过32-bit的限制。出于这个原因,我们选择使用32-bit的整数,而非64位。
  • 2) 即使有数十亿的文档,大多数词的出现次数要少于K次(其中K是主题数,在我们的试验中达到了100w)。这意味着大多数行$n_k$,在word-topic table中是相当稀疏的,因此一个稀疏行表示(hash maps)将极大减小内存占用(memory footprint)。

然而,对比于dense arrays,sparse的数据结构表现出较差的随机访问表现,它会伤到MCMC算法(比如:SparseLDA,AliasLDA以及我们的r Metropolis-Hastings算法),因为它们所有都很严重地依赖于随机访问索引。在我们的试验中,对比于dense arrays,使用纯hash maps会导致一个serveral-fold表示的丢失。当维持高的sampling throughput时,我们怎么才可以享受低内存占用?我们的解决方案是混合数据结构(hybrid data structure),其中,word-topic table的行对应于频繁出现的热词,用dense arrays进行存储;而对于非常见的长尾词,则使用开放寻址/二次探测(open-addressing/quadratic-probing)的hash tables。在数十亿级别的web-scale的语料上,我们发现词汇表中10%的词是热词(“hot”),会覆盖95%的语料中的tokens,而剩余90%的词汇表词则是长尾词,只会覆盖5%的tokens。这暗示着:

  • (1)大多数会访问我们的混合word-topic table中的dense arrays,这会保持高的throughput
  • (2)word-topic中的大多数行仍是稀疏的hash tables,它可以让内存占用量合理保持较低水平

在我们的V=K=100w的试验中,我们的混合word-topic table只使用0.7TB,如果我们使用纯dense arrays会达到4TB。当该表跨24台机器分布时,每台机器只需要30GB,可以空出昂贵的内存来给其它系统组件用。

6.系统实现

分布式实现对于web-scale的数据来说是令人满意的:它们会将训练时间减少到可承受的水平,大多数实践者会访问至少一台分布式集群。然而,目前存在的分布式LDA实现,只展示出在小问题规模上(特别是模型size)工作良好,或者使用极大的计算集群(有时上千台机器)来完成可接受时间内的训练。如何使用数十台机器来应对和解决大的LDA问题?如果我们希望使用数十亿的训练语料(每个文档至少上百tokens)会占用数T空间,那么在data-paralled的这一点上,简单地从磁盘拷贝数据到内存中都会花费数十小时,当将数据通过网络进行传输时也会花费类似的时间。在model-paralled这一点上,存储1T的参数(100w词 x 100w主题)可以达到上T的内存——只能分布式存储,需要跨机器的参数同步,会有很高的网络通信开销。根据这些注意点,为LightLDA设计了一个架构,它可以将数据传输和参数通信开销尽可能地减少,并让小集群实现成为可能。

系统总览 在开源分布式机器学习Petuum上构建了LDA,对于大规模机器学习,它为结构感知的模型并行(structure-aware model parallelism)以及有界异步数据并行(bounded asynchronous data-parallelism)提供了一个总的框架。根据代码,我们会利用parameter server来实现有bounded asynchronous data-parallelism。一个parameter server对用户会隐藏分布式网络细节(通信和并发控制 ),提供好用的API来开发分布式机器学习程序——该思想让机器学习专家专注于描述算法逻辑,而非系统的细节。我们首先引入总的parameter server的思想,接着描述我们如何让大的LDA模型在小集群上进行增强。

Parameter Server和Data Placement 在基本水平上,一个parameter server(PS)会保存一个分布式共享内存接口[16],其中编程者可以从任何机器上访问内存,对于参数的物理位置不可知。本质上,PS扩展了在单个机器上的内存结构(如图6);存储介质越接近CPU core,越具有较低的时延和较高的传输带宽,但有更少的容量(capacity)。在PS架构上,每个机器的RAM被分成两部分:对于客户端(client)使用的局部RAM,以及对于中心化参数存储的远程RAM(也称为:“server” part)。这样的硬件限制,以及由大的主题模型数据模型引入的需要条件,强烈地影响着我们运行Metropolis-Hastings算法的方式。

我们使用PS来存储两种类型的LDA模型参数:word-topic table $ { n_{kv} }{k=1,v=1}^{K,V}$,它会统计词v分布给主题k的tokens数,一个长为K的“summary row”:$ { n_k }{k=1}^{K} $,它会统计分配给主题k的总tokens数。32-bit的整数可以被用于word-topic table(使用一个dense arrays和sparse hash maps的组合),而对于summary row则使用一个64-bit的整数数组。我们观察到,随着LDA sampler的处理,word-topic table会变得进一步稀疏,随着时间推移会产生更低的网络传输开销。更进一步,Petuum PS支持一个bounded-asynchronous consistency model,它可以减少内部迭代(inter-iteration)参数同步时间,通过一个过时的参数s——对于LightLDA,它已经是一个pipeline的设计,我们发现最优值为:s=1.

如果输入数据比模型大(仍保留不变的throughout LDA接口),通过网络进行传输数据是不明智的。相反地,我们会进行shuffle,跨所有worker机器的磁盘共享语料,每个worker只在它的本机磁盘上访问数据。在图6中,$ { w_{di}, z_{di} }_{d=1,i=1}^{D_n,n_d} $表示在第n台worker上的一份训练数据的shard,其中$D_n$表示第n台worker上的文档数,$n_d$表示在文档d上的tokens数。每个worker的本地内存会持有:

  • (1)当前活动的工作数据集$ { w_{di}, z_{di} }{d=1,i=1}^{D{S_n,n_d}} $
  • (2)模型$ { n_{kv} }{k=1,v=1}^{K,V_s} $需要抽样tokens的当前集合(使用Metropolis-Hastings sampler)。在抽样期间,我们更新token topic indicators $z{di}$,以及word-topic table。token-topic pairs($w_{di}, z_{di}$)位于本地worker上,不会有网络通信,而word-topic table则被存储在PS中,因而需要一个后台线程来进行有效通信。

Token 和 Topic Indicator Storage 作为data-parallel执行的一部分,每个worker机器会在本地磁盘上存储语料的某个shard。对于web-scale级别的语料,每个shard仍会很大——如果没有许多T,也会有数百G——它不会将整个shard加载进内存中。这样,我们进一步将每个数据的shard分割成数据块(data blocks),并将这些块同时流式化进内存中(见图1左)。根据数据结构,我们故意将tokens $w_{di}$和它们的topic indicators $z_{di}$进行side-by-side放置,作为一个$(w_{di}, z_{di})$ pair的向量(vector),而非两个独立的tokens和topic indicators数组。我们这么做是为了提升数据的locality和CPU cache更有效:无论何时当我们访问一个token $ w_{di} $时,我们总是需要访问它的topic indicator $z_{di}$,vector-of-pairs的设计方式可以直接提升locality。这种设计的一个缺点是:额外的磁盘I/O,每次读/写 tokens $w_{di}$一个数据shard到磁盘中时会swap out。然而,磁盘I/O总是通过对读/写进行pipeline的方式进行masked,当sampler正处理当前shard时会在后台完成。

我们指出,我们的streaming和disk-swapping(out-of-core)设计,天然的会以如下的方式支持容错:如果我们通过原子文件重写来执行一个data swapping到磁盘,接着当系统发生失败时,它会简单地通过warm-start来进行resume训练过程:读取swapped-to-disk模型,re-initialize word-topic和doc-topic table,继续。作为比较,像PLDA+和YahooLDA也具有容错机制,它们需要周期性地将数据和(或)模型进行dump出来——但这在大数据/模型的情况下会引发不平凡的开销。

对结构感知的模型并行进行tuning 我们在第3部分引入了Structure-Aware Model Parallelization的高级思想并应用到LDA中,仍有许多改进来提升效果。我们描述了最重要的几点:

  • 1.在计算一个数据块或一个模型切片时,一个worker的CPU core需要等待下一个数据块/模型切片从磁盘/网络被加载。我们通过pipelinging(如图7所示)消除了该I/O延迟,尽管我们注意到:执行pipelining需要很仔细的参数配置(samplers的throughout,数据块的size,模型切片的size等)
  • 2.为了阻止数据加载在跨模型切片时的imbalance,我们通过对词汇表通过词频进行排序来生成模型切片,接着对词汇进行shuffing。这种方式下,每个切片会同时包含热词(hot words)和长尾词(long tail words),来改善加载的平衡。
  • 3.为了消除数据传输的不必要性,当生成数据块时,我们对token-topic pair $w_{di}, z_{di}$根据$w_{di}$在重排后(shuffled)的词汇表中的位置进行排序,确保属于相同的模型切片的所有tokens在数据块上实际是连续的(见图1)。这种排序只需要执行一次,在数据处理平台如Hadoop上会很快(对比于LDA sampling time)。我们认为:比起PLDA+中的”word bundle”,这种方式更有效,PLDA+会用一个倒排索引来避免数据传输,但会带来两倍的内存开销。

多线程的效果 我们的sampler在单个worker上会并行。通过将内存中的数据块分割成不相效的部分(通过独立线程进行抽样),并在线程间共防震内存中的模型切片。再进一步,我们会让shared模型切片变得immutable, 在将这些数据汇总发送到parameter server之前,会在本地延迟所有的模型更新。通过将模型切片保持immutable状态,我们避免了并发问题(比如:条件竞争和锁),这样就可以达到在接近线性的intra-node扩展性。当模型更新延迟时,理论上会减慢模型的收敛率(convergence rate),实际上,它会消除并发问题,增加sampler throughput,轻易地胜过更慢的收敛率。

现代的server级机器包含了许多CPU sockets(每个CPU有许多物理core),可以连接到不同的内存条(memory banks)上。当这些内存条可以被所有CPU寻址时,当访问绑定到另一socket上的远端内存条时,内存延迟会更长——也是就是:Non-Uniform Memory Access (NUMA). 在我们的实验中,通过对sampling参数进行调整(比如:f Metropolis-Hastings steps数),我们对它们进行部分寻址,发现NUMA的作用相当大。也就是说,我们相信,合适的NUMA-aware编程是一个更好的长期解决方案来解决该问题。最终,我们注意到:为每个线程设置core的关系,在intel处理器上开启硬件超线程(hardware hyper-threading)效果很好,我们观察到一个30%的性能增益。

7.试验数据

对比之前的LDA实现,我们展示了:只需要更少的机器,LightLDA可以调练更大的LDA模型——这归因于data-model的分片,特别是新的Metropolis-Hastings sampler,它比SparseLDA和AliasLDA要快一阶。我们使用许多数据集(表7),注意,Bing的”web chunk”数据集有12亿的网页(共2000亿的tokens)。我们的试验表明:

  • (1)在core数目和机器数目上,我们的分布式实现有接近线性的可扩展性
  • (2)比起state-of-art的SparseLDA和AliasLDA samplers,我们的分布式实现有接近线性的可扩展性(在单线程设置中测量得到)
  • (3)最重要的是,LightLDA可以允许很大的数据size和模型size,只需要8台左右机器即可。

参考

LightLDA: Big Topic Models on Modest Compute Clusters

最新一朋友在做比特币矿池方向的创业,受邀请帮忙研究下运营矿池的破产概率问题,以尽可能地规避风险。下面会将相应的一些概念与问题一一道来。

1.泊松分布与挖矿问题

泊松分布

  • 泊松分布适合于描述单位时间内随机事件发生的次数。
  • 泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生率。
  • 泊松分布的期望和方差均为λt.

1.1 问题

比特币挖矿的数目服从泊松分布。

这是为什么?且细细看来。

  • 1.btc挖矿机的一次计算是否产生一个合法区块可以认为是一个随机事件,任何所有的计算hash彼此相互独立。

  • 2.每次hash计算有对应的计算难度,标为D,决定着发现一个合法块的难度。

  • 3.每次hash计算(32位hash计算,共有1/2^32个hash值)都会有 $ \frac{1}{2^{32}D} $的概率产生一个合法区块。

  • 4.矿工的算力(hashrate:每秒计算hash的次数):h

ok,这个问题可以化简为:

t时间内,该算力的矿工可以挖到多少btc区块?它服从什么分布?

1.2 解释

ok,很明显,速率问题,泊松分布.

速率λ(即:每秒能挖到多少个区块)为:$ \lambda=\frac{h}{2^{32}D} $

  • 单人在t时间内挖到的区块数目期望:$ E(X)=\lambda t=\frac{ht}{2^{32}D} $
  • 单人在t时间内挖到的区块数目方差:$ D(X)=\lambda t=\frac{ht}{2^{32}D} $

另外,还有一个条件:即一个合法区块对应着B个btc。换算成btc的话,这一个常数项的线性变换,即是一个POI(BX)的问题.

根据期望和方差的性质:

  • C为常数,X为随机变量
  • 期望性质:$ E(CX)=CE(X) $
  • 方差性质:$ D(CX)=C^{2}D(X), D(X+C)=D(X) $

从而,我们得到:

单人在t时间内对应回报的期望为:$ E(BX)=BE(X)=\frac{htB}{2^{32}D} $

单人在t时间内对应回报的方差为:$ D(BX)=B^{2}D(X)=\frac{htB^{2}}{2^{32}D} $

单人在t时间内对应回报的标准差为: $ \sigma(BX)=\sqrt{D(BX)}=\sqrt{\frac{htB^{2}}{2^{32}D} $

单人在t时间内对应回报的标准差/期望(标准差是期望的多少倍)为: $ \frac{\sigma(BX)}{E(BX)}=\sqrt{\frac{2^{32}D}{ht}} $

1.3 进一步

矿池挖矿模式与单人solo挖矿模式略有不同:

  • 1.它集合了矿池内所有矿工的算力:其hashrate为:H

矿池将在周期t内获得的区块数同样服从泊松分布(为做区分,此处为随机变量Y)。修改一下算力,得到相应的期望/方差:

矿池将在周期t内获得的区块数期望:$ E(Y)=\frac{Ht}{2^{32}D} $

矿池将在周期t内获得的区块数方差:$ D(Y)=\frac{Ht}{2^{32}D} $

将区块数换算成btc,对应的期望/方差:

矿池在周期t内获得的btc期望:$ E(BY)=\frac{HtB}{2^{32}D} $

矿池在周期t内获得的btc方差:$ D(BY)=B^2D(Y)=\frac{HtB^2}{2^{32}D} $

那么在矿池中,单个矿工的收益又是肿么样的一个期望/方差呢?

这里又有另外一项变换:单个矿工的hashrate为:h=qH(其中:q是该矿工对该矿池中总算力的贡献,0<q<1)

根据期望/方差性质,再做一次换算:

在矿池中,个人在周期t内获得的btc期望: $ E(X)=E(qBY)=qE(BY)=\frac{qHtB}{2^{32}D}=\frac{htB}{2^{32}D} $,该值与solo模式一样

在矿池中,个人在周期t内获得的btc方差:$ D(X)=D(qBY)=q^{2}D(BY)=\frac{q^{2}HtB^2}{2^{32}D}=\frac{qhtB^2}{2^{32}D} $,是solo模式的q倍。(0<q<1,因而方差变小,风险也变小了)

2.矿池如何实现收支平衡?

2.1 一般的矿池

矿池通常由一个矿池运营者(pool operator)来维护,它会在相应的服务上花费一定的费用。这通常是区块回报的一个固定百分比:f。因此,对于每个发现的区块,operator都将收到一笔fB的费用,余下的(1-f)B将分配给矿工。

再做一次变换,利用期望/方差的性质:

矿池中,单个矿工获得的的实际btc收入的期望为:$ E(X)=E((1-f)qBY)=(1-f)E(qBY)=\frac{(1-f)htB}{2^{32}D} $,与solo模式略有下降(但其实个人挖一样需要支付电费等问题存在)

矿池中,单个矿工获得的的实际btc收入的方差为: $ D(X)=D((1-f)qBY)=(1-f)^{2}D(qBY)=(1-f)^{2}q\frac{htB^2}{2^{32}D} $,是solo模式的(1-f)^2q倍. 方差更小。

2.2 变态的矿池

PPS矿池就是这样。

只要挖,不管有没挖到,在周期t时间里,矿工都会有收入。

在矿池中,单个矿工的收入的方差为0。operator承担所有的方差,风险更大,因而需要对operator再做一定的补偿。如果operator不正确平衡矿池的费用以及他的财产准备金,矿池有很大可能会破产。

这里有两个问题:

  • 补偿方式有变化?
  • 在有限资源的情况下,准备金至少需要多少,才能让破产机率更低?

先回到原先讲的:

  • 1.矿池中每次hash计算成为一个share的概率:$ \frac{1}{2^{32}} $
  • 2.每个share成为合法区块都有一个概率:$ p=\frac{1}{D} $
  • 3.矿工在每次提交一个share时将平均接收到的回报:pB
  • 4.对于operator则收到的费用: $ (1-f)pB $

2.2.1 推导阶段一

如何分配它?

这里,每次提交share可以当成一个step。在这个周期t内,计算出来的share本身有两个状态:合法(可得到btc)、非法(无效计算,得不到btc)。合法的概率为p,非法的概率为:1-p。

如果合法,则获得B个btc。然后拿出(1-f)pB进行分配给矿工,剩余的归operator自己。如果非法,那就没有收入了,但仍要拿出(1-f)pB进行分配给矿工。这是一个典型的连续时间随机过程,可以用马尔可夫链来表示。一个周期间,operator所得到的收入(包括损失):

$ X_{t+1}-X_{t}={ \begin{aligned} &-(1-f)pB+B & w.p. & & p \ &-(1-f)pB & w.p. & & 1-p \end{aligned} $$

它的期望为:

同理使用方差计算公式可得,真实的方差为:$ p(1-p)B^{2} $ ,而btc矿池paper将它近似认为:$ pB^{2} $,这里有些疑问(只有当p的概率较大时,才有可能近似)。

根据中心极限定理可知(这一步有待进一步求证),长期行为服从$ (fpB, p(1-p)B^{2}) $的正态分布。而这面的这个随机过程正好服从该分布(期望/方差一致),因而可以近似等价为:

我们再对这个初始条件按因子$ \sqrt{p}/B $做一下缩放:

这样缩放的好处,对后面推导有利。每次输赢为常量(f恒定, p恒定)。

2.2.2 推导阶段二

剩下的问题,其实就等价于随机过程中马尔可夫链的经典问题:《赌徒输光问题》。

$a_n$表示,从状态n开始要达到0的概率(表示矿池破产)。我们在第一步得到的条件,表示:$q=(1+f\sqrt{p})/2 $

这个随机过程可以表示为:

可以用常系数齐次线性方程求解该多项式特征方程:

该方程的解为:

整个特征方程,它的通解形式为:

代入初始值(边界条件):$a_0=1,a_{\infty}=0 $

即:A=0, B=1,得到$ a_n $:

如果operator以一个R的话准备金启动,矿池的破产概率为:

相反地,为了维持一个破产概率最大为$ \delta $,矿池应至少保有准备金:

参考:

1.Analysis of Bitcoin Pooled Mining Reward Systems. Meni Rosenfeld

我们都清楚word2vec,这是Deep NLP最基本的任务。对于词有词向量,对于句子,或者是段落,也一样可以生成相应的向量(注意:两者的向量空间是不一样,不能合在一个空间中)。paragraph2vec在[1]有详细介绍,我们先来看下具体的概念:

1.PV-DM:(Paragraph Vector:Distributed Memory model)

受词向量(word vector)方法的启发,我们也学习到段落向量(paragraph vector)。词向量会被用于预测句子中的下一个词。因此,尽管实际上词向量的初始化是随机的,它们仍可以捕获语义,作为预测任务的间接结果。我们在paragraph vector中使用相类似的方式。在给定从段落中抽样获取多个上下文的情况下,也可使用paragraph vector来预测下一个词。

在我们的Paragraph Vector框架中(见图2), 每个段落(paragraph)都被映射到一个唯一的vector中,表示成矩阵D中的某一列;每个词(word)都映射到一个某一个向量中,表示成矩阵W中的某一列。对paragraph vector和word vector求平均,或者级联(concatenated)起来,以预测在上下文中的下一个词。在该试验中,我们使用级联(concatenation)作为组合向量的方法。

图2: 学习paragraph vector的框架。该框架与word2vec的框架相似;唯一的区别是:会有额外的paragraph token通过矩阵D映射到一个vector中。在该模型中,对该向量以及再带上一个三个词的上下文,对它们进行级联或者求平均,用来预测第4个词。paragraph vector表示从当前上下文缺失的信息,可以看成是关于该段落(paragraph)的主题(topic)的记忆单元。

更正式的,在模型中与词向量框架的唯一变化是,h是从W和D中构建的。

paragraph的token可以认为是另一个词。它扮演的角色是,作为一个记忆单元,可以记住当前上下文所缺失的东西–或者段落(paragraph)的主题。出于该原因,我们经常称该模型为Paragraph Vector分布式记忆模型(PV-DM:Distributed Memory Model of Paragraph Vectors)。

上下文是固定长度的,从沿段落(paragraph)滑动的一个滑动窗口中采样。所有在相同段落(paragraph)上生成的上下文,共享着相同的paragraph vector。在不同的段落(paragraphs)间,则共享着相同的词向量矩阵W,比如,单词”powerful”的向量,对于所有段落(paragraphs)是相同的。

Paragraph Vectors和Word Vectors都使用SGD进行训练,梯度通过backpropagation算法求得。在SGD的每一步,你可以从一个随机paragraph中抽样一个固定长度的上下文,计算error的梯度,更新模型参数。

在预测阶段,对于一个全新的段落(paragraph),需要执行一个推断步骤(inference)来计算paragraph vector。这也可以通过梯度下降法获取。在该步骤时,对于模型其余部分的参数,word vectors:W以及softmax的权重,是固定的。

假设在语料中有N个段落(paragraph),词汇表中有M个词,我们希望学到paragraph vectors,每个paragraph都被映射到p维上,每个word被映射到q维上,接着该模型具有总共N x p + M x q 个参数(将softmax参数排除在外)。尽管当N很大时,参数的数目会很大,在训练期间的更新通常是稀疏的,并且很有效。

在训练之后,paragraph vectors可以当成是该段落(paragraph)的特征(例如:代替bow或作为bow的额外附加)。我们可以将这些features直接输入到常用的机器学习技术(LR, SVM或者K-means)中。

总之,算法本身有两个关键步骤:

  • 1) 在训练(training)阶段:在已知的段落(paragraphs)上,获取词向量W,softmax的权重(U,b)以及paragraph vector: D.
  • 2) 在推断(inference)阶段:保持W,U,b固定不变,通过增加D中的更多列,在D上进行梯度下降,为新未曾见过的的段落(paragraph)获取paragraph vectors: D。我们使用D来做预测关于更多的特定labels。

paragraph vectors的优点:paragraph vectors的一个重要优点是,它们可以从未标记的数据(unlabeled data)中学到,在没有足够多带标记的数据(labeled data)上仍工作良好。

Paragraph vectors也处理了一些BOW模型所具有的主要缺点。首先,它们继承了词向量的一个重要特性:词的语义(semantics)。在该空间中,对比”Paris”与”strong”,”powerful”与”strong”更接近。Paragraph vector的第二个优点是:它们会考虑词顺序(至少在某个小上下文上会考虑),与n-gram模型(有一个大的n)的方式相同。这十分重要,因为n-gram模型保留着一部分段落(paragraph)的信息,包括词顺序。也就是说,我们的模型可能优于一个bag-of-n-gram模型,因为一个bag-of-n-gram模型可以创建出一个高维表示,这很难泛化。

2.PV-DBOW: (无词序的Paragraph Vector: Distributed BOW)

上面的方法会将paragraph vector和词向量串联起来来预测一个文本窗口中的下一个词。接下来的另一种方法则是忽略掉输入中的上下文词汇,强制模型去预测从段落(paragraph)中随机抽样出的词作为输出。在实际上,这意味着,在SGD的每次迭代中,我们可以抽样一个文本窗口,接着从该文本窗口中抽样一个随机词汇,去构建这样一个分类器任务来获取Paragraph Vector。该技术如图3所示。我们将该版本称为:PV-DBOW (Distributed Bag of Words version of Paragraph Vector)

图3: PV-DBOW.在该版本中,训练该paramgraph vector以预测在一个小窗口中的词汇.

除了概念简单之外,该模型存储的数据也更少。我们只需要存储softmax的权重,而PV-DM则需要存储softmax权重以及词向量。该模型与word2vec中的skip-gram模型相类似。

在我们的试验中,每个paragraph vector是一个两种向量的组合:一个向量由标准PV-DM模型学到,另一个向量由PV-DBOW模型学到的。对于大多数任务PV-DM单独工作也能达到很好的效果(state-of-art),如果与PV-DBOW组合在一起使用,在许多不同任务上可以更一致,强烈推荐使用组合方式

3.实验

我们会对paragraph vectors的表现进行实验。

对于语义分析,我们使用两个数据集:Stanford sentiment treebank dataset 以及 IMDB dataset。这些数据集中的文档在长度上区别很大:Stanford数据集是单句,而IMDB则包含着多句。

我们也在一个信息检索任务上测试我们的方法,目标是:给定一个query,一个文档是否该被索引出。

3.1 基于sentiment-treebank数据集的Sentiment Analysis

数据集:该数据集首先在2005年提出,随后在2013进行扩展,是sentiment analysis的一个benchmark。它包含了11855个句子,从烂蕃茄(Rotten Tomatoes)的电影评论中获取。

该数据集包含了三个集合:8544个句子用于训练(training),2210个句子用于测试(test),1101个句子用于验证(validation)。

数据集中的每个句子都有一个label,表示极性的正负程度,从0.0到1.0.label由亚马逊的众包(Amazon Mechanical Turk)人工标注完成。

该数据集对于句子有详细的label,子句(subphrases)同样也需要。为了达成该目标,Socker et al.(2013b)使用Stanford Parser(Klein & Manning,2003)来将每个句子解析成子句(subphrases)。子句接着以相同的方式被人工标注。目前该数据集总共有239232个带标记的句子。数据集下载地址:https://nlp.stanford.edu/sentiment/

任务以及Baselines: 在(Socker et al.,2013b)中,作者提出了两种benchmarking的方法。首先,可以考虑5-way细粒度分类任务,对应的label为:{Very Negative, Negative, Neutral, Positive, Very Positive}或一个2-way的粗粒度分类:{Negative, Positive}。另外,可以分为:是对整句,或者子句的划分。本工作主要针对完整句子的labeling.

在该数据集中,Socher应用许多方法,并发现Recursive Neutral Tensor Network比BOW模型更好! 这里仍有争议,因为电影评论通常很短,语义合成性(compositionality)在决定评论极性正负时扮演着重要角色。对于这个小训练集,对词语间的相似度也同样很重要。

试验约定:我们按照(Socher et al.2013b)所描述的实验约定。为了充分利用带标记数据,在我们的模型中,每个子句,都被当成是一个独立的句子,我们将为训练集中所有的子句学到它的向量表示。

在学习到训练句子和它们的子句的向量表示之后,我们将它们输入到一个logistic regression中来学习电影评分的预测。

在测试时,我们确定每个词的向量表示,使用梯度下降学到句子的向量表示。一旦学到测试句子的向量表示,我们将它们输入到logistic regression中来预测电影评分。

在我们的试验中,我们使用验证集对window size交叉验证,可选的window size为8。该分类器的向量表示是两个向量的串联:一个来自PV-DBOW,另一个来自PV-DM。在PV-DBOW中,学到的段落向量表示为400维。在PV-DM中,学到的词向量和段落向量表示均为400维。为了预测第8个房屋中,我们将paragraph vectors和7个word vectors相串联。我们将特征字符“,.!?”这些看成是一个普通词。如果该段落(paragraph)少于9个词,我们会预补上(pre-pad)一个特殊的NULL符号(NULL word symbol)。

结果:如表1所示。我们上报了不同方式的错误率。该表中高度部分是BOW或者是bag-of-n-gram模型(NB, SVM, NiNB)的效果很差。对词向量求平均(以BOW的方式)不会提升结果。因为BOW模型不会考虑句子是如何构成的(比如:词顺序),因此在识别许多复杂语义现象时(例如:反讽:sarcasm)会失败。结果也展示了更多的高级方法(比如:Socher.2013b的RNN),它需要parsing以及会对语义合成性做理解,效果更好。

我们的方法比所有的这些baselines都要好,尽管实际上不需要parsing。在粗粒度分类任务上,我们的方法在error-rates上有2.4%的提升。相对提升16%!

3.2 多句:IMDB数据集的Sentiment Analysis

前面的技术只应用在单句上,而非带有多句的段落或者文档上。例如:RNN会基于在每个句子上进行parsing,而对于多个句子上的表示的组合是不清楚的。这种技术只限制在句子上,而不能用在段落或者文档上。

我们的方法不需要parsing,它可以对于一个包含多句的长文档生成一个表示。这个优点使人们的方法比其它方法更通用。下面的试验在IMDB数据集上展示了该优点。

数据集:IMDB数据集,首先由Maas et al., 2011提出作为sentiment analysis的一个benchmark. 该数据集包含来自IMDB的10W的电影评论。该数据集的一个关键点是,每个电影评论都有多句话组成。

10w的电影评论被分成三个数据集:2.5W带标记的训练实例,2.5W带标记的测试实例,5W未标记的训练实例。有两类label: 正向(Positive),负向(Negative)。这些label对于训练集和测试集是均衡的(balanced)。数据集下载:http://ai.stanford.edu/~amaas/data/sentiment/

实验约定:我们会使用7.5W的训练文档(2.5W已经标注的实例,5W未标注的实例)来学到word vectors和paragraph vectors。对于2.5W已标注实例的paragraph vectors,接着会输入(feed)到一个单层的、含50个单元神经网络中,以及一个logistic分类器来预测语义。

在测试时,给定一个测试语句,我们再次固定网络的其余部分,通过梯度下降学到测试评论中段落向量(paragraph vectors)。当学到向量时,我们将它们输入到神经网络中来预测评论的sentiment。

我们的paragraph vector模型的超参数,和先前的任务相同。特别的,我们交叉验证了window size,最优的window size为10个词。输入到分类器的向量表示,是两个向量的串联,一个是PV-DBOW,另一个是PV-DM。在PV-DBOW中,学到的向量表示具有400维。在PV-DM中,为words和documents学到的向量表示都有400维。为了预测第10个词,我们将paragraph vectors和word vectors相串联。特殊词:”,.!?”被看成是一个普通词来对街。如果文档比9个词少。我们会使用一个特殊的NULL词符号进行以预补足(pre-pad)。

结果:Paragraph Vectors的结果和其它baselines如表2所示。对于长文档,BOW模型执行很好,很难在它们之上使用词向量进行提升。最大的提升发生在2012年(Dahl et al.2012),它将一个RBM模型与BOW相组合。两种模型的组合在error-rates上有1.5%的提升。

另一个大提升来自(Wang & Manning,2012)。他们使用了许多变种,在bigram特征上使用NBSVM,效果最好,在error-rates上有2%的提升。

在该paper上描述的方法,超出了10%的error-rate提升。它达到了7.42%,比上面最好的模型有1.3%的绝对提升(相对提升有15%)

表2: IMDB的Paragraph vector的效果对比.

3.3 使用PV的IR

我们在IR任务中,使用固定长度的paragraph表示。

这里,我们有一个段落数据集,给定100W的最流行搜索,返回有10个结果。这些段落的线一个都被称为片段“snippet”,它是一个网页的内容摘要,以及一个网页是如何匹配query的。

从这些collection中,我们派生了一个新的数据集作为测试集的paragraph向量表示。两个段落(paragraph)是对于相同的query的结果,第三个段落(paragraph)是从该collection的其它部分随机抽样得到的paragraph(作为一个不同的query得到的结果返回)。我们的目标是,确认这三个paragraph中哪些是相同query返回的结果。为了达到该目的,我们使用paragraph vectors,并计算paragraphs间的距离(distance)。也就是说:相同查询的段落对的距离的距离小,以及不同查询的段落对(paragraphs pairs)间的距离大。

这里有关于三个段落的一个样本,第一个段落更接近于第二个段落(比第三个):

  • 段落1: calls from ( 000 ) 000 - 0000 . 3913 calls reported from this number . according to 4 reports the identity of this caller is american airlines .
  • 段落2: do you want to find out who called you from +1 000 - 000 - 0000 , +1 0000000000 or ( 000 ) 000 - 0000 ? see reports and share information you have about this caller
  • 段落3: allina health clinic patients for your convenience , you can pay your allina health clinic bill online . pay your clinic bill now , question and answers…

该三联体(triplets)被划分为三个数据集:80%训练,10%验证,10%测试。任何方法都需要在训练集上学习,而超参数的选择则在验证集上选择。

我们对4种方法做benchmark,并计算段落的特征:bag-of-words, bag-of-bigrams, 对词向量求平均,对Paragraph Vector求平均。为了提升bag-of-bigrams,我们也学到了一个加权的martix:前2个的距离最小化,第1个和第3个段落的距离最大化(两个losses间的加权因子是个hyperparameter)

当每个方法中,两个段落的距离越来越小,第一个和第三个段落的距离越来越大时,我们记录了对应的时间数。如果方法不生成期望的结果,会出来一个error。

Paragraph Vector的结果和其它baseline如表3所示。在该任务中,我们发现,TF-IDF的加权效果比raw counts要好,因此,我们只上报了TF-IDF weighting方法。

结果展示了Paragraph Vector工作良好,在error-rate给出了一个32%的相对提升。实际上,paragraph-vector的方法好于bag-of-words以及bag-of-bigrams。

3.4 一些进一步观察

  • PV-DM比PV-DBOW的一致性要好。单独使用PV-DM达到的效果与本paper中的许多结果相接近(见表2)。例如,在IMDB上,PV-DM只达到了7.63%。PV-DM与PV-DBOW合一起更好一些(7.42%),因而推荐使用。
  • 在PV-DM中使用串联(concatenation),通常比求和(sum)更好。
  • 对window-size进行cross-validate更好。许多应用的window size在:5-12之间.
  • Paragraph Vector的计算开销大,但可以在测试时并行完成。平均的,我们的实现花了30分钟来计算IMDB测试集的paragraph vector,使用16-core机器(2.5W文档,每个文档平均230个词)

4.实现

4.1 gensim实现

gensim的models.doc2vec实现了该模型。

class gensim.models.doc2vec.Doc2Vec(documents=None, 
	dm_mean=None, 
	dm=1, 
	dbow_words=0, 
	dm_concat=0, 
	dm_tag_count=1, 
	docvecs=None, 
	docvecs_mapfile=None, 
	comment=None, 
	trim_rule=None, 
	**kwargs)

它的基类是gensim中的: gensim.models.word2vec.Word2Vec

  • documents:一个元素为TaggedDocument的list,对于更大的语料可以使用磁盘/网络。如果不提供documents,则模型会未初始化。
  • dm: 缺省为1. dm=1,表示使用PV-DM。否则使用PV-DBOW.
  • size: 特征向量的维度(基类中)
  • window: 要预测的词与上下文间的最大距离,用于文档中的预测
  • alpha: 初始的learning-rate(随着训练的进行,会线性降至0)
  • seed: 用于随机数字生成器。注意,对于一个完整的确定可再生的运行过程,你必须将该模型限制到单个worker线程上, 以便消除OS线程调度引起的时序抖动。(在python 3中,不同解释器加载之间可再生也需要使用PYTHONHASHSEED环境变量来控制hash随机化)
  • min_count: 忽略总频率低于该值的所有词
  • max_vocab_size: 在词汇表构建时的最大RAM限制; 如果有许多单个的词超过该值,会对频率低的进行剪枝。每1000w的词类型,需要大概1GB的RAM。缺省设为None,即无限制。
  • sample: 配置的阀值,更高频的词会随机下采样(random downsampled)。缺省为0(off), 有用的值为1e-5.
  • workers: 使用多个worker线程来训练模型(多核机器更快)
  • iter: 在语料上的迭代次数(epoches)。缺省值从Word2Vec继承下来,为5. 但对于’Paragraph Vector’来说,10或20更常用。
  • hs: 如果为1, 表示使用hierarchical sampling来进行模型训练,否则为0. 缺省为1
  • negative: 如果>0, 会使用negative sampling,int值表示应抽样“noise words”多少次。(通常设在5-20间)
  • dm_mean: 如果为0(缺省情况), 会使用上下文的词向量的求和(sum)。如果为1,则使用求平均(mean)。如果dm以非级联(non-concatenative)的模式,才会使用它。
  • dm_concat: 如果为1,则使用上下文向量的级联方式(concatenation),而非(sum/average)方式;缺省为0(off)。注意,级联(concatenation)会导致一个大的多的模型,输入不再是一个词向量(被抽样出或者算术结合)的size,而是使用该tag(s)的size和上下文中的所有词捆在一起。
  • dm_tag_count: 当使用dm_concat模式时,每个文档所期望常数个文档标签;缺省为1
  • dbow_words: 如果设置为1, 则会训练word-vectors(以skip-gram的方式),同时训练DBOW的doc-vector;缺省为0(只训练doc-vectors训练会更快)
  • trim_rule: 词汇表剪枝规则,指定了特定的词是否应保留在词汇表中,是否被削剪掉,或者使用缺省方式处理(如果词的count<min_count,直接抛弃). 可以置为None(即使用min_count),或者使用一个回调,使用参数(word,count,min_count),返回下述值:util.RULE_DISCARD, util.RULE_KEEP or util.RULE_DEFAULT. 注意:如果给定该规则,会使用它在build_vocab()期间来剪枝词汇表,不会被当成是模型的一部分进行保存。

另几个比较重要的函数:

  • delete_temporary_training_data(keep_doctags_vectors=True, keep_inference=True)

抛弃在训练时和评分时用到的参数。如果你确认模型训练完了,就可以使用它。keep_doctags_vectors=False,不会保存doctags向量,这种情况下,不可以使用most_similar进行相似度判断。keep_inference=False表示,你不希望保存用于infer_vector的参数.

相应的示例代码,可以参见:

二、Tomas Mikolov的c实现

Tomas Mikolov在https://groups.google.com/forum/#!msg/word2vec-toolkit/Q49FIrNOQRo/J6KG8mUj45sJ处提供了他的sentence2vec的实现。

  • cbow=0: 表示PV-DBOW.

三、其它实现

https://github.com/zseymour/phrase2vec

参考