Learning Non-parametric Densities in terms of Finite-Dimensional Parametric Hypotheses

Kenji YAMANISHI

Summary :

This paper proposes a model for learning non-parametric densities using finite-dimensional parametric densities by applying Yamanishi's stochastic analogue of Valiant's probably approximately correct learning model to density estimation. The goal of our learning model is to find, with high probability, a good parametric approximation of the non-parametric target density with sample size and computation time polynomial in parameters of interest. We use a learning algorithm based on the minimum description length (MDL) principle and derive a new general upper bound on the rate of convergence of the MDL estimator to a true non-parametric density. On the basis of this result, we demonstrate polynomial-sample-size learnability of classes of non-parametric densities (defined under some smoothness conditions) in terms of exponential families with polynomial bases, and we prove that under some appropriate conditions, the sample complexity of learning them is bounded as O((1/ε)^(2r1)/2r1n^(2r1)/2r(1/ε)(1/ε)1n(1/δ) for a smoothness parameter r (a positive integer), where ε and δ are respectively accuracy and confidence parameters. Futher, we demonstrate polynomial-time learnability of classes of non-parametric densities (defined under some smoothness conditions) in terms of histogram densities with equal-length cells, and we prove that under some appropriate condition, the sample complexity of learning them is bounded as O((1/ε)^3/21n^3/2(1/ε)(1/ε)1n(1/δ)).

• Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.4 pp.459-469
• Publication Date: 1992/07/25
• Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)

Authors

Kenji YAMANISHI

Keyword

learning from examples,  MDL principle,  non-parametric density estimation,  histogram densities,  exponential families