M. Studeny, J. Vomlel: On open questions in the geometric approach to structural learning Bayesian nets. International Journal of Approximate Reasoning 52 (2011), n. 5, pp. 627-640.

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

structural learning Bayesian nets
standard imset
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: