MRF optimization via dual decomposition explained

In dual decomposition a problem is broken into smaller subproblems and a solution to the relaxed problem is found. This method can be employed for MRF optimization.^[1] Dual decomposition is applied to markov logic programs as an inference technique.^[2]

Background

Discrete MRF Optimization (inference) is very important in Machine Learning and Computer vision, which is realized on CUDA graphical processing units.^[3] Consider a graph

G = (V,E) with nodes V and Edges E . The goal is to assign a label l _{p} to each p \in V so that the MRF Energy is minimized:

(1)

min \Sigma _{p\in} \theta _{p(l} _{p)} + \Sigma _{pq\in} \theta _{pq} (l _{p)(l} _{q)}

Major MRF Optimization methods are based on Graph cuts or Message passing. They rely on the following integer linear programming formulation

(2)

min _{x} E(\theta, x) = \theta.x = \sum _{p} \theta _{p.x} _{p+\sum} _{pq} \theta _{pq} .x _{pq}

In many applications, the MRF-variables are -variables that satisfy:

x _{p(l)=1} \Leftrightarrow label l is assigned to p , while x _{pq} (l,l ^{\prime)} =1 , labels l,l ^{\prime} are assigned to p,q .

Dual Decomposition

The main idea behind decomposition is surprisingly simple:

1. decompose your original complex problem into smaller solvable subproblems,
2. extract a solution by cleverly combining the solutions from these subproblems.

A sample problem to decompose:

min _{x} \Sigma _{i} f ^{i(x)} where x \in C

In this problem, separately minimizing every single

f ^{i(x)} over x is easy; but minimizing their sum is a complex problem. So the problem needs to get decomposed using auxiliary variables \{x ^{i\}} and the problem will be as follows:min _{\{x ^{i\}} ,x} \Sigma _{i} f ^{i(x} ^{i)} where x ^{i} \in C, x ^{i=x}

Now we can relax the constraints by multipliers

\{ λ ^{i\}} which gives us the following Lagrangian dual function:g(\{ λ ^{i\}) =min} _{\{x ^{i} \in C\} ,x} \Sigma _{i} f ^{i(x} ^{i)} + \Sigma _{i} λ ^{i.(x} ^{i - x) =min} ^{\{x ^{i} \in C\} ,x} \Sigma _{i} [f ^{i(x} ^{i)+λ} ^{i.x} ^{i] - (\Sigma} ^{i} λ ^{i)x}

Now we eliminate

x from the dual function by minimizing over x and dual function becomes:g(\{ λ ^{i\}) =min} _{\{x ^{i} \in C\} }\Sigma_i[f^i(x^i) + \lambda^i.x^i]

We can set up a Lagrangian dual problem:

(3)

max _{\{ λ ^{i\}} \in Λ } g({ λ ^{i}) = \Sigma} _{i} g ^{i(x} ^{i),} The Master problem

(4)

g ^{i(x} ^{i) = min} ^{x ^{i}} f ^{i(x} ^{i)} +λ ^{i.x} ^{i} where x ^{i} \in C The Slave problems

MRF optimization via Dual Decomposition

The original MRF optimization problem is NP-hard and we need to transform it into something easier.

\tau is a set of sub-trees of graph G where its trees cover all nodes and edges of the main graph. And MRFs defined for every tree T in \tau will be smaller. The vector of MRF parameters is \theta ^{T} and the vector of MRF variables is x ^{T} , these two are just smaller in comparison with original MRF vectors \theta, x . For all vectors \theta ^{T} we'll have the following:

(5)

\sum _{T} \theta ^{T =} _{p} \theta _{p,} \sum _{T} \theta ^{T =} _{pq} \theta _{pq} .

Where

\tau(p) and \tau(pq) denote all trees of \tau than contain node p and edge pq respectively. We simply can write:

(6)

E(\theta,x) = \sum _{T} E(\theta ^{T,} x ^{T)}

And our constraints will be:

(7)

x ^{T} \in \chi ^{T,} x ^{T = x} _{|T} ,\forall T \in \tau

Our original MRF problem will become:

(8)

min _{\{x ^{T\}} ,x} \Sigma _{T} E(\theta ^{T,} x ^{T)} where x ^{T} \in \chi ^{T,} \forall T \in \tau and x ^{T} \in x _{|T} , \forall T \in \tau

And we'll have the dual problem we were seeking:

(9)

max _{\{ λ ^{T\}} \in Λ } g(\{ λ ^{T\})=} \sum _{T} g ^{T(λ} ^{T),} The Master problem

where each function

g ^{T(.)} is defined as:

(10)

g ^{T(λ} ^{T) =min} ^{x ^{T}} E(\theta ^{T+} λ ^{T,} x ^{T)} where x ^{T} \in \chi ^{T} The Slave problems

Theoretical Properties

Theorem 1. Lagrangian relaxation (9) is equivalent to the LP relaxation of (2).

min _{\{x ^{T\}} ,x} \{E(x, \theta)|x ^{T} _{p,x} \in CONVEXHULL (\chi ^{T)\}}

Theorem 2. If the sequence of multipliers

\{\alpha _{t\}} satisfies \alpha _{t} \geq 0 , \lim _{t} \alpha _{t} = 0 , \sum ^{inf in} _{t =0} \alpha _{t=infin} then the algorithm converges to the optimal solution of (9).

Theorem 3. The distance of the current solution

\{\theta ^{T\}} to the optimal solution \{\bar \theta ^{T\}} , which decreases at every iteration.

Theorem 4. Any solution obtained by the method satisfies the WTA (weak tree agreement) condition.

Theorem 5. For binary MRFs with sub-modular energies, the method computes a globally optimal solution.

Notes and References

1. MRF Optimization via Dual Decomposition.
2. 10.1109/icdm.2012.96 . 2012 . IEEE . Feng Niu and Ce Zhang and Christopher Re and Jude Shavlik . Scaling Inference for Markov Logic via Dual Decomposition . 2012 IEEE 12th International Conference on Data Mining . 10.1.1.244.8755 .
3. 10.1109/btas.2013.6712721 . 2013 . IEEE . Shervin Rahimzadeh Arashloo and Josef Kittler . Efficient processing of MRFs for unconstrained-pose face recognition . 2013 IEEE Sixth International Conference on Biometrics: Theory, Applications and Systems (BTAS) .