研究机器学习概率模型中兼容性问题的计算复杂性
原文：On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions
本文的动机是探究机器学习中概率模型所隐含的权衡。模型常被用于以条件概率的形式进行预测。然而，一对条件分布 p(x|y) 与 p(y|x) 可能与任何联合分布 p(x,y) 都不兼容。给定两个这样的条件分布，判断是否存在兼容的联合分布，被称为兼容性问题。对于离散随机变量，当条件分布以概率表编码时，兼容性问题已有已知解法，且在计算上是可处理的。本文形式化并研究了该问题的一个简洁版本，即将条件分布编码为算术电路。这适用于高维场景下概率建模的实际应用，包括神经网络模型。我们证明，对于条件分布的简洁电路表示，兼容性问题是难解的。在所有概率均非零的情形下，该问题是 co-NP-完全的。在概率可为零的情形下，我们给出示例表明若干兼容性概念可以区分开来，并证明该问题的多个版本是 PSPACE-完全的。此外，我们证明，在多项式层级不塌缩的假设下，存在兼容的简洁条件分布，其联合分布无法被简洁表达。我们还讨论了这些结果对概率建模和机器学习的启示。作者：Guy Emerson 分类：cs.LG,cs.CC,math.PR