Efficient active learning of halfspaces via query synthesis

Ibrahim Alabdulmohsin, Xin Gao, Xiangliang Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Active learning is a subfield of machine learning that has been successfully used in many applications including text classification and bioinformatics. One of the fundamental branches of active learning is query synthesis, where the learning agent constructs artificial queries from scratch in order to reveal sensitive information about the true decision boundary. Nevertheless, the existing literature on membership query synthesis has focused on finite concept classes with a limited extension to real-world applications. In this paper, we present an efficient spectral algorithm for membership query synthesis for halfspaces, whose sample complexity is experimentally shown to be near-optimal. At each iteration, the algorithm consists of two steps. First, a convex optimization problem is solved that provides an approximate characterization of the version space. Second, a principal component is extracted, which yields a synthetic query that shrinks the version space exponentially fast. Unlike traditional methods in active learning, the proposed method can be readily extended into the batch setting by solving for the top κ eigenvectors in the second step. Experimentally, it exhibits a significant improvement over traditional approaches such as uncertainty sampling and representative sampling. For example, to learn a halfspace in the Euclidean plane with 25 dimensions and an estimation error of 1E-4, the proposed algorithm uses less than 3% of the number of queries required by uncertainty sampling.
Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
StatePublished - Feb 2015


Dive into the research topics of 'Efficient active learning of halfspaces via query synthesis'. Together they form a unique fingerprint.

Cite this