# A Transformational Characterization of Equivalent Bayesian Network Structures

@inproceedings{Chickering1995ATC, title={A Transformational Characterization of Equivalent Bayesian Network Structures}, author={David Maxwell Chickering}, booktitle={UAI}, year={1995} }

We present a simple characterization of equivalent Bayesian network structures based on local transformations. The significance of the characterization is twofold. First, we are able to easily prove several new invariant properties of theoretical interest for equivalent structures. Second, we use the characterization to derive an efficient algorithm that identifies all of the compelled edges in a structure. Compelled edge identification is of particular importance for learning Bayesian network… Expand

#### 369 Citations

An Algebraic Characterization of Equivalent Bayesian Networks

- Computer Science
- Intelligent Information Processing
- 2002

The new proposed algebraic characterization of Bayesian networks is derived from its intrinsic algebraic structure, i.e., the factorization of its joint probability distribution, and suggests simple and efficient methods for determining equivalence ofBayesian networks and identifying compelled edges in Bayesian Networks. Expand

A Characterisation of Bayesian Network Structures and its Application to · Learning

- 2021

We present an analysis of the minimal !map relation between Bayesian network structures and dependency models. This includes a partial order characterisation of the structures, and the connection… Expand

A Simple Method for Identifying Compelled Edges in DAGs

- Computer Science
- FLAIRS Conference
- 2003

It is shown that a joint probability distribution defined by a Bayesian network can be uniquely characterized by its intrinsic factorization. Expand

A comparison of structural distance measures for causal Bayesian network models

- Mathematics
- 2009

We compare measures of structural distance between both, Bayesian networks Aand equivalence classes of Bayesian networks. The main application of these measures is in learning algorithms, where… Expand

Learning Equivalence Classes of Bayesian-Network Structures

- Computer Science, Mathematics
- J. Mach. Learn. Res.
- 2002

It is argued that it is often appropriate to search among equivalence classes of network structures as opposed to the more common approach of searching among individual Bayesian-network structures, and a convenient graphical representation for an equivalence class of structures is described and a set of operators that can be applied to that representation by a search algorithm to move among equivalENCE classes are introduced. Expand

Structural Markov graph laws for Bayesian model uncertainty

- Mathematics
- 2015

This paper considers the problem of defining distributions over graphical structures. We propose an extension of the hyper Markov properties of Dawid and Lauritzen [Ann. Statist. 21 (1993)… Expand

On the Use of Skeletons when Learning in Bayesian Networks

- Computer Science, Mathematics
- UAI
- 2000

A heuristic operator which aims at simultaneously optimizing the orientations of all the edges in an intermediate Bayesian network structure during the search process by alternating between directed acyclic graphs (DAGs) and the space of skeletons. Expand

On characterizing Inclusion of Bayesian Networks

- Mathematics, Computer Science
- UAI
- 2001

Several characterizations of inclusion of DAG models are given and Meek's conjecture in the case that the DAGs K and L differ in at most one adjacency is verified. Expand

On Inclusion-Driven Learning of Bayesian Networks

- Mathematics, Computer Science
- J. Mach. Learn. Res.
- 2003

This paper introduces a condition for traversal operators, the inclusion boundary condition, which guarantees that the search strategy can avoid local maxima and carries out a set of experiments that show empirically the benefit of striving for the inclusion order when learning Bayesian networks from data. Expand

The marginal factorization of Bayesian networks and its application

- Mathematics, Computer Science
- Int. J. Intell. Syst.
- 2004

This article proposes an algebraic characterization of equivalent DAGs based on the marginal factorization of a jpd defined by a Bayesian network and shows a simple method to identify all the compelled edges in a DAG. Expand

#### References

SHOWING 1-10 OF 34 REFERENCES

Learning Equivalence Classes of Bayesian-Network Structures

- Computer Science, Mathematics
- J. Mach. Learn. Res.
- 1996

It is argued that it is often appropriate to search among equivalence classes of network structures as opposed to the more common approach of searching among individual Bayesian-network structures, and a convenient graphical representation for an equivalence class of structures is described and a set of operators that can be applied to that representation by a search algorithm to move among equivalENCE classes are introduced. Expand

Probalistic Network Construction Using the Minimum Description Length Principle

- Mathematics, Computer Science
- ECSQARU
- 1993

This paper presents a procedure for the construction of probabilistic networks from a database of observations based on the minimum description length principle, and preliminary test results show that the algorithm performs comparable to the algorithmbased on the Bayesian approach. Expand

Using Causal Information and Local Measures to Learn Bayesian Networks

- Mathematics, Computer Science
- UAI
- 1993

A new local way of computing the description length is presented, which allows for significant improvements in the search algorithm and opens the door for local refinement of an existent network. Expand

Learning Bayesian Networks: Search Methods and Experimental Results

- Computer Science
- 1995

A metric for computing the relative posterior probability of a network structure given data developed by Heckerman et al. (1994a,b,c) has a property useful for inferring causation from data and is described. Expand

A characterization of Markov equivalence classes for acyclic digraphs

- Mathematics
- 1997

Undirected graphs and acyclic digraphs (ADGs), as well as their mutual extension to chain graphs, are widely used to describe dependencies among variables in multivariate distributions. In… Expand

Equivalence and synthesis of causal models

- Computer Science
- UAI
- 1990

A canonical representation for causal models is presented which yields an efficient graphical crite rion for deciding equivalence, and provides a theoret ical basis for extracting causal structures from em pirical data. Expand

Causation, prediction, and search

- Mathematics
- 1993

What assumptions and methods allow us to turn observations into causal knowledge, and how can even incomplete causal knowledge be used in planning and prediction to influence and control our… Expand

A simple algorithm to construct a consistent extension of a partially oriented graph

- Mathematics
- 1992

A Partially directed acyclic graph, (pdag), is a graph which contains both directed and undirected edges, with no directed cycle in its directed subgraph. An oriented extension of a pdag G is a fully… Expand

An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation

- Computer Science, Mathematics
- UAI
- 1992

This paper addresses the question of whether there exists a causal model that explains ALL the observed dependencies and independencies and presents an algorithm which decides for an ar- bitrary list of conditional independence statements whether it defines a dag and, if it does, a correspond- ing dag is drawn. Expand

A new look at the statistical model identification

- Mathematics
- 1974

The history of the development of statistical hypothesis testing in time series analysis is reviewed briefly and it is pointed out that the hypothesis testing procedure is not adequately defined as… Expand