- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Link strength in Bayesian networks
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Link strength in Bayesian networks Boerlage, Brent
Abstract
This thesis introduces the concept of a connection strength (CS) between two nodes of a propositional Bayesian network (BN). Connection strength is a generalization of node independence, from a binary property to a graded measure. The connection strength from node A to node B is a measure of the maximum amount that the belief in B will change when the truth value of A is learned. If the belief in B does not change, they are independent, and if it changes a great deal, they are strongly connected. It also introduces the link strength (LS) between two adjacent nodes, which is an upper bound on that part of the connection strength between them which is due only to the link between them (and not other paths which may connect them). Calculating connection strengths is computationally expensive, while calculating link strengths is not. An algorithm is provided which finds a bound on the connection strength between any two nodes by combining link strengths along the paths connecting them (which is of complexity linear in the number of links). Such an algorithm lends substance to notions of an "effect" flowing along paths, and "effect" being attenuated by "weak" links, which is terminology that has appeared often in the literature, but only as an intuitive idea. An algorithm for faster, approximate BN inference is presented, and connection strengths are used to provide bounds for its error. A system is proposed for BN diagrams to be drawn with strong links represented by heavy lines and weak links by fine lines, as a visualization aid for humans. Another visualization aid which is explored is the iso-CS contour map, in which the amount that one particular node can effect each of the other nodes is shown as contour lines super-imposed on a regular BN diagram. Anon-trivial example BN is presented, some of its connection strengths are calculated, CS contour maps are constructed for it, and it is displayed with link strength indicated by line width.
Item Metadata
Title |
Link strength in Bayesian networks
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1992
|
Description |
This thesis introduces the concept of a connection strength (CS) between two nodes of a propositional Bayesian network (BN). Connection strength is a generalization of node independence, from a binary property to a graded measure. The connection strength from node A to node B is a measure of the maximum amount that the belief in B will change when the truth value of A is learned. If the belief in B does not change, they are independent, and if it changes a great deal, they are strongly connected. It also introduces the link strength (LS) between two adjacent nodes, which is an upper bound on that part of the connection strength between them which is due only to the link between them (and not other paths which may connect them). Calculating connection strengths is computationally expensive, while calculating link strengths is not. An algorithm is provided which finds a bound on the connection strength between any two nodes by combining link strengths along the paths connecting them (which is of complexity linear in the number of links). Such an algorithm lends substance to notions of an "effect" flowing along paths, and "effect" being attenuated by "weak" links, which is terminology that has appeared often in the literature, but only as an intuitive idea. An algorithm for faster, approximate BN inference is presented, and connection strengths are used to provide bounds for its error. A system is proposed for BN diagrams to be drawn with strong links represented by heavy lines and weak links by fine lines, as a visualization aid for humans. Another visualization aid which is explored is the iso-CS contour map, in which the amount that one particular node can effect each of the other nodes is shown as contour lines super-imposed on a regular BN diagram. Anon-trivial example BN is presented, some of its connection strengths are calculated, CS contour maps are constructed for it, and it is displayed with link strength indicated by line width.
|
Extent |
4149050 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2008-09-16
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
|
DOI |
10.14288/1.0051344
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
1992-11
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.