Deep Forest论文笔记

论文链接https://arxiv.org/abs/1702.08835

注：本文谨代表笔者观点，水平有限，若有不足及疏忽之处，诚请批评指正

Abstract

尝试用不可微模块建立深度模型
推测DNNs成功的秘密在于：
- layer by layer processing
- in-model feature transformation
- sufficient model complexity
提出gcForest，决策树集合方法，比DNNs更少的超参数，模型复杂度依据数据自动调整。采用默认参数设置，对于不同领域各种类型的数据，在大部分情况下相当鲁棒。

Introduction

DNNs缺点：

太多超参数，学习表现极度依赖细致的调参过程。训练过程太tricky，涉及到的factor太多几乎有无限种可能，理论分析十分困难。
对数据极度饥饿，在小数据量问题上很难应用。对于一些大数据量领域，由于标注的成本较高，数据还是不够充足。
黑箱，无法理解决策过程，无法理论分析学习过程
训练之前必须先确定网络结构，故而模型复杂度是预先确定的。实际中模型复杂度overly complicated，shortcut connection、剪枝、二值化有助于提高DNNs的性能。
一些任务上，DNNs仍然不够出众，有时甚至不够充分

神经网络是多层的参数化可微的非线性模块，但是现实世界中不是所有的properties都是可微或者best modelled as differentiable。文章在尝试解决这样一个问题：

Can deep learning be realized with non-differentiable modules?

这个问题的结果有助于解答：

深度模型是否只能用可微的模块构建
不用反向传播可以训练深度模型吗
在RandomForest或者XGBoost表现强劲的task上，能否让深度模型表现更好

由layer-by-layer结构启发，采用级联的forest结构，提出gcforest，有着这样的优点：

模型复杂度data-dependent，小数据问题表现良好
更少的超参数
即使是不同领域的各种数据，采用默认参数设置，表现依然出色

Inspiration

Inspiration from DNNs

DNNs成功最重要的是representation learning，表征学习最重要的是layer-by-layer processing。从底层往上，特征的抽象程度越高。

其它条件一定的情况下，模型较高的复杂度一般代表着较强的学习能力。但不能解释浅层网络表现一般的原因，即使添加无限个隐层节点，故模型复杂度本身无法解释DNNs的成功，而在于layer-by-layer。不管flat network复杂度有多高，它们并不能学到逐层处理的特征。

虽然决策树和Boosting方法有逐层处理，但是在学习过程中，总是work on 原始的特征表示，并没有创造新特征，即没有模型内的特征转换。与被武断地赋予足够复杂度的DNNs相比，决策树和Boosting方法的复杂度还是相对有限。

Inspiration from Ensemble Learning

对于集成学习来说，每个子学习器需要accurate和diverse。在融合的过程中，与单纯的精确度相比，子学习器间的互补性更重要。从error-ambiguity decomposition可得到：

E=¯¯¯¯E−¯¯¯¯A(1)(1)E=E¯−A¯

EE为集成error，¯¯¯¯EE¯为子分类器的平均误差，¯¯¯¯AA¯为子分类器间的平均ambiguity，之后称为多样性。子分类器的精确度和多样性越高，集成效果越好。ambiguity的定义说法不一，故无法将该式子拿来作为优化的函数。

实际中，多样性是通过训练时添加随机性实现的，主要有四种机制：

data sample manipulation
input feature manipulation
learning parameter manipulation
output representation manipulation

不同的机制可以融合使用，但是并不是很有效。

The gcForest Approach

Cascade Forest Structure

由layer-by-layer processing启发，gcForest采用一个级联结构。

每一层是一个决策树森林的集成，包含two random forests (black) and two completely-random tree forests(blue)。每个completely-random tree forests 包含500个完全随机的树，其中，每棵树随机选择属性分裂节点，直至纯净的叶子节点。每个random forest包含500个树，随机选择√dd个属性作为候选集，再依据jini分裂。

给定一个实例，通过计算实例所落在的叶子节点上，不同类别训练样本的比例，之后将该森林中每棵树的结果作以平均，每个forest就可以得到类别分布的估计。这个类别分布构成一个类别向量，再与之前原始特征拼接，作为下一层的输入。

假设有3个类别，那么四个森林，每个都会产生一个3维的类别向量，下一层会接收到12（=3×4=3×4）个扩增特征。

这里类别特征太简单，这样的小的增广特征，所能传递的增广信息很有限，会被原始特征淹没。很明显，更可以合并更多特征，比如父节点的类别分布（先验分布），兄弟节点的类别分布（互补分布）。

每个森林的类别向量利用k折交叉验证得到，以防止过拟合。扩展完一层后，整个级联结构可在验证集上面测试性能，若没有显著提高，训练过程会终止，故而层数可以自动确定。这也是gcForest能够自动决定模型复杂度的原因。

Multi-Grained Scanning

由CNNs和RNNs启发，利用多粒度扫描加强cascade forest。

如上图，利用滑动窗口扫描原始特征。假设原始特征为400，窗口大小为100。对于序列数据，一次滑动得到一个100维的特征向量，共生成301个特征向量。如果原始数据存在空间联系，例如400图像像素可视为20×2020×20的panel，10×1010×10的窗口会生成121个特征向量。特征向量的类别标签与原始数据的标签保持一致。以上图序列数据为例，假设有3类的前提下，每棵树利用100维的窗口生成了301个特征向量，同时就有301个3维的类别向量，即对应原始400维的特征向量就生成了一个1806维的转换特征。

每个特征向量的标签，分配成原始数据的标签不可避免的有问题。可采用Flipping Output方法，随机改变一些输入样本的标签。

当转换特征太长时，可作特征采样，具体来说是对滑动窗口扫描所得instances的二次采样。此采样过程与Random Subsapace方法有关（从初始属性集中抽取若干个属性子集, 再基于每个属性子集训练一个基学习器）。

上图仅仅展示了一个size的滑动窗口，通过使用多尺度的滑动窗口，便能生成多尺度下的特征向量，如下图。

Overall Procedure and Hyper-Parameters

上图展示了gcForest的整体算法结构。假定原始输入为400原始特征，多粒度扫描采用三个窗口size。对于mm个训练样本，窗口大小为100时会生成301×m301×m个100维的训练数据集。用这些数据去训练一个completely-random tree forest和一个random forest，每个都包含500个树。当要预测3个类别时，一个instance会有一个1806维的特征向量。做过如此转换的训练集，之后将在cascade forest的第一级上训练。

同样的，大小为200、300的滑动窗口对于每一个原始的训练样本，会分别生成一个1206维、606维的特征向量。转换的特征向量（12−dim12−dim），用前一级生成的类别向量增广之后，分别在第二级和第三级的cascade forest中训练。一直重复这个过程，直到验证集的性能收敛。最终的模型可视为是一个cascade of cascades，每个cascade包括多个level，每个level对应于一个扫描粒度。对于复杂问题，在计算资源允许的前提下可尝试更多粒度。

对于test instance，在经过多粒度扫描之后得到其对应转换表示，然后进入cascade直到最后一层。最后的预测结果是通过融合最后一层四个forest的四个3维类别向量，然后选取最大值的那个类别。

Table 1 总结了DNN和gcForest的超参数，我们实验中参数的默认值也已给出。

Experiments

Configuration

gcForest默认参数：

4 completely-random tree forest, 4 random forest
500 trees
three-fold cross validation
0.8 growing set, 0.2 estimating set, get number of levels, then retrian all
多粒度扫描过程，窗口大小⌊d/16⌋⌊d/16⌋、⌊d/8⌋⌊d/8⌋、⌊d/4⌋⌊d/4⌋
若原始数据由panel结构，按图4方法处理
针对不同任务的参数精调对精度有帮助，为了显示超参数设置比DNNs更容易，故采用相同的参数

对应DNNs，ReLU、cross-entropy、adadelta、droupout 0.25 or 0.5

Results

Image Categorization

MNIST（train/val : 60000/1000）：LeNet-5，SVM with rbf, Random Forest with 2000 trees, Deep Belief Nets

Face Recognition

ORL (400 gray-scale face images from 40 people):

CNN 2个卷积层，32个3×33×3kernel的feature maps，每个卷积层后一个2×22×2的最大池化，128的线性层和40的softmax ReLU, cross-entropy loss, dropout rate of 0.25, adadelta, batch size 10, epochs 50
kNN with k=3

Music Classification

GTZAN (10个流派，每个流派100个flips，train/val : 700/300 MFCC feature 1280×131280×13)

CNN 32个13×813×8kernel的feature maps，跟着一个池化层，2个全连接层1024，512，最后一个softmax Relu, categorical cross-entropy
Random Forest, Logistic Regression, SVM

Hand Movement Recognition

sEMG (time series, 1800 records for 6 classes)

MLP input-1024-512-output
LSTM 128 hidden units, sequence length 6

Sentiment Classification

IMDB (movie reviews, tf-idf features, train/val : 25000/25000)

MLP imput-1024-1024-512-256-output
tf-idf 没有空间或者序列特征，故gcForest跳过多粒度扫描

Low-Dimensional Data

UCI-datasets:

LETTER 16 dim, 16000/4000
ADULT 14 dim, 32561/16281
YEAST 8 dim, 1038/446

对比算法：

MLPs input-70\30\50-50\20\30-output
gcForest 跳过多粒度扫描

High-Dimensional Data

CIFAR-10 (50000/10000 10 classes)

增广特征在高维的原始特征前，出现淹没现象。效果提高：task-specific tuning, more grains, gbdt(简单替换最后一层)

Influence of Multi-Grained Scanning

Influence of Cascade Structure

图5介绍了cascade of cascades的多粒度融合方法，当然，也可将各粒度的特征直接拼接，结构如下图：

下表是gcForest与gcForestconcconc的性能比较：

Influence of Larger Models

由于计算资源限制，并未尝试更大模型。GPU目前无法加速gcForest！！！！！！

Running TIme

PC with 2 Intel E5 2695 v4 CPUs (18 cores)

IMDB dataset (25,000 examples with 5,000 features):

267.1 seconds per cascade level, automatically terminates with 9 cascade levels, amounting to 2,404 seconds or 40 minutes.
amounting to 4,650 seconds or 77.5 minutes. if using GPU (Nvidia Titan X pascal), amounting to 700 seconds or 11.6 minutes

多粒度扫描会增加时间成本，但是不同的粒度扫描过程内在并行，每一级内部的foerst生成过程也是并行的。故以后效率提升可用更好的并行化方法。

Related Work

Future Issues

加强特征re-representation过程：为了解决高维数据的特征淹没问题，可引入父节点，兄弟节点，决策路径等特征
加速，内存占用优化：
- 借用相关硬件架构，如Intel KNL；
- 算法分布式实现；
- feature sample以减少内存占用，还能增加多样性
- reuse some components
completely-random tree forests不仅增加了多样性，也有可能利用unlabeled data

Environment

CPU: Intel i5-7300HQ(4 cores, 2.50GHz)

Mem: 8GB total (∼5∼5GB for testing)

Datasets: MNIST

Official Codes：Github/gcForest

Test a:

XGBoost: n_estimators = 10, max_depth = 5
Radom Forest: n_estimators = 10
Extra-Trees: n_estimators = 10
Logistic Regression
each module cv = 5

Results:

Test b

XGBoost: n_estimators = 10, max_depth = 5
Radom Forest: n_estimators = 15
Extra-Trees: n_estimators = 15
Extra-Trees: n_estimators = 15
each module cv = 5