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。然而,取决于终端应用,可以调整同步频率。

参考

在各种类型的DNN漫天飘的时代,周老师等提出了gcForest算法。以下是论文核心部分的介绍:

3. gcForest算法

gcForest算法引入了cascade forest结构,以及multi-grained scanning。

3.1 cascade forest结构

DNN中的表征学习几乎全依赖于对原始特征(raw features)进行layer-by-layer的处理。受该点的启发,gcForest使用了一个层叠(cascade)结构,如图2所示,每一级(level)cascade会接受由先前级(preceding level)处理后的信息,然后输出它的结果到下一级(next level)中。

图2:cascade forest结构。假设,cascade的每一级(level)只包含两个random forest(黑色)以及两个completely-random tree forests(蓝色)。假设要预测三个类;这样,每个forest将输出一个三维的分类向量,接着将他们串联起来对原始特征进行重新表征( re-representation)。

每一级是一个决策树森林的ensemble(比如:一个ensemble of ensembles)。此处,我们引入了不同类型的forests来增强diversity,因为对于ensemble的构造来说diversity至关重要。出于简洁性,这里我们使用完全随林树森林(completely-random tree forests)以及两个随林森林(random forest)。每个completely-random tree forests只包含500个完全随机的树,通过对该树的每个节点上做split来随机选择一个feature、完全生长直到纯叶子(pure leaf:每个叶子节点只包含相同类的样本)来生成。相似的,每个随机森林包含了500棵树,通过随机选择个特征作为候选(candidate),并选择对于split后满足最好gini系数的候选(d为输入特征数)。每个forest上的树数目是一个超参数,会在后面1.3描述。

给定一个样本,每个forest为它将生成一个类分布的估计:通过统计不同分类训练样本在叶子节点上的百分比,接着在同一forest上对所有树做平均,如图3所示,其中红色会高亮出样本落到叶子节点的path。

图3: 类向量生成的展示。在叶子节点上不同的标记表示了不同的分类

估计得到的类分布(class distribution)形成了一个类向量(class vector),接着将它们与原始的特征向量进行串联作为cascade下一级的输入。例如,假设有三个类,接着,4个forests的每个都会产生一个三维的类向量;接着,下一级cascade会多接收12个(3x4)扩张特征。

注意,这里我们采用了类向量的最简形式,例如:样本落到的叶子节点上的类分布。结果表明,少量扩展的特征可以传达非常有限的扩张信息,当原始特征向量很高维时很可能被淹没。我们将在实验中展示,这样简单的特征扩展其实是有好处的。预期上如果有更多的扩展特征会收到更大的收益。实际上,显然更多特征可以被合并进去,强如:父节点的类分布表示着先验分布(prior distribution),兄弟节点(sibling nodes)表示着互补分布(complementary distribution)。

为了减小overfitting的发生,由每一个forest生成的类向量通过k-fold交叉验证产生。实际上,每个样本被用于K-1次训练,产生k-1个类向量,接着求平均产生最终的类向量作为下一级的扩展特征。在新一级后,整体cascade的效果会通过验证集被评估,如果没有大的效果增益,训练过程会终止;cascade levels的数目会被自动决定。注意,当考虑训练成本、或者有限计算资源时,使用训练误差(training error)而非交叉验证误差(cross-validation error)可以被用于控制cascade的生长。通过对比DNN(它的模型复杂度确定),gcFroest会自适应地决定它的模型复杂度。这允许它能应用于不同规模的训练数据,而非只限于大规模数据。

3.2 Multi-Grained Scanning

DNN在处理特征关系上很强大,例如,CNN在图片数据上很有效(其中原始像素间的空间关系是很重要的);RNN对于序列型数据很有效(其中序列关系很重要)。受它们的启发,gcForest使用滑动窗口(sliding windows)来扫描原始特征。假设有400个原始特征,我们使用100个特征的window size。对于序列数据,可以通过对每隔一个特征进行窗口滑动来生成一个100维的特征向量;总共可以生成301个特征向量。如果原始特征具有空间关系,比如:在400个图片像素上的20x20的panel,接着一个10x10的window可以产生121个特征向量(比如:121 10x10 panels)。所有的特征向量从正负训练样本上被抽取(忽略正负),接着被用于生成像3.1所述的类向量:从相同size的window中抽取的样本会被用于训练一个completely-random tree forest和一个 random forest,接着生成的类向量被串联作为转换后的特征。如图4所示,假设存在3个类和使用100维的window,对应于一个400维的原始特征向量,会产生一个1806维的转换特征向量。

图4: 使用滑动窗口扫描进行feature re-representation。假设存在三个类,原始特征是400维,滑动窗口是100维。

对于从窗口中抽取的样本,我们会简单地为他们分配原始训练样本带有的label。这样,一些label分配本质上是不正确的。例如,假设原始训练样本是一个关于“car”的正样本图像;很明显许多被抽取的样本(extracted instances)不包含一个car,因而它们相当于会被不正确地标记成正样本。该方法实际上是与Flipping Output方法有关:这是一种用于ensemble中增强diversity的典型的输入特征操作法。

图4展示了滑动窗口的一个size。通过使用多个size的滑动窗口,会生成不同粒度的特征向量,如图5所示。

图5: gcForest的整体过程。假设要预测三个类,原始特征400维,使用三个不同size的滑动窗口。

图5归纳了gcForest的整体流程。对于m个训练样本,一个100个特征size的窗口会生成一个 (301 x m) 的100维训练样本的数据集。这些数据会被用于训练一个completely-random tree forest和一个random forest,每一个包含了500 trees。如果要预测三个类,会获得3.1节中描述的一个1806维的特征向量。转换的训练集接着被用于训练第一阶段(1st-grade)的cascade forest。

相类似的,对于每个原始的训练样本,size为200和300个特征的滑动窗口会分别生成1206维和606维的特征向量。转换后的特征向量,会与由前一级生成的类向量一起扩展,接着被用于训练第二阶段(2nd-grade)、第三阶段(3nd-grade)的cascade forests。该过程会重复,直到验证集效果收敛。换句话说,最终模型实际上是一个cascade of cascades,其中每个cascade包含了许多级(level),每个level对应于一个粒度的scaning,例如:第一个cascade包含了从Level $ 1_A $到Level $ 1_C $ (A、B、C)三个level,如图5所示。注意,对于不同的任务,如果计算资源允许的话,用户可以尝试更多粒度。

给定一个测试样本,它会经过multi-grained scanning过程来得到相应的转换后的特征表示,接着经过cascade直到最后一个level。最终的预测会通过对最后一个level聚合4个3维类向量,使用聚合的最大值来得到最终分类。

表1总结了DNN和gcForest的超参数,其中,实验中使用了缺省值。

表1: 超参数和缺省值。粗体高亮超参数具有相当大的影响;“?”表示缺省值未知,或者对于不同的任务需要不同的设置

4.实验

4.6 Multi-Grained Scanning的影响

为了研究cascade forest structure和multi-grained scanning的贡献,表9对比了更可怕额cascade forest的gcForest在不同的数据集上的表现。结果表明当存在空间特征关系、或者序列特征关系时,multi-grained scanning可以明显提升效果。

4.7 Cascade Structure的影响

gcForest的最终模型结构是cascade of cascades,其中每个cascade包含了多个level,每个level对应于一个粒度的scanning,如图5所示。有许多其它可能的方式来利用多粒度(multi grain)的特征,比如:将所有特征连接起来,如图6所示。

图5: $gcForest_{conc}$变种,它会将多个grain的特征连接起来。假设有三个类要预测,原始特征是400维,使用三个size的滑动窗口。

表10比较了gcForest和$gcForest_{conc}$。

4.8 更大模型

结果表明,更大的模型趋向于提供更好的效果,由于计算资源因素,我们没有尝试更多的grains,forests,trees。

注意,计算设备对于更大的模型训练是很重要的,比如:GPUs 之于DNN。另一方面,一些新的计算设备,比如: Intel KNL of the MIC (Many Integrated Core),可以为gcForest提供类似于GPU对DNN那般的潜在加速。另一方面,gcForest的一些组件,比如:multi-grained scanning,可以通过利用GPU来加速。另外,使用分布式计算还有大量优化空间。

参考

https://arxiv.org/pdf/1702.08835.pdf

google在2017年提出了一个Deep&Cross Network的模型:

1.介绍

在该paper中,提出了Deep&Cross Network(DCN)模型,它能对sparse和dense的输入进行自动特征学习。DCN可以有效地捕获关于有限阶(bounded degrees)上的有效特征交叉,学到高度非线性交叉,无需人工特征工程或暴力搜索(exhaustive searching)。并且计算代价低。

  • 我们提出了一个新的cross network,它显式地在每个layer上进行特征交叉(feature crossing),可有效学习有限阶(bouned degrees)的特征交叉预测,无需人工特征工程和暴力搜索。
  • 该cross network简单有效。通过设计,最高的多项式阶在每一layer递增,由layer depth决定。该网络包含了所有阶的交叉项(直到最高阶),它们的系数都不同。
  • 该cross network内存高效,很容易实现。
  • 我们的实验结果表明,比起接近相同阶的DNN,DCN具有更低的logloss,更少的参数。

2.DCN

本节描述了Deep & Cross Network模型。一个DCN模型会以一个embedding and stacking layer开始,接着并列连一个cross network和一个deep network。接着通过最后一个combination layer将两个network的输出进行组合。完整的DCN模型如图1所示。

图1: Deep & Cross Network

2.1 Embedding and Stacking Layer

输入数据带有sparse和dense feature。在大规模推荐系统的CTR预测中,输入几乎都是类别型特征(categorical features),比如:”country=usa”。这样的feature通常被编码成one-hot vectors,比如:”[0,1,0]”;然而,对于大的vocabularies,这通常会产生超高维度的特征空间。

为了减小该维度,我们使用一个embedding procedure来将这些二元features转换到关于真实值(real values)的dense vectors中(称为embedding vectors)。

…(1)

其中是embedding vector,是第i个category的二元输入,是对应的embedding matrix,会与网络中的其它参数一起进行优化,分别是embedding size和vocabulary size。

最后,我们将embedding vectors,以及归一化稠密特征(normalized dense features)进行stack成一个vector:

…(2)

2.2 Cross Network

新的cross network的核心思想是,将显式特征(explicit feature)以一种有效方式进行交叉。cross network由多个cross layers组成,每一个layer具有以下的公式:

…(3)

其中:

  • 是列向量(column vectors),分别表示来自第l层和第(l+1)层cross layers的输出;
  • 是第l层layer的weight和bias参数。

在完成一个特征交叉f后,每个cross layer会将它的输入加回去,对应的mapping function f:,刚好等于残差。一个cross layer的可视化如图2所示。

图2: 一个cross layer的visualization

特征的高阶交叉(high-degree interaction):cross network的独特结构使得交叉特征的阶(the degress of cross features)随着layer的深度而增长。对于第l层layer,它的最高多项式阶(在输入上)是. 实际上,cross network由这些交叉项组成,对应的阶从1到l+1. 详见第3节。

复杂度分析:假设表示cross layers的数目,d表示输入维度。那么,在该cross network中涉及的参数数目为:

一个cross network的时间和空间复杂度对于输入维度是线性关系。因而,比起它的deep部分,一个cross network引入的复杂度微不足道,DCN的整体复杂度与传统的DNN在同一水平线上。如此高效(efficiency)是受益于的rank-one特性,它可以使我们生成所有的交叉项,无需计算或存储整个matrix。

cross network的参数数目少,从而限制了模型的能力(capacity)。为了捕获高阶非线性交叉,我们平行引入了一个deep network。

2.3 Deep Network

Deep network是一个fully-connected feed-forward神经网络,每个deep layer具有以下的公式:

…(4)

其中:

  • 分别是第l层和第(l+1)层hidden layer;
  • 是第l个deep layer的参数;
  • 是ReLU function。

复杂度分析:出于简洁性,我们假设所有的deep layers具有相同的size。假设表示deep layers的数目,m表示deep layer的size。那么,在该deep network中的参数的数目为:

2.4 Combination Layer

Combination Layer将两个network的输出进行拼接(concatenate),然后将该拼接向量(concatenated vector)feed 进一个标准的logits layer上。

下面是一个二分类问题的公式:

…(5)

其中:

  • 分别是来自cross network和deep network的输出
  • 是combination layer的weight vector,其中

loss function是logloss,带有一个正则项。

…(6)

其中 是等式(5)计算得到的probabilities,是true labels,N是输入的总数,正则项参数。

我们对两个network进行jointly train,在训练期间,每个独立的network会察觉到另一个。

3.Cross Network分析

在这一节,我们分析了DCN的cross network,以便于更有效地理解。我们提供了三个视角:多项式近似,泛化到FM,有效投影。为了简洁,我们假设:

概念:假设在中的第i个元素是。对于多索引(multi-index) ,以及,我们定义了:

术语:交叉项的阶(degree)由定义。一个多项式的阶由它的项的最高阶决定。

3.1 多项式近似

根据维尔斯特拉斯逼近定理(Weierstrass approximation theorem),任意满足特定平滑假设条件下的函数,可以通过一个多项式进行逼近到一个特定的精度上。因而,我们从多项式近似的角度分析了cross network。特别的,cross network会以一种高效的、有表现力的、能更好地对现实世界数据集进行泛化的方式,近似相同阶的多项式类。

我们详细研究了一个cross network,将它近似成相同阶的多项式类(polynomial class)。假定表示n阶的多元多项式类(multivariate polynomial class):

…(7)

在该类中的每个多项式具有个系数。只有个参数,cross network包含了在相同阶的多项式中的所有交叉项,每一项的系数与其它项各不相同。

理论 3.1: 一个l-layer的cross network,具有i+1个layer,定义成:。假设网络的输入是,输出是,参数是。接着,多元多项式会以下面的类进行重现(reproduce):

其中:

  • 其中 , 是一个与独立的常数
  • 是多元索引(multi-indices),
  • 是indice 的所有排列(permutations)的集合。

定理3.1的理论证明详见paper中的附录。举个例子,的系数,其中。直到一些常数,其中;其中

3.2 FM的泛化

cross network共享参数,类似于FM模型的参数共享,并扩展到了一个更深的结构上。

在FM模型中,特征与一个 weight vector 相关联,交叉项的权重通过 计算得到。在DCN中,与标量有关,的权重是集合的参数乘积。两种模型都会为每个特征学到一些与其它特征相互独立的参数,交叉项的权重是相应参数的一种特定组合。

参数共享(parameter sharing)不权使得模型更有效,也使模型可以泛化到未见过的特征交叉上,对噪声更健壮。例如,使用sparse features的数据集。如果两个二元特征很少或者几乎从未在训练集中共现过,假设,,接着,学到关于的权重不会带有对预测有意义的信息。

FM是一个浅层结构(shallow structure),受限于交叉项的阶是2. 而DCN可以构建所有的交叉项,其中阶 由一些常数决定,见理论3.1。因而,cross network扩展了参数共享的思想,将单个layer扩展到多个layer,并且有更高阶的交叉项。注意,与高阶FM不同的是,在cross network中的参数数目,只随着输入维度线性增长。

3.3 有效投影

每个cross layer会以一种有效方式,将在间的所有pairwise交叉进行投影到输入维度上。

考虑到是一个cross layer的输入。cross layer首先隐式构建了个关于的pairwise交叉,接着以一种内存高效的方式,隐式地将它们投影到维度d上。这种直接的方式会带来3次方开销。

我们的cross layer提供了一种有效的解决方式,将开销减小到维度d的线性开销上。考虑。事实上等于:

…(8)

其中,row vectors包含了所有的pairwise交叉,投影矩阵具有一个块对角化结构,其中是一个列向量。

4.实验结果

在本节中,我们评估了CDN在多个数据集上的效果。

4.1 Criteo Display Ads数据集

Criteo Display Ads数据集用于预测点击率。具有13个integer features和26个categorial features。其中,每个category都具有一个很高的维度基数。对于该数据集,在logloss上提升0.001可以看成是巨大的提升。当考虑到在一个很大的用户基数时,在预测准确率(prediction accuracy)的一个小的提升,可以为公司带到来一个大的回报。数据包含了11GB的包含7天的用户日志(~41000,000条记录)。我们使用前6天的数据做为训练,并将第7天的数据随机划分成等size的validation和test set。

4.2 实现细节

DCN在tensorflow上实现,我们会讨论一些关于训练CDN的细节。

数据处理和embedding。实数型特征通过一个log转换进行归一化。对于类别型特征,会将这些特征嵌入到dense vectors中,维度为 。最后将所有的embedding结果拼接(concatenating)成一个维度为1026的向量。

优化(Optimization):我们使用Adam optimizer,mini-batch进行随机优化。batch size=512. Batch normalization被应用于deep网络,gradient clip norm设置为100.

正则化:我们使用early stopping,我们未发现L2正则或dropout很有效。

超参数:我们基于一个grid search来在hidden layers的数目、size、初始learning rate以及cross layers的数目上进行探索。hidden layers的数目范围为2一5, hidden layers的数目从32到1024. 对于DCN,cross layers的数目从1到6.初始learning rate从0.0001依次递增调到0.001. 所有试验都使用early stopping,训练step为150000, 超过它可能会发生overfitting。

参考

https://arxiv.org/pdf/1708.05123.pdf

我们来看下gravityR&D提出的《SESSION-BASED RECOMMENDATIONS WITH RECURRENT NEURAL NETWORKS》。

2.相关工作

2.1 session-based的推荐

推荐系统领域的大多数工作主要关注于建模:当提供一个用户id时,可以为它构建一个明确的user profile。在该setting中,相应的文献主要是MF方法和基于近邻的模型。这些方法可以在session-based recommendation中采用;当缺失user profile时,一个很自然的解决方案是:item-to-item推荐方法。在该setting中,会从提供的session数据中预计算好item-to-item的相似度矩阵,也就是说:经常在sessions中一起被点击的这些items,被认为是相似的。相似矩阵接着在session期间被简单用于:为一个当前用户所点击的项推荐最相似的items。该方法被证明是有效的,并被广泛使用。这些方法只能说明用户的最近点击行为,实际上忽略了过去点击的行为。

对于session-based推荐,一些不同的方法有:Markov决策过程(MDP: Markov Decision Processes)。MDP是顺序随机决策问题的模型。一个MDP被定义成一个4元组 ,其中:S是状态集(state),A是动作集(action),Rwd是一个reward函数,tr是状态转移函数。在推荐系统中,动作(action)等价于推荐,最简单的MPDs本质上是一阶Markov链,其中下一个推荐可以根据item间的转移概率被简单计算。在session-based推荐中使用Markov链的主要问题是:当尝试包含所有可能的用户选择序列时,状态空间很快变成不可管理。

通用因子分解框架(GFF: General Factorization Framework)的扩展版本可以使用session data进行推荐。它会通过将这些事件进行求和(sum)来建模一个session。它使用两种类型的隐表示:一种用于表示item自身,另一种用于将item表示成一个session的部分。session接着被表示成关于part-of-a-session的item表示的feature vectors的平均。然而,该方法不会考虑任何在session中的顺序。

2.2 Deep learning推荐

最近在神经网络文献中的一个相关方法,它使用受限波尔茨曼机(RBM)进行CF计算(Salakhutdinov et al., 2007)。在该工作中,一个RBM被用于建模user-item交互并执行推荐。该模型已经被证明是最好的CF模型之一。Deep模型已经被用于从非结构化内容中(比如:音乐、图片)抽取特征,接着被一起用于更通用的CF模型。在(Van den Oord et al.2013) 中,使用一个CNN来从音乐文件中抽取特征,接着被用在一个因子模型中(factor model)。最近(Wang et al.2015)引入了一个更通用的方法,它使用一个深度网络来从任意类型的items中抽取通用内容特征,这些特征接着被合并到一个标准的CF模型中来增强推荐效果。该方法看起来特别有用,尤其是在没有足够多的user-item交互信息时。

3.使用RNN的推荐

RNN可以建模变长序列数据。在RNN和传统前馈深度模型间的主要不同之处是,在构成网络的units中存在一个内部隐状态(hidden state)。标准RNN会更新它们的隐状态h,它使用以下的更新函数:

…(1)

其中:

  • g是一个平滑边界函数(比如:使用一个logistic sigmoid函数)
  • 是在时间t上unit的input
  • 给定它的当前状态, 一个RNN会输出:关于该序列的下一个元素的一个概率分布

GRU是一个关于一个RNN unit的更精巧的模型。它的目标是,解决梯度消失问题(vanishing gradient problem)。GRU gate本质上会学习何时(when)以及多大(how much)进行更新unit的hidden state。GRU的activation是一个在之前activation和候选activation 上的线性插值。

…(2)

其中update gate为:

…(3)

其中,cadidate activation函数以相似方法进行计算:

…(4)

最后,reset gate的为:

…(5)

3.1 定制GRU模型

图1: 网络的通用结构。一次只处理事件流中的一个事件(event)

我们在我们的模型中使用GRU-based RNN来进行session-based推荐。网络的输入是该session的实际状态(state),而输出为在session中item的下一个事件(event)。到目前为止,该session的state可以是item的实际event或在session中的events。在前面的case中使用1-of-N的编码,例如,输出向量的长度实际为items数目,只有在对应于实际item的位置上为1,其它为0。后面的setting中会使用一个关于这些表示(representations)的加权和,如果events在更早前发生,那么它会降权(discounted)。出于稳定,输出向量接着会被归一化(normalized)。我们期望这会有帮助,因为它增强了记忆效应(memory effect):而非常局部顺序限制(very local ordering constraints)的增强则并不能被RNN的更长期记忆所捕获。我们也实验了其它方法: 通过增加一个额外的embedding layer,但1-of-N encoding的效果更好。

该网络的核心是:GRU layer(s)、以及额外的feed-forward layers(可以在最后一层和output间进行添加)。输出为items的预测偏好,例如,在session中对于每个item成为下一个被推荐的似然。当使用多个GRU layers时,前一layer的hidden state是下一layer的input。该input也可以可选地被连接到在网络中更深的GRU layers上,我们发现这确实能提升性能。整体架构如图1所示,它描述了单个event在events时间序列中的表示(representation)。

由于推荐系统并不是RNN的主要应用领域,我们修改了基础网络让它更好地适合推荐任务。我们也考虑到实际点以便我们的解决方案可以应用到一个现实环境上。

3.1.1 session-parallel mini-batches

NLP任务中的RNN通常使用in-sequence mini-batches。例如,很常用的是使用一个slide window来滑过句子中的词,并将这些window化的片段相互挨着来构成mini-batches。这种方法对于我们的任务来说不合适,因为:

  • (1) sessions的长度可能非常不同,甚至比句子还要更不同:一些sessions可能只有2个events,而其它可能有上百个;
  • (2) 我们的目标是,捕获一个session在时序上的演进,因此将它们分割成片段可能会没有意义

因此,我们使用session-parallel mini-batches。首先,我们为该sessions创建一个顺序(order)。接着,我们使用前X个sessions的第一个event来形成首个mini-batch的input(期望的output为我们的active sessions的第二个events)。第二个mini-batch会从第二个events来生成,自此类推。如果sessions的任意一个结束,下一个可提供的session会补上它的位置。Sessions被认为是相互独立的,因此,当该切换发生时,我们会重置(reset)合适的hidden state。如图2所示。

图2: session-parallel mini-batch creation

3.1.2 在output上进行sampling

当items数目很大时,推荐系统特别有用。对于一个中级规模(medium-sized)的网上商店来说,它的items范围可能是成千上万,但对于一个更大网络来说,可能有上百万items。在每一step为每个item计算一个score,会让算法与items数和events数的乘积成比例增长。这在实际上是不可行的。因此,我们必须对output进行抽样,只对items某个子集计算score。这也只有一些权重会被更新。除了期望的output之外,我们需要为一些负样本计算scores,并修改权重以便期望的output的排序更靠前。

对于一个任意missing event的天然解释是,用户不知道该item的存在,因而没有任何交互。然而,如果某用户不知道该item并选择不与之交互,是因为她不喜欢(dislike)该item,这种情况的概率很低。item越流行,用户越可能知道它,因此一个missing event更可能会传达dislike的意味。因此,我们应根据它们的流行度成比例抽样。我们并不会选为每个训练样本生成独立(separate) samples,而是选择:使用从该mini-batch中的其它训练样本的items来当成负样本。该方法的好外是,我们可以通过跳过抽样(sampling)来进一步减小计算时间。另外,这也可以从实现侧受益,可以让该代码更简单些,以便进行更快的矩阵操作。同时,该操作也是一个基于流行度的抽样(popularity-based sampling),因为一个item成为该mini-batch中的其它训练样本的似然概率(likelihood),与它的流行度成正比。

3.1.3 ranking loss

推荐系统的核是items的相关度排序(relevance-based)。尽管该任务可以被解释成一个分类任务,l2r方法通常要好于其它方法。ranking可以是pointwise,pairwise和listwise。pointwise ranking会独立的估计items的score或者rank,它的loss定义的目的是相关items的rank应较小(low)。pairwise ranking会比较一个positive和一个negative item pairs的score或rank,该loss会增强:positive item的rank应低于negative item的rank。Listwise ranking使用所有items的scores和ranks,并比较它们的顺序。由于它包含了排序(sorting),通常计算开销更大,并不常使用。同时,如果只有一个相关item(例如:在我们的case中)——listwise ranking可以通过pairwise ranking进行解决。

我们在我们的解决方案中包含了一些pointwise和pairwise ranking losses。我们发现,pointwise ranking对于网络不是稳定的(见第4节)。pairwise ranking losses在其它方法更胜一筹。我们使用以下的两个:

  • BPR:Bayesian Personalized Ranking (Randle et al., 2009)是一个矩阵因子方法,它使用pairwise ranking loss。它会比较一个positive和一个sampled negative item的score。这里,我们比较了positive item与一些sampled items的scores,并使用它们的平均作为loss。在一个session中对于某个结定点的该loss定义如下:

其中,是sample size,是在item k上在该session的给定点的score,i是期望的item(在session中下一item),j是负样本(negative samples)。

  • TOP1: 该ranking loss由我们提出。它是关于相关项的相对rank的正则近似。相关iitem的相对rank由给定。我们使用一个sigmoid来近似。这的最优化可以修改参数,以便i的score能高些。然而,这是不稳定的,因为特定positive items也扮演着负样本的角色,因为scores趋向于变得增长更高。为了避免这种情况,我们希望强制负样本的scores在零周围。这是对negative items的scores的一种自然期望。因而,我们添加到一个正则项到该loss中。很重要的是,在相同范围内的该term作为相对rank很重要,。最终的loss function如下所示:

4.实验

我们在两个数据集上,对rnn与其它流行的baslines进和对比。

第一个数据集是RecSys Challenge 2015. 该数据集包含了一个商业网站的click-streams,有时以购买事件结尾。我们会使用该比赛的trainset,只保留点击事件。我们过滤掉了长度为1的session。该网络使用〜6个月的数据进行训练,包含了7,966,257 sessions,在37,483个items上的31,637,239 clicks。我们使用后续天的sessions进行testing。每个session被分配给trainset或testset两者之一。由于CF方法的天性,我们会从testset中过滤出那些item点击并不在trainset中的点击。长度为1的Session也会从testset中移除。在预处理后,对于testset,我们留下了大约15324个session,它具有71222个events。该数据集被称为RSC15.

第二个数据集从Youtube-like OTT视频服务平台上收集。我们收集了在一段时间内关于观看vidio的events。只有特定范围会被归到该collection中:最近2个月。在这段时间内,每个视频后的屏幕左侧会提供item-to-item的推荐。这些items由不同算法选择得到,它们受用户行为的影响。预处理阶段与其它数据集相似,会过滤非常长的sessions,因为它们可能由机器生成。训练数据包含了所有,上述周期的最后一天。具有300w的sessions,具有在33w视频上的13w的watch events。testset包含了之前提的,具有~3.7w的sessions,~18w的watch events。该数据集被称为“VIDEO”。

评估(evaluation)通过挨个提供一个session的events,并确认下一event中该item的rank来完成。GRU的hidden state在一个session完成后会被重置为0. items通过它们的score以降序排序,在该list中它们的位置就是它们的rank。对于RSC15数据集, trainset中所有37483个items会被排序。然而,这对于VIDEO数据集是不现实的,因为items的数目很大。这里我们会对期望的item vs. 最流行的30000 items进行排序。这对于evaluation会有很小的影响,很少被访问的items经常获得较低分数。同时,基于流行度的预过滤在实际的推荐系统中很常见。

由于推荐系统一次只会推荐很少的items,一个用户可能选取的实际item应与在列表中的头几个items之中。因此,我们主要的评估指标是recall@20,也就是说,在所有test cases中,所期望item在top20之内的cases的比例。recall不考虑item的实际rank,只需要topN之内即可。这会建模实际场景,其中没有强调推荐,不关心绝对顺序。recall也通常与重要的online KPIs(比如:CTR)相关。第二个在实验中使用的metric是MRR@20 (Mean Reciprocal Rank)。这是关于所期望items的相互排序(reciprocal ranks)的平均。如果该rank超过20, 则reciprocal rank被置为0. MRR会解释该item的rank,在推荐顺序比较关注的情况下,这指标是重要的。(例如:低rank的items只会在滑动后可见)

4.1 Baselines

我们比较了该网络与一些其它baselines。

  • POP: 流行度预测,总是推荐训练集中最流行的items。它通常在特定领域内是一个较强的baseline。
  • S-POP:该baseline会推荐当前session的最流行items。推荐列表会在session期间随着items获得更多events而进行变化。使用全局流行度值可以突破束缚。该baseline在该领域很强,有较高的重复性。
  • Item-KNN:与实际item相似的Item可以通过该baseline被推荐,相似度的定义通过他们sessions向量间的cosine相似度来定义,例如:在sessions中两个items的共现次数,除以各自单个items出现所在的sessions数目的乘积的平方根。可以进行正则化,避免较少访问items的高相似度。该baseline是在实际系统中最常用的item-to-item解决方案,它提供给推荐系统这样的setting:观看了该item的其它人也会观看这些item。尽管它很简单,但它通常是一个较强的baseline。
  • BPR-MF:BPR-MF是一个常用的MF方法。它会为一个pairwise ranking目标函数通过SGD进行最优化。矩阵分解不能直接应用到session-based推荐上,因为新的sessions不会具有预计算好的特征向量。然而,我们可以通过使用在session中出现过的item的feature vectors的平均向量来克服这个问题。换句话说,在一个可推荐item和session的items间的特征向量的相似度进行求平均。

参考

https://arxiv.org/pdf/1511.06939.pdf

我们来看下lightgbm的paper:《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》。

1.

GBDT是流行的机器学习算法,只有少量的高效实现,比如:XGBoost和pGBRT。尽管在这些实现中采用了许多工程优化,但当特征维度很高、数据size很大时,其效率和可扩展性仍不能令人满意。其中一个主要原因是,对于每个特征,他们需要扫描所有数据样本来估计所有可能划分点的信息增益(information gain),这是非常耗时的。为了解决该问题,我们提供了两个新技术:基于梯度的单边采样(GOSS: Gradient-based One-Side Sampling)、独有特征打包(EFB: Exclusive Feature Bundling)。有了GOSS,我们可以使用小梯度来排除大量的样本,只使用剩余部分来估计信息增益。我们通过证明,由于更大梯度的数据样本,通常在计算信息增益时扮演更重要角色,GOSS使用更小的data size即可以获得相当精准的关于信息增益的估计。有了EFB,我们可以将多个独有特征(比如:他们很少会同时采用非零值)进行打包,以减小特征数。我们证明了,发现最优的独有特征bundling是一个NP-hard问题,但一个贪心算法可以达到相当好的近似(这样可以有效减少特征数,同时不伤害split点决策的accuracy)。我们将这种带GOSS和EFB机制的GBDT称为LightGBM。我们的实现在多个公共数据集上做了实验,LightGBM可以加速常用的GBDT训练过程达20倍,而几乎保持相同的accuracy。

1.介绍

由于高效,精准,可解释性强,GBDT被广泛使用。GBDT在许多机器学习任务上都达到了state-of-art的效果。最近几年,随机大数据的出现,GBDT面临着新挑战,尤其是在accuracy和efficiency的权衡上。GBDT的常见实现,需要对每个特征进行扫描所有数据样本来估计所有可能划分点的信息增益。因此,他们的计算复杂度与特征数、以及样本数成比例。这使得这些实现在处理大数据时非常耗时。

为了解决该挑战,一个简单的想法是,减少数据样本数、以及特征数。然而,这被证明是非常有意义(non-trivial)的。例如,如何为GBDT执行数据采样是不明确的。有一些工作开展会根据它们的权重来采样数据,以加速boosting的训练过程[5,6,7]。但它们不能直接被应用在GBDT中,因为在GBDT中根本没有抽样权重(sample weight)。为此,我们提出了两种新技术。

GOSS。在GBDT中对于数据样本没有原始权重(native weight),我们注意到不同梯度的数据样本在计算信息增益时扮演着不同的角色。特别的,根据信息增益的定义,这些带着更大梯度的(例如:under-trained样本实例)样本实例会在计算信息增益时贡献更多。因此,当对这些数据样本做下采样(down-sampling)时,为了保持信息增益的accuracy,我们最好保留这些带有大梯度的样本(例如:比一个预定义阀值要更大,或者在top百分比间),并只随机drop掉那些小梯度的样本实例。我们证明了,这样的处理比均匀随机抽样(uniformly random sampling)可以产生更精准的增益估计,特别是当信息增益的值具有具有较大范围时。

EFB。在真实应用中,尽管具有大量特征数,但特征空间相当稀疏,这提供给我们一个设计一个几乎无损的方法的可能性,来减小有效特征数。特别的,在一个稀疏特征空间中,许多特征是(几乎)独有的,例如,他们很小同时采用非零值。这些样本包含了one-hot特征(例如:文本挖掘中的one-hot词表示)。我们可以很安全地对这些独有特征进行捆绑(bundle)。q我们设计了一个高效算法,它通过会将最优bundling问题缩减到一个图着色问题(graph coloring problem:通过将特征看成是顶点,如果每两个特征间相互排斥就添加一条边),通过一个常数近似率的贪心算法来解决该问题。

我们将这个带有GOSS和EFB的新GBDT算法称为LightGBM。

2.前提条件

2.1 GBDT和它的复杂度分析

GBDT是一个关于决策树的ensemble模型,它会顺序式进行训练。在每轮迭代中,GBDT会通过拟合负梯度(被称为:残差 residual errors)来学习决策树。

GBDT的主要开销在学习决策树中,学习决策树时最耗时的部分,是发现最佳的分割点(split points)。一种最流行的算法是,pre-sorted算法【8,9】,它会在pre-sorted特征值上枚举所有可能的分割点。另一种流行的算法是,histogram-based算法【10,11,12】,如算法1所示。histogram-based算法会将连续特征值进行分桶成(buckets)离散bins,并在训练期间使用这些bins来构建特征的histograms。由于histogram-based算法在内存消耗和训练速度上都更高效,我们基于它进行开发。

算法1、2:

如算法1所示,histogram-based算法会基于特征的histograms去发现最佳split points。它会花费O(#data x #feature)的时间复杂度来进行histogram building,以及花费O(#bin x #feature)来进行split point finding。由于#bin通常要比#data更小很多,histogram building会决定着计算复杂度。如果我们可以缩减#data数或者#feature数,我们将能够实质上加速GBDT的训练。

2.2 相关工作

在文献中有相当少的GBDT实现,包含XGBoost[13], pGBRT[14], scikit-learn[15], R的gbm[16]。sklearn和R-gbm实现使用的是presorted算法,而pGBRT实现了histogram-based算法。XGBoost支持两种实现(pre-sorted和histogram-based)。如[13]所示,XGBoost的效果要好于其它工作包。因而,我们使用XGBoost作为我们实验中的baseline。

为了缩减训练数据的size,常用的方法是对数据样本进行下采样。例如,在[5]中,如果数据样本的权重小于一个固定阀值,它们将会被过滤。SGB[20]会在每轮迭代中使用一个随机子集来训练弱学习器(weak learners)。在[6]中,抽样率在训练过程中会动态调整。然而,除了SGB外的所有其它工作都基于AdaBoost,不能直接应用于GBDT,因为它们对于在GBDT中的数据样本实例来说没有原始权重(native weights)。尽管SGB可以被用于GBDT,但它通常会降低accuracy,因而不是一个理想选择。

相同的,为了缩减特征数,很自然地会过滤弱特征[22,23,7,24]。这通常可以通过PCA或投影来完成。然而,这些方法高度依赖于:假设这些特征包含大量冗余,这在实践中并不总是成立(特征通常会根据它们的独特贡献被设计,移除任意之一都会在一定程序上影响训练的accuracy)。

在实际应用中的大规模数据集通常是相当稀疏的。GBDT会使用pre-sorted算法,通过忽略零值特征来缩减训练开销【13】。而histogram-based GBDT不会对稀疏优化解决方法有影响。原因是,histogram-based算法需要为每个数据样本检索特征的bin值(根据算法1),不管特征值是零或非零。我们更推荐histogram-based算法,它可以有效消除这样的稀疏特性。

为了解决之前的局限性,我们提出了两个新技术:GOSS、EFB。

3 GOSS

3.1 算法描述

在AdaBoost中,sample weight被当成是一个关于数据样本实例重要性的指示器(indicator)。然而,在GBDT中,不存在天然的sample weights,因而像AdaBoost提出的sampling方法不能直接用。幸运的是,我们注意到,对于在GBDT中的每个数据样本,它们的梯度可以为我们提供有用信息来进行数据抽样。也就是说,如果一个实例与一个小梯度有关,该样本的training error很小,并已经过良好训练。一个简单的想法是,抛弃这些小梯度的数据样本。然而,这样做可能会改变数据分布,进而伤害所学模型的accuracy。为了避免该问题,我们提出了一个新方法称为:GOSS。

GOSS会保留所有带大梯度的样本,并在小梯度样本上进行随机抽样。为了对数据分布的影响进行补偿,当计算信息增益时,GOSS会为带小梯度的数据样本引入一个常数乘子(见算法2)。特别的,GOSS首先会根据它们梯度的绝对值来对数据样本进行排序,接着选取top a x 100%的样本。接着它会从其余数据中随机抽样 b x 100%的样本。最后,当计算信息增益时,GOSS会通过一个常数对小度数抽样数据进行放大。通过该方法,我们可以更关注under-trained样本实例,而不需要过多更改原始数据分布。

算法2:

3.2 理论分析

GBDT使用决策树来学习从输入空间到梯度空间的函数。假设,我们具有一个训练集,n独立同分布(i.i.d.),其中每个是一个在空间上的s维向量。在gradient boosting的每轮迭代中,关于loss函数的负梯度会根据模型的输出被表示为。决策树模型会在最具信息量的特征上分割每个节点(使用最大信息增益)。对于GBDT,信息增益通常会通过在进行分割之后的variance来进行衡量,如下定义。

定义 3.1: 假设O是在决策树的一个确定节点上的训练数据集。在该节点上,分割特征j在点d中的variance gain,定义如下:

其中,。

定理 3.2

4. EFB

在本部分,我们提出了一种新方法来有效缩减特征数。

算法3,4

高维数据通常非常稀疏。特征空间的稀疏性提供我们一个可能性来设计近科目无损的方法来缩减特征数。特别的,在一个稀疏特征空间中,许多特征相互排斥,例如,他们不会同时采用非零值。我们可以安全地将这些相互排斥的特征打包成单个特征(我们称之为一个“exclusive feature bundle”)。通过一个精心设计的特征扫描算法,我们可以从feature bundles中构建相同的feature histograms来作为从单个特征中计算的histograms。在这种方法中,histogram building的复杂度可以从O(#data x #feature)变为O(#data x #bundle),其中,#bundle « #feature。接着,我们可以在对accuracy无伤的情况下极大加速GBDT的训练。接着,我们会详细展示是如何得到的。

有两个要点要解决。第一个是,决定哪些特征应一起进行加包。第二个是如何构建bundle。

定理 4.1:将特征划分为更小数目的exclusive bundles问题是一个NP-hard问题。

证明:我们会将图着色问题(graph coloring problem)应用到我们的问题上。由于图着色问题是NP-hard的,我们可以推导我们的推论。

给定关于图着色问题的任意样本 。我们以如下方式构建一个样本实例。采用关联矩阵G的每一行作为一个feature,接着使用个特征来获取一个instance。很容易看到,在我们的问题中,特征的一个exclusive bundle对应于相同颜色的一个顶点集,反之即然。

对于第1个要点,定理4.1证明了:发现最优的bundling策略是一个NP-hard问题。这意味着,在多项式时间内发现一个准确的解是不可能的。为了发现一个好的近似算法,我们首先将optimal bundling问题精减为图着色问题。通过将特征看成是顶点、如果两两特征不相互排斥则在上面添加边。我们使用一个贪心算法来为图着色生成bundles来生成合理的好结果(具有一个常数近似几率)。接着,我们注意到,通常有相当少的特征,尽管它们并不是100%相互排斥的,很少同时采用非零值。如果我们的算法可以允许一定比例的冲突,我们可以获得一个更小数目的feature bundles,并进一步提升计算效率。通过简单计算,随机污染一定比例的特征值会影响训练accuracy,最多达到,其中是在每个bundle中的最大冲突然袭击。因此,如果我们选择一个相对小的,我们会在accuracy和efficiency上达到较好的平衡。

其于上述讨论,我们为exclusive feature bundling设计了一个算法来,如算法3所示。首先,我们使用一个带权重边来构建一个graph,它们有weights以应于特征间的总冲突。第二,我们通过在图中的度对特征进行降序排序。最后,我们在有序列表中确认每个特征,接着给它们分配一个已存在具有较小冲突的bundle(通过控制),或者创建一个新bundle。算法3的时间复杂度是,它在训练前仅会处理一次。当特征数不是非常大时,该复杂度是可接受的,但如果有数百万特征时仍会有问题。为了进一步提升效率,我们提出一种更有效的排序策略(ordering strategy),无需构建graph:通过非零值的数目排序,这与通过degree的方式排序相似,因为更多非零值通常会产生更高的冲突率。由于我们只会更改算法3的排序策略,新算法的细节会被忽略以免重复。

对于第二个要点,我们需要一种好方法来将相同bundle中的features合并,以便能缩减相应训练复杂度。关键点是确认原始特征值可以从feature bundles中被确认。由于histogram-based算法会存储离散bins,而非特征的连续值,我们可以通过让排斥特征(exclusive features)落在不同的bins上。这可以通过添加offsets到特征的原始值中来完成。例如,假设我们在一个feature bundle中有两个features。最初,feature A的取值为[0, 10),feature B的取值为[0, 20)。我们接着添加一个offsets为10到feature B中,以便重定义的features取值为[10,30)。这之后,可以安全地合并features A和B,并使用一个范围为[0,30)的feature bundle来替换原始的features A和B。详细情况见算法4.

EFB算法可以将多个排斥特征bundle到更少的dense features上,它可以有效避免不必要的零特征值计算。实际上,我们也可以优化最基本的histogram-based算法,通过为每个特征使用一个表来记录非零值数据来忽略零值。通过扫描该表的数据,对于一个特征,histogram building的开销会从O(#data)变更为O(#non zero data)。然而,该方法需要额外的内存和计算开销来维持这些在整个树增长过程中的per-feature tables。我们在LightGBM中将该优化实现作为一个基本功能。注意,该最优化不会与EFB冲突,因为在当bundles很稀疏时,我们仍可以使用它。

5.实验

本部分,我们会展示实验结果。我们使用了5个不同公共数据集。这些数据集如表1所示。其中,Microsoft Learning to Rank [LETOR]数据集包含了30K的网络搜索queries。该数据集所用的features大多数是dense numerical features。Allstate Insurance Claim数据集和Flight Delay数据集都包含了许多one-hot coding features。最后两个数据集来自于KDD CUP 2010和KDD CUP 2012. 我们直接使用来自NTU的获胜方案的features,它包含了dense和sparse features,这两个数据集都非常大。我们可以使用它们来直接测试算法。

表1

我们的实验环境是Linux server,它具有两个E5-2670 v3 CPUs(共24个核)以及256GB内存。所有实验都在多线程上运行,线程数固定在16个上。

5.1 总体比较

我们在下面提出了总的比较。XGBoost和没有GOSS和EFB的LightGBM(称为lgb_baseline)被用于baselines。对于XGBoost,我们使用两个版本,xgb_exa(pre-sorted算法)和xgb_his(histogram-based算法)。对于xgb_his,lgb_baseline,以及LightGBM,我们使用leaf-wise的树增长策略。对于xgb_exa,由于它只支持layer-wise的增长策略,我们为xgb_exa调整参数,以便让它像其它方法一样增长相似的树。接着,我们朝着在speed和accuracy间更好平衡的方向,为所有数据集调参。我们为Allstate,KDD10和KDD12设置a = 0.05, b=0.05, 为Flight Delay和LEFTOR设置a=0.1, b=0.5. 我们EFB中设置。所有算法会运行固定迭代次数,我们从该迭代中使用最好的score来获取accuracy结果。

表2

训练时间和测试accuracy在表2和表3中。从这些结果看,我们可以看到LightGBM是最快的,并且几乎与baselines维持着相同的accuracy。xgb_exa是基于pre-sorted算法的,它会比histogram-based算法要慢很多。通过比较lgb_baseline,LightGBM在AllState、Flight Delay、LETOR、KDD10和KDD12数据集上要快21x,6x,1.6x,14x和13x。由于xgb_his相当耗费内存,它在KDD10和KDD12数据集上不能成功运行,会out-of-memory。在其它数据集上,LightGBM会更快,直到在Allstate数据集上能达到9x加速。 加速的计算是通过每轮迭代的训练时间计算得到的,是由于所有算法会在相同迭代数上收敛。为了演示总的训练过程,我们展示各自在图1和图2上,基于wall clock time的训练曲线。

表3:

在所有数据集上,LightGBM可以达到几乎相同的test accuracy作为baselines。这意味着GOSS和EFB在带来大的加速时并不会伤害accuracy。这与第3.2节和第4节的理论分析相一致。

5.2 GOSS分析

首先,我们研究了GOSS的加速能力。从表2中LightGBM和EFB_only的比较来看,我们可以通过使用10%-20%的数据,看到GOSS可以带来接近2x的加速。GOSS可以只使用抽样数据就可以学到trees。然而,它会在整个数据集上保留一些计算,比如:指导预测和计算梯度。这样,我们就可以发现,整个加速与抽样数据的比例是非线性相关的。然而,由GOSS带来的加速仍非常大,该技术可以应用到不同数据集上。

第二,通过比较随机梯度增强(SGB:Stochastic Gradient Boosting),我们评估了GOSS的accuracy。不失一般性,我们使用LETOR数据集进行测试。我们通过选择在GOSS中不同的a和b来调参抽样比例,并为SGB使用相同的整体抽样比例。我们通过使用early stopping来运行这些settings直到收敛。结果如表4所示。我们可以看到,当使用相同的抽样比例(sampling ratio)时,GOSS的accuracy总是好于SGB。这些结果与在3.2节中讨论一致。所有实验演示了GOSS是一个比stochastic sampling更高效的sampling方法。

表4:

5.3 EFB分析

通过比较lgb_baseline和EFB_only,我们确认了EFB对于加速的贡献。结果如表2所示。这里,我们不允许在bundle finding process(例如:)中有冲突。我们发现EFB可以帮助达到在这些大规模数据集上更大的加速。

注意,lgb_baseline对于稀疏特征有优化,EFB可以通过一个较大因子达到训练加速。由于EFB会将许多稀疏特征(one-hot features和隐式exclusive features)合并到更少的特征中。然而,EFB在维持非零数据表上,对于在树学习过程中的每个特征,不会有额外开销。再者,由于许多之前孤立的特征会捆绑到一起,它可以增加spatial locality,并极大提升cache hit rate。因此,在效率上的整体提升是显著的。有以上分析后,EFB是一个非常有效的算法,可以利用在histogram-based算法上的sparse特性,它可以为GBDT训练过程带来一个极大加速。

参考

https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf