Hill-climbing and branch-and-bound algorithms for exact and approximate inference in credal networks

被引：21
作者：
Cano, Andres [1 ]
Gomez, Manuel [1 ]
Moral, Serafin [1 ]
Abellan, Joaquin [1 ]
机构：
[1] Univ Granada, ETS Ingn Informat, Dept Comp Sci & Artificial Intelligence, E-18071 Granada, Spain
来源：
INTERNATIONAL JOURNAL OF APPROXIMATE REASONING | 2007年 / 44卷 / 03期
关键词：
credal network; probability intervals; Bayesian networks; strong independence; hill-climbing; branch-and-bound algorithms;
D O I：
10.1016/j.ijar.2006.07.020
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
This paper proposes two new algorithms for inference in credal networks. These algorithms enable probability intervals to be obtained for the states of a given query variable. The first algorithm is approximate and uses the hill-climbing technique in the Shenoy-Shafer architecture to propagate in join trees; the second is exact and is a modification of Rocha and Cozman's branch-and-bound algorithm, but applied to general directed acyclic graphs, (C) 2006 Elsevier Inc. All rights reserved.
引用
收藏
页码：261 / 280
页数：20
相关论文
共 29 条
[11]   Credal networks [J].
Cozman, FG .
ARTIFICIAL INTELLIGENCE, 2000, 120 (02) :199-233
[12]  
COZMAN FG, 1997, P 13 C UNC ART INT
[13]  
COZMAN FG, 1998, P 14 C UNC ART INT U, P89
[14]  
de Campos CP, 2004, FRONT ARTIF INTEL AP, V109, P50
[15]  
DECAMPOS CP, 2005, P 4 INT S IMPR PROB, P78
[16]  
Elvira-Consortium, 2002, P 1 EUR WORKSH PROB, P222
[17]  
FERTIG KW, 1990, UNCERTAINTY ARTIFICI, V5, P149
[18]  
KOHLAS J, 2003, DISCRETE MATH & THEO, P1
[19]   ON INFORMATION AND SUFFICIENCY [J].
KULLBACK, S ;
LEIBLER, RA .
ANNALS OF MATHEMATICAL STATISTICS, 1951, 22 (01) :79-86
[20]  
LAURITZEN SL, 1988, J ROY STAT SOC B MET, V50, P157
123