Active Batch Selection via Convex Relaxations with Guaranteed Solution Bounds

Chakraborty, S and Balasubramanian, V N and Sun, Q and Panchanathan, S and Ye, J (2015) Active Batch Selection via Convex Relaxations with Guaranteed Solution Bounds. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37 (10). pp. 1945-1958. ISSN 0162-8828

Full text not available from this repository. (Request a copy)

Abstract

Active learning techniques have gained popularity to reduce human effort in labeling data instances for inducing a classifier. When faced with large amounts of unlabeled data, such algorithms automatically identify the exemplar instances for manual annotation. More recently, there have been attempts towards a batch mode form of active learning, where a batch of data points is simultaneously selected from an unlabeled set. In this paper, we propose two novel batch mode active learning (BMAL) algorithms: BatchRank and BatchRand. We first formulate the batch selection task as an NP-hard optimization problem; we then propose two convex relaxations, one based on linear programming and the other based on semi-definite programming to solve the batch selection problem. Finally, a deterministic bound is derived on the solution quality for the first relaxation and a probabilistic bound for the second. To the best of our knowledge, this is the first research effort to derive mathematical guarantees on the solution quality of the BMAL problem. Our extensive empirical studies on 15 binary, multi-class and multi-label challenging datasets corroborate that the proposed algorithms perform at par with the state-of-the-art techniques, deliver high quality solutions and are robust to real-world issues like label noise and class imbalance.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Balasubramanian, V NUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Batch Mode Active Learning, Optimization,
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 22 Sep 2015 05:56
Last Modified: 21 Apr 2016 09:32
URI: http://raiith.iith.ac.in/id/eprint/1940
Publisher URL: http://dx.doi.org/10.1109/TPAMI.2015.2389848
OA policy: http://www.sherpa.ac.uk/romeo/issn/0162-8828/
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 1940 Statistics for this ePrint Item