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:

Stage 1: Stage 2: Stage 3: Stage 4:         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.

The Results summary

Downloads