M. Studeny:
An algebraic approach to learning Bayesian networks.
In the book of abstracts of the 7th International Valencia
Meeting on Bayesian Statistics, Playa de las Americas, Tenerife,
Spain, June 1-6, 2002, p.179.
- 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.