M. Studeny, J. Vomlel, R. Hemmecke:
Geometric view on learning Bayesian network structures.
International Journal of Approximate Reasoning
51 (2010), n. 5, pp. 578-586.
- Abstract
-
We recall the basic idea of an algebraic approach to learning
Bayesian network (BN) structure, namely to represent every BN
structure by a certain (uniquely determined) vector, called the
standard imset.
The main result of the paper is that the set of standard imsets is
the set of vertices (= extreme points) of a certain polytope.
Motivated by the geometric view, we introduce the concept of the
geometric neighborhood for standard imsets, and,
consequently, for BN structures. Then we show it always includes
the inclusion neighborhood, which was introduced earlier
in connection with the greedy equivalence search (GES) algorithm.
The third result is that the global optimum of an affine function
over the polytope coincides with the local optimum relative to the
geometric neighborhood.
To illustrate the new concept by an example, we describe the
geometric neighborhood in the case of three variables and show it
differs from the inclusion neighborhood. This leads to a simple
example of the failure of the GES algorithm if data are not ``generated"
from a perfectly Markovian distribution. The point is that one can
avoid this failure if the search technique is based on the geometric
neighborhood instead. We also found out what is the geometric neighborhood
in the case of four and five variables.
- AMS classification 68T30, 62H05
- Keywords
- learning Bayesian networks
- standard imset
- inclusion neighborhood
- geometric neighborhood
- GES algorithm
- A
pdf version of the published paper (402kB) is already open-access available.
A related document is also an earlier web page prepared by J. Vomlel, named
Geometric neighborhood for Bayesian network structures .., from which
one can download text files describing the geometric neighborhood in the case three, four, and
five variables. These files were results of computations by J. Vomlel and R. Hemmecke.
The paper comes from (and extends substantially) the observations in the conference paper:
Thus, like the original conference paper, the paper refers to results from the following publications:
- M. Studeny (2005). Probabilistic Conditional Independence
Structures. London: Springer-Verlag.
- D. M. Chickering:
Optimal structure indentification with greedy search.
Journal of Machine Learning Research 3 (2002), pp. 507-554.