Title :
A Lagrangian Relaxation Algorithm for Finding the MAP Configuration in QMR-DT
Author :
Yu, Feili ; Tu, Fang ; Tu, Haiying ; Pattipati, Krishna R.
Author_Institution :
Connecticut Univ., Storrs
Abstract :
The quick medical reference decision-theoretic (QMR-DT) network is a large two-layer Bayesian network (BN) [consisting of 571 diseases (ldquofailure sourcesrdquo) and 4075 findings (ldquotest outcomesrdquo)] based on expert and statistical knowledge in internal medicine. The maximum a posteriori (MAP) diagnosis (configuration) based on QMR-DT constitutes an intractable inference problem for all, but a small set of, cases. Consequently, we consider near-optimal algorithms for finding the most likely set of diseases given a set of findings. A computationally efficient algorithm that can handle cases with hundreds of positive findings, i.e., the Lagrangian relaxation algorithm (LRA), is presented. By relaxing the original problem via a set of Lagrange multipliers, the LRA generates an upper bound for the objective function. The near-optimal diagnosis (configuration) is found by minimizing the duality gap via a subgradient method. Numerical experiments show that the LRA is promising in achieving highly accurate diagnosis, and that it is computationally very efficient in solving MAP configuration problems in large and dense two-layer BNs with noisy-OR (BN2O) nodes and containing undirected loops (cycles), such as the QMR-DT network.
Keywords :
belief networks; decision support systems; diseases; health care; inference mechanisms; medical diagnostic computing; medical expert systems; statistical analysis; Lagrange multiplier; Lagrangian relaxation algorithm; MAP configuration; diseases; expert system; internal medicine; intractable inference problem; maximum a posteriori diagnosis; near-optimal algorithm; quick medical reference decision-theoretic network; statistical knowledge; subgradient method; two-layer Bayesian network; Bayesian methods; Computer networks; Diseases; Genetic algorithms; Inference algorithms; Lagrangian functions; Medical diagnostic imaging; Medical services; Spread spectrum communication; Upper bound; Approximate belief revision algorithm (ABR); Lagrangian relaxation algorithm (LRA); Quick Medical Reference (QMR); approximate inference; decision-theoretic (DT); genetic algorithm (GA); maximum a posteriori (MAP) configuration; minibucket elimination (MBE); multiple-disease diagnosis;
Journal_Title :
Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on
DOI :
10.1109/TSMCA.2007.902657