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 Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a “global village” instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacle’s present vulgarity.”
—Guy Debord (b. 1931)
“To give an accurate description of what has never occurred is not merely the proper occupation of the historian, but the inalienable privilege of any man of parts and culture.”
—Oscar Wilde (1854–1900)
“Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
—Elaine Heffner (20th century)