Concept learning using complexity regularization
Gábor Lugosi, K. Zeger · IEEE Transactions on Information Theory · 1996
In pattern recognition or, as it has also been called, concept learning, the value of a { 0,1}-valued random variable Y is to be predicted based upon observing an R/sup d/-valued random variable X. We apply the method of complexity regularization to learn concepts from large concept classes. The method is shown to automatically find a good balance between the approximation error and the estimation error. In particular, the error probability of the obtained classifier is shown to decrease as O(/spl radic/(logn/n)) to the achievable optimum, for large nonparametric classes of distributions, as the sample size n grows. We also show that if the Bayes error probability is zero and the Bayes rule is in a known family of decision rules, the error probability is O(logn/n) for many large families, possibly with infinite VC dimension.
Cited by 66 works. doi:10.1109/18.481777
Authors
References
- A new look at the statistical model identification
- Estimating the Dimension of a Model
- A Theory of the Learnable
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- A theory of the learnable
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Learnability and the Vapnik-Chervonenkis dimension
- A Universal Prior for Integers and Estimation by Minimum Description Length
- Universal coding, information, prediction, and estimation
- Predicting (0, 1)-functions on randomly drawn points