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

论文概况	详细
标题	《Improving Deep Forest by Exploiting High-order Interactions》
作者	Yi-He Chen, Shen-Huan Lyu, Yuan Jiang
发表会议	IEEE International Conference on Data Mining (ICDM)
发表年份	2021
会议等级	CCF-B
论文代码	https://git.io/DM487

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

研究动机

尽管最近深度神经网络在数值数据上的发展相当有吸引力，但更多的现实问题属于分类和混合建模任务。这样的任务中很多属性只能从中得到定性特征，不能得到定量特征，因此将深度森林等非神经网络深度模型应用和探索到更广泛的任务中是未来深度学习的一个重要方向。虽然 gcForest 在经验和理论上都显示出了巨大的潜力，但 gcForest 存在以下 3 个缺点：

预测的类概率传递的信息非常有限，当输入特征比输出标签多得多时会导致预测向量很可能被原始特征淹没；
决策树森林已经是相当稳定的预测器，不同森林的集合可能会导致冗余且缺乏多样性；
基于预测的特征表示依赖于多层森林模型的存储，在测试过程中逐级进行预测时需要大量的内存和时间消耗。

文章贡献

为了对深度森林设计出信息量更大、计算成本更低的特征表示，本文提出了一种新的深度森林模型——高阶交互深度森林(hiDF)，利用输入特征的稳定高阶交互来生成信息丰富且多样化的特征表示。具体而言，本文设计了一个广义版本的随机交叉树(gRIT)来发现稳定的高阶相互作用，并应用激活线性组合(ALC)将这些相互作用转化为新的特征表示，这些特征表示可以跨多层与输入特征交互。在级联的堆叠下，hiDF 可以有效地挖掘输入特征之间的高阶交互，并利用它们来提高预测性能。通过实验表明，hiDF 在显著减少时间和内存成本的情况下获得了极具竞争力的预测性能。

本文方法

本文的 hiDF 采用多层结构进行表示学习，和 DF 之间的区别在于 DF 使用每层的预测作为表示，hiDF 使用高阶特征交互作为表示。hiDF 主要包括以下三个步骤：

在输入特征上拟合一个随机森林，从这些决策树中提取决策规则，然后利用广义随机交叉树（Grit）对这些决策规则进行处理，以获得特征交互；
在外部 bagging 过程中执行第一步，额外的数据扰动允许模型通过评估与识别的特征交互相关的稳定性来进行“交互选择”，只有具有高稳定性分数的特征交互通过激活线性组合(ALC)来产生新的特征表示；
应用度量感知机制自适应地堆叠后续的层次，降低过拟合的风险。

通过 gRIT 和 ERF 提取特征交互

hiDF 将特征交互识别为决策规则中的条件集合，决策规则的形式如下公式所示。对于连续变量 xi 可以采用 xi ≥ ti 的形式表示，其中 ti 是一个确定的阈值。对于分类变量则使用独热编码进行转换，就可以得到和连续变量类似的形式。

hiDF 只考虑一个决策规则，为了简洁地进行表示，本文使用带有阈值 ti 的有符号特征指数 ±i 来描述一个条件，其中正指数表示 xi≥ti，负指数表示 xi<ti。此时条件 i 下的决策规则 R 可以用如下公式所示，其中 I^index 是 i 个有符号特征指数的向量，I^threshold 表示该特征的阈值。

由于决策规则可以通过从根节点到叶节点的决策路径进行编码，本文使用了富集随机森林(Enriched random forests, erf)从数据中提取决策规则。erf 可以看作是具有软降维过程的 rf，它可以在输入空间中选择信息更丰富的特征。erf 有两个缺点，首先每个决策规则只对应少量的实例，缺乏统计上的重要性。其次是决策规则冗长复杂，不能进行很好地概括。针对这两个问题，hiDF 应用 gRIT 来处理这些的决策规则。gRIT 的主要思想是根据统计信息对决策规则进行剪枝，可以进一步发现具有较好泛化能力的重要特征交互。
gRIT 的流程如下伪代码所示，gRIT 包含 L 个交互树 l∈{1,...,L}，从数据中均匀采样 j 个样本索引 {i1，…ij} ，它们对应的决策规则被表示为{I_i1, I_ij}。然后对 I_i1∩…∩I_ij进行 j 折交集，实现保留信息特征并剔除噪声特征的作用。如果特征 xi 的特征交互 I 足够普遍，那么它将以高概率在交集中幸存下来。

特征交互的稳定性分数

hiDF 使用外部 bagging 评估与已识别特征交互的相关稳定性，生成 B 个 bootstrap 样本数据 D(b)(b={1,…,B})，拟在每个样本 D(B) 上拟合 B 个富集随机森林 ERF。然后使用 gRIT 对这 B 组特征交互 T(B) 进行评分，使用如下公式定义的稳定性公式作为打分的标准，它反映了交互 I 在 B 个 bootstrap 样本中出现的普遍性。

得到获取的特征交互及其稳定性分数后，需要保留那些具有前 k 分数或分数大于预先指定阈值的交互。这部分使用包含加权和和非线性激活函数的激活线性组合(Activated Linear Combination, ALC)为每个交互生成一个新特征，并用 rnew 表示这些新特征。
例如现在有特征交互 I={I^index,I^threshold}={(−2,3),(t2,t3)}，每个特征的 gini 重要性为 w=(w2, w3)，r_new(w, I)由如下公式计算。其中 σ(x)=x·1[x≥0] 为非线性激活函数，将新特征与当前输入特征连接起来就形成下一层的输入特征。

自适应层次生成

相对于浅层结构，深度结构促进了特征的重用，更倾向于发现高阶特征交互。hiDF 同样采用了多层结构，它的每一层都是随机森林的集合，在此基础上应用 erf 和 gRIT 来发现丰富的特征交互。然后通过稳定性分数来生成新的特征向量，将其与输入特征向量连接起来形成新的特征表示，作为下一层的输入。在扩展每个新层之后，hiDF 使用一个单独的验证集估计当前整个结构的性能，如果没有明显的性能提升，hiDF 将终止训练过程。训练的过程如下伪代码所示，自适应分层增长策略可以降低过拟合的风险，也有利于自动确定 hiDF 模型复杂度的自动确定。

实验结果

合成数据集实验

首先使用一个合成数据集来证明 hiDF 可以通过多层特征交互来学习特征表示，合成数据集是由 R2 上的高斯数据生成的二分类任务，具有球形决策边界(如下图 a 所示)。合成数据集包含 10000 个示例，其中 80% 用于训练、20% 用于测试。在特征空间中还有额外的 500 个均匀随机噪声特征，这样的无信息的随机特征使分类任务更加复杂。
hiDF 的第 6 层和第 12 层的输出特征表示通过 t-SNE 表示，如下图 (b) 所示。可见 hiDF 可以从原始输入空间获得信息丰富的特征表示，并且随着层的加深，数据点变得线性可分，表明 hiDF 具有与深度神经网络相似的表示学习能力。

接着通过边际重要性度量(marginal importance metric)检验在不同特征交互顺序中生成的新特征的重要性，结果如下箱线图所示。结果说明了由高阶交互产生的新特征往往具有更大的特征重要性，对学习任务有更大的影响。由于高阶特征交互通常在更深的层中发现，可说明 hiDF 可以从其分层结构中受益。