DocumentCode :
1101585
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
Volume :
37
Issue :
5
fYear :
2007
Firstpage :
746
Lastpage :
757
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;
fLanguage :
English
Journal_Title :
Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on
Publisher :
ieee
ISSN :
1083-4427
Type :
jour
DOI :
10.1109/TSMCA.2007.902657
Filename :
4292232
Link To Document :
بازگشت