This paper studies online active learning problems for classification tasks, devising so-called passive-aggressive active (PAA) learning algorithms. According to the paper, existing active learning methods such as perceptron methods usually “only use the misclassified instances to update the classifier,” which implies that those correctly classified instances have never been used in updating the classifier and the effort of requesting class labels has been wasted. The existing passive-aggressive algorithm updates the classifier based on a loss function, which implies that each incoming instance should be queried. The proposed PAA incorporates the ideas behind both the perceptron and PA methods.

Put simply, PAA introduces a Bernoulli random variable “to decide whether the ... incoming instance [is] queried.” The querying probability is defined via the prediction margin. Thus, according to Lu et al., PAA can address two “key challenges to an online active learning task”: (1) “when [the classifier] should query the class label of an incoming instance,” and (2) “how to exploit the labeled instance to update [the classifier]” once “the class label is queried and disclosed.” PAA is simple to implement. Moreover, the paper determined the effectiveness theoretically, giving the mistake bounds of the PAA algorithms. The paper has also extended PAA to multi-class classification and cost-sensitive classification problems, and conducted extensive empirical analysis. In summary, this paper makes important contributions to online active learning tasks.