We introduce a variant of the perceptron algorithm called second-order perceptron algorithm, which is able to exploit certain spectral properties of the data. We analyze the second-order perceptron algorithm in the mistake bound model of on-line learning and prove bounds in terms of the eigenvalues of the Gram matrix created from the data. The performance of the second-order perceptron algorithm is affected by the setting of a parameter controlling the sensitivity to the distribution of the eigenvalues of the Gram matrix. Since this information is not preliminarly available to on-line algorithms, we also design a refined version of the second-order perceptron algorithm which adaptively sets the value of this parameter. For this second algorithm we are able to prove mistake bounds corresponding to a nearly optimal constant setting of the parameter.

A second-order Perceptron algorithm

GENTILE, CLAUDIO
2002-01-01

Abstract

We introduce a variant of the perceptron algorithm called second-order perceptron algorithm, which is able to exploit certain spectral properties of the data. We analyze the second-order perceptron algorithm in the mistake bound model of on-line learning and prove bounds in terms of the eigenvalues of the Gram matrix created from the data. The performance of the second-order perceptron algorithm is affected by the setting of a parameter controlling the sensitivity to the distribution of the eigenvalues of the Gram matrix. Since this information is not preliminarly available to on-line algorithms, we also design a refined version of the second-order perceptron algorithm which adaptively sets the value of this parameter. For this second algorithm we are able to prove mistake bounds corresponding to a nearly optimal constant setting of the parameter.
2002
Kivinen, J.; Sloan, R.H.
Computational Learning Theory. 15th Annual Conference on Computational Learning Theory, COLT 2002. Proceedings
354043836X
15th Annual Conference on Computational Learning Theory, COLT 2002
Sydney, Australia
July 8-10, 2002
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/1773979
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? ND
social impact