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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180426G09BR600?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券