Generalized Information-Theoretic Criterion for Multi-Label Feature Selection

Wangduk Seo, Dae-Won Kim, Jaesung Lee

Introduction

In the era of high-dimensional data, feature selection has become a critical preprocessing step in machine learning. By identifying the most relevant subset of features, researchers can reduce model complexity, improve generalization, and decrease computational costs. While feature selection for single-label classification is well-established, multi-label learning—where an instance can belong to multiple categories simultaneously—presents unique challenges. The primary difficulty lies in capturing the complex dependencies between features and multiple labels without succumbing to the "curse of dimensionality."

The Challenge of Multi-Label Feature Selection

The theoretical gold standard for feature selection is based on maximizing mutual information or minimizing joint entropy. However, calculating joint entropy for high-dimensional feature sets and label sets is computationally intractable. It requires an exponentially large amount of data to estimate accurately, a problem known as the curse of dimensionality. To address this, existing methods typically rely on fixed approximations, often considering only pairwise interactions between variables. While efficient, these "one-size-fits-all" approximations often fail to capture higher-order dependencies present in complex real-world datasets, leading to suboptimal feature subsets.

The GICS Framework

This paper introduces the Generalized Information-Theoretic Criterion (GICS), a novel framework designed to provide a flexible and theoretically grounded approach to multi-label feature selection. GICS moves beyond static approximations by utilizing a $k$-cardinality entropy approximation derived from Han's inequality.

Key Methodological Components

  1. $k$-Cardinality Approximation: Instead of a fixed formula, GICS allows researchers to adjust the level of approximation ($k$). This parameter determines the number of variables considered in the entropy calculation. For instance, $k=2$ focuses on pairwise interactions, while $k=3$ incorporates triplet dependencies.
  2. Incremental Search Strategy: To maintain computational feasibility, GICS employs a greedy incremental search. Starting with an empty set, the algorithm iteratively selects the feature that maximizes the generalized score function ($J$) relative to the labels and the already-selected features.
  3. Filter-Based Versatility: As a "filter" method, GICS is independent of any specific classifier. This makes it highly versatile, as the selected features can be used with various multi-label algorithms like MLkNN (Multi-Label k-Nearest Neighbors) or MLNB (Multi-Label Naive Bayes).

Experimental Evaluation

The researchers evaluated the performance of GICS across eight diverse multi-label datasets spanning text mining (Enron, Medical), multimedia (Scene, Arts, Entertainment), and bioinformatics (Genbase). These datasets vary significantly in their number of patterns (662 to 12,730) and labels (6 to 75), ensuring a robust assessment of the framework's generalizability.

GICS was compared against three prominent multi-label feature selection methods: MCLS (Max-Dependency and Min-Redundancy), MDMR (Multi-label Dimensionality reduction via Max-Relevance), and PMU (Pairwise Mutual Information).

Key Insights and Results

The experimental results demonstrate that GICS consistently outperforms state-of-the-art methods across multiple performance metrics, including Multi-label accuracy, Hamming loss, Ranking loss, and Normalized coverage.

Flexibility and Performance

A central finding of the study is that the optimal value of $k$ is dataset-dependent. While $k=2$ is often sufficient and computationally efficient, certain datasets show significant performance gains when $k=3$ is used. This confirms that capturing higher-order interactions is essential for certain types of data.

Statistical Significance

Using the Friedman test followed by Bonferroni-Dunn post-hoc analysis, the authors established that GICS is statistically superior to its competitors. Specifically, GICS achieved the best average rank (often 1.000) across the tested datasets, particularly in minimizing Hamming loss regardless of whether a Nearest Neighbor or Naive Bayes classifier was used.

The Computational Trade-off

The study highlights a clear trade-off between approximation accuracy and computational time. Increasing $k$ from 2 to 3 can lead to better feature subsets but increases the processing time significantly. For example, on the Llog dataset, the execution time jumped from approximately 1.6 minutes to 95 minutes. This suggests that while $k=3$ is beneficial, higher values of $k$ may currently be impractical for very large datasets without further optimization.

Conclusion and Future Directions

GICS provides a powerful and flexible framework for multi-label feature selection, offering a theoretical bridge between various information-theoretic criteria. By allowing the approximation level to be tuned, it enables a more nuanced capture of feature-label dependencies. Future research will focus on developing methods to automatically determine the optimal $k$ for a given dataset and exploring more efficient search strategies to scale GICS to "big data" scenarios involving millions of features.

Summary updated

Abstract

Multi-label feature selection that identifies important features from the original feature set of multi-labeled datasets has been attracting considerable attention owing to its generality compared to conventional single-label feature selection. The unimportant features are filtered by scoring the dependency of features to labels. In conventional multi-label feature filter studies, the score function is obtained by approximating a dependency measure such as joint entropy because direct calculation is often impractical due to the presence of multiple labels with limited training patterns. Although the efficacy of approximation can differ depending on the characteristics of the multi-label dataset, conventional methods presume a certain approximation method, leading to a degenerated feature subset if the presumed approximation is inappropriate for the given dataset. In this study, we propose a strategy for selecting an approximation among a series of approximations depending on the number of involved variables and consequently instantiate a score function based on the chosen approximation. The experimental results demonstrate that the proposed strategy and score function outperform conventional multi-label feature selection methods.
BibTeX
@article{seo2019generalized,
  author = {Wangduk Seo and Dae-Won Kim and Jaesung Lee},
  title = {{Generalized Information-Theoretic Criterion for Multi-Label Feature Selection}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2927400},
}
Figure