We develop a formal representation of the technique introduced in (Shawe-Taylor, Bartlett, Williamson and Anthony, 1998), (Shawe-Taylor and 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 and 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 how this bound can be expressed in terms of the random process.
J. Howse, D. Hush, and C. Scovel, Linking learning strategies and performance for support vector machines. Los Alamos National Laboratory Technical Report LA-UR-02-1933, 2002. [ Abstract | PostScript (474 KB) | PDF (477 KB) ]
