Iterated Conditional Modes (ICM)

TL;DR

• Iteratively updates each variable to the value that maximizes its conditional probability given the current values of the other variables.
• Starts from a random initialization and repeats updates until a local maximum (MAP estimate) is reached.
• Applicable to Markov random fields with arbitrary connectivity; used in tasks such as image segmentation, object detection, and protein folding.

Definition

Iterated conditional modes (ICM) is an algorithm used in probabilistic graphical models, specifically in the context of Markov random fields (MRFs). The goal of the algorithm is to find a local maximum of the probability distribution over the MRF variables, known as the maximum a posteriori (MAP) estimate.

Explanation

ICM begins by initializing each variable in the MRF (for example, to random values). It then cycles through the variables one at a time. For each variable, the algorithm selects the value that maximizes that variable’s conditional probability given the current values of the other variables. This update step is repeated for every variable, and the cycle continues until no further improvements are found and a local maximum is reached.

One key advantage of ICM is that it can handle MRFs with arbitrary connectivity patterns (variables need not be connected in a particular way). This flexibility makes the algorithm useful in a range of applications in computer vision, machine learning, and computational biology.

Examples

Binary MRF example

Suppose we have a MRF with four variables, A, B, C, and D. Each variable can take on either a value of 0 or 1. The ICM algorithm begins by initializing each variable to a random value. When updating variable A, the new value is chosen as:

$$A_{\text{new}} = \arg\max_{A} P(A \mid B, C, D)$$

The same process is repeated for variables B, C, and D. The algorithm cycles through these updates until a local maximum is reached.

Protein folding example

In the context of protein folding, the variables represent different amino acids in a protein, and each variable’s value corresponds to the conformation of that amino acid. ICM can be applied to find the most probable conformations given known interactions between amino acids.

Use cases

• Image segmentation
• Object detection
• Computer vision
• Machine learning
• Computational biology (e.g., protein folding)

Notes or pitfalls

• ICM finds a local maximum of the posterior distribution (MAP estimate); it does not guarantee finding a global maximum.

Related terms

• Markov random fields (MRFs)
• Maximum a posteriori (MAP) estimate
• Probabilistic graphical models