Search strategies for Bayes network structure learning

The problem: A Bayes B net consists of two parts, a network structure B_S and a set of probability tables B_P. Learning a Bayes net from data therefore consists of two subtasks: learning B_S and learning B_P. There are super exponential (in the number of variables) many network structures to be considered, so efficient search of the space of network structures is required.

Observation: Often, a metric for the quality Q(B_S) of a network structure is used that can be decomposed into the effect of each of the nodes (plus parents), i.e., Q(B_S) = å_u in U q(u, p(u)) (where p(u) is the set of parents of u). This has the benefit that for operations like arc reversal, arc insertion and arc removal, which affect only one term in the sum, the quality of the new network structure can be efficiently calculated: at most two terms in the sum have to be recalculated. However, it is very difficult to proof optimality of search strategies based on these operations.

Friedman and Koller use an approach where the space is structured by considering orderings on the variables and only allowing network structures that conform to the ordering (i.e., an arrow u->v is only allowed when u>v according to the ordering). According to Friedman and Koller, the space of orderings is much smaller and more regular than the space of structures, and has a smoother posterior `landscape'. The most obvious operations on orderings are swapping of consequtively ordered variabels. Another, used in Friedman and Koller is selecting a node u_i at random, and swap the lot before to that after, that is, u₁...u_iu_i+1...u_n => u_i+1...u_nu₁...u_i.

How to exploit this: Other operations on ordering can be defined. To mention just a few:

Pick a node u_i at random and put it at the end of the ordering, u₁...u_i-1u_iu_i+1...u_n => u₁...u_i-1u_i+1...u_nu_i. This affects u_i and all nodes that have u_i in their parent set.
Pick a node u_i at random and put it at the beginning of the ordering, u₁...u_i-1u_iu_i+1...u_n => u_iu₁...u_i-1u_i+1...u_n. This affects u_i and all nodes that have u_i in their parent set. However, it is clear that p(u_i)={}, so no search is required to calculate optiomal parent set of u_i.
Pick a node u_i at random and do a full search on any ordering on u_i and its parents p(u_i). In an ideal world where unlimited data is available, it is expected that optimizating the number of arcs takes place by reordering cliques. In the less ideal world, such cliques do not form because lack of data does not justify adding arrows while actual dependencies are in the underlying distribution. A surrogate suggested here is to look at nodes and their parents instead.
Pick two nodes u_i u_j at random and reverse the order of the nodes in between, u₁...u_i-1u_iu_i+1...u_j-1u_ju_j+1...u_n => u₁...u_i-1u_ju_j-1...u_i+1u_iu_j+1...u_n
Pick two nodes u_i u_j at random and swap them u₁...u_i-1u_iu_i+1...u_j-1u_ju_j+1...u_n => u₁...u_i-1u_ju_i+1...u_j-1u_iu_j+1...u_n

Note that those operations can still to a large extend use local computations of the quality of a network since a lot of optimizations can be performed in determining the new network structure. For example, if two nodes are swapped and those nodes are not connected in the old network structure, the new network structure equals the old one.

Open problems

Interesting operations: Can other interestion operations be defined and which criteria make an operation interesting? One obvious criterion is how much computational effort is required to determine the quality of the newly created network structure. Another criterion is how easy it is to traverse the search space defined by the operation. Finally, the theoretical properties with respect to existance of convergence of search algorithms and speed of convergence make an operation of interest.

Theoretical properties: What can be said about optimality and speed of convergence of search algorithms based on the new operations.

Experimental behavior: How do the operations behave on data?

Any comment? Pleas mail to Remco.

1: Nir Friedman, Daphne Koller. Being Bayesian about Network Structure Uncertainty in Artificial Intelligence: Proceedings of the Sixteenth Conference, Craig Boutilier and Moises Goldszmidt (editors). Stanford University, Stanford, California, USA, Jun 30 2000 -- Jul 3 2000. © 2000 Morgan Kaufmann Publishers, San Francisco, CA.

Initial update: 9 Jan 2001 webmaster