Asymptotic distribution-free changepoint detection for data with repeated observations¶

作者: Hoseung Song, Hao Chen
来源: Biometrika
主题: 数理统计 / 假设检验
相关性: 5/10
机构绿灯: University of California, Davis（US News 前 50，免分进入精读）
链接: https://doi.org/10.1093/biomet/asab048

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向关注的是非参数变点检测问题，特别是当数据是高维或非欧几里得（如网络、图、流形）时。传统参数方法（如似然比）在高维或非结构化数据上失效，而基于图的扫描统计量（graph-based scan statistics）提供了一种灵活的非参数替代方案：通过构造一个图（如最小生成树、k-近邻图）来编码观测间的相似性，然后基于图上的边计数（edge-count）来检测序列中是否存在分布变化的点。该框架的核心优势是无需对数据分布做参数假设，且能处理非向量数据。当前成熟度：方法框架已建立，但处理重复观测（repeated observations）——即序列中存在完全相同的观测值——是一个已知但尚未被系统解决的缺口。

发展脉络（history）¶

奠基工作：Friedman & Rafsky (1979) 首次提出用最小生成树（MST）上的边计数构造两样本检验，奠定了图基非参数检验的基础。留下的口子：该框架只处理两样本比较，未涉及序列变点检测。
主要进展（变点检测）：Chen & Zhang (2015, JRSS-B) 将图基两样本检验推广到变点检测，提出了基于扫描统计量的方法，并给出了控制第一类错误的解析近似公式。留下的口子：该方法假设序列中无重复观测，否则最优图不唯一，统计量定义失效。
当前 frontier：Chu & Chen (2019, Biometrika) 进一步考虑了变化区间（changed-interval）备择，并发展了相应的图基扫描统计量。留下的口子：同样未处理重复观测问题。此外，这些方法在离散数据（如网络节点序列）中频繁遇到重复观测，限制了其应用。
本文的位置：本文（Song & Chen, 2024, Biometrika）直接填补上述缺口，通过平均或取并集所有可能最优图的方式，将图基框架扩展到允许重复观测的序列，并推导了相应的第一类错误解析控制公式。

子线索聚类¶

这些被引文献大致落在两条子线索上： 1. 图基两样本检验：Friedman & Rafsky (1979) 开创，后续有 Rosenbaum (2005) 等。核心是构造一个图，然后基于图上的边计数（如跨组边数）构造检验统计量。瓶颈：仅适用于两样本比较，无法直接处理序列变点。 2. 图基变点检测：Chen & Zhang (2015), Chu & Chen (2019) 等。核心是将扫描统计量思想与图基边计数结合，通过滑动窗口计算局部统计量，并取最大值作为检验统计量。瓶颈：假设序列中无重复观测，否则最优图不唯一，统计量定义不明确。

这个方向在追问的核心问题¶

如何定义图基统计量当最优图不唯一时？ 这是本文直接回答的问题。
如何控制第一类错误？ 解析公式 vs. 重抽样。解析公式对大规模数据至关重要，但推导依赖于统计量的渐近分布。本文给出了解析公式。
检验功效如何？ 对于给定的备择（单变点 vs. 变化区间），图基方法的功效性质如何？本文通过模拟和真实数据展示了功效，但未给出理论功效界。
如何选择图？ 不同图（MST, k-近邻, 最小距离图）对检验功效的影响。本文在重复观测设定下，图的选择问题变得更加复杂。

⚠️ 作者的 framing¶

作者的缺口 frame：作者将缺口 frame 成“图基变点检测框架在处理重复观测时失效，因为最优图不唯一”，并声称这是“一个重要的实际限制，特别是在离散数据（如网络数据）中”。因此，本文的贡献是“扩展该框架以处理重复观测”，并“推导解析公式以控制第一类错误”。
被淡化或回避的竞争路线：作者在引言中提到了“基于核的方法”（如 Gretton et al., 2012）和“基于距离的方法”（如 Matteson & James, 2014），但仅用一句话带过，称它们“在高维或非欧几里得数据上计算成本高”。作者没有深入比较图基方法与这些方法在重复观测设定下的优劣，也没有讨论这些方法是否天然能处理重复观测（例如，核方法中重复观测的核矩阵是奇异的，这本身也是一个问题）。
什么明显该被引 / 该存在、却没出现在 intro 里？ 作者没有引用关于离散数据变点检测的专门文献，例如针对网络序列（network time series）的变点检测方法（如 spectral methods, community detection based methods）。这些方法可能更直接地处理网络数据，而本文的方法是将网络数据视为“带有重复观测的序列”来处理。这是一个值得研究者去查的问题：是否存在更专门的网络变点检测方法，以及本文的方法与它们相比有何优劣？

张力¶

未见明显对立引用。所有被引工作都沿着图基框架的同一方向推进，没有出现彼此矛盾或在略不同条件下得相反结论的情况。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号：
\(X_1, X_2, \dots, X_n\)：观测到的数据序列，每个 \(X_i\) 可以是一个向量、一个图、一个字符串等，位于某个空间 \(\mathcal{X}\) 中。
\(n\)：序列长度（样本量）。
\(G\)：一个图，其顶点集为 \(\{1, 2, \dots, n\}\)，边集 \(E(G)\) 表示观测间的相似性。图的构造基于观测值 \(X_i\) 之间的距离或相似度（如欧氏距离、图编辑距离等）。
\(e_{ij}\)：图 \(G\) 中连接顶点 \(i\) 和 \(j\) 的边（如果存在）。
\(R_{ij}\)：指示变量，\(R_{ij} = 1\) 如果 \(X_i = X_j\)（即重复观测），否则 \(R_{ij} = 0\)。
\(\tau\)：变点位置（未知），在单变点备择下，序列在 \(\tau\) 处发生分布变化。
\(S(\tau)\)：扫描统计量，基于图 \(G\) 上的边计数构造，用于检验是否存在变点 \(\tau\)。
\(T_n\)：全局检验统计量，通常取所有可能变点位置 \(\tau\) 上扫描统计量的最大值，即 \(T_n = \max_{\tau} S(\tau)\)。
\(\alpha\)：显著性水平（第一类错误率）。
模型：
原假设 \(H_0\)：所有 \(X_i\) 独立同分布（i.i.d.）于某个未知分布 \(F\)。
备择假设 \(H_1\)：存在一个变点 \(\tau\)（或一个变化区间 \([a, b]\)），使得变点前后的分布不同。即 \(X_1, \dots, X_\tau \sim F\)，而 \(X_{\tau+1}, \dots, X_n \sim G\)，且 \(F \neq G\)。
图构造模型：给定观测值 \(X_1, \dots, X_n\)，构造一个图 \(G\)。常用的图包括：
- 最小生成树（MST）：连接所有 \(n\) 个顶点的树，使得所有边的权重（距离）之和最小。
- k-近邻图（k-NN）：每个顶点与其最近的 \(k\) 个顶点相连。
- 最小距离图（MDD）：连接所有距离小于某个阈值的顶点对。
关键假设：在无重复观测时，MST 是唯一的（几乎必然）。当存在重复观测时，MST 不唯一，因为距离为 0 的边可以任意选择。
可观测数据：
研究者实际能观测到的是：序列 \(X_1, \dots, X_n\)，以及基于这些观测值构造的图 \(G\)（但图可能不唯一）。
想要但观测不到的是：变点位置 \(\tau\) 的真实值，以及变点前后的分布 \(F\) 和 \(G\)。这些是推断的目标。

第二步：讲最小内核¶

最简特例：假设序列长度 \(n=4\)，观测值为 \(X_1, X_2, X_3, X_4\)，且 \(X_1 = X_2 = X_3 = a\)（重复观测），\(X_4 = b\)（唯一观测），其中 \(a \neq b\)。我们想检验是否存在一个变点（例如，在位置 3 之后，分布从 \(a\) 变为 \(b\)）。

传统图基方法（无重复观测）：如果所有观测都不同，我们可以构造一个唯一的 MST。例如，如果 \(a\) 和 \(b\) 是实数，且 \(a < b\)，那么 MST 会连接所有 \(a\) 的观测（距离为 0）和 \(b\) 的观测，但 \(a\) 和 \(b\) 之间的边只有一条。然后，扫描统计量 \(S(\tau)\) 会计算在变点 \(\tau\) 处，跨越变点的边数。如果变点存在，跨越变点的边数会显著少于期望值。

重复观测带来的问题：当 \(X_1 = X_2 = X_3 = a\) 时，这三个观测点之间的距离为 0。在构造 MST 时，连接这三个点的边可以任意选择（例如，连接 1-2 和 2-3，或者 1-3 和 2-3，等等）。因此，MST 不唯一。不同的 MST 会导致不同的边计数，从而使得扫描统计量的定义不明确。

本文的核心思路：既然最优图不唯一，我们就考虑所有可能的最优图。具体有两种方式： 1. 平均（Average）：对于每个可能的变点位置 \(\tau\)，计算在所有可能的最优图 \(G\) 上，扫描统计量 \(S_G(\tau)\) 的平均值，记为 \(\bar{S}(\tau)\)。然后取 \(\bar{T}_n = \max_{\tau} \bar{S}(\tau)\) 作为检验统计量。 2. 并集（Union）：构造一个“并图” \(G_{\text{union}}\)，其边集是所有可能最优图的边的并集。然后在这个并图上计算扫描统计量 \(S_{\text{union}}(\tau)\)，并取 \(T_{\text{union}} = \max_{\tau} S_{\text{union}}(\tau)\) 作为检验统计量。

在这个最简特例下： - 平均方法：所有可能的 MST 都是连接 \(\{1,2,3\}\) 的树（有 3 种可能），再加上连接其中一个 \(a\) 到 \(b\) 的边。对于变点 \(\tau=3\)，跨越变点的边是连接 \(\{1,2,3\}\) 和 \(\{4\}\) 的边。在所有可能的 MST 中，这条边总是存在（因为 \(a \neq b\)），所以平均跨越边数为 1。对于变点 \(\tau=1\) 或 \(\tau=2\)，跨越变点的边数也是 1。因此，\(\bar{T}_n = 1\)。在原假设下（所有观测 i.i.d.），跨越变点的期望边数可以通过解析公式计算，从而控制第一类错误。 - 并集方法：并图 \(G_{\text{union}}\) 包含所有可能的 MST 的边。在这个特例中，并图会包含 \(\{1,2,3\}\) 之间的所有 3 条边（形成一个完全图），以及连接其中一个 \(a\) 到 \(b\) 的边。然后，扫描统计量 \(S_{\text{union}}(\tau)\) 会计算在并图上跨越变点的边数。对于 \(\tau=3\)，跨越变点的边是连接 \(\{1,2,3\}\) 和 \(\{4\}\) 的边，只有 1 条。因此，\(T_{\text{union}} = 1\)。

核心数学困难：推导这些新统计量（平均或并集）在原假设下的渐近分布，并得到控制第一类错误的解析公式。这需要处理图的不确定性带来的组合复杂性。作者通过将问题转化为对边计数的期望和方差的计算，并利用图论和组合数学的技巧，得到了封闭形式的解析公式。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：针对高维或非欧几里得数据序列中，当存在重复观测时，图基变点检测方法失效的问题，提出了两种扩展方法（平均法和并集法）。
核心工具 / 方法：通过平均或取并集所有可能的最优图（如最小生成树），构造新的扫描统计量，并推导了控制第一类错误的解析公式。
主要结论：提出的方法在模拟和真实数据（动态网络序列）上表现良好，能够有效控制第一类错误，并具有与无重复观测时相当的检验功效。所有方法已实现为 R 包 gSeg。

关键设定与假设¶

设定：序列 \(X_1, \dots, X_n\)，每个 \(X_i \in \mathcal{X}\)。构造一个图 \(G\) 来编码观测间的相似性。考虑两种备择：单变点备择（序列在某个未知点 \(\tau\) 处分布发生变化）和变化区间备择（序列在一个未知区间 \([a, b]\) 内分布发生变化）。
假设：
独立性：观测值 \(X_i\) 在原假设下独立同分布。这是一个标准假设，但在时间序列数据中可能不成立。作者在模拟中考虑了弱相依性，但理论结果基于独立性。
图构造：图 \(G\) 是基于观测值之间的距离构造的，且距离函数是给定的。作者主要考虑最小生成树（MST），但方法可推广到其他图。
重复观测：重复观测是指 \(X_i = X_j\) 对于某些 \(i \neq j\)。作者假设重复观测的概率非零，且重复观测的集合可以很大。
相比已有文献：相比 Chen & Zhang (2015) 和 Chu & Chen (2019)，本文放宽了“无重复观测”的假设，这是核心贡献。其他假设（独立性、图构造方式）与已有文献一致。

主要结果¶

定理 1（单变点备择，平均法）：给出了在原假设下，平均扫描统计量 \(\bar{S}(\tau)\) 的期望和方差的解析公式。这些公式依赖于图的结构（如边数、顶点度数）和重复观测的模式（如重复观测的组大小）。基于这些公式，可以构造标准化统计量 \(Z(\tau) = (\bar{S}(\tau) - E[\bar{S}(\tau)]) / \sqrt{\text{Var}[\bar{S}(\tau)]}\)，并证明其渐近服从标准正态分布（在适当的条件下）。然后，全局检验统计量 \(\bar{T}_n = \max_{\tau} Z(\tau)\) 的渐近分布可以通过极值理论近似。
定理 2（单变点备择，并集法）：类似地，给出了并图扫描统计量 \(S_{\text{union}}(\tau)\) 的期望和方差的解析公式。
定理 3（变化区间备择）：将上述结果推广到变化区间备择，给出了相应的解析公式。
核心量化结论：解析公式使得方法无需重抽样（如置换检验或 bootstrap），计算复杂度为 \(O(n^2)\) 或 \(O(n \log n)\)（取决于图构造），适用于大规模数据。模拟结果显示，在重复观测比例较高时，平均法和并集法都能有效控制第一类错误，而忽略重复观测的原始方法则严重膨胀。在功效方面，平均法和并集法略低于无重复观测时的最优方法，但差距不大。

证明路线与技术技巧¶

整体路线：
定义统计量：首先，明确在重复观测下，所有可能的最优图构成的集合 \(\mathcal{G}\)。然后，定义平均统计量 \(\bar{S}(\tau) = \frac{1}{|\mathcal{G}|} \sum_{G \in \mathcal{G}} S_G(\tau)\) 和并图统计量 \(S_{\text{union}}(\tau)\)。
计算期望和方差：在原假设下，计算 \(\bar{S}(\tau)\) 和 \(S_{\text{union}}(\tau)\) 的期望和方差。这需要将统计量表示为图上的边计数之和，然后利用图论和组合数学计算这些和的期望和方差。关键技巧是将期望和方差分解为关于顶点对（pair）的项，然后利用重复观测的对称性简化计算。
渐近正态性：证明标准化后的统计量 \(Z(\tau)\) 渐近服从标准正态分布。这通常依赖于经验过程理论或鞅差序列的中心极限定理。作者采用了后一种思路，将扫描统计量视为一个鞅差序列的和。
极值理论：证明全局统计量 \(\bar{T}_n = \max_{\tau} Z(\tau)\) 的渐近分布服从 Gumbel 分布（或类似极值分布）。这需要处理扫描统计量之间的相关性，并利用极值理论中的经典结果（如 Leadbetter et al., 1983）。
关键跳跃点：
处理图的不确定性：最吃功夫的部分是计算 \(\bar{S}(\tau)\) 的方差。因为 \(\bar{S}(\tau)\) 是多个不同图上的统计量的平均，这些统计量之间是相关的。作者通过将方差分解为“同一图内”和“不同图之间”的协方差，并利用图论中的边计数矩阵来系统计算这些协方差，从而得到了封闭形式的解析公式。
并图统计量的方差计算：并图统计量 \(S_{\text{union}}(\tau)\) 的方差计算同样复杂，因为并图的边集是多个图的并集，其结构依赖于重复观测的模式。作者通过将并图视为一个“完全图”的子图，并利用包含-排除原理来计算边计数的期望和方差。
技术技巧点名：
图论：用于描述图的结构（边数、度数、路径等）。
组合数学：用于计算所有可能最优图的个数，以及在这些图上边计数的期望和方差。
鞅差序列的中心极限定理：用于证明扫描统计量的渐近正态性。
极值理论：用于近似全局统计量的渐近分布。

真实例子与应用¶

用的什么数据 / 场景：作者使用了动态网络序列数据。具体来说，他们模拟了一个随时间变化的网络序列，其中每个时间点的网络是一个随机图（如 Erdős–Rényi 图或随机块模型）。在某个时间点，网络的生成机制发生变化（如边概率改变或社区结构改变）。这些网络数据是离散的，因此存在大量重复观测（例如，两个时间点的网络可能完全相同）。
怎么把本文方法用上去：作者将每个时间点的网络表示为一个邻接矩阵，然后计算不同时间点网络之间的距离（如 Frobenius 范数或图编辑距离）。基于这些距离，构造 MST。由于存在重复观测（相同网络），MST 不唯一。作者应用本文提出的平均法和并集法进行变点检测。
得到什么结果：模拟结果显示，在动态网络序列中，本文的方法能够准确检测到变点，且第一类错误控制良好。与忽略重复观测的原始方法相比，本文的方法在重复观测比例较高时具有显著优势。
这个例子想说明什么：这个例子旨在展示本文方法在离散数据（如网络数据）上的实际应用价值，验证了理论结果，并说明了处理重复观测的必要性。

🔎 结论是否比证明窄¶

窄结论：作者在定理中假设了独立性，但在真实数据例子中，动态网络序列可能存在时间相依性。作者在模拟中考虑了弱相依性（如 AR(1) 过程），但未在理论上证明方法在相依数据下的有效性。因此，结论（方法适用于动态网络序列）可能比证明（基于独立性假设）更宽泛。作者在讨论部分提到了这一点，称“将方法扩展到相依数据是未来的工作”。
泛泛 claim：作者声称方法“适用于大规模数据”，但解析公式的计算复杂度为 \(O(n^2)\)（对于每个变点位置 \(\tau\) 都需要计算统计量），对于极长的序列（如 \(n > 10^5\)）可能仍然昂贵。作者没有讨论计算瓶颈或给出大规模数据下的计算时间。

四、开放问题¶

相依数据下的理论性质：本文的理论结果基于独立性假设。将方法扩展到时间序列数据（如 ARMA、GARCH）或空间数据，并推导相应的渐近分布，是一个自然且重要的开放问题。扎根点：作者在讨论部分提到“将方法扩展到相依数据是未来的工作”。
最优图的选择：本文主要考虑 MST。对于其他图（如 k-近邻图、最小距离图），在重复观测设定下，如何定义“所有可能的最优图”以及如何计算相应的解析公式？扎根点：作者在引言中提到“本文的方法可推广到其他图”，但未给出具体细节。
检验功效的理论界：本文通过模拟展示了检验功效，但未给出理论上的功效界（如 minimax 最优性）。对于给定的备择（如变点大小、位置），本文的方法是否达到最优？扎根点：作者在结论部分提到“功效性质值得进一步研究”。
高维数据下的计算效率：当数据维度极高时，距离计算和图构造的计算成本可能成为瓶颈。如何设计更高效的算法（如基于随机投影或近似最近邻）来加速图构造，同时保持统计性质？扎根点：作者在讨论部分提到“计算效率是实际应用中的一个考虑”。

Maintained by 陈星宇 · Homepage · Source on GitHub