Please consider a donation to the Higher Intellect project. See https://preterhuman.net/donate.php or the Donate to Higher Intellect page for more info.

Proposal for a Bayesian Network Interchange Format

From Higher Intellect Vintage Wiki
Jump to navigation Jump to search
Decision Theory Group

Microsoft Research

(Version 0.2 : Last Updated 8/28/96)


Introduction

This page describes a proposed standardized belief network interchange file format. We have developed this format as mechanism for:

  • Providing a path to the interoperability of Bayesian network tools
  • Facilitating intergroup sharing of knowledge bases encoded as Bayesian networks
  • Facilitating the benchmarking of algorithms and comparative research on Bayesian networks


An email listserver has been established for this subject through the courtesy of Oregon State University.


Overview

The BN mini-language of the proposed interchange format has borrowed a lot of elements from the C/C++ language. Not surprisingly, the format supports the single-line //... and multi-line /*...*/ comment sequences, and you will notice that we make liberal use of curly braces. In addition, the definitions of identifiers, strings, and reals follow closely those from C/C++. Instead of presenting the format by specifying its precise syntax, I will rather illustrate the format by means of examples. However, we plan to release the sources of a format verifying program called BNLINT, which will contain a full YACC specification of a belief network parser. (YACC syntax is very close to Backus-Naur form.)

Each belief network file (bnfile) carries the extension DSC for identification purposes.

Major elements or blocks in a belief network file are marked using curly braces. The general format of a block is:

        blockType BlockName
        {
            attribute-name = attribute-value;
               // or, alternatively,
            attribute-name is attribute-value;
        }

The blocks in a DSC file occur in the following order:

  • network declaration block (one, must be first)
  • property declaration block (one)
  • node declaration blocks (many)
  • probability definition blocks (many)

The network declaration block reveals the type of network and information that pertains to the network as a whole. Currently, only a single "Belief Network" type is defined, but it is expected that in the future other formats may be introduced (like, for instance, "Diagnostic Network", "Decision Diagram", etc.).

Node declaration blocks describe the events of the network and their possible states, along with other attributes.

Probability definition blocks define the conditioning arcs between nodes and contain the prior probabilities.


Properties

This proposed Belief Network format is designed to be flexible. In order to allow different groups to extend the standard to support special technologies and tools, bnfiles can define and utilize additional attributes particular to the individual network file. These dynamic attributes are known as properties, and are meant to model atom property lists available in the LISP language.

A property type is a declaration of the existence of a property and applies to the network as a whole. A property is a particular instance of a property type, and is specifically associated with either the network itself or a particular node.

Properties are named according to the rules of bnfile symbolic names. (These rules are identical to those of the 'C' language.) There are five possible property types:

  • a real number
  • a string
  • an array of real numbers
  • an array of strings
  • a choice of one of a set of tokens (symbolic names)

In addition, each property can have a descriptive comment string.

For example, there could be a property type of CarsOwned, declared to be an array of strings. Any node could then be given the CarsOwned property, with values such as ["87 Honda", "93 Pathfinder"] or ["83 Taurus"].

No particular interpretation is given to properties; they may contain any information desired. However, since the usage of property names could conflict between organizations, it is recommended that implementing groups prefix the properties with a unique identifier. At Microsoft, we will prefix our property types with the characters "MS_".

Here is an example properties block:

        properties
        {
            type description = string;
            type helpContextIds is array of real, "help ids";
            type stateDescriptions is array of string, "one for each state";
            type MS_label is choice of [other, hypothesis, informational,
                                        problem, fixable, unfixable];
            property description = "this is a test";
            helpContextIds = [344,43434,877,46875];
        }


The lines beginning with the keyword type define types of properties; the name of the property immediately follows. Each property type must have a data type declaration. Each may have an optional comment describing the purpose or usage of the attribute. Property types have file scope; that is, they may be used anywhere that properties are allowed.

The properties block is also used to define properties which exist at the network level. The line above beginning with the word property defines the value for the network-level property called description. The keyword property is optional, as demonstrated by the subsequent line, which defines the value for the network-level property helpContextIds.

This properties block above declares four property types:

  • description; a string
  • helpContextIds; an array of real numbers,
  • stateDescription; a array of strings
  • MS_label; an ordered list of words (enumeration).

The line beginning with the keyword property defines an instance of a property type. In this case, it is an instance of the description property defined a few lines above it. A property type must be declared before an instance of it can be defined..

The last property type defined, MS_label, is an example of an enumeration. An enumeration property is simply a set of words which map one-to-one onto the integers, starting with zero. In the example given, use of the word other would give the value zero; use of the word fixable would give the value 4. Enumerated properties are intended to provide a high degree of readability in dynamically declared properties. Instances of enumerated properties may be defined using either a word from the set or an integer within the allowed range.

Note that reserved words may not be used as choices in an enumeration.


Network Declaration

The first element in a DSC or bnfile is the declaration of the name of the network. For example:

        network "Car Starting Example"
        {
            format is "BNFormat";
        }

This declaration may be followed by the optional properties block. Then the actual belief network appears, defined by node blocks and probability blocks.

Node blocks declare the node variables in the network one at a time. Since node blocks do not interreference, they may occur in any order. Node blocks look like this:

        node NodeName
        {     //  node attributes, described later
        }

Here, 'node' is a keyword and 'NodeName' is an identifier (symbolic name). Probability blocks have the same general shape: Probability blocks specify the (conditional) probability tables (CPTs) for these variables, and hence the topology of the network.

        probability (Node | D1, D2, D3)
        {
            //  conditional probability tables
        }

Again, 'probability' is a keyword and the others are identifiers. As the notation suggests, this defines that node Node has a total of 3 parents, namely: D1, D2, D3.

Node and probability blocks can be freely mixed, except for the restriction that all the node blocks of variables referenced in a particular probability block have to precede the probability block.


Node Blocks

Node blocks contain information about the node such as:

  • type (discrete or continuous),
  • full name (string),
  • number of states and names of the states,
  • position on the screen (for use by Belief Network graphical editors),
  • other attributes, represented as properties.

The node's type attribute is the only one that is required. In general, an attribute is of the form:

        attribute-type is attribute-value;  //  or
        attribute-type = attribute-value;

Currently, standard attributes are: 'name', 'type', and, 'position'.. Here is an example of a node block from the automobile belief network (BN) that David Heckerman and Jack Breese presented some time ago, and that is also featured in one of the articles in the March, 1995 issue of Communications of the ACM.

        node Alternator
        {
           name is "Alternator Output Voltage";
           type = discrete[2]
            {
                "good",
                "bad"
            };
            position = (15625, 10195);
            property MS_label is "fixable";
            MS_category = "Service Fixable";
            MS_cost_observe = 15.00;
            MS_cost_fix = 200.00;
        }

This just tells us that we have a node with symbolic name Alternator. In this case, the full string description of the node/variable is "Alternator Output Voltage" (this is the string that is usually displayed in a BN editor). It also says that the node is a discrete node with two states, labeled good and bad, respectively. The position attribute is for the benefit of the BN editor, and represents a point in graphical display space. The other attributes are specific to a particular (research) group and their precise meaning does not concern us here. Note that the optional keyword property may introduce a property.

The minimum information needed to declare a node is its type. For instance, one can declare a ternary variable by

        node ThreeState
        {
            type: discrete[3];
        }

whereas a continuous node would look like

        node Temperature
        {
            type: continuous;
        }


Probability Blocks

Probability blocks are used t define the actual network topology and conditional probability tables (CPTs). There are two kinds of probability blocks:

  1. blocks for standard nodes; that is, nodes for which we have to define the probabilities for each discrete parent instantiation (DPI) and
  2. blocks for causally independent (CI) nodes, for which we have to define the probabilities for only a limited number of DPIs.

CPT for Standard Nodes

An example of a standard probability block from the automobile example, is the one for the gas gauge. We assume that the gas gauge has two states "not empty"/"empty" and two parents: 1) "Gas" (is there gas in the tank?) and 2) "BatteryPower" (is the battery power sufficient?). The variable "Gas" has two states: "yes" and "no", and the variable "BatteryPower" has three states: "good", "low" and "none".

        probability(GasGauge | Gas, BatteryPower)
        {
           (0, 0): 0.999, 0.001;
           (yes, "low"): 0.850, 0.150;
           (0, 2): 0.000, 1.000;
           (1, 0): 0.000, 1.000;
           (1, 1): 0.000, 1.000;
           (1, 2): 0.000, 1.000;
        }

The numbers in parentheses above cycle through all the DPIs (we number the states of a node consecutively and start at zero, which in general represents the "normal" or "good" state). The order of the numbers in parentheses corresponds to the order in which the discrete parents are listed after the bar in the opening line of the probability block.

Although the probability vectors are listed in consecutive DPI order here, this is not necessary in general. One is free to list the vectors in any order, since the integers in parentheses uniquely identify the parent instantiation. In addition to giving the vectors for each individual DPI, we support the concept of a default entry. So the above CPT could have been specified equivalently as:

        probability(GasGauge | Gas, BatteryPower)
        {
            default: 0.000, 1.000;
            (0, 1):  0.850, 0.150;
            (0, 0):  0.999, 0.001;
        }

Note: definitions for continuous probability distributions will be forthcoming at a later time.

CPT for Causally Independent Nodes

Causally Independent (CI) nodes are characterized by the property that the probability vectors for each DPI can be derived from the probability vectors of the leak parent instantiation, and the parent instantiations in which one and only one parent assumes a value different from its leak value. Conceptually, the leak parent instantiation represents the situation in which none of the parents is causing the child node to be in a abnormal state, and hence the probability vector associated with the leak instantiation models influences on the child node that are not explicitly accounted for the parents. Currently, we support two functional CI relationships, namely: 'max' (noisy or) and 'plus'. (For a more detailed description of CI nodes see the paper by Heckerman and Breese in the UAI proceedings of 1994.) Expressed in terms of a CI CPT the following probability specification for GasGauge is almost identical to the one given earlier:

        probability(GasGauge | Gas, BatteryPower)
        {
            function: type = max;
            (0, 0): 0.999, 0.001;  // leak term
            (0, 1): 0.850, 0.150;
            //     this implies Pr(GasGauge | 0, 1) = (p, 1 - p),
            //     with p = 0.85 * 0.999
            (0, 2): 0.000, 1.000;
            (1, 0): 0.000, 1.000;
        }

Typically, the state selectors of a leak instantiation are all zeros, because the 0th state usually represents the normal or good or absent state.


Proprietary or Organization-Specific Extensions

One reason for choosing a general block format for belief network files is that such blocks can be recognized in their entirety by simple syntax. This allows a parser to ignore blocks whose content is unfamiliar. Thus, any organization can create entirely new blocks which contain deeply nested information specific to their implementation. Files containing such blocks can still be parsed by correctly written parsers. The unrecognized blocks are discarded in their entirety.

The grammatical rules are as follows. If the parser finds an identifier (a valid unknown name) at the outer block level within a file, it will begin to consume tokens until the block has been closed. The general format for a block is:

identifier [(optional parenthetical argument list)]
{ [optional string of tokens]
}

Items in square brackets above are optional. Nesting can occur within both the argument list and the main block. Two nesting symbols are allowed: curly braces and parentheses. The parser allows them to be nested within themselves or within each other, but will report an error if a nested block is opened by one nesting symbol but closed by another.

See Also