We develop an online kernel Cumulative Sum (CUSUM) procedure, which consists of a parallel set of kernel statistics with different window sizes to account for the unknown change-point location. Compared with many existing sliding window-based kernel change-point detection procedures, which correspond to the Shewhart chart-type procedure, the proposed procedure is more sensitive to small changes. We further present a recursive computation of detection statistics, which is crucial for online procedures to achieve a constant computational and memory complexity, such that we do not need to calculate and remember the entire Gram matrix, which can be a computational bottleneck otherwise. We obtain precise analytic approximations of the two fundamental performance metrics, the Average Run Length (ARL) and Expected Detection Delay (EDD). Furthermore, we establish the optimal window size on the order of $\log ({\rm ARL})$ such that there is nearly no power loss compared with an oracle procedure, which is analogous to the classic result for window-limited Generalized Likelihood Ratio (GLR) procedure. We present extensive numerical experiments to validate our theoretical results and the competitive performance of the proposed method.
翻译:我们开发了一个在线内核累积总和(CUSUM)程序,该程序由一系列不同窗口大小的平行内核统计组成,以说明未知的变更点位置。与许多现有的基于滑动窗口的内核变化点检测程序相比,与Shewrt图表型程序相对应,拟议程序对小幅变化更为敏感。我们进一步提出了探测统计数据的循环计算方法,这对在线程序实现一个不变的计算和记忆复杂性至关重要,因此我们不需要计算和记住整个Gram矩阵,否则,该矩阵可以是计算瓶颈。我们获得了两种基本性能衡量标准,即平均运行长度和预期探测延迟(EDD)的精确分析近似值。此外,我们按照$(rm ARL})的顺序确定了最佳窗口大小,这样,与一个或骨架程序相比,几乎没有断电损失,这类似于窗口有限一般相似的相似的通用相似的结果。我们进行了广泛的数字实验,以验证我们的理论结果和拟议方法的竞争性表现。