Polynomial Learnability of Stochastic Rules with Respect to the KL-Divergence and Quadratic Distance-猫眼课题宝

随机规则关于 KL 散度和二次距离的多项式可学习性

DOI：

发表时间：

2001

期刊：

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

N. Abe;J. Takeuchi;Manfred K. Warmuth

我们考虑概率概念(p-概念)和更一般的随机规则的有效学习问题，这些规则是由Kearns和Schaplire[6]以及Yamanishi[18]定义的。他们的模型将Valiant的PAC学习模型[16]扩展到目标概念或函数是随机的而不是Valiant原始模型中的确定性的学习场景。在本文中，我们考虑了随机规则相对于经典的Kullback-Leibler发散(KL发散)的可学习性，以及规则之间的二次距离作为距离度量。首先，我们证明了使用KL散度的p-概念和具有固定范围大小的随机规则的多项式时间可学习性的概念实际上等价于使用二次距离的相同概念，从而得到了[6]和[18]中考虑的任何距离：二次距离、变差距离和Hellinger距离。作为推论，在[6]中被证明是关于二次距离的多项式可学习的大范围的p-概念类也关于KL散度是可学习的。然而，通过上述一般等价所获得的算法的样本和时间复杂度远远不是最优的。针对一类重要的凸线性随机规则组合，提出了一种具有合理样本和时间复杂度的多项式学习算法。我们还发展了一种简单而通用的技术来获得关于KL-散度和二次距离的随机规则学习类的样本复杂性界，并将它们应用于产生概率有限状态接受器(自动机)类、概率决策列表和凸线性组合的界。关键词：PAC-学习，KL-发散，二次距离，随机规则，p-概念

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 [6] and by Yamanishi [18]. Their models extend the PAC-learning model of Valiant [16] 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. key words: PAC-learning, KL-divergence, quadratic-distance, stochastic rules, p-concepts

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

随机规则关于 KL 散度和二次距离的多项式可学习性

文献摘要

被引文献

相似文献