Abstract
Learning the structure of Bayesian Networks (BNs) is a computationally challenging task, typically addressed using hybrid algorithms that combine constraint-based skeleton discovery with search-and-score refinement. A significant limitation of current hybrid methods, such as Max-Min Hill-Climbing (MMHC), is their susceptibility to "cascading errors" where missed edges in the initial phase cannot be recovered. This paper proposes H2PC (Hybrid HPC), a novel algorithm that prioritizes high recall during the skeleton discovery phase to mitigate these errors. Additionally, the authors demonstrate how H2PC can be applied to multi-label classification (MLC) by identifying minimal label powersets from the learned BN structure, effectively decomposing complex dependencies. Evaluations on synthetic benchmarks and real-world MLC datasets show that H2PC achieves superior structural accuracy and predictive performance compared to existing state-of-the-art methods.
Introduction
Learning the structure of a Bayesian Network (BN)—essentially a map of how variables in a dataset influence one another—is a notoriously difficult NP-hard problem. Most modern approaches are hybrid: they first use statistical tests to find a "skeleton" of possible connections (Constraint-Based phase) and then use a scoring function to orient those connections and refine the graph (Search-and-Score phase).
The major pitfall of existing hybrid algorithms, like the popular Max-Min Hill-Climbing (MMHC), is that they often suffer from "cascading errors." If the initial phase misses a true connection (a false negative), the second phase can never recover it. This paper tackles the challenge of reducing these false negatives to build more accurate and robust models, particularly for multi-label learning (MLC), where understanding the intricate web of dependencies between multiple target labels is crucial for accurate prediction.
The H2PC Algorithm
The core contribution is the H2PC (Hybrid HPC) algorithm. It operates in two distinct stages:
- The Skeleton Phase (HPC): Instead of relying on a single pass, H2PC uses an ensemble-like subroutine called HPC (Hybrid Parents and Children). It combines several "weak" learners to identify the neighborhood of each variable. By loosening the criteria for inclusion and performing extra computations, it aims for much higher recall (finding more true edges) than standard methods, even if it introduces a few more false positives initially.
- The Orientation Phase: Once the skeleton is established, H2PC uses a Bayesian-scoring greedy hill-climbing search (with a TABU list to avoid local optima) to orient the edges. Crucially, this search is constrained to only consider edges found in the first phase.
For the multi-label application, the authors provide new theoretical results to identify minimal label powersets—groups of labels that are irreducibly dependent on each other—directly from the learned BN structure. This allows them to break a massive multi-label problem into several smaller, independent multi-class problems.
Experimental Evaluation
The authors evaluated H2PC using two distinct sets of data: synthetic benchmarks and real-world multi-label data. The synthetic benchmarks consist of eight well-known Bayesian network structures, ranging from small networks like child to large networks like link, as detailed in Table 1. These provide a ground truth to measure how well the algorithm reconstructs the original network across varying sample sizes (from 50 to 50,000 samples).
For real-world application, ten diverse datasets from the Mulan repository were used, covering domains like music (emotions), biology (yeast, genbase), text (slashdot, enron), and images (scene, corel5k).
Results and Discussion
Experimental results indicate that H2PC's "over-inclusive" strategy in the skeleton phase pays off. While it may introduce more false positives initially, the subsequent scoring phase is highly effective at pruning them, whereas standard methods cannot recover from early false negatives.
- Structural Accuracy: H2PC significantly reduced the Structural Hamming Distance (SHD) compared to MMHC, especially on larger datasets. For 50,000 samples, H2PC's SHD was roughly half that of MMHC. It also consistently achieved better goodness-of-fit scores (BDeu and BIC) across nearly all sample sizes.
- MLC Performance: In real-world multi-label tasks, H2PC-based models showed superior global classification accuracy. For example, on the scene dataset, subset accuracy jumped from 20% (with MMHC) to 56% (with H2PC).
- Feature Selection: The BN-derived Markov boundary proved to be a powerful tool for feature selection. On the genbase dataset, this approach boosted accuracy from 7% to 98%.
Conclusion
H2PC demonstrates that focusing on learning accurate local neighborhoods leads to a superior global model. However, this accuracy comes at a computational cost; H2PC is roughly 10 times slower than MMHC on very large datasets due to the increased number of statistical tests. Future work will focus on parallelization to mitigate this cost and relaxing the "faithfulness condition" to better handle unfaithful real-world data distributions.
Summary updated