Abstract

Several approaches to learning Bayesian networks use the idea of a score metric S(G,D) which measures how the model determined by a graph G fits data D. Given data D, the goal is to maximize this function over G's. Natural assumption is that S ascribes the same value to equivalent graphs, that is, to graphs defining the same statistical model. This is fulfilled for the most popular BIC criterion and the criteria used in Bayesian approach to learning Bayesian networks. These metrics are also decomposable which means that they factorize according to the graph in a certain way. Several recent papers came with an idea to maximize score metric by the method of local search. To use this method, the main problem is to represent respective statistical models by suitable objects of discrete mathematics which can be handled by a computer. Traditional methods use acyclic (partially) directed graphs for this purpose. This contribution comes with an idea to use certain integer-valued vectors, named standard imsets instead. The novelty of this approach is that it brings an algebraic point of view which can perhaps be utilized in computer implementation. More exactly,

• the value of every decomposable score metric is nothing but the scalar product of a certain vector (depending on data) with the respective integer-valued vector,
• even the moves in the respective (inlusion neighbourhood) search space (utilized by the method of local search) can be evaluated by certain {-1,0,+1}-vectors, named elementary vectors, which have the intepretation of elementary conditional independence statements.

Inclusion between statistical models corresponds to certain (linear) algebraic relation between respective structural imsets.

AMS classification 68T30, 62H05

Keywords

score metric

learning Bayesian networks

standard (structural) imset

A pdf version (converted postscript version) of posters (294kB) is available.

The poster builds on the Chapter 8 of the (later published) monograph:

• M. Studeny: Probabilistic Conditional Independence Structures. Springer-Verlag, London, 2005.