NDLI: Learning noisy linear classifiers via adaptive and selective sampling

Content Provider	Springer Nature Link
Author	Cavallanti, Giovanni Cesa Bianchi, Nicolò Gentile, Claudio
Copyright Year	2010
Abstract	We introduce efficient margin-based algorithms for selective sampling and filtering in binary classification tasks. Experiments on real-world textual data reveal that our algorithms perform significantly better than popular and similarly efficient competitors. Using the so-called Mammen-Tsybakov low noise condition to parametrize the instance distribution, and assuming linear label noise, we show bounds on the convergence rate to the Bayes risk of a weaker adaptive variant of our selective sampler. Our analysis reveals that, excluding logarithmic factors, the average risk of this adaptive sampler converges to the Bayes risk at rate N $^{−(1+α)(2+α)/2(3+α)}$ where N denotes the number of queried labels, and α>0 is the exponent in the low noise condition. For all $\alpha>\sqrt{3}-1\approx0.73$ this convergence rate is asymptotically faster than the rate N $^{−(1+α)/(2+α)}$ achieved by the fully supervised version of the base selective sampler, which queries all labels. Moreover, for α→∞ (hard margin condition) the gap between the semi- and fully-supervised rates becomes exponential.
Starting Page	71
Ending Page	102
Page Count	32
File Format	PDF
ISSN	08856125
Journal	Machine Learning
Volume Number	83
Issue Number	1
e-ISSN	15730565
Language	English
Publisher	Springer US
Publisher Date	2010-05-20
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Active learning Selective sampling Adaptive sampling Linear classification Low noise Computing Methodologies Control , Robotics, Mechatronics Artificial Intelligence (incl. Robotics) Simulation and Modeling Language Translation and Linguistics
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The true sample complexity of active learning

Linear classifiers are nearly optimal when hidden variables have diverse effects

Adaptive regularization of weight vectors

Online Passive-Aggressive Active learning

Improving classification performance through selective instance completion

Anytime classification for a pool of instances

Efficient distance metric learning by adaptive sampling and mini-batch stochastic gradient descent (SGD)

Soft-max boosting

Random classification noise defeats all convex potential boosters

Learning noisy linear classifiers via adaptive and selective sampling

Similar Documents

The true sample complexity of active learning

Linear classifiers are nearly optimal when hidden variables have diverse effects

Adaptive regularization of weight vectors

Online Passive-Aggressive Active learning

Improving classification performance through selective instance completion

Anytime classification for a pool of instances

Efficient distance metric learning by adaptive sampling and mini-batch stochastic gradient descent (SGD)

Soft-max boosting

Random classification noise defeats all convex potential boosters

Learning noisy linear classifiers via adaptive and selective sampling