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:
“The near explains the far. The drop is a small ocean. A man is related to all nature. This perception of the worth of the vulgar is fruitful in discoveries. Goethe, in this very thing the most modern of the moderns, has shown us, as none ever did, the genius of the ancients.”
—Ralph Waldo Emerson (1803–1882)
“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)
“To make life more bearable and pleasant for everybody, choose the issues that are significant enough to fight over, and ignore or use distraction for those you can let slide that day. Picking your battles will eliminate a number of conflicts, and yet will still leave you feeling in control.”
—Lawrence Balter (20th century)