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.
|Title of host publication||Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)|
|Number of pages||8|
|Publication status||Published - 2003|
|Event||The Nineteenth Conference on Uncertainty in Artificial Intelligence, UAI-2003 - Acapulco, Mexico|
Duration: 07 Aug 2003 → 10 Aug 2003
|Conference||The Nineteenth Conference on Uncertainty in Artificial Intelligence, UAI-2003|
|Period||07/08/2003 → 10/08/2003|