The max-min hill-climbing Bayesian network structure learning algorithm

Ioannis TsamardinosLaura E. BrownConstantin F. Aliferis

article2006Machine-mediated learning2,206 citations

Modern data analysis in fields such as biomedicine frequently involves thousands of variables. Decision makers rely on Bayesian networks—graphical models representing probabilistic dependencies and potential causal relationships—to build decision-support systems and guide targeted scientific experiments. However, learning network structures directly from observational data is computationally hard. Prior algorithms struggle to scale efficiently, often fail when sample sizes are small, or require manual tuning parameters that propagate errors throughout the model.

The article develops and evaluates a hybrid structure learning algorithm called Max-Min Hill-Climbing (MMHC). The primary objective is to demonstrate that MMHC improves network reconstruction quality and computational efficiency while scaling to datasets containing thousands of variables.

MMHC operates in two sequential stages: it first applies statistical tests of conditional independence to reconstruct the unoriented network skeleton locally for each variable, and then performs a Bayesian-scoring greedy hill-climbing search restricted strictly to those identified connections to orient the edges. The authors conducted a large-scale empirical evaluation comparing MMHC against six prominent baseline methods across 22 benchmark networks (ranging from 20 to 801 variables, as well as synthetic scaled versions up to 5,000 variables) and sample sizes of 500, 1,000, 5,000, and 20,000 instances. Across the study, 4,290 networks were induced using approximately one single-CPU year of computation.

The key findings demonstrate significant performance advantages for MMHC. First, MMHC achieved superior structural reconstruction accuracy, yielding substantially fewer structural errors on average across nearly all sample sizes compared to all competing methods. Second, it demonstrated marked computational speed advantages, running between 9 and 41 times faster on average than established methods such as PC, Sparse Candidate, and unconstrained Greedy Search across finite samples. Third, MMHC performed fewer statistical independence tests and scoring calls, executing about 40% to 60% fewer calls than Greedy Search on typical networks as variable counts grew. Fourth, MMHC scaled successfully to a 5,000-variable network with 6,845 edges, achieving 99.9% specificity and 84% sensitivity in structural discovery.

These results show that constraining search-and-score methods using sound statistical tests resolves major limitations of earlier approaches. MMHC eliminates the need for users to guess maximum parent-set bounds, prevents the error cascades seen in heuristics like Sparse Candidate, and avoids the severe degradation that pure constraint-based algorithms like PC suffer when sample sizes are small. For organizations developing predictive decision models or causal discovery pipelines, MMHC reduces computational resource costs and lowers the risk of misleading structural conclusions.

Organizations analyzing complex observational data should adopt MMHC when seeking scalable Bayesian network induction. Teams may also use its underlying local search component to reconstruct targeted subnetworks around specific variables of interest when full-network learning is unnecessary. Future developmental work should focus on accelerating the edge-orientation phase, which consumed the vast majority of execution time on very large networks, and exploring continuous or parametric statistical tests.

Readers should note that the theoretical guarantees of MMHC assume data distributions are faithful (meaning all observed dependencies reflect true underlying graphical structure). The algorithm cannot detect dependencies that violate faithfulness, such as parity functions, and performance was evaluated exclusively on complete, discrete datasets. Confidence in MMHC's relative superiority across standard discrete decision-support domains remains high based on the extensive scope of the comparative benchmark.

Department of Biomedical Informatics Discovery Systems Laboratory Vanderbilt University bayesian network structure network topology structure-learning Bayesian network structure learning Max-Min Hill-Climbing Greedy Bayesian Pattern Search

pespila/max-min-hill-climbing-algorithm Tsamardinos et al (2006).pdf

Paper: Learning Bayesian networks: The combination of knowledge and statistical data, David Heckerman et al. (1994). It introduces the Bayesian scoring framework and score-and-search paradigms that MMHC utilizes for the edge-orientation phase.
Paper: A Bayesian method for the induction of probabilistic networks from data, Gregory F. Cooper et al. (1992). It provides foundational score-based structure induction and the standard greedy search baselines evaluated against MMHC.
Paper: A Tutorial on Learning with Bayesian Networks, David Heckerman (1999). It offers essential background on score-based versus constraint-based structure learning and the causal Markov assumptions underlying hybrid approaches like MMHC.
Paper: Toward Optimal Feature Selection, Daphne Koller et al. (1996). It lays the ground for local Markov blanket and neighborhood identification techniques used in constraint-based skeleton estimation.

Paper: Learning Bayesian Networks with the bnlearn R Package, Marco Scutari (2009). It provides the reference software implementation of MMHC alongside standard constraint-based and score-based structure learning algorithms in R.

Cover for The max-min hill-climbing Bayesian network structure learning algorithm

Abstract

We present a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). The algorithm combines ideas from local learning, constraint-based, and search-and-score techniques in a principled and effective way. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. In our extensive empirical evaluation MMHC outperforms on average and in terms of various metrics several prototypical and state-of-the-art algorithms, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search. These are the first empirical results simultaneously comparing most of the major Bayesian network algorithms against each other. MMHC offers certain theoretical advantages, specifically over the Sparse Candidate algorithm, corroborated by our experiments. MMHC and detailed results of our study are publicly available at http://www.dsl-lab.org/supplements/mmhc_paper/mmhc_index.html.

Topics

bayesian network structure network topology structure-learning

Keywords

Bayesian network structure learning Max-Min Hill-Climbing Greedy Bayesian Pattern Search Incremental Association Markov Blanket Sparse Candidate algorithm greedy hill-climbing search Dependency Analysis algorithm Bayesian score

1. Introduction
2. Background
3. The max-min parents and children algorithm
3.1. MMPC
3.2. Example trace
3.3. MMPC
4. Tests of conditional independence and measures of association
5. The Max-Min Hill-Climbing algorithm
6. Optimizing the computational performance
7. Time complexity of the algorithms
8. Related work
9. Empirical evaluation
9.1. Experimental design
9.1.1. Algorithms
9.1.2. Networks
9.1.3. Datasets
9.1.4. Measures of performance
9.2. Results of evaluation
9.2.1. Timing results
9.2.2. Statistical calls results
9.2.3. Bayesian score results
9.2.4. Structural hamming distance results
9.2.5. Simultaneous comparison of time and quality
9.2.6. Large sample
9.2.7. Scaling to thousands of variables
9.2.8. Relative performance of the algorithms
10. Greedy search vs. MMHC
11. PC vs. MMHC
11.1. A theoretical analysis of behavior of the PC for low sample cases
12. A theoretical analysis of the sparse candidate
13. Discussion, limitations, and future work
14. Conclusion
Appendix A: Proof of correctness
References

Knowls

Knowl 1 — Max-Min Hill-Climbing Algorithm
algorithm
The Max-Min Hill-Climbing (MMHC) algorithm is a hybrid Bayesian network structure learning method that reconstructs the network skeleton using local constraint-based tests and then directs edges using a constrained search-and-score procedure.
procedure MMHC(data D, variable set V)
    % Phase 1: Restrict (Skeleton Identification)
    for each variable X in V do
        PC_X = MMPC(X, D)
    end for
    % Phase 2: Search (Edge Orientation)
    CurrentDAG = EmptyGraph(V)
    BestDAG = CurrentDAG
    TabuList = Queue(max_size=100)
    no_improve_steps = 0
    while no_improve_steps < 15 do
        Find local graph modification operator op (add-edge Y -> X, delete-edge, or reverse-edge) that maximizes score Score(Apply(op, CurrentDAG), D) subject to:
            - op(Y -> X) is considered only if Y is in PC_X
            - op does not introduce directed cycles
            - Resulting graph is not in TabuList
        if no valid operator exists then
            break
        end if
        CurrentDAG = Apply(op, CurrentDAG)
        TabuList.push(CurrentDAG)
        if Score(CurrentDAG, D) > Score(BestDAG, D) then
            BestDAG = CurrentDAG
            no_improve_steps = 0
        else
            no_improve_steps = no_improve_steps + 1
        end if
    end while
    return BestDAG
end procedure
In the restrict phase, MMHC calls the Max-Min Parents and Children (MMPC) algorithm for every variable $X \in \mathcal{V}$ to discover its candidate parents and children set $\mathbf{PC}_X$ . In the search phase, greedy hill-climbing begins with an empty graph and iteratively evaluates single edge additions, deletions, or reversals using the Bayesian Dirichlet equivalence uniform (BDeu) score metric (with equivalent sample size $\text{ESS} = 10$ and structure prior parameter $\kappa = 1/(\text{ESS} + 1)$ ). The search is strictly constrained such that an edge addition $Y \to X$ is considered only if $Y \in \mathbf{PC}_X$ . A TABU list storing the last 100 visited DAGs prevents cycling, and search terminates after 15 consecutive moves without improving the best score found.
Knowl 2 — Max-Min Parents and Children Algorithm
algorithm
The Max-Min Parents and Children (MMPC) algorithm discovers the set of parents and children $\mathbf{PC}_T$ of a target variable $T$ from data $\mathcal{D}$ using conditional independence tests and a two-phase heuristic search followed by a symmetry correction step.
procedure MMPC(target variable T, data D)
    % Step 1: Run candidate parents and children discovery
    CPC_T = MMPC_Candidate(T, D)
    % Step 2: Symmetry correction
    for each variable X in CPC_T do
        CPC_X = MMPC_Candidate(X, D)
        if T is not in CPC_X then
            CPC_T = CPC_T \ {X}
        end if
    end for
    return CPC_T
end procedure
procedure MMPC_Candidate(target variable T, data D)
    % Phase I: Forward Phase (Inclusion)
    CPC = {}
    repeat
        for each variable X in V \ (CPC union {T}) do
            MinAssoc(X; T | CPC) = min_{S subset_or_equal CPC} Assoc(X; T | S)
        end for
        F = argmax_{X in V \ (CPC union {T})} MinAssoc(X; T | CPC)
        assocF = MinAssoc(F; T | CPC)
        if assocF > 0 then
            CPC = CPC union {F}
        end if
    until CPC does not change or assocF == 0
    % Phase II: Backward Phase (Filtering)
    for each variable X in CPC do
        if there exists S subset_or_equal (CPC \ {X}) such that Ind(X; T | S) then
            CPC = CPC \ {X}
        end if
    end for
    return CPC
end procedure
The association function $\text{Assoc}(X; T \mid \mathbf{S})$ is defined as the negative $p$ -value of the $G^2$ test of conditional independence $\text{Ind}(X; T \mid \mathbf{S})$ (breaking ties using the $G^2$ statistic value), where $\text{Assoc}(X; T \mid \mathbf{S}) = 0$ if the null hypothesis of independence cannot be rejected at significance level $\alpha = 0.05$ or if training samples are insufficient ( $< 5$ instances per contingency table parameter).
Knowl 3 — Soundness of the MMPC Algorithm
theoretical result
Let $\mathcal{D}$ be a dataset of instances sampled from a probability distribution $P$ that is faithful to a Directed Acyclic Graph (DAG) $G = \langle \mathcal{V}, \mathbf{E} \rangle$ . Let the association measure $\text{Assoc}(X; T \mid \mathbf{Z}) \ge 0$ with equality holding if and only if $\text{Ind}_P(X; T \mid \mathbf{Z})$ , and assume conditional independence tests accurately reflect independence in $P$ .

Under these assumptions, the candidate discovery subroutine $\overline{\text{MMPC}}(T, \mathcal{D})$ satisfies:
1. $\mathbf{PC}_T \subseteq \overline{\text{MMPC}}(T, \mathcal{D})$ , where $\mathbf{PC}_T$ is the true set of parents and children of $T$ in $G$ .
2. If $X \in \overline{\text{MMPC}}(T, \mathcal{D})$ and $X \notin \mathbf{PC}_T$ , then $X$ is a descendant of $T$ in all faithful DAGs representing $P$ .
Because acyclicity prevents two variables from each being a descendant of the other across all faithful representations, the symmetry check removes all false positives: $\text{MMPC}(T, \mathcal{D}) = \mathbf{PC}_T$ for every target variable $T \in \mathcal{V}$ in the large-sample limit.
Knowl 4 — Structural Hamming Distance for Bayesian Network Evaluation
definition
The Structural Hamming Distance (SHD) measures the total structural discrepancy between a learned graph and a gold-standard graph by evaluating their completed Partially Directed Acyclic Graph (PDAG) representations (Markov equivalence class patterns).
procedure SHD(Learned PDAG H, True PDAG G)
    shd = 0
    for each edge E with difference between H and G do
        if E is present in G but missing in H then
            shd = shd + 1
        else if E is present in H but extra relative to G then
            shd = shd + 1
        else if E has an incorrect orientation in H then
            % Includes directed vs. undirected mismatches and reversed edges
            shd = shd + 1
        end if
    end for
    return shd
end procedure
Learned DAGs are converted to their corresponding PDAGs prior to evaluation using standard DAG-to-PDAG transform algorithms so that statistically indistinguishable structures within the same equivalence class are not penalized.
Knowl 5 — Computational Complexity of MMPC and Skeleton Identification
theoretical result
For a variable set $\mathcal{V}$ , candidate set $\mathbf{CPC}$ , and conditioning subsets unbounded in size, the candidate discovery subroutine $\overline{\text{MMPC}}$ executes at most $O(|\mathcal{V}| \cdot 2^{|\mathbf{CPC}|})$ statistical tests during the forward phase and $O(|\mathbf{CPC}| \cdot 2^{|\mathbf{CPC}|-1})$ tests during the backward phase, yielding a per-variable test bound of $O(|\mathcal{V}| \cdot 2^{|\mathbf{CPC}|})$ .

When statistical power constraints restrict conditional independence tests to conditioning subsets of maximum size $l$ (due to requiring a minimum sample count per parameter), the number of tests per target variable is bounded by $O(|\mathcal{V}| \cdot |\mathbf{CPC}|^{l+1})$ .

When caching results across queries and assuming the heuristic keeps $|\mathbf{CPC}|$ on the order of the true parent/child size $|\mathbf{PC}|$ , the full skeleton reconstruction over all variables in $\mathcal{V}$ requires at most: $O(|\mathcal{V}|^2 \cdot |\mathbf{PC}|^{l+1})$ statistical association calculations and independence tests, where $|\mathbf{PC}| = \max_{X \in \mathcal{V}} |\mathbf{PC}_X|$ .
Knowl 6 — Scaling of Statistical Scoring Calls in MMHC Versus Greedy Search
theoretical result
To identify and add $k$ parents to a target node $T$ in a Bayesian network with $n = |\mathcal{V}|$ variables:
1. Standard unconstrained Greedy Search evaluates all remaining non-parent variables at each addition step, performing: $\sum_{i=1}^{k} (n - i) = kn - \frac{k(k-1)}{2} = O(kn)$ calls to the local scoring function.
2. MMHC restricts candidate parents using MMPC. In the best case where unrelated variables are discarded after the initial conditioning step, MMPC performs $(n - pc - 2) + 2^{pc}$ association calls (where $pc = |\mathbf{PC}_T| \ge k$ ), and the subsequent greedy orientation phase performs $k \cdot pc - \frac{k(k-1)}{2}$ scoring evaluations. The total statistical calls scale as: $O(n + 2^{pc})$
For sparse networks with fixed local connectivity $pc$ as the network size $n$ increases, MMHC requires approximately $O(n)$ calls per node compared to $O(kn)$ for Greedy Search.
Knowl 7 — Structural Error Propagation in the Sparse Candidate Algorithm
theoretical result
The Sparse Candidate (SC) algorithm enforces a uniform upper bound $k$ on the candidate parent set size $C(X)$ for every variable $X$ . If a node $X$ has $m > k$ true parents in the true network, at least $m - k$ true parents are omitted from $C(X)$ .

Because any true parent $Y$ is unconditionally or conditionally dependent on $X$ under faithfulness, the greedy search operator cannot add the true directed edge $Y \to X$ , and instead tends to insert the reversed edge $X \to Y$ to capture the statistical dependency in the score. The resulting erroneously directed edge $X \to Y$ induces spurious directed cycles with other true paths, preventing other legitimate edges from being added and propagating structural orientation and adjacency errors across non-local regions of the network.
Knowl 8 — Sample Non-Linearity and Low-Sample Degradation in the PC Algorithm
theoretical result
The PC algorithm exhibits non-monotonic behavior with respect to sample size due to initializing with a fully connected graph combined with minimum sample constraints on contingency tables:
1. At very small sample sizes, data are insufficient to meet the sample threshold for conditional tests involving a high-cardinality variable $X$ . PC skips testing and defaults to retaining the edge, keeping $X$ connected to every other node.
2. At slightly larger sample sizes, tests can be performed, but low statistical power prevents rejecting the null hypothesis of independence, leading to erroneous edge deletions.
3. At large sample sizes, tests achieve adequate power, correctly identifying true dependencies.
Furthermore, when a variable $X$ retains dense spurious connections because tests could not run, the orientation rule evaluates unshielded triples $Y - X - Z$ where $Y$ and $Z$ are non-adjacent. Because $X$ was never included in any conditioning separating set $\text{SepSet}(Y, Z)$ , PC misclassifies $X$ as a collider and orients $Y \to X \leftarrow Z$ , erroneously directing edges inward toward high-cardinality nodes throughout the graph.

Knowl 9 — Comparative Benchmark Performance of Bayesian Network Learning Algorithms

data/table

The table below presents the average normalized execution time, normalized number of statistical calls (independence tests and local score calculations), and normalized Structural Hamming Distance (SHD) across 22 benchmark Bayesian networks at sample sizes (SS) of 500, 1000, and 5000. Each metric is normalized by dividing the algorithm's raw value by MMHC's corresponding value on the same dataset (values $< 1.00$ indicate faster execution, fewer calls, or fewer structural errors than MMHC; values in parentheses denote the number of evaluated networks).

Metric and Algorithm	SS = 500	SS = 1000	SS = 5000	Average over SS
Normalized Time
MMHC	1.00 (22)	1.00 (22)	1.00 (22)	1.00
Optimal Reinsertion 1 ( $k=5$ )	1.29 (19)	1.16 (18)	1.18 (17)	1.21
Optimal Reinsertion 2 ( $k=5$ )	2.41 (19)	2.24 (18)	2.30 (16)	2.32
Sparse Candidate ( $k=5$ )	9.00 (21)	12.13 (22)	12.88 (18)	11.33
Sparse Candidate ( $k=10$ )	10.46 (13)	14.15 (13)	15.08 (13)	13.23
Greedy Search	10.94 (20)	11.20 (20)	8.13 (20)	10.09
PC	31.68 (18)	23.81 (18)	68.57 (20)	41.35
TPDA	20.05 (21)	6.89 (21)	0.71 (22)	9.21
GES	1128.77 (7)	343.55 (6)	167.06 (6)	546.46
Normalized Statistical Calls
MMHC	1.00 (22)	1.00 (22)	1.00 (22)	1.00
Greedy Search	2.94 (20)	2.54 (20)	1.55 (20)	2.34
PC	21.33 (18)	4.94 (18)	1.38 (20)	9.22
TPDA	2.41 (21)	1.33 (21)	0.42 (22)	1.38
Normalized SHD
MMHC	1.00 (22)	1.00 (22)	1.00 (22)	1.00
Optimal Reinsertion 1 ( $k=5$ )	1.30 (19)	1.45 (18)	1.70 (17)	1.48
Optimal Reinsertion 2 ( $k=5$ )	1.18 (19)	1.33 (18)	1.66 (16)	1.39
Sparse Candidate ( $k=5$ )	1.13 (21)	1.28 (22)	1.57 (18)	1.33
Sparse Candidate ( $k=10$ )	1.18 (13)	1.28 (13)	1.35 (13)	1.27
Greedy Search	1.62 (20)	2.08 (20)	1.86 (20)	1.85
PC	8.85 (18)	10.07 (18)	2.82 (20)	7.25
TPDA	9.63 (21)	10.22 (21)	1.76 (22)	7.21
GES	1.18 (7)	0.94 (6)	1.19 (6)	1.10

Across 792 individual learning tasks (12 comparative algorithms $\times$ 22 networks $\times$ 3 sample sizes), MMHC is outperformed simultaneously in both runtime and SHD in only 5 instances (0.63% of cases).

Knowl 10 — Empirical Scalability to Networks with Thousands of Variables
empirical result
MMHC was evaluated on an expanded Bayesian network created by tiling 135 copies of the ALARM network, yielding a structure with 4,995 variables and 6,845 edges, using 5,000 sampled cases. Reconstructing the full network required approximately 13 days of total single-CPU computing time (2.4 GHz Pentium Xeon, 2 GB RAM).

The restrict phase (skeleton identification via MMPC) finished in approximately 19 hours, while the greedy edge orientation phase consumed the remaining ~12 days. The resulting learned graph achieved a specificity of 99.9% (1,340 extra edges), a sensitivity of 84.0% (1,076 missing edges), and 1,468 orientation errors.

In a standalone skeleton evaluation on a 10,000-variable tiled network using 1,000 training instances, MMPC reconstructed the unoriented graph in 62 hours of single-CPU time (16 hours on 4 parallel CPUs), achieving 81.0% sensitivity (2,572 missing edges out of 13,640) and 99.9% specificity (11,068 extra edges).
Knowl 11 — Limitations of the MMHC Algorithm
limitation
The Max-Min Hill-Climbing algorithm operates under several theoretical and computational constraints:
1. Faithfulness Assumption: Correctness of the skeleton discovery phase requires the underlying distribution to be faithful (or locally faithful) to a DAG. MMHC cannot detect dependencies where a child is connected to parents via deterministic non-faithful interactions (e.g., parity or XOR relations).
2. Heuristic Edge Orientation: While the skeleton identification phase (MMPC) is sound in the sample limit, the subsequent edge orientation phase uses a greedy search-and-score heuristic that does not offer theoretical large-sample convergence guarantees.
3. Asymmetric Computational Bottleneck: For high-dimensional networks with thousands of variables, edge orientation dominates computation (e.g., consuming 12 out of 13 days on a 4,995-variable network), whereas skeleton discovery scales efficiently.
4. Distributional Scope: The implementation relies on discrete multinomial distributions using the $G^2$ statistic, requiring adaptation or continuous parametric tests (such as Fisher's $z$ -test) for continuous or mixed domains.

Coverage note — None was omitted; all key algorithms, theoretical correctness proofs, complexity analyses, error propagation mechanisms, empirical comparative benchmarks, scalability demonstrations, and limitations have been captured.

References

1.Abramson, B., Brown, J., Edwards, W., Murphy, A., & Winkler, R. L. (1996). Hailfinder: A Bayesian system for forecasting severe weather. International Journal of Forecasting, 12, 57–71.
2.Acid, S., de Campos, L., Fernandez-Luna, J., Rodriguez, S., Rodriguez, J., & Salcedo, J. (2004). A comparison of learning algorithms for Bayesian networks: A case study based on data from an emergency medical service. Artificial Intelligence in Medicine, 30, 215–232.
3.Acid, S., & de Campos, L. M. (2003). Searching for Bayesian network structures in the space of restricted acyclic partially directed graphs. Journal of Artificial Intelligence Research, 445–490.
4.Acid, S., & de Campos, L. (2001). A hybrid methodology for learning belief networks: BENEDICT. International Journal of Approximate Reasoning, 235–262.
5.Akaike, H. (1974). A new look at the statistical model identification. IEEE Transactions on Automatic Control, 19, 716–723.
6.Aliferis, C. F., Tsamardinos, I., Statnikov, A., & Brown, L. E. (2003a). Causal explorer: A causal probabilistic network learning toolkit for biomedical discovery. In International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences (METMBS ’03) (pp. 371–376).
7.Aliferis, C. F., Tsamardinos, I., & Statnikov, A. (2003b). HITON, A novel markov blanket algorithm for optimal variable selection. In American Medical Informatics Association (AMIA) (pp. 21–25).
8.Andreassen, S., Jensen, F. V., Andersen, S. K., Falck, B., Kharulff, U., & Woldbye, M. (1989). MUNIN—An expert EMG assistant. In J. E. Desmedt (Eds.), Computer-aided electromyography and expert systems.
9.Baeze-Yates, R., & Ribiero-Neto, B. (1999). Modern information retrieval. Addison-Wesley Pub Co.
10.Beal, M. J. & Ghahramani, Z. (2003). The variational Bayesian EM algorithm for incomplete data: With application to scoring graphical model structures. In J. M. Bernardo, M. J. Bayarri, J. O. Berger, A. P. Dawid, D. Heckerman, A. F. M. Smith, & M. West (Eds.), Bayesian statistics 7. Oxford University Press.
11.Beinlich, I. A., Suermondt, H., Chavez, R., Cooper, G., et al. (1989). The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks. In Second European Conference in Artificial Intelligence in Medicine.
12.Binder, J., Koller, D., Russell, S., & Kanazawa, K. (1997). Adaptive probabilistic networks with hidden variables. Machine Learning, 29.
13.Bouckaert, R. (1995). Bayesian belief networks from construction to inference. Ph.D. thesis, University of Utrecht.
14.Brown, L., Tsamardinos, I., & Aliferis, C. (2004). A novel algorithm for scalable and accurate bayesian network learning. In 11th World Congress on Medical Informatics (MEDINFO). San Francisco, California.
15.Brown, L. E., Tsamardinos, I., & Aliferis, C. F. (2005). A comparison of novel and state-of-the-art polynomial Bayesian network learning algorithms. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI).
16.Chapman, W. W., Fizman, M., Chapman, B. E. & Haug, P. J. (2001). A comparison of classification algorithms to automatically identify chest X-ray reports that support pneumonia. Journal of Biomedical Informatics, 34, 4–14.
17.Cheng, J., Bell, D., & Liu, W. (1998). Learning Bayesian networks from data: An efficient approach based on information theory. Technical report, University of Alberta, Canada.
18.Cheng, J., Greiner, R., Kelly, J., Bell, D. A. & Liu, W. (2002). Learning Bayesian networks from data: An information-theory based approach. Artificial Intelligence, 137, 43–90.
19.Chickering, D. (1995). A transformational characterization of equivalent Bayesian network structures. In Proceedings of the 11th Annual Conference on Uncertainty in Artificial Intelligence (UAI-95). San Francisco, CA (pp. 87–98). Morgan Kaufmann Publishers.
20.Chickering, D. (1996). Learning Bayesian networks is NP-complete. In D. Fisher and H. Lenz (Eds.), Learning from data: Artificial intelligence and statistics V (pp. 121–130) Springer-Verlag.
21.Chickering, D. (2002b). Learning equivalence classes of Bayesian-network structures. Journal of Machine Learning Research, 445–498.
22.Chickering, D., Geiger, D. & Heckerman, D. (1995). Learning Bayesian networks: Search methods and experimental results. In Fifth International Workshop on Artificial Intelligence and Statistics (pp. 112–128).
23.Chickering, D., Meek, C. & Heckerman D. (2004). Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research, 5, 1287–1330.
24.Chickering, D. M. (2002a). Optimal structure identification with greedy search. Journal of Machine Learning Research, 507–554.
25.Cooper, G. F., & Herskovits, E. (1992). A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9(4), 309–347.
26.Cowell, R. G., Dawid, A. P., Lauritzen, S. L., & Spiegelhalter, D. J. (1999). Probabilistic networks and expert systems. Springer.
27.Dash, D. (2005). Restructuring dynamic causal systems in equilibrium. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (AIStats 2005).
28.Dash, D. & Druzdzel, M. (1999). A hybrid anytime algorithm for the construction of causal models from sparse data. In Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI-99).
29.Dash, D., & Druzdzel, M. (2003). Robust independence testing for constraint-based learning of causal structure. In Proceedings of the Nineteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-03) (pp. 167–174), Morgan Kaufmann.
30.Dor, D., & Tarsi, M. (1992). A simple algorithm to construct a consistent extension of a partially oriented graph. Technicial Report R-185, Cognitive Systems Laboratory, UCLA.
31.Friedman, N. (1998). The Bayesian structural EM algorithm. In Proceedings of the 14th Annual Conference on Uncertainty in Artificial Intelligence (UAI-98). (pp. 129–138), San Francisco, CA, Morgan Kaufmann Publishers.
32.Friedman, N., Linial, M., Nachman, I., & Pe’er, D. (2000). Using Bayesian networks to analyze expression data. Computational Biology, 7, 601–620.
33.Friedman, N., Nachman, I., & Pe’er, D., (1999). Learning Bayesian network structure from massive datasets: The “sparse candidate” algorithm. In Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI-99).
34.Ghahramani, Z., & Beal, M. (2001). Graphical models and variational methods. In M. Opper, & D. Saad (Eds.), Advanced mean field methods—Theory and practice. MIT Press.
35.Glymour, C., & Cooper, G. F. (eds.) (1999). Computation, causation, and discovery. AAAI Press/The MIT Press.
36.Glymour, C. N. (2001). The mind’s arrows: Bayes nets & graphical causal models in psychology. MIT Press.
37.Goldenberg, A., & Moore, A. (2004). Tractable learning of large Bayes net structures from sparse data. In Proceedings of 21st International Conference on Machine Learning.
38.Heckerman, D. E., Geiger, D., & Chickering, D. M. (1995). Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20, 197–243.
39.Jensen, A., & Jensen, F. (1996). Midas—An influence diagram for management of mildew in winter wheat. In Proceedings of the 12th Annual Conference on Uncertainty in Artificial Intelligence (UAI-96) (pp. 349–356). Morgan Kaufmann Publishers.
40.Jensen, C. S. (1997). Blocking Gibbs sampling for inference in large and complex Bayesian networks with applications in genetics. Ph.D. thesis, Aalborg University, Denmark.
41.Jensen, C. S., & Kong, A. (1996). Blocking Gibbs sampling for linkage analysis in large pedigrees with many loops. Research Report R-96-2048, Department of Computer Science, Aalborg University, Denmark.
42.Jordan, M. I., Ghahramani, Z., T.S., J., & L.K., S. (1999). An introduction to variational methods for graphical models. Machine Learning, 37, 183–233.
43.Kocka, T., Bouckaert, R., & Studeny, M. (2001). On the inclusion problem. Technical report, Academy of Sciences of the Czech Republic.
44.Kovisto, M., & Sood, K. (2004). Exact Bayesian structure discovery in Bayesian networks. Journal of Machine Learning Research, 5, 549–573.
45.Koller, D., & Sahami, M. (1996). Toward optimal feature selection. In Thirteen International Conference in Machine Learning.
46.Komarek, P., & Moore, A. (2000). A dynamic adaptation of AD-trees for efficient machine learning on large data sets. In Proc. 17th International Conf. on Machine Learning (pp. 495–502). San Francisco, CA: Morgan Kaufmann.
47.Kristensen, K., & Rasmussen, I. A. (2002). The use of a Bayesian network in the design of a decision support system for growing malting barley without use of pesticides. Computers and Electronics in Agriculture, 33, 197–217.
48.Kullback, S., & Leibler, R. (1951). On information and sufficiency. Annals of Mathematical Statistics, 22, 79–86.
49.Margaritis, D., & Thrun, S. (1999). Bayesian network induction via local neighborhoods. In Advances in Neural Information Processing Systems 12 (NIPS).
50.Margaritis, D., & Thrun, S. (2001). A Bayesian multiresolution independence test for continuous variables. In 17th Conference on Uncertainty in Artificial Intelligence (UAI).
51.Meek, C. (1995). Strong completeness and faithfulnes in Bayesian networks. In Conference on Uncertainty in Artificial Intelligence 411–418.
52.Meek, C. (1997). Graphical models: Selecting causal and statistical models. Ph.D. thesis, Carnegie Mellon University.
53.Moore, A., & Lee, M. (1998). Cached sufficient statistics for efficient machine learning with large datasets. Journal of Artificial Intelligence Research, 8, 67–91.
54.Moore, A., & Schneider, J. (2002). Real-valued all-dimensions search: Low-overhead rapid searching over subsets of attributes. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI-2002) (pp. 360–369).
55.Moore, A., & Wong, W. (2003). Optimal reinsertion: A new search operator for accelerated and more accurate Bayesian network structure learning. In Twentieth International Conference on Machine Learning (ICML-2003).
56.Neapolitan, R. (2003). Learning Bayesian networks. Prentice Hall.
57.Nielson, J., Kocka, T., & Pena, J. (2003). On local optima in learning bayesian networks. In Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence, 435–442.
58.Pearl, J. (1988). Probabilistic reasoning in intelligent systems. San Mateo, CA: Morgan Kaufmann.
59.Pearl, J. (2000). Causality, models, reasoning, and inference. Cambridge University Press.
60.Pearl, J., & Verma, T. (1991). A theory of inferred causation. In J. F. Allen, R. Fikes, & E. Sandewall (Eds.), KR’91: Principles of knowledge representation and reasoning (pp. 441–452). San Mateo, California: Morgan Kaufmann.
61.Peterson, W., TG, B., & Fox, W. (1954). The theory of signal detectability. IRE Professional Group on Information Theory PGIT-4, 171–212.
62.Rissanen, J. (1978). Modeling by shortest data description. Automatica, 14, 465–671.
63.Rissanen, J. (1987). Stochastic complexity. Journal of the Royal Statistical Soceity, Series B, 49, 223–239.
64.Schwarz, G. (1978). Estimating the dimension of a model. The Annals of Statistics, 6, 461–464.
65.Silverstein, C., Brin, S., Motwani, R., & Ullman, J. (2000). Scalable techniques for mining causal structures. Data Mining and Knowledge Discovery, 4(2/3), 163–192.
66.Singh, M., & Valtorta, M. (1993). An algorithm for the construction of Bayesian network structures from data. In 9th Conference on Uncertainty in Artificial Intelligence, pp. 259–265.
67.Spellman, P. T., Sherlock, G., Zhang, M. Q., Iyer, V. R., Anders, K. et al. & Eisen, M. B. (1998). Comprehensive identification of cell cycle regulated genes of the yeast saccharomyces cerevisiae by microarray hybridization. Molecular Biology of the Cell, 9, 3273–3297.
68.Spirtes, P., Glymour, C., & Scheines, R. (1990). Causality from probability. In J. Tiles, G. McKee, & G. Dean (eds.): Evolving knowledge in the natural and behavioral sciences (pp. 181–199). London: Pittman.
69.Spirtes, P., Glymour, C. & Scheines, R. (1993). Causation, prediction, and search. Springer/Verlag, first edition.
70.Spirtes, P., Glymour, C., & Scheines, R. (2000). Causation, prediction, and search. The MIT Press, second edition.
71.Spirtes, P., & Meek, C. (1995). Learning Bayesian networks with discrete variables from data. In Proceedings from First Annual Conference on Knowledge Discovery and Data Mining (pp. 294–299). Morgan Kaufmann.
72.Statnikov, A., Tsamardinos, I., & Aliferis, C. F. (2003). An algorithm for the generation of large Bayesian networks. Technical Report DSL-03-01, Vanderbilt University.
73.Steck, H., & Jaakkola, T. (2002). On the dirichlet prior and Bayesian regularization. In Advances in Neural Information Processing Systems, 15.
74.Tsamardinos, I., & Aliferis, C. F. (2003). Towards principled feature selection: Relevancy, filters and wrappers. In Ninth International Workshop on Artificial Intelligence and Statistics (AI & Stats 2003).
75.Tsamardinos, I., Aliferis, C. F., & Statnikov, A. (2003b). Algorithms for large scale markov blanket discovery. In The 16th International FLAIRS Conference (pp. 376–381).
76.Tsamardinos, I., Aliferis, C. F., & Statnikov, A. (2003c). Time and sample efficient discovery of Markov blankets and direct causal relations. In The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 673–678).
77.Tsamardinos, I., Aliferis, C. F., & Statnikov, A. (2003a). Time and sample efficient discovery of Markov Blankets and direct causal relations. Technical Report DSL-03-02, Vanderbilt University.
78.Tsamardinos, I., Aliferis, C. F., Statnikov, A., & Brown. L. E. (2003a). Scaling-Up Bayesian network learning to thousands of variables using local Learning Technique. Technical Report DSL TR-03-02, Dept. Biomedical Informatics, Vanderbilt University.
79.Tsamardinos, I., Statnikov, A., Brown, L. E., and Aliferis, C. F. (2006) Generating realistic large bayesian networks by tiling. In The 19th International FLAIRS Conference (to appear).
80.Verma, T., & Pearl, J. (1988). Causal networks: Semantics and expressiveness. In: 4th Workshop on Uncertainty in Artificial Intelligence.
81.Verma, T., & Pearl, J. (1990). Equivalence and synthesis of causal models. In Proceedins of 6th Annual Conference on Uncertainty in Artificial Intelligence (pp. 255–268). Elsevier Science.

Citation

MLA

Tsamardinos, I., et al. “The Max-min Hill-climbing Bayesian Network Structure Learning Algorithm”. Machine Learning, vol. 65, no. 1, 2006, pp. 31–78, https://doi.org/10.1007/s10994-006-6889-7.

APA

Tsamardinos, I., Brown, L. E., & Aliferis, C. F. (2006). The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 65(1), 31–78. https://doi.org/10.1007/s10994-006-6889-7

Chicago

Tsamardinos, I., L. E. Brown, and C. F. Aliferis. 2006. “The Max-min Hill-climbing Bayesian Network Structure Learning Algorithm”. Machine Learning 65 (1): 31–78. https://doi.org/10.1007/s10994-006-6889-7.

Harvard

Tsamardinos, I., Brown, L.E. and Aliferis, C.F. (2006) “The max-min hill-climbing Bayesian network structure learning algorithm”, Machine Learning, 65(1), pp. 31–78. Available at: https://doi.org/10.1007/s10994-006-6889-7.

Vancouver

1. Tsamardinos I, Brown LE, Aliferis CF (2006) The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning 65:31–78

BibTeX

@article{Tsamardinos_2006, title={The max-min hill-climbing Bayesian network structure learning algorithm}, volume={65}, ISSN={1573-0565}, url={http://dx.doi.org/10.1007/s10994-006-6889-7}, DOI={10.1007/s10994-006-6889-7}, number={1}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Tsamardinos, Ioannis and Brown, Laura E. and Aliferis, Constantin F.}, year={2006}, month=Mar, pages={31–78} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

The max-min hill-climbing Bayesian network structure learning algorithm

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Max-Min Hill-Climbing Algorithm

Knowl 2 — Max-Min Parents and Children Algorithm

Knowl 3 — Soundness of the MMPC Algorithm

Knowl 4 — Structural Hamming Distance for Bayesian Network Evaluation

Knowl 5 — Computational Complexity of MMPC and Skeleton Identification

Knowl 6 — Scaling of Statistical Scoring Calls in MMHC Versus Greedy Search

Knowl 7 — Structural Error Propagation in the Sparse Candidate Algorithm

Knowl 8 — Sample Non-Linearity and Low-Sample Degradation in the PC Algorithm