๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the complexity of inference about probabilistic relational models

โœ Scribed by Manfred Jaeger

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

No coin nor oath required. For personal study only.

โœฆ Synopsis

We investigate the complexity of probabilistic inference from knowledge bases that encode probability distributions on finite domain relational structures. Our interest here lies in the complexity in terms of the domain under consideration in a specific application instance. We obtain the result that assuming NETIME = ETIME this problem is not polynomial for reasonably expressive representation systems. The main consequence of this result is that it is unlikely to find inference techniques with a better worst-case behavior than the commonly employed strategy of constructing standard Bayesian networks over ground atoms (knowledge based model construction).

๐Ÿ“œ SIMILAR VOLUMES

The computational complexity of probabil
The computational complexity of probabilistic inference using bayesian belief networks
โœ Gregory F. Cooper ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 708 KB

Bayesian belief networks provide a natural, efficient method for representing probabilistic dependencies among a set of variables. For these reasons, numerous researchers are exploring the use of belief networks as a knowledge representation m artificial intelligence. Algorithms have been developed

On modeling of if-then rules for probabi
On modeling of if-then rules for probabilistic inference
โœ Hung T. Nguyen; I. R. Goodman ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 417 KB

We identify various situations in probabilistic intelligent systems in which conditionals (rules) as mathematical entities as well as their conditional logic operations are needed. In discussing Bayesian updating procedure and belief function construction, we provide a new method for modeling if. .