In any probabilistic inference problem, one of the main objectives is to compute the local marginal densities of a global probability mass function (PMF). Such a computation in general require a summation with an exponential number of terms, which makes its exact computation intractable [Dagum and Luby, 1993].

Our approach for estimating marginal densities hinges

Proceedings of the 23International Conference on Artifi-cial Intelligence and Statistics (AISTATS) 2020, Palermo, Italy. PMLR: Volume 108. Copyright 2020 by the author(s).

on the notions of the normal realization (in which there is an edge for every variable) [Forney, 2001], the normal factor graph (NFG), and the dual NFG. The NFG duality theorem states that the partition function of a primal NFG and the partition function of its dual are equal up to some known scale factor [Al-Bashabsheh and Mao, 2011, Forney, 2011]. It has been demonstrated that, in the low-temperature regime, Monte Carlo methods for estimating the partition function converge faster in the dual NFG than in the primal NFG of the two-dimensional (2D) Ising model [Molkaraie and Loeliger, 2013] and of the q-state Potts model [Al-Bashabsheh and Mao, 2014, Molkaraie and Gómez, 2018].

In this paper, we prove that marginal densities of a global PMF of a primal NFG and the corresponding marginals of the dual NFG are related via local mappings. Remarkably, the mapping is independent of the size of the model, of the topology of the graph, and of any assumptions on the parameters of the model.

Each marginal density can of course be expressed as a ratio of two partition functions. In non-homogeneous models, each ratio needs to be estimated separately via variational inference algorithms or via Monte Carlo methods. However, our proposed mapping allows a simultaneous transformation of estimated marginal densities from one domain to the other.

The mapping is practically advantageous if computing such estimates can be done more efficiently in the dual NFG than in the primal NFG. Indeed, for the ferromagnetic Ising model in a positive external field there is a rapidly mixing Markov chain (called the subgraphs-world process) to generate configurations in the dual NFG of the Ising model. As models, we mainly focus on binary models with symmetric pairwise interactions (e.g., the Ising model). However, we will briefly discuss extensions of the proposed mappings to non-binary models (e.g., the q-state Potts model).

Next, we will describe our models in the primal and in the dual domains.

Suppose variables are associated with the vertices (sites) of a connected graph G = (V, E) with |V| = N vertices and |E| edges (bonds). Two variables () interact if their corresponding vertices are connected by an edge in G. Each variable takes values in A = Z/2Z, i.e., the set of integers modulo two. We will mainly view A as a group with respect to addition.

In the primal domain, the probability of a configura-tion x is given by

Furthermore, we assume that each pairwise potential factor ) is only a function of . To lighten notations we denote the index pair (by a single index . In the primal domain, we express the global probability mass function (PMF) as

Here, the normalization constant is the partition function, are the edge-weighing factors, and are the vertex-weighing factors [Molkaraie, 2017, Forney, 2018].

The factorization in (2) can be represented by an NFG G = (V, E), where vertices represent the factors and edges represent the variables. The edge that represents some variable is connected to the vertex representing the factor ) if and only if is an argument of ). If a variable appears in more than two factors, it is replicated using an equality indicator factor [Forney, 2001].

For a 2D lattice, the NFG of (2) is depicted in Fig. 1, in which the unlabeled boxes represent ), small unlabeled boxes represent ). In Fig. 1, boxes labeled “+” are instances of zero-sum indicator factors I), which impose the constraint that all their incident variables sum to zero, and boxes labeled “=” are instances of equality indicator factors I), which impose the constraint that all their incident variables are equal.

E.g., the equality indicator factor involving and is given by

and the zero-sum indicator factor involving and is as in

Figure 1: Primal NFG of the factorization (2).

where ) is the Kronecker delta function. (Note that all arithmetic manipulations are modulo two.)

In the primal NFG, variables include X = V} and Y = . However, these variables are not independent. Indeed, we can freely choose X and therefrom fully determine Y [Molkaraie and Gómez, 2018, Forney, 2018]. E.g., if we take G to be a d-dimensional lattice, we can compute each component of Y by adding two components of X that are incident to the corresponding zero-sum indicator factor (see Fig. 1).

The number of configurations in the primal domain is thus , and

The Ising model can be easily formulated via (2). In an Ising model the energy of a configuration x is given by the Hamiltonian

which can be expressed as

Here is the coupling parameter associated with the bond and is the external field at site V. The model is called homogeneous if couplings are constant and ferromagnetic if 0 for all .

the Hamiltonian is

The probability of x is given by the Gibbs-Boltzmann distribution [Yeomans, 1992]

where denotes the inverse temperature.

From (7) and (8), it is straightforward to obtain the edge-weighing factors of the Ising model as

and the vertex-weighing factors as

The Gibbs-Boltzmann distribution in (8) can therefore be expressed via the factorization (2).

The dual NFG has the same topology as the primal NFG, but with factors replaced by the discrete Fourier transform (DFT) or the inverse DFT of corresponding factors in the primal NFG.

We can obtain the dual NFG of our binary models by replacing factors by their one-dimensional (1D) DFT, equality indicator factors by zero-sum indicator factors, and zero-sum indicator factors by equality indicator factors [Al-Bashabsheh and Mao, 2011, Molkaraie and Loeliger, 2013, Molkaraie, 2016].

We will use the tilde symbol to denote variables in the dual NFG, which also take values in A.

The dual NFG of Fig. 1 is illustrated in Fig. 2, in which the unlabeled boxes represent ˜, the 1D DFT of ), given by

and for the small unlabeled boxes are ˜R, the 1D DFT of ), as in

The set of variables in the dual domain consist of ˜Y = and ˜X = . Again, these variables are not independent as we can freely choose ˜Y and therefrom fully determine ˜X. E.g., if we take G to be a d-dimensional lattice and assume periodic boundaries, each component ˜of ˜X can be computed by adding 2d components of ˜Y that are incident to the corresponding zero-sum indicator factor (see Fig. 2).

Figure 2: The dual of the NFG in Fig. 1.

In the dual NFG, the number of configurations is , and its the partition function is given by

On condition that factors (11) and (12) are nonnegative, we can define the global PMF in the dual NFG as

The dual Ising model can be expressed via (14). Indeed

in agreement with (9) and (11), and

in agreement with (10) and (12).

If the model is ferromagnetic (i.e., 0 ) and in a nonnegative external field (i.e., 0), factors (15) and (16) will be nonnegative. In this case, the global PMF of the dual Ising model is given by (14).

Throughout this paper, we assume that each edge connects two distinct vertices of the NFG (i.e., there are no dangling edges with one end attached to a vertex and the other end free). In this setting, according to the NFG duality theorem, the partition functions and are equal up to some scale factor ). Indeed

where ) only depends on the topology of G.

For more details, see [Al-Bashabsheh and Mao, 2011], [Molkaraie, 2017, Appendix],[Forney, 2018, Thm 8].

In [Jerrum and Sinclair, 1993], the authors proposed a rapidly mixing Markov chain (called the subgraphs-world process) which evaluates the partition function of an arbitrary ferromagnetic Ising model in a positive external field to any specified degree of accuracy.

The mixing time of the process is polynomial in the size of the model at all temperatures. Indeed, the expected running time of the generator of the subgraphs-world process is (log + , where is the confidence parameter. For more details, see [Jerrum and Sinclair, 1993, Section 4].

The subgraphs-world process employs the following expansion of Z defined on the set of edges in powers of tanh(H) and tanh() as

where odd(W) denotes the set of all odd-degree vertices in the subgraph of E induced by W. The expansion (18) is known as the high-temperature series expansion of the partition function [Newell and Montroll, 1953, Yeomans, 1992, Grimmett and Janson, 2009].

Proposition 1. The configurations that arise in the high-temperature series expansion of the partition function (which are the configurations of the subgraphs-world process) coincide with the valid con-figurations in the dual NFG of the Ising model.

See [Molkaraie and Gómez, 2018, Section VIII] and [Forney, 2018, Section III-E] for the proof.

Following Proposition 1, we can employ the subgraphs-world process (as a generator for the subgraphs-world configurations) to generate configurations in the dual NFG of the Ising model. The process is rapidly mixing and therefore converges in polynomial time. However, under reasonable complexity assumptions, there is no generalization of this approximation scheme to the (nonbinary) Potts model or to spin glasses. For more details, see [Goldberg and Jerrum, 2012, Galanis et al., 2016].

Next, we will present local (edge-based) mappings that transform marginal densities from the dual NFG to the primal NFG, or vice versa. The mappings depend on the DFT of the local factors of the models.

. . .

Figure 3: The edge in the intermediate primal NFG (left) and in the intermediate dual NFG (right). The unlabeled box (left) represents (22) and the unlabeled box (right) represents (23).

The edge marginal PMF of in the primal NFG can be computed as

where

with

(21) Here, 0 and ) = ), hence (19) is a valid PMF over A.

In coding theory terminology, is called the intrinsic message vector and is called the extrinsic message vector at edge . According to the sum-product message passing update rule, the edge marginal PMF vector is computed as the dot product of the intrinsic and extrinsic message vectors up to scale. The scale factor is equal to the partition function [Forney, 2001, Kschischang et al., 2001].

In our setup, ) is the partition function of an intermediate primal NFG with all factors as in the primal NFG, excluding the factor ), which is replaced by

Fig. 3 (left) shows the corresponding edge in the intermediate primal NFG. The intermediate dual NFG is shown in Fig. 3 (right), in which the factor ˜) is replaced by

which is the 1D DFT of (22). According to the NFG duality theorem (17), the partition function of the intermediate dual NFG is ).

Hence

Proposition 2. The vectors and { ˜are DFT pairs.

Proof. For , the partition function of the intermediate dual NFG is the dot product of message vectors and { ˜. Thus

which gives

which is an instance of the two-point DFT.

Proposition 3. The vectors and ˜are DFT pairs.

Proof. From (19) and (21) we have

But (17), (24), and (25) yield

in matrix-vector format via the two-point DFT. By virtue of Proposition 3, it is possible to estimate edge marginal densities in one domain, and then transform them to the other domain all together. The mapping is fully local, and is independent of the size of the graph N and of the topology of G. (Indeed, the relevant information regarding the rest of the graph is incorporated in the estimated edge marginal densities.)

We state without proof that

Proposition 4. The vectors and are DFT pairs.

For the general Ising model substituting factors (9) and (15) in (32) yields

(33) for = 0.

Let us consider a homogeneous and ferromagnetic Ising model. A straightforward calculation shows that the fixed points of the mapping (33) are given by

Fig. 4 shows the fixed points (34) as a function of .

Proposition 5. The min of (0) and the max of (1) are attained at the criticality of the 2D homo- geneous Ising model without an external field.

Proof. In the thermodynamic limit (i.e., as ) the 2D Ising model undergoes a phase transition at = ln(1 +44 [Onsager, 1944].

In the absence of an external field and for = 1, the Hamiltonian (7) can be expressed as

where for e = (.

Figure 4: The fixed points (34) as a function of . The filled circles show the fixed points at criticality of the 2D Ising model given by (46).

The average energy is equal to

In the 2D Ising model with periodic boundaries |E| = 2N, thus the average energy per site is given by

From Onsager’s closed-form solution

and the average (internal) energy per site is given by

See [Onsager, 1944], [Baxter, 2007, Chapter 7] for more details.

A routine calculation shows that ) = 1, thus

Figure 5: For a ferromagnetic Ising model in a nonnegative external field, the solid black plot and the dashed blue plot show the lower bound on (0), given by (47), and the lower bound on (0), given by (48), as a function of , respectively. The lower bounds intersect at the criticality of the 2D homogeneous Ising model in zero field, denoted by .

which coincides with the min of (0) and the max of (1). We emphasize that in the 2D homogeneous Ising model in zero field and in the thermodynamic limit (i.e., as ), edge marginal densities in the primal and dual domains are equal at criticality.

The fixed points (0) and (1) at criticality in (46) are illustrated by filled circles in Fig. 4.

Proposition 6. In an arbitrary ferromagnetic Ising model in a nonnegative external field, it holds that

and

Proof. Since the Ising model is ferromagnetic and in a nonnegative external field, we can define the global PMF ) in the dual domain as in (14). From (33), we have

We conclude from (50) that (0) achieves its minimum when (0) = 1. After substituting (0) = 1 in (50), and after a little rearranging, we obtain

The proof of (48) follows along the same lines.

Figure 6: The fixed points (60) as a function of for different values of q. The filled circles show the fixed points at criticality of the 2D Potts model located at = ln(1 + ).

Proposition 6 is valid for arbitrary ferromagnetic Ising models in a nonnegative external magnetic field, i.e., the bonds do not depend on N (the size of the graphical model G) and on the topology of G.

Fig. 5 shows the lower bounds in (47) and (48) as a function of . The lower bounds intersect at , i.e., at the criticality of the 2D homogeneous Ising model in the absence of an external field.

Remark 1. From (47) and (48) we conclude that in an arbitrary ferromagnetic Ising model in a nonnegative external field

which is in the form of an uncertainty principle.

We briefly discuss extensions of our mapping to non-binary models, in particular to the q-state Potts model [Wu, 1982, Baxter, 2007]. Accordingly, we let A = Z/qZ for some integer 2. (The binary Ising model is recovered as the special case q = 2.)

In the absence of an external field, the Hamiltonian of the model is given by

From (8) and (54), we obtain that in the primal NFG

and in the dual NFG, factors are equal to the 1D DFT

Figure 7: Everything as in Fig. 6 but for (1) in (61).

of (55) given by

which is nonnegative if the model is ferromagnetic (i.e., 0). See [Al-Bashabsheh and Mao, 2014, Molkaraie and Gómez, 2018] for more details on constructing the primal and the dual NFG of the Potts model, with or without an external field.

A straightforward generalization Proposition (3) gives the mapping between and ˜via

with

, where is the q-point DFT matrix (i.e., the Vandermonde matrix for the roots of unity) and i = 1 (see [Bracewell, 1999]).

However, due to symmetry in the factors of the primal (55) and the dual Potts model (56), we have

and

Thus, e.g., for q = 3, the mapping yields

which is real-valued.

For a homogeneous and ferromagnetic q-state Potts model, the fixed points are given by

and

for t 1, 2, . . ., q .

Figs. 6 and 7 show the fixed point (60) and (61) as a function of . Like the Ising model, the minimum of (0) is attained at the criticality of the 2D Potts model located at = ln(1 + ) [Wu, 1982].

It is easy to show that at criticality and in the manycomponent limit (i.e., as ), we have

Remark 2. Transforming marginals from one domain to the other requires a matrix-vector multiplication with computational complexity ). However, when there is symmetry in the factors, as in (9) and (55), the complexity can be reduced to O(|A|).

Remark 3. In binary models, factors in the dual NFG can in general take negative values, and in nonbinary models, the factors can be complex-valued. In such cases a valid PMF can no longer be defined in the dual domain. The mappings remain nevertheless valid; but for marginal functions (instead of marginal densities) of a global function with a factorization given by (14).

In both domains estimates of marginal densities can be obtained via Monte Carlo methods or via variational algorithms [Robert and Casella, 2004, Murphy, 2012]. We only consider the subgraphs-world process (SWP) and two variational algorithms, the belief propagation (BP) and the tree expectation propagation (TEP), for the Ising model. Estimated marginals in the dual domain are then transformed all together to the primal domain via (32) and(59). In all experiments, the exact marginal densities are computed via the junction tree algorithm implemented in [Mooij, 2010].

The choice of methods and the models is far from exhaustive – our goal is to show the advantage of using the mappings in approximating marginal densities in similar settings.

In our first experiment, we consider a 2D homogeneous Ising model, in a constant external field = 0.15, with periodic boundaries, and with size N = 6 6. For this model, BP and TEP in the primal and in the dual domains give virtually indistinguishable approximations. We also apply SWP using 10samples. Fig. 8 shows the relative error in estimating (0) as a function of , where SWP (which operates in the dual NFG) gives good estimates in the whole range.

Compared to variational algorithms, convergence of the SWP is slow; moreover, SWP is only applicable

0.05 0.15 0.25 0.35 0.45 0.55 0.65 0.75 10

Figure 8: Relative error as a function of in estimating (0) of a homogeneous Ising model in a constant external field = 0.15, with periodic boundaries, and with size N = 6 6.

to ferromagnetic Ising models in a positive field. (Indeed, in order to have an irreducible Markov chain in the SWP the external field needs to be nonzero [Welsh, 1993, Chapter 8]). In the rest of the experiments, we consider Ising models in the absence of an external field, and only compare the efficiency of variational algorithms employed in the primal and in the dual domains.

In the second experiment, we consider a 2D Ising model with size N = 6 6 and with periodic boundaries. Couplings are chosen randomly according to a half-normal distribution, i.e., with ). Fig. 9 shows the average relative error in estimating the marginal density (0) as a function of , where the results are averaged over 200 independent realizations. We consider a fully-connected Ising model with N = 10 in our last experiment. Couplings are chosen randomly according to ], i.e., uniformly between 0.05 and denoted by the x-axis. The average relative error over 50 independent realizations is illustrated in Fig. 10.

In both experiments, BP and TEP provide close approximations in the dual domain, therefore only BP results are reported. Figs. 9 and 10 show that for 25 and 20, BP in the dual NFG can significantly improve the quality of estimates – even by more than two orders of magnitude in terms of relative error.

We proved that marginals densities of a primal NFG and the corresponding marginal densities of its dual NFG are related via local mappings. The mapping provides a simple procedure to transform simultaneously

0.05 0.25 0.45 0.65 0.85 1.05 1.25 1.45 1.65 1.85 10

Figure 9: Average relative error in estimating (0) of an Ising model with periodic boundaries and with size N = 6 6. Couplings are chosen randomly according to a half-normal distribution with variance .

0.05 0.15 0.25 0.35 0.45 0.55 0.65 10

Figure 10: Average relative error in estimating (0) in a fully-connected Ising model with N = 10. Coupling parameters are chosen uniformly and independently between 0.05 and denoted by the x-axis.

the estimated marginals from one domain to the other. Furthermore, the mapping relies on no assumptions on the size or on the topology of the graphical model. Our numerical experiments show that estimating the marginals in the dual NFG can sometimes significantly improve the quality of approximations in terms of relative error. In the special case of the ferromagnetic Ising model in a positive external field, there is indeed a rapidly mixing Markov chain (the subgraphs-world process) to generate configurations in the dual domain.

The author is extremely grateful to G. D. Forney, Jr., for his comments and for his continued support. The author also wishes to thank J. Dauwels, P. Vontobel, V. Gómez, and B. Ghojogh for their comments.

[Al-Bashabsheh and Mao, 2011] Al-Bashabsheh, A. and Mao, Y. (2011). Normal factor graphs and holographic transformations. IEEE Transactions on Information Theory, 57:752–763.

[Al-Bashabsheh and Mao, 2014] Al-Bashabsheh, A. and Mao, Y. (2014). On stochastic estimation of the partition function. Proc. IEEE International Symposium on Information Theory, pages 1504–1508.

[Baxter, 2007] Baxter, R. J. (2007). Exactly Solved Models in Statistical Mechanics. Dover Publications.

[Bracewell, 1999] Bracewell, R. N. (1999). The Fourier Transform and Its Applications. McGrawHill.

[Dagum and Luby, 1993] Dagum, P. and Luby, M. (1993). Approximating probabilistic inference in Bayesian belief networks is NP-hard. Artificial Intelligence, 60:141–153.

[Forney, 2001] Forney, G. D. (2001). Codes on graphs: Normal realization. IEEE Transactions on Information Theory, 47:520–548.

[Forney, 2011] Forney, G. D. (2011). Codes on graphs: Duality and MacWilliams identities. IEEE Transactions on Information Theory, 57:1382–1397.

[Forney, 2018] Forney, G. D. (2018). Codes on graphs: Models for elementary algebraic topology and statistical physics. IEEE Transactions on Information Theory, 64:7465–7487.

[Galanis et al., 2016] Galanis, A., Stefankovic, D., Vigoda, E., and Yang, L. (2016). Ferromagnetic Potts model: Refined #BIS-hardness and related results. SIAM Journal on Computing, 45:2004–2065.

[Goldberg and Jerrum, 2012] Goldberg, L. A. and Jer- rum, M. (2012). Approximating the partition function of the ferromagnetic Potts model. Journal of the ACM, 59:1222–1239.

[Grimmett and Janson, 2009] Grimmett, G. and Jan- son, S. (2009). Random even graphs. The Electronic Journal of Combinatorics, 16:R46.

[Jerrum and Sinclair, 1993] Jerrum, M. and Sinclair, A. (1993). Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22:1087–1116.

[Kschischang et al., 2001] Kschischang, F. R., Frey, B. J., and Loeliger, H.-A. (2001). Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47:498–519.

[Molkaraie, 2016] Molkaraie, M. (2016). An importance sampling algorithm for the Ising model with strong couplings. Proc. International Zurich Seminar on Communications, pages 180–184.

[Molkaraie, 2017] Molkaraie, M. (2017). The primal versus the dual Ising model. Proc. 55th Annual Allerton Conference on Communication, Control, and Computing, pages 53–60.

[Molkaraie and Gómez, 2018] Molkaraie, M. and Gómez, V. (2018). Monte Carlo methods for the ferromagnetic Potts model using factor graph duality. IEEE Transactions on Information Theory, 59:7449–7464.

[Molkaraie and Loeliger, 2013] Molkaraie, M. and Loeliger, H.-A. (2013). Partition function of the Ising model via factor graph duality. Proc. IEEE International Symposium on Information Theory, pages 2304–2308.

[Mooij, 2010] Mooij, J. M. (2010). libdai: A free and open source C++ library for discrete approximate inference in graphical models. The Journal of Machine Learning Research, 11:2169–2173.

[Murphy, 2012] Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT Press.

[Newell and Montroll, 1953] Newell, G. F. and Mon- troll, E. W. (1953). On the theory of the Ising model of ferromagnetism. Reviews of Modern Physics, 25:353–389.

[Onsager, 1944] Onsager, L. (1944). Crystal statistics. I. A two-dimensional model with an orderdisorder transition. Physical Review, 65:117–149.

[Robert and Casella, 2004] Robert, C. P. and Casella, G. (2004). Monte Carlo Statistical Methods. Springer.

[Welsh, 1993] Welsh, D. J. A. (1993). Complexity: Knots, Colourings and Countings. Cambridge University Press.

[Wu, 1982] Wu, F.-Y. (1982). The Potts model. Reviews of Modern Physics, 54:235–268.

[Yeomans, 1992] Yeomans, J. M. (1992). Statistical Mechanics of Phase Transitions. Oxford University Press.