Polynomial learnability of stochastic rules with respect to the KL-divergence and quadratic distance

We consider the problem of efficient learning of probabilistic concepts (p- concepts) and more generally stochastic rules in the sense defined by Kearn s and Schapire [6] and by Yamanishi [18]. Their models extend the PAC-learn ing model of Valiant [16] to the learning scenario in which the target conc ept or function is stochastic rather than deterministic as in Valiant's ori ginal model. In this paper, we consider the learnability of stochastic rule s with respect to the classic 'Kullback-Leibler divergence' (KL divergence) as well as the quadratic distance as the distance measure between the rule s. First, we show that the notion of polynomial time learnability of p-conc epts and stochastic rules with fixed range sire using the KL divergence is in fact equivalent to the same notion using the quadratic distance, and hen ce any of the distances considered in [6] and [18]: the quadratic, variatio n, and Kellinger distances. As a corollary, it follows that a wide range of classes of p-concepts which were shown to be polynomially learnable with r espect to the quadratic distance in [6] 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 reasonable sample and tim e complexity far the important class of convex linear combinations of stoch astic rules. We also develop a simple and versatile technique for obtaining sample complexity bounds for learning classes of stochastic rules with res pect to the KL-divergence and quadratic distance, and apply them to produce bounds for the classes of probabilistic finite state accepters (automata), probabilistic decision lists, and convex linear combinations.