Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

被引：10
作者：
Shimony, SE [1 ]
Domshlak, C
机构：
[1] Ben Gurion Univ Negev, Dept Comp Sci, IL-84105 Beer Sheva, Israel
[2] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA
来源：
ARTIFICIAL INTELLIGENCE | 2003年 / 151卷 / 1-2期
关键词：
probabilistic reasoning; Bayes networks; complexity; singly-connected DAGs;
D O I：
10.1016/S0004-3702(03)00110-3
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Directed-path (DP) singly-connected Bayesian networks are an interesting special case that, in particular. includes both polytrees and two-level networks. We analyze the computational complexity of these networks. The prediction problem is shown to be easy, as standard message passing can perform correct updating. However, diagnostic reasoning is hard even for DP singly-connected networks. In addition, finding the most-probable explanation (MPE) is hard, even without evidence. Finally. complexity of nearly DP singly-connected networks is analyzed. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：213 / 225
页数：13
相关论文
共 27 条
[1]   Approximating MAPs for belief networks is NP-hard and other theorems [J].
Abdelbar, AM ;
Hedetniemi, SM .
ARTIFICIAL INTELLIGENCE, 1998, 102 (01) :21-38
[2]  
Bubley R, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P248
[3]  
CHARNIAK E, 1991, AI MAG, V12, P50
[4]   THE COMPUTATIONAL-COMPLEXITY OF PROBABILISTIC INFERENCE USING BAYESIAN BELIEF NETWORKS [J].
COOPER, GF .
ARTIFICIAL INTELLIGENCE, 1990, 42 (2-3) :393-405
[5]   APPROXIMATING PROBABILISTIC INFERENCE IN BAYESIAN BELIEF NETWORKS IS NP-HARD [J].
DAGUM, P ;
LUBY, M .
ARTIFICIAL INTELLIGENCE, 1993, 60 (01) :141-153
[6]  
DARWICHE A, 1995, P 11 C UNC ART INT U, P99
[7]   Local conditioning in Bayesian networks [J].
Diez, FJ .
ARTIFICIAL INTELLIGENCE, 1996, 87 (1-2) :1-20
[8]  
DOMSHLAK C, 2002, P 6 INT C ART INT PL, P34
[9]  
GAREY MR, 1979, COMPUTERS INTRACTABI, P190
[10]  
Horvitz E., 1989, P C UNC ART INT WIND, P182
123