作者 | 俞壹龄 校对 | 李仲深
今天给大家介绍的是厦门大学信息学院刘昆宏教授等人在Soft Computing上发表的论文”Improving deep forestby ensemble pruning based on feature vectorization and quantum walks”。众所周知，良好的剪枝策略可以提高随机森林的性能。作者创新性地利用量子游走这一图上的动力学过程，对随机森林中节点性能进行拓扑排序，从而实现了一种基于排序的高效剪枝策略，提高算法性能。
一、研究背景
两年前，南京大学周志华教授课题组提出了一种新的神经网络结构：深度森林。这是一种使用随机森林来作为神经元的级联网络结构。作为一种决策树集成方法，他能够在小型数据集上学到十分良好的特征，从而取得较高的算法精度。但是，级联的随机森林带来了相当大的计算开销，同时森林中也存在相当的分类器性能不佳或者是存在一定冗余，导致了整个模型复杂度过高，同时也限制了算法的性能。这时候就需要使用算法来对整个模型进行优化，剪枝便是这样一种常见的决策树优化算法。但是现有的剪枝方案不仅复杂度过高，而且难以直接将节点的两个性能指标：准确性和多样性结合。作者为了解决随机森林遇到的剪枝问题，提出了这种基于特征向量化和量子游走的集成剪枝技术。
二、模型与方法
具体的方案分为三步：
2.1 决策树的特征向量化
将决策树的特征向量化，提供一种对于决策树性能的多维度的评估方案。具体的特征包括但不仅限于：决策树的节点数、深度，以及多样性贡献和margin score（一种综合考量模型泛化性能和分类性能的指标）。
图1. 边际得分计算公式
2.2 RF(random forest)的图表示
将单独的森林抽象成一个加权图，具体一点来说就是把森林中的每一棵树作为节点，以该树的特征作为节点特征。并将两棵树之间的余弦相似度作为边上的权重，通过权重矩阵来对节点之间的连接进行刻画。
2.3 量子游走
在将RF抽象成图网络之后，通过图上的连续时间量子游走算法来探索所有节点之间的复杂关系，以便从中选择具有较高Margin score和多样性的决策树。
连续时间量子游走的具体实现如下：1）、初始化每个顶点的量子状态。2)、使用演化算子基于连续时间来控制量子状态的变化。3）、通过某节点量子行走的分数来衡量对应决策树的性能。
图2. 量子游走算法的流程
RF中的每一个顶点的初始量子状态都由其邻接矩阵A的一个特征向量来表述。整个量子游走的演变过程通过算子e-iLt来进行刻画。(为简便计，记状态转移算子e-iLt为状态转移矩阵P。该算子中的L = D - A为拉普拉斯矩阵，描述了整个图的结构关系。)
图3. 图中t时刻量子状态的演化
记At为t时刻的邻接矩阵，我们对节点量子游走的打分如下：对At矩阵的第u行进行累加。
图4. 量子游走分数的定义
2.4 基于排序的剪枝
通过以量子行走的分数进行生序排列，取前35%作为最终的模型。
三、实验结果
3.1 性能
PDF(Pruned Deep Forest)相比于传统DF(Deep Forest)在准确性上大约有着1-3个点的提升。相较于传统的机器学习模型的提升更大。
图5. 各类模型分类准确率对比图
3.2 效率
PDF的运行效率提升很大。对于一个多分类的问题，它的训练效率、剪枝效率和分类效率都很高。具体情况详见下图。
图6. 剪枝深度森林的训练、剪枝和分类时间
3.3 算法优化
量子游走算法性能良好，被剔除节点的概率分布函数与节点的性能函数成反比。性能好的节点被剔除的概率很低，性能差的节点被剔除的概率较高。具体情况详见下图。
图7. 深度森林中被选择决策树的分布情况
四、总结
多粒度级联森林作为一种作为一种良好的集成学习方案，在小型数据集上具有相当良好的表现。整个网络由级联的随机森林组成。所以无论是决策树的优化、随机森林的优化还是整个网络结构的优化都可以带来性能的提升。本文站在随机森林优化的角度提出了一种新的基于排序的剪枝策略。但是，深度森林的优化不能局限于次。我们还可以尝试更多的可能性。
参考文献
Gao, J., Liu, K., Wang,B. et al. Improving deep forest by ensemble pruning based on featurevectorization and quantum walks. Soft Comput (2020).
https://doi.org/10.1007/s00500-020-05274-z
https://link.springer.com/article/10.1007/s00500-020-05274-z
