技术摘要：无分布根因分析（CROC）

1. 问题表述

本文解决了多流数据中的根因分析问题。在该设定下，一个底层系统通过 $K$ 个独立的数据流进行监控，每个数据流可能在未知的时间点发生分布变化。目标是识别根因索引 $k^\star$，定义为分布最早发生变化的数据流（即 $k^\star = \arg\min_{k \in [K]} \xi_k$，其中 $\xi_k$ 是第 $k$ 个数据流的变化点时间）。

该框架基于最小假设运行：

1. 独立性：数据流之间相互独立。
2. 可交换性：在每个数据流内部，变化前和变化后的观测值是从任意未知的分布中可交换地采样的。
3. 约束集：变化点配置 $\xi$ 属于已知的约束集 $\mathcal{R} \subseteq [n]^K$（例如，允许任意配置或强制同步）。

挑战在于在不依赖参数模型（如高斯偏移）或对数据生成过程做出强结构假设的情况下实现有限样本有效性，而这些假设在实践中往往不可靠。

2. 方法论：共形根因分析（CROC）

作者提出了共形根因分析（CROC），这是一个利用共形 p 值为根因索引构建有效置信集框架。该方法将单流共形变化点定位（CONCH）框架扩展到了多流设定。

核心组件

1. 假设检验对应：
   为 $k^\star$ 构建置信集的问题被表述为对每个候选数据流 $k$ 检验零假设 $H_{0,k}$。$H_{0,k}$ 假设数据流 $k$ 是根因，这意味着真实的变化点配置 $\xi$ 位于集合 $\mathcal{I}_k = \{t \in \mathcal{R} : t_k < t_j, \forall j \neq k\}$ 中。

2. 变化点合理性（CPP）评分：
   定义评分函数 $S(\mathbf{X}, t)$ 以量化特定变化点配置 $t$ 为真实配置的可能性。该评分的设计使得较大的值表示对 $t$ 有更强的证据支持。

3. 分割置换群：
   对于候选配置 $t$，构建一个置换群 $\Pi_t$。$\Pi_t$ 中的元素在每个数据流的变化前和变化后片段内部独立地置换观测值，但不混合这些片段之间的观测值。在 $t$ 是真实变化点的零假设下，数据的联合分布在 $\Pi_t$ 的置换下是不变的。

4. 共形 p 值：
   对于每个候选 $t$，通过比较观测评分 $S(\mathbf{X}, t)$ 与通过对数据进行置换获得的评分来计算 p 值 $p_t$：
   $$p_t = \frac{1}{|\Pi_t|} \sum_{\pi \in \Pi_t} \mathbb{1}\{S(\pi(\mathbf{X}), t) \leq S(\mathbf{X}, t)\}$$
   为了处理计算复杂性，使用了蒙特卡洛近似。

5. 聚合：
   为了检验 $H_{0,k}$，使用最大算子聚合 $\mathcal{I}_k$ 中所有配置的 p 值：$p^{(k)} = \max_{t \in \mathcal{I}_k} p_t$。最终的置信集定义为：
   $$K_{1-\alpha}^{\text{CROC}} = \{k \in [K] : p^{(k)} > \alpha\}$$

处理依赖性

虽然主要框架假设数据流独立，但本文将 CROC 扩展到了跨流依赖性（算法 2，CROC-dep）。如果数据流可以被划分为相互独立的数据流组，该方法计算组级 p 值并通过邦费罗尼（Bonferroni）校正进行聚合，在保持有效性的同时，相比朴素聚合提高了效率。

3. 主要贡献

本文确立了四项主要的理论和实践贡献：

1. 有限样本有效性：
   定理 3.1 证明了 $K_{1-\alpha}^{\text{CROC}}$ 是一个有效的无分布置信集。对于任何 $\alpha \in (0,1)$，只要可交换性和独立性假设成立，该集合包含真实根因索引 $k^\star$ 的概率至少为 $1-\alpha$。这对任何CPP 评分的选择都成立。

2. 普适性属性：
   定理 4.1 表明 CROC 是一个通用框架。任何用于根因分析的无分布过程都可以表示为具有适当选择的 CPP 评分的 CROC 特定实例。这意味着 CROC 涵盖了整个无分布方法类。

3. 最优评分设计与渐近锐度：
   本文在独立同分布（i.i.d.）变化点模型下刻画了最优 CPP 评分（定理 5.2）。最优评分是似然比（LLR）的对数变换，用于比较在假设的变化点配置下与在真实配置下数据的似然度。

   • 实际实现：由于真实分布未知，作者提出了数据驱动的近似方法（例如，使用学习到的密度或分类器）。
   • 渐近锐度：定理 5.3 表明，在温和的正则条件下（变化点分离、分布可区分），使用 oracle LLR 评分构建的置信集变得渐近锐利，以概率趋近于 $1-\alpha$ 隔离出真实根因。

4. 向依赖性的扩展：
   本文提供了一种原则性的扩展（CROC-dep）来处理结构化的跨流依赖性，在邦费罗尼校正的保守性与利用已知独立结构带来的效率之间提供了权衡。

4. 实验结果

作者通过广泛的模拟验证了 CROC：

• 高斯均值偏移：在信号强度变化的设定中，CROC 成功隔离了根数据流。即使根数据流的信号弱于后续变化（这是一个具有挑战性的区域），该方法仍保持有效的覆盖率，并在必要时自适应地加宽置信集。
• 图像损坏（MNIST）：应用于图像发生模糊的高维设定。尽管损坏信号细微且使用了预训练的 CNN 进行评分，CROC 仍正确识别了根数据流，证明了其在弱信号、高维场景下的鲁棒性。
• 多领域情感分析：使用跨四个领域的情感分析数据集，CROC 成功识别了情感变化首先发生的领域，表现优于朴素的点估计方法。
• 依赖性处理：基线 CONCH-agg（朴素聚合）与 CROC-dep 的比较表明，利用已知的独立结构可以产生显著更锐利的置信集，同时保持有效性。

5. 意义与主张

本文主张 CROC 为根因分析提供了一种严谨的、无分布的解决方案，解决了现有文献中方法通常依赖参数假设或缺乏有限样本保证的空白。

• 鲁棒性：通过仅要求可交换性和独立性，该方法适用于多种数据类型（图像、文本、传感器数据），而无需指定底层分布。
• 理论完备性：普适性结果确立了 CROC 作为此类问题类的规范框架。
• 实用效用：构建渐近锐利的有效置信集的能力，使从业者不仅能够识别根因，还能量化识别的不确定性，即使在复杂、高维或弱信号环境中也是如此。

作者总结道，虽然该框架扩展到了依赖数据流，但未来的工作需要在结构化依赖性下提高效率，并处理流内依赖性。