### Abstract

Inferences in directed acyclic graphs associated with probability intervals and sets of probabilities are NP-hard, even for polytrees. We propose: 1) an improvement on Tessem’s A/R algorithm for inferences on polytrees associated with probability intervals; 2) a new algorithm for approximate inferences based on local search; 3) branch-and-bound algorithms that combine the previous techniques. The first two algorithms produce complementary approximate solutions, while branch-and-bound procedures can generate either exact or approximate solutions. We report improvements on existing techniques for inference with probability sets and intervals, in some cases reducing computational effort by several orders of magnitude.

Original language | English |
---|---|

Title of host publication | Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03) |

Publisher | Morgan Kaufmann Publishers, Inc. |

Pages | 217-224 |

Number of pages | 8 |

ISBN (Print) | 0-127-05664-5 |

Publication status | Published - 2003 |

Externally published | Yes |

Event | 19th Conference on Uncertainty in Artificial Intelligence - Acapulco, Mexico Duration: 7 Aug 2003 → 10 Aug 2003 |

### Conference

Conference | 19th Conference on Uncertainty in Artificial Intelligence |
---|---|

Abbreviated title | UAI-03 |

Country | Mexico |

City | Acapulco |

Period | 7/08/03 → 10/08/03 |

### Bibliographical note

(Double blind reviewed by multiple reviewers. plenary presentation)## Cite this

da Rocha, J. C. F., Cozman, F. G., & de Campos, C. P. (2003). Inference in polytrees with sets of probabilities. In

*Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)*(pp. 217-224). Morgan Kaufmann Publishers, Inc..