VEC
The VEC package performs exact inference in Bayesian networks. Specifically, it computes the probability of the evidence.
Author
Description
The vec package is based on variable elimination+ conditioning framework. When a problem having a high induced with is encountered, variable or bucket elimination may be unsuitable, primarily because of its extensive memory demand. To alleviate space complexity, another universal method for problem solving called conditioning can be incorporated.
Conditioning is a generic name for algorithms that search the space of partial value assignments of partial conditioning. Conditioning means splitting a problem into subproblems based on a certain condition. In general, a subset of variables, conditioning variables, will be instantiated, thus generating a subproblem that can be solved by any means; if the resulting subproblem is unsolvable, or if more solutions are needed, the algorithm can try different assignments to the conditioning set. Algorithms such as backtracking and branch and bound may be viewed as conditioning algorithms, while cutset-conditioning applies conditioning to a subset of variables that form a cycle-cutset of the interaction graph, and solves the resulting subproblem by bucket-elimination.
The complexity of conditioning algorithms is exponential in the conditioning set, which is normally larger than the induced-width and which frequently includes all variables. However, the space complexity of conditioning is only linear. Moreover, empirical studies show that its average performance is often far superior to that of bucket-elimination. This suggests that combining elimination with conditioning may be the key to improving reasoning. Particularly, tailoring the balance of elimination and conditioning to the problem instance may better utilize the benefits in each scheme on a case by case basis; we may have better performance guarantees, better space complexity, and better overall average performance.
Conditioning can be easily incorporated into the bucket elimination framework. Whenever a variable is processed, it can either be eliminated or conditioned upon, a decision that can be made statically or dynamically during run-time.
Input format
The belief network and the evidence need to be specified in the UAI Format.
For some example problems please see our Repository.
Usage
The algorithm is invoked with three arguments:
vec <networkFile> <evidenceFile> <seed>
with the following meaning:
<networkFile> specifies the path to the problem network specification in UAI format.
<evicendeFile> specifies the path to the evidence specification according to the UAI format.
<seed> Integer used as seed by the internal random number generator.
Download
A 32-bit Linux binary and an example parameter file is available here.