Graphical Representations for Algebraic Constraints of Linear Structural Equations Models¶

讲者: M. van Ommen
讨论人: Rohit Bhattacharya
来源: OCIS (Online Causal Inference Seminar)
日期: 2023-05-02
主题: 因果推断
视频: https://youtu.be/2B_-z9wNfXg · 幻灯片

本页据讲座录音的自动转写（ASR）生成。人名 / 术语 / 公式 / 具体的率与界可能被听错，关键处请对照视频或讲者论文核对。

一、这场报告在讲哪条工作线¶

这场报告位于因果推断的一个子方向：线性结构方程模型（LSEM）的约束描述与模型等价性测试。它追问的是：给定一个（可能有双向边、甚至带环的）LSEM图，可观测到的协方差矩阵 Σ 必须满足哪些超越条件独立性的约束？这些约束反过来能否帮助区分两个不同的图、或用于因果发现？

这个子方向有一条清晰的脉络：

奠基&主流路线：对于DAG，变量间的约束完全由有向分离（d-separation）给出的条件独立（CI）刻画（Pearl, 2000）。这一套由m-separation推广到含有隐含混杂（bidirected edges）的ADMGs（Richardson & Spirtes, 2002; Richardson, 2003），但仅靠CI约束不足以刻画所有LSEM模型。
超越CI的约束类型：
嵌套马尔可夫约束（Nested Markov constraints） 完全刻画非参数/离散情形下的ADMG可识别性（Tian & Pearl, 2002; Shpitser, Evans, Richardson & Robins, 2014）。
消退tetrads及其推广（Vanishing tetrads & generalizations）：在线性LSEM下出现的、比CI更强的多项式约束，有图形化判定准则（t-separation）（Sullivant, Talaska & Draisma, 2010）。
代数约束（Algebraic constraints）：一般的多项式等式，正是这场报告的核心对象。| 转写 [0:10-0:12] 、幻灯片第4-5页
这场报告站在哪儿：它不是在前两条线上加一个“新的约束类型”，而是在给第三个类型——代数约束——找到一个比直接写多项式更简洁、可计算的图形化表示（graphical constraints），以及一个从图到这些图形化约束的构造算法。

关键工作：van Ommen & Drton (2022) "Graphical Representations for Algebraic Constraints of Linear Structural Equations Models", PMLR 188 (Proceedings of PGM 2022)。报告还依赖： - 半追踪准则（Half-Trek Criterion, HTC）的充分条件判定LSEM的generic identifiability（Foygel, Draisma & Drton, 2012）。 - 用于含双向边图参数估计的RICF算法（Drton, Eichler & Richardson, 2009; Drton, 2018 等）。

用户交叉点：用户自己的专业是因果推断的识别/敏感性分析、半参数效率理论。这场报告的主线不涉及半参数效率或高维统计，但它处理的是线性SEM参数估计的前提——模型约束是否正确（constraint-based testing），以及哪些结构是等价的。这与用户的「identification theory in causal inference」和「model equivalence」直觉直接相关，也能为因果发现（causal discovery）的工具箱提供新的entry。
注意：用户目前对线性SEM的细节（如何用h Trek计算识别性的具体步骤、理想论的代数几何）很可能是"outsider status"，所以这场报告对用户的价值在于：它提供了一个用图论语言“包装”代数约束的低门槛视角，而非深入交换代数。

二、最小内核 / 一个最简例子¶

1. 设置符号

令有向图 \(G=(V,D,B)\)： - \(V=\{X_1,\dots,X_p\}\)，可观测变量。 - \(D\)：有向边集合 \(X_v \to X_w\)，表示 \(X_w\)的方程线性地包含\(X_v\)：

\[X_w = \lambda_{0,w} + \sum_{v: v \to w} \lambda_{v,w} X_v + \epsilon_w\]

- \(B\)：双向边集合 \(X_v \leftrightarrow X_w\)，表示误差项 \(\epsilon_v\) 与 \(\epsilon_w\) 可以非零协方差（隐含混杂的线性近似）。

可观测数据：协方差矩阵 \(\Sigma = \mathrm{Cov}(X)\)（\(p \times p\)，假定了Gauss性，但不必需多项式约束）。
不可观测参数：回归系数 \(\lambda_{v,w}\) 和误差协方差矩阵 \(\Omega\)（对角元为误差方差，非对角元由双向边决定）。

2. 一个直观的最简特例（转写多处反复提到）

图（4个节点）：

a → b → d
a ← c → d

这个LSEM（没有双向边）在协方差矩阵上施加了一个非CI的代数约束。

约束不是条件独立：
变量之间未观察到任何“给定某集合时C与D条件独立”（因为图中C→D有边，且D的父亲有B，C的父亲无B，任何包含B的条件都会m-connect C与D）。
也不是消退tetrad（因为4变量tetrad牵涉三阶，这里没有那种模式）。
这个约束长什么样（从幻灯片第5页提取）：
\[\sigma_{aa}\sigma_{bd}\sigma_{bc} - \sigma_{aa}\sigma_{bb}\sigma_{cd} - \sigma_{ab}\sigma_{ad}\sigma_{bc} + \sigma_{ab}^2 \sigma_{cd} = 0\]
一个四次齐次多项式。它很难直接“读懂”。
这场报告的图形化表示：构建一个二分图，左边节点标号集为 \(\{\,\{c\},\,\{b,a\},\,\{a\}\,\}\)，右边节点标号集为 \(\{\,\{d\},\,\{b\},\,\{c\}\,\}\)。边按如下对应填入——当且仅当标号集的交集非空时有边（幻灯片第6页图）：
```
{c}  —— {b, a}  —— {a}
 |       |         |
{d}     {b}      {c}
```
把这个二分图记为邻接矩阵 \(M\)，其中 \(M_{row,col} = \sigma_{u,v}\) 如果标号 \(u\) 与 \(v\) 的交集非空；否则为0。
\[M =\begin{pmatrix} \sigma_{c,d} & \sigma_{c,b} & \sigma_{c,c} \\ \sigma_{ba,d} & \sigma_{ba,b} & \sigma_{ba,c} \\ \sigma_{a,d} & \sigma_{a,b} & \sigma_{a,c} \end{pmatrix}\]
其中 “\(\sigma_{ba,d}\)” 表示 \(\sigma_{b,d}\) 或 \(\sigma_{a,d}\)？实际标号是集，做法是：每个标号对应一个变量子集，边存在当两个标号有交集，矩阵的条目则由那个交集里的变量对对应的协方差填充（幻灯片原文： “converted to ‘adjacency matrix’ with σ_{vw} where there is an edge”）。这个例子的填充方式在幻灯片中被略去，但示例图展示了这个二分图。然后取 \(\det(M)=0\) 就恢复了上面那个四次多项式。

这样就把一个难以直接阅读的代数约束，编码成了一个更紧凑的图模式。

核心思想：不是直接写出多项式，而是存一个 \(n\times n\) 的二分图+行列式计算，行列式即约束。如此可以快速评估约束是否成立（算一个行列式比算超大多项式长度快得多）。

三、报告主体：讲者讲了什么¶

时间线：整体约17分钟报告+15分钟讨论。以下时间标记按视频时间戳。

[0:00-0:02] 开场，LSEM定义 - 联合工作与 Mathias Drton（TUM）。发表于PGM 2022。 - LSEM：每个变量线性地依赖于其父变量 + Gaussian误差。允许双向边（表示误差相关，即隐含混杂）和bow（同一对变量既有有向边又有双向边），甚至允许有向环（但本报告主要处理无环情况）。| 幻灯片第2页

[0:02-0:07] 问题：描述LSEM的模型（=所有可能的 Σ 的集合） - 为什么需要描述模型？因为要区分两个图能不能只用观测数据区分开、用于因果发现。 - DAG情形：完事由条件独立性（CI）约束描述（d-separation）。 - LSEM超越CI：本报告核心例子（上面最简例子）非CI、非嵌套Markov、非tetrad。

[0:07-0:09] 代数约束 - 代数约束 = 多项式等式，形式如一长串 \(\sum c \cdot \sigma_{ab}\sigma_{cd}\cdots =0\)。 - 除了代数等式，还有半代数不等式（忽略）。 - 问题：多项式非常大，用到代数几何算法(如计算Gröbner basis)有时需数天/周。| 转写 [0:10-0:12]

[0:09-0:14] 图形约束（Graphical constraints）的引入和构造 - 定义：一个无向二分图，每个节点标号是 \(V\) 的一个子集。 - 翻译成多项式：二分图的邻接矩阵按如下规则填入 \(\sigma_{uv}\)：对每个节点（对应行/列），它的标号集 \(S\)；另一个节点的标号集 \(T\)；若 \(S \cap T \neq \emptyset\)，在 \(S\)（行）与 \(T\)（列）交叉处放 \(\sigma_{s,t}, s\in S, t\in T\)（实际如何确定具体变量？幻灯片和报告没有明确哪个 \(s\) 与哪个 \(t\) 对应。讲者说“there will be a Sigma... indexed by these two labels”。不确定。这是需要看原文细节的地方）。没有边的位置填 0。 - 例子： - 零协方差：二分图只有一个节点对 \(\{a\}\) — \(\{b\}\) → \(\sigma_{ab}=0\). - 偏相关系数：\(a\) 与 \(b\) 给定 \(c\) 的条件独立 → 二分图 \(\{a,c\}\) — \(\{b,c\}\) → 矩阵 \(\begin{pmatrix}\sigma_{ac} & \sigma_{ab}\\ \sigma_{bc} & \sigma_{bb}\end{pmatrix}\)？实际要核实。| 用户看到这可能不确定，应记为需要查原文。 - 消退tetrad：二分图 \(\{a,b\}\) — \(\{c,d\}\)。 - 更复杂的例子：上面最简例子的二分图（幻灯片第7页）。

[0:14-0:20] 背景：半追踪（Half-Trek）准则与Generic Identifiability - HTC是Foygel, Draisma & Drton (2012)给出的充分条件：如果一张图满足HTC，则模型参数在几乎处处的参数空间上可由 \(\Sigma\) 唯一恢复（generic identifiability）。 - HTC需要用到 "half-trek"：或者一条有向路径；或者一条双向边+之后全是单向的路径。 - 例子：instrumental variable (IV) 模型 (a→b↔c, b→c) 是generic identifiable（除非 \(\lambda_{a,b}=0\) 这个零测集）。

[0:20-0:27] 算法：从HTC-identifiable图到图形约束（重点） - 只对HTC-identifiable图有效（需要提供HTC certificate）。 - 对于BAPs（bow-free acyclic path diagrams，即无向环也无双向-有向边对的图）： 1. 对每对不相邻的节点v,w，用二分图 {v}—{w} 2. 反复“expand”节点：对当前节点x，将其父节点 pa(x) 加入标号集，同时创建新节点标号为单个元素 p ∈ pa(x)，并连边。 3. 递归扩展的条件：当且仅当存在从“子节点”回父节点的一个half-trek。 - 转写 [0:22-0:30] 以最简例子（4变量图）展示了递归过程： - 起始：{c}—{d} - 扩展D：B是D的父节点 → 标号集变成 {d,b}，新节点 {b} 连边。 - 检查从D到B是否有half-trek？有（b→d） - 扩展B：A是其父 → 标号集变成 {d,b,a}，新节点 {a} 连边。 - 检查从B到A的half-trek？没有（A→B，但B→A不存在）。停止。最终二分图上有4个节点（标号集分别为 {c}, {d,b,a}, {b}, {a}），三个属于“行”部分、四个“列”部分（但因为二分图补全了所有边？这一点在转写里不清晰）。

[0:27-0:34] 约束集合的代数性质 - 保证：若 \(\Sigma\) 来自模型，则所有图形约束对应的多项式在 \(\Sigma\) 处为0。 - 不保证反向：存在不在模型内的 \(\Sigma\) 满足所有图形约束。这种假正解发生的情况分三类： 1. 非 generic case（小洞口）：参数在零测集上。多项式约束本身也区分不了。 2. HTC计算遇到奇异矩阵：逆向构造参数时，解线性系涉及求逆矩阵，该矩阵可能奇异 → 走入“假区域”。 3. 有向环情形（本报告未深挖），相同参数不恢复原 \(\Sigma\)。

[0:34-0:42] 理想的分类（代数几何视角） - 一组多项式约束定义了一个理想（ideal）。 - Prime ideal：最理想情况，恰好描述模型。 - PD-primary ideal：限制在正定矩阵上等价于Prime ideal。例如，如果约束多项式为 \(\sigma_{aa} \cdot f_{\mathrm{prime}}\)，所有正定 \(\Sigma\) 满足约束的集合与 \(f_{\mathrm{prime}}=0\) 正定集相同，因为 \(\sigma_{aa}>0\) 不可能是负的。命题：若图是ancestral（包括DAG和MAG），算法输出PD-primary ideal。 - I-primary ideal：假组分可以通过检查 \(\Sigma = I\)（单位阵）是否在该假组分内来排除（因为任何LSEM都包含 \(\Sigma=I\)）。命题：若图为BAP，算法输出I-primary ideal。

[0:42-0:50] 多约束的交互与表达力的实验结果 - 一个5节点图（a,b,c,d,e）： - 算法输出2个约束（由组合数 \(\binom{5}{2} - |E|\) 决定，本处为 10-8=2）。 - 然而真正的Prime ideal需要3个约束（消退tetrad: {ab}{cd}, {ab}{ce}, {ab}{de}）。只留2个会产生假成分（由\(\sigma_{ac}=\sigma_{bc}=0\)定义）。 - 总结：多约束的交互可以制造“假成分”。 - 实验评估（5节点图，共约400个代数等价类）： - 17个类全部无HTC-identifiable图（不能跑算法）。 - 其余类：81%（约310个）能够找到graphical constraint； - 其中大多数（~85%）为Prime graphical constraint； - 另外3个类找到PD-primary但不是Prime（多项式有 \(\sigma_{aa}\) 或类似因子）。 - 2个类：算法只能产出PD-primary，穷举搜索证实不存在Prime graphical constraint（所以达不到Prime）。但PD-primary对应用目的已经足够。

[0:50-1:00] 讨论（Rohit Bhattacharya主持） - 关键问题：给定一个含约束的模型（Null），应该选择哪个超模型（Alternative）来做假设检验？ - 选择1：添加有向边（缺点：超模型可能不是全局可识别的，生成 MLE不稳定）。 - 选择2：添加双向边（可能全局可识别？但也可能失去HTC可识别性）。 - 选择3：坍缩到完全饱和DAG（太宽，可能引入额外约束）。 - 具体例子说明选择很重要：若选的有向边超模型是HTC-identifiable，参数估计平稳；若选的不在HTC内，参数估计可能发散。 - 最后展望因果发现：目前已有针对ancestral graphs和bow-free ADMGs的因果发现算法，能否推广到HTC-identifiable graphs？

四、对应论文与开放问题¶

对应的论文¶

主要论文: Thijs van Ommen & Mathias Drton. (2022). "Graphical Representations for Algebraic Constraints of Linear Structural Equations Models". Proceedings of the 12th International Conference on Probabilistic Graphical Models (PGM 2022), PMLR 188. arXiv: [个人应确认是否有arXiv版本；转写并未给出arXiv号]
依赖的关键前作:
Foygel, R., Draisma, J., & Drton, M. (2012). "Half-trek criterion for generic identifiability of linear structural equation models". The Annals of Statistics, 40(3), 1682–1713.
Sullivant, S., Talaska, K., & Draisma, J. (2010). "Trek separation for Gaussian graphical models". The Annals of Statistics, 38(5), 2885–2910.
Richardson, T. S. (2003). "Markov properties for acyclic directed mixed graphs". Scandinavian Journal of Statistics, 30(1), 145–174.

开放问题（每条扎根在转写具体位置）¶

如何将算法扩展到非HTC-identifiable图？ | 转写 [0:50-0:52] 明确说：“right now the algorithm only works for half-trek criterion identifiable graphs, but there have been a number of extensions of the half-trek criterion since the original... so it would be very interesting if an algorithm could be devised that can also leverage these generalizations.”
能否自动剔除图形约束中多余的因子（spurious factors）？ | 转写 [0:52-0:54]：实验中用手动方式（改变证书/在等价类里换图/行列操作）去掉如 \(\sigma_{aa}\) 这种因子来实现Prime。需要自动化办法。
能否为图形约束定义一个“separation criterion”（类似d-separation或t-separation）？ | 转写 [0:50-0:51]：“it would be great if there could be a graphical separation criterion along the lines of t-separation based on these graphical constraints.” 这将允许在不展开每个约束成多项式的情况下，直接用图读出“什么约束在什么图里成立”。
怎么设计统一的超模型做假设检验？ | 讨论中 Rohit 提出：当从含约束的约束模型（Null）到含更多边的超模型时，如何保证超模型是识别的？这直接关联到HTC可识别性。Rohit 的模拟显示，选错超模型（移到非识别区域）会导致MLE发散。问题：“Is there a general rule how we overcome these holes in the search space?” | 转写 [1:01-1:03]
能否将本工作整合进因果发现算法？ | 讨论末尾Rohit对比了已有的ancestral graph和bow-free ADMG的因果发现算法，提出开放问题“how do we get to doing causal discovery for HTC-identified ADMGs?” | 转写 [1:03-1:04]

Maintained by 陈星宇 · Homepage · Source on GitHub