MRF optimization via dual decomposition

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.

Background

Discrete MRF Optimization (inference) is very important in Machine Learning and Computer vision. 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 V}\theta _{p}(l_{p})+\Sigma _{pq\in \varepsilon }\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\in V}\theta _{p}.x_{p}+\sum _{pq\in \varepsilon }\theta _{pq}.x_{pq}$

In many applications, the MRF-variables are {0,1}-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 $\{\lambda ^{i}\}$ which gives us the following Lagrangian dual function:

$g(\{\lambda ^{i}\})=\min _{\{x^{i}\in C\},x}\Sigma _{i}f^{i}(x^{i})+\Sigma _{i}\lambda ^{i}.(x^{i}-x)=\min _{\{x^{i}\in C\},x}\Sigma _{i}[f^{i}(x^{i})+\lambda ^{i}.x^{i}]-(\Sigma _{i}\lambda ^{i})x$

Now we eliminate $x$ from the dual function by minimizing over $x$ and dual function becomes:

$g(\{\lambda ^{i}\})=\min _{\{x^{i}\in C\}}\Sigma _{i}[f^{i}(x^{i})+\lambda ^{i}.x^{i}]$

We can setup a Lagrangian dual problem:

(3) $\max _{\{\lambda ^{i}\}\in \Lambda }g({\lambda ^{i}})=\Sigma _{i}g^{i}(x^{i}),$ The Master problem

(4) $g^{i}(x^{i})=min_{x^{i}}f^{i}(x^{i})+\lambda ^{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\in \tau (p)}\theta _{p}^{T}=\theta _{p},\sum _{T\in \tau (pq)}\theta _{pq}^{T}=\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\in \tau }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\in \tau }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 _{\{\lambda ^{T}\}\in \Lambda }g(\{\lambda ^{T}\})=\sum _{T\in \tau }g^{T}(\lambda ^{T}),$The Master problem

where each function $g^{T}(.)$is defined as:

(10) $g^{T}(\lambda ^{T})=\min _{x^{T}}E(\theta ^{T}+\lambda ^{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_{p}^{T}=s_{p},x^{T}\in {\text{CONVEXHULL}}(\chi ^{T})\}$

Theorem 2. If the sequence of multipliers $\{\alpha _{t}\}$satisfies $\alpha _{t}\geq 0,\lim _{t\to \infty }\alpha _{t}=0,\sum _{t=0}^{\infty }\alpha _{t}=\infty$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.