The Interchange Format for Bayesian Networks


View this page in Romanian courtesy of azoft

Introduction

The objective of this web site is to summarize and distribute information on an effort to standardize formats for representation of Bayesian networks and other related graphical models.

The goal of the current effort is to specify a XML-based format that is very simple to understand and yet can represent directed acyclic graphs with probabilistic relations, decision variables and utility values. The current format is referred to as XMLBIF version 0.3.

Historic backgroud

Several members of the UAI community have felt that a common format for Bayesian networks would significantly enhance the exchange of knowledge and experimental results in the community. In the spirit of fostering such exchange, several attempts have been made at creating a standardized format. A panel was organized at the UAI conference 1996, and formats such as the BNIF and the BIF were then proposed; eventually, a a group was formed to debate issues related to a possible standard. As these discussions proceeded, it became evident that defining a single all-encompassing format would likely be too hard a task at the current stage of knowledge.

During UAI conference 1998, a new panel was formed to assess the strategy to be followed in the direction of a standard format. The panel suggested that it would be a good idea to base it on XML (the Extensible Markup Language), as XML is now receiving industry wide support as a mechanism for data specification. The idea is that XML can provide an inicial layer of standardization. Even if different formats are proposed by different groups, the fact that they are based on XML makes translation much simpler. And the fact that XML-compliant parsers are freely available makes the whole process much smoother.

Following the panel discussion, a number of meetings among members of the UAI community suggested that another step in the path to standardization could be taken. It would be a good idea to try to define a very simple standard format in XML. Such a standard would have to be simple so that people could understand it quickly and construct parsers for it without too much work. The standard would be beneficial to familiarize people with XML and to indicate how to proceed in future standardization efforts.

These discussions led to the present standardization effort. A very simple format has been defined during conversations between Fabio Cozman and members of the GeNie project, notably Marek Druzdzel and Daniel Garcia. This format is described below, and is current referred to as the XMLBIF (XML-based BayesNets Interchange Format) version 0.3.

The XMLBIF format is being implemented in the JavaBayes and GeNie systems; there have been signs that implementations in the Netica and Hugin systems are in the works.

The XMLBIF working group

A number of people have contributed to the XMLBIF format. The format has been designed primarily by Fabio Cozman, with important contributions from Marek Druzdzel and Daniel Garcia. Akihiro Shinmori has contributed with his expertise in XML issues. Brent Boerlage, Frank Jensen and Bruce D'Ambrosio have supported the idea and contributed to the discussion.

Anyone can join the group and contribute.

The XMLBIF format

The goal of the current XMLBIF format is to represent directed acyclic graphs that can be associated to conditional probability measures for discrete variables, with the possibility that decision and utility variables be present in the graph.

The format emphasizes internationalization by adopting XML's guidelines for document specification (the XML documentation explains this at lenght; it amounts to the adoption of Unicode as the standard for character representation, case-sensitive documents, and tags for indicating document encodings).

XML is very similar to HTML and most structures used in HTML appear in XML.

Every file in XMLBIF must contain an initial XML tag that displays basic information about the document:

<?xml version="1.0"?>

The version attribute is mandatory. Other attributes, coming after the version attribute, are optional. For example:

<?xml version="1.0" encoding="US-ASCII"?>
Other XML tags may come after this initial tag. The XML specification details the possible tags. Essentially, the XML document may contain several indications regarding the grammar that must be enforced by the XML parser. The most interesting possibility is to embed the whole document specification in the top of the document through a !DOCTYPE tag. Here is the complete XML specification of XMLBIF version 0.3 (this is called a Document Type Definition, or DTD):
<!DOCTYPE BIF [
	<!ELEMENT BIF ( NETWORK )*>
	      <!ATTLIST BIF VERSION CDATA #REQUIRED>
	<!ELEMENT NETWORK ( NAME, ( PROPERTY | VARIABLE | DEFINITION )* )>
	<!ELEMENT NAME (#PCDATA)>
	<!ELEMENT VARIABLE ( NAME, ( OUTCOME |  PROPERTY )* ) >
	      <!ATTLIST VARIABLE TYPE (nature|decision|utility) "nature">
	<!ELEMENT OUTCOME (#PCDATA)>
	<!ELEMENT DEFINITION ( FOR | GIVEN | TABLE | PROPERTY )* >
	<!ELEMENT FOR (#PCDATA)>
	<!ELEMENT GIVEN (#PCDATA)>
	<!ELEMENT TABLE (#PCDATA)>
	<!ELEMENT PROPERTY (#PCDATA)>
]>

This tag contains the whole Document Type Definition (DTD) for
XMLBIF version 0.3, and it can be included in any XMLBIF
version 0.3 document.

The DTD shows all the tags that are used by XMLBIF version 0.3. 
The networks represented
in a file must be enclosed by BIF tags; the opening BIF tag must contain
the version of the format. For example:

<BIF VERSION="0.3">

Network here

Another network here

</BIF>
Each network is enclosed by NETWORK tags. A network is defined through a NAME tag and a sequence of PROPERTY, VARIABLE and DEFINITION tags (note that no order is imposed on PROPERTY, VARIABLE and DEFINITION tags).
<BIF VERSION="0.3">
<NETWORK>
<NAME>Dog-Problem</NAME>
<PROPERTY>date Sunday, 19 July, 1998</PROPERTY>
<PROPERTY>author John</PROPERTY>

	variables and probabilities go here

</NETWORK>
</BIF>

A property is just a string of arbitrary text to be associated with a block. Examples of properties:

    <PROPERTY>size 12</PROPERTY>
    <PROPERTY>comment Trial number ten</PROPERTY>
Any text is valid in the string inside the PROPERTY opening and closing tags. The idea is to store information that is specific to a particular system or network in the properties. Any number of property attributes can appear in a block. Properties can be associated to a NETWORK, a VARIABLE or a DEFINITION.

Variables are defined by their names, types and properties:

<VARIABLE TYPE="nature">
	<NAME>light-on</NAME>
	<OUTCOME>true</OUTCOME>
	<OUTCOME>false</OUTCOME>
	<PROPERTY>position = (73, 165)</PROPERTY>
</VARIABLE>
Currently the content of a TYPE attribute must be the keyword either ``nature'' or ``decision'' or ``utility''.

Conditional probability densities are specified inside the DEFINITION tag. One example is:

<DEFINITION>
	<FOR>hear-bark</FOR>
	<GIVEN>dog-out</GIVEN>
	<TABLE>0.7 0.3 0.99 0.01 </TABLE>
</DEFINITION>

There is no mandatory order of variable and probability blocks.

The TABLE tag is specific to the DEFINITION block (note that a definition can be a probability distribution, a set of decision values or a set of utility values, depending on the TYPE attributes of the referred variable). DEFINITION blocks are used to define the actual network topology, by specifying conditional probability tables.

An example of a standard probability block is:

<DEFINITION>
	<FOR>GasGauge</FOR>
	<GIVEN>BatteryPower</GIVEN>
	<GIVEN>GasInTank</GIVEN>
	<TABLE>1.0 0.0
                   0.0 1.0
                   0.2 0.8
                   0.0 1.0 </TABLE>
</DEFINITION>
for a variable GasGauge that is defined with TYPE equal to ``nature''. The body of the TABLE tag is a sequence of non-negative real numbers, in the counting order of the declared variables, taking the GIVEN variables first and then the FOR variables (if all variables were binary, we would say binary counting with least significant digit in the right). If multiple table declarations exist, only the last one is valid.

Here is the dog-problem Bayesian network, based on the discussion in Charniak, E., Bayesian Networks without Tears, AI Magazine, 1991.

<?xml version="1.0" encoding="US-ASCII"?>


<!--
	Bayesian network in XMLBIF v0.3 (BayesNet Interchange Format)
	Produced by JavaBayes (http://www.cs.cmu.edu/~javabayes/
	Output created Wed Aug 12 21:16:40 GMT+01:00 1998
-->



<!-- DTD for the XMLBIF 0.3 format -->
<!DOCTYPE BIF [
	<!ELEMENT BIF ( NETWORK )*>
	      <!ATTLIST BIF VERSION CDATA #REQUIRED>
	<!ELEMENT NETWORK ( NAME, ( PROPERTY | VARIABLE | DEFINITION )* )>
	<!ELEMENT NAME (#PCDATA)>
	<!ELEMENT VARIABLE ( NAME, ( OUTCOME |  PROPERTY )* ) >
	      <!ATTLIST VARIABLE TYPE (nature|decision|utility) "nature">
	<!ELEMENT OUTCOME (#PCDATA)>
	<!ELEMENT DEFINITION ( FOR | GIVEN | TABLE | PROPERTY )* >
	<!ELEMENT FOR (#PCDATA)>
	<!ELEMENT GIVEN (#PCDATA)>
	<!ELEMENT TABLE (#PCDATA)>
	<!ELEMENT PROPERTY (#PCDATA)>
]>


<BIF VERSION="0.3">
<NETWORK>
<NAME>Dog-Problem</NAME>

<!-- Variables -->
<VARIABLE TYPE="nature">
	<NAME>light-on</NAME>
	<OUTCOME>true</OUTCOME>
	<OUTCOME>false</OUTCOME>
	<PROPERTY>position = (73, 165)</PROPERTY>
</VARIABLE>

<VARIABLE TYPE="nature">
	<NAME>bowel-problem</NAME>
	<OUTCOME>true</OUTCOME>
	<OUTCOME>false</OUTCOME>
	<PROPERTY>position = (190, 69)</PROPERTY>
</VARIABLE>

<VARIABLE TYPE="nature">
	<NAME>dog-out</NAME>
	<OUTCOME>true</OUTCOME>
	<OUTCOME>false</OUTCOME>
	<PROPERTY>position = (155, 165)</PROPERTY>
</VARIABLE>

<VARIABLE TYPE="nature">
	<NAME>hear-bark</NAME>
	<OUTCOME>true</OUTCOME>
	<OUTCOME>false</OUTCOME>
	<PROPERTY>position = (154, 241)</PROPERTY>
</VARIABLE>

<VARIABLE TYPE="nature">
	<NAME>family-out</NAME>
	<OUTCOME>true</OUTCOME>
	<OUTCOME>false</OUTCOME>
	<PROPERTY>position = (112, 69)</PROPERTY>
</VARIABLE>


<!-- Probability distributions -->
<DEFINITION>
	<FOR>light-on</FOR>
	<GIVEN>family-out</GIVEN>
	<TABLE>0.6 0.4 0.05 0.95 </TABLE>
</DEFINITION>

<DEFINITION>
	<FOR>bowel-problem</FOR>
	<TABLE>0.01 0.99 </TABLE>
</DEFINITION>

<DEFINITION>
	<FOR>dog-out</FOR>
	<GIVEN>bowel-problem</GIVEN>
	<GIVEN>family-out</GIVEN>
	<TABLE>0.99 0.01 0.97 0.03 0.9 0.1 0.3  0.7 </TABLE>
</DEFINITION>

<DEFINITION>
	<FOR>hear-bark</FOR>
	<GIVEN>dog-out</GIVEN>
	<TABLE>0.7 0.3 0.01 0.99 </TABLE>
</DEFINITION>

<DEFINITION>
	<FOR>family-out</FOR>
	<TABLE>0.15 0.85 </TABLE>
</DEFINITION>


</NETWORK>
</BIF>

Outside XML

It is important to note that there are some facts about the format that cannot be made explicit through XML. For example, if a DEFINITION contains several TABLE tags, only the last is valid. Another example is that XMLBIF version 0.3 accepts real numbers that are represented in scientific notation as specified in the ANSI C or Java language definitions.

XMLBIF version 0.3 is designed to make use of XML facilities; as such, it accepts Unicode characters. But as current implementations of parsers must, in many cases, rely on systems that do not have good Unicode support, we suggest that only ASCII characters are used in XMLBIF version 0.3 files for the moment. Also, identifiers (the name of the network, names of variables and names of outcomes) can be expressed in any Unicode character; however, we have some problems with this level of freedom. First, there are difficulties in writing customized parsers that can support the full range of Unicode. Second, there are questions related to the manipulation of mathematical expressions involving variables with arbitrarily complex names. For these reasons, we require that identifiers in XMLBIF version 0.3 satisfy somewhat restrictive conditions: any identifier must be a sequence of letters and digits, and the sequence must begin with a letter. A letter is any character in the sequences [a-z] and [A-Z] plus the underscore _. A digit is any character in the sequence [0-9]. It is possible that in the future a less restrictive set of conditions will be given for identifiers, along the lines of the Java language identifiers.

The most important aspect of the current format that is not captured by XML is the semantics of the contents of a TABLE tag. All distributions and utility values are specified as arrays of real numbers; XMLBIF version 0.3 does not require these numbers to be non-negative nor that they sum up to one. Such consistency conditions must be checked by the parser if desired. The important point is how tables are organized:

The probabilities for a binary variable can be specified in a simple manner:

0.15, 0.85

Let's consider a more complicated example. The conditional p(d|f,b) (the probability of d given f and b, where all variables are binary) is defined as

0.99, 0.01, 0.90, 0.1, 0.97, 0.03, 0.3, 0.70

The logic is simple: proceed as if you were filling a table, where the indices of the table vary from the right to left, with the conditional variables coming first (in the example above, it is like binary counting because all variables have only two values).

A more complicated example would be a function p(A|B,C) where A has 3 values, B has 2 values and C has 4 values. The function is represented as:

p(A1|B1 C1) p(A2|B1 C1) p(A3|B1 C1)


p(A1|B1 C2) p(A2|B1 C2) p(A3|B1 C2)


p(A1|B1 C3) p(A2|B1 C3) p(A3|B1 C3)


p(A1|B1 C4) p(A2|B1 C4) p(A3|B1 C4)


p(A1|B2 C1) p(A2|B2 C1) p(A3|B2 C1)


p(A1|B2 C2) p(A2|B2 C2) p(A3|B2 C2)


p(A1|B2 C3) p(A2|B2 C3) p(A3|B2 C3)


p(A1|B2 C4) p(A2|B2 C4) p(A3|B2 C4)


Fabio Gagliardi Cozman
1998-08-13