arXiv:2501.18059cs.LGcs.AI2025-01ICLR被引 4

用数据学习最优提前分类停止点,提升时序预测效率与可靠性。

Learning the Optimal Stopping for Early Classification within Finite Horizons via Sequential Probability Ratio Test

  • 基于SPRT框架,用密度比估计和凸函数学习替代传统反向归纳。
  • 在多种数据上实现贝叶斯风险最优,决策时间方差显著降低。
  • 适合需要快速、稳定决策的实时时序应用,如医疗监测与金融风控。

时序敏感的机器学习可受益于序贯概率比检验(SPRT),其能提供时序数据早期分类的最优停止时间。然而,在输入长度有限的有限时域场景中,由于需进行反向归纳,确定最优停止规则计算开销大,限制了实际应用。为此,本文提出FIRMBOUND——一种基于SPRT的高效框架,通过训练数据估算反向归纳解,弥合最优停止理论与真实部署间的差距。该方法采用密度比估计与凸函数学习,构建充分统计量与条件期望的统计相容估计器,从而最小化贝叶斯风险以实现最优性。此外,还提出一种基于高斯过程回归的加速版本,大幅减少训练时间,仅略有统计一致性损失。在独立同分布(i.i.d.)、非i.i.d.、二分类、多分类、合成及真实数据集上的实验表明,FIRMBOUND在贝叶斯风险与速度-准确率权衡上均达最优,并进一步逼近最优边界,同时降低决策时间方差,保障决策可靠性。代码已公开于https://github.com/Akinori-F-Ebihara/FIRMBOUND。

原文摘要 · Abstract (English)

Time-sensitive machine learning benefits from Sequential Probability Ratio Test (SPRT), which provides an optimal stopping time for early classification of time series. However, in finite horizon scenarios, where input lengths are finite, determining the optimal stopping rule becomes computationally intensive due to the need for backward induction, limiting practical applicability. We thus introduce FIRMBOUND, an SPRT-based framework that efficiently estimates the solution to backward induction from training data, bridging the gap between optimal stopping theory and real-world deployment. It employs density ratio estimation and convex function learning to provide statistically consistent estimators for sufficient statistic and conditional expectation, both essential for solving backward induction; consequently, FIRMBOUND minimizes Bayes risk to reach optimality. Additionally, we present a faster alternative using Gaussian process regression, which significantly reduces training time while retaining low deployment overhead, albeit with potential compromise in statistical consistency. Experiments across independent and identically distributed (i.i.d.), non-i.i.d., binary, multiclass, synthetic, and real-world datasets show that FIRMBOUND achieves optimalities in the sense of Bayes risk and speed-accuracy tradeoff. Furthermore, it advances the tradeoff boundary toward optimality when possible and reduces decision-time variance, ensuring reliable decision-making. Code is publicly available at https://github.com/Akinori-F-Ebihara/FIRMBOUND

时序分类最优停止SPRT实时决策

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。