bnt-master.zip

Journal of Machine Learning Research ? (2008) 1-?? Submitted 4/08; Published ??/08

BNT STRUCTURE LEARNING PACKAGE :

Documentation and Experiments

Olivier C.H. FRANCOIS Francois.Olivier.C.H@gmail.com

Sustainable Urban Environments Research Division, URS building, Room 3n38,

Whiteknights, PO Box 219, Reading, RG6 6AW, UK

http: // ofrancois. tuxfamily. org

Philippe LERAY Philippe.Leray@univ-nantes.fr

Ecole Polytechnique de l’Université de Nantes,

creasingly popular for tasks such as classification in data-mining. In some situations,

the structure of the Bayesian network can be given by an expert. If not, retrieving

it automatically from a database of cases is a NP-hard problem; notably because of

the complexity of the search space. In the last decade, numerous methods have been

introduced to learn the network’s structure automatically, by simplifying the search

space or by using an heuristic in the search space. Most methods deal with completely

observed data, but some can deal with incomplete data. The Bayes Net Toolbox for

Matlab, introduced by Murphy (2004), offers functions for both using and learning

Bayesian Networks. But this toolbox is not ’state of the art’ as regards structural

learning methods. This is why we propose the SLP package.

A Bayesian network B represents a probability distribution over X which admits the

following joint distribution decomposition:

This decomposition allows the use of some powerful inference algorithms for which

Bayesian networks became simple modeling and reasoning tools when the situation is

c

FRANÇOIS AND LERAY

uncertain or the data are incomplete. Bayesian networks are also practical for classifi-

cation problems when interactions between features can be modelized with conditional

probabilities. When the network structure is not given (by an expert), it is possible to

• TETRAD Spirtes et al. (2004)

• Causal explorer Tsamardinos et al.

(2005)

• LibB Friedman and Elidan (1999)

• BNPC Cheng et al. (2001)

• Web WeavR Xiang (1999)

• ProBayes Mazer et al. (2004)

• BayesiaLab Munteanu et al. (2001)

• Hugin Andersen et al. (1989)

• Netica Netica (1998)

• Bayes Builder Nijman et al. (2002)

cepts concerning Bayesian network structures, how to evaluate these structures and

some interesting properties of scoring functions. In section 3, we describe the common

methods used in structure learning; from causality search to heuristic searches in the

Bayesian network space. We also discuss the initialization problems of such methods.

In section 4, we compare these methods using two series of tests. In the first series,

we try to retrieve a known structure while the other tests aim at obtaining a good

Bayesian network for classification tasks. We then conclude on the respective advan-

tages and drawbacks of each method or family of methods before discussing future

relevant research. We describe the syntax of a function as follows.

Ver

2. Preliminaries

2.1 Exhaustive search and score decomposability

The first (but naive) idea as to finding the best network structure is the exploration

and evaluation of all possible graphs in order to choose the best structure. Robinson

Robinson (1977) has proven that r(n), the number of different structures for a Bayesian

network with n nodes, is given by the recursive formula of equation 2.

This equation gives r(2) = 3, r(3) = 25, r(5) = 29281, r(10) ' 4, 2 × 10

BNT

Since equation 2 is super exponential, it is impossible to perform an exhaustive

search in a decent time as soon as the node number exceeds 7 or 8. So, structure

of vertices in the graph, a decomposable score S must be the sum of local scores s:

2.2 Markov equivalent set and Completed-PDAGs

is equivalent to the first one. The space of Completed-PDAGs (CPDAGs or also named

essential graphs) is defined as the set of Partially Directed Acyclic Graphs (PDAGs) that

have only undirected arcs and unreversible directed arcs.

For instance, as Bayes’ rule gives

those structures,

/.-,()*+

'&%$ !"#

oo //

'&%$ !"#

/.-,()*+

'&%$ !"#

'&%$ !"#

oo

, are equivalent

But they are not equivalent to

(where P (A, B, C) = P(A)P(B|A, C)P(C) ) for

which the corresponding CPDAG is the same graph, which is named a V-structure.

FRANÇOIS AND LERAY

Verma and Pearl (1990) have proven that DAGs are equivalent if, and only if, they

have the same skeleton (i.e. the same edge support) and the same set of V-structures

(like

The BIC-score is the sum of a likelihood term and a penalty term which penalizes

complex networks. As two equivalent graphs have the same likelihood and the same

complexity, the BIC-score is equivalent. Using scores with these properties, it becomes