用随机傅里叶特征实现多变量数据流的高效在线变点检测
Optimal Online Change Detection via Random Fourier Features
- 基于核方法与随机傅里叶特征设计逐点检验流程
- 每步计算仅需对数时间，整体空间复杂度也为对数级
- 无需预训练数据或窗口参数，适合实时监控场景
本文研究多变量数据流中的在线非参数变点检测问题。通过核方法的两样本检验视角，提出一种基于随机傅里叶特征的序列检验算法，每观测值处理时间复杂度为对数级，总体空间复杂度也为对数级。相比现有方法，该算法具有两大优势：一是真正在线，无需预先已知变化前分布的训练数据；二是无需人工指定局部检验的窗口参数。理论证明显示，算法在信息论意义上实现了最小最大检测延迟的最优性。真实与合成数据上的数值实验表明，该算法性能可媲美当前最优方法。
原文摘要 · Abstract (English)
This article studies the problem of online non-parametric change point detection in multivariate data streams. We approach the problem through the lens of kernel-based two-sample testing and introduce a sequential testing procedure based on random Fourier features, running with logarithmic time complexity per observation and with overall logarithmic space complexity. The algorithm has two advantages compared to the state of the art. First, our approach is genuinely online, and no access to training data known to be from the pre-change distribution is necessary. Second, the algorithm does not require the user to specify a window parameter over which local tests are to be calculated. We prove strong theoretical guarantees on the algorithm's performance, including information-theoretic bounds demonstrating that the detection delay is optimal in the minimax sense. Numerical studies on real and synthetic data show that our algorithm is competitive with respect to the state of the art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。