Approximating MAPs for belief networks is NP-hard and other theorems

被引:56
作者
Abdelbar, AM
Hedetniemi, SM
机构
[1] Amer Univ Cairo, Dept Comp Sci, Cairo, Egypt
[2] Clemson Univ, Dept Comp Sci, Clemson, SC 29634 USA
关键词
Bayesian belief networks; dynamic abduction; next-best explanation; probabilistic reasoning; uncertainty; complexity; satisfiability;
D O I
10.1016/S0004-3702(98)00043-5
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Finding maximum a posteriori (MAP) assignments, also called Most Probable Explanations, is an important problem on Bayesian belief networks. Shimony has shown that finding MAPs is NP-hard. In this paper, we show that approximating MAPs with a constant ratio bound is also NP-hard. In addition, we examine the complexity of two related problems which have been mentioned in the literature. We show that given the MAP for a belief network and evidence set, or the family of MAPs if the optimal is not unique, it remains NP-hard to find, or approximate, alternative next-best explanations. Furthermore, we show that given the MAP, or MAPs, for a belief network and an initial evidence set, it is also NP-hard to find, or approximate, the MAP assignment for the same belief network with a modified evidence set that differs from the initial set by the addition or removal of even a single node assignment. Finally, we show that our main result applies to networks with constrained in-degree and out-degree, applies to randomized approximation, and even still applies if the ratio bound, instead of being constant, is allowed to be a polynomial function of various aspects of the network topology. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:21 / 38
页数:18
相关论文
共 24 条
[1]  
ABDELBAR AM, 1998, P IMACS C COMP ENG S
[2]  
ABDELBAR AM, 1997, P IEEE INT C NEUR NE, V1, P450
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]  
[Anonymous], 1991, UNCERTAINTY ARTIFICI
[5]   COST-BASED ABDUCTION AND MAP EXPLANATION [J].
CHARNIAK, E ;
SHIMONY, SE .
ARTIFICIAL INTELLIGENCE, 1994, 66 (02) :345-374
[6]   THE COMPUTATIONAL-COMPLEXITY OF PROBABILISTIC INFERENCE USING BAYESIAN BELIEF NETWORKS [J].
COOPER, GF .
ARTIFICIAL INTELLIGENCE, 1990, 42 (2-3) :393-405
[7]   APPROXIMATING PROBABILISTIC INFERENCE IN BAYESIAN BELIEF NETWORKS IS NP-HARD [J].
DAGUM, P ;
LUBY, M .
ARTIFICIAL INTELLIGENCE, 1993, 60 (01) :141-153
[8]  
Goldberg D., 1989, GENETIC ALGORITHMS S
[9]   OPTIMIZATION BY SIMULATED ANNEALING [J].
KIRKPATRICK, S ;
GELATT, CD ;
VECCHI, MP .
SCIENCE, 1983, 220 (4598) :671-680
[10]  
LAURITZEN SL, 1988, J ROY STAT SOC B MET, V50, P157