A credal network associates sets of probability distributions with directed acyclic graphs. Under strong independence assumptions, inference with credal networks is equivalent to a signomial program under linear constraints, a problem that is NP-hard even for categorical variables and polytree models. We describe an approach for inference with polytrees that is based on branch-and-bound optimization/search algorithms. We use bounds generated by Tessem's A/R algorithm, and consider various branch-and-bound schemes.
Keywords. Credal networks, strong independence,probability intervals, inference, branch-and-bound algorithms
Authors addresses:
Jose Rocha
Universidade Estadual de Ponta Grossa
Praça Santos Andrade s/n
Departamento de Informatica
Ponta Grossa - PR
84010.919
Fabio Cozman
Av. Prof. Mello Moraes, 2231
Cidade Univesitaria, CEP 05508-900
Sao Paulo, SP - BRAZIL
E-mail addresses:
| Jose Rocha | jrocha@uepg.br |
| Fabio Cozman | fgcozman@usp.br |
Related Web Sites