A framework for structural risk minimisation
John S. Shawe-Taylor, Peter L. Bartlett, Robert C. Williamson, Martin Anthony · 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...