Optimizing
the elimination order
of the
variables of the Bayesian networks.
Last updated 19.2.2002
By
David
Milman Yaniv Ben-Zrihem
under guidance of Prof. Dan
Gaiger and
Ma'ayan Fishelson
The Program presented here is
a modification of the SUPERLINK
program.
Problem:
The likelihood calculation on the given input pedigrees is performed
in a couple of stages:
Stage 1:
First, each pedigree is translated into a Bayesian network.
Stage 2:
Then, value elimination is performed for each pedigree (i.e.,
some of the impossible values of the variables of the network are eliminated).
Stage 3:
Third, an elimination order for the variables of each Bayesian
network is determined, according to some heuristic.
Stage 4:
Last, the likelihood of the pedigrees given the theta values
is calculated. This is done by performing inference on the Bayesian networks
constructed in stages 1 & 2, by performing variable elimination according
to the elimination order determined in stage 3.
In general, many possible elimination
orders exist. An optimal elimination order is one that minimizes the size
of the probability tables created during the inference process. The size
of the probability tables created affects both the memory overhead and
the time bounds. Therefore, finding a good elimination order is essential.
The task of finding an optimal elimination order is NP-complete. The goal
of this project is to try and optimize the elimination order found, by
experimenting with different heuristics for finding an elimination order.
Implementation
The original SUPERLINK program used
the greedy approach to calculate the elimination order. Our implementation
based on the that greedy function, however, in each iteration of a non-deterministic
calculation we do not choose the best (meaning: with the smallest table
to create) variable, rather we keep an array of numerous smallest variables,
and choose one randomly.
After running one deterministic (original greedy) function and a certain
number of random functions, we return the elimination order such that the
sum of tables to create in the Elimination algorithm itself in minimum,
considering the sum of tables to create as an estimation of the run time.
Each random iteration has
some parameters that effect the results, some chosen randomly and others
may have already been decided from past decisions. for specific information
please read the full report.
In the table linked below summarized
the results of the original program, the new program with the (alleged)
best parameters chosen manually and some possible predetermined parameters.
Downloads