Documentation: Programming guide

LEG structure and iteration

Each knowlegde base possesses an internal structure of tables to store the actual probabilities in. This is mostly done automatically and the application does not have to worry about this. The tables are called LEGs (local event groups) and represent relationships between the variables. Each LEG contains a set of variables and stores probabilities on all configurations on this set.

Activity States of a Rule

A rule is said to fit into a LEG, if the set of variables mentioned in the rule is a subset of the variables in the LEG. Fitting rules are either active or activable. Active rules will be learned during the forthcoming iteration process, whereas activable rules are ignored until they are activated. Non-fitting rules are called passive, i.e. they cannot be learned, because there is no LEG they would fit into. To request the actual activity state of a rule, call KBase.getRuleActivity.

An application is able to change the rule's activity state. There are no problems to swap between active and activable. Use the method KBase.toggleRuleActivity for that purpose. To activate a passive rule, the internal LEG structure has to be rebuild. The rebuild process will (in case of success) create a LEG suitable for all rules.

Rebuilding the LEG Structure

The rebuilding process initializes the internal LEG system to activate all rules. In order to rebuild a KBase, you must first supply a suitable enumeration of the variables. Usually, this task is taken by the KBase itself. It provides the method KBase.enumerateVars to create a valid enumeration sequence. Due to the fact that the problem of enumerating a set of variables is very complex (NP-complete), only heuristic algorithms are available. SPIRIT actually provides four heuristics to find an enumeration sequence. Each heuristics will induce a different internal LEG structure. To optimize it, you should try out and compare the four of them.

To be able to compare two structures, and to find out more about the actual LEGs, you can use the method KBase.getLEGInfo. You will seldom need this method, but it provides some interesting information.

After you made up a suitable enumeration of the variables, you can rebuild the LEG structure. This will create a structure without any passive rules. Use the KBase.rebuild method to do so. The whole KBase is reset to uniform distribution. To restore the previously valid probabilities, you have to reinit the structure. Use KBase.reinit for this.

The following example finds the optimal triangulation, rebuilds and reinits the LEGs.

/**
 * Tries to find the optimal variable enumeration and rebuilds.
 */
void rebuildOptimal()
{
	 // Test all 4 methods...
	 int bestSize = 0;
	 int bestMethod = -1;
	 for(int i = 0; i < 4; i++) {
		  try {
				kb.enumerateVars(i);
				kb.rebuild();
				int size = legForestSize();
				if(bestMethod < 0 || size < bestSize) {
					 bestMethod = i;
					 bestSize = size;
				}
		  } catch(KBE kbe) {
		  }
	 }
	 if(bestMethod >= 0) {
		  try {
				kb.enumerateVars(bestMethod);
				kb.rebuild();
				kb.reinit(false);
		  } catch(KBE kbe) {
				// Indicate failure
		  }
	 }
}
/**
 * Computes the size of the actual LEGForest
 * using the KBase.getLEGInfo method.
 * @return the number of configurations needed
 * @see rebuildOptimal
 */
private int legForestSize()
{
	 Vector info = kb.getLEGInfo();
	 int sum = 0;
	 for(int i = 0; i < info.size(); i++) {

		  int[] a = (int[]) info.elementAt(i);
		  int varCount = a[1];

		  int size = 1;
		  try {
				for(int j = 0; j < varCount; j++)
					 size *= kb.getVarArity(a[j + 2]);
		  }
		  catch(KBE kbe) {
		  }
		  sum += size;
	 }
	 return sum;
}

Learning Rules

The process of learning rules into a knowlegde base in SPIRIT is called the iteration. In the actual version of SPIRIT this is a very complex procedure and requires a deeper understanding of the theory. Nevertheless, SPIRIT tries to unburden the application developer from irrelevant details and provides a minimal set of methods for that purpose.

An iteration process can be started at any time, even though the application should ensure a suitable LEG structure (using the rebuild command). The iteration can be performed using the following typical call sequence:

try {
	 kb.beginIteration(0.00000000001, 10);
	 while(!kb.stepIteration());
	 kb.endIteration();
}
catch(KBE kbe) {
	 // Most probably a contradiction
}

Obviously, an iteration process must be embraces with beginIteration and endIteration calls. Remember, that after an iteration was started, calling most other methods would cause an exception raise, because the KBase finds itself then in an inconsistent state. The sequence above would finish after the fulfilling of the termination criterion (i.e. the specified threshold) or with a contradition found. In the latter case, the KBase would return to the probabilities valid before the call of beginIteration.

The sequence above should be useful for knowlegde bases that are known to be consistent. In a more realistic way, the user would like to be able to get information about the state of the iteration after each step. Therefore, SPIRIT includes the KBase.getIterationStatus method. Depending on the results given, the user should be enabled to stop the iteration if it takes too long.

Data Based Learning

Another way of getting knowledge into a KBase is to learn from observations. This is the purpose of the KBase.learnDatabase method. It must be supplied with an InputStream to read the observations from. They are typically stored in a file noticing the SPIRIT database file format.