Class BayesNet

java.lang.Object
  extended by BayesNet

public class BayesNet
extends java.lang.Object

A Bayesian network. Almost all translation procedures are done in this class.


Nested Class Summary
private  class BayesNet.VisitResult
          Immutable class containing a result of a visit in sorting a bucket.
private static class BayesNet.VStat
          Enum for the flags in topological sorting.
 
Field Summary
private  int[][] adjTab
          Directed adjacency table that specifies the network structure of the BN.
private static java.lang.String ATT_BIF_VERSION
           
private static java.lang.String ATT_VARIABLE_TYPE
           
private  java.lang.String basename
          Basename of the input file.
private  java.util.List<java.util.List<Cluster>> bucketList
          List of buckets, where each buckets contains cluster nodes, CPT nodes and instanciation nodes.
private  int[] elimOrder
          Elimination order.
private  int[] evidLevel
          Evidence levels used for generating random evidences.
private  java.io.PrintStream evidPsm
          Output stream for Prism evidences.
private  Format format
          Format of the XML input.
private  boolean hasEvid
          Flag indicating wheter the translator has some evidence file.
private  boolean hasExtElimOrder
          Flag indicating whether we have an external file (BASENAME.num) which specifies the elimination order.
private  boolean hasTrCPT
          Flag indicating whether the CPTs given in the input file are transposed.
private  Cluster[] headAry
          List of cluster nodes that lead to be heads of the translated Prism clauses.
private  int[] invOrder
          Inverse mapping of order[] (the total order).
private static int MAX_NVAR_NAIVE
          Max.
private  boolean modeEvid
          Flag for generating random evidences.
private  boolean modeNormalize
          Flag for normalizing CPT entries.
private  boolean modeRandom
          Flag for assigning random parameters.
private  boolean modeVerbose
          Flag for the verbose mode.
private  boolean modeZeroComp
          Flag for zero-compression of CPTs.
private static double NON_TINY_PROB
          Threshold by which we judge the non-tininess of a float-point number.
private static int NUM_EVID_LEVEL
          Number of levels for random evidences.
private  int[] order
          Total order of the variables in the BN.
private  int[] primCluster
          Primary clusters for variables.
private  int[] primClusterWidth
          The widths of primary clusters.
private  java.io.PrintStream psm
          Output stream for the translated Prism program.
private  java.io.PrintStream[] randEvidPsm
          Output streams for random Prism evidences.
private static java.lang.String TAG_BIF
           
private static java.lang.String TAG_DEFINITION
           
private static java.lang.String TAG_EVIDENCE
           
private static java.lang.String TAG_FOR
           
private static java.lang.String TAG_GIVEN
           
private static java.lang.String TAG_NAME
           
private static java.lang.String TAG_NETWORK
           
private static java.lang.String TAG_OUTCOME
           
private static java.lang.String TAG_PROBABILITY
           
private static java.lang.String TAG_PROPERTY
           
private static java.lang.String TAG_TABLE
           
private static java.lang.String TAG_VALUE
           
private static java.lang.String TAG_VALUES
           
private static java.lang.String TAG_VARIABLE
           
private static java.lang.String TAG_VARIABLENAME
           
private static double TINY_PROB
          Threshold by which we judge the tininess of a float-point number.
private  int[][] uAdjTab
          Undirected adjacency table that specifies the network structure of the BN.
private  java.util.List<Variable> varList
          List of the variables appearing in the BN.
private  java.util.Map<java.lang.String,java.lang.Integer> varMap
          Hashtable for the variable names.
private  java.lang.String version
          Version number of the translator.
 
Constructor Summary
BayesNet(BNSetting setting, org.w3c.dom.Document document, org.w3c.dom.Document documentEvid)
           
 
Method Summary
private  void addXBIFProbability(org.w3c.dom.Node n)
          Finds CPTs and adds them to the DOM tree.
private  void addXBIFVariable(int id, org.w3c.dom.Node n)
          Finds the definitions of random variables and adds them to the DOM tree.
private  void addXMLBIFDefinition(org.w3c.dom.Node n)
          Finds CPTs and adds them to the DOM tree.
private  void addXMLBIFEvidence(int id, org.w3c.dom.Node n)
          Finds evidences and adds them to the DOM tree.
private  void addXMLBIFVariable(int id, org.w3c.dom.Node n)
          Finds the definitions of random variables and adds them to the DOM tree.
private  void buildElimOrder()
          Builds the minimum deficiency order (MDO) using adjacency tables and return it.
 void buildInitialBuckets()
          Builds the initial buckets.
 void buildModes()
          Determines the input/output modes of cluster nodes and CPT nodes.
private  boolean checkHasEvid()
          Checks if there are evidences specified in the input.
private  void checkTableEntries(Variable v)
          Checks if the CPT entries are normalized.
private  void checkTableSize(Variable v)
          Checks the size of each CPT.
 void closeStreams()
          Closes the output streams.
 int[][] getAdjacencyTable()
          Builds the directed adjacency table and return it.
private  java.lang.String getCleanTextContent(org.w3c.dom.Node n)
          Cleans up the text contents by replacing all space symbols by white spaces and perform triming.
 void getElimOrder()
          Gets the elimination order.
 void getEvidLevel()
          Computes the evidence levels for all variables in the BN.
private  void getExternalElimOrder()
          Retrieves the elimination order from the file named BASENAME.num.
private  org.w3c.dom.Node getFirstNetworkNode(org.w3c.dom.Document document)
          Gets the first DOM tree of the BN specification.
 void getInverseTotalOrder()
          Builds the inverse mapping of order[].
private  int[][] getModeDepTable(int bSize, java.util.List<Cluster> bucket)
          Gets the table on input/output dependencies.
 int getNumberOfVariables()
          Returns the number of variables in the BN.
 void getPrimaryCluster()
          Gets the primary clusters for all variables.
 void getTotalOrder()
          Gets the total order of variables by topological sorting.
 int[][] getUndirectedAdjacencyTable()
          Converts a directed adjacency table to the undirected one.
 Variable getVariable(int i)
          Returns the i-th variable in the BN.
private  org.w3c.dom.Node getXBIFFirstNetworkNode(org.w3c.dom.Document document)
          Gets the DOM tree of the XBIF specification of a BN.
private  org.w3c.dom.Node getXMLBIFFirstNetworkNode(org.w3c.dom.Document document)
          Gets the DOM tree of the XMLBIF specification of a BN.
 void growBuckets()
          Grows the buckets one by one.
private  boolean matchName(java.lang.String s, java.lang.String name)
          Matches two strings ignoring the case.
private  void parseXBIFNetwork(org.w3c.dom.Document document)
          Traverses and collects information on the DOM of XBIF network file.
private  void parseXMLBIFEvidence(org.w3c.dom.Document document)
          Traverses and collects information on the DOM of XMLBIF _evidence_ file.
private  void parseXMLBIFNetwork(org.w3c.dom.Document document)
          Traverses and collects information on the DOM of XMLBIF _network_ file.
private  void postCheckNetwork()
          Performs post checking and post processing of the network specification.
 void printAdjacencyTable()
          Prints the directed adjacency table.
 void printBuckets()
          Prints buckets (the base method).
 void printElimOrder()
          Prints the elimination order.
 void printFinalBuckets()
          Prints the buckets finally obtained by the bucket-tree method.
 void printInitialBuckets()
          Prints the initial buckets.
 void printModedBuckets()
          Prints the buckets added the input/output modes.
 void printPrismBuckets()
          Writes the modeling part to the outoput.
 void printPrismCPT()
          Writes the definition of the cpt predicate.
 void printPrismDecls()
          Writes the declaration part to the outoput.
 void printPrismDistrib()
          Writes the naive version of the modeling part.
 void printPrismModes()
          Writes the mode declarations to the outoput.
 void printPrismNaiveBN()
          Writes the naive version of the modeling part.
 void printPrismNames()
          Writes the predicates that relate the names systematically given by the translator to the original ones given in the XML input.
 void printPrismRanges()
          Writes definitions of range/2 into the output according to the value of modeZeroComp.
private  void printPrismRanges2()
          Writes definitions of range/2 into the output without zero compression.
private  void printPrismRanges3()
          Writes definitions of range/3 into the output with zero compression.
 void printPrismSampler()
          Writes the routine for sampling.
 void printPrismSetSwitches()
          Writes the routine for parameter settings.
 void printPrismVersion()
          Writes the version number to the outoput.
 void printPsmEvid()
          Writes the evidences.
 void printPsmRandomEvid()
          Writes the random evidences.
 void printTotalOrder()
          Writes the total order of the variables in the BN.
 void printUndirectedAdjacencyTable()
          Prints the undirected adjacency table.
 void printVariables()
          Writes the variables in the BN.
 void sortBuckets()
          Orders the elements in each bucket according to the input/output modes.
 java.lang.String toString()
          Returns a string representation.
private  void transposeCPT(Variable v)
          Transposes the transposed CPT.
private  int visit(int l, int i, int k, BayesNet.VStat[] visited)
          Visits each variable in the BN based on the direct adjacency table.
private  BayesNet.VisitResult visitBucket(int bSize, int i, BayesNet.VisitResult r, int[][] adj, BayesNet.VStat[] visited, java.util.List<java.lang.Integer> order)
          Visit an element in a bucket recursively.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

TAG_BIF

private static final java.lang.String TAG_BIF
See Also:
Constant Field Values

TAG_NETWORK

private static final java.lang.String TAG_NETWORK
See Also:
Constant Field Values

TAG_NAME

private static final java.lang.String TAG_NAME
See Also:
Constant Field Values

TAG_VARIABLE

private static final java.lang.String TAG_VARIABLE
See Also:
Constant Field Values

TAG_OUTCOME

private static final java.lang.String TAG_OUTCOME
See Also:
Constant Field Values

TAG_DEFINITION

private static final java.lang.String TAG_DEFINITION
See Also:
Constant Field Values

TAG_FOR

private static final java.lang.String TAG_FOR
See Also:
Constant Field Values

TAG_GIVEN

private static final java.lang.String TAG_GIVEN
See Also:
Constant Field Values

TAG_TABLE

private static final java.lang.String TAG_TABLE
See Also:
Constant Field Values

TAG_PROPERTY

private static final java.lang.String TAG_PROPERTY
See Also:
Constant Field Values

TAG_EVIDENCE

private static final java.lang.String TAG_EVIDENCE
See Also:
Constant Field Values

TAG_VARIABLENAME

private static final java.lang.String TAG_VARIABLENAME
See Also:
Constant Field Values

TAG_VALUE

private static final java.lang.String TAG_VALUE
See Also:
Constant Field Values

TAG_VALUES

private static final java.lang.String TAG_VALUES
See Also:
Constant Field Values

TAG_PROBABILITY

private static final java.lang.String TAG_PROBABILITY
See Also:
Constant Field Values

ATT_BIF_VERSION

private static final java.lang.String ATT_BIF_VERSION
See Also:
Constant Field Values

ATT_VARIABLE_TYPE

private static final java.lang.String ATT_VARIABLE_TYPE
See Also:
Constant Field Values

NUM_EVID_LEVEL

private static final int NUM_EVID_LEVEL
Number of levels for random evidences.

See Also:
Constant Field Values

NON_TINY_PROB

private static final double NON_TINY_PROB
Threshold by which we judge the non-tininess of a float-point number.

See Also:
Constant Field Values

TINY_PROB

private static final double TINY_PROB
Threshold by which we judge the tininess of a float-point number.

See Also:
Constant Field Values

MAX_NVAR_NAIVE

private static final int MAX_NVAR_NAIVE
Max. number of variables allowed for a naive definition of a BN.

See Also:
Constant Field Values

basename

private java.lang.String basename
Basename of the input file.


version

private java.lang.String version
Version number of the translator.


format

private Format format
Format of the XML input.


hasExtElimOrder

private boolean hasExtElimOrder
Flag indicating whether we have an external file (BASENAME.num) which specifies the elimination order.


hasTrCPT

private boolean hasTrCPT
Flag indicating whether the CPTs given in the input file are transposed.


modeZeroComp

private boolean modeZeroComp
Flag for zero-compression of CPTs.


modeRandom

private boolean modeRandom
Flag for assigning random parameters.


modeEvid

private boolean modeEvid
Flag for generating random evidences.


modeNormalize

private boolean modeNormalize
Flag for normalizing CPT entries.


modeVerbose

private boolean modeVerbose
Flag for the verbose mode.


hasEvid

private boolean hasEvid
Flag indicating wheter the translator has some evidence file.


varList

private java.util.List<Variable> varList
List of the variables appearing in the BN.


varMap

private java.util.Map<java.lang.String,java.lang.Integer> varMap
Hashtable for the variable names.


adjTab

private int[][] adjTab
Directed adjacency table that specifies the network structure of the BN.


uAdjTab

private int[][] uAdjTab
Undirected adjacency table that specifies the network structure of the BN.


elimOrder

private int[] elimOrder
Elimination order. `i = elimOrder[q]' indicates that the q-th element in the elimination order is variable i.


bucketList

private java.util.List<java.util.List<Cluster>> bucketList
List of buckets, where each buckets contains cluster nodes, CPT nodes and instanciation nodes.


headAry

private Cluster[] headAry
List of cluster nodes that lead to be heads of the translated Prism clauses.


order

private int[] order
Total order of the variables in the BN. This total order is obtained by topological sorting.


invOrder

private int[] invOrder
Inverse mapping of order[] (the total order).


primCluster

private int[] primCluster
Primary clusters for variables. The primary cluster for a variable is the smallest cluster to which the variable belongs. Primary clusters are used in computing the marginal distribution of a variable.


primClusterWidth

private int[] primClusterWidth
The widths of primary clusters.


psm

private java.io.PrintStream psm
Output stream for the translated Prism program.


evidPsm

private java.io.PrintStream evidPsm
Output stream for Prism evidences.


randEvidPsm

private java.io.PrintStream[] randEvidPsm
Output streams for random Prism evidences.


evidLevel

private int[] evidLevel
Evidence levels used for generating random evidences. The evidence level of variable i can be 1 ... NUM_EVID_LEVEL. If the evidence level of variable i is k, the evidences for variable i will be given in k files (i.e. BASENAME_revid{NUM_EVID_LEVEL - k + 1}.psm, ..., BASENAME_revid{NUM_EVID_LEVEL}.psm).

Constructor Detail

BayesNet

public BayesNet(BNSetting setting,
                org.w3c.dom.Document document,
                org.w3c.dom.Document documentEvid)
         throws B2PException
Parameters:
setting - Setting for the translator.
document - DOM tree of the XML specification of a BN.
documentEvid - DOM tree of the XML specification of evidences.
Throws:
B2PException
Method Detail

checkHasEvid

private boolean checkHasEvid()
Checks if there are evidences specified in the input.


parseXMLBIFNetwork

private void parseXMLBIFNetwork(org.w3c.dom.Document document)
                         throws B2PException
Traverses and collects information on the DOM of XMLBIF _network_ file.

Throws:
B2PException

parseXMLBIFEvidence

private void parseXMLBIFEvidence(org.w3c.dom.Document document)
                          throws B2PException
Traverses and collects information on the DOM of XMLBIF _evidence_ file.

Throws:
B2PException

parseXBIFNetwork

private void parseXBIFNetwork(org.w3c.dom.Document document)
                       throws B2PException
Traverses and collects information on the DOM of XBIF network file.

Throws:
B2PException

postCheckNetwork

private void postCheckNetwork()
                       throws B2PException
Performs post checking and post processing of the network specification.

Throws:
B2PException

checkTableSize

private void checkTableSize(Variable v)
                     throws B2PException
Checks the size of each CPT. It is assumed that the parents and outcomes of v, and the outcomes of v's parents are non-null.

Throws:
B2PException

transposeCPT

private void transposeCPT(Variable v)
Transposes the transposed CPT.


checkTableEntries

private void checkTableEntries(Variable v)
                        throws B2PException
Checks if the CPT entries are normalized.

Throws:
B2PException

closeStreams

public void closeStreams()
Closes the output streams.


getXMLBIFFirstNetworkNode

private org.w3c.dom.Node getXMLBIFFirstNetworkNode(org.w3c.dom.Document document)
                                            throws B2PException
Gets the DOM tree of the XMLBIF specification of a BN. Note that we only get the first Bayesian network here.

Throws:
B2PException

getXBIFFirstNetworkNode

private org.w3c.dom.Node getXBIFFirstNetworkNode(org.w3c.dom.Document document)
                                          throws B2PException
Gets the DOM tree of the XBIF specification of a BN. Note that we only get the first Bayesian network here.

Throws:
B2PException

getFirstNetworkNode

private org.w3c.dom.Node getFirstNetworkNode(org.w3c.dom.Document document)
                                      throws B2PException
Gets the first DOM tree of the BN specification.

Throws:
B2PException

addXMLBIFVariable

private void addXMLBIFVariable(int id,
                               org.w3c.dom.Node n)
                        throws B2PException
Finds the definitions of random variables and adds them to the DOM tree.

Throws:
B2PException

addXMLBIFDefinition

private void addXMLBIFDefinition(org.w3c.dom.Node n)
                          throws B2PException
Finds CPTs and adds them to the DOM tree.

Throws:
B2PException

addXMLBIFEvidence

private void addXMLBIFEvidence(int id,
                               org.w3c.dom.Node n)
                        throws B2PException
Finds evidences and adds them to the DOM tree.

Throws:
B2PException

addXBIFVariable

private void addXBIFVariable(int id,
                             org.w3c.dom.Node n)
                      throws B2PException
Finds the definitions of random variables and adds them to the DOM tree.

Throws:
B2PException

addXBIFProbability

private void addXBIFProbability(org.w3c.dom.Node n)
                         throws B2PException
Finds CPTs and adds them to the DOM tree.

Throws:
B2PException

matchName

private boolean matchName(java.lang.String s,
                          java.lang.String name)
Matches two strings ignoring the case.


getCleanTextContent

private java.lang.String getCleanTextContent(org.w3c.dom.Node n)
Cleans up the text contents by replacing all space symbols by white spaces and perform triming.


getNumberOfVariables

public int getNumberOfVariables()
Returns the number of variables in the BN.


getVariable

public Variable getVariable(int i)
Returns the i-th variable in the BN.


getAdjacencyTable

public int[][] getAdjacencyTable()
Builds the directed adjacency table and return it.


printAdjacencyTable

public void printAdjacencyTable()
Prints the directed adjacency table.


printUndirectedAdjacencyTable

public void printUndirectedAdjacencyTable()
Prints the undirected adjacency table.


getUndirectedAdjacencyTable

public int[][] getUndirectedAdjacencyTable()
Converts a directed adjacency table to the undirected one.


getElimOrder

public void getElimOrder()
                  throws B2PException
Gets the elimination order. If it is not given in the file named BASENAME.num, we compute MDO (minimum deficiency order), which is described in:

B. D'Ambrosio (1999). Inference in Bayesian networks. AI Magazine, 20 (2), pp.21-36.

Throws:
B2PException

getExternalElimOrder

private void getExternalElimOrder()
                           throws B2PException
Retrieves the elimination order from the file named BASENAME.num.

Throws:
B2PException

buildElimOrder

private void buildElimOrder()
Builds the minimum deficiency order (MDO) using adjacency tables and return it.


printElimOrder

public void printElimOrder()
                    throws B2PException
Prints the elimination order.

Throws:
B2PException

buildInitialBuckets

public void buildInitialBuckets()
                         throws B2PException
Builds the initial buckets.

Throws:
B2PException

growBuckets

public void growBuckets()
                 throws B2PException
Grows the buckets one by one. The procedure is based on the bucket-tree method described in:

K. Kask, R. Dechter, J. Larrosa and A. Dechter (2005). Unifying tree decompositions for reasoning in graphical models. Artificial Intelligence, 166 (1-2), pp.165-193.

Throws:
B2PException

buildModes

public void buildModes()
                throws B2PException
Determines the input/output modes of cluster nodes and CPT nodes.

Throws:
B2PException

sortBuckets

public void sortBuckets()
                 throws B2PException
Orders the elements in each bucket according to the input/output modes. To do this, we basically perform a topological sorting. Besides, if a dependency loop is found while sorting, we add an instanciation node to break such a loop.

Throws:
B2PException

visitBucket

private BayesNet.VisitResult visitBucket(int bSize,
                                         int i,
                                         BayesNet.VisitResult r,
                                         int[][] adj,
                                         BayesNet.VStat[] visited,
                                         java.util.List<java.lang.Integer> order)
Visit an element in a bucket recursively. This is a depth-first recursive routine for topological sorting.


getModeDepTable

private int[][] getModeDepTable(int bSize,
                                java.util.List<Cluster> bucket)
                         throws B2PException
Gets the table on input/output dependencies. Note that `bSize' is the size of the original bucket and `bucket' may contain some instanciation nodes after the (bSize)-th element.

Throws:
B2PException

printInitialBuckets

public void printInitialBuckets()
Prints the initial buckets.


printFinalBuckets

public void printFinalBuckets()
Prints the buckets finally obtained by the bucket-tree method.


printModedBuckets

public void printModedBuckets()
Prints the buckets added the input/output modes.


printBuckets

public void printBuckets()
Prints buckets (the base method).


printPrismVersion

public void printPrismVersion()
Writes the version number to the outoput.


printPrismModes

public void printPrismModes()
Writes the mode declarations to the outoput.


printPrismDecls

public void printPrismDecls()
Writes the declaration part to the outoput.


printPrismBuckets

public void printPrismBuckets()
                       throws B2PException
Writes the modeling part to the outoput.

Throws:
B2PException

printPrismRanges

public void printPrismRanges()
Writes definitions of range/2 into the output according to the value of modeZeroComp. Also writes definitions of range/3 If modeZeroComp is true.


printPrismRanges2

private void printPrismRanges2()
Writes definitions of range/2 into the output without zero compression.


printPrismRanges3

private void printPrismRanges3()
Writes definitions of range/3 into the output with zero compression.


printPrismCPT

public void printPrismCPT()
Writes the definition of the cpt predicate.


getTotalOrder

public void getTotalOrder()
Gets the total order of variables by topological sorting.


visit

private int visit(int l,
                  int i,
                  int k,
                  BayesNet.VStat[] visited)
Visits each variable in the BN based on the direct adjacency table. This is a depth-first recursive routine for topological sorting.


getInverseTotalOrder

public void getInverseTotalOrder()
Builds the inverse mapping of order[].


getPrimaryCluster

public void getPrimaryCluster()
Gets the primary clusters for all variables.


printPrismNaiveBN

public void printPrismNaiveBN()
Writes the naive version of the modeling part. This part will be skipped if we have more than MAX_NVAR_NAIVE variables.


printPrismDistrib

public void printPrismDistrib()
Writes the naive version of the modeling part.


printPrismSetSwitches

public void printPrismSetSwitches()
Writes the routine for parameter settings.


printPrismSampler

public void printPrismSampler()
Writes the routine for sampling.


printPrismNames

public void printPrismNames()
Writes the predicates that relate the names systematically given by the translator to the original ones given in the XML input.


printTotalOrder

public void printTotalOrder()
Writes the total order of the variables in the BN.


printVariables

public void printVariables()
Writes the variables in the BN.


getEvidLevel

public void getEvidLevel()
Computes the evidence levels for all variables in the BN.


printPsmEvid

public void printPsmEvid()
Writes the evidences.


printPsmRandomEvid

public void printPsmRandomEvid()
Writes the random evidences. To handle the case where zero-compression is enabled, we should make a sampling following the topological order to take the context-specificity into account.


toString

public java.lang.String toString()
Returns a string representation.

Overrides:
toString in class java.lang.Object