BatchRank: A Novel Batch Mode Active Learning Framework for Hierarchical Classification

Active learning algorithms automatically identify the salient\ud and exemplar instances from large amounts of unlabeled\ud data and thus reduce human annotation effort in inducing\ud a classification model. More recently, Batch Mode Active\ud Learning (BMAL) techniques have been proposed, where a\ud batch of data samples is selected simultaneously from an un-\ud labeled set. Most active learning algorithms assume a \ud at\ud label space, that is, they consider the class labels to be in-\ud dependent. However, in many applications, the set of class\ud labels are organized in a hierarchical tree structure, with\ud the leaf nodes as outputs and the internal nodes as clusters\ud of outputs at multiple levels of granularity. In this paper,\ud we propose a novel BMAL algorithm (BatchRank) for hi-\ud erarchical classification. The sample selection is posed as\ud an NP-hard integer quadratic programming problem and a\ud convex relaxation (based on linear programming) is derived,\ud whose solution is further improved by an iterative truncated\ud power method. Finally, a deterministic bound is established\ud on the quality of the solution. Our empirical results on sev-\ud eral challenging, real-world datasets from multiple domains,\ud corroborate the potential of the proposed framework for real-\ud world hierarchical classification applications