A fast hill-climbing approach without an energy function for probabilistic reasoning

Integer linear programming (ILP) has long been an important tool for operations research akin to the AI search heuristics for NP-hard problems. However, there has been relatively little incentive to use it in AI, even though it also deals with optimization. The problem stems from the misperception that because the general ILP problem is difficult to solve, then it will be difficult for all cases. It is known that AI search at first glance also seems this way until one begins to apply it to a specific domain. Clearly, there are many gains to be had from studying the problem with a different perspective like ILP. The authors look at probabilistic reasoning with Bayesian networks. For some time now, they have been stalled by its computational complexities. Algorithms have been designed for small classes of networks, but have been mainly inextensible to the general case. In particular, the authors consider belief revision in Bayesian networks which is the search for the most probable explanation for some given evidence. They present a new approach for computing belief revision from the ILP point of view. By observing various properties inherent in Bayesian networks, one can successfully develop a hill-climbing strategy which does not require an energy function. This approach can handle the entire class of Bayesian networks. Furthermore, experimental results indicate that finding the most probable explanation can be accomplished fairly easily