Polynomial Learnability of Probabilistic Concepts with Respect to the Kullback-Leibler Divergence

Abstract

We consider the problem of efficient learning of probabilistic concepts (p-concepts), in the sense defined by Kearns and Schapire [KS90] and by Yamanishi [Yam90]. Their models extend the PAC-learning model of Valiant [Val84] to the learning scenario in which the target concept or function is stochastic rather than deterministic as in Valiant's original model. In this paper, we consider the learnability for p-concepts with respect to the classic ‘Kullback-Leibler divergence’ (KL divergence) as the distance measure between p-concepts. First, we show that the notion of polynomial time learnability of p-concepts using the KL divergence is in fact equivalent to the same notion using any of the distances considered in [KS90] and [Yam90], the quadratic, variation, and Hellinger distances. As a corollary, it follows that a wide range of classes of p-concepts which were shown to be polynomially learnable with respect to the quadratic distance in [KS90] are also learnable with respect to the KL divergence. The sample and time complexity of algorithms that would be obtained by the above general equivalence, however, are far from optimal. We present a polynomial learning algorithm with a reasonable sample complexity for the important class of convex linear combinations of p-concepts. We also develop simple and versatile techniques for obtaining sample complexity bounds for learning classes of p-concepts with respect to the KL-divergence and quadratic distance, and apply them to produce bounds for the classes of probabilistic finite state acceptors (automata), probabilistic decision lists, and linear combinations.