We study online algorithms for selective sampling that use regularized least squares (RLS) as base classifier. These algorithms typically perform well in practice, and some of them have formal guarantees on their mistake and query rates. We refine and extend these guarantees in various ways, proposing algorithmic variants that exhibit better empirical behavior while enjoying performance guarantees under much more general conditions. We also show a simple way of coupling a generic gradient-based classifier with a specific RLS-based selective sampler, obtaining hybrid algorithms with combined performance guarantees. Copyright 2011 by the author(s)/owner(s).

Better algorithms for selective sampling / F. Orabona, N. Cesa-Bianchi - In: Proceedings of the 28th international conference on machine learning : Bellevue, Washington, USA, june 28.july 2, 2011 / [a cura di] L. Getoor, T. Schaffer. - Madison : Omnipress, 2011. - ISBN 97814503-06195. - pp. 433-440 (( Intervento presentato al 28. convegno International Conference on Machine Learning tenutosi a Bellevue, WA, USA nel 2011.

Better algorithms for selective sampling

N. Cesa-Bianchi
Ultimo
2011

Abstract

We study online algorithms for selective sampling that use regularized least squares (RLS) as base classifier. These algorithms typically perform well in practice, and some of them have formal guarantees on their mistake and query rates. We refine and extend these guarantees in various ways, proposing algorithmic variants that exhibit better empirical behavior while enjoying performance guarantees under much more general conditions. We also show a simple way of coupling a generic gradient-based classifier with a specific RLS-based selective sampler, obtaining hybrid algorithms with combined performance guarantees. Copyright 2011 by the author(s)/owner(s).
Settore INF/01 - Informatica
   Pattern Analysis, Statistical Modelling and Computational Learning 2
   PASCAL2
   EUROPEAN COMMISSION
   FP7
   216886
2011
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
11icml_b.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 536.29 kB
Formato Adobe PDF
536.29 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/2434/160348
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 35
  • ???jsp.display-item.citation.isi??? ND
social impact