Deep Forest 算法解读

曾凡祥

北京邮电大学通信与信息系统博士，现为去哪儿网金融事业部大数据算法工程师，主要进行机器学习、深度学习等人工智能技术的研究和应用。

摘要

无论是这几年兴起的神经网络，还是经典的 LR、SVM、Random Forest 等机器学习模型，本质上都可以看成是 Representation Learning (呈现/表征/表示学习)。深度学习之所以在图像、语音、 NLP 等方面表现出超强的性能，本质上是因为深度神经网络代表了由具体特征到抽象概念，由细粒度对象表示到高层语义的层层信息流动和聚集，其各层网络的权重共同构成了对数据的表示；而图像，语音，自然语言这类数据的表征上，完美与深度神经网络的表征能力契合。比如图像中，最小的表征单元为像素，由像素构成一些基本线段，构成物体边缘、轮廓，再构成物体部件，最后构成物体（当然这个过程可以更加细致）。

但是，深度学习在实际的研究和应用中，需要大量的调参，因此不少人称深度学习调参为一门“炼丹术”；再者，深度学习参数数量一般比较庞大，对数据集的规模有较大的需求。因此，才有了这篇 gcForest 算法的尝试，基于决策树的集成模型(Decision Tree based Ensemble Model)，和深度学习类似，具有很好的表征学习能力，同时降低调参难度（超参数规模很小，一套超参数，可以在不同数据集上表现出较好的性能），且对在小的数据集上表现优越。

后面对算法的几个关键组件：级联森林，多粒度滑动窗口扫描，整体过程结合自己的一些经验进行。

Fig.1 对每个随机森林得到的类分布取平均值，然后哪个类的概率最大就是哪个类。

Cascade Forest Structure （级联森林）

模拟神经网络的分层结构，级联森林每一层使用一组 Forest 来模拟表征，且每一层的森林会使用上一层的信息，作为自己的输入信息，同时其输出为下一层提供输入信息(这是一种表征学习的思想，神经网络里用卷积，用 MLP ，这里使用 forest 而已， GBDT/XGBoost 等其他的模型都可以放到这种级联的结构中来，它可以看成是一种结构化的 Ensemble of Ensemble Model)。

具体的，如图 Fig.1所示，每一层包含2个完全随机-森林和2个普通随机森林；完全森林包含500棵完全随机树(完全随机森林参考了 icForest 的构造，随机选择样本子集，且在分割时，随机选择特征，直到叶子结点只包含一个类别)；普通随机森林也包含500棵树，每棵树随机取 sqrt(d) 个特征，通过 gini 系数构建； 每个随机森林会输出维度为 K 的类概率分布（要预测 K 个类别），每一层随机森林会输出(2+2) K 个类概率分布；这4K 个输出将与原始的特征向量连在一起，作为下层随机森林的输入（随机森林输出类概率的过程如图 Fig.2所示，过程比较简单，不再详述。）；为降低过拟合风险，每一个随机森林的 K 个输出，会经过 K-fold 交叉验证（取 K-1次的平均值）；森林停止增长的判定（cascade 的级数自动根据数据设定）：每增加一层随机森林后，使用验证集对已经生成的整个模型进行性能验证，若性能没有明显的增长即停止增长。

Fig.2 Illustration of class vector generation. Different marks in leaf nodes imply different classes.（某个样本 x 落在某个叶子节点，计算该叶子节点的类概率分布，然后对所有树得到的概率分布取平均，即得到该森林的类分布概率。）

Multi-grained Scanning （多粒度滑动窗口扫描）

将原始特征通过多粒度扫描后，可以得到增强的特征向量，包含了特征的局部结构的多种尺度。

Fig.3 多粒度滑动窗口扫描过程，上半部分针对1D 向量特征，下半部分针对2D 类图像特征。

如图 Fig.2所示，对于维度为400的训练样本，预测3个类，用大小为100的滑动窗口扫描，可以得到301个滑动样本实例，每个实例维度为100；若用大小为200的滑动窗口，则可以得到201m 个样本实例，每个实例的维度为200；（对于1D 向量特征， N=D-W+1； N 为滑动样本实例， D 为原始特征维度， W 为窗口大小；对于2D 类图像特征， N=(D1-W1+1)(D2-W2+1)，其中 D1， D2对应输入的长度和宽度， W1和 W2对应在长度和宽度上的采样窗口大小）

以100的窗口为例，得到了301个样本实例，每个实例代表了一种局部结构或者亚采样样本，假如训练集有 m 个样本，则每个实例可以得到 m 个训练样本，这 m 个100维的特征作为随机森林的输入，可以得到一个3维的类概率分布；那么所有301个实例（局部结构），则可以得到301*3=906维的类概率分布，这些类概率分布连在一起作为特征呈现，输入到下一级随机森林；

这里，其实可以看到为什么这个方法能够较好应对小样本集，可以看到多粒度滑动窗口的方式，其功能类似于做了一次上采样操作，一个样本变成 N 个滑动实例样本，并且这些样本一定程度代表了原始样本的局部结构，因此多粒度滑动窗口操作，可以称之为结构化上采样，增强了模型的表征能力。

Fig.4 The overall procedure of gcForest. Suppose there are three classes to predict, raw features are 400-dim, three sliding window scales.（400维特征，3个类。第一步是多粒度特征生成，随机森林的个数为2；第二步是级联随机森林生成，随机森林个数为4。）

整个流程

实验效果

4 个完全随机森林和4个普通随机森林（每个森林500棵树），3-FOLD 交叉验证用来产生类分布向量，先通过将训练集分为增长集（80%）和估计集（20%），增长集用于构建级联森林，估计集用于确定是否停止增长，在停止增长后，将增长集和估计集合并，重新调整已经生成的级联随机森林；滑动窗口（三种， d/16,d/8,d/4， d 为特征维度）从论文给出的实验结果来看，性能是很不错的，在测试的数据集中，相当于或者好于深度神经网络模型。

总结

整体来讲， gcForest 尝试从深度学习/机器学习的本质表征学习入手，借鉴了深度学习的分层结构，利用 Ensemble of Decision Tree 来建模每一层表征，同时利用多粒度滑动窗口，学习数据更为丰富的表征信息。当然这是一种思想，级联森林中，森林具体使用什么模型，可以根据实际应用的计算资源、性能需求综合考虑，从 Random Forest, GBDT, XGboost 等模型选择即可。

这个算法直观上，可以进行一些可能的改进，比如最终预测结果中，可以由级联森林中间层预测的加权，而不是只用最后的特征输出（类似于深度学习中使用层次化特征的过程）；级联森林中间层的表征学习过程还可以做一些变化。回头需要测试一下在大量样本的情况下， gcForest 与神经网络模型的性能对比。

参考文献

[1] Zhihua Zhou and Ji Feng, Deep Forest: Towards An Alternative to Deep Neural Networks, IJCAI, 2017, https://arxiv.org/abs/1702.08835v2 (V2)[2] https://arxiv.org/pdf/1702.08835v1.pdf (V1)[3] Github地址: https://github.com/kingfengji/gcForest