Label dependency modeling in Multi-Label Naïve Bayes through input space expansion

P. K. A. Chitra, Saravana Balaji Balasubramanian, Omar Khattab, Mhd Omar Al-KadriPeerJ Comput. Sci 2024 · DOI

TL;DR

This paper introduces an enhanced Multi-Label Naïve Bayes (iMLNB) algorithm that tackles the challenge of label dependencies in multi-label classification. By expanding the input space to include meta-information from the label space, iMLNB models these dependencies, leading to improved classification accuracy and reduced errors compared to traditional methods.

What Problem Does This Paper Address?

Traditional machine learning often deals with single-label classification, where each instance belongs to exactly one class. However, many real-world scenarios involve multi-label classification, where an instance can be associated with multiple labels simultaneously. This complexity arises in areas like document tagging, image annotation, and gene function prediction.

A common challenge in multi-label classification is the assumption of label independence, often made by algorithms like Naïve Bayes. This assumption, while simplifying the model, ignores the inherent relationships and dependencies that often exist between labels. For example, an image of a "forest" is likely also an image of "trees." Ignoring these correlations can lead to suboptimal performance and inaccurate predictions. This paper aims to address this gap by explicitly modeling label dependencies within the Naïve Bayes framework.

Methods

The core innovation of this paper lies in the improved Multi-Label Naïve Bayes (iMLNB) algorithm. It tackles label dependencies through a two-stage process:

  • Stage 1: Feature Space Reconstruction with Meta Data: The algorithm expands the original feature space by incorporating "meta data" derived from the label space. Specifically, it uses all but one label from the label set as input features for the current label being considered. This expansion allows the model to learn relationships between labels. To prevent overfitting due to the increased dimensionality, a feature selection process is employed, retaining only highly correlated labels (correlation coefficient $\rho > 0.5$). This creates a heterogeneous feature space containing both original continuous predictors and discrete (binary) label information.
  • Stage 2: MLNB Parameter Modelling: To handle the mixed nature of the expanded feature space (continuous and discrete predictors), the likelihood estimation in the Naïve Bayes model is adapted. It uses a mixed joint density function that combines Gaussian distributions for continuous features and Bernoulli distributions for discrete (label) features. This allows the model to effectively estimate probabilities from this heterogeneous input.

The algorithm is trained using actual label values as meta data and tested using predicted label values.

Datasets

The authors evaluated their iMLNB method on sixteen benchmark multi-label datasets from various domains, including music, text, image, and biology. These datasets are publicly available from the MULAN data repository and MEKA. The specific datasets used are:

  • Corel6k
  • MediaMill
  • CAL500
  • Enron
  • Corel15k
  • Rcv1 (subset 1)
  • Rcv1 (subset 2)
  • Eurlex-sm
  • tmc2007
  • Yeast
  • Bibtex
  • Medical
  • Genbase
  • Slashdot
  • Emotions
  • Scene

Key Insights and Ideas

  • Label Dependencies are Crucial: The research strongly emphasizes that ignoring label dependencies in multi-label classification leads to a loss of valuable information and can significantly hinder model performance.
  • Input Space Expansion as a Solution: Expanding the feature space to include information from other labels is an effective strategy to capture these dependencies.
  • Heterogeneous Data Handling: The challenge of mixed continuous and discrete data in the expanded feature space is effectively addressed by adapting the likelihood estimation to a mixed joint density function.
  • Trade-off Between Complexity and Performance: While expanding the input space increases model complexity and potentially training time, it leads to demonstrably better classification accuracy.

Key Results

The iMLNB method consistently outperformed the traditional Multi-Label Naïve Bayes (MLNB) and other state-of-the-art techniques across various evaluation metrics on the benchmark datasets.

  • Hamming Loss: iMLNB achieved the lowest Hamming loss in four out of six datasets, with an average Hamming loss of 0.07135, significantly lower than MLNB's 0.07573.
  • Subset Accuracy: iMLNB demonstrated the highest subset accuracy, reaching 0.65037, outperforming MLNB's 0.59078.
  • Recall and F1-Score: iMLNB showed competitive performance in recall and achieved the highest average F1-score of 0.52566, compared to MLNB's 0.46969.
  • One-Error: iMLNB achieved a remarkably low average one-error of 0.09303, indicating a significant reduction in misclassifications where the top-ranked label is incorrect.
  • Ranking Loss: iMLNB also achieved the lowest average ranking loss of 0.06233.
  • Training Time: While iMLNB exhibits a slightly higher training time than MLNB due to the expanded feature space, it is still competitive and significantly faster than some other methods like ML-C4.5.

Limitations and Future Work

The authors acknowledge two primary limitations:

  • Overfitting: The exponential growth of the input space due to label expansion can lead to overfitting, potentially limiting the model's generalizability.
  • Model Complexity and Computational Requirements: The inclusion of heterogeneous predictors (continuous and discrete) increases model complexity and computational demands, which could affect scalability.

The paper suggests that future work could explore further optimizations to address these limitations and potentially extend the approach to other machine learning algorithms.

Summary updated

BibTeX
@article{chitra2024label,
  author = {P. K. A. Chitra and Saravana Balaji Balasubramanian and Omar Khattab and Mhd Omar Al-Kadri},
  title = {{Label dependency modeling in Multi-Label Naïve Bayes through input space expansion}},
  journal = {PeerJ Comput. Sci.},
  year = {2024},
  doi = {10.7717/peerj-cs.2093},
}
Figure