Message Passing On Factor Graphs
A popular message passing algorithm on factor graphs is the sum-product algorithm, which efficiently computes all the marginals of the individual variables of the function. In particular, the marginal of variable is defined as
where the notation means that the summation goes over all the variables, except . The messages of the sum-product algorithm are conceptually computed in the vertices and passed along the edges. A message from or to a variable vertex is always a function of that particular variable. For instance, when a variable is binary, the messages over the edges incident to the corresponding vertex can be represented as vectors of length 2: the first entry is the message evaluated in 0, the second entry is the message evaluated in 1. When a variable belongs to the field of real numbers, messages can be arbitrary functions, and special care needs to be taken in their representation.
In practice, the sum-product algorithm is used for statistical inference, whereby is a joint distribution or a joint likelihood function, and the factorization depends on the conditional independencies among the variables.
The Hammersley–Clifford theorem shows that other probabilistic models such as Markov networks and Bayesian networks can be represented as factor graphs; the latter representation is frequently used when performing inference over such networks using belief propagation. On the other hand, Bayesian networks are more naturally suited for generative models, as they can directly represent the causalities of the model.
Read more about this topic: Factor Graph
Famous quotes containing the words message, passing and/or factor:
“if once the message greet him
That his True Love doth stay,
If Death should come and meet him,
Love will find out the way!”
—Unknown. Love Will Find Out the Way (l. 53–56)
“It’s a particular Observation I have always made, That of all Mortals, a Critick is the silliest; for by inuring himself to examine all Things, whether they are of Consequence or not, he never looks upon any Thing but with a Design of passing Sentence upon it; by which Means, he is never a Companion, but always a Censor.”
—Richard Steele (1672–1729)
“Children of the middle years do not do their learning unaffected by attendant feelings of interest, boredom, success, failure, chagrin, joy, humiliation, pleasure, distress and delight. They are whole children responding in a total way, and what they feel is a constant factor that can be constructive or destructive in any learning situation.”
—Dorothy H. Cohen (20th century)