On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions

The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning.

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…