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.
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.
@cite_19
2762016725
Like other machine learning paradigms, multi-label learning also suffers from the curse of dimensionality problem. Multi-label dimensionality reduction can alleviate the problem but they generally ask for sufficient labeled samples. Nevertheless, we often may only have scarce labeled samples and abundant unlabeled samples. In this paper, we propose a @math emi-supervised @math ulti-label @math imensionality @math eduction based on @math ependence @math aximization approach (SMDRdm in short). SDMRdm assumes the semantic similarity and feature similarity of multi-label samples are inter-depended. SMDRdm first applies label propagation on a neighborhood graph composed with labeled and unlabeled samples to obtain the soft labels of unlabeled samples, and then measures the semantic similarity between all the training samples (including unlabeled ones) based on these soft labels and available labels of labeled samples. Next, it measures the feature similarity between samples in the subspace projected by the target projective matrix, instead of the original high-dimensional feature space. After that, it maximizes the dependence between these two types of similarities and incorporates the dependence into linear discriminant analysis to optimize the target projective matrix. Experiments on publicly accessible multi-label data sets demonstrate that SMDRdm achieves more prominent results than other related approaches across various evaluation metrics. In addition, the empirical study also shows the semantic similarity between samples derived from soft labels works better than that derived from scarce available labels.