Description of The Sum-product Algorithm
Belief propagation operates on a factor graph: a bipartite graph containing nodes corresponding to variables V and factors U, with edges between variables and the factors in which they appear. We can write the joint mass function:
where xu is the vector of neighbouring variable nodes to the factor node u. Any Bayesian network or Markov random field can be represented as a factor graph.
The algorithm works by passing real valued functions called messages along the edges between the nodes. These contain the "influence" that one variable exerts on another. There are two types of messages:
- A message from a variable node v to a factor node u is the product of the messages from all other neighbouring factor nodes (except the recipient; alternatively one can say the recipient sends the message "1"):
- where N(v) is the set of neighbouring (factor) nodes to v. If is empty, then is set to the uniform distribution.
- A message from a factor node u to a variable node v is the product of the factor with messages from all other nodes, marginalised over all variables except xv:
- where N(u) is the set of neighbouring (variable) nodes to u. If is empty then .
The name of the algorithm is clear from the previous formula: the complete marginalisation is reduced to a sum of products of simpler terms than the ones appearing in the full joint distribution.
Read more about this topic: Belief Propagation
Famous quotes containing the words description of the, description of and/or description:
“The next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St. Paul’s, like the editions of Balbec and Palmyra.”
—Horace Walpole (1717–1797)
“God damnit, why must all those journalists be such sticklers for detail? Why, they’d hold you to an accurate description of the first time you ever made love, expecting you to remember the color of the room and the shape of the windows.”
—Lyndon Baines Johnson (1908–1973)
“He hath achieved a maid
That paragons description and wild fame;
One that excels the quirks of blazoning pens.”
—William Shakespeare (1564–1616)