An Algorithm for the Construction of Bayesian Network Structures from Data

Moninder Singh, Marco ValtortaUAI 1993

TL;DR

This paper introduces a novel algorithm, "CB," that integrates conditional independence (CI) tests with a Bayesian approach to construct Bayesian network structures from data. By using CI tests to generate a node ordering, CB overcomes the limitations of purely CI-based methods and the need for user-provided orderings, leading to more efficient and accurate network discovery.

What Problem Does This Paper Address?

Learning the structure of Bayesian networks from data is a fundamental problem in artificial intelligence and statistics. Existing methods generally fall into three categories: those relying on linearity and normality assumptions, those based on extensive conditional independence (CI) testing, and Bayesian methods. CI-based methods, while general, suffer from computational intractability as the number of variables grows and can be unreliable with limited data. Bayesian methods, like Cooper and Herskovits's K2 algorithm, are more robust but typically require a pre-defined ordering of the nodes, which can be difficult to obtain without domain expertise or can lead to suboptimal structures if the ordering is poor. This paper aims to bridge this gap by developing an algorithm that automatically generates a suitable node ordering using CI tests, thereby enabling a more efficient and less user-dependent Bayesian network structure learning process.

Methods

The proposed algorithm, "CB" (Conditional Independence-based Bayesian), combines CI tests and a Bayesian approach in two phases:

  • Phase I: Generating a Node Ordering: This phase uses CI tests to construct an undirected graph. Edges are then oriented based on specific rules derived from CI relations and the concept of a "partial order" consistent with a Directed Acyclic Graph (DAG). This process aims to create an ordering that reflects the underlying dependencies in the data.
  • Phase II: Bayesian Network Construction: This phase takes the DAG generated in Phase I and uses the K2 algorithm (a Bayesian method) to learn the Bayesian network structure. K2, given a node ordering, greedily searches for parent sets that maximize a specific probability metric. The CB algorithm modifies K2 to work with the partial order derived from Phase I, rather than a strict total order.

The algorithm iteratively refines the CI tests and graph orientation, aiming to find a structure that is both consistent with the data and as sparse as possible.

Datasets

The paper evaluates the CB algorithm on two benchmark datasets:

  • ALARM Network: A well-known network used for medical monitoring. The authors generated 10,000 cases from this network.
  • LED Network: A smaller network used to represent faulty LED displays. The authors used a database of 199 cases for this network.

Key Insights and Ideas

  • Synergistic Integration: The core idea is that CI tests can be effectively used to guide a Bayesian learner, overcoming the limitations of each approach when used in isolation. CI tests help establish a reasonable node ordering, which is crucial for the efficiency and accuracy of Bayesian methods like K2.
  • Automated Ordering: By generating a node ordering from the data itself, the algorithm removes the burden on the user to provide this potentially difficult-to-obtain information.
  • Partial Order for K2: Using a partial order derived from the CI-based phase, rather than a strict total order, allows K2 to explore a more constrained but still effective search space, potentially leading to better results and faster computation.
  • Heuristic for Edge Orientation: When faced with undirected edges that cannot be definitively oriented by CI tests, the algorithm uses a heuristic based on maximizing a probability metric (derived from the K2 metric) to choose an orientation, balancing computational feasibility with accuracy.

Key Results

  • ALARM Network: Using CI tests up to order 2, the CB algorithm recovered 45 out of 46 edges from the ALARM network with only two incorrectly oriented edges and 14 extra edges. When a modified version of CB was used with a partial order (skipping a step to enforce total order), it recovered 44 edges with 2 extra edges and 2 incorrectly oriented edges, in less time.
  • LED Network: For the LED network, CB reconstructed the network with 3 edges incorrectly oriented and one extra edge, using CI tests up to order 1, in less than a second. The modified version of CB (using partial order) recovered the same network with no extra edges.
  • Efficiency: The algorithm demonstrated significant speedups, particularly the modified version, reducing computation time considerably. The authors note that the algorithm is polynomial for sparse graphs, and their results suggest it can recover complex structures in polynomial time in practice due to low-order CI tests being sufficient.

Limitations and Future Work

  • Computational Complexity: While the algorithm is polynomial for sparse graphs, the worst-case complexity can still be exponential in the number of variables, especially if high-order CI tests are required.
  • Greedy Search: The K2 algorithm's greedy parent selection does not guarantee optimality, although the underlying metric is exact.
  • Heuristic Sensitivity: The quality of the recovered network structure is sensitive to the ordering determined by Phase I and the heuristics used for edge orientation.
  • Fixed Alpha Level: The use of a fixed alpha level for CI tests might introduce spurious dependencies.
  • Future Work: The authors plan to test the algorithm on larger, unknown databases, explore alternative search methods beyond greedy search (e.g., simulated annealing), develop better heuristics for edge orientation, investigate parallelization of the algorithm, and explore alternative stopping criteria.

Summary updated

BibTeX
@inproceedings{singh1993algorithm,
  author = {Moninder Singh and Marco Valtorta},
  title = {{An Algorithm for the Construction of Bayesian Network Structures from Data}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1993},
}
Figure