Details of Asymmetric Assessment

Introduction

The belief network authoring tool MSBNX provides two distinct means of assessing probabilities.

Traditional or standard probability assessment displays the complete distribution of a discrete variable as a table in which all possible parent instantiations are shown simultaneously. Subsets of the distribution can be selected as a group by appropriate control of the parent states. As always however, variables with many parents create unmanageably large tables.

The new asymmetric assessment capability in MSBNX displays the distribution of a discrete variable in the form of a decision tree. Each branch of the tree represents a logical grouping of states with similar prior probabilities. These grouped states can be further subdivided as necessary to represent the complete distribution.

This new assessment method is very useful when the instantiations of the parents of a node naturally cluster into causal domains. By its nature, the assessment "tree" is only as complex as the distribution itself.

These two methods can also be used in combination. Certain limitations apply to such usage.

Operation

Activating Asymmetric Assessment

As with standard assessment in MSBNX, there are several ways of activating asymmetric assessment:

• Use the tool bar button .

• Select View/Asymmetric Model Assessment from the main application menu.

• Select Asymmetric Assessment from the context (right-click) menu of a node (variable).

When asymmetric assessment is activated, a floating window appears over the belief network windows. This window will "track" the selected node of the current model. In other words, as you click on nodes in a model, the assessment window will change its contents to reflect the newly selected node.

In this document, the floating asymmetric assessment window will be referred to as ASYM.

Applicability

Asymmetric assessment cannot be applied in the following situations.

• A node with no parents.

• A node with no distribution.

• A node with a "causally independent" distribution.

Persistence

Whenever asymmetric assessment is performed on a node, a symbolic representation of the resulting tree is stored in the output model file (XBN or DSC).

When a node is selected that already has an assessment tree stored with it, that tree is loaded into ASYM.

The ASYM Window

Here is a sample ASYM window.

It is divided into two panes. The left-hand pane (tree view) gives a hierarchical view of the assessment "tree". The right-hand pane (grid) shows the probabilities for the state currently selected in the left-hand pane.

ASYM Tree View Display

ASYM uses the standard Microsoft Windows Tree Control to display the decision tree. Each displayed line of information in the control is divided into three parts. From left to right, they are:

• The expand/contract box is a small square that has either a minus sign or a plus sign in it. Clicking in this box causes this level of the tree to expand or contract. This does not change the form or contents of the tree- it merely hides sections of the tree from view.

• The icon is a small graphical image that indicates the nature of that level of the tree.

• The name is a text string describing the level of the tree.

The icons used in the tree are:

• a red ellipse, indicating the root of the tree.

• a small, green bucket, indicating the "residue" of that tree level (see below).

• a single, multicolored ellipse, indicating a single state.

• multiple overlapping ellipses, indicating a set of states.

The name of a tree level is initially assigned by ASYM itself, but users can change it as desired.

For example:

This excerpt from a tree view pane shows that the root node is UserAttention. Each Residue item is shown as a green bucket whose default name begins with the name if the represented parent node in brackets (e.g., [CalendarInfo]), followed by the names of the states contained in the residue partition.

The third parent level, labeled TimeOfDay, has five partitions:

• its Residue item (indicated by the "bucket" icon)

• three "singleton" partitions (i.e., representing single states), and

• a multi-state partition.

Tree Control Operations

All interactions with the tree are done either through context (right-click) menus or via drag-and-drop.

Menus

There are two available context menus in ASYM's tree pane. The first is the overall or primary menu. It appears when you right-click in the tree pane but not near any tree node. Here is an example:

The items in this menu control overall behavior of the tree and model in which it resides.

The branch or leaf menu appears when you right-click on a tree level. For example:

These menu items apply only to the tree level you selected.

The Primary Menu

Some items in the primary menu control behavioral settings, while others cause immediate actions. The items that control settings are referred to as toggles and display their state using a check mark

The items in the primary menu are:

The Tree Level Menu

The tree-level menu always contains a fixed number of entries. Those that are inapplicable at the current time are disabled. All its items cause immediate actions. The items are:

Merging Levels with Drag-and-Drop

Merging of tree levels can also be done by dragging a tree level item and dropping it onto another item at the same level.

Merging a tree level with another causes all detail from the sub-tree represented by the dragged (or selected) tree level to be lost, since it is now completely subsumed into the target item.

The ASYM Grid Pane

The right-hand pane of the ASYM window shows the probabilities for a single state of the assessment tree. The displayed information represents the probabilities associated with the selected tree level item in the tree pane. The grid pane is used for verifying and editing the probability values.

Note that probabilities only appear when a "leaf" or final state has been selected. If the tree level item has descendents (i.e., represents a "split"), you must click on an item below it to see the detail probability information.

To edit the values in the grid pane, select a specific "cell" or box containing a probability and start keying a new value. Alternatively, you may double-click on the cell to begin editing.

Edited values are saved or captured into the underlying model whenever the selection in the grid pane or tree pane is changed. Values are updated in every applicable probability set in the underlying discrete distribution.

Standard Operations

Basic Concepts

Parents, Splits and the Path to the Root

Every element in an ASYM tree represents the probabilities associated with one or more parent instantiations. In the trivial case of a single "root" entry, this represents every possible parent state combination. "Growing the tree" requires making decisions about which parent and its states are the most influential given the current position in the tree.

To inaugurate the tree from the topmost (root) level, use the Descend menu item to select a single parent from among the list of all the parents of the variable. This same action is required to descend again to a new level. Since each created tree level "claims" a parent, the tree can never be any deeper than the number of parent nodes. Hence, the list of possible parents to for use in further descent is the set of all parents that have not been mentioned along the path to the root of the tree.

As each new level is created, at least one distinction must be made across that parent's states before a new, deeper level can be created.

The "Residue" and Other Partitions

Once a new level has been created, a special tree item called a Residue automatically appears. All the states of the newly chosen parent are initially assigned to this item; hence its name.

To make finer-grained distinctions at the new level, some of the contents of the Residue item must extracted into independent items. Activating the Split Out menu item will show a list of the states of the level's parent node contained in the Residue item, and allows you to choose a state for separation. Alternatively, the Explode menu item will break every level but one out into separate levels.

In other words, every tree pane item other than the Root directly represents one or more states of a particular parent node. These groupings are called partitions. The most common partition is the Residue item, which initially contains all the states of the parent represented by a newly created level. Other partitions may represent single states or arbitrary groupings of states.

The Residue item cannot be removed from a level; it always represents at least one parent state.

The Exemplar Probability Set

To be eligible for asymmetric assessment, a node must have a complete, discrete probability distribution. Using ASYM causes many probability set values to be subsumed or grouped together. How, then, does ASYM determine the set of values to be associated with a group of parent states?

For any branch of the ASYM tree there exists a probability set considered logically to be the lowest in sequence. This is the probability set associated with the lowest-ordered parent state in each partition on the path to the root. This is referred to as the exemplar set.

When ASYM must display a set of probabilities, it computes the lowest set of parent state indices that exist in the partition and displays that set. After editing, these values are stored back into the exemplar set and into every other set covered by the partition.

This is also applies to automatic determination of asymmetry, which is explained later in this document.

Growing and Altering a Tree

The basic tree operations and their consequences are shown in the table below.

Automatic Asymmetry Tree Determination

Assessment of a preexisting network would be more tractable if its distributions could be analyzed to automatically discover any implicit asymmetries.

This is the purpose of automatic assessment. Given a node with parents and an assessed distribution, the algorithm attempts to discover the smallest tree that fits the distribution to within a chosen numeric error range.

This operation and its underlying algorithm will be referred to as AUTOASYM.

Running Asymmetric Assessment

To perform automatic asymmetric assessment, use the main context menu and select the menu item. Since this operation destroys any existing tree and may run for a long time, a warning dialog box will appear to verify that you really want the operation to proceed.

If you choose Yes, the following dialog box appears.

The name of the belief network node and its description appear at the top. A "progress bar" indicates the progress of the operation. The Cancel button allows you to discontinue the operation at any time.

The progress bar currently does not exactly reflect the remaining running time of the operation. Instead, it represents the progress of the operation in a worst-case scenario. The operation typically terminates much sooner than the progress bar indicates, since most distributions are not as degenerate as the worst possible case.

When the operation is complete, the dialog box disappears and the newly "grown" tree appears in the tree pane of ASYM.

The Algorithm

The AUTOASYM algorithm takes only two input parameters:

1. The belief network node to operate on.

2. The numeric threshold used for determination of equality between two probability sets.

The most basic operation of AUTOASYM is the comparison of two distinct probability sets of the distribution in order to determine if they are similar enough to warrant being combined into a partition. The comparison operation uses the numeric threshold it was given; differences greater than the threshold are considered distinct. This threshold is set by using the main context menu of the ASYM window.

The unfortunate truth is that the core algorithm is factorial in the number of parents and exponential in the number of parent states.

The output of the algorithm is the smallest possible tree representation of the asymmetry in the distribution. In the worst case there is an individual "leaf" element for every possible distinct parent instantiation.

 Here is a brief sketch of the algorithm.

This algorithm is clearly factorial, since it tries every possible parent combination at each level. Worse, it must try each of these combinations for each group of states it discovers at each parent level.

Fortunately, most nodes are binary and do not have large numbers of parents.

While the algorithm is running, you may cancel it at anytime. This may be important if you attempt to discover asymmetry in nodes with large state spaces and/or many parents.