An algorithm for finding MAPs for belief networks through cost-based abduction

被引：16

作者：

Abdelbar, AM ^{[1
]}

机构：

[1] Amer Univ Cairo, Dept Comp Sci, Cairo, Egypt

来源：

ARTIFICIAL INTELLIGENCE | 1998年 / 104卷 / 1-2期

关键词：

explanation; belief revision; uncertainty; complexity; probabilistic reasoning;

D O I：

10.1016/S0004-3702(98)00074-5

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In cost-based abduction, the objective is to find the least-cost set of hypotheses that are sufficient to explain the observed evidence. In the maximum a-posteriori (MAP) assignment problem on Bayesian belief networks, the objective is to find the network assignment A with highest conditional probability P(A\E), where E represents the observed evidence. In this paper, we present a provably-correct linear-time transformation that allows algorithms and heuristic methods for cost-based abduction, such as Charniak and Shimony's best-first search method or Santos' integer linear programming approach, to be used for the MAP problem. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：331 / 338

页数：8

共 17 条

[1]

[Anonymous], 451 SRI INT

[2]

[Anonymous], 1991, UNCERTAINTY ARTIFICI

[3]

CHARNIAK E, 1991, PROCEEDINGS : NINTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS 1 AND 2, P446

[4] COST-BASED ABDUCTION AND MAP EXPLANATION [J].

CHARNIAK, E ;

SHIMONY, SE .

ARTIFICIAL INTELLIGENCE, 1994, 66 (02) :345-374

[5]

CHARNIAK E, 1990, P NAT C ART INT AAAI

[6]

GAREY M, 1979, COMPUTRS INTRACTABIL

[7]

HOBBS JP, 1988, P 26 ANN M ASS COMP

[8]

HOPFIELD JJ, 1985, BIOL CYBERN, V52, P141

[9] NEURAL NETWORKS AND PHYSICAL SYSTEMS WITH EMERGENT COLLECTIVE COMPUTATIONAL ABILITIES [J].

HOPFIELD, JJ .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA-BIOLOGICAL SCIENCES, 1982, 79 (08) :2554-2558

[10]

NERNHAUSER GL, 1989, OPTIMIZATION HDB OPE, V1

← 1 2 →