Inferring Change Points in High-Dimensional Regression via Approximate Message Passing

📄 arXiv: 2404.07864v3 📥 PDF

作者: Gabriel Arpino, Xiaoqi Liu, Julia Gontarek, Ramji Venkataramanan

分类: stat.ML, cs.LG, math.ST

发布日期: 2024-04-11 (更新: 2025-09-05)

备注: 49 pages, 9 figures. To appear in the Journal of Machine Learning Research

💡 一句话要点

提出近似消息传递算法以定位高维回归中的变更点

🎯 匹配领域: 支柱八：物理动画 (Physics-based Animation)

关键词: 变更点检测 广义线性模型 近似消息传递 高维回归 贝叶斯推断 状态演化递归 信号估计

📋 核心要点

  1. 现有方法在高维回归中定位变更点时，计算复杂度高且难以处理信号的结构信息。
  2. 本文提出的近似消息传递算法能够高效估计信号和变更点位置，适应高维数据的特点。
  3. 实验结果表明，所提算法在合成和真实数据上均表现优越，尤其在不同回归模型中具有良好的适应性。

📝 摘要（中文）

本文考虑在广义线性模型（GLM）中定位变更点的问题，该模型涵盖了统计学习中许多广泛研究的问题，包括线性回归、逻辑回归和修正线性回归。我们提出了一种新颖且计算效率高的近似消息传递（AMP）算法，用于估计信号和变更点位置，并在高维极限下严格表征其性能。该表征通过状态演化递归实现，使我们能够精确计算变更点估计的渐近Hausdorff误差，并根据信号和变更点的先验结构信息调整算法。此外，我们展示了AMP迭代如何有效计算高维极限下变更点位置的贝叶斯后验分布。通过数值实验验证了我们的理论，并在合成和真实数据上展示了我们估计器在不同回归设置中的良好表现。

🔬 方法详解

问题定义：本文旨在解决在广义线性模型中定位变更点的问题。现有方法在高维情况下往往面临计算复杂度高和难以利用信号结构信息的挑战。

核心思路：我们提出的近似消息传递（AMP）算法通过状态演化递归来表征算法性能，能够在高维极限下有效估计信号和变更点位置。该设计使得算法能够灵活地利用先验信息。

技术框架：整体架构包括信号估计和变更点定位两个主要模块。首先，通过AMP迭代更新信号估计；其次，利用状态演化递归计算变更点位置的后验分布。

关键创新：本研究的主要创新在于引入状态演化递归来精确计算变更点估计的渐近Hausdorff误差，并能够根据先验信息调整算法。这与传统方法的固定结构设计形成鲜明对比。

关键设计：在算法设计中，我们设置了适应高维数据的参数，并采用了适当的损失函数来优化信号和变更点的估计，确保算法在不同回归模型下的有效性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，所提AMP算法在合成数据上相较于传统方法提高了变更点估计的准确性，Hausdorff误差显著降低，且在真实数据集上也展现出优越的性能，验证了理论的有效性。

🎯 应用场景

该研究的潜在应用领域包括金融市场分析、医疗监测和工业过程控制等。在这些领域中，准确定位变更点对于及时决策和风险管理至关重要。未来，该算法有望在更广泛的高维数据分析中发挥重要作用。

📄 摘要（原文）

We consider the problem of localizing change points in a generalized linear model (GLM), a model that covers many widely studied problems in statistical learning including linear, logistic, and rectified linear regression. We propose a novel and computationally efficient Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations, and rigorously characterize its performance in the high-dimensional limit where the number of parameters $p$ is proportional to the number of samples $n$. This characterization is in terms of a state evolution recursion, which allows us to precisely compute performance measures such as the asymptotic Hausdorff error of our change point estimates, and allows us to tailor the algorithm to take advantage of any prior structural information on the signals and change points. Moreover, we show how our AMP iterates can be used to efficiently compute a Bayesian posterior distribution over the change point locations in the high-dimensional limit. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic and real data in the settings of linear, logistic, and rectified linear regression.