Оптимизация MRF посредством двойной декомпозиции

При двойной декомпозиции проблема разбивается на более мелкие подзадачи и находится решение ослабленной проблемы. Этот метод можно использовать для оптимизации MRF . Двойная декомпозиция применяется к программам марковской логики как метод вывода.

Фон

Дискретная оптимизация MRF (вывод) очень важна в машинном обучении и компьютерном зрении , которая реализуется на графических процессорах CUDA. Рассмотрим график $G=(V,E)$с узлами $V$и края $E$. Цель — присвоить метку $l_{p}$каждому $p\in V$чтобы энергия MRF была минимизирована:

(1) $\min \Sigma _{p\in V}\theta _{p}(l_{p})+\Sigma _{pq\in \varepsilon }\theta _{pq}(l_{p})(l_{q})$

MRF Основные методы оптимизации основаны на разрезах графов или передаче сообщений . Они полагаются на следующую формулировку целочисленного линейного программирования

(2) $\min _{x}E(\theta ,x)=\theta .x=\sum _{p\in V}\theta _{p}.x_{p}+\sum _{pq\in \varepsilon }\theta _{pq}.x_{pq}$

Во многих приложениях переменные MRF представляют собой {0,1}-переменные, которые удовлетворяют: $x_{p}(l)=1$$\Leftrightarrow$этикетка $l$ назначен на $p$, пока $x_{pq}(l,l^{\prime })=1$ , этикетки $l,l^{\prime }$ назначены $p,q$.

Двойное разложение

Основная идея декомпозиции на удивление проста:

1. разложить исходную сложную задачу на более мелкие решаемые подзадачи,
2. Извлеките решение, умело комбинируя решения этих подзадач.

Пример задачи для декомпозиции:

$\min _{x}\Sigma _{i}f^{i}(x)$где $x\in C$

В этой задаче минимизация каждого отдельного $f^{i}(x)$над $x$ это легко; но минимизация их суммы представляет собой сложную задачу. Поэтому проблему необходимо разложить с использованием вспомогательных переменных. $\{x^{i}\}$и проблема будет в следующем:

$\min _{\{x^{i}\},x}\Sigma _{i}f^{i}(x^{i})$где $x^{i}\in C,x^{i}=x$

Теперь мы можем ослабить ограничения с помощью множителей $\{\lambda ^{i}\}$ что дает нам следующую двойственную лагранжеву функцию:

$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$

Теперь мы устраняем $x$ от двойной функции путем минимизации по $x$ и двойная функция становится:

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

Мы можем поставить лагранжеву двойственную задачу:

(3) $\max _{\{\lambda ^{i}\}\in \Lambda }g({\lambda ^{i}})=\Sigma _{i}g^{i}(x^{i}),$ Проблема Мастера

(4) $g^{i}(x^{i})=min_{x^{i}}f^{i}(x^{i})+\lambda ^{i}.x^{i}$где $x^{i}\in C$Проблемы раба

Оптимизация MRF с помощью двойной декомпозиции

Исходная задача оптимизации MRF NP-сложна , и нам нужно преобразовать ее во что-то более простое.

$\tau$представляет собой набор поддеревьев графа $G$где его деревья покрывают все узлы и ребра основного графа. И MRF определены для каждого дерева $T$ в $\tau$будет меньше. Вектор параметров MRF: $\theta ^{T}$а вектор переменных MRF равен $x^{T}$, эти два просто меньше по сравнению с исходными векторами MRF. $\theta ,x$. Для всех векторов $\theta ^{T}$у нас будет следующее:

(5) $\sum _{T\in \tau (p)}\theta _{p}^{T}=\theta _{p},\sum _{T\in \tau (pq)}\theta _{pq}^{T}=\theta _{pq}.$

Где $\tau (p)$и $\tau (pq)$обозначим все деревья $\tau$чем содержать узел $p$и край $pq$соответственно. Мы просто можем написать:

(6) $E(\theta ,x)=\sum _{T\in \tau }E(\theta ^{T},x^{T})$

Нашими ограничениями будут:

(7) $x^{T}\in \chi ^{T},x^{T}=x_{|T},\forall T\in \tau$

Наша первоначальная задача MRF будет такой:

(8) $\min _{\{x^{T}\},x}\Sigma _{T\in \tau }E(\theta ^{T},x^{T})$где $x^{T}\in \chi ^{T},\forall T\in \tau$и $x^{T}\in x_{|T},\forall T\in \tau$

И у нас возникнет двойная проблема, которую мы искали:

(9) $\max _{\{\lambda ^{T}\}\in \Lambda }g(\{\lambda ^{T}\})=\sum _{T\in \tau }g^{T}(\lambda ^{T}),$Проблема Мастера

где каждая функция $g^{T}(.)$определяется как:

(10) $g^{T}(\lambda ^{T})=\min _{x^{T}}E(\theta ^{T}+\lambda ^{T},x^{T})$где $x^{T}\in \chi ^{T}$Проблемы раба

Теоретические свойства

Теорема 1. Лагранжева релаксация (9) эквивалентна ЛП-релаксации (2).

$\min _{\{x^{T}\},x}\{E(x,\theta )|x_{p}^{T}=s_{p},x^{T}\in {\text{CONVEXHULL}}(\chi ^{T})\}$

Теорема 2. Если последовательность множителей $\{\alpha _{t}\}$удовлетворяет $\alpha _{t}\geq 0,\lim _{t\to \infty }\alpha _{t}=0,\sum _{t=0}^{\infty }\alpha _{t}=\infty$то алгоритм сходится к оптимальному решению (9).

Теорема 3. Расстояние текущего решения $\{\theta ^{T}\}$к оптимальному решению $\{{\bar {\theta }}^{T}\}$, который уменьшается на каждой итерации.

Теорема 4. Любое решение, полученное методом, удовлетворяет условию WTA (слабое древовидное согласие).

Теорема 5. Для бинарных МСО с субмодулярными энергиями метод вычисляет глобально оптимальное решение.