gcForest介绍

Reading time ~1 minute

在各种类型的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

xDeepFM介绍

前几天微软提出了一个xDeepFM算法:# 介绍传统交叉特征工程主要有三个缺点,以下部分来自paper:- 1.获取高质量特征代价高昂- 2.大规模预测系统(比如:推荐系统),存在大量原始特征(raw features),很难人工抽取所有交叉特征- 3.人工交叉特征不能泛化...… Continue reading

CRNN介绍

Published on March 04, 2018

CTPN介绍

Published on February 03, 2018