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.