Inference in Polytrees with Sets of Probabilities

Jose Carlos Ferreira da Rocha, Fabio Gagliardi Cozman, Cassio Polpo de Campos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish
Title of host publicationProceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)
PublisherMorgan Kaufmann
Number of pages8
ISBN (Print)0-127-05664-5
Publication statusPublished - 2003
EventThe Nineteenth Conference on Uncertainty in Artificial Intelligence, UAI-2003 - Acapulco, Mexico
Duration: 07 Aug 200310 Aug 2003


ConferenceThe Nineteenth Conference on Uncertainty in Artificial Intelligence, UAI-2003

Bibliographical note

(Double blind reviewed by multiple reviewers. Top 11%, plenary presentation)


Dive into the research topics of 'Inference in Polytrees with Sets of Probabilities'. Together they form a unique fingerprint.

Cite this