Active Batch Selection via Convex Relaxations with Guaranteed Solution Bounds.

Area of Science:

• Machine Learning
• Data Science
• Artificial Intelligence

Background:

• Active learning reduces human effort in data labeling for classifier training.
• Batch mode active learning selects multiple data points simultaneously, posing an optimization challenge.

Purpose of the Study:

• To propose two novel batch mode active learning (BMAL) algorithms: BatchRank and BatchRand.
• To address the NP-hard optimization problem in batch selection with convex relaxations.
• To provide the first mathematical guarantees on solution quality for BMAL.

Main Methods:

• Formulated batch selection as an NP-hard optimization problem.
• Developed two convex relaxations: one using linear programming, another using semi-definite programming.
• Derived deterministic and probabilistic bounds on solution quality.

Main Results:

• Proposed BatchRank and BatchRand algorithms for batch mode active learning.
• Achieved performance on par with state-of-the-art techniques across 15 diverse datasets.
• Demonstrated robustness to label noise and class imbalance.

Conclusions:

• The proposed BMAL algorithms offer efficient and high-quality data selection for machine learning.
• Mathematical guarantees on solution quality are provided for the first time in BMAL research.
• The algorithms are effective in real-world scenarios with noisy or imbalanced data.