Методы структурного обучения в задачах совместной разметки

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

Содержание
Введение

1 Ненаправленные графические модели и структурное обучение

1.1 Марковские сети и связанные задачи

1.2 Алгоритмы вывода МАР-оценки

1.2.1 Как задача математического программирования

1.2.2 Передача сообщений

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

1.2.4 Разрезы на графах

1.3 Обучение марковских сетей

1.3.1 Максимизация правдоподобия и его приближений

1.3.2 Максимизация отступа
1.3.3 Обучение нелинейных моделей
2 Использование различных типов аннотации обучающей выборки
2.1 Обучение со слабыми аннотациями
2.1.1 Обобщённый БЭУМ
2.1.2 Обобщённый БЗУМ и максимизация неполного правдоподобия
2.2 Типы аннотаций для обучения сегментации изображений
2.2.1 Обучение сегментации по полной разметке
2.2.2 Учёт аннотации метками изображений
2.2.3 Плотные рамки
2.2.4 Зёрна объектов
2.3 Обучение категоризации документов по слабой аннотации
2.4 Обзор литературы
2.5 Эксперименты
2.5.1 Наборы данных, детали реализации, критерии качества
2.5.2 Метки изображений
2.5.3 Добавление рамок и зёрен
2.5.4 Категоризация документов
2.6 Выводы
3 Структурное обучение неассоциативных марковских сетей
3.1 Неассоциативная марковская сеть для сегментации облаков точек

3.2 Функция потерь для несбалансированных категорий
3.3 Нелинейные ядра
3.3.1 Двойственная формулировка структурного 8УМ
3.3.2 Ядровой переход
3.4 Обзор литературы
3.5 Эксперименты
3.5.1 Детали реализации
3.5.2 Наборы данных
3.5.3 Результаты
3.5.4 Обсуждение
3.6 Выводы
4 Использование пространственного контекста при последовательной классификации
4.1 Машина вывода
4.2 Пространственная машина вывода
4.2.1 Описание модели и вывода в ней
4.2.2 Пространственные и структурные д-факторы
4.2.3 Обучение модели
4.3 Детали реализации
4.3.1 Структура модели
4.3.2 Обучение предикторов сообщений и их признаки
4.4 Обзор литературы
4.5 Результаты экспериментов
4.5.1 Данные и постановка эксперимента
4.5.2 Качество сегментации
4.5.3 Вычислительная сложность и число итераций
4.5.4 Анализ пространственных типов факторов
4.6 Выводы
Заключение
Список рисунков
Список таблиц
Список алгоритмов
Литература

Введение
Задачей машинного обучения с учителем является восстановление функциональной зависимости между случайными величинами X и ¥ по обучающей выборке {{х3, у3)}'’= ■ В классической постановке задачи У является скалярной случайной величиной, а пары (х3, у3) получаются независимой выборкой из генеральной совокупности. Это позволяет прогнозировать значение у лишь по соответствующему значению х. Однако во многих практических задачах это предположение о независимости не выполняется. Тогда моделирование зависимости между реализациями У позволяет повысить качество предсказания. Для этого необходимо принимать решение о значениях у3 совместно. Приведём несколько примеров таких задач из разных областей.
Компьютерное зрение. Одной из центральных задач компьютерного зрения является семантическая сегментация — одновременное распознавание категорий объектов сцены и их сегментация [1, §14.4.3]. В семантической сегментации изображений каждому пикселю изображения назначается одна из семантических категорий [2-4]. В семантической сегментации облаков точек, полученных лазерным сканированием или сшиванием карт глубины, каждой точке поверхности ставится в соответствие метка категории [5,6]. При этом категории представляют собой сущности реального мира, такие как ‘земля’, ‘небо’, ‘велосипед’, ‘стол’, ‘книга’, и т.д. Соседние пиксели или точки могут быть предварительно сгруппированы в суперпиксели. Получение качественной семантической сегментации — значительный шаг к решению задачи понимания сцены. В данной работе эксперименты проводятся в основном с семантической сегментацией.
Родственной является задача оценки геометрии сцены по одному изображению [6, 7]. Предполагается, что оно представляет собой фотографию городской сцены, где могут присутствовать земля и небо, а между ними находятся в основном вертикальные поверхности, такие как стены домов. Каждому пикселю изображения необходимо сопоставить метку одной из категорий ‘земля’, ‘небо’, ‘вертикаль’. Подобная информация позволяет делать выводы о трёхмерной геометрии сцены и помогает решать более высокоуровневые задачи, такие как распознавание пешеходов или пострение трёхмерной модели сцены.
Другая задача — определение диспаритетов пикселей через поиск соответствий в стереопаре — паре изображений, снятых с соседних ракурсов [8]. При определённых условиях найденные диспаритеты можно использовать для однозначного определения глубины точек сцены.

Субградиентные методы оптимизации
Целевую функцию (1.60) можно оптимизировать и напрямую. Она является выпуклой, но недифференцируемой. Поэтому можно применить метод субградиентного спуска. Субградиент может быть вычислен по формуле:

Э к(’И') = [^(у^ш)^) - ^(у^х5)] , (1.65)

где у3[у^) = а^таХу^ {Д(у;у^) + при текущем значении у. Инициализировав
вектор параметров некоторым значением те-0, метод итеративно обновляет его значения по формуле
чу"+1 = луп-7п§(зу"), (1.66)
где 7П — убывающий размер шага. Поскольку целевая функция выпукла, существует такая последовательность {7при которой оптимизация сходится к глобальному оптимуму. В частности, достаточно, чтобы 7„ —> 0, но 22=0уп 1 оо [53]. Например, такому свойству
удовлетворяет последовательность 7„ = В практических задачах важна скорость сходимости, которая сильно зависит от выбора конкретной последовательности размеров шагов.
На практике бывает полезно ограничивать множество у. Например, при использовании ассоциативных марковских сетей приходится полагать лу > О (см. раздел 2.2.1). Если на каждой итерации брать проекцию луп+1 на некоторое выпуклое множество, то метод сходится к оптимуму целевой функции на этом выпуклом множестве [53].
Лакост-Жулие и др. [54] рассмотрели субградиентный метод для оптимизации двойственной функции к (1.60). Формулы пересчёта, выраженные через целевые переменные прямой задачи, совпали с (1.66), однако удалось получить в аналитическом виде оптимальный размер шага 7„ на каждой итерации п. Кроме того, появилась возможность вычислять текущий интервал двойственности, который является верхней оценкой отклонения значения целевой функции в текущей точке от оптимума.
Исследования других применений субградиентного метода [55,56] показали, что неэффективно оценивать градиент точно на каждой итерации. Сумму по J объектам в (1.65) можно приблизить суммой по их случайному подмножеству:
|т(ш) = у + [ф{у3(ч/);х3) - 1/)(у^;хЦ] , (1.67)

где 3 С {1,...,7} — некоторое случайное подмножество. В вырожденном случае 3 состоит из одного элемента, тогда метод называют онлайн-обучением. При его использовании скорость сходимости субградиентных методов может конкурировать со скоростью метода секущей плоскости [54].