BlazingText介绍

Reading time ~1 minute

Amazon在hogwild、hogbatch之后,提出了《BlazingText: Scaling and Accelerating Word2Vec using Multiple GPUs 》,利用多GPU来加速word2vec的训练。

介绍

Word2vec是流行的算法。原始google c实现、以及facebook fastText可以利用多核cpu架构来并行化。还有一少部分实现方式则利用GPU并行化,但会牺牲accuracy和可扩展性。本paper提出了BlazingText,一个使用CUDA高度优化的word2vec实现,可以利用多GPU进行训练。BlazingText可以在8GPU上达到43M words/sec的训练速度,达到了8线程CPU实现的9倍,并且对embeddings的质量影响很小。

word2vec的最优化通过SGD完成,它会进行迭代式求解;在每一个step,会选取一个词对(pair of words):一个输入词和一个目标词,它们来自于window或一个随机负样本。接着根据选中的两个词来计算目标函数的梯度,然后基于该梯度值更新两个词的词表示(word representations)。该算法接着使用不同的word pair来处理下一次迭代。

SGD的一个主要问题是,它的顺序性;这是因为它在这一轮迭代的更新、与下一轮迭代的计算之间存在着依赖关系(他们可能遇到相同的词表示),每一轮迭代必须潜在等待前一轮迭代的更新完成。这不允许我们使用硬件并行资源。

然而,为了解决上述问题,word2vec使用Hogwild,它使用不同线程来并行处理不同的word pairs,并忽略任何在模型更新阶段中发生的冲突。理论上,对比起顺序运行,这会让算法的收敛率下降。然而,对于跨多线程更新不可能会是相同的词的这种情况,Hogwild方法已经得到验证能运行良好;对于大词汇表size,冲突相对较少发生,收敛通常不受影响。

Hogwild方法在多核架构上的成功,使得该算法利用GPU成为可能,GPU比CPU提供更强的并行化。在该paper中,我们提出了一种有效的并行化技术来使用GPU加速word2vec。

在深度学习框架中使用GPU加速,对于加速word2vec来说并不是好选择[6]。这些框架通常更适合于“深度网络(deep networks)”,它们的计算量主要由像卷积(conv)以及大矩阵乘法(large matrix multiplications)等重型操作主宰。而word2vec则是一个相对浅层的网络(shallow network),每一个training step包含了一个embedding lookup、梯度计算(gradient computation)、以及最终为word pair进行权重更新(weight updates)。梯度计算和更新涉及很小的点乘操作,使用cuDNN[7]或cuBLAS[8]并不能受益。

深度学习框架的限制导致我们探索CUDA C++ API。我们从头设计了训练算法,以便最优利用CUDA多线程能力,并且防止对GPU并行化的过度利用,从而不伤害输出的accuracy。

最终,我们开发了BlazingText,它处理文本语料的速率能达到数百万 words/sec,我们演示了使用多GPU来执行数据并行训练的可能性。我们对比了开源的工具与BlazingText之间的benchmark。

2.word2vec模型

word2vec有两种不同的模型架构:Contextual Bag-Of-Words (CBOW)以及Skip-Gram with Negative Sampling (SGNS) 。CBOW的目标函数是由给定上下文去预测一个词,而Skipgram则给定一个词去预测它的上下文。实际上,Skipgram会给出更好的效果,我们会在下面描述它。

给定一个大型训练语料,它由一个words序列组成。skipgram模型的目标是最大化log似然:

其中,T是词汇表size,上下文是围绕的词的集合。给定所观察到的一个上下文词的概率可以使用上述的词向量进行参数化。假设我们给定一个得分函数s,它将(word, context)的pairs映射到得分。定义一个上下文词的概率的一个可能的选择是:

然而,这样的模型不适合我们的case中,因为它意味着,给定一个词,我们只能预测一个上下文词

预测上下文词(context words)的问题可以通过构建独立的二分类任务集合来替代。接着,该目标是独立地预测上下文词是否出现。对于在位置t处的词,我们会考虑所有的上下文词作为正例,并从字典中随机抽样负样本。对于一个选中的上下文位置c,使用binary logistic loss,我们可以获取以下的negative log-likelihood:

其中是从词汇表中抽取的负样本的一个集合。通过表示logistic loss function l:,我们可以重写目标函数:

对于在词和它的一个上下文词之间的scoring function s的一个天然参数化方案是,使用词向量(word vectors)。假设在词汇表中的每个词w,定义两个向量。这两个向量有时被称为是输入向量(input vector)和输出向量(output vector)。特别的,我们的向量分别对应于词。接着,score可以使用在该词与上下文向量间的点乘(dot product)来表示:

3.相关工作

一些已经存在的word2vec系统被限制在只能在单机CPU上运行,而一些使用多核cpu多节点来加速word2vec的方式则进行分布式数据并行训练。这些方法包含了Spark MLLib和Deeplearning4j。这些系统在每轮iteration后依赖reduce操作在所有executors间同步模型。将所有的word vectors跨节点广播(broadcast)的这种方式限制了可扩展性,因为通常网络带宽只比CPU内存要低一阶。另外,模型的accuracy会大幅下降,因为使用了更多节点来增加吞吐。

Intel的工作[11]展示了通过基于minibatching和shared negative samples的scheme可在多CPU节点上进行极强地扩展。该方法将level-1 BLAS操作转换成level-3 BLAS矩阵乘法操作,从而有效地利用现代架构的向量乘法/加法指令(vectorized multiply-add instructions)。然而,该方法仍不能利用GPUs,而且他们的实现只能在Intel BDW和KNL处理器上扩展良好,而这些处理器比GPU要昂贵,不会被主流的云服务平台所提供。借鉴他们提出的思想,我们可以通过一个minibatch共享negative samples,并使用高度优化的cuBLAS level-3矩阵乘法核(matrix multiplication kernels),但由于要进行乘法操作的矩阵size很小,CUDA核启动(kernel-launches)的开销会剧烈降低性能和可扩展性。

其它一些工作[12,13]已经利用像tensorflow, keras, theano等深度学习库,但展示出的性能要比fasttext的CPU实现要慢。由于word2vec的一轮迭代计算并不非常密集,需要使用一个很大的batch size来完全利用GPU。然而,对训练数据进行mini-batching会急剧降低收敛率,而如果batch size=1, 训练又会非常慢。

4. 使用CUDA进行GPU并行化

由于GPU架构比CPU cores提供了更强的(多好多阶)并行机制,word2vec看起来能很好地使用GPU进行加速,算法本身展示了可以通过异步SGD(asynchronous SGD)或Hogwild进行很好的并行化。然而,如果使用更多的并行化,不同线程之间在读取和更新词向量时可能会发生冲突,从而对accuracy产生大幅下降。因而,必须仔细考虑,如何在并行化级别上和同步机制间做好权衡。

深度学习框架没有像CUDA C++ API那样,提供在GPU的可扩展性与并行化之间的细粒度控制。有必要对算法设计进行大幅重构,从而允许最大化并行吞吐,而强制同步会阻止accuracy的降低。我们控制了以下两种方法来基于CUDA实现。

4.1 每个词一个线程块(one thread block per word)

原始的word2vec实现按顺序处理一个句子,例如:对于中心词,它会考虑围绕中心词作为目标词的window size(ws)中的所有词,这意味着在所有的词向量,会在一个step中获得更新。相似的在下一step中,对于中心词,在范围内的所有向量都将被更新。这意味着,当处理一个句子时,一个词向量可以被修改2ws+1次,理想的,每个连续的step都应使用被前一step修改更新后的向量(updated vectors)。

从头设计一个CUDA程序需要我们对网格结构(grid)和线程块(thread blocks)做总体规划。在相同线程块中的线程可以相互进行同步,但如果属于不同线程块的线程不能相互通信,使得线程块相互独立。在该方法中,我们选择为每个词分配一个线程块,在一个块内的线程数可以是乘以32, 相当有效。随着在一个块内的线程数与向量维度(通常100)越来越接近,每个线程会映射到一个向量维度上,并做element-wise乘法操作。这种单独的乘法接着使用一个reduce kernel来计算任意2个给定向量间的点乘来进行有效求和。我们探索了一些并行reduction技术,最终使用采用一个高度优化过的completely unrolled reduce kernel。该算法设计采用并行机制能达到峰值,因为每个词会通过一个线程块进行独立处理,在线程块中的线程只有当执行reduce操作时会进行同步(synchronize)。然而,该方法会有一个主要缺点,它能极大地破坏embeddings的质量。不同的线程块可以独立的修改词向量,没有同步机制,它对于accuracy是有害的,因为随着窗口沿着句子进行滑动,每个向量可以更新2w+1次。这会产生大量线程覆盖写(overwrites)和非最新读取(stale reads)。

4.2 每个句子一个线程块

在之前章节讨论过,没有任何同步机制的词向量更新,可以充分利用CUDA并行机制,但是会由于竞争条件(race conditions),会降低embeddings的accurary。随着窗口沿着句子滑动,当处理后一个词时,应使用前面已经更新(updated)的词向量。因而,为了解决顺序依赖(sequential dependency),与前面的方法类似,该方法会将每个句子映射到一个CUDA线程块上,它会将该向量的每一维映射到一个线程上。因此,不同线程块相互并行处理句子,而在一个句子中,线程块会根据词进行循环来顺序更新向量。该方法仍会导致一些竞争条件(race conditions),但由于不同句子通常不会有许多词相同,它实际上不会造成收敛问题。

由于文本语料对于驻在GPU内存中来说可能很大,数据从磁盘到GPU中会流式化(streamed),并且许多句子会进行batch化,以分摊数据在CPU和GPU间传输的开销。为了评估accuracy和throughput间进行平衡,线程块、或者句子被并行处理的最优化数目,通过经验选择。并发处理越多勉励子,会增加throughput,但会产生accuracy的降低,因为不同线程块更新相同的词向量的机率会增加。

一些其它的最优化(optimizations),可以使该方法更有效。如果kernel的执行时间比数据传输时间要少,那么GPU会空闲等待下一batch的句子。为了避免这种情况,我们尝试通过使用多CPU线程和CUDA streams,将数据传输和在GPU上进行kernel execution的过程进行重叠(overlap),它允许数据传输到GPU时仍在忙着运行kernels,这样GPU时间不会空闲。我们使用多CPU线程来从磁盘读取数据,并准备下一batch的句子,它可以使用多个CUDA streams来并发传输数据给GPU。

我们将在第5节描述上述方法的实验。

4.3 在多GPU上的分布式训练

在多GPU分布式系统上扩展BlazingText是很关键的,因为在单GPU上训练一些工业界特别大的数据集时(数T),它仍可能花费数天时间。为了扩展BlazingText,我们探索了不同的分布式训练范式——模型并行化(model parallelism) 和 数据并行化(data parallelism)。由于向量维度通常很小,点乘的规模也不会很大,因而将向量的不同维量进行分布式,不会带来很多的性能增益。因而,我们使用数据并行化,当使用N个GPU时,我们将数据集等分为N份相等的shards。对于词汇表中的所有词,输入向量和输出向量的模型参数,会被复制到每个GPU上;每个设备接着独立处理它所拥有的数据分区,并更新它的局部模型(local model),然后与其它N-1个GPU周期性同步局部模型(local model)。

数据并行化要解决的主要问题是,如何在GPU间有效进行模型同步。它可以使用NVIDIA的NCCL库[15]来有效解决,该库提供了AllReduce方法,它可以基于GPU网络拓朴以一种最优的方法,来处理在GPU间的peer-to-peer数据传输。如果GPU没有通过相同的PCIe swith或者相同的IOH chip进行连接,那么数据会通过host CPU进行传输。由于模型参数的size可能是数百MB,同步机制可能开销很大,因而决定合理的同步间隔十分重要。频繁的同步将产生更好的收敛,但会减慢训练,反之亦然。出于简洁性,我们选择在每轮迭代后进行同步,并在后续会继续探索更有效的同步机制。

5.实验

我们使用上述提到的方法,为单GPU和多GPU系统进行最优化BlazingText。在本节中,我们会展示throughput(单位:百万 words/sec)和所学到的embeddings的accuracy(在标准word similarity和word analogy test上)。我们会对BlazingText和FastText CPU(没有subword embeddings的版本)实现进行benchmark。

硬件:所有的实验都在AWS p2.8xlarge GPU实例上运行,它具有8个NVIDIA K80 GPU卡,以及Intel Xeon CPU E5-2684 v4@2.3GHz 16核(32线程)。

软件:BlazingText使用C++编写,使用CUDA compiler:NVCC v8.0编译。

训练语料:我们使用两个不同语料进行训练:(1) 来自Wikipedia的包含1700w个词的Text8数据集[16],(2) 一个十亿词的benchmark dataset[17]。

测试集:学到的embedding会在word similarity和word analogy任务上进行评估。对于word similarity,我们使用WS-353[18],它是最流行的测试数据集。它包含了人工审核过的相似word pairs。词表示的评估通过根据cosine相似度对这些pairs进行排序,并使用Spearman’s rank相关系数进行评估。我们使用google analogy dataset来进行word analogy评估。

超参数:对于所有的实验,我们展示了使用CBOW和Skipgram算法(negative sampling)和FastText的缺省参数设置(dim=100,window size=5, sampling threold=1e-4, inital learning rate=0.05)。我们为Text8数据集使用20个epochs,One Billion Words Benchmark则使用10个epochs。

5.1 Throughput

图1

图1和图2展示了BlazingText on GPU和FastText on CPU的throughput以百万 words/sec测量。分别跨多GPU和多CPU运行,分别跑SKipgram和CBOW。当扩展到多GPU时,我们的实现达到了接近线性的加速。使用8个GPU,Skipgram可以达到1.32 亿 words/sec,而CBOW可以达到4.25 亿 words/sec,它比32线程的FastText要快3倍。如表1所示,跨多GPU扩展在accuracy上影响很小,因为我们的实现可以有效利用多GPU架构。随着在throughput和accuracy间进行平衡,我们进一步通过降低同步频率来增加throughput,只要accuracy的下降是可接受的。

图2

5.2 Accuracy

表1

我们评估了从fasttext实现以及我们的实现(随GPU数目不同)中训练得到的该模型,并在表1中展示了他们在word similarity和word analogy任务上的预测效果。为了确保我们的实现可以很好泛化,我们会使用2个不同的语料来训练模型——text8和1B words benchmark。

由于GPU并行化,为了消除随机性,我们运行每个实验多次(n=10),并展示了平均结果。如表1所示,BlazingText展示了在多GPU上的效果与FastText CPU上的效果相近。当使用4GPU时,性能几乎相同,在一些情况下比CPU版本要好。如你所料,预测的效果会随着使用更多GPU而减少,但在可接受范围内。对于相似度评估,使用8 GPUs会达到2%更差的accurary,但会比32 CPU线程超过3倍加速。

对于analogy评估,在多GPU和CPU上的不同更显著。在我们的实验中,我们主要关注可扩展性,因而当扩展到更多GPU时,我们不会增加同步频率。增量同步频率可以维持一个可接受的accuracy,但会在扩展性上可降,导致一个sub-linear scaling。然而,取决于终端应用,可以调整同步频率。

参考

DIN介绍

阿里在KDD 2018上开放了它们的方法:《Deep Interest Network for Click-Through Rate Prediction》, 我们来看下:# 背景在电商网站上,比如:阿里巴巴,广告是天然的商品。在本paper的剩余部分,如果没有特别声明,我...… Continue reading

淘宝embedding介绍

Published on November 13, 2018

airbnb embedding介绍

Published on November 02, 2018