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

• Автор: Осокин, Антон Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 121 с. : ил.

Содержание
Введение
1 Задача минимизации дискретных энергий
1.1 Нотация и постановка задачи
1.2 Энергии и марковские случайные поля
1.3 Методы минимизации энергии
1.3.1 Частные случаи, допускающие точные решения
1.3.2 Приближённые алгоритмы
2 Субмодулярная релаксация
2.1 Парно-сепарабельные ассоциативные энергии
2.2 Энергии с потенциалами высоких порядков
2.3 Несубмодулярный лагранжиан
2.4 Линейные глобальные ограничения
3 Точность нижних оценок
3.1 Вспомогательные леммы
3.2 Парно-сепарабельные ассоциативные энергии
3.3 Энергии с потенциалами высоких порядков
3.3.1 Перестановочные потенциалы Поттса
3.4 Произвольные парно-сепарабельные энергии
3.5 Линейные глобальные ограничения
4 Максимизация нижних оценок
4.1 Теоретические свойства точек максимума
4.1.1 Условия сильной и слабой согласованности
4.1.2 Зазор между прямой и двойственной задачами
4.2 Методы оптимизации для решения двойственной задачи
4.3 Максимизация двойственной функции на основе мин-маргиналов

4.4 Построение решения прямой задачи
4.4.1 Построение целостного дробного решения
4.4.2 Частичная оптимальность
4.4.3 Построение прямого решения при нулевом зазоре
4.4.4 Построение прямого решения в общем случае
5 Экспериментальное сравнение
5.1 Парно-сепарабельные ассоциативные энергии
5.2 Энергии с потенциалами высоких порядков
5.3 Произвольные парно-сепарабельные энергии
5.4 Глобальные ограничения
5.4.1 Сравнение с аналогами
5.4.2 Применимость метода на реальных данных
Заключение
Список рисунков
Список таблиц
Литература
А Потоки и разрезы в сетях

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

1.3.2.2.3. Двойственная декомпозиция для случая потенциалов высоких порядков.
Комодакис и др. [71] исследовали возможность применения подхода двойственной декомпозиции для минимизации энергий с потенциалами высоких порядков (1.1).
Наиболее простым способом использования подхода двойственной декомпозиции является введение подзадач на каждый из потенциалов высоких порядков. Аналогично разделу 1.3.2.2.2 можно получить нижнюю оценку на глобальный минимум энергии:
min Е(у) = min Е ( 9с(у°) + Е Е 0,РУ°/С{г у {у [^с, ,у :C(iC j£C

= mm max {ус},у‘ }
Е 9^ус)+ЕЕд^Л/ic(oi + Е Е Е х^<гЛ - у*)
I CSC »SC pep ) isv pep CsC(i) >
^,vaxi,!с1п. E °c(yc) + EEVip(M/ic(*)i + Kc) -ЕЕ E к,су:р
t .p,cMv },y yCeC i<=c per } tsv pep cec(i) у
= max. ( ^c(2/C) + E E (MIC(0I + Ai|C) )
IV.cT {Vе} V ‘—t t—L
хч.с=0 A izcpep /
max D(A) (1.39)
{>*ip,cY-Hc4C(i) ^ip,c=
Необходимым условием работы с нижней оценкой энергии (1.39) является возможность эффективно решать задачи минимизации, возникающие при вычислении нижней оценки 79(A) при фиксированных множителях Лагранжа А. Данные задачи имеют вид суммы одного потенциала высокого порядка и унарных потенциалов:
mill ( 9с(хс) + ЕМО ) • С1-40)
хсеАс V 7tc )
Если порядок потенциалов небольшой, то задачи (1.40) можно решать при помощи полного перебора.
При порядках потенциалов, когда перебор становится вычислительно неприемлем, возникает проблема хранения потенциалов в памяти. Необходимо некоторое компактное представление, требующее значительно меньше памяти, чем задание таблицей. Одним из способов такого компактного задания является задание значения по умолчанию и небольшого числа значений в выделенных конфигурациях. Такие потенциалы были независимо рассмотрены в работах [104, 71] и названы разреженными (sparse) и заданным шаблонами (pattern-based).
Будем говорить, что потенциал 9с задан шаблонами, если он принимает ненулевые значения только на заранее выделенном множестве конфигураций переменных Т>с С Хс, а в осталь-