Search papers, labs, and topics across Lattice.
This paper investigates the complexity of the compatibility problem for succinctly encoded conditional distributions, focusing on the trade-offs in probabilistic models used for predictions. It establishes that, when conditional distributions are represented as arithmetic circuits, determining the existence of a compatible joint distribution is intractable, with the problem being co-NP-complete for non-zero probabilities and PSPACE-complete in other cases. The findings highlight significant limitations in high-dimensional probabilistic modeling, particularly in the context of neural networks, where succinct representations may not yield compatible joint distributions.
Compatibility of succinctly encoded conditional distributions is intractable, revealing critical limitations for high-dimensional probabilistic models.
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.
