𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of approximating MAPs for belief networks with bounded probabilities

✍ Scribed by Ashraf M. Abdelbar; Stephen T. Hedetniemi; Sandra M. Hedetniemi

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
69 KB
Volume
124
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

✦ Synopsis

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 l < 0.5 < u 1. Our results cover both deterministic and randomized approximation.

πŸ“œ SIMILAR VOLUMES

On the complexity of approximating mappi
On the complexity of approximating mappings using feedforward networks
✍ Pascal Koiran πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 359 KB

I4~, study the approximation o.f continuous mappings and dichotomies by one-hidden-layer networks from a computational point of view Our approach is based on a new approximation method specially designed for constructing "small networks. We give upper bounds on the size o.f these networks.

The bounded approximation property for s
The bounded approximation property for spaces of holomorphic mappings on infinite dimensional spaces
✍ Erhan Γ‡alışkan πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 175 KB πŸ‘ 1 views

## Abstract We study the bounded approximation property for spaces of holomorphic functions. We show that if __U__ is a balanced open subset of a FrΓ©chet–Schwartz space or (__DFM__ )‐space __E__ , then the space ℋ︁(__U__ ) of holomorphic mappings on __U__ , with the compact‐open topology, has the b