Related Algorithm and Complexity Issues
A similar algorithm is commonly referred to as the Viterbi algorithm, but also known as the max-product or min-sum algorithm, which solves the related problem of maximization, or most probable explanation. Instead of attempting to solve the marginal, the goal here is to find the values that maximises the global function (i.e. most probable values in a probabilistic setting), and it can be defined using the arg max:
An algorithm that solves this problem is nearly identical to belief propagation, with the sums replaced by maxima in the definitions.
It is worth noting that inference problems like marginalization and maximization are NP-hard to solve exactly and approximately (at least for relative error) in a graphical model. More precisely, the marginalization problem defined above is #P-complete and maximization is NP-complete.
The memory usage of belief propagation can be reduced through the use of the Island algorithm (at a small cost in time complexity).
Read more about this topic: Belief Propagation
Famous quotes containing the words related, complexity and/or issues:
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)
“The “universal moments” of child rearing are in fact nothing less than a confrontation with the most basic problems of living in society: a facing through one’s children of all the conflicts inherent in human relationships, a clarification of issues that were unresolved in one’s own growing up. The experience of child rearing not only can strengthen one as an individual but also presents the opportunity to shape human relationships of the future.”
—Elaine Heffner (20th century)