A framework for structural risk minimisation
John S. Shawe-Taylor, Peter L. Bartlett, Robert C. Williamson et al. · Annual Conference on Computational Learning Theory (COLT) · 1996
The paper introduces a framework for studying structural risk minimisation. The model views structural risk minimisation in a PAC context. It then considers the more general case when the hierarchy of classes is chosen in response to the data. This theoretically explains the impressive performance of the maximal margin hyperplane algorithm of Vapnik. It may also provide a general technique for exploitingserendipitous simplicity in observed data to obtain better prediction accuracy from small training sets. 1 Introduction The standard PAC model of learning considers a fixed hypothesis class H together with a required accuracy ffl and confidence 1 \\Gamma ffi . The theory characterises when a target function from H can be learned from examples in terms of the Vapnik-Chervonenkis dimension, a measure of the flexibility of the class H and specifies sample sizes required to deliver the required accuracy with the allowed confidence. In many cases of practical interest the precise class conta...
Cited by 79 works. doi:10.1145/238061.238070
Authors
References
- The Nature of Statistical Learning Theory
- Support-Vector Networks
- A training algorithm for optimal margin classifiers
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Estimation of Dependences Based on Empirical Data
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Convergence of Stochastic Processes.
- Scale-sensitive dimensions, uniform convergence, and learnability
- A result of Vapnik with applications
- Results on learnability and the Vapnik-Chervonenkis dimension