Combinatorial Characterizations of the Learnability of Conditional Distributions
The PAC-learnability of function classes that map inputs to probability distributions over a finite space is studied, and it is shown that a distribution-valued function class is learnable if and only if each of its coordinate classes is learnable in the probabilistic concept model.