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. 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.
@inproceedings{ DBLP:conf/nips/GraepelHW00,
abstract = {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.},
address = {Denver},
author = {Graepel, Thore and Herbrich, Ralf and Williamson, Robert C},
booktitle = {Advances in Neural Information Processing Systems 13},
file = {:Users/rherb/Dropbox/Documents/tex/nips2000/sparsity/perc.pdf:pdf},
pages = {210--216},
publisher = {The MIT Press},
title = {{From Margin to Sparsity}},
url = {http://www.herbrich.me/papers/perc.pdf},
year = {2000}
}
Downloads: 0
{"_id":{"_str":"53421b61ecd21cdc070003fc"},"__v":2,"authorIDs":["5456e9a38b01c8193000005e"],"author_short":["Graepel, T.","Herbrich, R.","Williamson","C, R."],"bibbaseid":"graepel-herbrich-williamson-c-frommargintosparsity-2000","bibdata":{"abstract":"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.","address":"Denver","author":["Graepel, Thore","Herbrich, Ralf","Williamson","C, Robert"],"author_short":["Graepel, T.","Herbrich, R.","Williamson","C, R."],"bibtex":"@inproceedings{ DBLP:conf/nips/GraepelHW00,\n abstract = {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.},\n address = {Denver},\n author = {Graepel, Thore and Herbrich, Ralf and Williamson, Robert C},\n booktitle = {Advances in Neural Information Processing Systems 13},\n file = {:Users/rherb/Dropbox/Documents/tex/nips2000/sparsity/perc.pdf:pdf},\n pages = {210--216},\n publisher = {The MIT Press},\n title = {{From Margin to Sparsity}},\n url = {http://www.herbrich.me/papers/perc.pdf},\n year = {2000}\n}","bibtype":"inproceedings","booktitle":"Advances in Neural Information Processing Systems 13","file":":Users/rherb/Dropbox/Documents/tex/nips2000/sparsity/perc.pdf:pdf","id":"DBLP:conf/nips/GraepelHW00","key":"DBLP:conf/nips/GraepelHW00","pages":"210--216","publisher":"The MIT Press","title":"From Margin to Sparsity","type":"inproceedings","url":"http://www.herbrich.me/papers/perc.pdf","year":"2000","bibbaseid":"graepel-herbrich-williamson-c-frommargintosparsity-2000","role":"author","urls":{"Paper":"http://www.herbrich.me/papers/perc.pdf"},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://herbrich.me/bib/herbrich.bib","downloads":0,"keywords":[],"search_terms":["margin","sparsity","graepel","herbrich","williamson","c"],"title":"From Margin to Sparsity","year":2000,"dataSources":["y2DvMgAcqeDpXQ6ds"]}