From Margin to Sparsity. Graepel, T., Herbrich, R., Williamson, & C, R. In Advances in Neural Information Processing Systems 13, pages 210--216, Denver, 2000. The MIT Press.
From Margin to Sparsity [pdf]Paper  abstract   bibtex   
We present an improvement of Novikoff's perceptron convergence theorem. Reinterpreting this mistake bound as a margin dependent sparsity guarantee allows us to give a PAC-style generalisation error bound for the classifier learned by the dual perceptron learning algorithm. The bound value crucially depends on the margin a support vector machine would achieve on the same data set using the same kernel. Ironically, the bound yields better guarantees than are currently available for the support vector solution itself.

Downloads: 0