TY - JOUR

T1 - A geometric view on learning Bayesian network structures

AU - Studený, Milan

AU - Vomlel, Jiří

AU - Hemmecke, Raymond

PY - 2010/6

Y1 - 2010/6

N2 - We recall the basic idea of an algebraic approach to learning Bayesian network (BN) structures, namely to represent every BN structure by a certain (uniquely determined) vector, called a 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 that 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.

AB - We recall the basic idea of an algebraic approach to learning Bayesian network (BN) structures, namely to represent every BN structure by a certain (uniquely determined) vector, called a 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 that 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.

KW - GES algorithm

KW - Geometric neighborhood

KW - Inclusion neighborhood

KW - Learning Bayesian networks

KW - Standard imset

UR - http://www.scopus.com/inward/record.url?scp=77955230142&partnerID=8YFLogxK

U2 - 10.1016/j.ijar.2010.01.014

DO - 10.1016/j.ijar.2010.01.014

M3 - Article

AN - SCOPUS:77955230142

SN - 0888-613X

VL - 51

SP - 573

EP - 586

JO - International Journal of Approximate Reasoning

JF - International Journal of Approximate Reasoning

IS - 5

ER -