Rooted-Join-Tree Construnction

Jul 22, 2017


For computing multiple marginals efficiently in the Shenoy-Shafer architecture, a binary join tree has been proposed in [1].

For a given valuation network , if we want to compute marginal for a subset , we can use the Fusion algorithm  .

Fusion algorithm: Suppose is a VN where is a valuation for , and suppose and satisfy Axioms A1-A3 [1] . Let denote . Suppose , and suppose is a sequence of variables in . Then

 

With this fusion Algorithm, we can compute the marginal of the joint valuation one by one. It is obviously inefficient that it involves much repetition of effort. Then they use a join tree with message passing to mimic the fusion algorithm.

A join tree is a tree whose nodes are subsets of such that if a variable is in two distinct nodes, then it is in every node on the path between the two nodes. In [1], a procedure is given out. I follow the algorithm and implement it with Python. The input and are given by the Chest clinic example in [1]. It is worth to noting that the deletion sequence is which is derived by the one-step lookahead heuristic approach. Below is the source code.

import JoinTree as jt
variables = set({'A','T','E','X','D','L','S','B'})

valuations = []
valuations.append(jt.Valuation(frozenset({'A'})))
valuations.append(jt.Valuation(frozenset({'A'}),observed=True))
valuations.append(jt.Valuation(frozenset({'S'})))
valuations.append(jt.Valuation(frozenset({'A','T'})))
valuations.append(jt.Valuation(frozenset({'S','L'})))
valuations.append(jt.Valuation(frozenset({'S','B'})))
valuations.append(jt.Valuation(frozenset({'T','L','E'})))
valuations.append(jt.Valuation(frozenset({'E','X'})))
valuations.append(jt.Valuation(frozenset({'E','B','D'})))
valuations.append(jt.Valuation(frozenset({'D'}),observed=True))

subsets = set()
for i in valuations:
    subsets.add(i.variables)

def get_superset(superset,t):
    for i in superset:
        if t in i:
            yield i

def construct( variables, subsets,object):
    nodes = set()
    edges = set()
    variables.difference_update(object)

    heuristic_count = ['E','L','B','D','S','A','X']

    while(len(subsets)>1):

        picked=heuristic_count.pop()
        s = reduce(frozenset .union,get_superset(subsets,picked))

        s_all = set([i for i in get_superset(subsets,picked)])

        #update nodes
        nodes.update(s_all)

        s_set = set()
        s_set.add(s)
        nodes.update(s_set)

        temp = set()
        temp.add(picked)

        _s=set(s)
        s_no_y = set()       #{s-{Y}}
        s_no_y.add(frozenset(_s.difference(temp)))
        nodes.update(s_no_y)

        #update edge

        u_s = subsets.difference(s_set)
        temp = set([ (i,s) for i in get_superset(u_s,picked) ])
        single = s.difference(set(picked))

        edges.update(temp)
        edges.update(set([(s,single)]))

        variables.difference_update(set(picked))
        subsets.difference_update(s_all)
        subsets.update(s_no_y)

    nodes.update(subsets)
    return nodes,edges

nodes, edges=construct(variables,subsets,'T')

By using the visualization tool GraphViz, you can get the graph:

You can also download the source code from here

[1] P. P. Shenoy, “Binary join trees for computing marginals in the Shenoy-Shafer architecture,” Int. J. Approx. Reason., vol. 17, no. 2–3, pp. 239–263, Aug. 1997.