«Субмодулярная релаксация в задаче минимизации энергии марковского случайного поля ...»

1.1. Нотация и постановка задачи В этом разделе даются базовые определения и вводится нотация, используемая в данной работе. За основу взята нотация, использованная в работах [133, 17].

Рассмотрим гиперграф G = (V, C), где V – конечное множество вершин, C – конечное мультимножество гиперрёбер – подмножеств множества вершин V: C 2V.

Пусть каждой вершине гиперграфа i V соответствует переменная xi, принимающая значения из конечного непустого множества меток P. Для любого гиперребра C C символом xC обозначим кортеж переменных, индексы которых принадлежат множеству C: xC = (xi | i C)1, а символом XC – совместное множество значений этих переменных: XC = P, Xi = P. При обозначении кортежа всех переменных из V и множества значений этих переменных индекс V будем опускать: x, X.

Определение 1. Назовём энергией, заданной на гиперграфе G, функционал следующего вида:

Здесь и далее будем считать, что на множестве вершин V задан полный порядок (нумерация 1,..., |V|). При переходе от подмножества C множества V (неупорядоченного набора вершин) к кортежу xC (упорядоченному набору переменных) упорядочивание элементов будем проводить в соответствии с этим порядком.

Здесь функционалы i : P R называются унарными потенциалами, а функционалы C : XC R – потенциалами, заданными на гиперрёбрах.

Для каждой переменной i V множество C(i) C содержит гиперрёбра, инцидентные переменой i: C(i) = {C | C C, i C}.

Порядком потенциала C называется количество вершин, входящее в множество C. Порядок унарных потенциалов равен 1. Потенциалы порядка 2 назовём парными, потенциалы больших порядков – потенциалами высоких порядков. Потенциалы, для которых мощности гиперребер равны общему количеству переменных |V|, назовём глобальными. Для обозначения значений унарных потенциалов будем использовать символы ixi = i (xi ) = {i} (x{i} ), парных – ij,xixj = ij (xi, xj ) = {i,j} (x{i,j} ), потенциалов произвольных порядков – C,xC = C (xC ).

Энергии, состоящие только из унарных и парных потенциалов, назовём парносепарабельными. Парно-сепарабельные энергии будем записывать следующим способом:

Здесь E – множество рёбер (гиперрёбер мощности 2). В этой нотации множество гиперрёбер C состоит из гиперрёбер порядка 2: C = {{i, j} | {i, j} E}. Множество вершин V и множество рёбер E образуют граф (V, E), поэтому часто говорят, что парно-сепарабельная энергия задается графом.

Данная работа посвящена задаче минимизации энергии E(x) (1.1) по дискретным переменным x:

Задача (1.3) является задачей дискретной оптимизации. Известно, что для произвольного гиперграфа G и произвольных потенциалов задача (1.3) является NP-трудной [113, 24]. Данная работа посвящена разработке приближённых методов решения данной задачи. Раздел 1.3.1 содержит описание частных случаев, когда задача (1.3) может быть решена точно, а раздел 1.3.2 посвящён приближённым методам решения задачи (1.3), имеющим наиболее близкое отношение к данной работе.

В дальнейшем изложении, для удобства, будем использовать индикаторную нотацию. Для каждой метки p P и переменной xi, i V введем индикатор – бинарную переменную yip := [xi = p]2. Энергия (1.1) в индикаторной нотации выглядит следующим образом:

Здесь и далее символы [A], где A – логическое выражение, соответствуют скобке Айверсона: [A] := 1, если A истинно; [A] := 0, если A ложно.

Здесь символы di, где i V, обозначают ту метку из кортежа меток d, которая соответствует переменной xi из исходного множества переменных (существует и единственна, когда i C).

Очевидно, что задача безусловной оптимизации (1.3) эквивалентна задаче условной оптимизации, записанной в терминах индикаторных переменных:

Ограничения (1.6), (1.7) гарантируют, что каждой переменной xi исходного набора переменных, ставится в соответствие вектор из |P| 1 нуля и ровно одной единицы, по которому исходную метку из множества P можно однозначно восстановить. Ограничения (1.6) будем называть целочисленностью, а ограничения (1.7) – целостностью.

В данной работе задачи условной оптимизации вида (1.5)-(1.7) будет удобно записывать следующим образом: miny(1.6),(1.7) EI (y).

1.2. Энергии и марковские случайные поля Энергия, заданная на гиперграфе G (1.1), имеет непосредственное отношение к марковским случайным полям (Markov random fields, MRF) и часто называется энергией MRF.

Действительно, рассмотрим распределение Гиббса над множеством X, где вероятность конфигурации x определяется следующим образов:

Здесь T > 0 – параметр распределения, называемый температурой. Z – нормировочная конexp T E(x).

станта, равная xX Говорят, что данное распределение задаёт Марковское случайное поле (вероятностную графическую модель), которая факторизуется согласно гиперграфу G:

Здесь i и C – факторы MRF, равные exp(i (xi )/T ) и exp(C (xC )/T ), соответственно.

Задача минимизации энергии (1.1) эквивалентна задаче поиска наиболее вероятного состояния MRF, а при наличии наблюдаемых переменных (Conditional Random Field, CRF) [81] – задаче поиска максимума апостериорного распределения (maximum a posteriori probability estimate, MAP).

1.3. Методы минимизации энергии В этом разделе приводится обзор существующих методов решения задачи минимизации энергии (1.3).

В общем виде задача является NP-трудной [113, 24], а значит решить её в общем случае за полиномиальное время не представляется возможным3. Тем не менее, существует ряд частных случаев, когда задача полиномиально разрешима:

• граф (фактор-граф, см. опр. 2, для энергии с потенциалами высоких порядков) не содержит циклов [99, 20];

• энергия является парно-сепарабельной и субмодулярной [44, 68, 30];

• энергия представляет собой парно-сепарабельную модель Изинга, а граф планарен [109];

• граф энергии имеет небольшую ширину [82, 129].

В разделе 1.3.1 приведены описания первых двух случаев, как наиболее известных и имеющих наибольшее отношение к настоящей работе.

Для ситуаций, когда задача минимизации энергии является NP-трудной, существует целый ряд приближённых методов. Можно выделить несколько основных групп приближённых методов:

• алгоритмы, делающие шаги (метод покоординатного спуска (ICM) [19], алгоритмы, основанные на разрезах графов [24, 87]);

• релаксационные алгоритмы (методы покоординатного подъёма [8, 5, 132, 42, 117], алгоритмы, основанные на декомпозиции [130, 65, 73]);

• алгоритмы передачи сообщений (LBP [138], TRW [130]);

• стохастические методы (имитация отжига [41], методы сэмплирования [20]);

• комбинаторные алгоритмы (метод ветвей и границ [118, 55]).

В разделе 1.3.2 приведены описания нескольких методов, имеющих наиболее близкое отношение к теме настоящей работы.

Существует несколько работ по сравнению методов различных видов на широком спектре энергий, возникающих в прикладных задачах [120, 54].

Также существует большое количество методов, разработанных для потенциалов специальных видов (часто специфичных конкретным прикладным задачам): потенциалы, обеспечивающие ограничения на глобальные статистики разметок [135, 76, 32, 80, 91], связность [93] и Если только P не равно NP.

априорные распределения на форму объекта [39, 125, 86, 89] в задаче сегментации изображений, и др.

1.3.1. Частные случаи, допускающие точные решения Как уже было сказано выше, задача минимизации энергии (1.1) в общем виде является NP-трудной. Тем не менее, существует несколько важных частных случаев, когда задачу можно решить точно за полиномиальное время. Выделим два способа ограничить количество степеней свободы задачи: ограничения на структуру гиперграфа при произвольных потенциалах, ограничения на вид потенциалов при произвольной структуре гиперграфа.

1.3.1.1. Ограничения на структуру гиперграфа 1.3.1.1.1. Парно-сепарабельная энергия с графом без циклов. Рассмотрим задачу минимизации парно-сепарабельной энергии (1.2), заданной на графе G = (V, E). Пусть граф G не содержит циклов и состоит из одной компоненты связности (является деревом).

Назовём сообщением от вершины i к вершине j следующий вектор:

Сообщение от вершины i к вершине j рекуррентно зависит от сообщений из всех соседей вершины i, кроме j, в вершину i.

Алгоритм передачи сообщений выбирает некоторое начальное приближение значений сообщений, после чего пересчитывает их в некотором порядке, называемом расписанием, до сходимости. Покажем, при каком расписании алгоритм передачи сообщений точно решает задачу минимизации энергии (1.2), заданной на ациклическом графе.

Без ограничения общности предположим, что граф связный. Выделим произвольную вершину графа и назовём её корнем. Пронумеруем все вершины графа G, кроме, в таком порядке, что для дерева обхода графа G в глубину, начиная с вершины, все потомки стоят раньше родителей.

Будем передавать сообщения от вершины к её родителю (согласно дереву обхода в глубину) в соответствии с введённой нумерацией. При этом либо в выражении (1.8) в сумме не будет элементов (если текущая вершина является листом), либо все слагаемые суммы уже будут вычислены. Всего нужно вычислить |V| 1 сообщение. Данное расписание проиллюстрировано на рис. 1.1.

При таком расписании переданное сообщение от вершины i к вершине j соответствует минимальной энергии поддерева, «висящего» на ребре {i, j} со стороны i, если переменная xj принимает фиксированное значение. Минимум всей энергии, при этом, может быть вычислен при помощи суммирования всех сообщений, входящих в корень, и унарного потенциала корня:

Конфигурация, на которой достигается минимум энергии, может быть найдена при помощи рекуррентного взятия аргминимума в формулах (1.9) и (1.8).

Описанный выше алгоритм является прямым обобщением алгоритма динамического программирования для случая, если граф G имеет вид цепочки. Примером моделей-цепочек являются скрытые марковские модели (hidden Markov models, HMM). При работе с HMM алгоритм динамического программирования обычно называют алгоритмом Витерби [20].

Отметим, что сложность алгоритма передачи сообщений при вычислении по формулам (1.8) напрямую составляет O(|V||P|2), что может быть достаточно медленно при большом количестве меток (например, в задаче обнаружении человека на изображении количество меток равно количеству возможных позиций каждой части тела [37]). Тем не менее, оказывается, что для ряда типов парных потенциалов выражение (1.8) можно вычислять за линейное по числу меток время. Например, если парные потенциалы являются потенциалами Поттса (ij (xi, xj ) = cij [xi = xj ], cij R), то сообщения можно вычислить следующим образом:

где ij (xi ) = i (xi ) + µki (xi ). Такие вычисления требуют уже O(|V||P|) операций. В работах [35, 36] предложен способ быстрых вычислений сообщений потенциалов более общего вида, основанных на быстром вычислении преобразований расстояний (distance transforms).

1.3.1.1.2. Обобщения на случай потенциалов высоких порядков. Алгоритм передачи сообщений несложно обобщить на случай энергий с потенциалами высоких порядков. Для этого будем использовать понятие фактор-графа.

Определение 2. Фактор-графом, соответствующим энергии (1.1), заданной на гиперграфе G = (V, C), назовём граф G = (V, E), в котором вершины V соответствуют как вершинам, так и факторам (слагаемым в выражении для энергии) исходного гиперграфа G, а рёбра соединяют вершины фактора C и переменной xi, только когда фактор C зависит от переменной i: i C.

Рисунок 1.1.: Расписание алгоритма передачи сообщений, позволяющее точно решить задачу минимизации парно-сепарабельной энергии, заданной на ацикличном графе из 8 вершин. Вершина выделена и является корнем дерева обхода в глубину. Стрелки вдоль рёбер показывают направления сообщений, задействованных при вычислении минимума энергии с данным корнем. Цифры возле стрелок показывают одну из возможных последовательностей передач сообщений, позволяющую точно решить задачу.

Граф, определённый таким образом, является двудольным (рёбра соединяют только вершины-факторы с вершинами-перемеными). Вершины фактор-графа, соответствующие переменным, будем индексировать при помощи индексов исходных переменных i V; вершины фактор-графа, соответствующие переменным, – при помощи гиперрёбер C C.

Стоит отметить, что по энергии, записанной формулой (1.1), фактор-граф строится неоднозначно, поскольку слагаемые можно разными способами объединять в факторы, и, более того, можно объединять несколько переменных в одну. Рис. 1.2 показывает примеры фактор-графов, построенных для одной энергии разными способами. Здесь и далее будем считать, что все преобразования с энергией проведены до формирования гиперграфа G, а фактор-граф G построен «естественным образом», описанным выше.

Определим сообщения для фактор-графов. Выделим сообщения двух видов: от факторов к вершинам (1.10) и от вершин к факторам (1.11).

Аналогично случаю парно-сепарабельного графа, алгоритм передачи сообщений, начиная с некоторой инициализации, пересчитывает сообщения по формулам (1.10) и (1.11) в соответствии с некоторым порядком - расписанием.

Если фактор-граф не содержит циклов, то легко показать, что существует расписание, позволяющее точно решить задачу минимизации энергии. Такое расписание строится аналогично расписанию для случая парно-сепарабельных графов, а именно как передача сообщений от листьев к корню согласно дереву поиска в глубину, построенному от некоторой выделенной вершины. Пример одного из таких расписаний приведен на рис. 1.3. После того, как все необходимые Рисунок 1.2.: Фактор-графы, построенные для энергии, заданной на графе (a). (b) соответствует фактор графу, построенному «естественным способом». Данный фактор-граф содержит циклы. (c) соответствует фактор-графу той же энергии, но построенному при помощи другой группировки слагаемых по факторам.

Данный фактор-граф не содержит циклов, но, при такой группировке, фактически, произошёл отказ от факторизации модели. (d) содержит фактор-граф, построенный при помощи объединения нескольких переменных в одну. Данный фактор-граф одновременно не содержит циклов и содержит информацию (хотя и не всю) о факторизации.

сообщения вычислены минимум энергии может быть вычислен аналогично (1.9):

Нетрудно видеть, что сложность алгоритма передачи сообщений линейна по количеству вершин и факторов, но экспоненциальна (формула (1.10)) по размеру факторов. Аналогично случаю парно-сепарабельных энергий для факторов некоторых специальных видов сообщения можно вычислять существенно быстрее. Примерами таких ситуаций являются энергии с глобальными потенциалами специальных видов [121], а также алгоритм кластеризации «распространение близости» (affinity propagation) [40].

1.3.1.2. Ограничения на вид потенциалов 1.3.1.2.1. Парно-сепарабельная субмодулярная энергия с бинарными переменными.

Рассмотрим задачу минимизации парно-сепарабельной энергии (1.2), заданной на произвольном графе G = (V, E). Пусть все переменные бинарны: P = {0, 1}. Функции, отображающие булев куб на множество действительных чисел, часто называют псевдо-булевыми. Известно, что если не вводить никаких дополнительных ограничений, то задача минимизации парно-сепарабельной псевдо-булевой функции является NP-трудной [68]. Однако, если все парные потенциалы такой функции удовлетворяют условию субмодулярности, то задачу можно решить за полиномиальное время при помощи сведения к задачам построения максимального потока и минимального Рисунок 1.3.: Обобщение алгоритма передачи сообщений на случай энергии с потенциалами высоких порядков на примере энергии из 7 вершин и 4-х факторов. (a) – структура факторов энергии; области показывают вершины, объединённые факторами. (b) – ацикличный фактор-граф, построенный для данной энергии. (c) – расписание алгоритма передачи сообщений; стрелки вдоль рёбер показывают направления сообщений, задействованных при вычислении минимума энергии при выделенном корне. Цифры возле стрелок показывают одну из возможных последовательностей передач сообщений, позволяющую точно решить задачу.

разреза в графе. Данный результат был известен ещё в середине 60-х годов [46, 22], но был переоткрыт в начале нулевых В. Колмогоровым и др. [68]. С тех пор алгоритмы минимизации энергии, основанные на использовании алгоритмов построения разрезов графов (graph cuts) активно используются в задачах компьютерного зрения и машинного обучения.

Определение субмодулярности. Рассмотрим одно из центральных понятий теории псевдобулевых функций – субмодулярность.

Определение 3. Функция бинарных переменных E(x) называется субмодулярной, если для любых двух разметок x1 и x2 выполнено условие где операции «» и «» – поэлементная дизъюнкция (максимум) и конъюнкция (минимум), соответственно4.

Часто определение субмодулярности формулируется для функций, определённых на всех подмножествах множества переменных V: g : 2V R. Условие (1.13) в этом случае записывается следующим образом:

где A, B 2V. Если каждому подмножеству V взаимнооднозначно поставить в соответствие вектор индикаторных переменных длины |V|, то условия (1.14) и (1.13) определяют эквивалентные классы функций.

Утверждение 1. Парно-сепарабельная функция бинарных переменных E(x) является субмодулярной, тогда и только тогда, когда для каждого парного потенциала выполнено следующее условие:

Доказательство. Достаточность следует из того, что в случае функции двух переменных условия (1.15) и (1.13) совпадают, а также того, что сумма субмодулярных является субмодулярной.

Для доказательства необходимости можно рассмотреть в качестве x1 и x2 вектора, совпадающие во всех компонентах, кроме i и j, и содержащие значения 0 и 1 на i-й и j-й позициях в разном порядке.

Часто, если речь идет о парно-сепарабельных функциях, именно условие (1.15) используют в качестве определения субмодулярности.

Соответствие минимизации энергии разрезу графа. Рассмотрим парно-сепарабельную энергию бинарных переменных, в которой потенциалы удовлетворяют следующим ограничениям:

• парные потенциалы неотрицательны и равны 0 при равенстве связанных переменных:

В этом случае энергию можно записать в следующем виде:

E(x) = По энергии (1.16) построим ориентированный граф G = (V, E), st-разрез которого будет соответствовать присвоению значений переменным x • Множество вершин V = V {s, t}, где s и t – две дополнительные вершины: исток и • Множество дуг E строится следующим образом: каждому ребру {i, j} E ставим в соответствие две дуги (i, j) и (j, i) (нетерминальные дуги), каждой вершине i V ставим в соответствие дуги (s, i) и (i, t) (терминальные дуги).

• st-разрезом графа будем считать разбиение всех вершин множества V на два непересекающихся множества S и T, S T =, S T = V, такое что s S и t T. Будем считать, что множество истока S соответствует значению переменных 0, а множество Основные определения и факты, связанные с разрезами графов и потоками в сетях, даны в дополнении A.

Рисунок 1.4.: Граф, построенный для минимизации энергии от двух переменных xi, xj. Разрез, отображенный пунктирной линией, соответствует присваиванию xi = 1, xj = 0. Величина разреза составляет i (1) + j (0) + ij (1, 0).

• Веса терминальных дуг: c(s, i) = i (1), c(i, t) = i (0), где i V.

• Веса нетерминальных дуг: c(i, j) = ij (0, 1), c(j, i) = ij (1, 0), где {i, j} E, и, по • Присваивание значений переменных по построенному st-разрезу строится следующим образом: i S xi = 0, i T xi = 1. Величина разреза совпадает со значением энергии (1.16) при таких значениях переменных x. Таким образом, задача минимизации энергии вида (1.16) эквивалента задаче поиска минимального st-разреза в графе G.

Пример графа, построенного для энергии, зависящей от 2-х переменных, и его разреза приведен на рис. 1.4.

Репараметризация. Рассмотрим, какие ещё энергии (кроме (1.16)) можно минимизировать при помощи разрезов графов.

На энергию E(x) можно смотреть как на функцию. У одной и той же функции может быть несколько различных записей вида (1.2). Назовем преобразование записи энергии E(x), не меняющее энергию, как функцию, репараметризацией. Рассмотрим несколько видов репараметризаций:

• Вычитание константы из унарного потенциала: i (0) := i (0), i (1) := i (1), • Изменение парных потенциалов: ij (p, 0) := ij (p, 0), ij (p, 1) := ij (p, 1), i (p) := Легко показать, что описанные преобразования не меняют энергию E(x) как функцию.

Рассмотрим, какие парно-сепарабельные энергии общего вида (1.2) при помощи описанных преобразований-репараметризаций можно свести к виду (1.16). Заметим, что применяя репараметризацию унарных потенциалов c = min(i (0), i (1)) унарные потенциалы всегда можно сделать неотрицательными. Таким образом, можно снять все ограничения на унарные потенциалы энергии (1.16).

Рассмотрим, что можно сделать при помощи репараметризаций парных потенциалов.

Пусть потенциал ребра {i, j} E принимает следующие значения: ij (0, 0) = a, ij (1, 1) = b, ij (0, 1) = c, ij (1, 0) = d. Применим следующую последовательность преобразований:

Можно убедиться, что данные преобразования приводят к следующим значениям парного потенциала ij : ij (0, 0) = ij (1, 1) = ij (0, 1) = 0, ij (1, 0) = d+cab. Если после этого при помощи описанных ранее действий сделать все унарные потенциалы неотрицательными, то энергия будет иметь вид (1.16), тогда и только тогда, когда выполнено условие d+cab 0. Заметим, что это условие в точности соответствует условию субмодулярности парно-сепарабельной энергии бинарных переменных (1.15). Данное условие вызвано тем, что для полиномиальной разрешимости задач о максимальном потоке и минимальном разрезе пропускные способности дуг графа должны быть неотрицательны.

1.3.1.2.2. Обобщение на случай |P|-значных переменных. Рассмотрим задачу минимизации парно-сепарабельной энергии (1.2), заданной на произвольном графе G = (V, E). Пусть все переменные принимают одно из K значений: P = {0,..., K 1}. Если на множестве меток определён полный порядок и все парные потенциалы являются субмодулярными (обобщение понятия на K-значный случай), то задачу можно решить за полиномиальное время при помощи алгоритмов построения минимального разреза графа. Первой работой в данном направлении была работа Ишикавы [50]; Дарбон расширил применимость метода и сформулировал его в текущем виде [30].

Определение понятия субмодулярности для небинарных переменных аналогично бинарному случаю (опр. 3):

Определение 4. Функция K-значных переменных E(x) называется субмодулярной, если для любых двух разметок x1 и x2 выполнено условие где операции «» и «» – поэлементный максимум и минимум, соответственно. Подразумевается, что эти две операции определены для любых значений переменных, что соответствует введению на множестве полного порядка.

Критерием субмодулярности парно-сепарабельных энергий является субмодулярность всех парных потенциалов (аналогично бинарному случаю, утв. 1).

Введём индикаторные переменные [x]ip, i V, p P, соответствующие линиям уровня Унарные и парные потенциалы исходной энергии можно выразить через введённые переменные [30]. Унарные потенциалы выражаются следующим образом:

где Di (p) = i,p+1 i,p, p {0,... K 2}. Парные потенциалы можно выразить так:

Здесь Выражения (1.19) и (1.20) позволяют переписать энергию (1.2) через парно-сепарабельную функцию бинарных переменных [x]ip. Условие того, что переменные [x]ip являются линиями уровня какой-либо разметки переменной xi (в смысле определения (1.18)), можно записать как парные потенциалы энергии:

Здесь M – достаточно большое положительное число [30].

Заметим, что все парные потенциалы, появляющиеся в выражениях (1.19), (1.20), (1.21) являются субмодулярными6, а значит, согласно критерию субмодулярности парно-сепарабельной функции (утв. 1) полученное выражение является субмодулярным. Таким образом, в данном случае можно применить метод минимизации субмодулярных парно-сепарабельных псевдо-булевых функций, описанный в разделе 1.3.1.2.1.

Потенциалы (1.21) субмодулярны, поскольку M > 0. Потенциалы (1.20) субмодулярны, поскольку Rij (p, q) 0, что следует из опр. 1.3.1.2.3. Потенциалы высоких порядков. Рассмотрим задачу минимизации энергии с потенциалами высоких порядков (1.1), где все переменные являются бинарными. Известно, что субмодулярные (опр. 3) энергии высоких порядков могут быть точно минимизированы за полиномиальное время. Тем не менее, все известные алгоритмы обладают высокой сложностью, что делает их малоприменимыми на практике (например, алгоритм [51] обладает сложностью O(|V|5)). Для потенциалов небольших порядков более близкими к практичным оказываются алгоритмы, обладающие не строго полиномиальной сложностью. Например, алгоритм [14], обладающий сложностью O(|V|3 2M ), где M = maxCC |C|.

Из-за высокой сложности общих алгоритмов на практике часто используются специализированные алгоритмы, применимые лишь к потенциалам определённых видов. Наиболее популярным способом минимизации энергий вида (1.1) является сведение их к парно-сепарабельным энергиям, а именно добавление в энергию новых переменных z, так что где E – парно-сепарабельная субмодулярная функция.

Наиболее популярным (и хронологически первым [38]) примером такой редукции является тождество На каждое слагаемое энергии, при котором стоит неположительный коэффициент, вводится дополнительная переменная z, так чтобы относительно переменных x и z функция была парносепарабельной и субмодулярной. При этом, минимум энергии E по расширенному множеству переменных (x и z) совпадает с минимумом энергии E по переменным x. Подробнее о сведении энергий высоких порядков к парно-сепарабельным написано в работе [49].

1.3.2. Приближённые алгоритмы 1.3.2.1. Шагающие алгоритмы Шагающие алгоритмы (move-making algorithms) – это приближённые методы минимизации энергии, которые, начиная с некоторого начального приближения, итеративно переходят от одной разметки к другой. На каждой итерации рассматривается некоторое множество разметок, в которые можно перейти (совершить шаг), и выбирается разметка из данного множества, на которой энергия принимает минимальное (по текущему множеству) значение. Алгоритм останавливается, когда не может выполнить шаг, приводящий к уменьшению энергии. Интуитивноочевидно, что алгоритм тем лучше, чем большее количество разметок покрывается на каждом шаге. Современные алгоритмы данного класса, такие как -расширение и -замена [24], на каждой итерации выбирают шаг из экспоненциально большого количества возможных шагов и для многих реальных задач являются наиболее быстрыми [120]. Существуют алгоритмы, использующие и другие виды шагов: алгоритм range-moves [126] на каждом шаге минимизирует субмодулярные энергии от небинарных переменных, алгоритм fusion moves [87] использует приближённые алгоритмы минимизации бинарных несубмодулярных энергий. Недостатком алгоритмов данного класса является отсутствие гарантий оптимальности, а также ограниченная область применимости методов, позволяющих делать большие шаги.

Алгоритм ICM. Наиболее простым и хронологически первым шагающим методом является алгоритм ICM (Iterated Conditional Models) [19]. Шаги алгоритма ICM заключаются в выборе подмножетсва переменных A V, фиксации всех переменных, не входящих в множество A, и полному перебору по всем разметкам переменных, входящих в множество A. Сложность одного шага данного алгоритма экспоненциально мощности множества A, что делает алгоритм ICM неприменимым при больших A. Тем не менее, данный алгоритм применим для произвольных энергий и часто применяется, чтобы немного уточнить окончательное решение (например, в работе [111]), или в качестве эвристики, позволяющей получить прямое решение при решении двойственной задачи (например, в работе [96]).

Алгоритмы на основе разрезов графов. В 2001 г. Бойков и др. [24] предложили два шагающих алгоритма, основанных на итеративном применении алгоритма построения минимального разреза графа:

-расширение и -замена. Каждый шаг обоих алгоритмов представляет собой задачу минимизации субмодулярной энергии бинарных переменных. В алгоритме -расширение на каждом шаге каждая переменная из xi, i V может либо получить выбранное значение P, либо сохранить текущее значение. В алгоритме -замена на каждом шаге все переменные, которым присвоены метки, P, могут получить значения или. Примеры шагов обоих алгоритмов приведены на рис. 1.5. Количество возможных шагов на каждой итерации обоих алгоритмов экспоненциально по количеству пикселей.

Приведем формальное описание каждого шага алгоритма -расширение. Рассмотрим парно-сепарабельную энергию (1.2), заданную на графе G = (V, E). Пусть есть текущая разметка x0 и выбрана «расширяемая» метка P. Обозначим новую |P|-значную разметку x.

Построим парно-сепарабельную энергию бинарных переменных Рисунок 1.5.: Шаги алгоритмов -расширение (a) и -замена (b).

по энергии (1.2) следующим образом:

• Граф энергий EB (y) и E(x) одинаков: VB = V, EB = E.

• Значение бинарной переменной yi = 0 соответствует x = x0 (значение переменной xi не меняется); yi = 1 соответствует x =.

• Унарные потенциалы: i (0) = i (x0 ), i (1) = i ().

• Парные потенциалы: ij (0, 0) = ij (x0, x0 ), ij (1, 1) = ij (, ), ij (0, 1) = ij (yi, ), Условием применимости алгоритма разреза графа является условие субмодулярности парных потенциалов (1.15). В терминах |P|-значных переменных условие выглядит следующим образом:

где,, P. Часто предполагают, что ij (, ) = 0 и ij (, ) = ij (, ). В этом случае условие (1.22) становится неравенством треугольника, а все парные потенциалы ij – метриками.

Алгоритм -расширение может быть существенно ускорен либо при помощи использования динамических разрезов графов [11], либо рассмотрения одновременно прямых и двойственных задач линейного программирования [72]. Алгоритм -расширение может быть «совмещен»

с алгоритмом -замена для дальнейшего улучшения качества [108].

Алгоритм -расширение можно обобщить и на случай потенциалов высоких порядков некоторых специальных видов: потенциалы Поттса высокого порядка (P n -Potts) [60] и их робастный вариант [61], потенциалы, штрафующие использование большого числа меток в решении [32], а также использующие информацию о частоте одновременного появления меток разных классов [80].

Современные работы по сравнению разных методов минимизации энергии [120, 54] показывают, что шагающие алгоритмы, основанные на разрезах графов, работают очень быстро, когда применимы.

1.3.2.2. Релаксационные алгоритмы Одним из популярных подходов к решению задачи минимизации энергии (1.3) является релаксация. Данный подход заключается в формулировании задачи, как целочисленного программирования, после чего ограничения целочисленности отбрасываются, и решается непрерывная задача оптимизации.

Особенностью релаксационных методов является возможность предоставления так называемого сертификата оптимальности: если по решению непрерывной задачи удаётся построить решение дискретной задачи с таким же значением функционала, то построенное дискретное решение является глобально оптимальным. При решении непрерывных задач часто переходят к двойственным им. При таком переходе каждое значение двойственной функции является нижней оценкой на глобальный минимум, что, в свою очередь, позволяет говорить о построении наиболее точной нижней оценки среди определённого семейства оценок. Необходимым условием предоставления сертификата оптимальности является равенство нулю зазора7 между предъявленным решением прямой дискретной задачей и наилучшей нижней оценкой на её глобальный минимум.

1.3.2.2.1. Линейная релаксация. Наиболее распространённой релаксацией является линейная релаксация, предложенная в 70-х годах М. И. Шлезингером [8], и позднее переоткрытая другими авторами [27, 130].

Рассмотрим задачу минимизации парно-сепарабельной энергии (1.2). Переформулируем её в виде эквивалентной задачи целочисленного линейного программирования (ЦЛП) c целевой функцией:

Разность между значением глобального минимума непрерывной прямой задачи и значением глобального максимума двойственной задачи называется зазором двойственности (duality gap). Если непрерывная прямая задача является выпуклой, то обычно зазор двойственности равен 0 (в силу применимости выпуклого варианта теоремы Каруша-Куна-Таккера). Зазором целочисленности обычно называют разность между значением глобального минимума дискретной задачи и значением глобального минимума прямой непрерывной задачи. При решении прикладных задач особый интерес представляет сумма зазоров целочисленности и двойственности. Будем назвать эту величину просто зазором.

и множеством ограничений Ограничения (1.27) и (1.24) аналогично ограничениям (1.6) и (1.7) обеспечивают целочисленность и целостность (возможность единственным образом восстановить значения переменных x исходной задачи). Ограничения (1.25) и (1.26) обеспечивают согласованность унарных переменных yip и парных переменных yij,pq.

Уэйнрайт и др. [130] показали, что значение глобального минимума дискретной задачи (1.23)-(1.27) равно значению минимума линейного функционала (1.23) на некотором выпуклом многограннике, называемом маргинальным многогранником (marginal polytope). Охарактеризовать его полностью достаточно сложно, поскольку он имеет экспоненциальное количество граней. Одним из многогранников, содержащим в себе все целочисленные решения задачи (1.23)-(1.27), является многогранник, получаемый заменой ограничения целочисленности (1.27) на неотрицательность переменных yij,pq и yip. Такой многогранник часто называют локальным маргинальным многогранником (local marginal polytope). Маргинальный и локальный маргинальный многогранники для энергий, определённых на графе G, будет обозначать Marginal(G) и Local(G), соответственно.

Определение 5. Стандартной линейной релаксацией задачи минимизации дискретной парносепарабельной энергии (1.2) назовём задачу минимизации линейного функционала (1.23) по переменным yip, yij,pq, принимающим действительные неотрицательные значения, при ограничениях (1.24), (1.25), и (1.26).

В некоторых ситуациях зазор между решением дискретной задачи (1.23)-(1.27) и её стандартной релаксацией может быть достаточно большим. В последние годы был разработан целый ряд методов уточнения стандартной релаксации, так или иначе основанных на добавлении дополнительных линейных ограничений: [133, 70, 116, 17]. Тем не менее, во многих практически важных случаях зазор либо отсутствует, либо мал, что делает стандартную линейную релаксацию популярным инструментом при решении прикладных задач. Можно показать, что для ряда важных частных случаев стандартная линейная релаксация является точной.

Утверждение 2. Если граф G, на котором задана парно-сепарабельная энергия E(x), не содержит циклов, то значение глобального минимума энергии E(x) в точности совпадает со значением минимума стандартной линейной релаксации задачи минимизации энергии E(x).

Утверждение 3. Если парно-сепарабельная энергия бинарных переменных E(x), заданная на произвольном графе G, субмодулярна, то значение глобального минимума энергии E(x) в точности совпадает со значением минимума стандартной линейной релаксации задачи минимизации энергии E(x).

Доказательства утв. 2 и 3 представлены в работах [129] и [67], соответственно.

Стандартная линейная релаксация описывается полиномиальным множеством ограничений. Тем не менее, во многих реальных ситуациях в возникающей задаче линейного программирования очень много переменных, что делает невозможным применение существующих методов общего назначения (например, симплекс-метода). Существует целый ряд специализированных методов для решения именно такой задачи линейного программирования. Большинство методов строят двойственную задачу тем или иным способом, после чего решается оптимизационная задача в пространстве двойственных переменных. Все такие методы можно разделить на два класса:

• двойственная задача выписывается в явном виде;

decompostion), что не позволяет выписать её в явном виде.

Явный вид двойственной задачи. Построим двойственную задачу в явном виде, предложенном М. И. Шлезингером [8, 132]. Рассмотрим задачу минимизации парно-сепарабельной энергии (1.2). Добавим и вычтем новые слагаемые следующим образом:

Здесь mji (xi ) – добавленные слагаемые, которые часто в силу сходства с µij (xj ) (1.8) называют сообщениями. Группируя слагаемые согласно выражению (1.28), получим следующую нижнюю оценку на энергию E(x):

Задачу максимизации двойственной функции (1.29) можно переписать в виде задачи линейного программирования, двойственной к стандартной линейной релаксации исходной задачи:

Запись двойственной задачи оптимизации в явном виде позволяет получать схемы блочнокоординатной оптимизации, гарантирующие монотонное неубывание нижней оценки на каждом шаге. Алгоритмами данного класса являются алгоритмы MSD [8, 5, 132], а также различные варианты алгоритма MPLP [42, 117].

Общим инструментом выписывания двойственных задач в явном виде является двойственность по Фенхелю. Зак и др. [139] используют двойственность по Фенхелю для построения двойственных функций, которые можно сглаживать, что, в свою очередь, позволяет применять гладкие методы оптимизации для решения двойственных задач. Похожая идея была применена Савчинским и др. [106] для ситуации, когда двойственную функцию в явном виде выписать не удаётся.

Парно-сепарабельные бинарные энергии. Особняком стоит ситуация стандартной линейной релаксации для случая парно-сепарабельных энергий бинарных переменных (в том числе, несубмодулярных). В этом случае стандартную линейную релаксации можно эффективно найти при помощи построения разреза специального графа. В литературе эта техника обычно называется алгоритмом QPBO.

Для каждой переменной xi {0, 1}, i V введём дополнительную переменную xi = 1xi.

Использую новые переменные, исходную энергию можно записать как субмодулярную функцию8. Если после этого отбросить ограничения xi + xi = 1, i V, то записанную функцию можно будет эффективно минимизировать при помощи построения разреза графа (см. раздел 1.3.1.2).

Можно доказать несколько свойств такой релаксации:

• величина минимального разреза построенного графа равна значению минимума стандартной линейной релаксации (лемма 1 и теоремы 6 и 10 из работы [22]);

Пусть, без ограничения общности, все значения и унарных, и парных потенциалов неотрицательны. Тогда унарные потенциалы можно записать, например, так: i (xi ) = i (0)i + i (1)xi. Парные так: ij (xi, xj ) = ij (0, 0)(1 xi )j + ij (0, 1)(1 xi )xj + ij (1, 0)xi (1 xj ) + ij (1, 1)xi (1 xj ). При такой записи всех потенx циалов энергия, как функция расширенного множества переменных, будет субмодулярна.

• если для некоторого множества вершин W V для разметки, построенной по разрезу графа, выполнено условие xi + xi = 1, то существует оптимальная разметка x исходной энергии, в которой x = xi, i W (частичная оптимальность) [66, 47];

• если для произвольной разметки исходных переменных x положить xi = xi, i W, и xi = xi, i W, то энергия при этом не увеличится E(x) Обычно говорят, что алгоритм QPBO строит частичную разметку переменных x – присваивает каждой переменной xi, i V значение из множества {0, 1, }, где элемент соответствует отказу от разметки. В стандартной линейной релаксации, решаемой алгоритмом QPBO, при этом выполнено свойство полуцелочисленности (half-integrality): существует решение, в котором все переменные принимают значения из множества {0, 0.5, 1}.

Существуют обобщения алгоритма QPBO на случай энергий с небинарными переменными [74, 63], а также методы, использующие свойство частичной оптимальности для повышения производительности [11] и улучшения качества решений [87, 107].

1.3.2.2.2. Двойственная декомпозиция. Комодакис и др. [73] сформулировали идею декомпозиции графа задачи минимизации энергии на подзадачи с ациклическими графами [130, 65] через релаксацию Лагранжа. Такой подход является более простым для понимания (чем подход, основанный на передаче сообщений [130, 65]) и обладает большей гибкостью.

Рассмотрим задачу минимизации парно-сепарабельной энергии (1.2), определённой на произвольном графе G = (V, E). Разобьём энергию на слагаемые следующим образом:

Здесь символ S индексирует слагаемые (подэнергии), S – конечное множество индексов слагаемых. Подэнергии E S являются энергиями, заданными на графах G S = (V S, E S ), где V S V и торых входят в множество V S (сокращение от xV S ). Потенциалы каждой из подэнергий в сумме составляют потенциалы энергий:

Решение задачи минимизации подэнергии E S (xS )9 (подзадачи) может оказаться существенно проще, чем решение задачи минимизации исходной энергии E(x). Например, если граф G S подзадачи S не содержит циклов, то эту подзадачу можно эффективно решить точно при помощи алгоритмов передачи сообщений (см. раздел 1.3.1.1.1). Предположим, что разбиение на подэнергии выбрано так, что все графы G S, S S, не содержат циклов, а значит задачи minxS E S (xS ) можно решить точно. Решая все подзадачи независимо, можно получить нижнюю оценку на глобальный минимум исходной задачи:

Данную нижнюю оценку можно существенно уточнить, обеспечивая согласование переменных подзадач, при помощи релаксации Лагранжа. Сформулируем исходную задачу минимизации энергии как задачу условной оптимизации, относительно индикаторных переменных подзаS S дач yip, yij,pq (аналогично задаче ЦЛП 1.23-1.27):

ленные переменные, обеспечивающие согласование подзадач, EL (y S ) – целевая функция станS дартной линейной релаксации (1.23) подзадачи S. Поскольку стандартная линейная релаксация на дереве точна (утв. 2), можно писать, что переменные y S лежат в многограннике Local(G S ) (а не принадлежат дискретному множеству с ограничениями вида (1.24), (1.25), (1.26), (1.27)).

Запишем лагранжиан задачи условной оптимизации (1.30)-(1.32):

где yS – часть переменных вектора y, относящиеся ко множествам V S и E S ; S – множители Лагранжа для ограничений (1.31) и (1.32), относящиеся к подзадаче S. Символы ·, · соответствуют скалярному произведению. Используя лагранжиан, получим нижнюю оценку на решение Заметим, что в символы xS и xS вкладывается несколько разный смысл. Символ xS означает проекцию переменных x на множество V S V, а xS – независимые переменные, соответствующие такому же множеству.

Принципиальная разница состоит в том, что если используется запись xS, то подразумевается, что в данном выражении переменные для разных множеств V S1 и V S2 согласованы: i V S1 V S2 xS1,i = xS2,i.

оптимизационной задачи (1.30)-(1.32):

Здесь D(S ) – двойственная функция.

При минимизации лагранжиана (1.33) по переменным y на эти переменные нет никаких ограничений. Поскольку эти переменные входят линейно, то везде, где коэффициенты перед ними не равны нулю, значение минимума лагранжиана не ограничено снизу. Из этого следует, что переменные S, по которым проводится максимизация, никогда не примут значений, при которых возникнут ненулевые коэффициенты. Данное рассуждение позволяет записать задачу максимизации нижней оценки (1.34) в виде задачи условной оптимизации, в которой переменные y не присутствуют:

Для вычисления целевой функции (1.35) при произвольном значении переменных S необходимо решать задачи оптимизации по переменным y S вида Эти задачи являются задачами минимизации парно-сепарабельной энергии на графе без циклов, а значит могут быть эффективно решены при помощи алгоритма передачи сообщений.

Задача (1.35)-(1.37) является задачей максимизации вогнутой кусочно-линейной функции (1.35) при ограничениях (1.36)-(1.37). Данную задачу можно решать методом проекции субградиента10. Используя решения подзадач (1.38), субградиент можно вычислить следующим Субградиент является обобщением понятия градиента для случая негладких функций. Для вогнутой функции f () субградиент в точке 0 – это такой вектор g, при котором для любых выполнено Если в точке 0 функция f () дифференцируема, то субградиент определён единственным образом и совпадает с градиентом. Если же функция f () в точке 0 не дифференцируема, то субградиент не единственен.

образом:

Проекцию субградиента на множество, заданное ограничениями (1.36) и (1.37), можно вычислить следующим образом:

Заметим, что количество двойственных переменных S существенно зависит от способа разбиения задачи на деревья. Если каждое ребро исходного графа G покрывается одним и только одним подграфом G S, то ограничения (1.37), а значит и переменные S, не нужны. Если каждая вершина покрывается только двумя подграфами, то ограничения (1.36) можно заменить на более простые: xS1 = xS2. Примером такой ситуации может случить граф G вида 4-х связная решётка, разбитый на два подграфа, содержащих только вертикальные или только горизонтальные рёбра.

Комодакис и др. [73] доказали следующее утверждение о наилучшей нижней оценке решения задачи минимизации энергии E(x), построенной при помощи решения непрерывной задачи (1.35)-(1.37):

Утверждение 4. Если графы G S всех подзадач S S не содержат циклов, то значение глобального максимума задачи (1.35)-(1.37) в точности совпадает со значением глобального минимума стандартной линейной релаксации исходной задачи.

Это утверждение означает, что оптимальное значение нижней оценки, которую можно получить при помощи двойственной декомпозиции с разбиением графа задачи на ациклические подграфы (деревья), не зависит от конкретного способа разбиения. Тем не менее, конкретный способ разбиения на деревья может существенно влиять на скорость сходимости метода.

В рамках данной работы метод минимизации парно-сепарабельной энергии при помощи декомпозиции графа задачи на деревья и дальнейшего согласования при помощи релаксации Лагранжа будем называть DD TRW (dual decomposition tree reweighted message passing).

В работах [70, 16, 136, 137, 53] показано, что метод двойственной декомпозиции может получать нижние оценки, более точные, чем стандартная линейная релаксация. Для этого надо использовать подзадачи, которые можно решить точно и при этом стандартная линейная релаксация на них не точна. Примерами таких подзадач могут служить задачи с графами малой ширины [82, 129] и энергии моделей Изинга для планарных графов [109].

1.3.2.2.3. Двойственная декомпозиция для случая потенциалов высоких порядков.

Комодакис и др. [71] исследовали возможность применения подхода двойственной декомпозиции для минимизации энергий с потенциалами высоких порядков (1.1).

Наиболее простым способом использования подхода двойственной декомпозиции является введение подзадач на каждый из потенциалов высоких порядков. Аналогично разделу 1.3.2.2. можно получить нижнюю оценку на глобальный минимум энергии:

Необходимым условием работы с нижней оценкой энергии (1.39) является возможность эффективно решать задачи минимизации, возникающие при вычислении нижней оценки D() при фиксированных множителях Лагранжа. Данные задачи имеют вид суммы одного потенциала высокого порядка и унарных потенциалов:

Если порядок потенциалов небольшой, то задачи (1.40) можно решать при помощи полного перебора.

При порядках потенциалов, когда перебор становится вычислительно неприемлем, возникает проблема хранения потенциалов в памяти. Необходимо некоторое компактное представление, требующее значительно меньше памяти, чем задание таблицей. Одним из способов такого компактного задания является задание значения по умолчанию и небольшого числа значений в выделенных конфигурациях. Такие потенциалы были независимо рассмотрены в работах [104, 71] и названы разреженными (sparse) и заданным шаблонами (pattern-based).

Будем говорить, что потенциал C задан шаблонами, если он принимает ненулевые значения только на заранее выделенном множестве конфигураций переменных DC XC, а в остальных случаях принимает значение по умолчанию – 0:

Шаблонами может быть задан произвольный потенциал C, но при этом множество DC может быть очень большого размера. Будем говорить, что потенциал C является разреженным, если он задан шаблонами, мощность множества DC много меньше числа всех возможных конфигураций |P|C, и все коэффициенты C,d отрицательны.

Примером разреженных потенциалов второго порядка являются потенциалы Поттса (Potts):

{i,j} (xi, xj ) = [xi = xj ]. Примером разреженных потенциалов высоких порядков являются потенциалы Поттса высокого порядка (P n -Potts), введённые в работе [60]:

1, если все переменные xi, i C, принимают одинаковые значения, Если потенциалы высокого порядка разреженные, то задачи (1.40) можно решить эффективно. В этом случае минимум может достигаться либо на одной из конфигураций множества выделенных конфигураций DC (обычно |DC | |XC |) или на конфигурации, доставляющей минимум унарных потенциалов: xi = arg minxi P i (xi ), i C. Перебор всех этих конфигураций и приводит к решению задачи (1.40).

Аналогично задаче (1.35)-(1.37) задача максимизации нижней оценки (1.39) является кусочно-линейной и вогнутой, а значит её можно решить при помощи методов проекции субградиента.

Заметим, что нижнюю оценку (1.39) можно комбинировать с разложением парносепарабельных энергий на деревья, а именно объединять потенциалы порядка 2, если таковые присутствуют в энергии, в группы, так чтобы графы не образовывали циклов. В рамках данной работы будем называть этот метод CWD (clique-wise decomposition).

В работе [71] предложен способ объединения нескольких разреженных потенциалов высоких порядков в группу, допускающий эффективное решение задачи аналогичной (1.40) (алгоритм PatB).

1.3.2.2.4. Альтернативные виды релаксаций. Стандартная линейная релаксация является не единственной непрерывной релаксацией задачи минимизации энергии (1.5)-(1.7). Существуют и более точные линейные релаксации [115, 70, 116, 17], и другие виды релаксаций: квадратичная релаксация [101], коническая релаксация [78], полуопределённая (semidefinite, SDP) релаксация [131].

В семействах линейных релаксаций, более точных чем стандартная релаксация, обычно делается попытка построить приближение маргинального многогранника, более точное чем локальный маргинальный многогранник. Примером такого приближения может служить многогранник, описываемый всеми циклическими ограничениями (cycle inequalities) [115, 70]. Несмотря на, вообще говоря, более точные нижние оценки, методы этой группы редко используются на практике, поскольку являются достаточно медленными.

Квадратичная релаксация в формулировке из работы [101] всегда точна (зазор равен 0), но часто является не выпуклой. Для её использования приходится строить дополнительную нижнюю оценку (QP-RL), которая, в свою очередь, уже является выпуклой. Коническая релаксация второго порядка [78] (SOCP-MS) является выпуклой оптимизационной задачей, но в ней возможен ненулевой зазор. Кумар и др. [79] провели теоретическое сравнение трёх подходов (стандартная линейная релаксация, QP-RL, SOCP-MS) и показали, что стандартная линейная релаксация предоставляет нижнюю оценку строго лучше нижних оценок двух других подходов.

Также Кумар и др. [79] предложили способ построения более точного семейства оценок на основе конического программирования, но для этого семейства не известно эффективных алгоритмов поиска наилучшей оценки. SDP-релаксация была предложена лишь в 2013 г., и её сравнение с другими видами релаксаций ещё не проведено.

2. Субмодулярная релаксация В этой главе описан подход к задаче минимизации энергии, основанный на применении релаксации Лагранжа к ограничениям целостности: субмодулярная релаксация (submodular relaxation, SMR). Раздел 2.1 описывает частный случай SMR для парно-сепарабельных ассоциативных энергий: субмодулярное разложение (submodular decomposition, SMD), предложенное в работах [128, 97]. Раздел 2.2 описывает расширение SMD на случай энергий с потенциалами высоких порядков [96], раздел 2.3 – на случай парных потенциалов произвольного вида [127].

Раздел 2.4 описывает способ учёта глобальных линейных ограничений в рамках SMR.

2.1. Парно-сепарабельные ассоциативные энергии Рассмотрим задачу минимизации парно-сепарабельной энергии в индикаторной нотации:

Ограничения (2.2) гарантируют, что каждая переменная i исходной задачи принимает одно и только одно значение из множества меток P (ограничения целостности), ограничения (2.3) – делают индикаторные переменные yip бинарными (ограничения целочисленности).

Пусть все парные потенциалы ij принадлежат классу ассоциативных потенциалов [123]:

где Cij,p – неотрицательные константы. Стоит отметить, что если значения Cij,p в случае равенства меток p и q не зависят от метки p (Cij,p = Cij ), то ассоциативные потенциалы (2.4) становятся потенциалами Поттса (отличаются на константу от стандартной записи из работы [24]).

В случае ассоциативных парных потенциалов (2.4) ненулевые коэффициенты в целевой функции (2.1) могут присутствовать только при слагаемых, отвечающих унарным потенциалам, а также парным потенциалам вида yip yjp, p P. В этом случае индикаторы yip, относящиеся к разным меткам, связаны только ограничениями целостности (2.2). Таким образом, если отбросить ограничения целостности, то целевая функция распадается на |P| групп слагаемых (подзадач), каждая из которых содержит только переменные, относящиеся к определённой метке p.

Формально, целевая функция (2.1) может быть представлена в виде суммы слагаемых EI (yp ), каждое их которых зависит только от переменных yp = {yip | i V}, относящихся к одной метке p P. Слагаемые можно записать следующим способом:

Используя разложение целевой функции (2.1) на слагаемые (2.5), можно получить нижнюю оценку на глобальный минимум оптимизационной задачи (2.1)-(2.3):

эти функции субмодулярны, а значит могут быть эффективно минимизированы при помощи применения алгоритмов разрезов графов (см. раздел 1.3.1.2), что, в свою очередь, позволяет эффективно вычислять нижнюю оценку (2.6).

Нижнюю оценку (2.6) можно существенно уточнить при помощи перехода от отбрасывания ограничений целостности (2.2) к применению к ним релаксации Лагранжа (аналогично алгоритмам двойственной декомпозиции, см. раздел 1.3.2.2.2). Рассмотрим следующий лагранжиан:

Соотношение между минимумом максимумов (минимакс) и максимумом минимумов (максимин) позволяет получить следующую нижнюю оценку на точное решение задачи (2.1)-(2.3):

Здесь D() – это двойственная функция:

Минимизация функций по переменным yp = {yip }iV может быть проведена при помощи алгоритмов поиска минимального разреза графа, поскольку множители Лагранжа i влияют только на унарные потенциалы j yjp, которые, в свою очередь, не влияют на свойство субмодулярности. Таким образом, двойственная функция D() может быть эффективно вычислена.

Утверждение 5. Двойственная функция D() вогнута и кусочно-линейна. Субградиент функции D() может быть вычислен следующим образом:

где Доказательство. Заметим, что множества {0, 1}|V|, по которым проводится минимизация при вычислении двойственной функции D() (2.9), конечны. При фиксированных yp, p P, лагранжиан L(y, ) (2.7) линеен по переменным. Отсюда следует, что функция D() имеет вид минимума из конечного числа линейных функций: mini a. Функции такого вида кусочноi линейны и вогнуты. Субградиент равен aj, где j = arg mini a.

Задача поиска наиболее точной нижней оценки вида (2.8) эквивалентна задаче максимизации функции D() по переменным. Поскольку функция D() вогнута и позволяет эффективно вычислять субградиент, то для её максимизации можно применять методы негладкой оптимизации первого порядка. Конкретные методы оптимизации, использованные в данной работе, будут рассмотрены в главе 4.

Заметим, что размерность пространства, по которому требуется осуществить оптимизацию (количество множителей Лагранжа), составляет |V|, что меньше чем в методе DD TRW [73] как минимум в |P| раз. Этот факт даёт основания надеяться, что алгоритм SMD будет сходиться быстрее, чем алгоритм DD TRW. Теоретическое сравнение нижних оценок методов SMD и DD TRW, а также их экспериментальное сравнение проведены в главах 3 и 5, соответственно.

2.2. Энергии с потенциалами высоких порядков Рассмотрим задачу минимизации энергии, состоящей из унарных потенциалов и потенциалов произвольных порядков (1.1). Запишем энергию при помощи индикаторных переменных yip :

Минимизация функции (1.1) по многозначных дискретным переменным x эквивалентна минимизации энергии (2.12) по бинарным переменным y при ограничениях целостности (1.7).

Пусть все потенциалы высоких порядков разреженные (см. раздел 1.3.2.2.3). По определению разреженных потенциалов все коэффициенты C,d отрицательны. В этом случае при помощи тождества можно преобразовать функцию бинарных переменных EI (2.12) с потенциалами высоких порядков к парно-сепарабельной функции EI от расширенного набора переменных так, что минимум EI по расширенному множеству переменных совпадает c минимумом EI по исходному множеству переменных:

Данный прием был предложен в работе [68] для потенциалов порядка 3, а в работе [38] был сформулирован в форме (2.13) и обобщен на случай потенциалов произвольных порядков.

Для произвольного потенциала высокого порядка заданного шаблонами C (см. раздел 1.3.2.2.3) для того, чтобы применить преобразование (2.13), можно вычесть константу maxf DC C,f из всех значений потенциалов (в том числе при тех конфигурациях, где стоит значение по умолчанию), одновременно прибавив её в качестве константного слагаемого к энергии. После этого преобразование (2.13) можно применить, но, вообще говоря, придется ввести в энергию экспоненциально много дополнительных переменных z: по одной для каждого ненулевого значения. В случае же разреженных потенциалов количество добавляемых переменных равно сумме мощностей множеств DC.

Энергию EI (y, z) можно записать в виде Функция EI (y, z) парно-сепарабельна и субмодулярна относительно переменных y и z (утв. 1), а значит, если нет никаких дополнительных ограничений, может быть эффективно минимизирована при помощи алгоритмов построения минимального разреза в графе (см. раздел 1.3.1.2).

Добавив ограничения целостности (1.4) к задаче минимизации функционала (2.14), применим к ним релаксацию Лагранжа. Аналогично случаю парно-сепарабельной энергии (см. раздел 2.1) запишем лагранжиан и двойственную функцию Лагранжиан L(y, z, ) является субмодулярной парно-сепарабельной функцией относительно переменных (y, z) для любых значений множителей Лагранжа, что позволяет эффективно вычислить двойственную функцию D в произвольной точке. Функция D() является нижней оценкой глобального минимума энергии (1.1). Аналогично утв. 5 функция D() переменных является вогнутой кусочно-линейной, что позволяет решать задачу максимизации D() при помощи алгоритмов выпуклой негладкой оптимизации. Субградиент функции D() может быть вычислен следующим образом:

где ({yip }pP, z ) = arg minyp,z{0,1} L(y, z, ). Возможность эффективно вычислить субградиент позволяет применять методы оптимизации первого порядка. Конкретные методы оптимизации, использованные в данной работе, будут рассмотрены в главе 4.

В случае парно-сепарабельной энергии с ассоциативными парными потенциалами SMR эквивалентно SMD. Если энергия парно-сепарабельна, но парные потенциалы не ассоциативны, то SMR можно существенно упростить. В этом случае вводить дополнительные переменные z при помощи (2.13) не требуется, поскольку лагранжиан (2.15) является парно-сепарабельным и субмодулярным уже относительно переменных y, что позволяет эффективно вычислять двойственную функции (2.16). Здесь 0 = maxk,P ij,k.

Размерность пространства, в котором требуется осуществить оптимизацию, составляет |V|, как и в методе SMD. Размерность пространства двойственных переменных, возникающего при использовании метода CWD [71], составляет не менее |P|( |C| |C|). Метод PatB [71] позволяет сократить количество переменных путём усложнения подзадач, но, например, для гиперграфа, состоящего из 4-х связной решётки из парных потенциалов и дополнительных потенциалов высоких порядков, количество двойственных переменных составляет не менее |P|(|V| + | CC:|C|>2 C|).

Робастные разреженные потенциалы. Выше в данном разделе подход SMR был применен для разреженных потенциалов высоких порядков. Данный подход можно обобщить и на случай робастных разреженных потенциалов высоких порядков при помощи методов, применённых в работах [61, 104]. Потенциалы такого вида не только поощряют разметки тождественно соответствовать предопределённым конфигурациям d DC, но и поощряют небольшие отклонения от них. Потенциал такого вида для гиперребра C можно выразить как через |P|-значные переменные x так и через индикаторные переменные y Параметрами потенциалов гиперребра C являются константы C,d < 0, d DC и w > 0, C.

Последнее выражение может быть редуцировано к парно-сепарабельной функции при помощи добавления переменных-переключателей zC,d (аналогично трансформации (2.14)):

Данное выражение парно-сепарабельно и субмодулярно (т.к. w 0) относительно переменных y и z. Применение релаксации Лагранжа и максимизация двойственной функции в SMR с робастными разреженными потенциалами абсолютно аналогичны SMR с обычными разреженными потенциалами.

Для вывода SMR для робастных разреженных потенциалов использовалась формулировка из работы [104], а именно свёртка элементов различных выделенных конфигураций при помощи операции «сумма», а не «минимум». Данные две схемы эквивалентны, если все выделенные конфигурации достаточно далеко друг от друга (например, см. [61, ур. 17, 18]).

2.3. Несубмодулярный лагранжиан В разделах 2.1 и 2.2 лагранжиан всегда был субмодулярен относительно бинарных переменных. Оказывается, что от этого требования можно отказаться, если использовать приближённый алгоритм минимизации энергии QPBO [66, 22] вместо точного алгоритма, основанного на построении минимально разреза графа.

Разберём данную ситуацию на примере задачи минимизации парно-сепарабельной энергии (2.1)-(2.3), где парные потенциалы ij не являются ассоциативными (но, по-прежнему, ij,pq = 0 при p = q). В этом случае метод SMD (см. раздел 2.1) не применим. Для применения метода SMR (см. раздел 2.2) необходимо из всех значений потенциала вычесть его максимум: maxp,q ij,pq. Данная операция может негативно сказаться на разреженности потенциала, например, если он штрафует появление нескольких выделенных конфигураций. Если отбросить шаг вычитания максимума, то свойство разреженности сохраняется, но выражение (2.1) может быть несубмодулярно, а значит, минимизация его по бинарным переменным yip может быть NPтрудной задачей. Вместо того, чтобы выполнять минимизацию псевдо-булевой функции (2.1), можно вычислить её стандартную релаксацию при помощи алгоритма QPBO и далее применять релаксацию Лагранжа потенциалов целостности (2.2). Назовём данный подход несубмодулярной релаксацией, или, сокращённо, NSMR.

Приведем формальное описание NSMR. Рассмотрим следующий лагранжиан:

Лагранжиан L(y, ) является парно-сепарабельной псевдо-булевой функцией переменных y, а значит, его стандартная релаксация может быть вычислена при помощи алгоритма QPBO. Данный метод предоставляет значение нижней оценки DQP BO () глобального минимума, а также частичную разметку переменных y: каждой переменной yip ставится в соответствие значение из множества {0, 1, }. Нижняя оценка, предоставляемая методом QPBO, по значению равна стандартной релаксации [132]:

а значит, функция DQP BO () вогнута и кусочно-линейна, как функция переменных. Здесь вершины графа G соответствуют переменным yip лагранжиана (2.18), а ребра графа E соответствуют слагаемым ij,pq yip yjq лагранжиана (2.18).

Для того чтобы вычислить субградиент функции DQP BO (), воспользуемся тем, что стандартная релаксация парно-сепарабельной псевдо-булевой функции является полуцелой [22]: существует решение задачи линейного программирования, такое что все переменные принимают значения из множества {0, 1, 0.5}. В частности, если QPBO присваивает значения 0, 1, переменной yip, то соответствующие переменные стандартной релаксации равны 0, 1, 0.5, соответственно. Парные потенциалы стандартной релаксации yij,pq могут быть найдены по следующему правилу (док-во следует из леммы 1):

Нижняя оценка DQP BO (), получаемая методом NSMR, является нижней оценкой нижней оценки, получаемой методом SMD, а значит, может привести к увеличению зазора между прямой и двойственной задачами. Данные свойства теоретически исследованы в разделе 3.4.

2.4. Линейные глобальные ограничения Важным частным случаем глобальных потенциалов энергии являются линейные ограничения на индикаторные переменные. Можно перечислить несколько видов таких ограничений:

Ограничения (2.21) являются жёсткими ограничениями на количество переменных, принимающих значение p P. Ограничения (2.22) – интервальными ограничениями.

Пусть каждой вершине j V соответствует некоторая наблюдаемая скалярная или векторная величина Ij. Например, в случае если множество вершин V соответствует пикселям изображения, то величины Ij могут соответствовать интенсивностям или цветам (например, в пространстве RGB) пикселей изображения. Используя Ij в качестве весов, можно записать, например, следующие линейные ограничения на индикаторные переменные y:

Ограничения (2.23) и (2.24) задают равенство средних и ковариаций величин Ij величинам µ и, соответственно. Ограничение (2.25) задаёт равенство потоков через вершины, принимающие значения p и q.

Для некоторых частных случаев линейных ограничений существуют специализированные методы. Например, работы [91, 76] исследуют ограничения видов (2.21) и (2.22).

Подход SMR (а также SMD и NSMR) позволяет учитывать ограничения общего вида:

Введём дополнительные множители Лагранжа = {m }m=1,...,M, = {m }m=1,...,M по одному на каждое из ограничений (2.26), (2.27) и получим лагранжиан:

где множители Лагранжа, соответствующие ограничениям вида неравенство, должны быть неотрицательны. Лагранжиан субмодулярен относительно индикаторных переменных y, и поэтому двойственная функция может быть эффективно вычислена.

Аналогично случаям, рассмотренным ранее, задача поиска наиболее точной нижней оценки соответствует задаче максимизации Двойственная функция D(,, ) является кусочно-линейной и вогнутой по всем двойственным переменным, а значит, может быть максимизирована, например, методами выпуклой оптимизации.

3. Точность нижних оценок В главе 2 настоящей работы получены методы для задачи минимизации энергии (1.1) общего вида, а также для нескольких частных случаев. Все описанные методы основаны на максимизации нижней оценки глобального минимума, полученной при помощи релаксации Лагранжа ограничений целостности (1.7). Качество этих методов существенно зависит от того, насколько точной является полученная оценка. В данной главе данный вопрос изучается теоретически: для каждого метода формулируется линейная релаксация, значению решения которой равен максимум его нижней оценки, а также проводится сравнение со стандартной релаксацией.

Сначала (раздел 3.1) приведены формулировки и доказательства нескольких вспомогательных лемм, облегчающих работу со стандартной линейной релаксацией функций бинарных переменных. Далее, раздел 3.2 посвящён парно-сепарабельным ассоциативным энергиям (метод SMD), раздел 3.3 – энергиям с потенциалами высоких порядков (метод SMR), раздел 3.4 – произвольным парно-сепарабельным энергиям (метод NSMR). В разделе 3.5 рассматривается случай глобальных линейных ограничений.

3.1. Вспомогательные леммы Лемма 1. Рассмотрим задачу минимизации парно-сепарабельной энергии где переменные y = {yi }iA бинарны. Здесь A и B – множества унарных и парных потенциалов, соответственно. Тогда стандартная линейная релаксация данной энергии эквивалентна следующей задаче линейного программирования:

Доказательство. Рассмотрим стандартную линейную релаксацию для рассматриваемой задачи:

Покажем, что по решению задачи (3.5)-(3.8) можно построить допустимую точку задачи (3.1)-(3.4) с таким же значением целевой функции, откуда будет следовать, что значение минимума задачи (3.1)-(3.4) не больше значения минимума задачи (3.5)-(3.8). Положим значения переменных следующим образом: yi = zi1, yij = zij,11. Допустимость данной точки следует из неотрицательности z и ограничений (3.8). Значения целевых функций обеих задач при таком присваивании совпадают.

Обратное соотношение между значениями минимумов задач (3.5)-(3.8) и (3.1)-(3.4) показывается аналогично. Действительно, по решению (3.1)-(3.4) можно положить zj1 = yj, zj0 = 1 zj1, zij,11 = yij, zij,01 = zj1 zij,11, zij,10 = yi1 zij,11, zij,00 = zij,11 + 1 yi1 yj1.

Легко убедиться, что такое присваивание переменных допустимо и приводит к такому же значению целевой функции.

Таким образом, показано, что значения минимумов двух задач совпадают, и по решению любой из них можно построить допустимую точку другой с таким же значением целевой функции, что и является эквивалентностью.

Лемма 2. Рассмотрим задачу минимизации парно-сепарабельной энергии где переменные y = {yi }iA бинарны. Здесь A и B – множества унарных и парных потенциалов, соответственно. Пусть все коэффициенты bij 0. Тогда стандартная линейная релаксация данной энергии точна, и может быть записана как задача линейного программирования (3.1)Доказательство. По утв. 1 функция E(y) субмодулярна, а значит, согласно утв. 3, стандартная линейная релаксация данной задачи точна.

По лемме 1 стандартная линейная релаксация рассматриваемой задачи может быть записана в виде задачи линейного программирования (3.1)-(3.4). Покажем, что в данном случае функции, выгоднее принимать наибольшее из допустимых значений, а именно min(yi, yj ). Нераyi +yj 1 выполнено для любых значений yi и yj, а значит ограничение (3.4) венство min(yi, yj ) избыточно и может быть опущено.

Тогда существует набор значений {zpq }K, таких что Доказательство. Положим zpp = min(yp, yp ). Рассмотрим транспортную задачу где ap = yp zpp, bp = yp zpp. Решение данной транспортной задачи {zpq } существует, поскольку ap 0, bp 0, и ограничения сбалансированы:

При этом выполнено zpp = 0. Положим zpq = zpq, p = q. Набор значений {zpq }K искомым.

Лемма 4. Пусть y1,..., yK – произвольные действительные числа, принадлежащие отрезку [0, 1], K > 1. Рассмотрим задачу линейного программирования:

Минимальное значение целевой функции на допустимом множестве достигается в точке z = z1 = · · · = zK = mink=1,...,K yk.

Доказательство. Не ограничивая общности, предположим, что y1... yK. Обозначим значения переменных, являющихся решением оптимизационной задачи (3.9)-(3.10), через z, z1,..., zK, а значение минимума – через f. Переменная z входит в линейную целевую функцию (3.9) с положительным коэффициентом и ограничена неравенствами (3.10) снизу, что означает, что в точке оптимума она принимает наименьшее допустимое значение:

z = maxk=1,...,K zk. Аналогично, переменные z1,..., zK принимают наибольшие допустимые значения: zk = min(yk, z ).

Покажем, что z y1. Предположим, что это не так. Пусть = y1 z > 0. Заметим, что точка z +, z1 +,..., zK + является допустимой, целевая функция (3.9) в ней принимает значения f, что противоречит предположению минимальности f.

Покажем, что z y2. Предположим, что это не так. Возможны 2 случая:

1. yK < z. Пусть = z yK > 0. Точка z, z1,..., zK является допустимой, целевая функция (3.9) в ней принимает значения f, что противоречит предположению z1,..., z, z+1,..., zK является допустимой, целевая функция (3.9) в ней принимает значения f ( 1), что противоречит предположению минимальности f.