APPROXIMATING PROBABILISTIC INFERENCE IN BAYESIAN BELIEF NETWORKS

被引:23
作者
DAGUM, P [1 ]
CHAVEZ, RM [1 ]
机构
[1] ROCKWELL INT CORP,PALO ALTO LAB,PALO ALTO,CA
基金
美国国家科学基金会;
关键词
D O I
10.1109/34.204906
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
A belief network comprises a graphical representation of dependencies between variables of a domain and a set of conditional probabilities associated with each dependency. Unless P=NP, an efficient, exact algorithm does not exist to compute probabilistic inference in belief networks. Stochastic simulation methods, which often improve run times, provide an alternative to exact inference algorithms. We present such a stochastic simulation algorithm D-BNRAS that is a randomized approximation scheme. To analyze the run time, we parameterize belief networks by the dependence value D(xi), which is a measure of the cumulative strengths of the belief network dependencies given background evidence xi. This parameterization defines the class of f-dependence networks. The run time of D-BNRAS is polynomial when f is a polynomial function. Thus, the results of this paper prove the existence of a class of belief networks for which inference approximation is polynomial and, hence, provably faster than any exact algorithm.
引用
收藏
页码:246 / 255
页数:10
相关论文
共 20 条
[1]  
BERZUINI C, 1989, 1989 P WORKSH UNC AR, P14
[2]  
BRODER AZ, 1986, 18TH P ACM S THEOR C, P50
[3]  
CHAVEZ R, 1990, 6TH P C UNC ART INT, P130
[4]   A RANDOMIZED APPROXIMATION ALGORITHM FOR PROBABILISTIC INFERENCE ON BAYESIAN BELIEF NETWORKS [J].
CHAVEZ, RM ;
COOPER, GF .
NETWORKS, 1990, 20 (05) :661-685
[5]  
CHAVEZ RM, 1990, THESIS STANFORD U ST
[6]   THE COMPUTATIONAL-COMPLEXITY OF PROBABILISTIC INFERENCE USING BAYESIAN BELIEF NETWORKS [J].
COOPER, GF .
ARTIFICIAL INTELLIGENCE, 1990, 42 (2-3) :393-405
[7]  
DAGUM P, 1991, KSL9151 STANF U KNOW
[8]  
DAGUM P, 1992, 8TH P C UNC ART INT, P49
[9]  
DAGUM P, 1991, KSL9167 STANF U KNOW
[10]  
FUNG R, 1990, UNCERTAINTY ARTIFICI, V5, P209