Inference Does Not Work for Non-Tree Factor Graphs

[studentbrad]

It looks like inference is not working for non-tree structures. For example consider the following simple factor graph with nodes x1, x2, x3 and factors fa, fb, fc.

from fglib import graphs, nodes, inference, rv

# Create factor graph
fg = graphs.FactorGraph()

# Create variable nodes
x1 = nodes.VNode("x1", rv.Discrete)
x2 = nodes.VNode("x2", rv.Discrete)
x3 = nodes.VNode("x3", rv.Discrete)

# Create factor nodes (with joint distributions)
dist_fa = [[1.0, 0.0],
           [0.2, 0.8]]
fa = nodes.FNode("fa", rv.Discrete(dist_fa, x1, x2))

dist_fb = [[1.0, 0.0],
           [0.3, 0.7]]
fb = nodes.FNode("fb", rv.Discrete(dist_fb, x2, x3))

dist_fc = [[1.0, 0.0],
           [0.4, 0.6]]
fc = nodes.FNode("fc", rv.Discrete(dist_fc, x1, x3))

# Add nodes to factor graph
fg.set_nodes([x1, x2, x3])
fg.set_nodes([fa, fb, fc])

# Add edges to factor graph
fg.set_edge(x1, fa)
fg.set_edge(fa, x2)
fg.set_edge(x2, fb)
fg.set_edge(fb, x3)
fg.set_edge(x1, fc)
fg.set_edge(fc, x3)

# Perform sum-product algorithm on factor graph
# and request belief of variable node x3
belief = inference.sum_product(fg, x3)

# Print belief of variables
print("Belief of variable node x3:")
print(belief)

The terminal output is shown below.

Traceback (most recent call last):
  File "fglib_example.py", line 35, in <module>
    belief = inference.sum_product(fg, x3)
  File "/home/bradley/.local/lib/python3.6/site-packages/fglib/inference.py", line 63, in sum_product
    return belief_propagation(graph, query_node)
  File "/home/bradley/.local/lib/python3.6/site-packages/fglib/inference.py", line 42, in belief_propagation
    msg = u.spa(v)
  File "/home/bradley/.local/lib/python3.6/site-packages/fglib/nodes.py", line 270, in spa
    msg *= self.graph[n][self]['object'].get_message(n, self)
  File "/home/bradley/.local/lib/python3.6/site-packages/fglib/rv.py", line 255, in __imul__
    return self.__mul__(other)
  File "/home/bradley/.local/lib/python3.6/site-packages/fglib/rv.py", line 212, in __mul__
    if len(self.dim) < len(other.dim):
AttributeError: 'NoneType' object has no attribute 'dim'

[adam-carruthers]

In the docstring for inference.sum_product it says that the algorithm only works for tree graphs. The algorithm for non-trees is different - try inference.loopy_belief_propagation. However be warned that this algorithm is non-exact, all message-passing algorithms on a loopy graph are non exact!

[studentbrad]

Thanks for the response. I tried inference.loopy_belief_propagation. However, I've run into another error. Is model what I think it is? An arbitrary structured graph?

# Perform loopy-belief propagation on factor graph
# and request belief of variable node x3
belief = inference.loopy_belief_propagation(fg, 10, (x3,))

The terminal output is shown below.

Traceback (most recent call last):
  File "fglib_example.py", line 39, in <module>
    belief = inference.loopy_belief_propagation(fg, 10, (x3,))
  File "/home/bradley/.local/lib/python3.6/site-packages/fglib/inference.py", line 165, in loopy_belief_propagation
    return _schedule(model, 'spa', iterations, query_node, order)
  File "/home/bradley/.local/lib/python3.6/site-packages/fglib/inference.py", line 205, in _schedule
    b[n].append(n.belief(model))
  File "/home/bradley/.local/lib/python3.6/site-packages/fglib/nodes.py", line 140, in belief
    belief *= self.graph[n][self]['object'].get_message(n, self)
TypeError: unsupported operand type(s) for *=: 'NoneType' and 'NoneType'

[mercicle]

@studentbrad did you ever resolve this? I have the same issue for loopy graph when trying to compute marginals

[mercicle]

@goodyguts, for my loopy graph I tried:

score_node_list = [n for (n, attr) in M.nodes(data=True) if attr["type"] == "vn"]
belief = fg_lib.inference.loopy_belief_propagation(M,iterations=100, query_node = score_node_list)

and runs without error, but no marginals. Can you comment please thx!

[studentbrad]

@mercicle, I wasn't able to get this implementation of loopy belief propagation working. Of course I appreciate the authors work, but there are other tools for doing the same loopy belief on a structured graph.

[Mahdi-Soleymani]

@mercicle, I wasn't able to get this implementation of loopy belief propagation working. Of course I appreciate the authors work, but there are other tools for doing the same loopy belief on a structured graph

Could you please let us know what tool you finally used for the loopy BP? Thanks!