Polynomial Learnability of Stochastic Rules with Respect to the KL-Divergence and Quadratic Distance

Naoki ABE; Jun-ichi TAKEUCHI; Manfred K. WARMUTH

Polynomial Learnability of Stochastic Rules with Respect to the KL-Divergence and Quadratic Distance

Naoki ABE, Jun-ichi TAKEUCHI, Manfred K. WARMUTH

Full Text Views

0

Cite this

Summary :

We consider the problem of efficient learning of probabilistic concepts (p-concepts) and more generally stochastic rules in the sense defined by Kearns and Schapire and by Yamanishi. Their models extend the PAC-learning model of Valiant 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 of stochastic rules with respect to the classic 'Kullback-Leibler divergence' (KL divergence) as well as the quadratic distance as the distance measure between the rules. First, we show that the notion of polynomial time learnability of p-concepts and stochastic rules with fixed range size using the KL divergence is in fact equivalent to the same notion using the quadratic distance, and hence any of the distances considered in [6] and [18]: 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 [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 time complexity for the important class of convex linear combinations of stochastic rules. We also develop a simple and versatile technique for obtaining sample complexity bounds for learning classes of stochastic rules 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 convex linear combinations.

Publication: IEICE TRANSACTIONS on Information Vol.E84-D No.3 pp.299-316

Publication Date: 2001/03/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Theory of Automata, Formal Language Theory

Cite this

Copy

Naoki ABE, Jun-ichi TAKEUCHI, Manfred K. WARMUTH, "Polynomial Learnability of Stochastic Rules with Respect to the KL-Divergence and Quadratic Distance" in IEICE TRANSACTIONS on Information, vol. E84-D, no. 3, pp. 299-316, March 2001, doi: .
Abstract: We consider the problem of efficient learning of probabilistic concepts (p-concepts) and more generally stochastic rules in the sense defined by Kearns and Schapire and by Yamanishi. Their models extend the PAC-learning model of Valiant 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 of stochastic rules with respect to the classic 'Kullback-Leibler divergence' (KL divergence) as well as the quadratic distance as the distance measure between the rules. First, we show that the notion of polynomial time learnability of p-concepts and stochastic rules with fixed range size using the KL divergence is in fact equivalent to the same notion using the quadratic distance, and hence any of the distances considered in [6] and [18]: 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 [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 time complexity for the important class of convex linear combinations of stochastic rules. We also develop a simple and versatile technique for obtaining sample complexity bounds for learning classes of stochastic rules 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 convex linear combinations.
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_3_299/_p

Copy

@ARTICLE{e84-d_3_299,
author={Naoki ABE, Jun-ichi TAKEUCHI, Manfred K. WARMUTH, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial Learnability of Stochastic Rules with Respect to the KL-Divergence and Quadratic Distance},
year={2001},
volume={E84-D},
number={3},
pages={299-316},
abstract={We consider the problem of efficient learning of probabilistic concepts (p-concepts) and more generally stochastic rules in the sense defined by Kearns and Schapire and by Yamanishi. Their models extend the PAC-learning model of Valiant 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 of stochastic rules with respect to the classic 'Kullback-Leibler divergence' (KL divergence) as well as the quadratic distance as the distance measure between the rules. First, we show that the notion of polynomial time learnability of p-concepts and stochastic rules with fixed range size using the KL divergence is in fact equivalent to the same notion using the quadratic distance, and hence any of the distances considered in [6] and [18]: 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 [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 time complexity for the important class of convex linear combinations of stochastic rules. We also develop a simple and versatile technique for obtaining sample complexity bounds for learning classes of stochastic rules 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 convex linear combinations.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Polynomial Learnability of Stochastic Rules with Respect to the KL-Divergence and Quadratic Distance
T2 - IEICE TRANSACTIONS on Information
SP - 299
EP - 316
AU - Naoki ABE
AU - Jun-ichi TAKEUCHI
AU - Manfred K. WARMUTH
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2001
AB - We consider the problem of efficient learning of probabilistic concepts (p-concepts) and more generally stochastic rules in the sense defined by Kearns and Schapire and by Yamanishi. Their models extend the PAC-learning model of Valiant 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 of stochastic rules with respect to the classic 'Kullback-Leibler divergence' (KL divergence) as well as the quadratic distance as the distance measure between the rules. First, we show that the notion of polynomial time learnability of p-concepts and stochastic rules with fixed range size using the KL divergence is in fact equivalent to the same notion using the quadratic distance, and hence any of the distances considered in [6] and [18]: 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 [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 time complexity for the important class of convex linear combinations of stochastic rules. We also develop a simple and versatile technique for obtaining sample complexity bounds for learning classes of stochastic rules 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 convex linear combinations.
ER -