Geometric neighborhood
for Bayesian network structures over three and four
variables
The method
As it is described in a draft paper
M. Studený, J. Vomlel
(2008). Geometric
View on Learning Bayesian Network Structures.
the first step was to use the
computer
package
M. Franz (2006). Convex
– a Maple package for convex geometry, version 1.1,
available at http://www.math.uwo.ca/~mfranz/convex/
to compute the
facets of the standard imset
polytope P. They are characterized by facet-defining
inequalities. The result is summarized in the first table, which
depicts whether a
vertex (= standard imset) belongs to a facet (characterized by a
facet-defining inequality), named shortly
vertex-facet
table.
The method for
obtaining the geometric
neighborhood is based on the following two observations:
- First, every face F
of P is uniquely
determined by the list of vertices of P
contained in F. This follows from
Proposition 2.3(i) in
G.M. Ziegler (1995). Lectures on Polytopes New
York:Springer-Verlag.
- Second, every proper face can be
obtained
as the intersection of all facets containing it. See the observation
(14) on
page 102 in
A. Schrijver (1986). Theory of Linear and
Integer Programming/ Chichester:John Wiley.
We got the geometric
neighborhood on the
basis of the vertex-facet table. The procedure was as follows (the code
written in R is available here).
- For every pair
of distinct vertices u and
v of P,
we found the least face F(u,v) of P containing
{u,v} as the intersection of all facets
containing them. Of course, if there is no facet containing {u,v}
then F(u,v)=P.
- We characterized F(u,v)
by the list R of vertices contained
in F(u,v). Thus, we „obtained“ it as
the „intersection“ of all columns of the vertex-facet table
containing both u and v.
- Finally, we recognized the geometric neighbors as
those pairs $[u ,v]$
for which the face F(u,v) is en
edge, that is, for which R={u,v}.
- The result is summarized in the other table,
which depicts whether a vertex (=
standard imset) is a geometric neighbor of another vertex, named
shortly the vertex-vertex table.
- The table also indicates inclusion neighbors (the
R code of this procedure is available
here). They were determined as those pairs of standard imsets u, v
for which the differential imset u-v
is
an elementary imset or its multiple by (-1). We confirmed for
N={1,2,3,4} the conjecture that the inclusion neighborhood is contained
in the geometric neighborhood (the code used to confirm the
hypothesis was written in R and is available here).
Convention
In the vertex-facet tables we describe facet-defining inequalities in
the form <m,u> +c >= 0,
where <.,.> denotes the scalar product, m is the vector of coefficients, u is the
standard imset, and c a constant (scalar).
In the vertex-facet tables the left margin defines the standard imset
values for subsets A,
|A| > 1 of
N={1,2,3} and N={1,2,3,4}, respectively. The top margin defines the
coefficients in m of the inequalities that define facets.
In the vertex-vertex table the left and top margins define the standard
imset values for subsets A, |A| > 1 of
N={1,2,3} and N={1,2,3,4}, respectively.
Results for three variables
Results for four variables
R code and the input files
For the computations we have used the following code written in the R
language and the
following two input files:
Geometric neighborhood
for Bayesian network structures over five variables
As concerns the case of 5 variables the geometric neighborhood has
been computed by another method. More specifically, if V denotes
vertices of a polytope P and if u,v are vertices then the line segment
[u,v] is an edge of P iff v-u is not a non-negative linear combination
of the vectors w-u, where w belongs to V but differs from u and
v. This was tested for every pair u,v of standard imsets by the linear
program software Cplex.
Because of the size of the resulting matrix it has no sense to put on
the web the whole vertex-vertex table. Instead, we provide the text
files containing the relevant information that can be processed by a
computer program. The geometric neighborhood for five variables is
described in the text file S5.edges, which has
142 lines each having 8782 zero-one entries. Each line corresponds to a
representative u of permutation equivalence of standard imsets, each
entry to standard imset v. Value 1 of the entry means that u and v are
geometric neighbors, value 0 means they are not. The list of
permutation equivalence representatives u is the file S5.rep,
while the list of all standard imsets is in the S5.ver.