The minimum L-complexity algorithm and its applications to learning non-parametric rules

ABSTRACT

This paper proposes the minimum L-complexity algorithm (MLC), which can be thought of as an extension of the minimum description length (MDL) principle-based algorithm to the case where general real-valued functions are used as hypotheses and general loss functions are used as distortion measures. MLC is also closely related to Barron's complexity regularization algorithm and Vapnik's structural risk minimization. We demonstrate the effectiveness of MLC in terms of sample complexity within the decision theoretic PAC learning model. Specifically using MLC, we develop a unifying method of deriving upper bounds on target-dependent (non-uniform) sample complexity both for parametric and non-parametric settings. We further introduce a method for evaluating average-case sample complexity where the average is taken with respect to a prior probability over the parametric target class. These target-dependent and average-case sample complexity bounds offer a new view of sample complexity analysis, while most of previous work focusing on the worst-case sample complexity. As applications of MLC, we consider the issues of learning and non-parametric rules in terms of 1) stochastic rules with finite partitioning, 2) finite Hermite series, and 3) finite Fourier series. We use MLC to improve the previously-known best results on sample complexity for these issues.

REFERENCES

• 1: Naoki Abe , Manfred K. Warmuth, On the Computational Complexity of Approximating Distributions by Probabilistic Automata, Machine Learning, v.9 n.2-3, p.205-260, July 1992 [doi>10.1007/BF00992677]
• 2: Barron, A.R.(1991). Complexity regularization with application to artificial neural networks. Nonparametric Functional Estimation and Related Topics, G.Roussas ed., 561-576, Kluwer Academic Publishers.
• 3: Barron, A.R. and Cover T.M.(1991). Minimum complexity density estimation. IEEE Trans. Inform. Theory, IT-37:1034-1054.
• 4: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• 5: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 6: Greblicki, W.(1981). Asymptotic efficiency of classifying procedures using the Itermite series estimate of multivariate probability densities. IEEE Trans. Inform. Theory, IT-27:364-366.
• 7: Greblicki, W. and Pawlak, M.(1981). Classification using the Fourier series estimate of multivariate density functions. IEEE Trans. Syst., Man, Cybern., SMC- 11:726-730.
• 8: David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
• 9: David Haussler , Michael Kearns , Robert Schapire, Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension, Proceedings of the fourth annual workshop on Computational learning theory, p.61-74, August 05-07, 1991, Santa Cruz, California, United States
• 10: Kearns, M. and Schapire, R.(1990). Efficient distribution free learning of probabilistic concepts. Proc. FOCS- 90, (pp. 382-391).
• 11: Rissanen, J.(1978). Modeling by shortest data description. Automatics, Li, 465-471.
• 12: Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 13: Schwarz, S.C.(1967). Estimation of probability density by an orthogonal series. Ann. Stat., 5:1258-1264.
• 14: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 15: Van Ryzin, J.(1966). Bayes risk consistency of classification procedures using density estimates. Sankhya, A, 28:161-170.
• 16: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 17: Wahba, G.(1975). Optimal convergence properties of variable knot, kernel, and orthogonal series methods for density estimation. Ann. Stat., 3:15-29.
• 18: Waiter, G.G.(1977). Properties of Hermite series estimation of probability density. Ann. Stat., 5:1258-1264.
• 19: Kenji Yamanishi, A Learning Criterion for Stochastic Rules, Machine Learning, v.9 n.2-3, p.165-203, July 1992 [doi>10.1007/BF00992676]
• 20: Kenji Yamanishi, Learning non-parametric smooth rules by stochastic rules with finite partitioning, Proceedings of the first European conference on Computational learning theory, p.217-227, October 1994, Royal Holloway, Univ. of London, United Kingdom

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification