Multi-Label Informed Feature Selection

Ling Jian, Jundong Li, Kai Shu, Huan Liu

Introduction

In modern data science, multi-label learning is essential for tasks such as image tagging and document categorization. Unlike traditional single-label classification, multi-label instances belong to multiple categories simultaneously. This complexity introduces significant hurdles: high dimensionality, complex label correlations, and the prevalence of imperfect, noisy human annotations. Existing feature selection methods often struggle because they either treat labels independently or rely too heavily on potentially flawed raw labels.

The Multi-Label Informed Feature Selection (MIFS) framework addresses these issues by mapping high-dimensional, noisy labels into a clean, low-dimensional latent space. By selecting features that predict these underlying latent semantics rather than raw labels, the model captures label correlations while remaining robust to annotation errors.

Methodology

The MIFS framework integrates label decomposition, manifold learning, and sparse regression into a unified optimization problem.

Latent Semantic Decomposition

Instead of using the raw label matrix ($Y$), MIFS decomposes it into a low-dimensional latent space ($V$) and a coefficient matrix ($B$). This process uncovers underlying themes shared across labels and smooths out noise.

Structure Preservation

To ensure the latent space reflects the original data's intrinsic structure, the model employs a Graph Laplacian. This forces data points that are close in the original feature space to remain close in the latent semantic space.

Joint Feature Selection

MIFS performs a regression to map input features ($X$) to the latent space ($V$). By applying an $\ell_{2,1}$-norm regularization on the weight matrix ($W$), the model selects a small, shared subset of features useful for predicting all latent dimensions simultaneously.

Optimization

The resulting non-convex problem is solved using an efficient alternating optimization algorithm. The inclusion of the Armijo rule for adaptive step sizes significantly accelerates convergence.

Convergence of the objective function value with and without the Armijo rule.

Experimental Evaluation

The framework was evaluated on four benchmark datasets:

  • Scene: An image dataset with 6 labels and 294 features.
  • RCV1 (Topics, Regions, Industries): Three subsets of the Reuters Corpus Volume 1 text archive, featuring up to 354 labels and 18,894 features.

Results and Discussion

MIFS consistently outperformed state-of-the-art methods, such as CSFS and SFUS, across all datasets in terms of Micro-average and Macro-average F-measures.

Micro-average F-measure performance of MIFS compared to baseline methods across four benchmark datasets.

Key Findings

  • Robustness to Noise: By using a "latent teacher," MIFS filters out human annotation errors and focuses on core signals.
  • Feature Efficiency: MIFS achieves high accuracy even with a very small percentage of features (often less than 14%), identifying the most discriminative data effectively.
  • Computational Efficiency: MIFS relies on matrix multiplications ($O(ndc)$) rather than expensive inversions, making it faster than competitors. For instance, on the Industries dataset, MIFS converged in approximately 5,500 seconds, compared to over 25,000 seconds for SFUS.
  • Rapid Convergence: As shown in the convergence analysis, the Armijo update rule allows the model to reach a stable solution in roughly 100 iterations, a ten-fold improvement over standard updates.

Conclusion

The MIFS framework provides a robust and efficient solution for feature selection in multi-label learning by leveraging latent semantic structures. While highly effective in batch learning scenarios, future research will focus on adapting this approach for streaming data environments where samples arrive continuously.

Summary updated

Abstract

Multi-label learning has been extensively studied in the area of bioinformatics, information retrieval, multimedia annotation, etc. In multi-label learning, each instance is associated with multiple interdependent class labels, the label information can be noisy and incomplete. In addition, multilabeled data often has noisy, irrelevant and redundant features of high dimensionality. As an effective data preprocessing step, feature selection has shown its effectiveness to prepare high-dimensional data for numerous data mining and machine learning tasks. Most of existing multi-label feature selection algorithms either boil down to solving multiple single-labeled feature selection problems or directly make use of imperfect labels. Therefore, they may not be able to find discriminative features that are shared by multiple labels. In this paper, we propose a novel multi-label informed feature selection framework MIFS, which exploits label correlations to select discriminative features across multiple labels. Specifically, to reduce the negative effects of imperfect label information in finding label correlations, we decompose the multi-label information into a low-dimensional space and then employ the reduced space to steer the feature selection process. Empirical studies on real-world datasets demonstrate the effectiveness and efficiency of the proposed framework.
BibTeX
@inproceedings{jian2016multi,
  author = {Ling Jian and Jundong Li and Kai Shu and Huan Liu},
  title = {{Multi-Label Informed Feature Selection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure