A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states

Denis D. Maúa; Cassio P. de Campos; Marco Zaffalon

A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states

Denis D. Maúa, Cassio P. de Campos, Marco Zaffalon

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

Abstract

Credal networks lift the precise probability assumption of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper we present a new algorithm which is an extension of the wellknown variable elimination algorithm for computing posterior inferences in extensively specified credal networks. The algorithm efficiency is empirically shown to outperform a state-of-the-art algorithm. We then provide the first fully polynomial time approximation scheme for inference in credal networks with bounded treewidth and number of states per variable.

Original language	English
Title of host publication	ISIPTA 2011 - Proceedings of the 7th International Symposium on Imprecise Probability
Subtitle of host publication	Theories and Applications
Pages	277-286
Number of pages	10
Publication status	Published - 1 Dec 2011
Externally published	Yes
Event	7th International Symposium on Imprecise Probability: Theories and Applications, ISIPTA 2011 - Innsbruck, Austria Duration: 25 Jul 2011 → 28 Jul 2011

Conference

Conference	7th International Symposium on Imprecise Probability: Theories and Applications, ISIPTA 2011
Country/Territory	Austria
City	Innsbruck
Period	25/07/11 → 28/07/11

Keywords

Approximation scheme
Credal networks
Probabilistic graphical models
Valuation algebra

Cite this

@inproceedings{2792b477971f4229bf4d0eb533304b91,

title = "A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states",

abstract = "Credal networks lift the precise probability assumption of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper we present a new algorithm which is an extension of the wellknown variable elimination algorithm for computing posterior inferences in extensively specified credal networks. The algorithm efficiency is empirically shown to outperform a state-of-the-art algorithm. We then provide the first fully polynomial time approximation scheme for inference in credal networks with bounded treewidth and number of states per variable.",

keywords = "Approximation scheme, Credal networks, Probabilistic graphical models, Valuation algebra",

author = "Ma{\'u}a, {Denis D.} and {de Campos}, {Cassio P.} and Marco Zaffalon",

year = "2011",

month = dec,

day = "1",

language = "English",

isbn = "9783902652409",

pages = "277--286",

booktitle = "ISIPTA 2011 - Proceedings of the 7th International Symposium on Imprecise Probability",

note = "7th International Symposium on Imprecise Probability: Theories and Applications, ISIPTA 2011 ; Conference date: 25-07-2011 Through 28-07-2011",

}

Maúa, DD, de Campos, CP & Zaffalon, M 2011, A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states. in ISIPTA 2011 - Proceedings of the 7th International Symposium on Imprecise Probability: Theories and Applications. pp. 277-286, 7th International Symposium on Imprecise Probability: Theories and Applications, ISIPTA 2011, Innsbruck, Austria, 25/07/11.

A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states. / Maúa, Denis D.; de Campos, Cassio P.; Zaffalon, Marco.

ISIPTA 2011 - Proceedings of the 7th International Symposium on Imprecise Probability: Theories and Applications. 2011. p. 277-286.

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

TY - GEN

T1 - A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states

AU - Maúa, Denis D.

AU - de Campos, Cassio P.

AU - Zaffalon, Marco

PY - 2011/12/1

Y1 - 2011/12/1

N2 - Credal networks lift the precise probability assumption of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper we present a new algorithm which is an extension of the wellknown variable elimination algorithm for computing posterior inferences in extensively specified credal networks. The algorithm efficiency is empirically shown to outperform a state-of-the-art algorithm. We then provide the first fully polynomial time approximation scheme for inference in credal networks with bounded treewidth and number of states per variable.

AB - Credal networks lift the precise probability assumption of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper we present a new algorithm which is an extension of the wellknown variable elimination algorithm for computing posterior inferences in extensively specified credal networks. The algorithm efficiency is empirically shown to outperform a state-of-the-art algorithm. We then provide the first fully polynomial time approximation scheme for inference in credal networks with bounded treewidth and number of states per variable.

KW - Approximation scheme

KW - Credal networks

KW - Probabilistic graphical models

KW - Valuation algebra

UR - http://www.scopus.com/inward/record.url?scp=84883229801&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84883229801

SN - 9783902652409

SP - 277

EP - 286

BT - ISIPTA 2011 - Proceedings of the 7th International Symposium on Imprecise Probability

T2 - 7th International Symposium on Imprecise Probability: Theories and Applications, ISIPTA 2011

Y2 - 25 July 2011 through 28 July 2011

ER -

A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states

Abstract

Conference

Keywords

Other files and links

Fingerprint

Cite this