Technical University of Munich) Half-Trek Criterion for Identifiability of Latent Variable Models¶
讲者: Mathias Drton (
讨论人: Robin Evans
来源: OCIS (Online Causal Inference Seminar)
日期: 2022-03-22
主题: 因果推断
视频: https://youtu.be/XAoKhwMdFqI · 幻灯片
本页据讲座录音的自动转写（ASR）生成。人名 / 术语 / 公式 / 具体的率与界可能被听错，关键处请对照视频或讲者论文核对。
相关论文¶
- 2201.04457 （尚未精读 —
talks read --id … --read-papers可补）
一、这场报告在讲哪条工作线¶
这场报告扎根于 线性结构方程模型（Linear SEM） 的因果效应识别问题。该子方向追问：给定一个被有向图描述——图中节点既包括观测变量 (observed variables) 也包括潜变量 (latent variables)——的线性数据生成过程，能否从观测数据的协方差矩阵中唯一恢复出观测变量之间的直接因果效应（即结构方程中观测变量间的系数 Λ）？
- 奠基与主流路线：
* 奠基性工作可追溯到 Wright (1921, 1934) 的路径分析 (path analysis) 和追寻规则 (trek rule)，该规则给出了协方差与图结构参数之间的多项式关系。
* Brito & Pearl (2002, 2010) 提出了第一个系统性的图论识别准则，利用潜伏协方差矩阵中零元素（即无共同潜变量混淆的变量对）来建立方程，并在观测变量间系数中求解。这些方法本质上是线性代数的：从 (I-Λ)^T Σ (I-Λ) 的零项得到关于 Λ 的线性方程。
* 在潜变量投影框架 (latent projection) 下，Foygel, Draisma, & Drton (2012, Ann. Statist.) 提出了半游程准则 (HTC)。该方法将潜变量的混淆效应投影为双向边，利用零混淆结构下 Ω 的零元素，通过组合条件（半游程无侧交）保证线性方程组的可解性。该准则在混淆稀疏时有效。
- 当前 frontier 与这场报告的站位：
* 上述方法无法处理一种常见情形：一个潜变量密集地影响多个（甚至全部）观测变量。这时潜伏协方差矩阵 Ω 是稠密的（无零元素），但它是低秩的（对角阵 + 若干个秩1矩阵的和）。这场报告（Barber, Drton, Sturma, Weihs 2022, arXiv:2201.04457）的核心贡献是：提出潜因子半游程准则 (LF-HTC)，将之前的零元素策略推广到利用低秩结构。关键技巧：不再找 Ω 的零元素，而是找秩亏缺的离对角子矩阵，利用该低秩性将 Ω 的列空间线性依赖转化到 (I-Λ)^T Σ (I-Λ) 上，从而得到关于 Λ 的线性方程组。条件仍然是充分而非必要的，但多了计算复杂性的权衡：当搜索中考虑潜变量子集 |H| 有界时，算法是多项式时间的；无界时，搜索是 NP-完全的。
二、最小内核 / 一个最简例子¶
模型、符号与可观测数据：
- 节点: V = {1,2,3} 观测节点, L = {h} 一个潜变量。
- 有向图: 边集 D: 1→2 (系数 λ₁₂), 2→3 (系数 λ₂₃), h→2 (系数 γ₂), h→3 (系数 γ₃)。潜变量 h 无入边 (源节点, latent factor)。
- 结构方程 (无截距，用均值0变量):
X₁ = ε₁
X₂ = λ₁₂ X₁ + γ₂ L₁ + ε₂
X₃ = λ₂₃ X₂ + γ₃ L₁ + ε₃
L₁ = ε_ℓ
(X₁, X₂, X₃) 的联合协方差矩阵 Σ 是一个 3×3 正定矩阵。
- 潜在不可观测量: L₁, 所有误差项 (ε₁, ε₂, ε₃, ε_ℓ)；以及所有参数：λ₁₂, λ₂₃ (感兴趣的 estimand), γ₂, γ₃, ω₁, ω₂, ω₃（误差方差，均为正值）。
- 核心思想: 定义潜伏协方差矩阵 Ω = Var[ (Γ^T L + ε) ]，这里 Γ = [0, γ₂, γ₃]。根据结构，Ω = diag(ω₁, ω₂+γ₂², ω₃+γ₃²)，但有两个关系：Ω₁₂ = 0 且 Ω₁₃ = 0 (因为潜变量 h 不作用于 X₁，且误差独立)。根据 X = (I-Λ)^{-T} (Γ^T L + ε)，有 Ω = (I-Λ)^T Σ (I-Λ)。因此，Ω 的零元素给出了关于 Λ 和 Σ 的方程：
[ (I-Λ)^T Σ (I-Λ) ]₁₂ = 0 => σ₁₂ - λ₁₂ σ₁₁ = 0 => λ₁₂ = σ₁₂/σ₁₁
[ (I-Λ)^T Σ (I-Λ) ]₁₃ = 0 => σ₁₃ - λ₂₃ σ₁₂ = 0 => λ₂₃ = σ₁₃/σ₁₂
X₁ 无入边 (λ 不作用在 X₁ 上)，所以 (I-Λ)^T X 的第一行等于 X₁。这就直接得到了经典的 IV 估计量。新工作的关键推广：当低矩阵没有零元素，但 Ω 的某个子矩阵是低秩的时，仍然可以从该子矩阵的秩亏缺中找到关于 Λ 的方程。
例子: 考虑 V = {1,2,3,4,5}, L = {h}，h 影响所有 5 个观测变量。这时 Ω 是稠密的 (秩为 1 的部分是满的)，但它是 diag + 秩1 结构。幻灯片 18 展示了如何用 LF-HTC 递归求解这个 5 节点模型中的全部 3 个观测边效应 (1→2, 2→3, 4→5)。
三、报告主体：讲者讲了什么¶
[0:07 - 0:29] 开场与滑动示例
- 介绍了线性 SEM 以及由有向图诱导的模型。以工具变量 (IV) 模型为例：X₁ 税额 → X₂ 母亲吸烟 → X₃ 婴儿体重，潜变量 L₁ (socioeconomic factors) 同时影响 X₂, X₃。给出线性方程，解释系数 λ₁₂, λ₂₃ 是从观测协方差 Σ 中通过有理函数恢复的：λ₁₂ = σ₁₂/σ₁₁, λ₂₃ = σ₁₃/σ₁₂。
[0:29 - 0:45] 问题一般化
- 将模型推广到一般图 G = (V ∪ L, D)，观测节点 V，潜节点 L。关键假设：所有潜变量都是源节点 (latent factors)，即它们只外生作用于观测变量，彼此独立，方差归一为 1。模型参数化：φ_G: (Λ, Γ, Ω_diag) → Σ。关心有理可识别性 (rational identifiability)：是否存在有理函数 ψ_G 使得 ψ_G(Σ) = Λ 对几乎所有的参数成立。
[0:45 - 1:00] 软件演示
- 简要演示了 R 包 SEMID：用户定义图结构（结合观测和潜节点），调用 lfhtcID() 函数即可查询哪些观测边系数是可识别的。讲者指出该包可以整合到工作流中。
[1:00 - 1:18] 核心代数关系：潜伏协方差矩阵与低秩结构
- 推导 Ω = (I-Λ)^T Σ (I-Λ)。由于潜变量是源节点，Ω = Ω_diag + Γ^T Γ，其结构是对角阵 + 若干个秩 1 矩阵的和。因此，Ω 具有丰富的代数关系：零项（无共同潜混淆）和低秩的离对角子矩阵（潜变量有密集影响）。这些关系通过 (I-Λ)^T Σ (I-Λ) 转化为关于 Λ 和 Σ 的代数方程。
- 以 IV 模型为例：Ω₁₃ = 0（因为 γ₁=0） → [ (I-Λ)^T Σ (I-Λ) ]₁₃ = σ₁₃ - λ₂₃ σ₁₂ = 0，直接得到线性方程。
[1:18 - 1:30] 追寻规则与 2012 年 HTC 的回顾
- 追溯回 Wright 的追寻规则：Σ 的条目是沿追寻 (treks)（先上溯路径后下溯路径）的乘积之和，这是 (I-Λ)^{-1} 是路径矩阵这一事实的体现。
- Foygel et al. (2012) 的半游程准则 (HTC)：通过零迷失 (no latent confounding) 带来 Ω 的零项，建立线性方程系统；利用半游程（从节点出发只向下或先到潜变量再向下）序列的无侧交 (no-sided-intersection) 条件，借助Gessel-Viennot 引理来判定系数矩阵是否可逆。计算复杂度：通过网络流在多项式时间内完成。注意：HTC 2012 是在潜变量投影后的混合图上工作的。
[1:30 - 1:39] 新工作的动因：需要处理密集潜变量
- 举例：一个潜变量 h 影响所有 5 个观测变量 ⇒ 潜伏协方差矩阵 Ω 是稠密的（无零元素），但它是低秩的（对角 + 秩1）。HTC 2012 无法处理。
[1:39 - 1:48] 新 LF-HTC 准则的主思路
- 基本策略不变：递归地逐一解出 Λ 的列。
- 新技巧：不是找零项，而是找秩亏缺的离对角子矩阵 Ω_{Y, Z ∪ {v}}。由于 Ω 具有低秩结构，该子矩阵的秩等于 |Z|，且 Ω_{Y, {v}} 是 Ω_{Y, Z} 中列的线性组合（即有向量 ψ 使得 Ω_{Y, {v}} = Ω_{Y, Z} ψ）。这个秩亏缺关系转化为关于 Λ 和未知向量 ψ 的线性方程组，再结合已解出的其他列，最终可唯一求解。
[1:48 - 1:54] 半游程定义与 LF-HTC 的正式条件
- 半游程：v → ... → w 或 v ← ℓ → ... → w。重点是“无侧交”：左右两侧的节点集不交。讲者指出该条件确保系数矩阵的可逆性。
- LF-HTC 三元组 (Y, Z, H)：定义模糊，但核心约束是：
1. |Y| = |pa(v)| + |H|，|Z| = |H| (确保方程数与未知数匹配)。
2. Y \ (Z ∪ {v}) = ∅ (确保子矩阵完全在离对角线)。
3. pa_L(Y) \ pa_L(Z ∪ {v}) ⊆ H (控制哪些潜变量产生混淆)。
4. 存在从 Y 到 pa(v) ∪ Z 的无侧交半游程系统。
- 命题：满足上述条件 ⇒ Ω_{Y, Z ∪ {v}} 的秩为 |H| (即 |Z|)。
[1:54 - 1:59] 算法与计算复杂性
- 递归求解：对一个节点 v，搜索满足 LF-HTC 的三元组，全部使用已知的 Λ 列和 Σ；求解后标记 Λ_{pa(v), v} 已知。迭代直到所有列被解出或停滞。
- 多项式时间：如果搜索对潜变量集合大小 |H| 设置常数上界，则可通过网络流在多项式时间内找到合适的三元组。无上界时，搜索问题是 NP-完全的。
[2:00 - 2:10] 例子与讨论 (Robin Evans 主持)
- Robin Evans 的讨论：
* 指出一个微妙陷阱：观测 Σ 是从原始有向图生成的，如果进行潜变量投影（用双向边代替潜变量），投影后的混合图可能变得 HTC 可识别，但原始模型在投影后的参数空间中落在一个低维子流形上，导致分母为零/数值不稳定。LF-HTC 保留原始结构，避免了此问题。
* Tian 分解 (Tian, 2005)：将大图按“区 (district)”分解，如果每个区独立 LF-HTC 可识别，则整体可识别。举例说明分解可以显著扩大可识别图的集合。
* 提出开放问题：是否存在必要性的图论条件？对于中等大小的图，LF-HTC 的覆盖率如何？Tian 分解能增加多少个可识别的图？
- 讲者回应：
* 必要性问题是开放问题。旧 HTC (2012) 能用雅可比矩阵的秩给出维度判据，但在新设置下更复杂，是未来的方向。
* 论文中的模拟实验仅考察了 LF-HTC 本身，未系统评估 Tian 分解带来的增益。后者是值得进一步探索的。
四、对应论文与开放问题¶
对应论文 (parameters: uncertain for arXiv number, but confirmed by talk and slides):
- Barber, Drton, Sturma, Weihs (2022). Half-Trek Criterion for Identifiability of Latent Variable Models. arXiv:2201.04457. (讲者明确提及，地址未给出，需在 arXiv 上核实)
- 背景论文：
* Foygel, Draisma, Drton (2012). Half-Trek Criterion for Generic Identifiability of Linear Structural Equation Models. Ann. Statist. 40(3), 1682–1713.
* 关于代数方法：Drton (2018). Algebraic Problems in Structural Equation Modeling. The 50th Anniversary of Gröbner bases.
- 软件: R 包 SEMID (slides 和转写都提到)。
开放问题 (相关转写时间点 [H:MM]):
1. 必要性的图论条件 ([1:55 - 1:59] 讲者回应 Robin Evans 的第一个问题): 旧 HTC 有维度判据，但新 LF-HTC 下，如何推导基于雅可比矩阵的非识别性必要条件？讲者将其定为未来工作。
2. Tian 分解的实际增益 ([1:55 - 2:00] 讲者回应 Robin Evans 的第二个问题): 将一个图分解为区，并递归应用 LF-HTC，能多大程度扩大可识别的图集？论文的模拟是否包含了这种分解？讲者未给出答案，表示是“going forward”的方向。
3. 计算复杂性的边界 ([1:48 - 1:54] 讲者陈述): 已证明：当潜变量子集大小 |H| 无上界时，寻找 LF-HTC 三元组的搜索问题是 NP-完全的。是否存在某个特定的图结构 (如 bounded treewidth) 能使搜索变易？ 这对应您对 computational-complexity 的兴趣，可查阅 paper 对此的证明细节。
Maintained by 陈星宇 · Homepage · Source on GitHub