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:
“Never miss an opportunity to allow a child to do something she can and wants to on her own. Sometimes we’re in too much of a rush—and she might spill something, or do it wrong. But whenever possible she needs to learn, error by error, lesson by lesson, to do better. And the more she is able to learn by herself the more she gets the message that she’s a kid who can.”
—Polly Berrien Berends (20th century)
“It was like passing a boundary to dive
Into the sun-filled water, brightly leafed
And limbed and lighted out from bank to bank.
That’s how the stars shine during the day.”
—Wallace Stevens (1879–1955)
“In his very rejection of art Walt Whitman is an artist. He tried to produce a certain effect by certain means and he succeeded.... He stands apart, and the chief value of his work is in its prophecy, not in its performance. He has begun a prelude to larger themes. He is the herald to a new era. As a man he is the precursor of a fresh type. He is a factor in the heroic and spiritual evolution of the human being. If Poetry has passed him by, Philosophy will take note of him.”
—Oscar Wilde (1854–1900)