本文主要是结合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

参考

本文主要译自Tomas Mikolov、Jeffrey Dean等人的.

Abstract

最近介绍的continuous Skip-gram model是一个很有效的方法,用于学习高质量的分布式向量表示,它可以捕获大量精准的语法结构和语义词关系。在该paper中,我们介绍了许多种扩展,用来改进向量的质量和训练速度。通过对高频词进行subsampling,我们可以获得极大的速度提升,也可以学到更常规的词表示。我们也描述了在hirearchical softmax之外的一种简单的备选方法:negative sampling。

词向量表示的一个限制是,它不区分词顺序(word order),它们不能表示常用短语。例如,”Canada”和”Air”的意思,不能简单的组合在一起来获取”Air Canada”(加拿大航空)。受该示例的启发,我们描述了另一种方法来寻找文本中的短语,并展示了如何在上百万的句子中学习到好的向量表示。

介绍

词在向量空间上的分布式表示(distributed representations),通过将相似的词语进行群聚,可以帮助学习算法在nlp任务中完成更好的性能。词向量表示的最早应用可以追溯到1986年Rumelhart, Hinton等人提的(详见paper 13). 该方法用于统计语言建模中,并取得了可喜的成功。接下来,应用于自动语音识别和机器翻译(14,7),以及其它更广泛的NLP任务(2,20,15,3,18,19,9)

最近,Mikolov(8)提出了Skip-gram模型,它是一个高效的方法,可以从大量非结构化文本数据中学到高质量的词向量表示。不同于大多数之前用于词向量学习所使用的神经网络结构,skip-gram模型(图1)不会涉太到稠密矩阵乘法(dense matrix multiplications)。这使得学习极其有效率:一个优化版的单机实现,一天可以训练超过10亿个词。

使用神经网络的词向量表示计算非常有意思,因为学习得到的向量显式地编码了许多语言学规律和模式。更令人吃惊的是,许多这些模式可以被表示成线性变换(linear translations)。例如,比起其它向量,向量计算vec(“Madrid”)-vec(“Spain”)+vec(“France”)与vec(“Paris”)的结果更接近(9,8)。

本文中,我们描述了一些原始skip-gram模型的扩展。我们展示了高频词的subsampling,在训练期间可以带来极大的提升(2x-10x的性能提升),并改进了低频词的向量表示的精度。另外,我们提出了一种Noise Contrastive Estimation (NCE) (4)的变种,来训练skip-gram模型,对比于复杂的hierachical softmax,它的训练更快,并可以为高频词得到更好的向量表示。

词向量表示受限于它不能表示常用短语,因为它们不由独立的单词组成。例如, “Boston Globe”(波士顿环球报)实际是个报纸,因而它不是由“Boston”和”Globe”组合起来的意思。因此,使用向量来表示整个短语,会使得skip-gram模型更有表现力。因此,通过语向量来构成有意义的句子的其它技术(比如:递归autoencoders 17),可以受益于使用短语向量,而非词向量。

从基于词的模型扩展成基于短语的模型相当简单。首先,我们使用数据驱动的方法标识了大量的短语,接着我们在训练中将这些短语看成是独自的tokens。为了评估短语向量的质量,我们开发了一个类比原因任务(analogical reasoning tasks)测试集,它同时包含了词和短语。我们测试集中的一个典型的类比对(analogy pair):“Montreal”:“Montreal Canadiens”::“Toronto”:“Toronto Maple Leafs”。如果与vec(“Montreal Canadiens”)-vec(“Montreal”)+vec(“Toronto”)最接近的向量是:vec(“Toronto Maple Leafs”),那么我们可以认为回答是正确的。

译者注1:

  • Montreal: 蒙特利尔(城市)
  • Montreal Canadiens: 蒙特利尔加拿大人(冰球队)
  • Toronto: 多伦多(城市)
  • Toronto Maple Leafs: 多伦多枫叶队(冰球队)

译者注2:

英文是基于空格做tokenized的. 常出现这个问题。

最后,我们再描述skip-gram模型的另一个有趣特性。我们发现,向量加法经常产生很有意思的结果,例如:vec(“Russia”)+vec(“river”)的结果,与vec(“Volga River”)接近。而vec(“Germany”)+vec(“capital”)的结果,与vec(“Berlin”)接近。这种组成暗示着,语言中一些不明显的程度,可以通过使用基本的词向量表示的数据操作来获取。

2.Skip-gram模型

Skip-gram模型的训练目标是,为预测一个句子或一个文档中某个词的周围词汇,找到有用的词向量表示。更正式地,通过给定训练词汇w1,w2,w3,…,wT, Skip-gram模型的目标是,最大化平均log概率:

(1)

其中,c是训练上下文的size(wt是中心词)。c越大,会产生更多的训练样本,并产生更高的准确度,训练时间也更长。最基本的skip-gram公式使用softmax函数来计算:

(2)

其中,vw和v’w表示w的输入向量和输出向量。W则是词汇表中的词汇数。该公式在实际中不直接采用,因为计算与W成正比,经常很大(10^5-10^7次方)

2.1 Hierarchical Softmax

略,详见另一篇。

2.2 Negative Sampling

Hierarchical Softmax外的另一可选方法是Noise Contrastive Estimation(NCE),它由Gutmann and Hyvarinen(4)提出,将由Mnih and Teh(11)用于语言建模中。NCE假设,一个好的模型应该能够通过logistic regression从噪声中区分不同的数据。这与Collobert and Weston(2)的hinge loss相类似,他通过将含噪声的数据进行排序来训练模型。

而NCE可以近似最大化softmax的log概率,Skip-gram模型只关注学习高质量的向量表示,因此,我们可以自由地简化NCE,只要向量表示仍能维持它的质量。我们定义了Negative sampling(NEG)的目标函数:

在Skip-gram目标函数中,每个项都被替换掉。该任务是为了区分目标词wo,以及从使用logistic回归的噪声分布Pn(w)得到的词。其中每个数据样本存在k个negative样本。我们的试验中,对于小的训练数据集,k的值范围(5-20)是合适的;而对于大的数据集,k可以小到2-5。Negative sampling和NCE的最主要区分是,NCE同时需要样本和噪声分布的数值概率,而Negative sampling只使用样本。NCE逼近最大化softmax的log概率时,该特性对于我们的应用不是很重要。

NCE和NEG都有噪声分布Pn(w)作为自由参数。对于Pn(w)我们采用了一些不同选择,在每个任务上使用NCE和NEG,我们尝试包含语言建模(该paper没提及),发现unigram分布U(w)提升到3/4幂(如:)时,胜过unigram和uniform分布很多!

2.3 高频词的subsampling

3.结果

该部分我们评估了Hierarchical Softmax(HS), Noise Contrastive Estimation, Negative Sampling和训练词汇的subsampling。我们使用由Mikolov引入的analogical reasoning task进行评估(8)。该任务包含了类似这样的类比:s“Germany” : “Berlin” :: “France” : ?。通过找到这样的一个向量x,使得在cosine距离上,vec(x)接近于vec(“Berlin”)-vec(“Germany”)+vec(“France”)。如果x是”Paris”,则该特定示例被认为是回答正确的。该任务有两个宽泛的类别:syntactic analogies:句法结果的类比(比如: “quick” : “quickly” :: “slow” : “slowly”),以及semantic analogies: 语义类比(比如:国家与城市的关系)。

对于训练Skip-gram模型来说,我们已经使用了一个大数据集,它包括许多新文章(内部Google数据集,超过10亿单词)。我们抛弃了训练集中在词汇表中出现次数不足5次的词汇,这样产生的词汇表大小为:692k。在词类比测试中,多种Skip-gram模型的性能如表1。在analogical reasoning task上,该表展示了Negative Sampling的结果比Hierarchical Softmax效果要好,并且它比Noise Contrasitive Estimation的效果也略好。高频词的subsampling提升了好几倍的训练速度,并使得词向量表示更加精准。

仍有争议的是,skip-gram模型使它的向量更适合linear analogical reasoning,但Mikolov的结果(8)也展示了在训练数据量极剧增加时,由标准的sigmoidal RNN(非线性)可以在该任务上获得极大的提升,建议,对于词向量的线性结果,非线性模型同样可以有很好的表现。

4.学习短语

在前面的讨论中,许多短语具有特定的意义,它不是单个词的含义的简单组合。为了学习到短语的向量表示,我们首先发现,在一些不常见的上下文中,有些词经常共现。例如,“New York Times”和”Toronto Maple Leafs”在训练数据中,被替换成唯一的token,但另一个bigram:”this is”则保留不做更改。

表2:短语的analogical reasoning task(完整测试集:3218个示例)。目标是使用前三2上计算第4个短语。在该测试集上最好的模型的准确率为72%

这种方法,我们可以产生许多合理的短语,同时也不需要极大增加词汇的size;理论上,我们可以使用所有n-gram来训练Skip-gram模型,但这样很耗费内存。在文本上标识短语方面,之前已经有许多技术提出。然而,对比比较这些方法超出了该paper范围。我们决定使用一种简单的基于数据驱动的方法,短语的形成基于unigram和bigram的数目,使用:

(6)

其中,delta被用于一个打折系数(discounting coefficient),它可以阻止产生过多的包含许多不常见词的短语。bigram的score如果比选择的阀值要大,那么则认为该短语成立。通常,我们会不断降低阀值,运行2-4遍的训练数据,以允许形成包含更多词的更长短语。我们使用一个新的关于短语的analogical reasoning task,来评估短语表示的质量。该数据集在网上是公开的。下载

4.1 短语的Skip-Gram结果

我们使用在前面的试验中相同的新闻数据,我们首先基于训练语料来构建短语,接着我们训练了多个Skip-gram模型,它们使用不同的超参数。在这之前,我们使用了300维的向量,上下文size=5。该设置可以在短语数据集上达到很好的效果,我们快速比较Negative Sampling和Hierarchical Softmax,是否采用高频token的subsampling。结果如表3所示:

表3:Skip-gram在短语类比数据集上的准确率。这些模型在10亿词的新闻数据集上进行训练

为了最大化短语类比任务的准确率,我们增加了训练数据量,使用了另一个包含330亿词汇的数据集。我们使用hierarchical softmax,1000维,上下文为整个句子。模型上的结果,准确率将达到72%。当我们将训练数据集减小到60亿的词汇量时,得到更低的准确率66%,这意味着,数据量的大小是十分重要的。

为了更深理解,不同模型学到的词向量表示的不同,我们人工检查了不同模型下的不常用短语的最近邻词。如表4,我们展示了这样的一个比较样例。前面的结果是一致的,它展示了可以学到的短语最佳向量表示模型是:hierarchical softmax和subsampling。

表4:两个模型下,给定短语,与它们最接近的其它条目

5.加法组合

我们展示了由Skip-gram模型学到的词和短语向量表示,它们展示出一种线性结构,这使得使用向量运算来执行精准的analogical reasoing成为可能。有意思的是,我们发现,Skip-gram表示法展示出了另一种线性结构,它可以将词向量进行element-wise加法组成。该现象见表5.

表5:使用element-wise加法的向量组合。使用最好的skip-gram模型得到的, 与该向量和接近的4个接近的tokens

向量的加法属性可以通过对训练目标进行检查来解释。该词向量与softmax非线性的输入存在线性关系。训练出的词向量用来预测句子周围的词,这些向量可以被看成是,用来表示一个词在特定上下文出现中的分布。这些值与由输出层计算的概率的对数(logP)相关,两个词向量的和(sum)与两个上下文分布的乘积(product)相关联。这里的该乘积是AND函数:两个词向量中都分配了高概率的词,也会得到高概率,否则会得到低概率。因而,如果“Vloga River”在相同的句子中,与”Russian”和”river”出现的很频繁,那么两个词向量的和将产生这样的特征向量,它们与”Vloga River”很接近。

6.目前的词向量表示的比较

之前,有许多作者在基于词向量的神经网络领域工作,并发表了许多模型,可以用于进一步使用和比较:最著名的有Collober和Weston(2), Turian(17),以及Mnih和Hinton的(10). 我们从网上下载了这些词向量, 下载地址。Mikolov(8)已经在词类比任务上评估了这些词向量表示,其中,Skip-gram模型达到了最好的性能和效果。

表6:各种模型比较,空意味着词不在词汇表里.

为了更深地理解学到的向量质量的不同之处,我们提供了表6的比较。这些示例中,Skip-gram模型在一个大的语料上进行训练,可以看到,效果比其它模型好。部分原因是因为模型训练的词料词汇超过300亿个词,是其它数据集的3个数量级。有意思的是,尽管训练集更大,Skip-gram的训练时间复杂度比前面的模型还要短。

参考

- 1.Domain adaptation for large-scale sentiment classi- fication: A deep learning approach

  • 1 Yoshua Bengio, R´ejean Ducharme, Pascal Vincent, and Christian Janvin. A neural probabilistic language model. The Journal of Machine Learning Research, 3:1137–1155, 2003.
  • [2] Ronan Collobert and Jason Weston. A unified architecture for natural language processing: deep neural networks with multitask learning. In Proceedings of the 25th international conference on Machine learning, pages 160–167. ACM, 2008.
  • [3] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Domain adaptation for large-scale sentiment classi- fication: A deep learning approach. In ICML, 513–520, 2011.
  • [4] Michael U Gutmann and Aapo Hyv¨arinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. The Journal of Machine Learning Research, 13:307–361, 2012.
  • [5] Tomas Mikolov, Stefan Kombrink, Lukas Burget, Jan Cernocky, and Sanjeev Khudanpur. Extensions of recurrent neural network language model. In Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on, pages 5528–5531. IEEE, 2011.
  • [6] Tomas Mikolov, Anoop Deoras, Daniel Povey, Lukas Burget and Jan Cernocky. Strategies for Training Large Scale Neural Network Language Models. In Proc. Automatic Speech Recognition and Understanding, 2011.
  • [7] Tomas Mikolov. Statistical Language Models Based on Neural Networks. PhD thesis, PhD Thesis, Brno University of Technology, 2012.
  • [8] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. ICLR Workshop, 2013.
  • [9] Tomas Mikolov, Wen-tau Yih and Geoffrey Zweig. Linguistic Regularities in Continuous Space Word Representations. In Proceedings of NAACL HLT, 2013.
  • [10] Andriy Mnih and Geoffrey E Hinton. A scalable hierarchical distributed language model. Advances in neural information processing systems, 21:1081–1088, 2009.
  • [11] Andriy Mnih and Yee Whye Teh. A fast and simple algorithm for training neural probabilistic language models. arXiv preprint arXiv:1206.6426, 2012.
  • [12] Frederic Morin and Yoshua Bengio. Hierarchical probabilistic neural network language model. In Proceedings of the international workshop on artificial intelligence and statistics, pages 246–252, 2005.
  • [13] David E Rumelhart, Geoffrey E Hintont, and Ronald J Williams. Learning representations by backpropagating errors. Nature, 323(6088):533–536, 1986.
  • [14] Holger Schwenk. Continuous space language models. Computer Speech and Language, vol. 21, 2007.
  • [15] Richard Socher, Cliff C. Lin, Andrew Y. Ng, and Christopher D. Manning. Parsing natural scenes and natural language with recursive neural networks. In Proceedings of the 26th International Conference on Machine Learning (ICML), volume 2, 2011.
  • [16] Richard Socher, Brody Huval, Christopher D. Manning, and Andrew Y. Ng. Semantic Compositionality Through Recursive Matrix-Vector Spaces. In Proceedings of the 2012 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2012.
  • [17] Joseph Turian, Lev Ratinov, and Yoshua Bengio. Word representations: a simple and general method for semi-supervised learning. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 384–394. Association for Computational Linguistics, 2010.
  • [18] Peter D. Turney and Patrick Pantel. From frequency to meaning: Vector space models of semantics. In Journal of Artificial Intelligence Research, 37:141-188, 2010.
  • [19] Peter D. Turney. Distributional semantics beyond words: Supervised learning of analogy and paraphrase. In Transactions of the Association for Computational Linguistics (TACL), 353–366, 2013.
  • [20] Jason Weston, Samy Bengio, and Nicolas Usunier. Wsabie: Scaling up to large vocabulary image annotation. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence-Volume Volume Three, pages 2764–2770. AAAI Press, 2011.

本文主要译自paper 1.

Abstract

神经网络概率语言模型(NPLM)与过去广泛使用的n-gram语言模型相互竞争,甚至偶尔优于后者NPLM最大的缺点是训练和测试时间超长。Morin和Bengio提出了一种层次化语言模型,它会构建一棵关于词的二叉树,它比非层次化的使用专家知识的模型快2个数量级。我们引入了一种快速的层次化语言模型,它使用一种简单的基于特征的算法,可以从数据中自动构建word树。我们接着展示,产生的模型胜过非层次化神经网络模型、n-gram模型。

介绍

统计语言模型的关注点是,构建基于词序列的概率模型。这样的模型可以被用于区分可能的序列与不可能的序列,广泛用于语音识别,信息检索,机器翻译。大多数统计语言模型都基于Markov猜想:一个词的分布只依赖于 在它之前出现的固定数目的词。该猜想明显是错误的,但它很简洁方便,因为它将固定长度的词序列的概率分布建模问题,缩减成:给定前面固定数目的词(称为上下文:context),建模下一个词的分布。此处,我们使用:$P(w_n | w_{1:n-1})$来表示分布,wn是下一个词, $ w_{1:n-1} $表示上下文$(w_1,..,w_{n-1}) $。

目前n-gram模型是最流行的统计语言模型,因为简单,并且性能很好。这些模型的条件概率表$ P(w_n | w_{1:n-1}) $,通过统计训练数据中的n元组,并进行归一化进行估计。因为n元组的数据是n的指数级,对raw counts进行平滑会达到很好的性能。n-gram模型有许多平滑方法,详见paper 2. 尽管n-gram模型有许多复杂的平滑方法,n-gram模型很难利用大量上下文,因为数据的稀疏性问题很严重。这种现象的主要原因是,经典的n-gram模型是本质上有界的条件概率表,里面的条目都是相互独立的。这些模型不会利用这样的事实:即相似的词常出现在相似的上下文中,因为它们没有相似性的概率。基于分类的n-gram模型(paper 3)主要解决该问题,通过将词和上下文,基于使用模式聚类到分类中,使用这些分类信息来提升泛化。它会提升n-gram的性能,这种方法引入了严格死板的相似性,因为每个词很典型,都属于确定的某个类。

另一种可选的、更灵活的抵消数据稀疏性问题的方法是,将每个词使用一个real-valued的特征向量,它会捕获该特性,以便相似的上下文中的词,具有相似的特征向量。接着,下一个词的条件概率可以被建模成一个关于上下文词和下一个词的平滑函数。这种方法提供了自动平滑,因为对于一个给定的上下文,相似的词可以保证分配到相似的概率。同样的,相似的上下文现在也可能具有相似的表示,并会生成对下一个词相似的预测。大多数基于该方法的模型,使用一个前馈神经网络(feed-forwark NN),将上下文词汇的特征向量映射到下一个词的分布上。这种方法的可能最好模型是神经网络语言模型NPLM(paper 4),在100w词级别的语料上,它胜过n-gram模型。

层次化神经网络语言模型

NPLM的主要缺点是,这样的相类似模型,训练和测试时间很慢。因为下一个词的概率计算,需要显式对词汇表中所有词进行归一化,对于给定下一个词的概率计算开销,以及对于在下一个词之上的所有分布的计算开销,事实上两者几乎一样:它们会花费关于词汇表size的线性时间开销。由于在这样的模型上,计算精确的梯度,需要重复计算给定上下文的下一个词的概率,通过增加概率来更新模型参数,训练时间与词汇表size成线性关系。通常,自然语言数据集包含着上万的词汇,这意味着即使以最简单方式训练这种类NPLM模型,在实际中的计算开销仍过大。一种加速该过程的方法是,使用专门的重要性sampling过程,来逼近要学习所需的梯度(paper 5)。然而,该方法可以本质上加速训练时间,测试时间的开销依然很快。

我们引入了层次化NPLM(paper 6),对比普通的NPLM,它在训练和测试的时间复杂度均做到了指数级的衰减。通过二叉树替代NPLM中非结构化的词汇表,可以表示成一个层次化的词汇表词簇。每个词对应于树上的叶子节点,可以由顶点到叶子节点的路径唯一确定。如果N是词汇表的词数,并且树是一棵平衡树,任何词都可以由一串O(log N)二分决策来指定,它会指定两个子节点,当前节点可以访问到下一节点。该过程将N-way选择替换成一串O(log N)的二分选择。在概率术语中,N-way归一化,可以替换成一串O(log N)的局部(二分)归一化。结果上,词汇表中的词分布,可以通过提供访问左子节点的概率来指定。在层次化NPLM中,这样NPLM方式的局部概率的计算:采用一个特征向量作为上下文词汇,同时给当前节点的一个特征向量作为输入。下一个词的概率,由该词所对应路径的二分决策的概率指定。

当数据集包含上百万的词时,该模型的表现优于基于分类的3-gram,但比paper 6中的NPLM表现差。这种层次化NPLM模型,比普通的NPLM快2个数量级。这种方法的主要限制,主要是用于构建word树的过程。该树可以从WordNet IS-A分类体系开始,通过结合人工和数据驱动处理,并将它转换成一个二叉树。我们的目标是,将该过程替换成从训练数据中自动构建树,不需要任何专家知识。我们也探索了使用树(里面的词汇至少出现一次)的性能优点。

log-bilinear model

我们使用log-bilinear语言模型(LBL:Paper 7)作为我们层次化模型的基础,因为它的性能十分出色,并且很简洁。类似于所有神经网络语言模型,LBL模型将每个词表示成一个real-valued的特征向量。我们将词w的特征向量表示成:$ r_w $,所有词的特征向量组成矩阵R. 模型的目标:给定上下文$ w_{1:n-1} $,预测下一个词$w_n$。我们将要预测下一个词的的特征向量表示成$ \hat{r} $,它可以通过对上下文词汇的特征向量进行线性组合得到:

公式一:$ \hat{r}=\sum_{i=1}^{n-1}C_{i}r_{w_i} $

其中,$C_i$是权重矩阵,它与位置i的上下文有关。接着,要预测的特征向量,和词汇表中每个词的特征向量,两者间的相似度通过内积计算。该相似度接着进行指数化,归一化,从而获取下一个词的分布:

公式二:

这里的$ b_w $是词w的偏置bias,它被用于捕获上下文独立的词频。

注意,LBL模型可以被解释成一种特殊的前馈神经网络,它只有一个线性隐层,以及一个softmax输出层。该网络的输入是上下文词汇的特征向量,而从隐层到输出层的权重矩阵,则可以简单通过特征向量矩阵R指定。该向量隐单元的激活,对应于下一个词的预测特征向量。不同于NPLM,LBL模型需要计算隐层激活,每次预测只计算一次,隐层不存在非线性。虽然LBL模型很简单,但表现很好,在相当大的数据集上,优于NPLM和n-gram模型。

4.层次化log-bilinear模型

我们的层次化语言模型基于该模型. 该模型的特点是,使用log-bilinear语言模型来计算每个节点的概率,并处理树中每个词多次出现率。注意,使用多个词出现率的思想,由papar 6提出,但它并没有实现。

HLBL的第一部分是:一棵关于词作为叶子的二叉树。接着,我们假设词汇表中每个词对应一个叶子结点。接着,每个词可以通过从树顶点到叶子节点的路径唯一指定。该路径本身可以编码成一串二进制字符串d(每个节点会做二分决策),$ d_i=1 $对应于:访问当前节点的左子节点。例如,字符串”10”表示的是:从顶点,到左子节点,然后到右子节点。这样,每个词可以被表示成一串二进制码。

HLBL模型的第二部分是:每个节点会做出二分决策的概率模型,在我们的case中,使用了一个LBL模型的改进版本。在HLBL模型中,和非层次化的LBL类似,上下文词汇表示成real-valued特征向量。树上的每个非叶子节点,也具有一个特征向量与它相关联,它用于区分词是在该节点的左子树还是在右子树。不同于上下文词汇,被预测的词,被表示成使用它们的二进制码。然而,这种表示相当灵活,因为编码中的每种二进制数字,相当于该节点做出的决策,它依赖于节点的特征向量。

在HLBL模型中,给定上下文,下一个词是w的概率,就是由该词编码指定的一串二分决策的概率。因为在一个节点上做出一个决策的概率,只取决于要预测的特征向量(由上下文决定),以及该节点的特征向量,我们可以将下一个词的概率表示成二分决策的概率乘积:

公式三:$ P(w_{n}=w | w_{1:n-1}) = \prod P(d_{i} | q_i,w_{1:n-1}) $

di是词汇w的第i位数字编码,qi是编码所对应路径上第i个节点的特征向量。每个决策的概率为:

公式四:$ P(d_{i}=1 | q_{i},w_{1:n-1})= \delta (\hat{r}^T q_{i}+b_{i}) $

其中,$ \delta(x) $是logistic函数,而$ \hat{r} $是使用公式一计算得到的要预测的特征向量,在该公式中的bi是该节点的偏置bias,它可以捕获当离开该节点到它的左子节点上的上下文独立的趋势。

D(w)表示词汇w所对应的一串编码集合。每个词允许多个编码,可以更好地预测词,具有多种含义或者多种使用模式。每个词使用多种编码,也可以使它更容易将多种不同的词层次结构,组合成单一的结构。这也反映了一个事实:没有单一的层次结构可以表示词之间的所有关系。

使用LBL模型(而非NPLM)来计算局部概率,允许我们避免计算隐层的非线性,这可以让我们的层次模型,比层次化NPLM模型更快作出预测。更重要的是,对于O(log N)个决策中的每一个,层次化NPLM都需要计算一次隐层激活,而HLBL模型只在每次预测时计算一次要预测的特征向量。然而,在LBL模型中,单个二分决策的概率计算的时间复杂性,仍然是特征向量维度D的二次方,这会使高维特征向量的计算开销很高昂。我们可以使时间复杂度与D是线性关系,通过将权重矩阵Ci限制为对角阵。注意,对于上下文size=1的情况,该限制条件不会减小模型表示的幂(power),我们相信,这种损失(loss),多于可以通过使用更复杂的树更快的训练时间的补偿。

HLBL模型可以通过最大化(带罚项的)log似然进行训练。因为下一个词的概率只依赖于上下文权重、上下文词汇的特征向量、以及从顶点到词汇所在叶子节点路径上的节点的特征向量,在每个训练case上,只有一小部分(log级别)的参数需要更新。

参考