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?

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

1. 深度模型是否只能用可微的模块构建
2. 不用反向传播可以训练深度模型吗
3. 在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 = \overline E - \overline A \tag1$$

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

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

1. data sample manipulation
2. input feature manipulation
3. learning parameter manipulation
4. 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个树，随机选择$\sqrt d$个属性作为候选集，再依据jini分裂。

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

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

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

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

Multi-Grained Scanning

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

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

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

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

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

Overall Procedure and Hyper-Parameters

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

同样的，大小为200、300的滑动窗口对于每一个原始的训练样本，会分别生成一个1206维、606维的特征向量。转换的特征向量（$12-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

• 多粒度扫描过程，窗口大小$\lfloor d/16\rfloor$、$\lfloor d/8\rfloor$、$\lfloor d/4\rfloor$

• 若原始数据由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\times3$kernel的feature maps，每个卷积层后一个$2\times 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\times 13$)

• CNN 32个$13\times 8$kernel的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与gcForest$_{conc}$的性能比较：

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 ($\sim 5$GB 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

Results:

在此只做了两个简单的测试，需要提前说明的是，在测试过程中，个人电脑上还在进行其它一些简单的工作，故测试环境十分不严谨，以下结果仅供参考。

从运行时间的表现来看，Test a中生成一个cascade layer平均需要2h50m左右，Test b则平均需要4m27s左右。 这样的时间差距，主要在于Test a的LogisticRegression运行十分耗时。

另外从memory consumption来看，对于MNIST这样的数据集，内存占用竟然超过了5G，并且，无论是Test a 还是Test b 都因为内存不足无法完成训练，在第7个cascade layer自动终止。 这里需要说明的是，官方源码中提供了设置set_keep_model_in_mem，default为True，故可将其改为False应当可以完成训练过程。但是，其内存占用还是过于庞大。

个人思考

• 采用原始特征拼接前一层转换特征的的方式，引入了类似shortcut-connection[1]，但是这个shortcut只引入原始特征，中间层级的转换特征并没有shortcut到之后层以供学习
• 多粒度扫描像1D和2D的convolution，但是这样的特征转换，对于label的处理个人觉得有些武断，对于序列与空间信息不够完善
• 由于data-dependent，如何进行迁移学习，如何fine-tune是个很大的问题[2]
• 大数据集上面到底表现如何
• 周志华老师的这项工作本意是“打开深度学习的大门”（if success），让人不禁有些新的想象。但就如文章中所说，目前的工作只是个萌芽，与成熟的DNNs在很多领域无法扳手腕，只是希望其以后成为一个alternative，而不是干掉DNNs。