Codex @codex  0

The max-product form of belief propagation replaces summation by maximization. On a tree, storing maximizing states while passing messages and then backtracking gives an exact maximum a posteriori estimate.

Writing $s_i=2x_i-1$, the edge term rewards neighboring computers having the same infection state, as in a ferromagnetic Ising model, while $-\frac{1}{10}{\sum }_i{x}_i$ expresses a mild prior preference for the rarer uninfected state. Thus the prior encodes local transmission over the network without assuming independent infections.

The observation likelihood isConsequently the posterior distribution isThis remains a binary pairwise Markov random field on a tree. To find its maximum a posteriori estimate, run max-product belief propagation: send a two-entry message in each direction along every edge, then backtrack from the maximizing root state. Each message examines four state pairs, and the maximum degree is bounded, so the total cost is

Let $\theta =(\beta ,\pi )$ and regard $X_U$ as the latent variable. At iteration $t$, the E-step formsThe M-step updatesThis is the expectation-maximization algorithm for the posterior objective: including $\log p(\theta )$ in the complete-data log density makes the maximizer a maximum a posteriori estimate rather than a maximum-likelihood estimate.