把几组“条件概率表”拼回一张完整联合分布表这件事听起来像数据工程师应该随手解决的问题左边拿到 (P(点击|用户))右边拿到 (P(购买|点击))还有一份 (P(购买|用户))。三条统计口径分别来自同一份业务日志按道理应该能还原出一个联合分布但工程实践里你经常发现拼出来的高维概率分布根本不存在约束之间互相打架任意两条边际都能对上整体就是不兼容。如果只是问“是否存在一个联合分布”这个问题相当古老。概率论里它叫兼容性问题Compatibility Problem也叫边际问题Marginal Problem的变体。难的地方不在于“有没有解”而在于输入条件分布的编码形式。当条件分布以完整表格形式给出时小规模实例可以化成线性规划求解器几乎可以直接回答但当条件分布是“简洁编码”的也就是说只给一段规则或程序由它现场输出每一项概率时问题的复杂度会发生剧烈变化。这篇文章想拆解的是标题里这个理论问题On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions。更准确地说我想把它翻译成做工程也能理解的复杂度问题为什么输入变短了问题反而变难为什么线性规划不是万能的以及在实际做多源概率融合、因果推断、量子关联判定时你应该在什么前提下处理兼容性。读完之后你会得到三样东西一是兼容性问题的清晰数学定义和输入规模视角二是用 Python 跑通的最小不兼容检测示例确认线性规划能做什么和不能做什么三是关于“简洁编码为什么让问题跳档”的判断力至少遇到这类问题不会被表面小输入骗住。1. 兼容性问题到底在问什么先看一个最简情况。假设有两个离散变量 (X) 和 (Y)(X) 被当作“条件方”(Y) 被当作“结果方”。我们拿到一组条件分布[ Q_1(y \mid x), \quad Q_2(x \mid y) ]问题是从数学上是否存在一个联合分布 (P(Xx, Yy))使得[ P(Yy \mid Xx)Q_1(y \mid x),\quad P(Xx \mid Yy)Q_2(x \mid y) ]如果存在我们就说这两个条件分布是兼容的。这个定义可以推广到任意多个变量、任意多组局部条件。写成更技术化的形式给定若干下标集合 (S_i, T_i) 和条件分布 (Q_i(x_{S_i}\mid x_{T_i}))问是否存在一个所有变量上的联合分布 (P)能同时生成所有这些条件分布。这里有一个新手经常误解的细节单独看每个条件分布时它们各自完全合法行和为 1、每个元素均非负看起来毫无问题。兼容性考量的不是“每个条件分布自己合不合法”而是“它们能不能来自同一个潜在联合分布”。如果没有额外约束只给一个 (Q_1(y\mid x))它永远兼容因为随便选定一个 (P(Xx))再乘上 (Q_1) 就能构造出一个合法联合分布。真正的不兼容往往出现在多个条件表互相牵制或者条件分布同一些边缘分布同时给定时。比如给定了 (P(X)) 和完整的 (P(Y\mid X))联合分布就被唯一确定但如果再给定一组来自别处的 (P(X\mid Y)) 或边缘 (P(Y))就可能没有解。这类问题的实际价值不只是数学游戏。在概率图模型结构学习中我们从数据估计出的经常是局部势函数或局部条件分布在变分推断里不同组件给出的条件分布需要能被同一个变分分布容纳在多源统计报表里不同部门提供的条件统计口径也要能被同一个业务总体解释。兼容性正是这些应用的底层前提。2. 表格式编码与简洁编码问题规模的真正分水岭讨论复杂度之前要先区分输入是按什么形式给出的。同一组条件分布可以用两种完全不同的方式交给算法。第一种是表格式explicit tabular编码。直接把每一行每一列的概率值列出来。假设变量支持集是有限的条件分布就是一堆二维表格。输入的大小和概率表元素个数成正比。如果所有变量都是二元变量共有 (m) 个变量那完整联合分布表需要 (2^m) 行如果 (m50)这个数字已经超过 (10^{15})任何显式表格都是灾难。第二种是简洁succinct编码。输入不再是完整概率表而是一个“生成器”。它可能是一段布尔电路、一个算术电路或者一段可执行程序。输入一个状态编号它输出该状态上的概率质量或未归一化权重。比如对于所有由 (m) 个 bit 组成的取值给定下面的电路规则[ W(i)1(i \bmod 3) ]输入只描述了一条简单规则但展开后的概率表有 (2^m) 行。电路本身的规模可能只是 (O(m))真正的概率空间却在以指数扩张。为什么编码方式会成为复杂度分水岭因为算法复杂度是“输入长度”的函数。在表格式输入下读入概率表本身就要花掉与展开表大小成正比的输入时间一个多项式时间的线性规划算法在这个尺度上也许是可行的。但在简洁编码下输入长度唯一可以依赖的多项式是“生成器的描述长度”而验证一个候选联合分布是否满足条件通常需要接触到指数多个联合状态中的很多项。这就造成了反直觉的现象输入越短计算可能越难。你拿到的是一个几十行的 Python 函数它背后可能代表指数规模的概率空间。试图在这种输入上精确回答“是否存在联合分布”本质上等价于在指数规模的变量空间里求解约束系统而不是在几十个输入符号上做点简单判断。完全展开的兼容性检测可以交给线性规划输入一变成简洁编码线性规划变量个数就会随展开表指数膨胀朴素的约束建模立刻失效。3. 为什么线性规划在这里会失效直接给一张概率表时兼容性问题看起来确实像线性规划可以处理的约束满足问题。我们设联合分布的每一项概率为未知数把“条件分布等于给定值”写成线性约束
把几组“条件概率表”拼回一张完整联合分布表这件事听起来像数据工程师应该随手解决的问题左边拿到 (P(点击|用户))右边拿到 (P(购买|点击))还有一份 (P(购买|用户))。三条统计口径分别来自同一份业务日志按道理应该能还原出一个联合分布但工程实践里你经常发现拼出来的高维概率分布根本不存在约束之间互相打架任意两条边际都能对上整体就是不兼容。如果只是问“是否存在一个联合分布”这个问题相当古老。概率论里它叫兼容性问题Compatibility Problem也叫边际问题Marginal Problem的变体。难的地方不在于“有没有解”而在于输入条件分布的编码形式。当条件分布以完整表格形式给出时小规模实例可以化成线性规划求解器几乎可以直接回答但当条件分布是“简洁编码”的也就是说只给一段规则或程序由它现场输出每一项概率时问题的复杂度会发生剧烈变化。这篇文章想拆解的是标题里这个理论问题On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions。更准确地说我想把它翻译成做工程也能理解的复杂度问题为什么输入变短了问题反而变难为什么线性规划不是万能的以及在实际做多源概率融合、因果推断、量子关联判定时你应该在什么前提下处理兼容性。读完之后你会得到三样东西一是兼容性问题的清晰数学定义和输入规模视角二是用 Python 跑通的最小不兼容检测示例确认线性规划能做什么和不能做什么三是关于“简洁编码为什么让问题跳档”的判断力至少遇到这类问题不会被表面小输入骗住。1. 兼容性问题到底在问什么先看一个最简情况。假设有两个离散变量 (X) 和 (Y)(X) 被当作“条件方”(Y) 被当作“结果方”。我们拿到一组条件分布[ Q_1(y \mid x), \quad Q_2(x \mid y) ]问题是从数学上是否存在一个联合分布 (P(Xx, Yy))使得[ P(Yy \mid Xx)Q_1(y \mid x),\quad P(Xx \mid Yy)Q_2(x \mid y) ]如果存在我们就说这两个条件分布是兼容的。这个定义可以推广到任意多个变量、任意多组局部条件。写成更技术化的形式给定若干下标集合 (S_i, T_i) 和条件分布 (Q_i(x_{S_i}\mid x_{T_i}))问是否存在一个所有变量上的联合分布 (P)能同时生成所有这些条件分布。这里有一个新手经常误解的细节单独看每个条件分布时它们各自完全合法行和为 1、每个元素均非负看起来毫无问题。兼容性考量的不是“每个条件分布自己合不合法”而是“它们能不能来自同一个潜在联合分布”。如果没有额外约束只给一个 (Q_1(y\mid x))它永远兼容因为随便选定一个 (P(Xx))再乘上 (Q_1) 就能构造出一个合法联合分布。真正的不兼容往往出现在多个条件表互相牵制或者条件分布同一些边缘分布同时给定时。比如给定了 (P(X)) 和完整的 (P(Y\mid X))联合分布就被唯一确定但如果再给定一组来自别处的 (P(X\mid Y)) 或边缘 (P(Y))就可能没有解。这类问题的实际价值不只是数学游戏。在概率图模型结构学习中我们从数据估计出的经常是局部势函数或局部条件分布在变分推断里不同组件给出的条件分布需要能被同一个变分分布容纳在多源统计报表里不同部门提供的条件统计口径也要能被同一个业务总体解释。兼容性正是这些应用的底层前提。2. 表格式编码与简洁编码问题规模的真正分水岭讨论复杂度之前要先区分输入是按什么形式给出的。同一组条件分布可以用两种完全不同的方式交给算法。第一种是表格式explicit tabular编码。直接把每一行每一列的概率值列出来。假设变量支持集是有限的条件分布就是一堆二维表格。输入的大小和概率表元素个数成正比。如果所有变量都是二元变量共有 (m) 个变量那完整联合分布表需要 (2^m) 行如果 (m50)这个数字已经超过 (10^{15})任何显式表格都是灾难。第二种是简洁succinct编码。输入不再是完整概率表而是一个“生成器”。它可能是一段布尔电路、一个算术电路或者一段可执行程序。输入一个状态编号它输出该状态上的概率质量或未归一化权重。比如对于所有由 (m) 个 bit 组成的取值给定下面的电路规则[ W(i)1(i \bmod 3) ]输入只描述了一条简单规则但展开后的概率表有 (2^m) 行。电路本身的规模可能只是 (O(m))真正的概率空间却在以指数扩张。为什么编码方式会成为复杂度分水岭因为算法复杂度是“输入长度”的函数。在表格式输入下读入概率表本身就要花掉与展开表大小成正比的输入时间一个多项式时间的线性规划算法在这个尺度上也许是可行的。但在简洁编码下输入长度唯一可以依赖的多项式是“生成器的描述长度”而验证一个候选联合分布是否满足条件通常需要接触到指数多个联合状态中的很多项。这就造成了反直觉的现象输入越短计算可能越难。你拿到的是一个几十行的 Python 函数它背后可能代表指数规模的概率空间。试图在这种输入上精确回答“是否存在联合分布”本质上等价于在指数规模的变量空间里求解约束系统而不是在几十个输入符号上做点简单判断。完全展开的兼容性检测可以交给线性规划输入一变成简洁编码线性规划变量个数就会随展开表指数膨胀朴素的约束建模立刻失效。3. 为什么线性规划在这里会失效直接给一张概率表时兼容性问题看起来确实像线性规划可以处理的约束满足问题。我们设联合分布的每一项概率为未知数把“条件分布等于给定值”写成线性约束
