Graphical modeling of stochastic processes driven by correlated noise¶

作者: Søren Wengel Mogensen, Niels Richard Hansen
来源: Bernoulli
主题: 因果推断
相关性: 4/10
机构绿灯: University of Copenhagen（US News 前 50，免分进入精读）
链接: https://doi.org/10.3150/21-bej1446

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向研究的是随机过程中局部独立性（local independence）的图模型表示。核心问题是：给定一个多变量随机过程（如时间序列），如何用一个有向图来编码“一个分量的未来是否在概率上独立于另一个分量的过去，给定所有其他分量的历史”？这种图称为局部独立性图。该方向当前处于理论成熟但计算可行性边界尚未完全厘清的阶段：图模型的等价类（多个图编码相同独立性）已被刻画，但最坏情况下的复杂度（coNP-complete）表明，任何“简洁”的等价类特征描述在计算上都是不可能的。

发展脉络（history）¶

奠基工作：Schweder (1970) 与 Didelez (2000, 2008)。Schweder 首次提出“局部独立性”概念，用于点过程。Didelez (2000, 2008) 将其系统化为图模型框架，定义了局部独立性图（local independence graph, LIG），并给出了基本性质。留下的口子：Didelez 的框架假设误差过程是独立的（即驱动过程的噪声是独立的），这在许多应用中（如神经科学、金融）不现实。
主要进展：Eichler (2012, 2013)。Eichler 将局部独立性图推广到更一般的随机过程（包括连续时间过程），并建立了与 Granger 因果性的联系。留下的口子：Eichler 的工作仍主要处理独立误差，且对等价类的刻画不完整——多个图可能编码相同的局部独立性，但如何系统地表征这些等价类未被解决。
当前 frontier：Mogensen & Hansen (2020, 2022)。作者在本文之前的工作（Mogensen & Hansen, 2020）研究了局部独立性图的马尔可夫等价类，但仅限于无相关误差的情形。留下的口子：当误差过程之间存在相关性时，等价类结构会如何变化？这是本文要填补的缺口。
本文的位置：本文是上述工作的直接扩展——将局部独立性图的等价类理论从独立误差推广到相关误差过程。作者证明，即使允许误差相关，等价类的特征描述在结构上类似于独立误差情形，但最坏情况下的复杂度（coNP-complete）表明，任何“多项式大小”的特征条件集合都不可能存在。

子线索聚类¶

这些被引文献大致落在两条子线索上： 1. 局部独立性图的理论基础（Schweder, Didelez, Eichler）：定义、基本性质、与 Granger 因果性的联系。这一簇主要处理独立误差。 2. 图模型的马尔可夫等价类（Verma & Pearl, 1990; Chickering, 2002; Andersson et al., 1997）：这是更广泛的因果图模型领域的经典问题。Verma & Pearl 对有向无环图（DAG）的等价类给出了特征描述（骨架 + v-结构）。Chickering 证明了 DAG 等价类的学习是 NP-hard。本文的 coNP-complete 结果可视为这一线索在局部独立性图上的对应。

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

局部独立性图的可识别性：给定观测数据，能否唯一确定生成过程的局部独立性图？等价类理论回答“不能”——多个图可能编码相同独立性。
等价类的特征描述：能否用一组可验证的条件（如“某条边必须存在/不存在”）来刻画一个等价类？本文证明，在最坏情况下，这样的条件数量是超多项式的。
计算可行性：给定数据，能否在多项式时间内找到等价类的代表？本文的 coNP-complete 结果暗示，除非 P=NP，否则不能。

⚠️ 作者的 framing¶

这是作者的说法：作者将缺口 frame 成“现有局部独立性图理论假设误差独立，但许多应用中误差相关，因此需要推广”。他们淡化/回避了以下竞争路线： - 直接建模相关误差：例如，用向量自回归（VAR）模型加上相关残差，然后通过 Granger 因果检验学习结构。作者认为这不够“图模型化”，但并未在 intro 中正面比较。 - 动态贝叶斯网络（DBN）：DBN 也能处理时间序列的因果结构，且已有成熟的等价类理论。作者未提及 DBN 与局部独立性图的关系。 - 什么明显该被引/该存在、却没出现在 intro 里？：作者未引用 Peters et al. (2013) 关于时间序列因果结构学习的综述，也未引用 Runge et al. (2019) 关于高维时间序列因果发现的实证工作。这些工作可能提供了与本文互补的视角（如有限样本下的结构选择一致性）。

张力¶

未见明显对立引用。所有被引工作基本一致地认为局部独立性图是时间序列因果建模的有用工具，分歧主要在于假设的强弱（独立 vs. 相关误差）和计算可行性。

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

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

符号：
\( V = \{1, \dots, p\} \)：节点集，每个节点对应一个随机过程分量。
\( X = (X_t)_{t \in \mathbb{R}} \)：一个 \( p \)-维随机过程，\( X_t = (X_t^1, \dots, X_t^p) \)。
\( \mathcal{F}_t^A \)：由 \( \{X_s^j : s \leq t, j \in A\} \) 生成的 σ-代数（即节点集 \( A \) 到时间 \( t \) 为止的历史）。
\( \mathcal{F}_{t-}^A \)：由 \( \{X_s^j : s < t, j \in A\} \) 生成的 σ-代数（严格过去）。
局部独立性：节点 \( i \) 在时间 \( t \) 处局部独立于节点 \( j \) 的过去，给定所有其他节点的过去，记作 \( j \not\rightarrow i \)，如果
\[\mathbb{E}[f(X_t^i) \mid \mathcal{F}_{t-}^{V \setminus \{j\}}] = \mathbb{E}[f(X_t^i) \mid \mathcal{F}_{t-}^{V}]\]
对所有有界可测函数 \( f \) 成立。直观上，\( j \) 的过去对预测 \( i \) 的现在没有额外信息，一旦已知所有其他节点的过去。
局部独立性图：一个有向图 \( G = (V, E) \)，其中边 \( j \rightarrow i \) 存在当且仅当 \( j \not\rightarrow i \) 不成立（即 \( i \) 不局部独立于 \( j \)）。
误差过程：\( \epsilon = (\epsilon_t)_{t \in \mathbb{R}} \)，一个 \( p \)-维随机过程，驱动 \( X \) 的演化。本文允许 \( \epsilon \) 的分量之间相关。
马尔可夫等价类：两个图 \( G_1, G_2 \) 是马尔可夫等价的，如果它们编码相同的局部独立性集合（即对任意节点对 \( i, j \)，\( G_1 \) 和 \( G_2 \) 中 \( j \rightarrow i \) 的存在性相同）。
模型：本文考虑一个一般性的随机过程，其局部独立性由一个有向图 \( G \) 编码。关键假设是局部马尔可夫性质：对每个节点 \( i \)，\( X^i \) 的现在（\( X_t^i \)）在给定其父节点（\( pa(i) \)）的过去后，条件独立于所有非后代节点的过去。形式上，
\[X_t^i \perp\!\!\!\perp \mathcal{F}_{t-}^{V \setminus (pa(i) \cup \{i\})} \mid \mathcal{F}_{t-}^{pa(i)}.\]
这是图模型的标准假设，将图结构与概率分布联系起来。
可观测数据：研究者实际能观测到的是随机过程 \( X \) 的样本路径（离散时间观测或连续时间采样）。想要但观测不到的是：
误差过程 \( \epsilon \) 的相关结构（是独立还是相关？相关程度如何？）。
真实的局部独立性图 \( G \)（这是要推断的目标）。
过程的完整历史（\( \mathcal{F}_{t-} \) 是理论构造，实际只能观测有限时间点）。

第二步：讲最小内核¶

最简特例：考虑一个二元过程（\( p = 2 \)），节点 \( 1 \) 和 \( 2 \)，且假设过程是离散时间、一阶马尔可夫的：

\[X_t^1 = a X_{t-1}^1 + b X_{t-1}^2 + \epsilon_t^1, \quad X_t^2 = c X_{t-1}^1 + d X_{t-1}^2 + \epsilon_t^2,\]

其中 \( \epsilon_t = (\epsilon_t^1, \epsilon_t^2) \) 是均值为零的噪声，可能相关：\( \text{Cov}(\epsilon_t^1, \epsilon_t^2) = \sigma_{12} \)。

在这个特例下，局部独立性图 \( G \) 的边由系数决定： - \( 2 \rightarrow 1 \) 存在当且仅当 \( b \neq 0 \)（\( X_{t-1}^2 \) 有助于预测 \( X_t^1 \)）。 - \( 1 \rightarrow 2 \) 存在当且仅当 \( c \neq 0 \)。 - 自环（\( 1 \rightarrow 1, 2 \rightarrow 2 \)）总是存在（因为 \( a, d \) 非零）。

核心问题：给定观测数据 \( \{X_t\}_{t=1}^T \)，能否唯一确定 \( b \) 和 \( c \) 是否为零？等价类回答“不能”——多个图可能产生相同的局部独立性集合。

等价类的例子： - 如果 \( b = 0, c = 0 \)（无交叉影响），则图 \( G \) 只有自环。这是唯一的图。 - 如果 \( b \neq 0, c = 0 \)（只有 \( 2 \rightarrow 1 \)），则图 \( G \) 有边 \( 2 \rightarrow 1 \) 和自环。这也是唯一的。 - 如果 \( b \neq 0, c \neq 0 \)（双向影响），则图 \( G \) 有两条边。这也是唯一的。

但：如果误差相关（\( \sigma_{12} \neq 0 \)），情况变得复杂。考虑一个不可观测的公共驱动过程 \( Z_t \)：

\[X_t^1 = a X_{t-1}^1 + Z_t, \quad X_t^2 = d X_{t-1}^2 + Z_t,\]

其中 \( Z_t \) 是独立同分布噪声。这等价于 \( b = c = 0 \) 但 \( \epsilon_t^1 = Z_t, \epsilon_t^2 = Z_t \) 完全相关。此时，局部独立性图只有自环（无交叉边）。但如果观测者错误地假设误差独立，他们可能会推断出 \( 1 \rightarrow 2 \) 和 \( 2 \rightarrow 1 \) 都存在（因为 \( X_t^1 \) 和 \( X_t^2 \) 的过去相关）。这就是相关误差带来的混淆：它可能产生虚假的局部独立性关系。

本文的核心思路：在允许相关误差的情况下，多个图可能编码相同的局部独立性集合。例如，图 \( G_1 \)（无交叉边，误差相关）和图 \( G_2 \)（有交叉边，误差独立）可能产生相同的局部独立性。本文的目标是刻画这些等价类：给定一个图 \( G \)，哪些其他图与它马尔可夫等价？

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在允许误差过程相关的情况下，局部独立性图的马尔可夫等价类（多个图编码相同局部独立性）的特征描述。
核心工具/方法：图论中的路径条件（类似于 DAG 中的 d-分离）和等价类特征条件（类似于 DAG 中的骨架 + v-结构），以及计算复杂度理论中的 coNP-completeness 归约。
主要结论：给出了等价类的特征描述（定理 1-3），但证明在最坏情况下特征条件数量超多项式增长；进一步证明判定马尔可夫等价是 coNP-complete 问题（定理 4），表明该特征描述不可能被本质改进（除非 P=NP）。此外，对多元 Ornstein-Uhlenbeck 过程，在驱动布朗运动相关的情形下，证明了全局马尔可夫性质（定理 5）。

关键设定与假设¶

在第二节最小记号的基础上，补全完整设定：

定义 1（局部独立性图）：正式定义已在第二节给出。关键假设是局部马尔可夫性质（定义 2）：对每个节点 \( i \)，\( X_t^i \) 在给定其父节点 \( pa(i) \) 的过去后，条件独立于所有非后代节点的过去。这是图与过程之间的桥梁。
假设 1（正则性）：过程 \( X \) 是正则的，即其分布由所有有限维分布唯一确定。这是技术性假设，确保局部独立性条件可以传递到全局。
假设 2（误差过程）：误差过程 \( \epsilon \) 是可加的且独立于过去（即 \( \epsilon_t \) 独立于 \( \mathcal{F}_{t-} \)），但分量之间可以相关。这是本文与已有工作的关键区别：已有工作假设 \( \epsilon \) 的分量独立。
定义 3（马尔可夫等价）：两个图 \( G_1, G_2 \) 是马尔可夫等价的，如果对任意节点对 \( i, j \)，\( G_1 \) 中 \( j \rightarrow i \) 存在当且仅当 \( G_2 \) 中 \( j \rightarrow i \) 存在。注意：这是边存在性的等价，而不是整个图结构的等价（因为自环总是存在，所以等价类只关心交叉边）。

相比已有文献的放宽/强化： - 放宽：误差过程允许相关（已有工作假设独立）。 - 强化：本文的等价类定义只关心边存在性，而不是更精细的“方向性”等价（如 DAG 中的 v-结构）。这是因为局部独立性图是有向图，但自环总是存在，所以等价类只由交叉边的有无决定。

主要结果¶

定理 1（等价类的特征描述——充分必要条件）： - 陈述：两个图 \( G_1, G_2 \) 是马尔可夫等价的当且仅当它们满足一组路径条件：对任意节点对 \( i, j \)，存在一条从 \( j \) 到 \( i \) 的路径（在 \( G_1 \) 中）当且仅当存在一条从 \( j \) 到 \( i \) 的路径（在 \( G_2 \) 中）。 - 直觉：局部独立性只关心“是否存在一条有向路径”，而不关心路径的具体结构。因此，如果两个图有相同的可达性关系（即传递闭包相同），它们就是等价的。 - 必要条件：图必须是无环的（即没有有向环，除了自环）。这是局部独立性图的标准假设。 - 解决的技术难点：证明充分性需要构造一个过程，使得其局部独立性由给定图编码，且两个图产生相同的局部独立性。作者使用线性随机微分方程（SDE）来构造这样的过程。

定理 2（等价类的特征描述——局部条件）： - 陈述：两个图 \( G_1, G_2 \) 是马尔可夫等价的当且仅当它们满足一组局部条件：对每个节点 \( i \)，\( G_1 \) 中 \( i \) 的父节点集 \( pa_1(i) \) 与 \( G_2 \) 中 \( i \) 的父节点集 \( pa_2(i) \) 满足某种包含关系（具体条件略）。 - 直觉：等价类可以由每个节点的“父节点集”的某种等价关系来刻画。 - 与定理 1 的关系：定理 2 是定理 1 的局部版本，更容易用于实际检验。

定理 3（等价类的特征描述——最坏情况复杂度）： - 陈述：在最坏情况下，定理 1 和定理 2 中的条件数量随节点数 \( p \) 超多项式增长（即 \( \Omega(2^{p^\delta}) \) 对某个 \( \delta > 0 \)）。 - 直觉：这意味着，不存在一个“简洁”的特征描述（如多项式大小的条件集合）能覆盖所有情况。 - 证明思路：通过归约到图同构问题的变种。

定理 4（判定马尔可夫等价是 coNP-complete）： - 陈述：给定两个图 \( G_1, G_2 \)，判定它们是否马尔可夫等价是 coNP-complete 问题。 - 直觉：这意味着，除非 P=NP，否则不存在多项式时间算法来判定两个图是否等价。这解释了定理 3 的超多项式增长：任何“简洁”的特征描述都会导致多项式时间判定算法，而 coNP-complete 结果排除了这种可能性。 - 证明思路：通过归约到无向图上的独立集问题（已知 NP-complete）。作者构造了一个从独立集实例到马尔可夫等价判定实例的映射，使得独立集实例有解当且仅当两个图不等价。

定理 5（多元 Ornstein-Uhlenbeck 过程的全局马尔可夫性质）： - 陈述：考虑一个多元 Ornstein-Uhlenbeck 过程 \( dX_t = A X_t dt + B dW_t \)，其中 \( W_t \) 是相关布朗运动（即 \( \text{Cov}(dW_t) = \Sigma dt \)）。如果图 \( G \) 由矩阵 \( A \) 的非零模式定义（即 \( A_{ij} \neq 0 \) 当且仅当 \( j \rightarrow i \)），则 \( G \) 满足全局马尔可夫性质：对任意不相交节点集 \( A, B, C \)，如果 \( A \) 和 \( B \) 在 \( G \) 中被 \( C \) d-分离，则 \( X^A \) 和 \( X^B \) 在给定 \( X^C \) 的过去后条件独立。 - 直觉：这是对已有结果（Eichler, 2012）的推广：即使驱动布朗运动相关，全局马尔可夫性质仍然成立。 - 证明思路：利用 Ornstein-Uhlenbeck 过程的显式解（\( X_t = e^{At} X_0 + \int_0^t e^{A(t-s)} B dW_s \)）和布朗运动的性质。

证明路线与技术技巧¶

整体路线（定理 1-4）： 1. 定义等价关系：先证明“可达性相同”是等价关系的充分必要条件（定理 1）。这一步相对直接：如果两个图有相同的传递闭包，则它们编码相同的局部独立性；反之，如果它们编码相同的局部独立性，则传递闭包必须相同。 2. 局部化：将全局的可达性条件转化为每个节点的局部条件（定理 2）。这一步需要图论中的路径分解技巧。 3. 复杂度下界：证明最坏情况下条件数量超多项式增长（定理 3）。这一步通过构造一个图族，其中每个图都需要指数多个条件来区分。 4. coNP-complete 归约：将独立集问题归约到马尔可夫等价判定问题（定理 4）。这是最吃功夫的一步。

关键跳跃点（定理 4 的归约）： - 难点：如何将独立集问题（一个无向图问题）转化为有向图等价问题？ - 作者的解法：构造一个辅助图 \( H \)，其节点集包含原始独立集实例的所有节点，再加上一些辅助节点。然后构造两个有向图 \( G_1, G_2 \)，使得 \( G_1 \) 和 \( G_2 \) 不等价当且仅当原始独立集实例有解。具体构造利用了有向路径的“阻塞”机制：如果独立集实例有解，则 \( G_1 \) 中有一条路径在 \( G_2 \) 中被阻塞，导致等价性被破坏。

技术技巧点名： - 图论中的路径分解：用于定理 2 的局部化。 - 组合构造：用于定理 3 的超多项式下界。 - 归约（reduction）：用于定理 4 的 coNP-complete 证明。这是计算复杂度理论的标准技巧，但对统计学家来说可能不熟悉。 - 随机微分方程（SDE）：用于定理 5 的全局马尔可夫性质证明。作者利用 Ornstein-Uhlenbeck 过程的显式解和布朗运动的独立增量性质。

真实例子与应用¶

本文为纯理论/无实证例子。作者没有使用任何真实数据或模拟实验来验证理论结果。所有结论都是数学定理。

🔎 结论是否比证明窄¶

定理 1-3 的结论与证明范围一致：它们严格在“允许相关误差”的设定下成立。
定理 4（coNP-complete）的证明依赖于一个特定的归约构造。作者在文中明确写道（第 5 节）：“The reduction uses a construction that requires the graphs to have a specific structure... It is an open question whether the coNP-completeness result holds for restricted classes of graphs (e.g., graphs with bounded indegree).” 这意味着，对于有界入度的图，判定马尔可夫等价可能不是 coNP-complete（即可能有多项式时间算法）。这是一个比证明窄的结论：作者只证明了最坏情况下的复杂度，但未排除实际中常见情况（如稀疏图）的可处理性。
定理 5 的结论与证明范围一致：它严格在 Ornstein-Uhlenbeck 过程和相关布朗运动的设定下成立。作者未尝试推广到其他随机过程。

四、开放问题¶

有界入度图的等价类判定：定理 4 的 coNP-complete 结果是否对有界入度的图也成立？作者在第 5 节明确提到这是一个开放问题。如果答案是否定的（即存在多项式时间算法），则实际应用（如稀疏时间序列）中可能可以高效地学习等价类。扎根点：定理 4 证明后的讨论。
有限样本下的结构学习：本文只给出了等价类的理论特征，但未讨论有限样本下如何从数据中学习等价类（或等价类的代表）。例如，能否用高维统计中的惩罚似然或假设检验方法，在稀疏假设下一致地估计等价类？扎根点：本文未涉及任何统计推断或算法。
相关误差的识别：本文允许误差相关，但未讨论如何从数据中识别误差的相关结构。例如，能否用谱分析或残差分析来检验误差是否独立？如果不能识别，则等价类可能非常大，导致结构学习几乎不可能。扎根点：本文的设定部分（假设 2）允许任意相关结构，但未给出识别条件。
非马尔可夫过程的推广：本文假设过程满足局部马尔可夫性质。对于非马尔可夫过程（如长记忆过程），局部独立性图是否仍然有意义？等价类理论是否需要修改？扎根点：本文的假设 1（正则性）和局部马尔可夫性质是核心，但未讨论更一般的过程。

Maintained by 陈星宇 · Homepage · Source on GitHub