独立成本与选择性模型下顺序过滤的最优性

# 独立成本与选择性模型下序列滤波的最优性
来源：https://arxiv.org/html/2606.07589
Hrishikesh Paranjape, Abhishek Mandal, Xian Sun已被2026年IEEE国际电学/信息技术会议（EIT 2026）接收。© 2026 IEEE。允许个人使用本材料。如需用于其他任何当前或未来媒体，包括广告或促销目的的再版/转载、创建新的集体作品、转售或分发到服务器或列表，或重用本作品中任何受版权保护的部分，必须获得IEEE许可。

###### 摘要

序列滤波流水线是大规模系统中的常见设计模式，其中大量的候选条目通过一系列阶段逐步减少，每个阶段都会产生成本。尽管这种模式在排序系统、级联机器学习推理和欺诈检测中普遍存在，但滤波器的排序通常由启发式方法决定，缺乏正式保证。我们在期望成本目标下对序列滤波进行了形式化，并证明在独立模型下，按成本与拒绝概率之比的升序排列滤波器可以最小化期望总成本。大量的蒙特卡罗模拟表明，在期望值和全分布结果上，最优排序在所有运行中均严格优于常见的启发式排序。

## I 引言

大规模系统经常通过一系列成本逐渐增加的测试来处理庞大的候选集。例子包括搜索和推荐系统中的多阶段排序流水线、机器学习中的级联推理架构，以及垃圾邮件和欺诈防御中的检测流水线。

一个核心的系统问题是，如何对这些阶段进行排序，以在保持所需精度或召回率的同时最小化总体成本。在实践中，流水线阶段通常使用简单的启发式方法进行排序，例如将最便宜的滤波器放在前面，或者将选择性最强的滤波器放在前面。这些启发式方法虽然直观，但由于忽略了成本与选择性之间的交互，可能系统性地次优。

考虑一个流水线，其中高度选择性但昂贵的滤波器被较早应用：虽然它拒绝了大量条目，但在全部候选集上产生的成本可能主导总计算量。相反，将便宜但弱的滤波器放在前面可能无法充分减少候选规模，从而放大下游成本。这些权衡表明需要一种原则性的排序准则。

在本工作中，我们在一个常用的独立假设模型下研究了序列滤波问题，并推导出一个简单的全局最优排序规则。我们进一步通过实证表明，该排序不仅最小化期望成本，而且在完整的结果分布上主导了常见的启发式排序。

### I-A 贡献

- • 我们形式化了序列滤波流水线的期望成本模型。
- • 我们使用成对交换论证证明了一个简单且全局最优的排序规则。
- • 我们通过大规模蒙特卡罗模拟实证验证了该理论。
- • 我们使用经验CDF和主导性散点图展示了分布上的主导性。

## II 问题定义

我们考虑一组滤波器 F = \{1, ..., n\}。每个滤波器 i 具有每项成本 c_i > 0 和通过概率 p_i ∈ [0, 1]。我们假设滤波器结果是独立的，成本是可加的，通过概率是固定的。

给定一个排序 π = (i_1, ..., i_n)，期望总成本为

E[C(π)] = ∑_{k=1}^n c_{i_k} ∏_{j=1}^{k-1} p_{i_j}, (1)

其中空乘积等于1。我们的目标是找到最小化 E[C(π)] 的排序 π*。

## III 最优排序

###### 定理1（最优序列滤波顺序）

在第二部分假设下，按 c_i / (1 - p_i) 的非递减值排列滤波器，可在所有排序中最小化期望总成本。

###### 证明

考虑两个相邻的滤波器 A 和 B，参数为 (c_A, p_A) 和 (c_B, p_B)。先 A 后 B 产生的期望成本为 c_A + p_A c_B，而先 B 后 A 产生的期望成本为 c_B + p_B c_A。当前者不差于后者当且仅当

c_A (1 - p_B) ≤ c_B (1 - p_A), (3)

这等价于 c_A/(1 - p_A) ≤ c_B/(1 - p_B)。任何违反该条件的排序都可以通过交换相邻滤波器进行局部改进。重复应用此类交换即可得到全局最优排序。∎

## IV 实验评估

### IV-A 设置

我们评估三种策略：(i) 成本排序，按成本递增排列滤波器；(ii) 通过率排序，按通过概率递增排列；(iii) 最优排序，按 c/(1-p) 递增排列。每个实验采样 n=50 个滤波器，成本从 {1,...,100} 均匀抽取，通过概率从 [0.4, 1.0] 均匀抽取。我们模拟一个包含 10^6 个项目的候选集，并重复实验 R=500 次独立运行。

### IV-B 汇总结果

在所有运行中，最优排序实现了最低的总成本。基于成本的排序始终是次优的，但相对稳定，而基于通过率的排序方差很大，偶尔出现极端成本。这些结果凸显了仅依赖选择性而不考虑成本的风险。

### IV-C 主导性散点图

主导性散点图提供了每个实例上的强保证：没有点落在对角线以下，表明在实验模型下，最优排序的成本从未高于基线。

### IV-D 经验CDF分析

经验CDF（ECDF）揭示了均值之外的分布行为。最优策略在每个成本阈值上为更大比例的运行实现了更低成本，而通过率启发式呈现出重尾分布。

参见标题图1：比较启发式策略与最优排序的主导性散点图。每个点对应一次运行。所有点位于对角线上或上方，表明在任何模拟中启发式策略均未优于最优排序。参见标题图2：跨运行总成本的经验CDF。最优排序在整个支撑集上主导基线，表明一阶随机占优。

## V 相关工作

我们的结果与基于比率的调度规则密切相关，最著名的是用于最小化单台机器上加权完成时间的史密斯规则[1 (https://arxiv.org/html/2606.07589#bib.bib1)]。经典调度考虑确定的作业完成，而我们的设置则对具有可加成本的随机淘汰进行建模。

序列拒绝流水线也出现在级联分类器中，例如用于目标检测的增强级联[3 (https://arxiv.org/html/2606.07589#bib.bib2)]，以及现代用于深度学习的早期退出或级联推理架构的级联推理系统[2 (https://arxiv.org/html/2606.07589#bib.bib4)]。阶段化测试的序列决策理论基础可以追溯到序列分析的经典工作[4 (https://arxiv.org/html/2606.07589#bib.bib3)]。

## VI 讨论与局限

最优性保证依赖于独立性和固定性假设。在实际系统中，滤波器可能是相关的、自适应的或状态依赖的。虽然我们的实证结果在假设模型下与理论一致，但将分析扩展到相关或自适应场景是未来工作的重要方向。

## VII 结论

我们提出了序列滤波流水线的形式化分析，并证明了在独立模型下的一个简单最优排序规则。大量模拟表明，最优排序在所有运行中以及成本的完整分布上严格优于常见的启发式排序。这些结果为设计高效的大规模滤波系统提供了理论指导和实践见解。

## 参考文献

- [1] (1956) 单阶段生产的各种优化器。《海军研究物流季刊》3(1–2)，第59–66页。引自：§V (https://arxiv.org/html/2606.07589#S5.p1.1).
- [2] S. Teerapittayanon, B. McDanel, and H. T. Kung (2016) BranchyNet: 通过深度神经网络早期退出实现快速推理。收录于《国际模式识别会议》。引自：§V (https://arxiv.org/html/2606.07589#S5.p2.1).
- [3] P. Viola and M. Jones (2001) 使用增强级联简单特征进行快速目标检测。收录于《IEEE计算机视觉与模式识别会议论文集》。引自：§V (https://arxiv.org/html/2606.07589#S5.p2.1).
- [4] A. Wald (1947) 序列分析。John Wiley and Sons。引自：§V (https://arxiv.org/html/2606.07589#S5.p2.1).