Субмодулярная релаксация в задаче минимизации энергии марковского случайного поля тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет имени М. В. Ломоносова

На правах рукописи

Осокин Антон Александрович

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

Москва — 2014

15 ПАП 2014

005547736

Работа выполнена на кафедре математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова

Научный руководитель: кандидат физико-математических наук,

Ветров Дмитрий Петрович.

Официальные оппоненты: доктор физико-математических наук, с.н.с.,

Защита состоится «30» мая 2014 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М. В. Ломоносова, расположенном по адресу: 119991, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией и авторефератом можно ознакомиться в Научной библиотеке МГУ, а также на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Диссертации».

Автореферат разослан «I % » г.

Председатель , профессор

диссертационного совета Васин А. А.

нач. подраздел. 3000 «Системы интеллектуального анализа данных, технического зрения, улучшеного и синтезированного видения» ФГУП «ГосНИИАС», Визильтер Юрий Валентинович;

кандидат физико-математических наук, научный сотрудник Санкт-Петербургского отделения Математического института им. В.А. Стеклова РАН, Николенко Сергей Игоревич.

Ведущая организация: Московский физико-технический институт

(государственный университет).

Общая характеристика работы

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

Большинство задач распознавания образов и машинного обучения заключается в предсказании неизвестных величин на основе наблюдаемых. Можно выделить два типа задач, связанных со структурированными данными:

1. предсказания всех ненаблюдаемых величин осуществляются независимо;

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

Задачи первого типа обладают структурой на уровне описания данных, но

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

В решении задач первого типа в настоящее время доминируют нейронные сети нового поколения (глубинное обучение, deep learning). В рамках этого подхода делается попытка получить по данным признаковое описание, содержащее

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

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

Один из наиболее популярных подходов к математической формулировке и решению задачи распознавания второго типа основан на поиске моды совместного апостериорного распределения неизвестных переменных (maximum а posteriori estimation, MAP-inference). Задача поиска моды является задачей оптимизации (либо непрерывной, либо дискретной). Часто распределение представляет собой произведение большого числа множителей (факторов), и работать с ним в таком виде неудобно. В этом случае берут отрицательный логарифм апостериорного распределения и переходят к эквивалентной задаче минимизации. Минимизируемую функцию при этом обычно называют энергией.3 Несмотря на то что задача минимизации энергии в общем случае является NP-трудной, на практике её приближённые решения получать существенно проще, чем, например, приближённо вычислять апостериорные маргинальные распределения. Задачи минимизации энергии также часто возникают в качестве подзадач при решении задачи наст-ройки параметров модели по наблюдаемым данным. Наи-

1 A. Krizhevsky, I. Sutskever, G. Е. Hinton, ImageNet Classification with Deep Convolutional Neural Networks,

Advances in Neural Information Processing Systems (NIPS), 2012.

2M. J. Wainwright, M. I. Jordan, Graphical models, exponential familles, and variational inference, Foundations and

Trends in Machine Learaing, no. 1-2, Now publishers, 2008.

'Термин «энергия» используется из-за связи с понятием энергии из статистической физики.

2

более известным методом, в котором возникает подзадача минимизации энергии, является структурный метод опорных векторов (structured support vector machine, SSVM).4 SSVM часто используется на практике для решения задач второго типа, т. к. в ряде случаев превосходит альтернативные методы как по качеству, так и по скорости работы.

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

Приведём формальную постановку задачи минимизации энергии, решению которой посвящена настоящая работа. Пусть задан гиперграф Q = (V, С), где V -конечное множество вершин, С - конечное мультимножество гиперрёбер (подмножеств множества вершин). Пусть каждой вершине гиперграфа г £ V соответствует переменная xit принимающая значения из конечного непустого множества меток V. Для любого гиперребра С 6 С символ хс соответствует кортежу переменных, индексы которых принадлежат множеству С: хс = | г £ С). При обозначении кортежа всех переменных индекс V будем опускать: х. Энергией, заданной на гиперграфе Q, будем называть функционал следующего вида:

ВД + (1)

i£V СеС

Здесь функционалы 0,- : V R называются унарными потенциалами, а функционалы 6с : Хс —^ M - потенциалами, заданными на гиперрёбрах.

Задача минимизации энергии Е{х) по дискретным переменным х

min Е(х). (2)

хегт

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

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

4В. Taskar, С. Guestrin, D. Koller, Max-Margin Markov Networks, Advances in Neural Information Processing Systems (NIPS), 2003.

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

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

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

Методы исследования. Для достижения поставленной цели был выбран подход, основанный на релаксации Лагранжа ограничений, затрудняющих решение задачи. Частным случаем этого подхода является двойственная декомпозиция (dual decomposition), применённая для задач минимизации энергии, например, в работах Комодакиса и др.8 В настоящей диссертации используется вариант

5J. Kappes, В. Andres, F. Hamprecht, С. Schnorr, S. Nowozin, D. Batra, S. Kim, B. Kausler, J. Lellmann, N. Komodakis, C. Rother, A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization

Problems, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013.

6P. Kohli, P. M. Kumar, P. Torr, V3&Beyond: Move Making Algorithms for Solving Higher Order Functions, IEEE

Transactions on Pattern Analysis and Machine Intelligence (PAM1), Vol. 31, no. 9, pp. 1645-1656, 2008.

7N. Komodakis, N. Paragios, Beyond Pairwise Energies: Efficient Optimization for Higher-Order MRFs, IEEE

Conference on Computer Vision and Pattern Recognition (CVPR), 2009.

8N. Komodakis, N. Paragios, G. Tziritas, MRF Energy Minimization and Beyond via Dual Decomposition, IEEE

Transactions on Pattern Analysis and Machine Intelligence (PAM1), vol. 33, no. 3, pp. 531-552, 2011.

4

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

Основные положения, выносимые на защиту:

1. Новый подход для решения задачи минимизации энергии: субмодулярная релаксация.

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

3. Алгоритм покоординатного подъема для максимизации нижней оценки, построенной в рамках подхода субмодулярной релаксации, применимый в случае ассоциативных парно-сепарабельных энергий.

4. Экспериментальное исследование всех разработанных методов, содержащее их сравнение с существующими аналогами.

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

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

'Y, Boykov, V. Kolmogorov, An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 26, no. 9, pp. 1124-1137, 2004.

I0P. Kohli, P. Torr, Dynamic graph cuts for efficient inference in Markov random fields, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 29, no. 12, pp. 2079-2088, 2007.

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

Достоверность результатов обеспечивается доказательствами теорем и подробными описаниями экспериментов, допускающими воспроизводимость.

Апробация работы. Результаты настоящей работы неоднократно докладывались на семинаре группы байесовских методов машинного обучения кафедры математических методов прогнозирования, ВМК МГУ, а также докладывались на следующих конференциях:

1. Международная конференция по компьютерному зрению и распознаванию образов (Computer Vision and Pattern Recognition, CVPR), 2010. [1]

2. Международная конференция «Интеллектуализация обработки информации» (ИОИ), 2010. [11, 9]

3. Международная конференция по компьютерному зрению и распознаванию образов (Computer Vision and Pattern Recognition, CVPR), 2011. [7]

4. Всероссийская конференция «Математические методы распознавания образов» (ММРО), 2011. [8]

5. Международная конференция «Системы обработки нейроинформации» (Neural Information Processing Systems, NIPS), секция «Дискретная оптимизация в машинном обучении» (discrete optimization in machine leaming, DISCML), 2011. [10]

6. Международная конференция «Системы обработки нейроинформации» (Neural Information Processing Systems, NIPS), 2012. [3]

7. Европейская конференция по компьютерному зрению (European Conference on Computer Vision, ECCV), секция «Модели высоких порядков и глобальные ограничения в компьютерном зрении» (Higher-Order Models and Global Constraints in Computer Vision), 2012. [6]

8. Международная конференция по компьютерному зрению и распознаванию образов (Computer Vision and Pattern Recognition, CVPR), 2013. [4]

Публикации. Основные результаты по теме диссертации изложены в 11 печатных изданиях [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, И], 7 из которых входят в список

6

изданий, рекомендованных ВАК [1, 2, 3, 4, 5, 6, 7], 4 - сборники докладов конференций [8, 9, 10, 11].

Личный вклад диссертанта заключается в выполнении основного объёма теоретических и экспериментальных исследований, изложенных в диссертационной работе, а именно: в разработке подхода SMR, включая его частные случаи SMD и NSMR; формулировке и доказательстве всех теорем (за исключением теоремы 2); разработке и реализации конкретных алгоритмов решения задачи минимизации энергии, основанных на подходе SMR; разработке методик и проведении экспериментального исследования, включающего в себя сравнение с существующими аналогами; оформлении результатов в виде публикаций и научных докладов.

Объём и структура работы. Диссертация состоит из оглавления, введения, пяти глав, заключения, списка иллюстраций (19 п.), списка таблиц (2 п.), списка литературы (139 п.) и одного приложения. Общий объём работы составляет 121 стр.

Краткое содержание работы

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

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

1. алгоритмы передачи сообщений для точного решения задачи минимизации энергии в случае ациклического графа (фактор-графа)11;

"С. М. Bishop, Pottern recognition and machine learning. Springer, 2006.

7

2. алгоритмы точной минимизации парно-сепарабельных энергий, зависящих от бинарных12 и многозначных13 переменных, основанные на построении минимальных разрезов графов;

3. приближённые алгоритмы минимизации энергии, основанные на итеративном построении разрезов графов14;

4. приближённые алгоритмы минимизации энергии, основанные на линейной релаксации дискретной задачи и двойственной декомпозиции (алгоритмы DD TRW15 и CWD16).

В главе 2 приведено формальное описание предложенного подхода субмодулярной релаксации. В разделе 2.1 изложен частный случай данного подхода - субмодулярная декомпозиция (SMD) [7]. SMD применим в ситуациях, когда энергия Е(х) является парно-сепарабельной, и все парные потенциалы являются ассоциативными: в^(р, q) = -Cijp[p = q], {i,j} e С, p,q <E V, где символы «[■]» - нотация Айверсона (для логического выражения А выполнено равенство [Л] = 1, если А истинно, и [А] = 0, если А ложно), а С1]ф - неотрицательные константы.

Используя индикаторные переменные гцр — [хi = р], i G V, р £ V, исходную задачу минимизации энергии (2) можно переписать в следующем виде:

i'eV peV {i,j}eC рдеР

s.t. £yip = l, Vi€V, (4)

peP

yip e {0, l}, VieV,peV. (5)

Целевая функция (3) как функция бинарных переменных угр является парно-

сепарабельной и субмодулярной, а значит задача минимизации (3), (5) без огра-

ду

Kolmogorov, R. Zabih, What energy functions can be minimized via graph cuts?, IEEE Transactions on Pattern

Analysis and Machine Intelligence (PAMI), vol. 26, no. 2, pp. 147-159, 2004.

13 J. Darbon, Global optimization for first order Markov random fields with submodular priors, Discrete Applied

Mathematics, vol. 157, no. 16, pp. 3412-3423, 2009.

i4Y. Boykov, O. Veksler, R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 23, no. 11, pp. 1222-1239, 2001.

I3N. Komodakis, N. Paragios, G. Tziritas, MRF Energy Minimization and Beyond via Dual Decomposition, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 33, no. 3, pp. 531-552, 2011.

I6N. Komodakis, N. Paragios, Beyond Pairwise Energies: Efficient Optimization for Higher-Order MRFs, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.

8

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

Цул) = Е Е 9Фл)У1рУзя+^х1 1 (6)

¿6V p&V {i,j}eCp,q£P jeV \ptV )

как функция переменных у — {y!p}f|y является парно-сепарабельным и субмодулярным, а значит, может быть эффективно минимизирован по переменным у при помощи алгоритмов разрезов графов. Двойственная функция

D(А) = mmL(y, А) у

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

функции £>(А) может быть вычислен аналитически:

= (?)

peV

где {i/?p}teV,P6P = arg miny L(y, А),

В разделе 2.2 приводится обобщение подхода SMD на случай энергий с потенциалами высоких порядков (подход субмодулярная релаксация, SMR). В разделе 2.3 приводится обобщение подхода SMD на случай парно-сепарабельных энергий с неассоциативными потенциалами (подход несубмодулярная релаксация, NSMR). В разделе 2.4 приведен способ учёта в рамках подхода SMR глобальных линейных ограничений на индикаторные переменные yip:

= m = 1,...,М, (8)

ieV реР

к = (9)

ieV р£Р

где w1^, ст, у*,, dk - константы.

В главе 3 приводятся основные теоретические результаты данной работы. Для подхода SMR и нескольких его частных случаев, описанных выше, характеризуется наилучшая нижняя оценка на глобальный минимум энергии, которую можно найти в рамках каждого из подходов. В разделе 3.1 приведены вспомогательные леммы, использующиеся в последующих доказательствах теорем. В разделе 3.2 приведено описание нижней оценки на глобальный минимум, достижимой в рамках SMR (теорема 1).

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

min У1У2дг{р)у{р+ J2 Мр-^ОУу«. 0°)

Vip'Vij™ ieV peV (i,j)eCP,qeP

s.t. = l, VieV, (Ii)

per

J2 W** - Уп> i> € C, Vg € P, (12)

peV

5>« = »p. V{i,j}eC,Vp€7>, (13)

qeV

Уц,рч > 0, yip > 0. (14)

Данное значение нижней оценки в точности равно наилучшей нижней оценке, которую можно получить при помощи подхода DD TRW.

В разделе 3.3 доказывается результат, обобщающий теорему 1 на случай потенциалов высоких порядков (теорема 3).

Теорема 3. Для энергии вида (1) наилучшая нижняя оценка, достижимая в рамках подхода SMR, равна значению решения следующей задачи линейного про-

граммирования:

тш + I] 9с{(£)усл, (15)

гбУрбР СбС^ерЮ!

вЛ. У1Р > 0, ус.ег > О, Уг е V, Ур £ V, УС е С, У<* 6 (16)

Уел < Уед, vc е С, Усг е У<? е с, (17)

]Г>Р = 1, Уг€У. (18)

р€~Р

Для частного случая потенциалов высоких порядков задачу линейного программирования (15)-(18) можно переписать в форме, эквивалентной аналогичной задаче, получаемой в рамках подхода С\¥Б (теорема 4).

Теорема 4. Для энергии вида (1) с потенциалами высоких порядков, являющимися перестановочными потенциалами Поттса}1 подход 5МК позволяет найти нижнюю оценку, равную значению решения задачи линейного программирования (15)-(18) с добавлением следующих ограничений:

^ УС* = У^ е С, Уд е V* е С.

В разделе 3.4 результаты, аналогичные теоремам 1, 3 и 4, доказываются для подхода ЫБМЯ. В разделе 3.5 формулируются результаты, показывающие наилучшее значение нижней оценки, построенной в рамках подхода 8М11, применённого в случае наличия глобальных линейных ограничений (8), (9).

Глава 4 содержит теоретическое исследование, посвящённое различным вопросам, связанным с максимизацией нижней оценки, возникающей при субмодулярной релаксации. В разделе 4.1 рассматриваются теоретические свойства точки максимума двойственной функции £>(А). В подразделе 4.1.1 формулируются условия сильной и слабой согласованности, которые характеризуют значения двойственных переменных Л, а также доказываются несколько свойств точек, удовлетворяющих этим условиям. В частности, показывается, что сильная согласованность влечёт за собой слабую, и точка максимума двойственной

"Потенциал 9с, С 6 С называется перестановочным потенциалом Поттса (регал^ес! Р"-Ро«з), если он равен О на всех конфигурациях, кроме заданных множеством Т>с, на которых он принимает отрицательные значения, и выполнено условие

ч<£, л" е : <г' Ф <*" => < Ф ы е с,

характеризующее достаточную степень «разреженности» потенциалов.

11

функции удовлетворяет свойству слабой согласованности. В подразделе 4.1.2 приводятся три ситуации, возможные в точке максимума двойственной функции D(X):

1. в точке максимума двойственной функции D(А) выполнено условие сильной согласованности, а значит, субградиент, вычисленный по правилу (7), является нулевым вектором. В этом случае подход SMR позволяет найти и значение глобального минимума энергии (1), и разметку переменных, на которых оно достигается;

2. в точке максимума двойственной функции D{А) условие сильной согласованности не выполнено, и не удаётся проверить, является ли нулевой вектор субградиентом. Тем не менее, глобальный минимум энергии (1) совпадает с максимумом двойственной функции D{Л), а значит, в этой ситуации подход SMR позволяет найти значение глобального минимума энергии, но не конфигурацию переменных, на которых оно достигается;

3. в точке максимума двойственной функции D(X) условие сильной согласованности не выполнено, нулевой вектор не является субградиентом, глобальный минимум энергии (1) не совпадает с максимумом двойственной функции D(X). В этой ситуации подход SMR позволяет найти не значение глобального минимума энергии, а лишь нижнюю оценку на него.

В разделе 4.2 рассматривается возможность применения различных методов выпуклой оптимизации для максимизации двойственной функции D(Л). Приведённый анализ описывает способ применения для этой задачи следующих методов:

1. методы субградиентного подъёма18;

2. методы пучков субградиентов (bundle methods)19;

3. алгоритм BFGS для негладких функций.20

I8N. Komodakis, N. Paragios, G. Tziritas, MRF Energy Minimization and Beyond via Dual Decomposition, IEEE

Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 33, no. 3, pp. 531-552, 2011.

"J. Kappes, В. Savchynskyy, С. Schnorr, A Bundle Approach To Efficient MAP-Inference by Lagrangian Relaxation,

IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012.

20A. S. Lewis, M. L. Overton, Nonsmooth optimization via quasi-Newton methods. Mathematical Programming, vol.

141,no. 1-2, pp. 135-163,2013.

В разделе 4.3 приводится алгоритм покоординатного подъёма для поиска наилучшей нижней оценки глобального минимума энергии (1) из семейства, построенного при помощи подхода БМБ.

Рассмотрим текующее значение двойственных переменных Xм. Рассмотрим все мин-маргиналы21 по переменным у лагранжиана (6) в точке Х"ы\ ММ^кЬ (у, Хш) = тт{уе(5% 1у.р=к} Ь (у, Xм), к £ {0,1}, г е V, р £ V.

Выберем некоторую вершину £ Уи обозначим разность мин-маргиналов за 0 и за 1 через ¿¿: 5>р = ММ^Ь(у,ХоЫ) - ММшЬ(у, Xм), р £ V. Пусть д3^ - максимальное из чисел 6?р, р £ V, 53^ - следующее наибольшее число (второй максимум); р^ и р^р - соответствующие индексы (аргмаксиму-мы): р{р = а^тахреР<^, 53{1) = 53(1), р\;.2) = а^тахреЛ{ра)} 53{2) = 53{?). Построим новое значение Хпеш двойственных переменных Л по следующему правилу:

{\?й + А1, 1=3, хпеШ = ) * 3> (}9)

иначе.

Здесь г £ V, а А,- любое число из отрезка (возможно состоящего из одной точки)

с к, а ijj

Теорема 9. Итерационный процесс (19), пересчитывающий значения двойственных переменных X, обладает следующими свойствами:

1. На каждой итерации процесса (19) нижняя оценка .О (А) не убывает.

2. Если для вершины 3 £ V выполнено либо 63^ < 0, либо б3^ > 0, то применение пересчёта (19) приведет к строгому возрастанию нижней оценки 1?(А).

3. Неподвижная точка процесса (19) удовлетворяет условию слабого согласования;

4. Если для вершины j £ V значение 0 принадлежит отрезку то данная точка является максимумом нижней оценки по переменной А^

2|Мин-маргиналом функции дискретных переменных F(z), z = {¿i}£Li, = l,...,K, соответствующим переменной z» и значению h, назовём минимальное значение функции F(z), достигаемое на конфигурациях, в которых переменная zt принимает значение к:

MMikF(z)= min F(z).

' х: Zi=k

Следствием теоремы 9 является то, что неподвижная точка процесса (19) является покоординатным максимумом нижней оценки D(Л). Полученный алгоритм покоординатного подъёма сходится к точке слабого согласования очень быстро. Тем не менее, в большинстве случаев двойственные функции обладают большим количеством покоординатных максимумов, что приводит к тому, что метод может сходится к низкому значению нижней оценки. На практике этот метод может быть использован в комбинации с другими методами оптимизации для предотвращения осцилляций и гарантированного получения точки слабого согласования.

В разделе 4.4 рассматривается вопрос построения решения задачи минимизации энергии (1) при использовании подхода SMR для максимизации двойственной функции D(А). Существует несколько вариантов постановки данной задачи:

1. построение дробного целостного решения (построение решения задачи линейного программирования (15)-(18), минимум которой равен наилучшей нижней оценке, достижимой в рамках подхода SMR);

2. построение целочисленного частичного решения, обладающего свойством частичной оптимальности;

3. построение целочисленного решении в ситуации, когда зазор между прямой и двойственной задачами равен 0.

4. построение, вообще говоря, не оптимального целочисленного решения в общем случае.

Постановка 1 рассматривается в подразделе 4.4.1. Оказывается, что если максимизацию функции D(А) проводить при помощи методов субградиентного подъёма, то искомое решение можно получить при помощи взвешенной суммы субградиентов с разных итераций метода и последующей, так называемой, оптимизирующей проекции.22

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

22В. Savchynskyy, S. Schmidt, Getting Feasible Variable Estimates From Infeasible Ones: MRF Local Polytope Study, in proceedings of the Workshop on Inference for Probabilistic Graphical Models at ICCV, 2013.

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

В подразделе 4.4.3 рассматривается задача построения целочисленного решения в ситуации, когда зазор между прямой и двойственной задачами равен 0. В рамках настоящей работы показывается, что в некоторых частных случаях, если зазор равен 0, то решение задачи (3)-(5) может быть найдено. Теорема 10 содержит один из результатов этой группы.

Теорема 10. Пусть точка Л° удовлетворяет условию слабого согласования и ■y0 = arg minye(5) L(y, А0). Пусть для некоторой метки р G V выполнены вложения Free(q, А0) С Free(p, А0),23 где q е V \ {р}. Тогда разметка

1, j е Free(r, А0), г = р, 0, j € Free(r, А0), г ^ р,

у°г, иначе,

является решением задачи (3)-(5).

В подразделе 4.4.4 рассматривается 4-й вариант постановки задачи поиска решения прямой задачи. В рамках данной работы предложен эвристический алгоритм, представляющий собой разновидность алгоритма блочно-координатного спуска и позволяющий строить некоторое целостное и целочисленной, но, вообще говоря, не оптимальное решение задачи (3)-(5).

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

В разделе 5.1 описан эксперимент, преследующий две цели: 1. исследование работы различных методов оптимизации двойственной функции (раздел 4.2), построенной при помощи варианта БМИ для ассоциативных парно-сепарабельных энергий - алгоритма Б МБ (раздел 2.1);

23 Через Fгee(p, Л), р е V, обозначено подмножество множества вершин V, содержащее все вершины ] е V, такие что мин-маргиналы лагранжиана (6) по переменной за метки 0 и 1 совпадают.

2. сравнение работы алгоритма SMD и известного алгоритма двойственной декомпозиции, основанного на разложении графа энергии на деревья -алгоритма DD TRW. Для достижения цели 1 в рамках данного эксперимента рассматривались следующие методы оптимизации нижней оценки: субградиентный подъём с адаптивным размером шага, метод пучков субградиентов с ограниченным размером пучка, метод пучков субградиентов с усреднением пучка, комбинированный метод пучков (алгоритм LMBM24), негладкий вариант алгоритма BFGS.

Сравнение различных схем построения нижних оценок с использованием релаксации Лагранжа (например, SMD и DD TRW) осложнено тем, что работоспособность каждой из схем существенно зависит от метода оптимизации, используемого для максимизации соответствующей нижней оценки. Исходя из этой трудности, для достижения цели 2 для алгоритма DD TRW были применены все методы оптимизации, использованные и для SMD. Сравнение также проводилось относительно алгоритма TRW-S,25 максимизирующего нижнюю оценку при помощи передачи сообщений.

Эксперименты данного раздела проводились на задачах минимизации энергий, построенных по реальным данным Алахари и др.26 Были использованы задачи двух видов: семантическая многоклассовая сегментация (5 задач, см. рис. 1а-в) и выровненное стерео-сопоставление (4 задачи, см. рис. 1г-е). Из проведённого эксперимента можно сделать следующие выводы: 1. все рассмотренные методы оптимизации нижних оценок (как для SMD, так и для DD TRW) при правильном выборе параметров показывают похожие результаты; часть методов менее чувствительна к выбору параметров, часть - более; метод LMBM показал себя наименее чувствительным к выбору параметров и часто достаточно эффективным, а значит может быть рекомендован для использования на практике;

24N. Haarala, К. Miettinen, М. М. Makela, Globally Convergent Limited Memory Bundle Method for Large-Scale

Nonsmooth Optimization, Mathematical Programming, vol. 109, no. 1, pp. 181-205, 2007.

25V. Kolmogorov, Convergent Tyee-reweighted Message Passing for Energy Minimization, IEEE Transactions on

Pattern Analysis and Machine Intelligence (PAMI), vol. 28, no. 10, pp. 1568-1583, 2006.

26K. Alahari, P. Kohli, P. H. S Torr, Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs, IEEE

Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 32, no. 10., pp. 1846-1857, 2010.

■1 «ЖЩШШШябтЩШ -. л-:!',-;',,. * 1 ¡INnl 11 ¡8 ¡¡¡¡я ¡¡И ¡¡В Ш -1 1 к * ■ "3* sfc: • ЩЩ рщ ' 1 В I si

КВН - §flШЬШ^Ш ШШЩЛЩ;! г ' L ' - 4

Рис. 1: Данные для эксперимента по сравнению различных методов оптимизации, используемых в рамках подхода SMD, и по сравнению подхода SMD с подходом DD TRW. Использовались задачи двух типов: семантическая сегментация изображений и стереосопоставление. Входом задачи семантической сегментации является изображение (а), выходом - разметка пикселей изображения на классы: (б) - правильный ответ, (в) - разметка, полученная в рамках подхода SMD. Входом задачи стереосопо-ставления является пара изображений, снятых при помощи расположенных рядом камер ((г) - одно из изображений), выходом - карта горизонтальных смещений пикселей левого изображения, относительно правого: (д) - правильный ответ, (е) - разметка, полученная в рамках подхода SMD.

2. алгоритмы, основанные на подходе SMD работают в целом быстрее, чем алгоритмы, основанные на подходе DD TRW; скорее всего, это вызвано тем фактом, что максимизации нижних границ SMR происходят в пространствах намного меньших размерностей;

3. в ситуациях, когда в исходной задаче мало меток, алгоритмы, основанные на SMD, работают быстрее стандартного метода TRW-S; скорее всего, это вызвано тем, что в этом случае ограничения целостности оказывают меньшее влияние на оптимальное решение.

В разделе 5.2 описан эксперимент, оценивающий применимость подхода SMR для энергий с потенциалами высоких порядков, а также по сравнению подхода SMR с подходом CWD. Эксперимент проводился как на модельных, так и на реальных задачах. Исходя из проведённого эксперимента можно сделать несколько выводов. Во-первых, алгоритм, максимизирующий нижнюю оценку SMR, сходится быстрее, чем алгоритм, максимизирующий нижнюю оценку CWD. Во-вторых, применение алгоритма ICM (раздел 4.4) для получения

17

прямых решений не существенно улучшает текущее значение энергии в случае SMR, и существенно - в случае CWD.

Раздел 5.3 посвящен экспериментальному исследованию применимости алгоритма NSMR для случая неассоциативных парно-сепарабельных энергий. В рамках данного эксперимента на модельных данных проводится сравнение подхода NSMR с аналогами DD TRW и TRW-S. Рельтаты эксперимента показывают, что алгоритм TRW-S находит наилучшие нижние оценки на начальных итерациях, но после этого застревает в покоординатных максимумах, т. е. не сходится к глобальным максимумам нижних оценок. Плохие результаты DD TRW могут быть объяснены тем, что число переменных в нижней оценке DD TRW в 10 раз больше, чем число переменных в нижней оценке NSMR. Тем не менее, возможно, алгоритм DD TRW можно улучшить за счёт использования другой схемы разбиения графа энергии на подграфы-деревья.

Раздел 5.4 посвящён экспериментам с подходом SMR, в которых проверяется возможность учёта глобальных ограничений. Подраздел 5.4.1 содержит сравнение на модельных данных подхода SMR с аналогами: вариантом алгоритма MPF,27 (задача разбивается на две подзадачи: первая - задача минимизации энергии без ограничений, вторая - транспортная задача, обеспечивающая учёт ограничений), алгоритмом GTRW (вложенный итерационный процесс, где на внутренних итерациях решается задача без ограничений, а на внешних осуществляется её согласование с ограничениями при помощи их релаксации Лагранжа). По результатам данного эксперимента можно сделать вывод, что все методы сходятся к одной точке, но алгоритм, основанный на подходе SMR, делает это намного быстрее.

В рамках подраздела 5.4.2 проводится демонстрация применимости подхода SMR с глобальными ограничениями на нескольких реальных задачах: сегментация изображений с ограничением «звёздности» формы и ограничением на площадь объекта, сегментация магнитограмм Солнца с ограничением равенства потоков магнитных полей через разные сегменты.

270. J. Woodford, С. Rother, V. Kolmogorov, A global perspective on MAP inference for tow-level vision. International Conference on Computer Vision (ICCV), 2009.

Заключение

Основные результаты данной работы заключаются в следующем:

1. Разработан новый подход к решению задачи минимизации энергий: субмодулярная релаксация (SMR). Подход SMR основан на релаксации Лагранжа ограничений целостности. Основное отличие подхода SMR от существующих методов, основанных на релаксации Лагранжа и двойственной декомпозиции (DD TRW, CWD), состоит в том, что не происходит разбиение графа задачи на подграфы.

2. Проведено теоретическое исследование подхода SMR. Приведена точная формулировка линейной релаксации, значение решения которой равно максимуму нижней оценки SMR. Доказано, что в случае парно-сепарабельных энергий с ассоциативными парными потенциалами построенная линейная релаксация эквивалентна стандартной (решаемой DD TRW). Также показано, что в случае перестановочных потенциалов Поттса высоких порядков построенная линейная релаксация эквивалентна релаксации, решаемой методом CWD.

3. Исследован вопрос применимости различных методов выпуклой оптимизации для решения задачи поиска наилучшей нижней оценки на глобальный минимум энергии из семейства оценок, построенных подходом SMR. Разработан алгоритм покоординатного подъёма, обеспечивающий монотонное улучшение оценки в случае парно-сепарабельных ассоциативных потенциалов.

4. Проведено экспериментальное исследование подхода SMR, включающее в себя его сравнение с аналогами: DD TRW, CWD, TRW-S. Показано, что в ряде случаев алгоритм SMR превосходит аналоги по скорости работы. Также показана возможность учёта некоторых видов глобальных ограничений в рамках подхода SMR.

Публикации автора по теме диссертации

Публикации из списка ВАК

1. Delong A., Osokin A., Isack Н. N., Boykov Y. Fast Approximate Energy Minimization with Label Costs // IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2010.

2. Delong A., Osokin A., Isack H. N.. Boykov Y. Fast Approximate Energy Minimization with Label Costs // International Journal of Computer Vision (IJCV). 2012. Vol. 96, no. 1. P. 1-27.

3. Delong A., Veksler 0., Osokin A., Boykov Y. Minimizing Sparse High-Order Energies by Submodular Vertex-Cover // Advances in Neural Information Processing Systems (NIPS). 2012.

4. Kohli P., Osokin A., Jegelka S. A Principled Deep Random Field Model for Image Segmentation // IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2013.

5. Kropotov D., Laptev D., Osokin A., Vetrov D. Variational segmentation algorithms with label frequency constraints // Pattern Recognition and Image Analysis. 2010. Vol. 20. P. 324-334.

6. Osokin A., Vetrov D. Submodular Relaxation for MRFs with High-Order Potentials // Computer Vision - ECCV 2012. Workshops and Demonstrations / Ed. by A. Fusiello, V. Murino, R. Cucchiara. Vol. 7585 of Lecture Notes in Computer Science. 2012. P. 305-314.

7. Osokin A., Vetrov D., Kolmogorov V. Submodular Decomposition Framework for Inference in Associative Markov Networks with Global Constraints // IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2011.

Прочие публикации

8. Осокин А. А., Ветров Д. П. Решение задач оптимизации на марковских случайных полях с помощью разложения, сохраняющего структуру графа // Доклады 15-ой Всероссийской конференции «Математические методы распознавания образов». 2011. С. 207-210.

9. Kropotov D., Laptev D., Osokin A., Vetrov D. Signal Segmentation with Label Frequency Constraints using Dual Decomposition Approach for Hidden Markov Models // Intellectualization of information processing (IIP). 2010. P. 403-406.

10. Vetrov D., Osokin A. Graph Preserving Label Decomposition in Discrete MRFs with Selfish Potentials // NIPS Workshop on Discrete Optimization in Machine learning (DISCML NIPS). 2011.

11. Vetrov D., Osokin A. Submodular Decomposition Approach for Inference in Markov Random Fields // Intellectualization of information processing (IIP). 2010. P. 5-8.

Напечатано с готового оригинал-макета

Подписано в печать 25.03.2014 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 80 экз. Заказ 049.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики

На правах рукописи

04201457615

Осокин Антон Александрович

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель: к.ф.-м.н. Д. П. Ветров

Москва - 2014

Содержание

Введение..............................................................................................4

1 Задача минимизации дискретных энергий ..............................................11

1.1 Нотация и постановка задачи ............................................................11

1.2 Энергии и марковские случайные поля..................................................13

1.3 Методы минимизации энергии ..........................................................14

1.3.1 Частные случаи, допускающие точные решения ..............................15

1.3.2 Приближённые алгоритмы........................................................24

2 Субмодулярная релаксация..................................................................38

2.1 Парно-сепарабельные ассоциативные энергии..........................................38

2.2 Энергии с потенциалами высоких порядков ............................................40

2.3 Несубмодулярный лагранжиан............................................................43

2.4 Линейные глобальные ограничения......................................................45

3 Точность нижних оценок ....................................................................47

3.1 Вспомогательные леммы..................................................................47

3.2 Парно-сепарабельные ассоциативные энергии..........................................51

3.3 Энергии с потенциалами высоких порядков ............................................54

3.3.1 Перестановочные потенциалы Поттса............................................55

3.4 Произвольные парно-сепарабельные энергии ..........................................57

3.5 Линейные глобальные ограничения......................................................58

4 Максимизация нижних оценок..............................................................59

4.1 Теоретические свойства точек максимума ..............................................59

4.1.1 Условия сильной и слабой согласованности ....................................59

4.1.2 Зазор между прямой и двойственной задачами ................................61

4.2 Методы оптимизации для решения двойственной задачи..............................63

4.3 Максимизация двойственной функции на основе мин-маргиналов ..................67

4.4 Построение решения прямой задачи ....................................................73

4.4.1 Построение целостного дробного решения ....................................74

4.4.2 Частичная оптимальность ........................................................77

4.4.3 Построение прямого решения при нулевом зазоре ............................78

4.4.4 Построение прямого решения в общем случае ................................81

5 Экспериментальное сравнение..............................................................83

5.1 Парно-сепарабельные ассоциативные энергии..........................................83

5.2 Энергии с потенциалами высоких порядков ............................................88

5.3 Произвольные парно-сепарабельные энергии ..........................................91

5.4 Глобальные ограничения..................................................................94

5.4.1 Сравнение с аналогами............................................................94

5.4.2 Применимость метода на реальных данных ....................................96

Заключение.............................................101

Список рисунков..........................................106

Список таблиц...........................................107

Литература .............................................108

А Потоки и разрезы в сетях..................................120

Введение

В рамках данной диссертационной работы разработан новый подход к решению задачи поиска наиболее вероятных конфигураций марковских случайных полей: субмодулярная релаксация (submodular relaxation, SMR). Проведено теоретическое и экспериментальное исследование предложенного подхода, а также сравнение его с аналогами.

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

Большинство задач распознавания заключается в предсказании неизвестных величин на основе наблюдаемых. Можно выделить два типа задач распознавания, связанных со структурированными данными:

1. предсказания всех ненаблюдаемых величин осуществляются независимо;

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

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

изображений (сопоставление метки класса каждому пикселю), отслеживание (трекинг) объекта на видео, восстановление произнесённой фразы по звукозаписи, и т. д.

В решении задач первого типа в настоящее время доминируют нейронные сети нового поколения [83, 48] (глубинное обучение, deep learning). Данная парадигма делает попытку получить по данным признаковое описание, содержащее представление внутренних закономерностей. Методы, основанные на глубинном обучении, показывают лучшие на сегодняшний день результаты при решении большого числа прикладных задач (например, для задачи классификации изображений по самой большой открытой базе изображений ImageNet [75]).

Для решения задач второго типа большой популярностью пользуется аппарат, так называемых, графических моделей [20, 129]. Данный подход делает попытку напрямую моделировать закономерности данных, затрагивающие как признаковое описание, так и результат распознавания. Обычно под графической моделью понимается вероятностная модель, задающая совместное распределение большого количества переменных, структура зависимостей в котором задаётся при помощи графа или гиперграфа. Важным отличием методов, относящихся к графическим моделям, от методов для решения задач типа 1 является то, что сложной является не только задача обучения модели (настройка параметров по наблюдаемым данным), но и задача распознавания нового объекта по уже обученной модели.

Один из наиболее популярных подходов к математической формулировке и решению задачи распознавания второго типа основан на поиске моды совместного апостериорного распределения неизвестных переменных (maximum a posteriori estimation, MAP-inference). Задача поиска моды является задачей оптимизации (либо непрерывной, либо дискретной). Часто распределение представляет собой произведение большого числа множителей - факторов, и работать с ним в таком виде неудобно. В этом случае берут отрицательный логарифм апостериорного распределения и переходят к эквивалентной задаче минимизации. Минимизируемую функцию обычно называют энергией! Несмотря на то что задача минимизации энергии в общем случае является NP-трудной [113], на практике её приближённые решения получать существенно проще, чем, например, приближённо вычислять апостериорные маргинальные распределения.

Задачи минимизации энергии часто возникают в качестве подзадачи при решении задачи настройки параметров модели по наблюдаемым данным. Наиболее известным методом, в котором возникает подзадача минимизации энергии, является структурный метод опорных векторов (structured support vector machine, SSVM) [122, 124]. SSVM часто используется на практике для решения задач второго типа, т. к. в ряде случаев превосходит альтернативные методы как по качеству, так и по скорости работы [95, 100].

1 Термин энергия используется из-за связи с понятием потенциальной энергии из статистической физики [92].

В рамках данной работы изучается задача минимизации энергии, в которой, во-первых, все переменные энергии дискретны (задача минимизации энергии является задачей дискретной оптимизации), и, во-вторых, существует компактное представление энергии в виде суммы слагаемых, каждое из которых зависит от небольшого числа переменных (опр. 1.1). Задачам минимизации таких энергии уделяется внимание как отечественными [8, 2, 3, 4, 9], так и зарубежными учёными (например, в работах [21, 54]).

Задача минимизации энергии дискретных переменных появилась достаточно давно: в отечественной литературе она исследовалась ещё в 70-х в работах М. И. Шлезингера [8]. В западной литературе первые работы (из известных автору) появились в начале 80-х: Гиман и Гиман [41], Блейк и Циссерман [21] сформулировали задачу именно в том виде, в котором она часто рассматривается сейчас, а также предложили алгоритм имитации отжига (simulated annealing) для её решения. Вехой в развитии данной задачи стали работы Перла [99], в которых были сформулированы алгоритмы передачи сообщений и оформилось понимание того, что если граф энергии не содержит циклов, то задача может быть решена точно за полиномиальное время.

Важный класс функций, допускающих минимизацию за полиномиальное время, - субмодулярные функции бинарных переменных - был известен среди специалистов по дискретной оптимизации ещё в 60-х годах [46]. В конце 80-х годов Грейг [44] и др. впервые использовали подход, основанный на минимизации энергии при помощи построения минимальных разрезов графов, в задаче подавления шума на бинарных изображениях. В начале 00-х годов работы Бой-кова и др. [24, 26], Колмогорова и Заби [68] положили начало активному использованию разрезов графов в компьютерном зрении. В качестве примеров задач, решаемых при помощи минимизации энергии, можно привести стерео-сопоставление [24], сегментацию изображений [26, 114], восстановление неизвестных областей изображения (inpainting) [94], сегментацию трёхмерных объектов [85, 12]. По мере роста числа приложений подхода происходил рост и размеров задач, и сложности используемых потенциалов. Например, для задачи сегментации изображений было разработано большое число потенциалов, позволяющих учитывать сложные высокоуровневые свойства объектов [61, 86, 93, 88].

Наиболее изучена задача минимизации в случае парно-сепарабельпых энергий, т. е. энергий, являющихся суммами слагаемых, зависящих не более чем от двух переменных. Экспериментальные исследования [120, 54] показывают, что для случая парно-сепарабельных энергий существует большое число алгоритмов, позволяющих решать многие практические задачи с требуемой точностью. В случае же не парно-сепарабельных энергий (энергий с потенциалами, зависящими от более 2-х переменных) арсенал существующих методов гораздо более скромен. Существующие методы либо позволяют минимизировать потенциалы очень специальных ви-

дов [61, 32, 80], либо работают недостаточно быстро [104, 71], либо обладают одновременно обоими недостатками [86, 93].

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

Методы исследования. Для достижения поставленной цели был выбран подход, основанный на релаксации Лагранжа ограничений, затрудняющих решение задачи. Частным случаем этого подхода является двойственная декомпозиция (dual decomposition), применённая для задач минимизации энергии в работах Комодакиса и др.[73, 71], Вудфорда и др. [135], Зонтага и др. [117]. В настоящей диссертации используется вариант релаксации Лагранжа, выходящий за рамки двойственной декомпозиции. Также для разработки метода активно используются алгоритмы построения разрезов графов [23] и их динамических расширений [59]. Основные положения, выносимые на защиту:

1. Новый подход для решения задачи минимизации энергии: субмодулярная релаксация.

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

3. Алгоритм покоординатного подъема для максимизации нижней оценки, построенной в рамках подхода субмодулярной релаксации, применимый в случае ассоциативных парно-сепарабельных энергий.

4. Экспериментальное исследование всех разработанных методов, содержащее их сравнение с существующими аналогами.

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

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

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

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

Степень достоверности. Достоверность результатов обеспечивается доказательствами теорем и подробными описаниями экспериментов, допускающими воспроизводимость.

Апробация работы. Результаты настоящей работы неоднократно докладывались на семинаре группы байесовских методов машинного обучения кафедры математических методов прогнозирования, ВМК МГУ, а также докладывались на следующих конференциях:

1. Международная конференция по компьютерному зрению и распознаванию образов (Computer Vision and Pattern Recognition, CVPR), 2010. [31]

2. Международная конференция «Интеллектуализация обработки информации» (ИОИ), 2010. [128, 77]

3. Международная конференция по компьютерному зрению и распознаванию образов (Computer Vision and Pattern Recognition, CVPR), 2011. [97]

4. Всероссийская конференция «Математические методы распознавания образов» (ММРО), 2011.[7]

5. Международная конференция «Системы обработки нейроинформации» (Neural Information Processing Systems, N1PS), секция «Дискретная оптимизация в машинном обучении» (discrete optimization in machine learning, DISCML), 2011. [127]

6. Международная конференция «Системы обработки нейроинформации» (Neural Information Processing Systems, N1PS), 2012. [33]

7. Европейская конференция по компьютерному зрению (European Conference on Computer Vision, ECCV), секция «Модели высоких порядков и глобальные ограничения в компьютерном зрении» (Higher-Order Models and Global Constraints in Computer Vision), 2012. [96]

8. Международная конференция по компьютерному зрению и распознаванию образов (Computer Vision and Pattern Recognition, CVPR), 2013. [64]

Публикации. Основные результаты по теме диссертации изложены в 11 печатных изданиях [7, 31, 32, 33, 64, 76, 77, 96, 97, 127, 128], 7 из которых входят в список изданий, рекомендованных ВАК [31, 32, 33, 64, 76, 96, 97], 4 - сборники докладов конференций [7, 77, 127, 128]. Отдельные результаты настоящей работы включались в отчёты по проектам РФФИ 08-01-00405, 12-01-31254, 12-01-00938, 12-01-33085, и по проекту М1С 3827.2010.9.

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

Объём и структура работы. Диссертация состоит из оглавления, введения, пяти глав, заключения, списка иллюстраций (19 п.), списка таблиц (2 п.), списка литературы (139 п.) и одного приложения. Общий объём работы составляет - 121 стр.

Краткое содержание работы по главам.

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