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 |
| Pages | 217-224 |
| Number of pages | 8 |
| ISBN (Print) | 0-127-05664-5 |
| 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
| Conference | The Nineteenth Conference on Uncertainty in Artificial Intelligence, UAI-2003 |
|---|---|
| Country/Territory | Mexico |
| City | Acapulco |
| Period | 07/08/2003 → 10/08/2003 |