Abstract

The basic idea of an algebraic approach to learning Bayesian network (BN) structures is to represent every BN structure by a certain uniquely determined vector, called the standard imset. In a recent paper (Studeny, Vomlel, Hemmecke 2010), it was shown that the set S of standard imsets is the set of vertices (= extreme points) of a certain polytope P and natural geometric neighborhood for standard imsets, and, consequently, for BN structures, was introduced. The new geometric view led to a series of open mathematical questions. In this paper, we try to answer some of them. First, we introduce a class of necessary linear constraints on standard imsets and formulate a conjecture that these constraints characterize the polytope P. The conjecture has been confirmed in the case of (at most) 4 variables. Second, we confirm a former hypothesis by Raymond Hemmecke that the only lattice points (= vectors having integers as components) within P are standard imsets. Third, we give a partial analysis of the geometric neighborhood in the case of 4 variables.

AMS classification 68T30, 62H05

Keywords

structural learning Bayesian nets

standard imset

polytope

geometric neighborhood

differential imset

A pdf version of the published paper (262kB) is already open-access available.

The paper builds on resuls from the following publications:

• M. Studeny (2005). Probabilistic Conditional Independence Structures. London: Springer-Verlag.
• 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.