attention机制在2014年被引入到NLP中:《NEURAL MACHINE TRANSLATION BY JOINTLY LEARNING TO ALIGN AND TRANSLATE》,我们可以看下具体实现:

2.背景:神经机器翻译

从概率角度,翻译等同于:给定一个源句子(source sentence)x,发现这样一个目标句子y(target sentence),使得它的条件概率最大化: 。在神经机器翻译中,会拟合一个参数化模型,使用一个并行训练语料,来最大化关于句子对(sentence pairs)的条件概率。一旦通过一个翻译模型学到了条件分布后,对于给定一个源句子,对应的翻译可以通过搜索使条件概率最大的句子来生成。

最近,许多paper已经提出使用神经网络来直接学习该条件概率。 这些神经机器翻译方法通常包含两个组件:第1个组件会编码(encode)一个源句子x,第2个组件会解码(decode)成一个目标句子y。例如,(Cho.2014a)使用两个RNN来将一个变长的源句子编码到一个固定长度的vector上,然后将该vector解码到一个变长的目标句子上。

神经机器翻译已经成为相当新的方法,并展示了很好的结果。Sutskever 2014, 在English-to-Frech翻译任务上,使用基于RNN与LSTM units的神经机器翻译已经达到了接近state-of-the-art的效果。。。

2.1 RNN encoder-decoder

这里,我们描述了下述框架,称为RNN Encoder-Decoder,由Cho 2014a和Sutskever 2014提出。 在此基础上我们构建了一个新结构,它可以同时学到对齐(align)和翻译(translate)。

在Encoder-Decoder框架中,encoder会读取输入句子(input sentence),一个向量序列:,将它映射到一个向量c上。使用RNN时最常用的方法是:

…(1)

…(2)

其中:

  • 是一个在时间t时的hidden state
  • **c是一个从hidden states序列生成的vector。
  • f和q是一些非线性函数。例如:Suskever 2014使用一个LSTM作为f,

decoder通常被训练成:在给定上下文向量(context vector)c、以及之前预测过的词的情况下,用来预测下一个词。换句话说,decoder定义了一个在翻译y上的概率,它通过将联合概率(joint probability)解耦成顺序条件(ordered conditionals):

…(2)

其中,。在一个RNN中,每个条件概率被建模成:

…(3)

其中:

  • g是一个非线性、可能多层的函数,会输出概率
  • 是RNN的hidden state。

需要注意的是,其它结构(比如:一个RNN与一个de-convolutional网络进行混合的结构)可以被使用。

3.学习align和translate

在本节中,我们提出了一个新的神经机器翻译结构。新结构包含了一个Bidirectional RNN作为一个encoder(3.2节),以及一个decoder,它在对一个翻译进行decoding期间,通过一个源句子进行模拟搜索来完成。

3.1 Decoder: 通用描述

在新模型结构中,我们定义了等式(2)中的每个条件概率:

…(4)

其中,是一个在时间i上的RNN hidden state,可以通过下述公式计算得到:

需要注意的是,不同于已经存在的encoder-decoder方法(等式(2)),这里的概率是条件概率,它基于对于每个目标词(target word)上一个不同的上下文向量(context vector) 得到。

上下文向量依赖于一个annotation序列:,一个encoder会将输入句子(input sentence)映射到它上。每个annotation 包含了整个输入序列相关的信息,它会强烈关注围绕在输入序列第i个词周围的部分。后续我们会解释 annotation是如何被计算的。

1.png

图1: 给定一个源句子,提出的模型尝试生成第t个目标词图示

上下文向量通过对这些 annotations 进行加权求和得到

…(5)

每个annotation 的权重通过计算下述公式得到:

其中:

是一个对齐模型(alignment model),它会对围绕位置j的输入与位置i的输出间的匹配度进行打分。该得分基于RNN hidden state (等式(4))和关于输入句子的第j个 annotation 计算得到。

我们将对齐模型(alignment model)a参数化成一个前馈神经网络,它会与系统的所有其它组件一起进行jointly train。注意,这与在传统的机器翻译不同,对齐(alignment)不会被当成一个隐变量来考虑。相反的,对齐模型(alignment model)会直接计算一个软对齐(soft alignment),它允许cost函数的梯度可以进行BP。该梯度可以被用于联合训练alignment model与translation model。

我们可以理解,采用对所有annotations进行加权求和的方法来计算一个期望注解(expected annotation),其中期望是对所有alignments进行的。假设是目标词与源词对齐的概率、或从源词进行翻译的概率。接着,第i个上下文向量是使用概率在所有annotations上的expected annotation。

概率,或者它相关的能量,会影响annotation 在关于前一hidden state 在决定下一state 和生成的重要性。直觉上,这实现了在decoder中的attention机制。该decoder决定着源句子中要关注(pay attention to)的部分。通过让decoder具有一个attention机制,我们会减轻encoder将源句子中的所有信息编码成一个固定长度向量的负担。使用这种新方法,可以通过annotations序列进行传播信息,这些annotations可以根据相应的decoder进行选择性检索。

3.2 Encoder:对annotating序列使用Bi-RNN

常用的RNN,如等式(1)所描述,会以从的顺序读取一个输入序列x。然而,在提出的scheme中,我们希望每个词的annotation可以归纳不仅仅是前面出现的词,也可以归纳后续跟着的词。因而,我们提出使用一个BiRNN。

BiRNN包含forward和backward RNN两部分。forward RNN 会按从的顺序读取输入序列,并计算一个forward hidden states序列。backward RNN 会以逆序 (即:从的顺序)来读取序列,产生backward hidden state序列

我们通过将forward hidden state 和backward 进行拼接(concatenate)(如:),来为每个词获得一个annotation。这种方式下,annotation 包含了前面词和后续词的总结信息(summaries)。由于RNN可以更好地表示最近输入,annotation 将关注周围的词。该annotations序列被用在decoder上,alignment model后续会计算该上下文向量(等式(5)-(6))。

4.实验

参考

我们来看下《AutoRec: Autoencoders Meet Collaborative Filtering》,它提出的autorec,会使用新的autoencoder框架来进行CF:

1.介绍

CF模型的目的是,根据用户对items(评分)的偏好进行探索,从而来提供个性化推荐。Netflix竞赛提出了一全套不同的CF模型,比较流行的方法有:矩阵分解[1,2]以及邻近模型[5]。该paper提出了AutoRec,一种新的基于autoencoder范式的CF模型。它的灵感原自于最近在视觉和语音任务上的深度学习上获得的成功。AutoRec对于已经存在的CF上的神经网络方法[4]在表征和计算上均有优势,我们会展示它的效果要好于state-of-art方法。

2.AutoRec模型

在基于评分(rating)的CF中,我们有m个用户,n个items,以及:

  • 一个部分可观察(相对的,有一部分missing)到的user-item评分矩阵
  • 每个用户,可以被表示成一个部分可观察向量(partially observed vector):

相似的,每个item ,可以被表示成:

我们的目标是,设计一个item-based(user-based)的autoencoder,它可以将输入看成是每个部分可观测的,将它投影到一个低维的隐空间(hidden/latent space),接着,在输出空间将进行重构来预测缺失的ratings。

正式的,给定在中的一个S集合,,一个autoencoder可以求解:

…(1)

其中,是对输入的重构(reconstruction):

对于激活函数 。这里,对于转换(transformations): ,其中biases为: 。该目标函数对应于一个自关联的神经网络(auto-associative neural network),它使用单个k维的hidden layer。参数可以通过backpropagation进行学习。

图1: Item-based AutoRec模型。我们使用plate notation来表示,该网络存在n个拷贝(每个item一个),W和V跨多个拷贝绑定。

item-based AutoRec模型,如图1所示,使用一个autoencoder作为等式(1)到向量集合中,有两个重要变化。第一,我们会解释:每个通过在BP期间的更新上关权重来被部分观测,这一点与矩阵分解和RBM方法相同。第二,我们会对学习参数进行正则化,以便防止在观测到的ratings上overfitting。正式的,Item-based AutoRec (I-AutoRec)模型的目标函数是:

…(2)

其中,意味着,我们只需考虑可观测评分的贡献即可。User-based AutoRec (U-AutoRec)则由 而来。总之,I-AutoRec 需要估计 个参数。给定要学习的参数,I-AutoRec会为用户u和item i预测相应的评分:

…(3)

图一展示了该模型,阴暗色节点表示观测到的评分,实线连接对应于权重(对于输入要更新的权重)

AutoRec与已经存在的CF方法不同。对比RBM-based CF模型,有一些不同之处:

  • 1.RBM-CF提出了一种通用的概率模型,它基于Boltzmann机;而AutoRec是一个判别模型(discriminative model),它基于autoencoders
  • 2.RBM-CF通过最大化log似然来估计参数,而AutoRec直接最小化RMSE(在评分预测上的标准评判指标)。
  • 3.训练RBM-CF需要使用对比散度( contrastive divergence),而训练AutoRec需要比较快的基于梯度的BP算法。
  • 4.RBM-CF也用于离散评分,并每个评分值估计一个独立的参数集合

对于r个可能的评分,这意味着对于user-based RBM有nkr个参数;对于item-based RBM有mkr个参数。AutoRec对于r是不可知的,因而需要更少的参数。更少参数能让AutoRec具有更少的内存占用,不容易overfitting。对于MF(矩阵分解)方法,会将users和items嵌入到一个共享的隐空间中;而item-based AutoRec模型只会将items嵌入到隐空间中。再者,MF会学到一个线性隐表示,AutoRec可以通过激活函数学到一个非线性隐表示

3.实验评估

在本部分,在数据集:Movielens 1M, 10M and Netflix datasets上评估了AutoRec、RBM-CF、BiasedMF、以及LLORMA。接着,我们使用一个缺省的评分3用于测试users或items,没有训练观察。我们将数据划分为:随机的90%-10%的train-test集合,并留下10%的训练集数据进行超参数调节。我们会重复5次的splitting过程,并上报平均的RMSE。在RMSE上的95%置信区间是,或者更小。对于所有baselines,我们会将正则参数以及合理的隐维度

训练autoencoders的一个挑战是,目标函数的非凸性。我们发现RProp与L-BFGS对比来说会更快。因此,我们在所有实验中使用RProp:在item-based和user-based方法上,对于RBM或AutoRec autoencoding哪个更好?表1a展示了item-based(I-)方法上,RBM和AutoRec通常会更好;这很可能是因为每个item的评分平均数,比单用户的要多;对于user-based方法,user ratings的数目的高偏差会导致更低可靠性的预测。I-AutoRec的效果要比所有RBM变种要好。

AutoRec的效果随线性和非线性激活函数是如何变化的?表1b展示了在hidden layer中的非线性(通过)对于I-AutoRec上取得好效果是很重要的,它比MF更好。将sigmoid替换为Relu效果会差些。所有AutoRec实验使用标准的和sigmoid 函数。

AutoRec的hidden units数目与效果是啥关系?在图2中,我们评估了AutoRec模型的效果,AutoRec会随着hidden units数目变化,并且收益递减。所有AutoRec实验使用k=500.

图2: I-AutoRec在Movielens 1M上的RMSE,随hidden units数目k而变化

AutoRec的效果与所有baseline相比如何?表1c展示了AutoRec会一直好于所有baseline。

表1: a) I/U-AutoRec与RBM模型的比较 b) I-AutoRec中线性与非线性选择 c) I-AutoRec与其它baseline模型的比较

对autoRec的深度做扩展如何?我们开发了一个深度版本的I-AutoRec,它有三个hidden layers(500, 250, 500),每个使用sigmoid激活。我们使用贪婪预训练,接着通过梯度下降调参。在Movielens 1M上,RMSE会从0.831降至0.827, 表示有提升。

参考

http://users.cecs.anu.edu.au/~u5098633/papers/www15.pdf

先来看一下 paper中提取的FFM。

一、前置

对于一个有m个样本的数据集:$(y_i, x_i)$,i=1,…,m,其中$y_i$是label,$x_i$是一个n维特征向量,模型w通过对下面问题进行最优化求解得到。

…(1)

其中λ是正则参数,在loss function,如果是线性模型(LM: Linear Model),则:

另外,有两种其它的模型:Poly2和FM。

Poly2(度为2的多项式)可以有效捕获特征交叉信息。通过在线性模型上应用度为2的mapping的显式形式,训练和测试时间可以比使用kernel方式更快。这种方法可以学到每个feature pair的weight:

…(2)

其中$ h(j_1, j_2) $是一个用于将j1和j2编码成一个自然数的函数。计算(2)的复杂度为 $O(\bar{n}^2)$,其中n是每个实例非零元素个数的平均值。

FM则可以为每个feature学到一个隐向量。每个隐向量包含着k个隐因子,其中k是一个用户指定的参数。接着,特征交叉的效果通过两个隐因子进行内积建模而成:

…(3)

变量数为n x k,直接计算(3)的代价是 $O(\bar{n}^2 k)$。可以进行化简,得到:

其中:

复杂度可以减少到$ O(\bar{n}k) $.

二、FFM

FFM的idea来自于带有个性化标签的推荐系统中提出的PITF(paper 7)。在PITF中,假设有三种fields:User,Item,Tag,在独立隐空间中对(User, Item), (User, Tag), (Item, Tag)进行因子分解。在paper[8]中,将PITF泛化到更多的fields(比如:AdID, AdvertiserID, UserID, QueryID),并有效地将它应用在CTR预估上。由于 paper[7]的目标是推荐系统,并受限于三个特定的fields(User, Item, Tag),paper[8]在FFM上缺乏详细讨论,在本节中,我们提供了一个更复杂的在CTR预测上的研究。对于大多数像表 1所示的CTR数据集,“features”可以被分组成”fields”中。在我们的示例中,有三个features:ESPN,Vogue,NBC,它们都属于Publisher field;而其它三个features:Nike,Gucci,Adidas,它们都属于Advertiser field。FFM是FM的一个变种,它会利用这些信息。为了解释FFM是如何工作的,我们来看下面的新样本:

1
2
Clicked	Publisher(P)	Advertiser(A)	Gender(G)
Yes		ESPN			Nike			Male

回顾下FM,$ \phi_{FM}(w,x) $ 等于:

在FM中,每个feature都只有一个隐向量(latent vector)来学到与其它任何features的隐式影响。以ESPN为例,$ w_{ESPN} $用于学到与Nike(),以及Male()的隐式影响(latent effects)。然而,由于Nike和Male属于不同的fields,(ESPN, Nike)和(ESPN, Male)的隐式影响可能是不同的。

在FFM中,每个features具有不同的隐向量(latent vectors)。这取决于其它features的fields,其中之一会被用于做内积。在我们的示例中,$ \phi_{FM}(w,x) $ 为:

我们看到,为了学到(ESPN, Nike)的隐式影响,会被使用,因为Nike属于field(Advertiser:A),同理, 会被使用,因为ESPN属于field(Publisher:P)。

同理,学了学到(EPSN, Male)的隐因子,会被使用,因为Male会属于field(Gender: G);会被使用,因为ESPN属于field(Publisher: P)。 数学上:

…(4)

其中$f_1$和$f_2$各表示$j_1$和$j_2$的fields。如果f是fields的数目,那么FFM的变量数目为$ \bar{n}fk $,计算公式(4)的复杂度为$ O(\bar{n}^2 k) $。在FFM中,由于每个隐向量只需要学到一个特定field的影响,通常:

表2比较了不同模型的变量数和计算复杂度。

三、求解最优化问题

FFM的最优化问题与LM相似。这里使用的是SG方法(stochastic gradient)。最近,一些adaptive learning-rate方法有提出:AdaGrad等。使用AdaGrad是因为它对于矩阵因子分解(包括FFM)很有效。

在SG的每一个step中,会抽样一个数据点(y,x) 来更新 $ w_{j_1,f_2}$和$ w_{j_2,f_1}$。注意,由于x在我们的应用中高度稀疏,我们只会使用非零值来更新维度(dimensions)。首先,子梯度(sub-gradients)为:

…(5)

…(6)

其中:

接着,对于每个坐标 d=1,…,k,梯度平方和会进行如下累积:

…(7)

…(8)

最终,$ (w_{j_1,f_2})d$和$ (w{j_2,f_1})_d$会进行如下更新:

…(9)

…(10)

其中$\eta$是一个用户指定的learning-rate。w的初始值从一个在$[0, 1/\sqrt{k}]$间的均匀分布中进行随机抽样。G的初始值被设置成1以便于阻止一个关于$ (G_{j_1,f_2})_d^{\frac{1}{2}}$大值。整个过程如算法1所示。

经验中,我们发现归一化每个实例到单位长度上,可以让accuracy稍好,对参数更不敏感些。

3.2 共享内存系统上进行并行化

现代计算机基本都采用多核CPUs。如果这些核能被充分利用,训练时间可以极大缩短。许多SG的并行方法被提出。在这paper中,我们应用HOG-WILD!,它允许每个线程独立运行,没有任何锁。特别的,在算法1中的第3行的for循环是并行的。

3.3 增加Field信息

考虑到我们使用的是LIBSVM的数据格式:

1
label feat1:val1 feat2:val2 · · · 

其中每个(feat,val)pair 表示特征index和value。对于FFM,我们扩展了以上的格式:

1
label field1:feat1:val1 field2:feat2:val2 · · ·

也就是说,我们必须为每个feature分配一个对应的field。这种分配在某些类型的特征上很容易,但是在另外一些类型的特征上不太容易。这里讨论了三种类型。

Categorical Features

对于线性模型,一个categorical feature常以被转换成一些二值特征。对于一个数据实例:

1
Yes P:ESPN A:Nike G:Male

我们生成了它的Libsvm格式:

1
Yes P-ESPN:1 A-Nike:1 G-Male:1

注意,对应于在一个categorical feature中可能值的数目,会生成相同数目的二值特征,每次只有其中之一会具有值1。在Libsvm格式中,零值的features不会被存储。我们将这种setting应用到所有模型中。为了添加field信息,我们可以将每个category看成是一个field。以上的实例就变成了:

1
Yes P:P-ESPN:1 A:A-Nike:1 G:G-Male:1

Numerical Features

考虑到以下的示例是预测一个paper是否会被某会议接收。我们使用三种数值型特征:“会议接收率:accept rate of the conference (AR),”“作者的h-index:h-index of the author (Hidx),” and “作者的引用数:number of citations of the author (Cite):”.

1
2
3
Accepted	AR		Hidx	Cite
Yes			45.73	2		3
No			1.04	100		50000

这里有两种可能的方式来分配fields。一种自然的方式是,将每个feature看成是一个dummy field,因而生成的数据是:

1
Yes AR:AR:45.73 Hidx:Hidx:2 Cite:Cite:3

然而,该dummy fields可能没有任何信息量,因为它们仅仅只是特征的复制。

另一个可能的方式是,对每个数值型特征离散化成一个类别型特征。接着我们使用和categorical features相同的setting来添加field信息。生成的数据如下:

1
Yes AR:45:1 Hidx:2:1 Cite:3:1

其中,AR特征被归整(round)为一个整数。主要的缺点是,通常决定最好的离散化设置并不容易。例如,我们可能将45.73转化成: 45.7, 45, 40, 或者 int(log(45.73))。另外,我们会在离散化后失去一些信息。

single-field features

在一些数据集上,所有的features都属于单个field,因而,为它分配一个field是无意义的。通常该情况发生在NLP数据集中。考虑到以下示例:预测一个句子表达是好心情,还是坏心情。

1
2
3
good mood		sentence
Yes				Hooray! Our paper is accepted!
No				Well, our paper is rejected.

在该例中,只有一个field:“sentence”。如果我们为所有的words分配一个field,那么FFM就成了FM。读者们可能会问到可以分配类似numerical features的dummy field。回顾下FFM的model size为:O(nfk)。使用dummy fields不实际,因为f=n,n通常很大。

4.实验

详见paper。

参考

我们都清楚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

参考

我们来看下Feng Niu等人提出的《Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent》。

#

SGD是许多机器学习任务的一种流行优化算法。之前的许多研究者都提出了并行化SGD的schemes,但都需要影响性能的内存锁和同步机制。本文主要展示了使用新的理论分析、算法和Hogwild!实现,它允许处理器以相互覆写(overwriting)的方式访问共享内存。当相关优化问题是sparse时,大多数梯度更新(gradient updates)只会修改决策变量的很小一部分,接着Hogwild!可以达到一个近似最优的收敛率。实验结果表明Hogwild!的效果要比使用锁版本的要好一阶。

1.介绍

由于较小的内存占用、对噪声健壮、以及快速的learning rate,SGD被证明是很适合数据密集(data-intensive)的机器学习任务。然而,SGD的扩展性受它的顺序型(serial)特性限制;很难并行化。随着不贵的多核处理器和超大型机器出现,大规模(web-scale)数据集启发着研究者们为SGD开发了许多并行化schemes。许多大型数据集当前在类MapReduce并行处理框架上进行预处理,在并行SGD上的最近的许多工作都主要关注在MapReduce实现。MapReduce是一个很强大的工具,但它不适合online、数值密集的数据分析。迭代型计算很难在MapReduce上表示,并且确保容错的开销可能会产生更大的吞吐量。Google研究者建议其它系统(例如:Dremel)比MapReduce更适合。

对于一些数据集,数据的绝对规模(sheer size)预示着是否需要一个机器集群。然而,存在一个问题,在合适预处理后,对于统计分析所需要的数据,可能仍包含上兆(TB)字节。而对于一些问题,并不需要上百台集群,可以使用单个便宜的工作站就行。多核系统具有极大的性能优点:包括:

  • 1)低延迟、高吞吐,共享主要内存:这样的系统中一个处理器可以以超过12GB/s的速率读写共享物理内存,延迟只有数10ns
  • 2)跨多磁盘高带宽(high bandwidth off multiple disks):一个上千美金的RAID可以以超过1GB/s的速率将数据导入到主存中。而作为对比,由于存在容错机制上频繁的checkpoint,一个典型的MapReduce setup会以低于数十MB/s的速率读取数据。多核系统可以达到高速率,瓶颈在处理器间的同步(或locking)上。因而,为了能在多核机器上允许可扩展的数据分析,一些好的解决方案必须能最小化加锁开销。

在本paper中,我们提出了一种称为”HOGWILD!”的简单策略来消除与锁相关的开销:无锁方式并行运行SGD。在HOGWILD中,各处理器被允许公平访问共享内存,并且能随意更新内存私有变量(individual components)。这样的lock-free scheme看起来注定会失败,因为处理器可以覆盖写(overwrite)其它的处理器的操作。然而,当数据处理是稀疏时,这意味着单独的SGD steps只会修改决策变量的一小部分,我们展示了内存覆盖写(memory overwrites)很少发生,并且当它们发生时只会将很少的错误引入到计算中。我们展示了,理论上和实验上一个近似的与处理器数成线性加速,这通常发生在稀疏学习问题上。

在第2节,我们对稀疏概念公式化,它足够保障这样的加速,并提供了在分类问题、协同过滤、图分割上关于稀疏机器学习问题的示例。我们的稀疏性概率允许我们提供关于线性加速的理论保证。作为我们分析的一个副产品,我们也派生了常数步长(constant stepsizes)收敛率的算法。我们展示了使用constant stepsize schemes的1/k收敛率是可能的,它实现了一个在常数时间上的指数级补偿(backoff)。该结果本身挺有意思的,它展示了不必满足于来保证在SGD算法上的健壮性。

实际上我们发现,无锁版的计算性能要超过我们的理论保证。我们实验上比较了lock-free SGD,以及其它最近提出的方法。结果展示了所有提出内存锁(memory locking)的方法,比起lock-free版本要慢很多。

2.稀疏可分的cost functions

我们的目标是,最小化一个函数:

…(1)

这里,e表示了的一个小的子集,其中表示向量x在坐标索引e上的值。在我们的lock-free方法中的关键点是,与许多机器学习问题相关的cost functions是稀疏的(sparse)的,和n都非常大,但每个单独的只在x的一小部分成分起作用。也就是说,每个子向量只包含了x的一少部分成分(components)。

(2.1)的cost function引入了一个hypergraph:,它的节点是x的单个元素。每个子向量相当于在图中引入一条边,它包含了节点的一些子集。以下的示例展示了该概念。

图1: 由cost function引入的样本图. (a) 一个sparse SVM会引入一个hypergraph,其中每个hyperedge对应一个样本 (b) 一个矩阵补全示例,它在行与列间引入了一个二分图(bipartite graph),如果有出现一个entry,那么两个节点间就有一条edge (c) 在graph-cut问题中的hypergraph就是一个简单图,它的切分就是我们想找的

2.1 Sparse SVM

假设我们的目标是,拟合一个SVM:数据对为。其中和y是对于每个的一个label:

…(2.2)

其中,我们知道一个先验(priori)是,样本是非常稀疏的。为了以(2.1)的形式编写该cost function,假设表示该组件在中是非零的,并假设表示在第u(u=1,2,…,n)维上非零的训练样本数。可以将(2.2)改写成:

…(2.3)

在(2.3)中的求和只依赖通过集合索引的x的components。

2.2 矩阵补全(Matrix Completion)

在矩阵补全问题上,我们从索引集合E中提供了一个低秩的、的矩阵X的entries。这种问题在协同过滤(CF)、欧氏距离估计、聚类中常出现。我们的目标是,从该数据的稀疏样本中重构Z。一种流行的启发法(heuristic)可以将Z的估计恢复成:以下最小化公式得到的一个的因子乘积:

…(2.4)

其中,L是, R为表示L(对应:R)的第u(对应:vth)行。为了将该问题放入到稀疏形式,如(2.1)所示,我们将(2.4)编写成:

其中:

2.3 Graph Cuts

2.4 结论

在所有三个示例中,在一个特定项上所涉及的components数目,对于所有总条目数来说只占很小比例。我们将该概率进行公式化,定义了以下的关于hypergraph G的统计:

…(2.6)

可以简单量化hyper edges的size。决定了与任意给定edge交叉的edges最大比例。决定了与任何变量交叉的edges的最大比例。是一个关于hypergraph稀疏度的衡量,其中决定着节点的正则化(node-regularity)。对于我们的例子,我们可以做出以下关于的观察:

  • 1.Sparse SVM。是在一个样本中出现的任何特征的最大频率,决定着hypergraph是如何聚类的。如果一些特征在整个数据集上很常见,那么会与某一个很接近。
  • 矩阵补全(Matrix Completion):如果我们假设,提供的样本是随机均匀抽样的,我们可以看到超过个样本,接着 。它会遵从一个彩票收集问题(coupon collector argument)。
  • 3.Graph Cuts。 是由划分的最大度(degree),至少为

我们现在描述了一个简单的protocol,当都很小时,它会在处理器数上达到一个线性加速。

3.Hogwild!算法

这里我们讨论并行化处理setup。我们假设,一个具有p个处理器的共享内存模型。决策变量x可以被所有处理器访问。每个处理器可以读取x,也可以为x贡献一个更新向量(update vector)。向量x存储在共享内存中,我们假设,component-wise加法操作是原子的,也就是说:

对于一个标量a和,该操作可以被任意处理器原子执行。该操作在大多数现代硬件上不需要一个独立的锁结构:这样的一个操作在GPUs和DSPs上是单个原子指令,它在像Intel Nehalem这样的专有目的多核处理器上可以通过一个compare-and-exchange操作来实现。相反的,一次更新多个components的操作需要一个辅助锁(auxiliary locking)结构。

每个处理器接着按照算法1的流程。为了完整描述该算法,假设:

  • 表示在中的标准基元素(standard basis elements)之一,其中v的范围为1, …, n。也就是说,在第v个component上等于1, 否则为0. 假设表示在坐标v上的欧几里德投影矩阵,例如:。其中是一个对角矩阵,它在第v个对角上为1,否则为0。
  • 表示函数相乘的一个梯度或者子梯度。也就是说,我们将,从坐标e上的一个函数扩展为上所有坐标上,通过忽略下标e来得到。那么:

这里,在的组件上的等于0.使用一个稀疏表示,只需要知道通过e索引的components中的x的值,我们就可以计算。注意,从E进行平均随机抽样得到e(uniform random sampling),我们具有:

在算法1中,每个处理器会均匀地随机抽取一个项,计算在的梯度,接着:

(3.1)

重要的是,注意,该处理器只修改通过e索引的变量,在中(e之外)的保持不变。

  • : 我们假设,stepsize 是一个固定的常数。
  • : 尽管这些处理器并不知道任何其它处理器是否已经修改了x,我们定义是决策变量x在j执行更新后的状态(state)。由于两个处理器可能会在同时写入x,我们需要注意该定义,但我们会通过随机方式来简单断绝关系。注意,通常使用一个旧的梯度进行更新,它基于x的一个在多个时钟周期前读取的值。我们使用来表示用于产生状态的用于计算梯度或次梯度的决策变量值。

在下文中,我们提供了这种异步、增量梯度算法收敛的条件。另外,我们也展示了,如果通过f引入的hypergraph是同性的(isotropic)并且稀疏的,那么,该算法的收敛几乎与它的serial版本具有相同数目的梯度计算steps。由于我们以并行方式运行并且无锁,这意味着我们会得到一个与处理器数目成接近线性关系的加速。

注意:下标i,j,k指的是迭代数,v和e指的是components或者components的子集。

4.Lock-Free Parallelism的Fast Rates

我们接着讲述Hogwild!算法的理论分析。为了让这个分析更易理解,我们假设,我们会使用以下的“有放回(with replacement)”过程进行更新:每个处理器会均匀随机抽样一条边e,并计算该决策变量的当前值上的的一个次梯度。

注意,该stepsize比(3.1)的step要更多一个因子。注意,该更新完全等价于:

…(4.1)

该概念对于下面的分析更方便。

该有放回(with replacement)scheme假设:一个梯度被计算,那么它的components中只有一个元素被用于更新该决策变量。这样的一个scheme计算很浪费,因为该梯度的components其它部分携带着关于对cost function进行递减的信息。因此,实际上以及在我们的实验中,我们会执行该过程的一个修改版本。在每个epoch的开始处,我们将这些边进行无放回(without replacement)划分到所有处理器上。这些处理器接着在它们各自的队列上,对每条边的所有components执行完全更新(full updates)。然而,我们需再次强调的是,我们不会实现对任何变量的任何锁机制。我们不会分析该“无放回(without replacement)”过程,因为在任何无放回抽样模型中,没人可以对SGD进行可控分析。实际上据我们所知,无放回抽样的所有分析,会产生与一个标准的次梯度下降算法(它会采用(2.1)完全梯度的steps)相当的rates。也就是说,这些分析建议:无放回抽样需要一个因子,因而比有放回抽样需要更多的steps。实际上,这种糟糕的情况从不会观察到。事实上,在机器学习中更明智的做法是,在SGD上进行无放回抽样,实际效果要好于有放回的形式

为了说明我们的理论结果,我们必须描述一些工程量,它对于我们的并行化SGD scheme的分析很重要。为了简化该分析,我们假设,在(2.1)中的每个是一个convex函数。我们假设f的Lipschitz连续微分,会使用Lipschitz常数L:

…(4.2)

我们也假设,f是具有系数c很强的convex性质。这意味着:

…(4.3)

其中,f具有很强的convex性,存在一个唯一的最小解,我们表示。我们额外假设,存在一个常数M,使得:

…(4.4)

我们假设,。(实际上,当,普通的梯度下降算法也会离散)

我们的主要结果通过以下进行归纳:

命题(Proposition) 4.1

假设在算法1中,当一个梯度被计算时,与它在step j被使用时,两者间的lag——,总是小于或等于,即,那么被定义为:

…(4.5)

对于一些 的情况。定义, 并让整数k满足:

…(4.6)

那么在关于x的k个compoments更新后,我们有

在该case中,,它可以精准减小到由serial SGD达到的rate。如果通常为,可以达到一个相同的rate。在我们的setting中,与处理器数据成比例,只要处理器数目小于,我们就可以获得在线性rate的循环。

我们在附录证明了命题4.1的两个steps. …(略)

注意,在(4.6)中,对于一个常数stepsize的SGD scheme,我们的分析接近提供了一个1/k 的收敛率,不管是顺序版本(serial)还是并行版本(parallel)。另外,注意,我们的收敛率相当robust;我们会为曲率f的低估花费线性时间。相反的,, Nemirovski等人展示了当stepsize与迭代数成反比时,高估的c可能会产生指数下降(n exponential slow-down)。我们转向展示,我们可以消除(4.6)的log项,通过一个稍微复杂些的方式,其中stepsize会在多次迭代后缓慢递减。

5.Robust 1/k rates

假设,对于算法1, 我们使用stepsize 运行固定数目K次的梯度更新。接着,我们等待线程合并结果,通过一个常数因子来对进行reduce,接着运行轮迭代。从某种意义上说,该piecewise constant stepsize protocol近似成一个1/k衰减的diminishing stepsize。以下分析与之前工作的主要不同之处是,对比开始非常大的stepsizes,我们的stepsize总是比1/c小。总是使用小的stepsizes运行,允许我们避免可能的指数级递减(exponential slow-downs),它发生于标准的diminishing stepsize schemes中。

为了更精准,假设是任意满足下述条件的实数的序列:

…(5.1)

其中,是一些关于的非负函数,它满足:

其中和B是常数。这种递归是许多SGD收敛证明的基础,其中表示在k轮迭代后的最优解的距离。我们会在附录中为Hogwild!选择合适的常数。我们也会在下面讨论对于标准的SGD算法的这些常数。

上的依赖,对于下面的情况很有用。将(5.1)化解开:

假设我们希望该量(quantity)要比要小。两项都要小于是充分的。对于第二项,这意味着:

…(5.2)

对于第一项,我们需要:

它持有:

…(5.3)

通过(5.2),我们应选择:,其中。使用(5.3)进行组合,k满足

在k轮迭代后,我们会有。这几乎可以提供给我们一个1/k的rate,模上因子。

为了消除log因子,我们可以实现一个backoff scheme,其中,我们在多轮迭代后通过一个常数因子来减小stepsize。这种backoff scheme有两个phases:第一个阶段将包含以一个指数的rate收敛到 的平方半径(它比要小)的球。接着,我们将通过对stepsize进行微调(shrinking)收敛到

为了计算到达在球体内所需的迭代次数,假设初始stepsize选择为:。stepsize的选择保证了会收敛到。我们使用参数来展示,我们不需要做多少调整,即可在我们的算法中得到最优stepsize(例如:)的下限。使用(5.3),我们可以发现:

(5.4)

k轮迭代后足够收敛到该球体。注意,这是一个线性rate的收敛率。

现在,假设。假设在每一轮通过一个因子来减小stepsize。这会导致通过一个因子来减小已经达到的。从而,在轮迭代后,我们的accuracy会是。迭代的总轮数接着会是公式(5.3)的各项求和,其中,通过之前的epoch被设置成已经达到的半径,被设置成。从而,对于epoch数v,初始距离是,最终的半径为

5.1 顺序型(serial)SGD的结论

我们对比了constant step-size protocol,以及在第k轮迭代将stepsize设置为(应用在等式(2.1)的标准顺序型(serial)增量梯度算法的一些初始step size )。 Nemirovsk[23]等人展示了到最优解的期望平方距离,, 满足:

我们可以将该递归式放到公式(5.1)中,通过设置:

[23]的作者演示了一个大的step size: 可以产生一个边界:

该边界可以通过将这些算法参数插入到公式(5.6)中、并使得 来得到。

注意,两个边界渐近的在M、c、k上有相同的依赖,表达式:

是最小的,等于1.34. 表达式:

时是最小的,等于1. 因此,产生的常数在constant stepsize protocol中当所有其它参数设置为最优时,会稍微变差些。然而,如果,那么1/k protocol的error会与成比例,但我们的constant stepsize protocol仍在初始距离上只有一个log依赖。再者,constant stepsize scheme在对曲率参数c高估上会更健壮些(robust)。而对于1/k protocol,如果你高估了曲率(对应于的一个小值),你会获得较慢的收敛率。简单的,在[23]中的一维样本展示了,可以生成一个的收敛率。在我们的scheme中,会通过一个因子5来简单增加迭代数目。

在[23]中提出的fix,会渐近式产生比更慢的收敛率。值得注间的是,我们不需要满足于这些更慢的收敛率,仍可以在1/k rates达到健壮收敛。

5.2 补偿(backoff) scheme的并行化实现

该scheme会为HOGWILD!产生一个1/k的收敛率,只有在每一轮(round/epoch)迭代结果时发生同步开销。当为Hogwild实现一个backoff scheme时,处理器间会在何时reduce stepsize上达到一致。一个简单的策略是,在所有的处理器上以一个固定数目的迭代次数运行,等待所有线程完成,然后在一个主线程上全局进行reduce stepsize。我们注意到,它可以为这些线程消除合并的需要,通过发送带外信息(out-of-band messages)给处理器来发送何时对进行reduce的信号来完成。这会让理论分析变得复杂,因为有可能有例外:当不同处理器以不同stepsizes运行时,但实际上可以允许某一个避免同步开销。我们不会实现该scheme,因此不会更进一步分析该思想。

6.相关工作

大多数并行化SGD的schemes是 Bertsekas and Tsitsiklis[4]提出的变种。实际上,在[4]中,他们描述了通过主从方式(master-worker)跨多机计算来使用stale gradient updates(老的梯度更新),也描述了不同处理控制访问决策变量的特定组件的settings。他们证明了这些方法的全局收敛,但没有提供收敛率。这些作者已经展示了SGD收敛率对多种模型是健壮的。

我们也注意到,constant stepsize protocols结合backoff过程在SGD实践中是权威,但在理论上不是。一些理论性工作至少已经展示了这些protocols的收敛性,可以在[20, 28]中找到。这些工作并没有确立上述的1/k rates。

最近,许多parallel schemes被提出。在MapReduce中,Zinkevich等提出在不同的机器上运行许多SGD实例,然后对output进行平均[30]。尽管作者宣称该方法可以同时reduce他们的估计方差(variance)和整体偏差(bias),在我们的实验中,对于我们关注的那类问题来说,该方法的效果不能胜过serial scheme。

通过一个distributed protocol对梯度求平均的schemes也由许多作者提出[10, 12]。而这些方法也可以达到线性加速,但他们很难在多核机器上有效实现,因为他们需要大量通信开销。分布式梯度求平均需要在多核之间进行消息传递,多个核需要频繁进行同步,以便计算合理的梯度平均。

与我们工作最接近的是round-robin scheme,它由Langford[16]提出。在该scheme中,多个处理器会排好序,然后按顺序更新决策变量。其中为进行写操作对内存上锁时所需时间,对比起梯度计算时间来说忽略不计,该方法会产生一个线性加速,因为在梯度中的lag所产生的errors并不会太剧烈。然而,我们注意到,在许多机器学习应用中,梯度计算时间是非常快的,我们现在证明了在许多应用中,Hogwild!的效果要胜过round-robin方法一个阶的量级。

7.实验

我们在许多机器学习任务上运行了数值型实验,并对比了[16]中的round-robin方法,它在Vowpal Wabbit[15]中有实现。我们将该方法简写为RR。为了公平,我们手工编码RR以便接近等同于Hogwild!方法,唯一的区别是,他们如何更新梯度的scheme不同。与Vowpal Wabbit软件中的RR的一个明显不同是,我们优化了RR的locking和signaling机制,以便使用spinlocks和busy waits(这对于通用signaling来说没有必要去实现round robin)。我们验证了对于我们讨论的问题,该optimization在wall clock time是会产生多一个阶。

我们也比较了一个称为AIG的模型,它可以看成是RR和Hogwild!间的一个折中。AIG会运行一个等同于Hogwild!的protocol,但它会锁住在e中的所有变量(在算法1中第4行的for loop的前后)。我们的实验演示了该细粒度的locking会产生不希望看到的速度减慢。

所有实验都以C++进行编码,并运行一个相同的配置:一个dual Xeon X650 CPUs(6 cores x 2超线程)机器,它具有24GB的RAM,software RAID-0超过7, 2TB Seagate Constellation, 7200RPM disks。kernel为Linux 2.6.18-128. 我们使用的内存不超过2GB。所有训练数据都存储在一个7-disk raid 0上。我们实现了一个定制的文件扫描器来演示从磁盘将数据集读取到共享内存的速度。这允许我们从raid读取的速率达到接近1GB/s。

所有的实验均使用一个constant stepsize ,它在每次整个训练集pass后会通过一个因子进行衰减。我们使用20个这样的passes运行所有的实验,尽管更少的epochs通常就能达到收敛。我们的结果表明,对于learning rate 收敛的最大值,我们会使用的吞吐量。我们注意到,结果与更大范围 pairs看起来相似,所有这三种并行化schemes的train erros和test errors都在相互很小的误差内。在分类问题会在第2节描述。

Sparse SVM。我们在Reuters RCV1数据集上测试了我们的sparse SVM实现,使用二分类任务CCAT。它具有804414条样本,划分为:23149训练样本,781265测试样本,存在47236个特征。我们在我们的实验中交换了训练集和测试集,以演示并行多核算法的可扩展性。在本例上,,Hogwild中大值通常会产生一个badcase。在图3a中,我们看到,Hogwild可以达到3倍加速,而RR会随着线程的增加而变差。确实,对于快速梯度,RR要比顺序实现(serial implement)还差。

图3: 对于不同(a) RCV1 (b) Abdomen (c)DBLife,总CPU时间 vs. 线程数

对于该数据集,我们也实现了在[30]中的方法,它会以并行并对输出求平均方式运行多个SGD。在图5b中,我们展示了跨并行线程并在每个pass结尾进行ensemble求平均的方式的train error。我们注意到,线程只在计算的最后需要通信,每个并行线程会在每个pass中接触到每条数据样本。因而,10线程会比顺序版本(serial version)运行10倍(更多)的梯度计算。这里,不管是serial版本还是10个实例的版本,error是相同的。我们可以在该问题上下结论,并行求平均的scheme并没有优点。

矩阵补全(Matrix completion)。我们在三个非常大的matrix比赛问题中运行Hogwild!。Netflix Prize数据集具有17770行,480189列,以及100198085个条目。KDD Cup 2011(task 2)数据集具有624961行,1000990列,252800275个条目。我们也人工生成了一个低秩矩阵,它的rank=10, 1e7个行和列,2e9个条目。我们把该数据集称为”Jumbo”。在人工生成的样本中,都在1e-7. 这些值与都在1e-3阶上的真实数据集形成鲜明对比。

图4:

图5a展示了这三个数据集在使用Hogwild!的加速。注意,Jumbo和KDD数据集不能完全装载进(fit in)我们分配的内存,但即使从磁盘读取数据时,Hogwild都能获取一个接近线性的加速。Jumbo会花费2个半小时来完成。图4展示了Hogwild!、AIG和RR在三个矩阵补全(Matrix completion)数据集上的实验结果。与快速计算梯度的实验相似,RR并没有展现出比serial版本的方式有任何提升。事实上,使用10个线程,RR在KDD Cup上会比serial版本慢12%,在Netflix版本上会慢62%。实际上,以合理的时间量完成Jumbo实验是很慢的,而10-way并行化Hogwild!实现可以在3个小时内解决该问题。

图5

Graph Cuts。 我们的第一个cut问题是一个在计算机视觉中很流行的标准图片切分。xxx(略)

如果梯度很慢会怎么样? 在DBLIFE数据集上,当梯度计算很慢时,RR方法会获得一个几乎线性的加速。这抛出了一个问题:对于梯度计算慢的问题,RR是否要胜过Hogwild?为了回答这个问题,我们运行了RCV1实验,并在每次梯度计算时引入一个人工生成的delay来模仿一个慢梯度计算。如图5c所示,我们画出了求解SVM问题所需的wall clock time,我们会对比RR与Hogwild方法的delay。

注意到,Hogwild!会获得一个更大的计算时间减少的收益。当delay为几ms时,两种方法的加速是相同的。也就是说,如果一个梯度花费超过1ms的计算时间,RR会与Hogwild相当(但不是超过)。在该rate上,每个小时只能计算大约100w次SGD,因此,梯度计算必须非常耗时,这时RR方法才有竞争力。

8.结论

我们提出的Hogwild算法利用了在机器学习中的稀疏性,在多种应用上可以达到接近线性的加速。经验上,我们的实验可胜过理论分析。例如,在RCV1 SVM问题上相当大,我们也仍能获得巨大加速。再者,我们的算法允许并行加速,即使当梯度计算非常密集时。

我们的Hogwild scheme可以泛化到:一些变量的出现相当频繁的问题上。我们可以在高度竞争的那些特定变量上,选择不更新。例如,我们可能希望添加一个bias项到我们的SVM上,然后仍运行一个Hogwild scheme,更新bias只需要每上千次迭代时进行。

对于将来的工作,我们有兴趣枚举那些允许没有冲突的并行梯度计算的结构。也就是说,可能会与SGD迭代有偏差,以便完全避免处理器间的内存竞争。例如,最近的工作【25】提出了一个在matrix比赛问题中的SG的biased ordering,来完全避免处理器间的内存竞争。关于如何将该方法泛化到其它结构上,以便更快的机器学习计算,这样的调查也在开展中。

参考

1.https://arxiv.org/pdf/1106.5730v2.pdf