Abstract
Multi-label feature selection is a critical task for high-dimensional data where multiple target variables are interdependent. Traditional causal methods based on Markov Blanket (MB) discovery often suffer from high computational complexity and redundancy. We propose MCF-Spouse, a novel algorithm that optimizes spouse discovery and utilizes mutual information to recover informative features that might otherwise be blocked by label correlations. Experimental results across eight diverse real-world datasets demonstrate that MCF-Spouse consistently achieves state-of-the-art predictive accuracy while significantly reducing computational overhead compared to existing Bayesian network approaches.
Introduction
In multi-label learning (MLL), instances are associated with multiple labels simultaneously. Selecting the most relevant features is essential to improve model performance and interpretability. Causal feature selection aims to identify the Markov Blanket (MB) of target variables—the minimal set of parents, children, and spouses that renders the target independent of all other variables.
Despite its theoretical robustness, MB discovery in MLL faces three major challenges:
- Equivalent Information: Redundancy between features and labels can lead to suboptimal selection.
- Path Blockage: Strong correlations between labels can obscure the causal path from a feature to a specific label.
- Spouse Search Explosion: Identifying spouse variables (other parents of a target's children) typically requires an exhaustive search with a large number of Conditional Independence (CI) tests.
Methodology
MCF-Spouse addresses these hurdles through a three-phase algorithm designed to build an optimal Markov Blanket:
Phase 1: Initial Discovery
The algorithm identifies the initial Parent-Child (PC) set for each label using the HITON-PC framework, establishing the primary causal relationships.
Phase 2: Feature Recovery
To overcome path blockage and equivalent information issues, MCF-Spouse employs Mutual Information (MI). It re-evaluates features that were initially excluded. A feature $F$ is "recovered" and added to the candidate set if it provides more information about a target label $L_1$ than a correlated label $L_2$ does (i.e., $I(L_1; F) > I(L_1; L_2)$). This ensures that labels act as informative anchors rather than obstacles.
Phase 3: Optimal Spouse Discovery
This phase optimizes the computationally expensive spouse search. By leveraging a theoretical pruning strategy (Theorem 2), the algorithm focuses only on "optimal" spouse configurations. It specifically targets cases where a target label and a candidate feature share a common "collider" variable, drastically reducing the search space.
Experimental Evaluation
The method was evaluated on eight real-world datasets spanning biology (VirusGO, Yeast, HumanGO, PlantGO, CHD 49), image processing (Flags, Image), and text (Enron). Performance was assessed using four standard metrics: Hamming Loss, Ranking Loss, F-Micro, and F-Macro.
Results and Discussion
MCF-Spouse demonstrated superior performance across all datasets and metrics:
- Predictive Accuracy: It consistently outperformed nine state-of-the-art methods, maintaining high accuracy even as the number of features increased.
- Computational Efficiency: The targeted spouse search drastically reduced runtime. On the Image dataset, MCF-Spouse was approximately twice as fast as other Bayesian Network-based methods, such as M2LC (137s vs 278s).
- Stability and Consistency: The "spider web" diagrams illustrate the algorithm's robustness. MCF-Spouse typically forms the outer boundary of these plots, indicating it is the most stable and high-performing method across diverse data types.
Conclusion
MCF-Spouse provides an efficient and accurate solution for multi-label causal feature selection. By refining the spouse discovery process and utilizing mutual information for feature recovery, it overcomes common pitfalls in causal discovery. Future work will focus on further reducing spurious variables and incorporating advanced logic rules to sharpen Markov Blanket construction.
Summary updated