wmkouw / schedulefree-mp

Schedule-free variational message passing on factor graphs

Schedule-free variational message-passing

Message passing in factor graphs should be free of an explicit message scheduler. The scheduler is the bottleneck in computational cost, because it has to parse the graph in its entirety. By passing messages based on a local, distributed criterion, the scheduler can be circumvented. Schedule-free MP scales better to to larger graphs.

Comments

Feedback can be submitted to the issues tracker.

schedulefree-mp's Issues

Free energy computation around deterministic nodes

Currently, free energy is computed by the edges who query the connected nodes. However, deterministic nodes have no free energy.

This becomes a problem in equality nodes. Suppose we have 3 edges x,y and z connected via and equality node. They each are also connected to other nodes, f,g and h respectively.

[f] -----x-----[ = ]-----y-------[g]
                 |
                 z
                 |
                [h]

To get the free energy for edge y, we would need to query the energies of f and h. Edge y cannot access these nodes, because the equality is in between. We need some way of passing energies through equality / deterministic nodes or some way for edges to reach beyond just their connected nodes.

Edit by Joris if you add three backticks around a graph it will be rendered as-is. This is typically just used for code, but helps in this case as well.

Incorporate buffered signals

Currently, I'm looking at a time slice of the factor graph and each outgoing message is placed in a queue. After defining the nodes and edges, I run a clock where I dequeue messages and update variational parameters.

The main issue with passing messages in continuous time is that no two messages will ever arrive at exactly the same time. That changes the variational updates. Instead of a single update consisting of the product of two new messages, it becomes two updates with the product of a new message and an old message.

One solution, offered by Joris Kraak, is to set up buffers. When two messages arrive within the same time window, the variational parameters are updated using both messages.

He also recommended Signals.jl for a true reactive-programming-style setup.

Hard-coded node id's

In the Kalman filter, each edge has a dictionary of connected nodes. However, the keys for this dictionary are hard-coded based on orientation in the time-slice of the factor graph. This is confusing, since "left" does not describe whether the node is to the left of the edge or whether the edge is to the left of the node.

Possible fixes: use symbol id's (problem is that one should visualize a time-slice of the factor graph and actually name nodes and edges).

Remove use of global variables and duplication of FFG "edges" and "nodes"

The current implementation of ReactiveMP makes extensive use of global variables. Specifically:

x_tmin = EdgeGaussian("x_tmin")
g_t = TransitionGaussian("g_t")
x_t = EdgeGaussian("x_t")
f_t = LikelihoodGaussian("f_t")
y_t = EdgeDelta("y_t")

are all global variables that later need to be accessed inside different functions, for example inside act. Moreover, an unconventional way of using the eval() function is being used to obtain a reference to these to be able to modify them. A general trend in many programming languages, including Julia, is to avoid changing values of global variables inside function:

Avoiding changing the value of global variables is considered by many to be a programming best-practice. Changing the value of a global variable can cause "action at a distance", making the behavior of a program harder to reason about. This is why the scope blocks that introduce local scope require the global keyword to declare the intent to modify a global variable (source)

Another problem with the current implementation of ReactiveMP is that there are duplicate instances of the notions of "edges" and "nodes" in a factor graph: the ones contained inside the MetaGraph object and the composite types defined by us, like x_tmin, g_t, etc.

One way to solve these two issues is to encapsulate all the relevant data of edges and nodes into the MetaGraph object itself. We can do this by transferring all the fields defined inside the composite types into properties of the MetaGraph instance. One way to do this is by overloading the add_edge! and add_vertex! functions. Here is a small example that does this:

using LightGraphs, MetaGraphs, Distributions

import LightGraphs:
    add_edge!

"""
Overloads the 'add_edge!' function by accepting an extra 'distribution'
argument that will be stored as a property of the edge.
"""
function add_edge!(
    graph::LightGraphs.SimpleGraphs.AbstractSimpleGraph,
    distribution::Normal{Float64},
    src,
    dst)

    set_prop!(mg, Edge(src, dst), :type, distribution)
    # TODO: add all other properties needed by a FFG edge

    add_edge!(graph, src, dst)
end


# Call the overloaded add_edge!
mg = MetaGraph(path_digraph(5))
d = Normal(3, 5)
add_edge!(mg, d, 1, 2)

All the relevant data of the factor graph would be included inside the MetaGraph object which could be easily passed and modified by the different functions without having to rely on global variables. And there will be one instance of edges and nodes.

Queues of unequal length

In the Kalman filter, every edge has a message for each connected node. But exactly when to dequeue them and update the edge is difficult.

Currently, I iterate through the longer one until both are equally long.