Link strength in Bayesian networks

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.Science, Faculty ofComputer Science, Department ofGraduat