3
$\begingroup$

Ising Model

$$ Pr(x; \lambda) = \frac{1}{Z(\lambda)} \exp \left( \sum_{ij \in E} \lambda_{ij} x_{ij} \right) $$

In which $\lambda_{ij} \in \mathbb{R}$, and
$$ x_{ij} = \begin{cases} 1 & x_i = x_j\\ -1 & x_i \neq x_j \end{cases} $$

and we are looking for

$$ x^* = \arg\max_x Pr(x; \lambda) $$

This is proven to be NP-Complete.

Max Cut

Given the graph $G(V,E)$ and non-negative weights $w_{ij} \in E $ the goal is to find the set of vertices $S$ such that we maximize the the weight of edges in the cut $(S, V \setminus S)$ (the edges with the start-point in $S$ and end-point in $V\setminus S$). More formally, by assuming $w_{ij} = 0, \forall e_{ij} \notin E $, we dote the weight of the cut by $w(S, V \setminus S) = \sum_{i \in S, j \in V \setminus S} w_{i,j}$

This is proven to be NP-Complete.

Min Cut

Exactly like Max-Cut, but the goal is to minimize the weight of the cut.

The problem could be solved in polynomial time using its max-flow formulation.

Problem Statement

In [1] (Page 16, last paragraph) it is mentioned that "finding the most likely assignment in an Ising model is equivalent to a cut problem. For example, if $\mu \leq 0$, then the MAP assignment for graph $G = (V; E)$ corresponds to the maximum cut of $G$ with edge weights $\lambda$."

I am looking for the direct conversion between the two problems. The 2nd sentences (Started by "For example") also doesn't make sense to me.

On the other hand in Page 20 of [1] (Second paragraph), it is mentioned that:

"In the positive side, MAP inference in Ising models with ferromagnetic potentials, or positive edge weights, is equivalent to the minimum cut problem, which can be solved in nearly linear time (Karger, 2000)"

I'd interpret this as, Min Cut (which is Poly-time) is special case of MAP inference. Again, this is a little vague.

[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf

$\endgroup$

migrated from math.stackexchange.com Nov 4 '13 at 9:35

This question came from our site for people studying math at any level and professionals in related fields.

3
$\begingroup$

Finding the most likely assignment in the Ising model is equivalent to maximum cut, so forget about minimum cut for a minute.

In the formulation you give for the Ising model, we are trying to maximize $\sum_{ij\in E}\lambda_{ij}x_{ij}$, where $x_{ij}=1$ if $x_i=x_j$ and $x_{ij}=-1$ otherwise. In maximum cut, we take each edge weight $w$ and try to maximize $\sum_{ij\in E}w_{ij}(-x_{ij})$ -- this is equivalent to maximizing the weight of the cut because the total weight remaining is completely determined by the cut. So we just want to set $w_{ij}=\lambda_{ij}$ to make an equivalent formulation.

For minimum cut, the problem doesn't make any sense unless you have fields in the Ising model, either local or global.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.