An Introduction to PottsUtils

Dai Feng Email: dai_feng@merck.com

Package PottsUtils comprises several functions related to the Potts models defined on undirected graphs. The main purpose of the package is to make available several functions that generate samples from the models. To facilitate that, there are other utilities. Furthermore, there is a by-product of simulation functions. Altogether, there are three sets of functions. The first produces basic properties of a graph to facilitate the simulation functions (they maybe used for other purposes as well). The second provides various simulation functions. The third currently includes only one function which computes the normalizing constant based on simulation results.

This introduction was intended to help users to understand better the functions, the documentation (Rd files), and the source code. For more technical details (mathematical proof among others), we refer users to references herein.

Hereafter, first we introduce some basic concepts and definitions related to the Potts models. Second, algorithms used in simulation functions are presented in a concise way. Third, a function to obtain normalizing constant is introduced. Forth, we discuss some computational issues. Finally, some future work is outlined.

1 Notation and Terminology

In this section we introduce concepts and definitions involved in the discussions of the Potts models. The notations used are similar to those given in Winkler (2003). Based on that, several related functions in the package are introduced.

We consider the Potts model defined on a finite undirected graph. A graph describes a set of connections between objects. Each object is called a node or vertex. There are observations to characterize the properties of vertices. Let 𝒱 be a finite set, the set of vertices; 𝒱={1,2,,…,N}, where N is the total number of vertices. For every vertex i∈𝒱, let zi take values in a finite set of categories 𝒵={1,2,…,k}, where k is the number of categories. In the package we use different colors to represent different categories and vertices from the same category are of the same color. The product 𝐙=𝒵N is the space of configurations 𝐳=(zi,i∈𝒱). A strictly positive probability measure P on 𝐙 for every 𝐳∈𝐙 is called a stochastic or random field. Note that P has to be strictly positive on 𝐙 to satisfy the assumptions of the Hammersley-Clifford theorem; see Besag (1974) and Winkler (2003) for details.

A collection ∂=(∂(v):v∈𝒱) of subsets of 𝒱 is called a neighborhood system, if (i) i∉∂(i) and (ii) i∈∂(j) if and only if j∈∂(i). The sites j∈∂(i) are called neighbors of i. We use i∼j to denote that i and j are neighbors of each other. There is an edge between i and j if and only if they are neighbors. Define a graph 𝒢={𝒱,ℰ}, where ℰ is the set of edges. For a finite undirected graph, the number of vertices are finite and edge (i,j) is equivalent to edge (j,i). The function getEdges() can be used to get edges of a graph. When neighbors i and j are from the same category (of the same color), then there is a bond between them.

The random field P is a Markov random field (MRF) w.r.t. the neighborhood system ∂ if for all 𝐳∈𝐙,

P⁡(zi|zj,j≠i)=P⁡(zi|zj,j∈∂(i))

Probability measures of the form

P⁡(𝐳)=exp⁡{−H⁡(𝐳)}∑𝐱∈𝐙exp⁡{−H⁡(𝐱)}

are called Gibbs fields (or measures). H is called the energy function or Hamiltonian, and ∑x∈𝐙exp⁡{−H⁡(x)} is called the partition function or normalizing constant. For detailed account on MRF, Gibbs measures, and related issues, we refer to Winkler (2003).

When using Markov random field models, the first question is how to define neighbors of all vertices. For a 1D lattice, the simplest way to define neighbors is that every vertex (except those on the boundaries) has the two adjacent vertices as its neighbors, see Figure 1 for illustration. Of course, a vertex could have more than two neighbors.

Refer to caption
Figure 1: 2 neighbors in 1D

For a 2D lattice, there are two common ways to define neighbors. One is that neighbors of a vertex comprise its available N, S, E, and W adjacencies. Another is that, besides those four, there are four diagonal adjacencies on its north-west, north-east, south-west, and south-east. See Figure 2 for illustrations. Probability measures defined on the former are called the first-order Markov random fields and the latter the second-order Markov random fields.

Refer to caption
Figure 2: Four and eight neighbors in 2D

For a 3D lattice, besides defining six neighbors in the x, y, and z directions, one can add twelve diagonal neighbors in the x−y, x−z, and y−z planes, and another eight on the 3D diagonals. This leads to a six neighbor structure, an eighteen neighbor structure, and a twenty-six neighbor structure. For illustration, see Figure 3.

Refer to caption
(a) six neighbors
Refer to caption
(b) eighteen neighbors
Refer to caption
(c) twenty-six neighbors
Figure 3: Illustration of neighbor structures in 3D

The package provides a function called getNeighbors() to generate all neighbors of a graph.

After defining neighbors, the second question is how to model the spatial relationship among neighbors. One choice is to use a model from the Potts model family, a set of MRF models with the Gibbs measure defined as follows.

p⁡(𝐳)=C⁢(β)−1⁢exp⁡{∑i=1Nαi⁢(zi)+β⁢∑i∼jwi⁢j⁢f⁢(zi,zj)} (1)

where C⁡(β) is a normalizing constant and i∼j indicates neighboring vertices. We need to define neighborhood structure and then assign relationships among neighboring vertices. The parameter β, called the inverse temperature, determines the level of spatial homogeneity between neighboring vertices in the graph. A zero β would imply that neighboring vertices are independent. We use positive β values. The wi⁢j are weights and we assume wi⁢j>0. The term ∑i=1Nαi⁢(zi) is called the external field. The αi⁢(zi) are functions of zi. When β=0, the external field completely characterizes the distribution of the independent zi,i=1,2,…,N.

When f⁡(zi,zj)=I⁢(zi=zj) model (1) becomes

p⁡(𝐳)=C⁢(β)−1⁢exp⁡{∑i=1Nαi⁢(zi)+β⁢∑i∼jI⁢(zi=zj)} (2)

For k=2, this model is called the Ising model (Ising, 1925); for k>2 it is the Potts (1953) model. The Ising model was originally proposed to describe the physical properties of magnets. Due to its flexibility and simplicity, the Ising model and its various versions have been widely used in other fields, such as brain models in cognitive science (Feng, 2008), information and machine learning theory (MacKay (2003) and references therein), economics (Bourgine and Nadal (2004) and references therein), sociology (Kohring, 1996) and game theory (Hauert and Szabó, 2005).

The most commonly used Potts model is the one without an external field and with wi⁢j≡1,

p⁡(𝐳)=C⁢(β)−1⁢exp⁡{β⁢∑i∼jI⁢(zi=zj)} (3)

We refer to this as the simple Potts model.

Let αi⁢(zi)≡0 and f⁡(zi,zj)=wi⁢j⁢I⁢(zi=zj). Then (1) reduces to

p⁡(𝐳)=C⁢(β)−1⁢exp⁡{β⁢∑i∼jwi⁢j⁢I⁢(zi=zj)} (4)

where wi⁢j is the weight between vertex i and j. For example we might take wi⁢j=1d⁡(zi,zj) where d⁡(zi,zj) is a distance function, say Euclidean distance, between two vertices. This model is referred to as the compound Potts model.

In model (1), let αi⁢(zi)=0 and define f⁡(zi,zj) as

f⁡(zi,zj)={a1if⁢zi=zja2if⁢|zi−zj|=1a3otherwise (5)

where a1≥a2≥a3. We call this model the repulsion Potts model. This model assumes an ordering of the colors and that neighboring vertices are most likely of the same color, and if they are different then it is more likely that they are similar than totally different. See Feng (2008) for more details.

2 Simulation of the Potts Models

It is very hard to find algorithms (such as inversion of CDF, rejection sampling, adaptive rejection sampling, or ratio-of-uniforms sampling) to generate i.i.d. samples from the Potts models, and Markov chain methods have to be used for the simulation.

To generate samples from model (1), single site updating, for example Gibbs sampling, is easy but may mix slowly. The Swendsen and Wang (1987) algorithm (SW) is widely used to generate random samples from the simple Potts model. Wolff’s algorithm (Wolff, 1989) has been advocated as an alternative to the SW. A Gibbs sampler that takes advantage of the conditional independence structure to update variables zi,i=1,2,…,N, could make the simulation much faster than a single site updating scheme (Feng, 2008). When there is external field, the partial decoupling method might outperform the Gibbs sampling.

2.1 Swendsen-Wang Algorithm

The SW algorithm was originally proposed for the simulation of the simple Potts model. Drawing auxiliary variables ui⁢j|𝐳 for neighboring vertices (i,j) from independent and uniform distributions on [0,exp⁡{β⁢I⁢(zi=zj)}] makes the joint density

p⁡(𝐳,𝐮)∝∏i∼jI[0,exp⁡{β⁢I⁢(zi=zj)}]⁢(ui⁢j) (6)

The conditional distribution of 𝐳 given 𝐮 is also uniform on possible configurations. If ui⁢j≥1, then there is a bond between vertices i and j (when ui⁢j≥1 definitely zi=zj); otherwise there is no further constraint. Therefore, all vertices can be divided into patches (clusters). A patch is a collection of vertices, in which any two vertices are connected by a bond or a sequence of bonds. There is no bond between vertices from different patches. See Figure 4 for illustrations. The vertices within each patch should belong to the same category and the categories of different patches are i.i.d. from the discrete uniform distribution among all possible categories.

Refer to caption
Figure 4: Illustration of the concept of patches.

The SW algorithm is the seminal work on algorithms using auxiliary variables (in this case 𝐮) in this area. A slightly generalized version of the original SW algorithm can be used to generate samples from a compound Potts model (Feng, 2008). Given all vertices, there are three steps in each iteration as follows.

  1. 1.

    Build bonds among vertices in neighbor with probability

    1−e⁢x⁢p⁢(−β⁢wi⁢j⁢I⁢(zi=zj))
  2. 2.

    Build patches for vertices bonded together

  3. 3.

    Flip the patches randomly to any color

The SW algorithm may outperform single-site updating samplers, especially when there is no external field and there is patchiness among vertices, in which simultaneous switching of clusters is necessary. For more details see Feng (2008).

2.2 Wolff’s Algorithm

A modification of the Swendsen-Wang algorithm was proposed by Wolff (1989). The difference between the Wolff and the SW is that instead of flipping all patches randomly, one patch is chosen and all vertices in that patch are flipped to their opposites in the simple Potts model. To be more specific, for Wolff’s algorithm, a vertex, say v, is selected randomly among all vertices, and bonds between v and its neighbors are set the same way as in the SW. If there are bonds between v and its neighbors, say Cv, then the bonds between vertices in Cv and their neighbors are set. Follow the same procedure recursively until no new bonds are created. Now there is a patch around v and all vertices in this patch are flipped to their opposites. Note, there is no randomness involved when flipping vertices for the Ising Model. Although Wolff’s algorithm is similar to the SW, its proof is formalized from another perspective where detailed balance and irreducibility are verified (see Wolff (1989) for details).

To generate samples from a compound Potts model, a slighted generalized version of the original Wolff algorithm as follows can be adopted. There are four steps in each iteration.

  1. 1.

    Randomly select a vertex

  2. 2.

    Build a patch around it with probability

    1−e⁢x⁢p⁢(−β⁢wi⁢j⁢I⁢(zi=zj))
  3. 3.

    Continue building the patch till no additional vertex can be bonded together

  4. 4.

    Flip the patch randomly to another color

See Feng (2008) for more details.

2.3 A Gibbs Sampler Using Conditional Independence

Various multiple-site sampling methods might outperform single-site updating, but sometimes they might not. Multi-site sampling methods like the SW algorithm could tackle the critical slowing down problem. When there is no external field, from the results pointed out in Higdon (1998), the SW algorithm outperforms single-site Metropolis updating when β is at the critical value. When there is an external field (a likelihood function in Bayesian inference for example), the SW slows down since it does not make good use of the data. Hurn (1997) and Smith and Smith (2006) suggested that when β is large, Gibbs samplers might be more effective. The choice of the best sampling method is likely to be problem-specific and there is no clear-cut winner as pointed out in Hurn (1997) and Higdon (1998). Furthermore, the previous studies just focus on relatively small grids in two dimensions with the number of categories equal to 2. What the convergence properties of various algorithms are on a three dimensional large grid with more than 2 categories, the case in MRI analysis for example (Feng, 2008), needs further study. Given that, a Gibbs sampler might be a good choice under certain circumstances. The package provides functions that uses the Gibbs sampler taking advantage of the conditional independence structure to update colors of vertices. It could make the simulation much faster than a one-site-after-another sampling scheme by using the vectorization functions in 𝐑.

The idea is that if we can divide variables that need to be updated into different blocks and given the variables in other blocks, all the variables within the same block are conditionally independent, then we can update all blocks iteratively with the variables within the same block being updated simultaneously. In Figure (a) of 5, under the four neighbor structure in 2D, given the black vertices, the whites are independent and vice versa. By this kind of independence, updating can be done in two steps: one for the blacks, one for the whites. The idea of taking advantage of this kind of independence can be traced back at least to the “Coding Methods” in Besag (1974). It was described in Wilkinson (2005) and detailed discussion can be found in Winkler (2003). This conditional independence can be generalized to 3D lattices with a six neighbor structure, see (b) of Figure 5 for illustration. Under six neighbor structure, given the blacks, the whites are independent and vice versa. The minimum number of blocks to make the vertices within each block independent given the other blocks is called the chromatic number in Winkler (2003). So the chromatic numbers for four neighbor configuration in 2D and six neighbor in 3D are both 2.

Refer to caption
(a) 2D
Refer to caption
(b) 3D
Figure 5: Illustration of Conditional Independence

The extension to the eight neighbor configuration in 2D and eighteen and twenty-six neighbor in 3D is as follows. Under the eight neighbor structure in 2D, the chromatic number is four; under the eighteen neighbor configuration in 3D, the chromatic number is seven; under the twenty-six neighbor configuration in 3D, the chromatic number is eight. For more details, see Feng (2008).

The function to split vertices into conditional independent blocks is getBlocks(). Right now, for a 2D graph, the vertices can be divided into either 2 or 4 blocks, and for a 3D graph either 2 or 8. The functions using the Gibbs sampler that takes advantage of conditional independence are BlocksGibbs() and rPotts1(). The difference between the two is that the first one can only generate samples from a Potts model without the external field while the second is good for all Potts models. The relationship among neighboring vertices can be defined by specifying the parameter spatialMat.

2.4 The Partial Decoupling Method

Besides the Gibbs sampling, another way to obtain samples from a Potts model with external field is to use the partial decoupling method through the function rPotts1().

The partial decoupling method was originally developed by Higdon (1993) for an Ising model with an external field. Given the external field, the symmetry property is violated. Instead of drawing ui⁢j|𝐳 for neighbor points (i,j) from independent uniform distributions on [0,exp⁡{β⁢I⁢(zi=zj)}], draw ui⁢j|𝐳 from the uniform distribution [0,exp⁡{δi⁢j⁢β⁢I⁢(zi=zj)}]. Now, the bonding probability is not only controlled by β alone, but δi⁢j as well. When δi⁢j=0, it reduces to single site updating; when δi⁢j=1, it corresponds to the SW algorithm. The smaller the δi⁢j, the less likely bonds are formed. After setting the bonds, clusters are usually not independent anymore and Gibbs, Metropolis-Hastings, or even partial decoupling could be used to update the coarser model. The Gibbs sampling is used in the package.

The goal of choosing δi⁢j is to improve the mixing when sampling from 𝐳|𝐮. Strategies for the determination of {δi⁢j} are based on the nature of the likelihood function of the data. For example, choosing δi⁢j=0 for vertices on the boundaries of adjacent sub-graphs and δi⁢j=1 for others can prevent the clusters from growing beyond certain limits. Another choice is δi⁢j=aI{yi=yj} with 0<a<1, where yi and yj are observations for vertex i and j. The details of the partial decoupling method can be found in Higdon (1998) and Hurn (1997).

3 Calculation of the Normalizing Constant

The normalizing constant is not critical and can be ignored if β is known. However, if β is treated as unknown, for example in studies using the Bayesian methods (Green and Richardson, 2002; Smith and Smith, 2006), then the normalizing constant is necessary when drawing samples from the conditional distribution of β by a Metropolis-Hastings algorithm.

The package provide a function getNC() to obtain the normalizing constant of a simple Potts model. The method adopted is similar to that in Green and Richardson (2002) and Smith and Smith (2006), in which the thermodynamic integration approach was used. The thermodynamic integration approach comes from the differential equations for describing thermodynamic relationships in physics. Basically, the thermodynamic integration method uses the fact that the normalizing constant can be obtained by solving the differential equation

∂∂β⁢log⁡(C⁡(β))=E⁡(U⁡(𝐳)|β,k)

where U⁡(𝐳)=∑i∼jI⁢(zi=zj) and k is the number of categories. Since

log⁡C⁡(0)=N⁢log⁡k

it follows

logC(β)=Nlogk+∫0βE(U(𝐳)|β′,k)dβ′ (7)

In order to compute log⁡C⁡(β) we use the following steps:

  1. 1.

    Take k grid values {0<β1<β2<…<βk≤β}. For each βi,i=1,2,…,k, obtain n simulations of the graph and estimate E⁡(U⁡(𝐳)|βi,k) by the average of the functions U⁡(𝐳) from n simulations. Possible methods for simulation include Gibbs sampling with single site updating, or the SW, or the Wolff algorithms discussed previously.

  2. 2.

    Compute the integral by numerical integration.

4 Computational Issues

As mentioned in sub-section 2.3, it is beneficial to use vectorization functions in 𝐑 to fulfill the idea of conditional independence. Furthermore, for the SW algorithm the major computational work is the identification and labeling of the patches of connected vertices. This is an instance of a connected component labeling problem for an undirected graph. We use Rem’s algorithm (Dijkstra, 1976) to fulfill the task in the function getPatches(). Besides facilitating the SW algorithm, it can be used in other clustering methods as well. See Heller et al. (2006) for example.

5 Future Work

In the future, the package might be upgraded in several directions. First we might incorporate more available sampling methods for the Potts models. Second, the speed of current functions might be enhanced by using embedded 𝐂 functions and parallel computations. Third, changes based on feedback of users.

References

  • Besag (1974) J. Besag Spatial interaction and the statistical analysis of lattice systems (with discussion). Journal of the Royal Statistical Society. Series B (Methodological) 36 (2), pp. 192–236. Cited by: §1, §2.3.
  • P. Bourgine and J. P. Nadal (Eds.) (2004) P. Bourgine and J. P. Nadal (Eds.) Cognitive economics-and interdisciplinary approach. Springer. Cited by: §1.
  • Dijkstra (1976) E. W. Dijkstra A discipline of programming. Englewood Cliffs, New Jersey : Prentice-Hall, Inc. Cited by: §4.
  • Feng (2008) D. Feng Bayesian hidden markov normal mixture models with application to MRI tissue classification. Ph.D. Thesis, The University of Iowa. Cited by: §1, §1, §2.1, §2.2, §2.3, §2.3, §2.
  • Green and Richardson (2002) P. J. Green and S. Richardson Hidden markov models and disease mapping. Journal of the American Statistical Association 97, pp. 1055–1070. Cited by: §3, §3.
  • Hauert and Szabó (2005) C. Hauert and G. Szabó Game theory and physics. American Journal of Physics 73 (5), pp. 405–414. Cited by: §1.
  • Heller et al. (2006) R. Heller, D. Stanley, D. Yekutieli, N. Rubin, and Y. Benjamini Cluster-based analysis of fmri data. NeuroImage 33, pp. 599–608. Cited by: §4.
  • Higdon (1993) D. M. Higdon Comments on “Spatial Statistics and Bayesian Computation”. Journal of the Royal Statistical Society Series B-Statistical Methodology 55 (1), pp. 78. Cited by: §2.4.
  • Higdon (1998) D. M. Higdon Auxiliary variable methods for Markov chain Monte Carlo with applications. Journal of the American Statistical Association 93, pp. 585–595. Cited by: §2.3, §2.4.
  • Hurn (1997) M. Hurn Difficulties in the use of auxiliary variables in Markov chain Monte Carlo methods. Statics and Computing 7, pp. 35–44. Cited by: §2.3, §2.4.
  • Ising (1925) E. Ising Beitrag zur theorie des ferromagnetismus. Zeitschrift fu̇r Physik 31, pp. 253–258. Cited by: §1.
  • Kohring (1996) G. A. Kohring Ising models of social impact: the role of cumulative advantage. Journal de Physique I 6 (2), pp. 301–308. Cited by: §1.
  • MacKay (2003) D. J.C. MacKay Information theory, inference and learning algorithms. Cambridge University Press. Cited by: §1.
  • Potts (1953) R. B. Potts Some generalized order-disorder transformations. In Cambridge Philosophic Society, Vol. 48, pp. 106–109. Cited by: §1.
  • Smith and Smith (2006) D. Smith and M. Smith Estimation of binary Markov random fields using Markov chain Monte Carlo. Journal of Computational and Graphical Statistics 15 (1), pp. 207–227. Cited by: §2.3, §3, §3.
  • Swendsen and Wang (1987) R. H. Swendsen and J. Wang Nonuniversal critical dynamics in monte carlo simulations. Physical Review Letters 58 (2), pp. 86–88. Cited by: §2.
  • Wilkinson (2005) D. J. Wilkinson Parallel bayesian computation. In Handbook of Parallel Computing and Statistics, E. J. Kontoghiorghes (Ed.), pp. 481–512. Cited by: §2.3.
  • Winkler (2003) G. Winkler Image analysis, random fields and dynamic monte carlo methods: a mathematical introduction. second edition, Springer-Verlag. Cited by: §1, §1, §1, §2.3.
  • Wolff (1989) U. Wolff Collective monte carlo updating for spin systems. Physical Review Letters 62 (4), pp. 361–364. Cited by: §2.2, §2.