Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
Learning Bayesian Network Classifiers to Minimize the Class Variable Parameters
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a Bayesian network classifier whose I-map structure minimizes class-variable parameters (NCP) among structures with no class parents, and learns it exactly via a depth-first branch-and-bound search over an order graph with a naive-Bayes lower-bound heuristic.
Problem
Exact learning of Bayesian network classifiers under marginal likelihood tends to be unstable for small samples when the class variable has many parents, since it minimizes all parameters rather than the class-variable parameters that drive classification.
Approach
Restrict the search to structures where the class variable has no parents (NPCDAGs), prove that maximizing BDeu per variable order yields the I-map with the lowest number of class variable parameters (NCP), formulate learning as a shortest-path problem on an NPC reverse order graph, and speed it up with a consistent heuristic given by the NCP of a naive Bayes classifier.
Key results
- Proposed(BFS) achieves average accuracy 0.8385 vs 0.8354 for Proposed(DFB&B) and 0.8201 for GBN-BDeu on 24 UCI datasets (Table 1), outperforming most methods at p<0.1.
- On 11 large UCI datasets, Proposed(DFB&B) averages 0.8961 accuracy versus 0.8405 for the best baseline (GBN-CMDL), while the exact baselines hit time limits.
- Proposed(DFB&B) runtime averages 49.4 s versus 1026 s for GBN-BDeu across the 24 datasets (Table 3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| learn an NPCDAG with the fewest class-variable parameters using breadth-first search instead of the compared methods | Bayesian network classifier · 24 UCI benchmark datasets | classification accuracy: 0.8106 -> 0.8385 | Helped |
| use depth-first branch-and-bound search for the proposed classifier | Proposed(BFS) · 11 large UCI datasets | classification accuracy: 0.8405 -> 0.8961 | Helped |
| use depth-first branch-and-bound search instead of breadth-first search | Proposed BNC · 24 UCI benchmark datasets | average runtime (s): 1026.0 -> 49.4 | Helped |
| use depth-first branch-and-bound search instead of breadth-first search | Proposed BNC · 24 UCI benchmark datasets | classification accuracy: 0.8385 -> 0.8354 | Hurt |
| minimize the number of class-variable parameters rather than the number of all network parameters | Proposed(BFS) versus GBN-BDeu · Markov network simulation, N=100,000 | average KLD: 1.20 × 10−3 -> 7.94 × 10−5 | Helped |
Surprising findings
- On large datasets, exact GBN-BDeu, ANB-BDeu and fsANB-BDeu failed to finish within 6 hours, while the depth-first branch-and-bound variant could be stopped at any time and still return a current best solution.
Limitations
- Exact learning (Proposed(BFS)) fails on datasets with more variables due to exponential time and memory, so scaling relies on the branch-and-bound variant.
- Theoretical guarantees depend on Assumption 1 (faithfulness) and sufficiently large samples.
- Explainability of the learned graphical structure is not analyzed in the paper.
Experimental setup
Datasets: UCI repository 24 datasets UCI large datasets (11) Cancer network simulation Asia network simulation Markov network simulation
Benchmarks: 24 UCI datasets 11 large UCI datasets simulated Cancer/Asia/Markov networks
Metrics: classification accuracy number of class variable parameters (NCP) runtime KL divergence of class posterior p-value from Hommel's test
Baselines: Naive Bayes GBN-CMDL BNC2P TAN-aCLL MC-DAGGES GBN-BDeu ANB-BDeu fsANB-BDeu
Builds on: ANB (augmented naive Bayes) fsANB-BDeu BDeu score Greedy equivalence search Conditional MDL
Closest papers by meaning
- Compiling Bayesian Network Classifiers into Decision Graphs (AAAI 2019 · similarity 0.85)
- Extendable and Iterative Structure Learning Strategy for Bayesian Networks (ICLR 2025 · similarity 0.84)
- Learning Bayesian Networks with Low Rank Conditional Probability Tables (NeurIPS 2019 · similarity 0.84)
- Natural-Parameter Networks: A Class of Probabilistic Neural Networks (NeurIPS 2016 · similarity 0.84)
- A Metalearned Neural Circuit for Nonparametric Bayesian Inference (NeurIPS 2024 · similarity 0.82)
- Random-Set Neural Networks (ICLR 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.