Inference by belief propagation in composite systems

We devise a message passing algorithm for probabilistic inference in composite systems, consisting of a large number of variables, that exhibit weak random interactions among all variables and strong interactions with a small subset of randomly chosen variables; the relative strength of the two interactions is controlled by a free parameter. We examine the performance of the algorithm numerically on a number of systems of this type for varying mixing parameter values.

Figure 1

Graphical representation of the composite inference problem, characterized by a high number of weak links between all variables and an evidential node, and only a few strong couplings to randomly selected variables.

Figure 2

(Color online) Performance of the BP-based algorithm for composite systems. (a) Error probability as a function of the number of iterations $t$ for different mixing parameter values $\gamma$ and fixed connectivity systems of $C=3$. Rapid convergence to low error-probability values is observed for high $\gamma$ values while residual asymptotic error probability remains for dense connectivity dominated systems of low $\gamma$ values. (b) Asymptotic error probability $P_e^{asy}$ as a function of $\gamma$, for fixed (solid lines) and random connectivity (of mean $\overline{C}$—dashed lines). (c) Median number of time steps required for convergence $t_{\text{med}}$ as a function of $\gamma$, both for the fixed (solid lines) and random (dashed lines) connectivities. (d) Asymptotic error probability as a function of the noise variance for fixed connectivity $C$, and mixing parameters $\gamma =0.25$ (solid lines), and 0.75 (dashed lines).

Figure 3

(Color online) The convergence measure $D\left(t\right)$ for various $\gamma$ and connectivity values. (a) Fixed connectivity $C=5$; (b) Fixed connectivity $C=6$.