We study exact active learning of binary and multiclass classifiers with margin. Given an n-point set X⊂Rm, we want to learn an unknown classifier on X whose classes have finite strong convex hull margin, a new notion extending the SVM margin. In the standard active learning setting, where only label queries are allowed, learning a classifier with strong convex hull margin γ requires in the worst case Ω(1+1γ)m−12 queries. On the other hand, using the more powerful \emph{seed} queries (a variant of equivalence queries), the target classifier could be learned in O(mlogn) queries via Littlestone's Halving algorithm; however, Halving is computationally inefficient. In this work we show that, by carefully combining the two types of queries, a binary classifier can be learned in time poly(n+m) using only O(m2logn) label queries and O(mlogmγ) seed queries; the result extends to k-class classifiers at the price of a k!k2 multiplicative overhead. Similar results hold when the input points have bounded bit complexity, or when only one class has strong convex hull margin against the rest. We complement the upper bounds by showing that in the worst case any algorithm needs Ω(kmlog1γ) seed and label queries to learn a k-class classifier with strong convex hull margin γ.
Active Learning of Classifiers with Label and Seed Queries / M. Bressan, N. Cesa Bianchi, S. Lattanzi, A. Paudice, M. Thiessen (ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS). - In: NeurIPS / [a cura di] S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh. - [s.l] : Curran Associates, 2022. - ISBN 9781713871088. - pp. 30911-30922 (( Intervento presentato al 36. convegno Conference on Neural Information Processing Systems : Monday November 28th through Friday December 9th tenutosi a New Orleans nel 2022.
Active Learning of Classifiers with Label and Seed Queries
M. BressanPrimo
;N. Cesa BianchiSecondo
;A. PaudicePenultimo
;
2022
Abstract
We study exact active learning of binary and multiclass classifiers with margin. Given an n-point set X⊂Rm, we want to learn an unknown classifier on X whose classes have finite strong convex hull margin, a new notion extending the SVM margin. In the standard active learning setting, where only label queries are allowed, learning a classifier with strong convex hull margin γ requires in the worst case Ω(1+1γ)m−12 queries. On the other hand, using the more powerful \emph{seed} queries (a variant of equivalence queries), the target classifier could be learned in O(mlogn) queries via Littlestone's Halving algorithm; however, Halving is computationally inefficient. In this work we show that, by carefully combining the two types of queries, a binary classifier can be learned in time poly(n+m) using only O(m2logn) label queries and O(mlogmγ) seed queries; the result extends to k-class classifiers at the price of a k!k2 multiplicative overhead. Similar results hold when the input points have bounded bit complexity, or when only one class has strong convex hull margin against the rest. We complement the upper bounds by showing that in the worst case any algorithm needs Ω(kmlog1γ) seed and label queries to learn a k-class classifier with strong convex hull margin γ.File | Dimensione | Formato | |
---|---|---|---|
NeurIPS-2022-active-learning-of-classifiers-with-label-and-seed-queries-Paper-Conference.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
387.34 kB
Formato
Adobe PDF
|
387.34 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.