Inference in polytrees with sets of probabilities

José Carlos Ferreira da Rocha; Fabio Gagliardi Cozman; Cassio P. de Campos

Inference in polytrees with sets of probabilities

José Carlos Ferreira da Rocha, Fabio Gagliardi Cozman, Cassio P. de Campos

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

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/Territory	Mexico
City	Acapulco
Period	7/08/03 → 10/08/03

Bibliographical note

(Double blind reviewed by multiple reviewers. plenary presentation)

Cite this

@inbook{7218eb901ae841ed977a9c90947c2b0c,

title = "Inference in polytrees with sets of probabilities",

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{\textquoteright}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.",

author = "{da Rocha}, {Jos{\'e} Carlos Ferreira} and Cozman, {Fabio Gagliardi} and {de Campos}, {Cassio P.}",

note = "(Double blind reviewed by multiple reviewers. plenary presentation); 19th Conference on Uncertainty in Artificial Intelligence, UAI-03 ; Conference date: 07-08-2003 Through 10-08-2003",

year = "2003",

language = "English",

isbn = "0-127-05664-5",

pages = "217--224",

booktitle = "Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)",

publisher = "Morgan Kaufmann Publishers, Inc.",

address = "United States",

}

Inference in polytrees with sets of probabilities. / da Rocha, José Carlos Ferreira; Cozman, Fabio Gagliardi; de Campos, Cassio P.
Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03). Morgan Kaufmann Publishers, Inc., 2003. p. 217-224.

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Inference in polytrees with sets of probabilities

AU - da Rocha, José Carlos Ferreira

AU - Cozman, Fabio Gagliardi

AU - de Campos, Cassio P.

N1 - (Double blind reviewed by multiple reviewers. plenary presentation)

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

M3 - Chapter

SN - 0-127-05664-5

SP - 217

EP - 224

BT - Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)

PB - Morgan Kaufmann Publishers, Inc.

T2 - 19th Conference on Uncertainty in Artificial Intelligence

Y2 - 7 August 2003 through 10 August 2003

ER -

Inference in polytrees with sets of probabilities

Abstract

Conference

Bibliographical note

Fingerprint

Cite this