On the Sample Complexity of Consistent Learning with One-Sided Error

概要

論文の詳細を見る
Although consistent learning is sufficient for PAC-learning, it has not been found what strategy makes learning more efficient, especially on the sample complexity, i.e., the number of examples required. For the first step towards this problem, classes that have consistent learning algorithms with one-sided error are considered. A combinatorial quantity called maximal particle sets is introduced, and an upper bound of the sample complexity of consistent learning with one-sided error is obtained in terms of maximal particle sets. For the class of n-dimensional axis-parallel rectangles, one of those classes that are consistently learnable with one-sided error, the cardinality of the maximal particle set is estimated and O(d/ε+1/εlog 1/δ) upper bound of the learning algorithm for the class is obtained. This bound improves the bounds due to Blumer et al. [2] and meets the lower bound within a constant factor.
社団法人電子情報通信学会の論文
1995-05-25