Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions¶

讲者: Anish Agarwal
讨论人: Christina Lee Yu
来源: OCIS (Online Causal Inference Seminar)
日期: 2024-10-01
主题: 因果推断
视频: https://youtu.be/o_rHksAzXCg · 幻灯片

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

相关论文¶

2303.14226 （尚未精读 — talks read --id … --read-papers 可补）

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

这个方向在追问什么¶

许多实际决策问题关心的是 组合干预（combinatorial intervention）——即同时采取多项行动（如推荐一组电影、敲除一组基因、选择一组特征）对某个结局（用户参与度、疾病状态、预测性能）的因果效应。从因果推断的经典问题“做 A 对 Y 有什么影响”出发，这里本质上是问“对同一个体，所有 2^P 种组合的个体化潜在结果是什么”。挑战是双重的：实验上，需要 N×2^P 场实验，不可行；观测数据中，大多数组合未被观测到（“列缺失”严重），且有未观测混杂。

奠基与主流路线¶

仅利用稀疏性：将每个个体的潜在结果视为一个布尔函数，并在 Fourier 基下假设该函数是 s-稀疏的（只有少数 Fourier 系数非零，例如 k-Junta 或低度多项式）。这类工作（Negahban & Shah ’12 用 Lasso；Syrgkanis & Zampetakis ’15 用 CART）对每个个体独立做一次稀疏回归，样本复杂度为 O(N×s²p)。缺点：没有利用个体之间的相似性。
仅利用低秩性（矩阵补全）：将 N 个个体 × 2^P 种组合的期望潜在结果矩阵假设为 秩 r （远小于 N, 2^P）。经典矩阵补全方法（Candès & Recht ’09；Mazumder et al. ’11；Chatterjee ’15 等）的样本复杂度为 O(poly(r)×(N+2^P))。缺点：2^P 项导致仍然指数依赖 P；且在实际中，大多数列（组合）零观测，导致列空间信息不足。
结合低秩与稀疏的已有尝试：稀疏+低秩的结构在降秩回归（reduced-rank regression）中已有研究，但通常是对回归系数矩阵同时做稀疏性与低秩性约束（记不清准确引用，讲者在讨论环节提到“sparse reduced rank regression”）。不过，大部分工作没有将个体层面的稀疏性与群体层面的低秩性同时用于因果推断的组合干预问题，也未处理由此产生的两步式误差传导。

这场报告的站位¶

讲者提出的 Synthetic Combinations 框架同时利用两重结构： 1. 稀疏性（Sparsity）：每个个体的潜在结果函数在 Fourier 基下稀疏（只有 s 个非零系数，s ≪ 2^P）。 2. 低秩性（Low-rank）：所有个体的 Fourier 系数矩阵 α ∈ ℝ^{N×2^P} 是低秩的（秩 r）。

关键推论：由于 Fourier 基是正交的，潜在结果矩阵的低秩性等价于 Fourier 系数矩阵的低秩性。因此两个假设实际上都施加在同一个潜变量矩阵 α 上：行稀疏（每行只有 s 个非零）+ 全局低秩。

与纯 Lasso/纯矩阵补全相比，Synthetic Combinations 的样本复杂度为 O(poly(r)×(N + s²p))，既消除了 N×2^P 中的乘法，又去掉了 2^P 中的指数项，逼近信息论下界 O(N + s)。这本质上是“将个体之间的低秩结构用于跨个体共享信息，同时将组合之间的稀疏结构（通过 Fourier 基）用于压缩列维度”。

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

符号设置¶

N 个用户（单位），P 个物品（干预项）。
组合 π ⊆ {1,...,P} 表示“被推荐的电影集合”。每种组合对应一个唯一的二进制向量 v(π) ∈ {–1,1}^P（取–1 表示“不在组合中”，+1 表示“在组合中”；也可用 0/1，但 ±1 使 Fourier 基正交）。
潜在结果（无特别说明指期望潜在结果）：Y_n(π) = 𝔼[Y_nπ | user n, combination π]。
观测数据：Y_nπ = 𝔼[Y_nπ] + ε_nπ，其中 ε_nπ 为零均噪声。
目标：对每个用户 n 和每种组合 π，估计 𝔼[Y_nπ] — 总共 N×2^P 个目标参数。

一个直观例子¶

P=3 部电影：{A, B, C}。一个用户 Alice 仅在意电影 A 是否在推荐集里，与 B、C 无关。那么她的期望潜在结果 𝔼[Y_Alice(π)] 只由 A 在不在决定： - 若 A∈π：𝔼[Y]= 5（高评分）；若 A∉π：𝔼[Y]= 1（低评分）。

用两种基表示的对比： - One-hot 基（指示函数）：需 2^3=8 个基向量，每个基向量对应一种具体组合。即使有如此简单的结构，8 个系数仍全部非零——例如组合 {A,B} 与 {A,C} 在 one-hot 下是不同的基，系数不同，无法体现“只有 A 起作用”这一事实。 - Fourier 基：定义基函数 χ_S(v(π))=∏{j∈S} v_j(π)，其中 S⊆{1,2,3}。该用户函数的 Fourier 表示只需一个非零系数（对应 S={1}，即只与第一个坐标有关）：𝔼[Y]=α{Alice,{1}}·χ_{{1}}(v(π)) + 常数项。所以 s=2（常数项 + 电影 A 项，严格来说零阶和一阶项），而 2^P=8。这就是稀疏性。

若我们对所有 N 个用户做类似假设——即每个用户的 Fourier 系数向量只有 s 个非零——则一旦我们知道某“重用户”（power user）在这 s 个 Fourier 系数上的值，就可以通过 Lasso 从少量观测组合中恢复其全部 2^P 个潜在结果。进而，如果用户间的 Fourier 系数矩阵 α 是低秩的（例如所有用户的 α 可以表示为少数几类“用户类型”的线性组合），那么对于“轻度用户”（只观测了少数组合），可以根据其与重用户的得分回归（PCR）来借用信息，补齐所有 2^P 个潜在结果。

因此，核心思想是：以 Fourier 基为载体，将稀疏性用于压缩列维度，将低秩性用于跨用户共享信息，两步串联实现有效估计。

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

[0:00:06–0:05:01] 问题设置与直观动机¶

讲者开篇用“推荐系统”“基因敲除”“特征选择”三个例子说明组合干预的普遍性：每个例子里，目标不是单个干预，而是同时采取多项行动（如推荐多部电影）对 Y 的效果。关键诉求是个性化：对每个用户有效估计所有 2^P 种组合的潜在结果。
实验挑战：N×2^P 场实验不可行；观测挑战：大多数组合零观测，且存在未观测混杂。

[0:05:57–0:08:02] 形式化与 Boole 函数视角¶

讲者将组合 π 编码为 Boole 向量 v(π)∈{–1,1}^P，从而将每个用户的期望潜在结果视为一个 Boole 函数。并指出 rankings 也可通过类似编码（比较对偶交换）表达为 Boole 函数，维度为 P 选 2。

[0:08:02–0:14:20] Fourier 基的引入¶

对比 One-hot 基：即使结构简单（如“只有电影 A 起作用”），One-hot 仍需 2^P 个基向量；Fourier 基只需 O(1) 个。
定义 Fourier 基函数：χ_S(v(π))=∏{j∈S} v_j(π)，对于任意 S⊆{1,...,P}。这些 χ_S 构成 2^P 维正交基。于是任一用户的期望潜在函数可写为线性组合：𝔼[Y_n(π)] = ∑{S⊆[P]} α_n,S·χ_S(v(π))。这里 α_n,S 是用户 n 对子集 S 的 Fourier 系数（潜变量）。
讲者特别点出：该表示中，用户索引 n 和组合索引 π 分离开来（类似矩阵分解中的行/列因子）。

[0:14:20–0:19:32] 稀疏性的来源与现有稀疏性方法¶

例子：k-Junta（只取决于 k<P 个物品）→ s = 2^k；低度多项式交互（如只考虑配对交互）→ s = O(P²)。
现有仅利用稀疏性的做法（Negahban & Shah ’12 的 Lasso）对每个用户独立回归，样本复杂度 O(N×s²p)。缺点：不跨用户共享信息，因此 N 仍在乘法里面。

[0:19:32–0:25:20] 低秩矩阵补全的局限¶

矩阵补全样本复杂度 O(poly(r)×(N+2^P))，问题是：多数组合（列）无观测，2^P 项导致指数依赖仍存。
核心观点：不能简单把组合视为独立列，需利用组合结构（sparsity）来降低列的有效维度。

[0:25:20–0:28:00] 双结构模型：稀疏 + 低秩¶

假设 Fourier 系数矩阵 α ∈ ℝ^{N×2^P} 同时满足：
行稀疏：每行只有 s 个非零系数；
整体低秩：rank(α) = r （从而利用用户相似性）。
由于 χ 是正交基，潜在结果矩阵的低秩等价于 α 的低秩。
讲者强调：“我们只是开始探索这种联合结构的含义，我认为这很有趣，完全可以推广到其他问题。”

[0:28:00–0:32:16] 算法：Synthetic Combinations（两步法）¶

水平回归（Horizontal regression）：对“捐赠用户（donor set）”运行 Lasso（或其它稀疏适应方法），从它们观测到的组合中学习其 Fourier 系数 α̂_u，进而填充所有 2^P 个组合的期望值。
垂直回归（Vertical regression）：对每个非捐赠用户，用主成分回归（PCR）拟合其观测到的组合结果与捐赠用户对应组合的估计结果之间的关系，利用低秩结构为其补全未观测组合。
关键难度：第一步 Lasso 的误差会作为“误差变量”（errors-in-variables）传入第二步 PCR，且这种误差是最坏情况有界误差（而非亚高斯噪声），需要专门的误差变量分析。

[0:30:14–0:33:30] 实证验证¶

使用 Sharma et al. ’19 的 Netflix 组合实验数据：800 用户，30,000 个组合（平均每组合 5 部电影），99% 缺失。
假设验证：做 SVD 显示低秩成立（少数奇异值解释大部分方差）；Lasso 得到的 Fourier 系数中仅 8.7% 非零，支持稀疏性。
性能对比：RMSE 从 Lasso 的 0.80、矩阵补全的 0.67 降至 Synthetic Combinations 的 0.55（提升约 20%）。

[0:33:30–0:37:00] 理论与识别条件¶

适用于 Lasso 的条件：① 稀疏性 s；② Fourier 特征向量的 incoherence（已观测组合在特征空间中足够“丰富”，典型 Lasso 条件）。
适用于 PCR 的条件：① 低秩 r；② 子空间包含（subspace inclusion）：非捐赠用户的观测组合的列空间被捐赠用户的列空间包含（或近似包含）。
混杂处理：假设 selection on Fourier coefficients——即处理分配仅依赖 Fourier 系数 α（而非残差 ε），这类似“选择未观测潜变量的因果矩阵补全”中的识别条件（Agarwal & Kallus 等）。
讲者指出：前两个条件可由数据诊断（易检验），第三个是未验证的因果假设。

[0:37:00–0:40:50] 样本复杂度总结与实验设计¶

样本复杂度对比表：
Lasso: O(N×s²p)
矩阵补全: O(poly(r)×(N+2^P))
Synthetic Combinations: O(poly(r)×(N + s²p))
信息论下界：O(N + s)（可进一步去除 s²p 项中的依赖；如果使用 CART 等自适应方法用于 k-Junta，可去掉 p 依赖）。
实验设计：构建一个 L 型观测模式——随机选 O(r) 个捐赠用户，对其观测 O(r²s²p) 个组合（使得 Lasso 与 Inclusion 条件以高概率成立）；对其他用户仅观测 O(r⁴) 个组合。这种按行/列不对称随机化而非均匀随机抽样的设计，是确保两步回归条件成立的关键。

[0:40:50–0:51:30] 讨论环节（Christina Yu）¶

计算可行性：Lasso 在全 2^P 的基上实施不现实。讲者回应可通过限制低度交互（truncation）、用 CART 或稀疏 Fourier 变换（sparse FFT）等技巧规避显式构造全基。
Fourier 基的泛化性：Christina 提问是否可用任意正交基替代。讲者同意这在理论上可行，只要基是正交且特征具备 incoherence，即可推广。
网络干扰的扩展：组合干预可类比为个体对邻居处理模式的函数。 Fourier 基（±1 编码）与标准的 0/1 编码低度多项式模型有细微差别（Fourier 基更侧重 parity）。讲者认为这是一个有希望建立桥梁的方向。
平衡约束 vs. 不对称设计：Christina 提出若没有“重用户”，是否可设计对称采样+联合优化（如 sparse reduced-rank regression）。讲者回应，不平衡采样（存在部分高观测用户）更有助于新用户的冷启动（只须少量观测即可通过 PCR 推演全表），而对称采样+联合稀疏低秩回归也是可行的替代。

技术技巧亮点¶

将 Boole 函数的 Fourier 分析引入因果推断的潜在结果框架，实现列维度压缩（从 2^P 到 s）。
两步法中，第一步产生最坏情况有界误差而非经典亚高斯误差，第二步的误差变量 PCR 分析需处理这种非随机噪声——这是理论上的主要难点。
在实验设计中，用行/列不对称随机化替代均匀随机条目采样，来保证 Lasso 的 incoherence 和 PCR 的子空间包含条件同时成立。

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

对应论文¶

讲者提到：arXiv 2303.14226 “Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions”，合作者：Abhineet Agarwal, Anish Agarwal, Suhas Vijaykumar。（转写中讲者将 Abhineet 称为 “Alan”，可能是 ASR 错误；幻灯片证实为 “Abhineet Agarwal”。）
讲者声称论文除有限样本一致性外，还证明了渐近正态性（asymptotic normality）条目级置信区间。

开放问题（每条可靠地扎根于转写/幻灯片某处）¶

是否可将两步法统一为联合优化？ 转写末尾 Christina 提问询问是否存在联合优化方案（[0:55:40–0:55:52]）。讲者回应 sparse reduced-rank regression 是一类现成工具，但未在本框架下具体展开。
如何处理非 Fourier 基 / 非正交基？ Christina 在 [0:52:23–0:52:40] 提问：若更换基（不一定正交），incoherence 条件如何调整。讲者认为理论上可行，但具体条件待推导。
扩展到网络干扰 [0:53:57–0:55:10]：将个体暴露视为其邻居处理模式的 Boole 函数，此时暴露模式间有结构相关性（邻居重叠导致非独立）。如何在 Fourier 基切换的 +1/–1 与标准 0/1 之间桥接，以及如何处理邻居效应的相关性，是关键问题。
平衡约束下的实验设计 [0:55:40–0:55:52]：当无法实现“重用户-轻度用户”的不对称采样时（例如每人有观测预算），是否仍有办法用更均匀抽样的方式保证两步回归的条件成立？讲者回应：联合稀疏低秩合并可能是一个路线，但不平衡采样在新用户冷启动场景有独特优势。
移除 s² 以接近下界 O(N+s)：最终样本复杂度公式中有 s² 项（来自 ℓ∞ 范数误差）。讲者在 [0:36:55–0:38:00] 指出若关心 Frobenius 范数而非 max-norm，或采用其他正则化策略，可望降为 s。

Maintained by 陈星宇 · Homepage · Source on GitHub