[PDF] Characteristic imset: a simple algebraic representative of a Bayesian

View - Download Characteristic imset: a simple algebraic representative of a Bayesian

Previous PDF

Next PDF

Pp. 257-265 inProceedings of the Fifth European Workshop on Probabilistic Graphical Models (PGM-2010),

edited by Petri Myllym¨aki, Teemu Roos and Tommi Jaakkola. HIIT Publications 2010-2. Characteristic imset: a simple algebraic representative of a

Bayesian network structure

Milan Studen´y

Institute of Information Theory and Automation of the ASCR, Czech Republic studeny@utia.cas.cz

Raymond Hemmecke

TU Munich, Germany

hemmecke@ma.tum.de

Silvia Lindner

University of Magdeburg, Germany

lindner@mail.math.uni-magdeburg.de

Abstract

First, we recall the basic idea of an algebraic and geometric approach to learning a Bayesian network (BN) structure proposed in (Studen´y, Vomlel and Hemmecke, 2010): to represent every BN structure by a certain uniquely determined vector. The original proposal was to use a so-calledstandard imsetwhich is a vector having integers as components, as an algebraic representative of a BN structure. In this paper we propose an even simpler algebraic representative called thecharacteristic imset. It is 0-1-vector obtained from the standard imset by an affine transformation. This implies that every reasonable quality criterion is an affine function of the characteristic imset. The characteristic imset is much closer to the graphical description: we establish a simple relation to any chain graph without flags that defines the BN structure. In particular, we are interested in the relation to theessential graph, which is a classic graphical BN structure representative. In the end, we discuss two special cases in which the use of characteristic imsets particularly simplifies things: learning decomposable models and (undirected) forests.

1 Introduction

The score and search method for learning

Bayesian network (BN) structure from data

consists in maximizing aquality criterionQ, also named ascoring criterionor simply ascore by other authors. It is a real function of the (acyclic directed) graphGand the observed databaseD. The valueQ(G,D) measures how well the BN structure defined byGfits the databaseD.

Two important technical requirements on the

criterionQemerged in the literature in con- nection with computational methods dealing with this maximization task:Qshould bescore equivalent(Bouckaert, 1995) and (additively)decomposable(Chickering, 2002).

Another important question is how to rep-

resent the BN structure in the memory of a computer. It could be the case that differ- ent acyclic directed graphs are Markovequiv- alent, i.e., they define the same BN structure.

A classic graphical characterization of equiva-

lent graphs (Verma and Pearl, 1991) states that they are equivalent iff they have the sameadja- cenciesandimmoralities, which are special in- duced subgraphs. Representing a BN structure by any of the acyclic directed graphs defining it leads to a non-unique description causing later identification problems. Thus, researchers call- ing for methodological simplification proposed to use a unique representative for each individ-

258Studen´y et al.

ual BN structure. The classic unique graphical representative is theessential graph(Andersson,

Madigan and Perlman, 1997).

The idea of an algebraic approach, introduced

in Section§8.4 of (Studen´y, 2005), is to use an algebraic representative, called thestandard im- set. It is a vector whose components are inte- gers indexed by subsets of the set of variables (= nodes)N. Moreover, it is a unique BN struc- ture representative and the memory demands for its computer representation are polynomial in|N|. The most important point, however, is:

Every score equivalent and decomposable crite-

rionQis an affine function (= linear function plus a constant) of the standard imset. Specif- ically, given an acyclic directed graphG(over

N) and a databaseD, we have

Q(G,D) =sQ

D- ?tQ

D,uG?,(1)

wheresQ

Dis a constant depending on the

database and where?tQ

D,uG?is the scalar prod-

uct of a vector depending on the database, called thedata vector(relative toQ), and of the standard imsetuG(forG). Note that there is a polynomial-time algorithm (in|N|) for the reconstruction of the essential graph from the standard imset (Studen´y and Vomlel, 2009).

The geometric view was introduced in the pa-

per (Studen´y, Vomlel and Hemmecke, 2010), where it was shown that the set of standard im- set (over a fixed set of variablesN) is the set of vertices (= extreme points) of a certain poly- tope. In particular, the maximization ofQover acyclic directed graphs can be re-formulated as a classiclinear programming problem, that is, optimizing a linear function over a polyhedron. 1

In this paper, we propose an alternative al-

gebraic representative of a BN structure, called thecharacteristic imset. It is a vector obtained from the standard imset by a one-to-one affine transformation that maps lattice points to lat- tice points (in both directions). Thus, every score equivalent and decomposable criterion is an affine function of the characteristic imset and the set of characteristic imsets is the set of ver- tices of a polytope. The characteristic imset has

1Note that a polytope is simply a bounded polyhe-

dron.only zeros and ones as its components. More-over, it is very close to the graphical description:some of its components with value one corre-spond to adjacencies. Immoralities can also berecognized in the graph(s) on the basis of thecharacteristic imset. We establish a simple re-lation of the characteristic imset to any chaingraph (without flags) defining the BN structure.In particular, this makes it possible to get im-mediately the characteristic imset on the basisof the essential graph. We also consider the con-verse task of reconstructing the essential graphfrom the characteristic imset.

If we restrict ourselves to decomposable mod-

els (= BN structures defined by acyclic directed graphs without immoralities), then the charac- teristic imset has a quite simple form. The sit- uation is particularly transparent in the case of (undirected) forests: the edges of the for- est are in one-to-one correspondence with 1"s in the characteristic imset. The polytope spanned by these special characteristic imsets has al- ready been studied in matroid theory (Schrijver,

2003). Consequently, we can easily learn (undi-

rected) tree structures, which give an elegant geometric interpretation to a classic heuristic procedure proposed by Chow and Liu (1968).

The structure of this paper is as follows. In

Section 2 we recall some of the definitions and

relevant results. In Section 3 we introduce the characteristic imset and derive the above men- tioned observations on it. Section 4 is devoted to the reconstruction of the essential graph from the characteristic imset. Section 5 briefly outlines our results about learning undirected forests from (Hemmecke et al., 2010). In Con- clusions we discuss further perspectives.

2 Basic concepts

2.1 Graphical concepts

Graphs considered in this paper have a finite

non-empty set of nodesNand two types of edges: directed edges, calledarrows, denoted likei→jorj←i, and undirected edges. No multiple edges are allowed between two nodes.

If there is an edge between nodesiandj, we

say they areadjacent.

Studen´y et al.259

Given a graphGoverNand a non-empty

set of nodesA?N, theinduced subgraphof

GforAhas just those edges inGhaving both

end-nodes inA. AnimmoralityinGis an in- duced subgraph (ofG) for three nodes{a,b,c} in whicha→c←bandaandbare not ad- jacent. Aflagis another induced subgraph for {a,b,c}in whicha→b,bandcare adjacent by an undirected edge andaandcare not adjacent.

A set of nodesK?NiscompleteinGif

every pair of distinct nodes inKis adjacent by an undirected edge. A maximal complete set is called aclique. A setC?Nisconnectedif every pair of distinct nodes inCis connected via an undirected path. Maximally connected sets are calledcomponents.

A graph isdirectedif it has no undirected

edges. A directed graphGoverNis called acyclicif it has no directed cycle, that is, a sequence of nodesa1,...,an,n≥3 with a i→ai+1fori= 1,...n, under the conven- tionan+1≡a1. An equivalent definition is the existence of an orderingb1,...,bm,m≥1, of all nodes inNwhich is consistent with the di- rection of arrows, that is,bi→bjinGimplies i < j.

A graph isundirectedif it has no arrow. An

undirected graph is calledchordal, ordecompos- able, if every (undirected) cycle of length at least

4 has a chord, that is, an edge connecting two

non-consecutive nodes in the cycle. There is a number of equivalent definitions for a decom- posable graph (Lauritzen, 1996); one of them says that it is an undirected graph which can be acyclically directed without creating an im- morality. A special case of a chordal graph is aforest, which is an undirected graph without undirected cycles. A forest overNin whichN is connected is called a(spanning) tree.

Achain graphis a graphG(allowing both di-

rected and undirected edges) whose components can be ordered into a chain, which is a sequence

C1,...,Cm,m≥1 such that ifa→binGthen

a?Ciandb?Cjwithi < j. An equivalent definition is: It is a graph without semi-directed cycles. Of course, every acyclic directed graph and every undirected graph is a special case of a chain graph (without flags).Given a connected setCin a chain graphG, the set ofparentsofCis pa

G(C)≡ {a?N;a→binGfor someb?C}.

Clearly, in a chain graph,paG(C) is disjoint

with (a connected set)C.

2.2 Bayesian network structures

LetNbe a finite set ofvariables; to avoid the

trivial case assume|N| ≥2. For eachi?N consider a finite individualsample spaceXi(of possible values); to avoid technical problems as- sume|Xi| ≥2, for eachi?N. ABayesian net- workcan be introduced as a pair (G,P), where

Gis an acyclic directed graph havingNas the

set of its nodes andPa probability distribution on thejoint sample space? i?NXithat recur- sively factorizes according toG. Note that a factorization ofPis equivalent to the condition thatPisMarkovianwith respect toGmean- ing that it satisfies conditional independence re- strictions determined by the respective separa- tion criterion (Lauritzen, 1996).

BN structure(= Bayesian network structure)

defined by an acyclic directed graphGis for- mally the class of probability distributions (on a fixed joint sample space) being Markovian with respect toG. Different graphs overNcan be

Markov equivalent, which means they define the

same BN structure. The classic graphical char- acterization of (Markov) equivalent graphs isquotesdbs_dbs1.pdfusesText_1

[PDF] imset cnam

[PDF] imset formation tunisie prix

[PDF] imset logo

[PDF] imset sousse numero

[PDF] imset sousse sans bac

[PDF] imsva pro cdm ma

[PDF] in tabelul de mai jos este inregistrata evolutia temperaturii medii din moldova

[PDF] in1606fhg hgec

[PDF] in1706 fhg hgec

[PDF] inaghei options

[PDF] inaghei resultat concours 2015

[PDF] inalco cilo

[PDF] inalco inscription

[PDF] inca 2016

[PDF] incertitude absolue chimie