AI Glossary / Probabilistic machine learning / Advanced

Max-product algorithm

Definition

The max-product algorithm is a message-passing method for finding a highest-probability joint assignment in a factorized probability model. On a tree, it can compute exact maximum scores and recover a consistent best assignment using stored choices and backtracking.

What it means

Many prediction tasks involve connected decisions. A label for one position may be plausible by itself but incompatible with labels elsewhere. Max-product searches for the best combination under the model, rather than selecting each variable's most probable marginal value independently.

The probability can be represented as a product of nonnegative factors expressing local evidence and compatibility. A normalizing constant shared by every assignment does not affect which assignment has the largest score.

The word “max” distinguishes this operation from sum-product inference. Summing over alternatives measures their combined probability; maximizing retains only the best-scoring alternative for the particular message calculation. These answer different questions.

How it works

Choose a root in a tree and send messages inward from its leaves. A message to a neighboring variable specifies the best score achievable on the sender's side for each possible value of the receiving variable.

Combine local factors with incoming messages, maximize over the variables being eliminated and store which choices attained each maximum. At the root, select a value with the highest total score. Follow the stored choices outward to recover one globally consistent assignment.

A second message pass can obtain max-marginal scores at all nodes. These are maxima over the other variables, not ordinary marginal probabilities. On graphs with loops, repeatedly applying similar updates is not generally guaranteed to converge or find the global optimum. Working with logarithms gives the related max-sum algorithm and avoids many tiny products.

Three practical examples

• A sequence model finds its most probable complete hidden-state sequence rather than choosing each position separately.
• A tree-structured diagnostic model identifies one best joint explanation of observed signals under its specified factors.
• A structured labeling prototype combines local label evidence with pairwise compatibility when the dependency graph permits exact tree inference.

Think of it this way

Think of planning a connected journey by keeping the best route to each intermediate destination. Once the final destination is chosen, recorded predecessor choices reveal the full route.

The analogy explains dynamic programming and backtracking. An arbitrary travel network may contain cycles or constraints that do not match the tree structure, and a best route does not describe the probability of all possible routes.

Worked example

Three binary variables on a chain

Consider A - B - C, with each variable either 0 or 1. Their local factors for values (0, 1) are A: (2, 1), B: (1, 3), and C: (4, 1). Each neighboring pair contributes factor 2 when its values match and factor 1 when they differ.

Root the chain at B. The A-to-B message for B = 0 is max(2 times 2, 1 times 1) = 4. For B = 1 it is max(2 times 1, 1 times 2) = 2.

The C-to-B message is 8 for B = 0 and 4 for B = 1. Combining these messages with B's local factors gives root scores 1 times 4 times 8 = 32 and 3 times 2 times 4 = 24.

Choose B = 0. Backtracking selects A = 0 and C = 0, giving the joint assignment (0, 0, 0) with score 32. Independently choosing each variable's preferred local value would produce (0, 1, 0), whose score is only 24.

These are unnormalized joint scores, not probabilities. The example does not calculate marginal probabilities; its purpose is to show why compatibility and global backtracking matter.

Illustrative case study

A fictional document-processing team assigns labels to a sequence of form fields. Its local recognizer occasionally chooses combinations inconsistent with the model's allowed field transitions.

The team constructs a chain model and uses max-product-style decoding with predecessor records. It validates the implementation on short sequences where every assignment can also be enumerated, including cases with tied best sequences and impossible transitions.

The resulting decoder returns the best sequence under the specified model. That does not establish that its learned factors represent every real form layout, so the team separately reviews errors on unfamiliar document types.

Common misconceptions and mistakes

• Max-marginals are ordinary marginals: they maximize over other variables rather than sum over them.
• Independent tie-breaking always gives a valid optimum: choices can conflict. For example, if two binary variables prefer disagreement equally, choosing 0 at both nodes independently misses both best assignments.
• The largest local evidence determines the global answer: compatibility can change the best combination.
• Tree guarantees automatically extend to loops: loopy max-product needs separate analysis and may fail.

Business use

The method is useful when a system must output one coherent structured prediction and its factorization supports efficient inference. Sequence decoding and tree models can avoid enumerating an exponentially large list of complete assignments.

Clarify whether the business decision needs one best configuration, uncertainty for each component or expected cost under all possibilities. A maximum-probability configuration is not automatically the action with the lowest expected business loss. Track numerical stability, handling of zero factors and deterministic tie-breaking as implementation requirements.

People also ask

Is this the Viterbi algorithm?

Viterbi decoding is a closely related dynamic-programming instance for finding a best state sequence in a chain model.

Must factors sum to one individually?

No. Nonnegative compatibility factors can be unnormalized as long as the overall probability model is well defined.

Can it return confidence for each label?

Its max-marginal scores are not directly marginal probabilities. Probability-based confidence typically requires a different calculation, such as sum-product where applicable.

Check your understanding

Two best assignments are (0, 1) and (1, 0). Can independently selecting the smaller tied value at each node safely recover a best assignment?

Answer: No. That rule selects (0, 0), which need not be optimal. Backtracking preserves compatible choices from one joint solution.

Related terms

• Factor graph
• Belief propagation
• Viterbi algorithm
• Dynamic programming
• Maximum a posteriori estimation
• sum-product algorithm
• max-sum algorithm
• backtracking

Learn next

Enumerate every assignment in a tiny chain, then reproduce its best score with messages. Replace maxima by sums and compare the resulting quantities. Finally introduce a loop and identify exactly which tree-based independence arguments no longer apply.

More in Probabilistic machine learning

• Masked autoregressive flow - A masked autoregressive flow, or MAF, is a normalizing-flow model that uses masked neural networks to transform observed data into a simpler base distribution.
• Matching network - A matching network is a few-shot classification model that predicts a query's label by attending to labeled examples in a support set.
• Matrix normal distribution - The matrix normal distribution is a probability distribution for a matrix whose entries jointly follow a multivariate Gaussian distribution with a separable...
• Maximum entropy reinforcement learning - Maximum entropy reinforcement learning trains a policy to maximize a combination of expected reward and policy entropy.
• Maximum pseudolikelihood estimation - Maximum pseudolikelihood estimation fits model parameters by maximizing a product of conditional probabilities, often one variable conditional on all the...
• Metric multidimensional scaling - Metric multidimensional scaling represents objects as points in a chosen-dimensional space so their distances approximate supplied numerical dissimilarities.

Sources

MIT OpenCourseWare, Algorithms for Inference, Lecture 11: The Max-Product Algorithm, tree updates, backtracking and log-domain variants: https://ocw.mit.edu/courses/6-438-algorithms-for-inference-fall-2014/adb9cebcb7c3feae1cabe02127a4eba5_MIT6_438F14_Lec11.pdf

The three-variable chain, tie illustration and fictional document case are original teaching examples. Exactness statements here concern tree-structured inference with correctly specified factors.

Previous: Max pooling Next: Maxim, Gricean