Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。

论文概况	详细
标题	《Deep Forest》
作者	Zhi-Hua Zhou, Ji Feng
发表期刊	National Science Review
发表年份	2018
期刊等级	中科院 SCI 期刊分区(2022年12月最新升级版）1 区、综合类顶刊
论文影响	首次提出基于树模型的深度学习算法
论文代码	https://deep-forest.readthedocs.io/en/stable/

作者单位：
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China

研究动机

在深度学习领域中，深度神经网络(DNN)在视觉和音频任务中的已经取得巨大成功，目前几乎所有深度学习应用都是建立在 DNN 上。DNN 主要使用了多层参数化的可微非线性模块，这些模块通过反向传播训练。但 DNN 也存在许多不足，主要包括以下几点：

DNN 有太多的超参数，学习性能严重依赖于调参。DNN 的干扰因素多且配置组合的情况几乎无限，对其进行理论分析也非常困难。
DNN 训练需要大量的训练数据，当数据集是中、小规模训练数据的话可能效果不好。在现实中由于标注成本高，许多真实任务仍然缺乏足够数量的标注数据。
神经网络是黑盒模型，模型的可解释性较差。在 DNN 训练之前必须确定网络结构，提前确定模型的复杂度。

同时仍然有一些任务无法应用 DNN，例如在 Kaggle 竞赛的一些任务中使用 Random Forest 或 XGBoost 的效果更好。综上所述，本文有充分的理由去探索非 DNN 的深度学习模型。

文章贡献

本文使用不可微模块实现深度学习进行的探索，提出了一种非 DNN 的深度森林算法 gcForest(多粒度级联森林)。gcForest 具有级联结构，可以通过森林进行表示学习。它的表征学习能力可以通过多粒度扫描进一步增强，从而可能使 gcForest 具有上下文或结构感知能力。级联的级别可以自动确定，超参数比 DNN 少得多，使其能以数据依赖的方式确定模型规模，用户能够根据计算资源控制训练成本。实验表明在大多数情况下，gcForest 能够通过使用默认设置在不同领域的数据集中获得出色的性能。

设计来源

DNN

表示学习能力是 DNN 成功的关键，DNN 中表示学习的关键在于逐层处理。如下图所示，随着模型层次从底部向上延伸，逐步构建出了高阶特征。注意到 DNN 的模型都较为复杂，但为什么不是模型复杂性提升了模型性能呢？因为对于浅层网络而言，可以添加几乎无限数量的隐藏单元来增加浅层网络的复杂性，显然不能从模型复杂性来解释为什么浅层网络的性能不佳。反之无论浅层网络的模型有多复杂，其都不具备逐层处理特征的能力，因此更有可能是 DNN 的高性能是来源于逐层处理。虽然本文还没有一个严格理论佐证，但这个猜想为 gcForest 的设计提供了重要的灵感。

同时也有一些机器学习模型是逐层处理的，例如 DT 和 Booting，但是它们的性能并不如 DNN 出色。本文认为和 DNN 相比，以上模型都是在原始特征表示上进行学习，不会在学习过程中创建新的特征空间。同时这些模型的模型复杂度也有限，可能也会在一定程度上限制模型的学习能力。
综上所述，本文推测 DNN 的高性能存在三个关键特征：逐层处理、模型内特征变换、足够的模型复杂性。

集成学习

集成学习是一种机器学习范式，核心思想是训练多个基学习器后集成组合来完成任务，它通常比训练单个学习器具有更好的泛化性能。集成学习器性能要好的关键是基学习器满足好而不同，基学习器的互补性比纯粹的准确性更重要。如下是误差——歧义分解理论推导出的方程，其中 E 表示集成的误差，E¯ 表示集成中单个基分类器的平均误差，A¯ 表示单个基分类器之间的平均歧义，也就是多样性。由该公式可知，个体分类器越准确、越多样化，集成效果越好。

该方程对集成学习器的构建提供了一般性的指导，但不能作为优化的目标函数，因为在推导过程中模糊项是数学定义的，不能直接操作。后来学界中设计了一些多样性度量方法，但没有一个被作为广泛接受的多样性定义。在实践中，多样性增强的基本策略是在训练过程中引入基于启发式的随机性，主要有对数据样本、特征空间、超参数、输出表示这几种操作。

本文方法

级联森林

受 DNN 的逐层处理的启发，gcForest 采用了如下图所示的级联结构。其中每一层级联接收其前一层处理的特征信息，并将其处理结果输出到下一层。每一层都是 DT 森林的集成，也就是 ensemble of ensembles。此处引入不同类型的森林来提高多样性，简单起见使用两个随机森林 RF 和两个极端随机森林 ETs，图中分别用蓝色和黑色 unit 表示。每个 ETs 包含 500 棵极端随机树 ET，ET 通过在树的每个节点随机选择一个特征进行分裂，并将树生长到纯叶子。每个 RF 包含 500 棵 DT，通过随机选择特征子集并根据 gini 值生成划分。

给定一个实例，每个森林将产生类的分布估计，方法是计算实例所在叶节点上不同类别的样本的百分比，然后对同一森林中的所有树进行平均。该过程如下图所示，其中红色突出显示了实例遍历到叶节点的路径。估计的类分布形成一个类向量与原始特征向量连接，输入到下一级级联。例如有三个类，则四个森林中的每一个都将产生一个三维类向量，下一级级联将接收 12=3×4 个增强特征。

注意此处的特征构造使用的是最简单的类向量，如此少量的增强特征传递的增强信息可能非常有限，当原始特征向量是高维的时候还可能被淹没。后续的实验中证明这样的简单特征增强方法已经是有益的，如果对增强特征进行改进还可能进一步提升性能。
为了减少过拟合的风险，每个森林产生的类向量通过 k-fold 交叉验证生成。每个实例将被用作 k−1 次的训练数据，产生 k−1 个类向量，然后将其平均产生最终的类向量作为下一级级联的增强特征。扩展一个新的层次后在验证集上估计整个级联的性能，如果没有显著的性能增益则训练过程终止，实现自动确定级联级别的数量。可见 gcForest 通过适时终止训练来自适应地决定模型复杂度，使得它可以适用于不同规模的训练数据。

多粒度扫描

DNN 在处理具有空间或时序关系的特征方面非常强大，例如 CNN 和 RNN，在这样的启发下本文使用多粒度扫描来增强级联森林。多粒度扫描使用滑动窗口用扫描原始特征，从相同大小的窗口中提取的实例将用于训练一个 RF 和一个 ETs，然后生成类向量并将其连接作为转换后的特征。通过使用不同大小的滑动窗口，将生成不同粒度的特征向量。
多粒度扫描的过程如下图所示，假设有 400 个原始特征，窗口大小为 100。对于序列数据滑动一个特征的窗口生成 100 维特征向量，总共产生 301 个特征向量。如果原始特征具有空间关系，例如 20×20 = 400 的图像，则 10×10 窗口将产生 121 个特征向量。假设有 3 个类并使用一个 100 维的窗口，每个森林生成 301 个三维类向量，最终得到一个 1806 维的变换特征向量。

对于从滑动窗口中得到的实例，本文简单地为它们分配原始训练样例的标签。这里一些标签赋予本质上是不正确的，例如假设原始训练样例是关于“汽车”的图像，显然许多提取的实例不包含汽车。此处涉及到翻转输出方法，该方法是用于增强集成多样性的输出表示操作的代表方法。当转换的特征向量太长而无法进行训练时可以进行特征选择，涉及到集成学习的 Random Subspace 方法，它也是增强集成多样性的输入特征操作的代表方法。

整体结构

gcForest 的整体结构如下图所示，gcForest 还使用了 200 和 300 大小的滑动窗口，它们分别为每个原始训练样本生成 1206、606 维特征向量。变换后的特征向量与前一级生成的类向量进行增广，分别用于二级和三级梯级森林的训练。此过程将重复，直到验证性能收敛。最终的模型实际上是一个级联的级联，每个级联由多个级别组成，每个级别对应于一个扫描粒度。给定一个测试样本，它将通过多粒度扫描过程来获得相应的转换后的特征表示，然后进行级联直到最后一级。将最后一层的 4 个类向量聚合，取聚合值最大的类作为最终的预测结果。

下表总结了 DNN 和 gcForest 的超参数，同时作为实验中使用的默认值。

实验结果

实验设置

在所有的实验中，gcForest 都使用了相同的级联结构，每个级联由 4 个 ETs 和 4 个 RF 组成，每个森林包含 500 棵树。使用三折交叉验证生成类向量，将训练集按照 4:1 分为训练集和验证集，用训练集对级联进行生长，用验证集对性能进行估计。如果增加一个新的水平不能提高性能则终止级联的增长，然后在合并训练集和验证集的基础上对级联进行再训练。
对于 d 个原始特征，多粒度扫描将使用三种窗口大小，分别是 d/16、d/8、d/4，如果原始特征是二维的则特征窗口也相应使用二维。
本文为了强调 gcForest 的超参数设置比 DNN 简单，gcForest 在所有数据集使用相同的设置，DNN 分别进行调参。
DNN 使用 ReLU 作为激活函数，使用交叉熵作为损失函数，使用 adadelta 优化器进行优化。根据训练数据的规模，隐层的 dropout 率为 0.25 或 0.5。使用的 DNN 将在验证集上检查各种不同配置的性能，并选择性能最好的一个，然后在训练集上重新训练整个网络并报告测试精度。

对比实验

图像分类

该实验使用 MNIST 数据集，其中包含 60000 张大小为 28×28 的图像。对比算法是 LeNet-5、rbf 核 SVM 、具有 2000 棵树的 RF 进行比较，并引用其他论文中的 Deep Belief Nets 的结果。实验结果如下表所示，可见 gcForest 在使用默认设置的情况下获得了最好的性能。

人脸识别

该实验使用 ORL 数据集，其中包含 40 个人的 400 张灰度面部图像。使用测试出来性能最好的 CNN 进行实验，随机选择每人 5/7/9 张图像进行训练并报告剩余图像的测试性能。实验结果如下表所示，可见 gcForest 在使用默认设置的情况下在 3 种实验设置中获得了最好的性能。

音乐分类

该实验使用 GTZAN 数据集，其中包含 10 种类型的音乐片段。每种类型由 100 首 30 秒长的曲目表示。使用 MFCC 特征将原始声波转化为 1280×13 特征矩阵。对比算法是 CNN、MLP、RF、逻辑回归和、SVM，实验结果如下表所示，可见 gcForest 在使用默认设置的情况下获得了最好的性能。

手部动作识别

该实验使用 sEMG 数据集，其中包含由 1800 条手部动作记录组成。该数据集是一个时间序列数据集，其中肌电传感器每秒捕获 500 个特征，每个记录与 3000 个特征相关联。对比算法是 LSTM、MLP、RF、逻辑回归、SVM，实验结果如下表所示，可见 gcForest 在使用默认设置的情况下获得了最好的性能。

情感分类

该实验使用 IMDB 数据集，其中包含 50000 条电影评论和，使用 TF-IDF 特性表示。对比算法是 CNN、MLP、RF、逻辑回归、SVM，其中 CNN 引用于一篇使用词嵌入进行训练的结果。实验结果如下表所示，可见 gcForest 在使用默认设置的情况下获得了最好的性能。

不同维度数据实验

低维数据集

此处使用 UCI 中特征数量相对较少的数据集进行实验，包括 LETTER、ADULT、YEAST 数据集。对比算法是 RF 和 MLP，其中 3 个数据集分别使用了最优的结构设置，gcForest 不使用多粒度扫描。实验结果如下表所示，可见 gcForest 在使用默认设置的情况下获得了最好的性能。

高维数据集

此处使用 CIFAR-10 数据集，其中包含 10 个类别共 60000 张图像。每个图像都是 32×32 的彩色图像，具有 8 个灰度级，因此每个实例是 8192 维。测试结果如下表所示，其中也引用了一些其他论文的几种 DNN 的结果。目前只使用来自每个森林的 10 维的增强特征向量，尽管默认设置的 gcForest 不如最先进的 DNN，但已经是非 DNN 方法中最好的。gcForest 的性能可以通过特定于任务的调优进一步提高，例如通过包含更多粒度的 gcForest(5 grains)。gcForest(gbdt)的性能得到了显著提高，它只是用 gbdt 替换了最终级别。如果可以训练更大的 gcForest 模型，可以获得更好的性能。

运行时间

对于 IMDB 数据集(25000 个样本、5000 个特征)，gcForest 的每个级联需要 267.1 秒，并自动终止在第 9 级联，总计 2404 秒或 40 分钟。相比之下，在同一数据集上 MLP 需要 50 个 epoch 来收敛，每个 epoch 需要 93 秒，训练时间为 4650 秒或 77.5 分钟。如果使用 GPU 则每个 epoch 需要 14 秒(批大小为 32)，总计 700 秒或 11.6 分钟。ETs 和 RF 都是并行集成方法，可以通过优化并行实现可以进一步提高 gcForest 的效率。同时上述比较对 gcForest 有些不公平，因为在尝试 DNN 的架构和参数的时间并没有结合考虑。

性能趋势

下图显示了当级联级数增加时 gcForest 的性能趋势，可以看出 gcForest 从一开始的性能不如 SVM 和 MLP，然后逐渐提高。

消融实验

多粒度扫描

此处将 gcForest 与单独的级联森林在 MNIST、GTZAN、sEMG 数据集上进行了比较。实验结果如下表所示，显然当存在空间或顺序特征关系时，多粒度扫描过程明显有助于提高性能。

极端随机树森林

为了研究 ETs 的贡献，将 gcForest 与用 RF 代替了 ETs 的模型进行比较。在 MNIST/IMDB/LETTER上，使用/不使用 ETs 的测试准确率分别为 99.26%/89.16%/97.40% 和 99.11%/87.62%/96.65%。结果表明无论是否应用多粒度扫描，还是数据是否低维，完全随机森林都是有帮助的。

级联结构

还有其他可能的方法来利用来自多粒度的特征，例如下图所示的将所有特征连接在一起的变体。

实验结果如下表所示，将多个粒度的特征连接起来不如 gcForest 中的当前设计好。

规模较大的模型

下图的实验结果表明，更大的模型往往提供更好的性能。

未来工作

未来对增强特征重新表示过程的改进是很重要的，gcForest 的实现采用最简单的类向量形式。当原始特征向量是高维的时候，这样少量的增强特征很容易被淹没。此处还可以使用更多的特征，如表示先验分布的父节点的类分布、表示互补分布的兄弟节点、决策路径编码等。更长的类向量可以支持联合的多粒度扫描过程，从而带来更大的重新表示灵活性。
另一个重要的未来问题是加速和减少内存消耗，构建更大的深度森林可能会在实践中带来更好的泛化性能。DNN 的成功很大程度上归功于 GPU 提供的加速，但森林结构并不适合 GPU。一种可能性是考虑一些新的计算设备，另一种方法是使用分布式计算实现。当多粒度扫描产生的变换特征向量太长而无法容纳时，可以执行特征采样。这不仅有助于减少存储，而且还提供了另一种渠道来增强集成的多样性。除了随机抽样之外，探索更智能的抽样策略也可能有效，例如 BLB 或特征哈希。难例挖掘策略可能有助于提高泛化性能，以及考虑重用部分组件。当学习到的模型较大时，可以使用二次学习策略将模型缩小到较小的模型，不仅有助于减少存储，而且有助于提高预测效率。
ETs 的使用不仅有助于提高多样性，而且还提供了利用未标记数据的机会。这也 gcForest 提供了结合主动学习或半监督学习策略的机会。