M. Studeny, J. Vomlel:
A geometric approach to learning BN structures
In Proceedings of the 4th
European Workshop on Probabilistic Graphical Models
(M. Jaeger,T. D. Nielsen eds.), University of Aalborg, 2008, pp. 281-288.
- Abstract
-
We recall the basic idea of an algebraic approach to learning a
Bayesian network (BN) structure, namely to represent every BN
structure by a certain (uniquely determined) vector, called
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. To illustrate this
concept by an example, we describe the geometric neighborhood in
the case of three variables and show it differs from the
inclusion neighborhood, which was introduced earlier in
connection with the GES algorithm. This leads to an 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 greedy search technique is based on the geometric
neighborhood instead.
- AMS classification 68T30
- Keywords
- standard imset
- inclusion neighborhood
- geometric neighborhood
-
A
scanned pdf copy (691kB) is available.
The contribution 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.