Variable elimination by factor indexing

Sander Evers; Peter J.F. Lucas

Variable elimination by factor indexing

Sander Evers^*
, Peter J.F. Lucas

^*Corresponding author for this work

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

65 Downloads (Pure)

Abstract

It is known that solving an exact inference problem on a Bayesian network with many deterministic nodes can be far cheaper than what would be expected based on its treewidth. In this article, we introduce a novel technique for this, which stores a deterministic node as an array of function values rather than one of probabilities. We propose a variable elimination algorithm, including a new elimination heuristic, that maximally exploits this encoding using factor indexing. A preliminary empirical evaluation gives promising results.

Original language	English
Title of host publication	Proceedings of the 5th European Workshop on Probabilistic Graphical Models, PGM 2010
Editors	Petri Myllymäki, Teemu Roos, Tommi Jaakkola
Publisher	HIIT Publications
Pages	129-136
Number of pages	8
ISBN (Print)	978-952-60-3314-3
Publication status	Published - 2010
Externally published	Yes
Event	5th European Workshop on Probabilistic Graphical Models, PGM 2010 - Helsinki, Finland Duration: 13 Sept 2010 → 15 Sept 2010 Conference number: 5

Publication series

Name	HIIT Publications
Publisher	Helsinki Institute for Information Technology (HIIT)
Volume	2010-2
ISSN (Print)	1458-9451
ISSN (Electronic)	1458-946X

Conference

Conference	5th European Workshop on Probabilistic Graphical Models, PGM 2010
Abbreviated title	PGM 2010
Country/Territory	Finland
City	Helsinki
Period	13/09/10 → 15/09/10

Access to Document

ArticleFinal published version, 281 KB

Cite this

@inproceedings{1c20f98238fc4dfdb8c284cb65cbdbe8,

title = "Variable elimination by factor indexing",

abstract = "It is known that solving an exact inference problem on a Bayesian network with many deterministic nodes can be far cheaper than what would be expected based on its treewidth. In this article, we introduce a novel technique for this, which stores a deterministic node as an array of function values rather than one of probabilities. We propose a variable elimination algorithm, including a new elimination heuristic, that maximally exploits this encoding using factor indexing. A preliminary empirical evaluation gives promising results.",

author = "Sander Evers and Lucas, \{Peter J.F.\}",

year = "2010",

language = "English",

isbn = "978-952-60-3314-3",

series = "HIIT Publications",

publisher = "HIIT Publications",

pages = "129--136",

editor = "Petri Myllym{\"a}ki and Teemu Roos and Tommi Jaakkola",

booktitle = "Proceedings of the 5th European Workshop on Probabilistic Graphical Models, PGM 2010",

note = "5th European Workshop on Probabilistic Graphical Models, PGM 2010, PGM 2010 ; Conference date: 13-09-2010 Through 15-09-2010",

}

Variable elimination by factor indexing. / Evers, Sander; Lucas, Peter J.F.
Proceedings of the 5th European Workshop on Probabilistic Graphical Models, PGM 2010. ed. / Petri Myllymäki; Teemu Roos; Tommi Jaakkola. HIIT Publications, 2010. p. 129-136 (HIIT Publications; Vol. 2010-2).

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

TY - GEN

T1 - Variable elimination by factor indexing

AU - Evers, Sander

AU - Lucas, Peter J.F.

N1 - Conference code: 5

PY - 2010

Y1 - 2010

N2 - It is known that solving an exact inference problem on a Bayesian network with many deterministic nodes can be far cheaper than what would be expected based on its treewidth. In this article, we introduce a novel technique for this, which stores a deterministic node as an array of function values rather than one of probabilities. We propose a variable elimination algorithm, including a new elimination heuristic, that maximally exploits this encoding using factor indexing. A preliminary empirical evaluation gives promising results.

AB - It is known that solving an exact inference problem on a Bayesian network with many deterministic nodes can be far cheaper than what would be expected based on its treewidth. In this article, we introduce a novel technique for this, which stores a deterministic node as an array of function values rather than one of probabilities. We propose a variable elimination algorithm, including a new elimination heuristic, that maximally exploits this encoding using factor indexing. A preliminary empirical evaluation gives promising results.

UR - https://www.scopus.com/pages/publications/84874736036

M3 - Conference contribution

SN - 978-952-60-3314-3

T3 - HIIT Publications

SP - 129

EP - 136

BT - Proceedings of the 5th European Workshop on Probabilistic Graphical Models, PGM 2010

A2 - Myllymäki, Petri

A2 - Roos, Teemu

A2 - Jaakkola, Tommi

PB - HIIT Publications

T2 - 5th European Workshop on Probabilistic Graphical Models, PGM 2010

Y2 - 13 September 2010 through 15 September 2010

ER -

Variable elimination by factor indexing

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this