Belief network algorithms: a study of performance based on domain characterisation

Nathalie Jitnah; Ann E Nicholson

doi:10.1007/3-540-64413-X_35

Belief network algorithms: a study of performance based on domain characterisation

Nathalie Jitnah, Ann E Nicholson

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

2 Citations (Scopus)

Abstract

In recent years belief networks have become a popular representation for reasoning with incomplete and changing information and are used in a wide variety of applications. There are a number of exact and approximate inference algorithms available for performing belief updating, however in general the task is NP-hard. Typically comparisons are made of only a few algorithms, and on a particular example network. We survey belief network algorithms and propose a system for domain characterisation as a basis for algorithm comparison. We present performance results using this framework from three sets of experiments: (1) on the Likelihood Weighting (LW) and Logic Sampling (LS) stochastic simulation algorithms? (2) on the performance of LW and Jensen's algorithms on state-space abstracted networks, (3) some comparisons of the time performance of LW, LS and the Jensen algorithm. Our results indicate that domain characterisation can be useful for predicting inference algorithm performance on a belief network for a new application domain.

Original language	English
Title of host publication	Learning and Reasoning with Complex Representations
Subtitle of host publication	PRICAI'96 Workshops on Reasoning with Incomplete and Changing Information and on Inducing Complex Representations Cairns, Australia, August 26-30, 1996 Selected Papers
Editors	Grigoris Antoniou, Aditya K. Ghose, Miroslaw Truszczynski
Place of Publication	Berlin Germany
Publisher	Springer
Pages	168-187
Number of pages	20
ISBN (Print)	354064413X
DOIs	https://doi.org/10.1007/3-540-64413-X_35
Publication status	Published - 1998
Event	Pacific Rim International Conference on Artificial Intelligence 1996 - Cairns, Australia Duration: 26 Aug 1996 → 30 Aug 1996 Conference number: 4th https://link.springer.com/book/10.1007/3-540-61532-6 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	1359
ISSN (Print)	0302-9743

Conference

Conference	Pacific Rim International Conference on Artificial Intelligence 1996
Abbreviated title	PRICAI 1996
Country/Territory	Australia
City	Cairns
Period	26/08/96 → 30/08/96
Internet address	https://link.springer.com/book/10.1007/3-540-61532-6 (Proceedings)

Access to Document

10.1007/3-540-64413-X_35

Cite this

Jitnah, N., & Nicholson, A. E. (1998). Belief network algorithms: a study of performance based on domain characterisation. In G. Antoniou, A. K. Ghose, & M. Truszczynski (Eds.), Learning and Reasoning with Complex Representations: PRICAI'96 Workshops on Reasoning with Incomplete and Changing Information and on Inducing Complex Representations Cairns, Australia, August 26-30, 1996 Selected Papers (pp. 168-187). (Lecture Notes in Computer Science; Vol. 1359). Springer. https://doi.org/10.1007/3-540-64413-X_35

Jitnah, Nathalie ; Nicholson, Ann E. / Belief network algorithms : a study of performance based on domain characterisation. Learning and Reasoning with Complex Representations: PRICAI'96 Workshops on Reasoning with Incomplete and Changing Information and on Inducing Complex Representations Cairns, Australia, August 26-30, 1996 Selected Papers . editor / Grigoris Antoniou ; Aditya K. Ghose ; Miroslaw Truszczynski. Berlin Germany : Springer, 1998. pp. 168-187 (Lecture Notes in Computer Science).

@inproceedings{49826ccca17c45eb928409bb9229e708,

title = "Belief network algorithms: a study of performance based on domain characterisation",

abstract = "In recent years belief networks have become a popular representation for reasoning with incomplete and changing information and are used in a wide variety of applications. There are a number of exact and approximate inference algorithms available for performing belief updating, however in general the task is NP-hard. Typically comparisons are made of only a few algorithms, and on a particular example network. We survey belief network algorithms and propose a system for domain characterisation as a basis for algorithm comparison. We present performance results using this framework from three sets of experiments: (1) on the Likelihood Weighting (LW) and Logic Sampling (LS) stochastic simulation algorithms? (2) on the performance of LW and Jensen's algorithms on state-space abstracted networks, (3) some comparisons of the time performance of LW, LS and the Jensen algorithm. Our results indicate that domain characterisation can be useful for predicting inference algorithm performance on a belief network for a new application domain.",

author = "Nathalie Jitnah and Nicholson, {Ann E}",

year = "1998",

doi = "10.1007/3-540-64413-X_35",

language = "English",

isbn = "354064413X",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "168--187",

editor = "Grigoris Antoniou and Ghose, {Aditya K.} and Miroslaw Truszczynski",

booktitle = "Learning and Reasoning with Complex Representations",

note = "Pacific Rim International Conference on Artificial Intelligence 1996, PRICAI 1996 ; Conference date: 26-08-1996 Through 30-08-1996",

url = "https://link.springer.com/book/10.1007/3-540-61532-6",

}

Jitnah, N & Nicholson, AE 1998, Belief network algorithms: a study of performance based on domain characterisation. in G Antoniou, AK Ghose & M Truszczynski (eds), Learning and Reasoning with Complex Representations: PRICAI'96 Workshops on Reasoning with Incomplete and Changing Information and on Inducing Complex Representations Cairns, Australia, August 26-30, 1996 Selected Papers . Lecture Notes in Computer Science, vol. 1359, Springer, Berlin Germany, pp. 168-187, Pacific Rim International Conference on Artificial Intelligence 1996, Cairns, Queensland, Australia, 26/08/96. https://doi.org/10.1007/3-540-64413-X_35

Belief network algorithms: a study of performance based on domain characterisation. / Jitnah, Nathalie; Nicholson, Ann E.
Learning and Reasoning with Complex Representations: PRICAI'96 Workshops on Reasoning with Incomplete and Changing Information and on Inducing Complex Representations Cairns, Australia, August 26-30, 1996 Selected Papers . ed. / Grigoris Antoniou; Aditya K. Ghose; Miroslaw Truszczynski. Berlin Germany: Springer, 1998. p. 168-187 (Lecture Notes in Computer Science; Vol. 1359).

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

TY - GEN

T1 - Belief network algorithms

T2 - Pacific Rim International Conference on Artificial Intelligence 1996

AU - Jitnah, Nathalie

AU - Nicholson, Ann E

N1 - Conference code: 4th

PY - 1998

Y1 - 1998

N2 - In recent years belief networks have become a popular representation for reasoning with incomplete and changing information and are used in a wide variety of applications. There are a number of exact and approximate inference algorithms available for performing belief updating, however in general the task is NP-hard. Typically comparisons are made of only a few algorithms, and on a particular example network. We survey belief network algorithms and propose a system for domain characterisation as a basis for algorithm comparison. We present performance results using this framework from three sets of experiments: (1) on the Likelihood Weighting (LW) and Logic Sampling (LS) stochastic simulation algorithms? (2) on the performance of LW and Jensen's algorithms on state-space abstracted networks, (3) some comparisons of the time performance of LW, LS and the Jensen algorithm. Our results indicate that domain characterisation can be useful for predicting inference algorithm performance on a belief network for a new application domain.

AB - In recent years belief networks have become a popular representation for reasoning with incomplete and changing information and are used in a wide variety of applications. There are a number of exact and approximate inference algorithms available for performing belief updating, however in general the task is NP-hard. Typically comparisons are made of only a few algorithms, and on a particular example network. We survey belief network algorithms and propose a system for domain characterisation as a basis for algorithm comparison. We present performance results using this framework from three sets of experiments: (1) on the Likelihood Weighting (LW) and Logic Sampling (LS) stochastic simulation algorithms? (2) on the performance of LW and Jensen's algorithms on state-space abstracted networks, (3) some comparisons of the time performance of LW, LS and the Jensen algorithm. Our results indicate that domain characterisation can be useful for predicting inference algorithm performance on a belief network for a new application domain.

U2 - 10.1007/3-540-64413-X_35

DO - 10.1007/3-540-64413-X_35

M3 - Conference Paper

SN - 354064413X

T3 - Lecture Notes in Computer Science

SP - 168

EP - 187

BT - Learning and Reasoning with Complex Representations

A2 - Antoniou, Grigoris

A2 - Ghose, Aditya K.

A2 - Truszczynski, Miroslaw

PB - Springer

CY - Berlin Germany

Y2 - 26 August 1996 through 30 August 1996

ER -

Jitnah N, Nicholson AE. Belief network algorithms: a study of performance based on domain characterisation. In Antoniou G, Ghose AK, Truszczynski M, editors, Learning and Reasoning with Complex Representations: PRICAI'96 Workshops on Reasoning with Incomplete and Changing Information and on Inducing Complex Representations Cairns, Australia, August 26-30, 1996 Selected Papers . Berlin Germany: Springer. 1998. p. 168-187. (Lecture Notes in Computer Science). doi: 10.1007/3-540-64413-X_35