From margin to sparsity

Thore Graepel; Ralf Herbrich; Robert C. Williamson

From margin to sparsity

Thore Graepel, Ralf Herbrich, Robert C. Williamson

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

32 Citations (Scopus)

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 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.

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 13 - Proceedings of the 2000 Conference, NIPS 2000
Publisher	Neural Information Processing Systems Foundation
ISBN (Print)	0262122413, 9780262122412
Publication status	Published - 2001
Event	14th Annual Neural Information Processing Systems Conference, NIPS 2000 - Denver, CO, United States Duration: 27 Nov 2000 → 2 Dec 2000

Publication series

Name	Advances in Neural Information Processing Systems
ISSN (Print)	1049-5258

Conference

Conference	14th Annual Neural Information Processing Systems Conference, NIPS 2000
Country/Territory	United States
City	Denver, CO
Period	27/11/00 → 2/12/00

Cite this

@inproceedings{6e61231a3dec44e98e24654298f09052,

title = "From margin to sparsity",

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 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.",

author = "Thore Graepel and Ralf Herbrich and Williamson, \{Robert C.\}",

year = "2001",

language = "English",

isbn = "0262122413",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural Information Processing Systems Foundation",

booktitle = "Advances in Neural Information Processing Systems 13 - Proceedings of the 2000 Conference, NIPS 2000",

note = "14th Annual Neural Information Processing Systems Conference, NIPS 2000 ; Conference date: 27-11-2000 Through 02-12-2000",

}

Graepel, T, Herbrich, R & Williamson, RC 2001, From margin to sparsity. in Advances in Neural Information Processing Systems 13 - Proceedings of the 2000 Conference, NIPS 2000. Advances in Neural Information Processing Systems, Neural Information Processing Systems Foundation, 14th Annual Neural Information Processing Systems Conference, NIPS 2000, Denver, CO, United States, 27/11/00.

From margin to sparsity. / Graepel, Thore; Herbrich, Ralf; Williamson, Robert C.
Advances in Neural Information Processing Systems 13 - Proceedings of the 2000 Conference, NIPS 2000. Neural Information Processing Systems Foundation, 2001. (Advances in Neural Information Processing Systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

TY - GEN

T1 - From margin to sparsity

AU - Graepel, Thore

AU - Herbrich, Ralf

AU - Williamson, Robert C.

PY - 2001

Y1 - 2001

N2 - 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 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.

AB - 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 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.

UR - https://www.scopus.com/pages/publications/84898991622

M3 - Conference Paper

SN - 0262122413

SN - 9780262122412

T3 - Advances in Neural Information Processing Systems

BT - Advances in Neural Information Processing Systems 13 - Proceedings of the 2000 Conference, NIPS 2000

PB - Neural Information Processing Systems Foundation

T2 - 14th Annual Neural Information Processing Systems Conference, NIPS 2000

Y2 - 27 November 2000 through 2 December 2000

ER -

From margin to sparsity

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this