Optimized Sequential Testing for Binary Ensemble Classifiers

问题陈述
集成分类器（如随机森林）通过多数投票结合多个基模型（如决策树）的预测，以实现高准确率。然而，较大的集成模型在推理过程中会产生显著的计算成本，这对于低功耗设备或高频应用而言是一个问题。本文解决的核心问题是如何在不显著降低准确率的情况下，降低二分类集成分类器的测试时计算成本。具体而言，作者研究了在何时停止对基模型进行顺序评估（即一旦出现“明确多数”时停止），而不是执行所有的 $N$ 个模型。其目标是最小化期望执行的基模型数量（运行时间），同时严格控制“分歧率”（即提前停止的集成结果与完整集成结果不同的概率）。

方法论
论文将提前停止问题形式化为一个顺序测试任务，其状态由 $(i, j)$ 定义，其中 $i$ 代表已执行的基模型数量，$j$ 代表正向票数。作者假设基模型按随机顺序执行，从而允许使用超几何分布来建模达到任何状态的概率，而不假设基模型之间相互独立。

为了寻找最优停止策略，作者提出了三种不同的优化框架，所有框架都通过线性规划（LP）进行构建，以确保计算效率：

1. 极小极大（Minimax）： 在满足最坏情况下的分歧率约束下，最小化最坏情况下的期望运行时间。该方法不需要预先知道正向票数（$n$）的分布。
2. 极小均值（Minimean）： 在已知或估计的分布 $\hat{D}$ 下，在满足期望分歧率约束的情况下，最小化期望运行时间。
3. 极小混合（Minimixed）： 在假设存在 $n$ 的分布的情况下，在满足最坏情况下的分歧率约束下，最小化期望运行时间。

作者证明了原始的非线性优化问题可以通过条件概率决策变量（$p_{ij}, \pi_{ij}, \bar{\pi}_{ij}$）进行重构。这种重构将问题转化为一个拥有 $O(N^3)$ 个决策变量的线性规划问题，即使对于拥有数百棵树的集成模型也能高效求解。生成的策略在很大程度上是确定性的，遵循一个简单的“包络线（envelope）”规则：如果正向票数超过上限阈值或在特定步骤 $i$ 下低于下限阈值，则停止。

核心贡献

• 理论构建： 论文为多数投票集成的提前停止提供了一个严谨的数学框架，正式定义了停止策略以及衡量指标（运行时间和分歧率）。
• 最优线性规划解： 作者表明，针对三种不同最优性概念（极小极大、极小均值、极小混合）的最优停止策略，可以通过求解线性规划来获得。这与以往依赖启发式方法或假设独立性的研究工作形成了对比。
• 无需独立性假设： 与以往用于集成模型的顺序测试方法（例如 Schwing 等人，2011 年）不同，本方法不假设基模型相互独立，这使其能够直接应用于决策树预测具有相关性的随机森林。
• 可预计算策略： 作者为各种集成规模和允许的分歧率（ADR）预计算了最优策略，从而可以立即应用而无需针对每个新数据集进行重新优化（特别是对于极小极大方法）。

实证结果
研究人员使用包含 $N=101$ 棵树的随机森林，在来自 UCI 机器学习库和 Grinsztajn 等人提出的基准测试的 27 个真实世界数据集上对这些方法进行了评估。

• 加速效果： 在大多数数据集上，所提方法实现了 4 倍或更多的加速（将运行时间减少到完整集成模型的 10–20%），同时保持了 0.1% ($10^{-3}$) 的分歧率。
• 性能差异： 极小均值方法（使用校准集来估计分布）通常提供了最高的加速比，其次是 极小混合，而 极小极大 最为保守。
• 数据集特征： 提前停止的效果与树的投票分布相关。在树对某一类投出压倒性选票（双峰分布）的数据集中，可以进行激进的提前停止。相反，在具有高基模型错误率和中心化投票分布（如 "Dota2" 和 "Hospitalization"）的数据集中，加速效果较小，因为难以早期达成共识。
• 对比： 所提方法优于 Schwing 等人（2011 年）提出的基准方法，后者依赖于二项置信带和独立性假设。

意义与声明
论文声称，这是第一个在不假设基模型相互独立的情况下，为基于多数决策的二分类集成分类器提供可证明最优提前停止策略的方法。作者强调，他们的方法允许用户训练更大、更准确的集成模型，并依靠停止策略来针对每次具体的推理仅利用必要的计算资源。

论文也谦虚地指出了其局限性：该方法仅限于二分类和无权重多数投票集成。它不能直接应用于多分类问题、回归问题或基模型具有特定权重或特定执行顺序的集成。此外，作者指出，虽然该方法与剪枝兼容，但对于已剪枝的森林，收益可能不会那么显著，因为剪枝旨在减少使提前停止有效的冗余（相关投票）。作者建议未来的工作应扩展到多分类和加权集成。