Marginalization without summation exploiting determinism in factor algebra

Sander Evers; Peter J.F. Lucas

doi:10.1007/978-3-642-22152-1_22

Marginalization without summation exploiting determinism in factor algebra

Sander Evers^*, Peter J.F. Lucas

^*Corresponding author for this work

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

1 Citation (Scopus)

Abstract

It is known that solving an exact inference problem on a discrete 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: to the operations of factor multiplication and factor summation that form the basis of many inference algorithms, we add factor indexing. We integrate this operation into variable elimination, and extend the minweight heuristic accordingly. A preliminary empirical evaluation gives promising results.

Original language	English
Title of host publication	Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings
Pages	251-262
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-22152-1_22
Publication status	Published - 2011
Externally published	Yes
Event	11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011 - Belfast, United Kingdom Duration: 29 Jun 2011 → 1 Jul 2011 Conference number: 11

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6717 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011
Abbreviated title	ECSQARU 2011
Country/Territory	United Kingdom
City	Belfast
Period	29/06/11 → 1/07/11

Keywords

n/a OA procedure
deterministic variables
exact inference
factor algebra
Bayesian networks

Access to Document

10.1007/978-3-642-22152-1_22

Cite this

Evers, S., & Lucas, P. J. F. (2011). Marginalization without summation exploiting determinism in factor algebra. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings (pp. 251-262). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6717 LNAI). https://doi.org/10.1007/978-3-642-22152-1_22

Evers, Sander ; Lucas, Peter J.F. / Marginalization without summation exploiting determinism in factor algebra. Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings. 2011. pp. 251-262 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8d9e2eeb441045ad8abaad59879b7fe3,

title = "Marginalization without summation exploiting determinism in factor algebra",

abstract = "It is known that solving an exact inference problem on a discrete 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: to the operations of factor multiplication and factor summation that form the basis of many inference algorithms, we add factor indexing. We integrate this operation into variable elimination, and extend the minweight heuristic accordingly. A preliminary empirical evaluation gives promising results.",

keywords = "n/a OA procedure, deterministic variables, exact inference, factor algebra, Bayesian networks",

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

year = "2011",

doi = "10.1007/978-3-642-22152-1_22",

language = "English",

isbn = "9783642221514",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "251--262",

booktitle = "Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings",

note = "11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011, ECSQARU 2011 ; Conference date: 29-06-2011 Through 01-07-2011",

}

Evers, S & Lucas, PJF 2011, Marginalization without summation exploiting determinism in factor algebra. in Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6717 LNAI, pp. 251-262, 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011, Belfast, United Kingdom, 29/06/11. https://doi.org/10.1007/978-3-642-22152-1_22

Marginalization without summation exploiting determinism in factor algebra. / Evers, Sander; Lucas, Peter J.F.
Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings. 2011. p. 251-262 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6717 LNAI).

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

TY - GEN

T1 - Marginalization without summation exploiting determinism in factor algebra

AU - Evers, Sander

AU - Lucas, Peter J.F.

N1 - Conference code: 11

PY - 2011

Y1 - 2011

N2 - It is known that solving an exact inference problem on a discrete 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: to the operations of factor multiplication and factor summation that form the basis of many inference algorithms, we add factor indexing. We integrate this operation into variable elimination, and extend the minweight heuristic accordingly. A preliminary empirical evaluation gives promising results.

AB - It is known that solving an exact inference problem on a discrete 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: to the operations of factor multiplication and factor summation that form the basis of many inference algorithms, we add factor indexing. We integrate this operation into variable elimination, and extend the minweight heuristic accordingly. A preliminary empirical evaluation gives promising results.

KW - n/a OA procedure

KW - deterministic variables

KW - exact inference

KW - factor algebra

KW - Bayesian networks

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

U2 - 10.1007/978-3-642-22152-1_22

DO - 10.1007/978-3-642-22152-1_22

M3 - Conference contribution

AN - SCOPUS:79960110674

SN - 9783642221514

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 251

EP - 262

BT - Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings

T2 - 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2011

Y2 - 29 June 2011 through 1 July 2011

ER -

Evers S, Lucas PJF. Marginalization without summation exploiting determinism in factor algebra. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 11th European Conference, ECSQARU 2011, Proceedings. 2011. p. 251-262. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-22152-1_22

Marginalization without summation exploiting determinism in factor algebra

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this