Name
Abstract | ||
|---|---|---|
Probabilistic inference and maximum a posteriori (MAP) explanation are two important and related problems on Bayesian belief networks. Both problems are known to be NP-hard for both approximation and exact solution. In 1997, Dagum and Luby showed that efficiently approximating probabilistic inference is possible for belief networks in which all probabilities are bounded away from 0. In this paper, we show that the corresponding result for MAP explanation does not hold: finding, or approximating, MAPs for belief networks remains NP-hard for belief networks with probabilities bounded within the range [l, u] for any 0 less than or equal to l < 0.5 < u less than or equal to 1. Our results cover both deterministic and randomized approximation. (C) 2000 Elsevier Science B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0004-3702(00)00076-X | Artif. Intell. |
Keywords | Field | DocType |
bounded probability,approximating maps,belief network,bayesian belief network,bayesian belief networks,satisfiability,complexity,exact solution | Probabilistic inference,Exact solutions in general relativity,Discrete mathematics,Satisfiability,Bayesian network,Artificial intelligence,Bayesian statistics,Maximum a posteriori estimation,Machine learning,Mathematics,Bounded function,Belief propagation | Journal |
Volume | Issue | ISSN |
124 | 2 | 0004-3702 |
Citations | PageRank | References |
3 | 0.40 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashraf M. Abdelbar | 1 | 243 | 25.43 |
| Stephen T. Hedetniemi | 2 | 1575 | 289.01 |
| Sandra M. Hedetniemi | 3 | 230 | 20.65 |