AI summaryⓘ
The authors study a problem in machine learning about whether two conditional probability models, like probabilities of x given y and y given x, can come from a common overall joint probability. For simple cases with small sets, this problem is solvable efficiently. But they show that when these probability models are represented in a compact way (with arithmetic circuits) often used in high-dimensional or neural network settings, the problem becomes very hard to solve (intractable). They also explore different versions of this problem depending on whether zero probabilities are allowed and find that some are even tougher (PSPACE-complete). The authors discuss how these results impact building and understanding probabilistic models in machine learning.
conditional probabilityjoint distributioncompatibility problemarithmetic circuitsprobabilistic modelingNP-completePSPACE-completepolynomial hierarchymachine learningneural networks
Abstract
The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.