Linking Learning Strategies and Performance for Support Vector Machines

摘要

We developed a formal representation of the technique introduced in (Shawe-Taylor, Bartlett, Williamson, & Anthony, 1998$ Shawe-Taylor & Cristianini, 1998) for bounding the generalization error of support vector machines. As a consequence we provide a framework that can be utilized to link learning strategies to their performance bounds in such a way that the bounds are expressed in terms of the structural properties of the learning strategy (e.g. characterizations of the optimum classifier in terms of the structure of the finite sample optimization criterion and its value at optimum). We use this framework to provide performance bounds for a class of support vector machines that includes the soft margin learning strategies commonly used in practice. We also show how to eliminate the effects of the center and scale of the data in the learning theorem. We apply this framework to improve results obtained in (Shawe-Taylor & Cristianini 1998) for the 2-norm soft margin learning strategy by exploiting a relationship between covering numbers of classes of linear functions and covering numbers of linear operators. This result is expressed in terms of the finite sample criterion value at optimum. Finally we show this bound can be expressed in terms of the random process.