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:
“Perhaps it is nothingness which is real and our dream which is non-existent, but then we feel think that these musical phrases, and the notions related to the dream, are nothing too. We will die, but our hostages are the divine captives who will follow our chance. And death with them is somewhat less bitter, less inglorious, perhaps less probable.”
—Marcel Proust (1871–1922)
“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 current flows fast and furious. It issues in a spate of words from the loudspeakers and the politicians. Every day they tell us that we are a free people fighting to defend freedom. That is the current that has whirled the young airman up into the sky and keeps him circulating there among the clouds. Down here, with a roof to cover us and a gasmask handy, it is our business to puncture gasbags and discover the seeds of truth.”
—Virginia Woolf (1882–1941)