Extreme multi-label classification aims to learn a classifier that annotates an instance with a relevant subset of labels from an extremely large label set. Many existing solutions embed the label matrix to a low-dimensional linear subspace, or examine the relevance of a test instance to every label via a linear scan. In practice, however, those approaches can be computationally exorbitant. To alleviate this drawback, we propose a Block-wise Partitioning (BP) pretreatment that divides all instances into disjoint clusters, to each of which the most frequently tagged label subset is attached. One multi-label classifier is trained on one pair of instance and label clusters, and the label set of a test instance is predicted by first delivering it to the most appropriate instance cluster. Experiments on benchmark multi-label data sets reveal that BP pretreatment significantly reduces prediction time, and retains almost the same level of prediction accuracy.
@cite_19: We consider the case of ranking a very large set of labels, items, or documents, which is common to information retrieval, recommendation, and large-scale annotation tasks. We present a general approach for converting an algorithm which has linear time in the size of the set to a sublinear one via label partitioning. Our method consists of learning an input partition and a label assignment to each partition of the space such that precision at k is optimized, which is the loss function of interest in this setting. Experiments on large-scale ranking and recommendation tasks show that our method not only makes the original linear time algorithm computationally tractable, but can also improve its performance.
In contrast to the above methods, we develop a pretreatment for those algorithms. The following three approaches are relevant to ours. Label Partitioning for Sub-linear Ranking (LPSR) follows a two-step approach. At the training stage, it clusters the training instances, and then assigns a fixed number of potential labels to each cluster. At the testing stage, a test instance is first put in one of the clusters, and its labels are predicted only from the labels attached to that cluster @cite_19 . While LPSR and our proposal stand on the same testing stage, three differences can be observed at the training stage. First, the optimized number of clusters in our method is selected by the algorithm, whereas the number in LPSR is predefined. Second, cardinality of our label clusters may vary across clusters, while the number of potential labels in each cluster in LPSR is fixed. Moreover, our instance and label clusters are updated via optimization, whereas assignment of training instances in LPSR solely depends on feature matrix. Consequently, our method permits more flexibility in cluster structure.