Greedy Search-And-Score Structure Learning

The greedy search-and-score algorithm for learning the structure of a Bayesian network uses a score function to evaluate the goodness of a candidate network structure. The algorithm performs a search through the space of possible network structures and returns the structure with the highest score. The operators used to perform the search given a current candidate are add an arc, remove an arc and reverse an arc.

The candidate network structure is provided with a maximum likelihood estimate of the conditional probability tables associated with the nodes of the network in order to compute the score of the candidate structure. If the data is incomplete, the EM algorithm must be used. However, if the data is complete, this can be done by counting cases and normalizing the counts.

For simplicity, we assume that the data is complete (by ignoring the missing data).

We also assume that the score function is decomposable. This means that the total score can be computed as a sum of scores of the nodes in the network. This makes it easy to compute the effect of a simple modification to the network (such as adding or removing an edge).

The user can chouse between using the Akaike Information Criterion (AIC) or the Bayesian Information Criterion (BIC) as the score function.

The user can specify an upper limit on the number of parents of each node in the network structure.