Участник:Anton/Песочница

Материал из MachineLearning.

< Участник:Anton(Различия между версиями)
Перейти к: навигация, поиск
 
(60 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
__NOTOC__
+
{{stop|
 +
'''Задание находится в разработке.'''<br/>
 +
Не приступайте к выполнению задания пока не убрано это сообщение.
 +
}}
-
[[Байесовские методы машинного обучения (курс лекций, Д.П. Ветров, Д.А. Кропотов)|Перейти к основной странице спецкурса]]
+
{{TOCright|300px}}
-
'''Начало выполнения задания''': 22 ноября 2010 г.<br>
+
{{Main|Графические модели (курс лекций)}}
-
'''Срок сдачи''': {{важно|6 декабря 2010 г., 23:59.}}
+
-
==Модель Изинга==
+
[[Изображение:GM12 task4 intro.png‎ | 600px]]
-
[[Изображение:BayesML2010_task2_rectGrid.PNG|200px|thumb|Прямоугольная система соседства]]
+
-
[[Изображение:BayesML2010_task2_triGrid.PNG|200px|thumb|Треугольная система соседства]]
+
-
'''Модель Изинга''' — математическая модель статистической физики, предназначенная для описания намагничивания материала.
+
-
Каждой вершине кристаллической решётки (рассматриваются не только трёхмерные, но и одно- и двумерные случаи) сопоставляется число, называемое спином и равное +1 или −1 («поле вверх»/«поле вниз»). Каждому из <tex>2^N</tex> возможных вариантов расположения спинов (где N — число атомов решётки) приписывается энергия, получающаяся из попарного взаимодействия спинов соседних атомов J и действия внешнего магнитного поля H:<br>
+
-
<tex>
+
-
E(X) = -\left( \sum_{(i,j) \in E} J_{ij}x_i x_j + \sum_{i=1}^N H_i x_i \right),
+
-
</tex><br>
+
-
где <tex>x_i</tex> - переменные, соответствующие спинам, E - система соседства (в данном задании рассматривается 2 системы соседства: прямоугольная и треугольная) . Вероятность нахождения в каждом конкретном состоянии задается распределением Гиббса:<br>
+
-
<tex>
+
-
P(X) = \frac{1}{Z} \exp{\left( -\beta E(X) \right)}, \qquad \beta = \frac{1}{kT},
+
-
</tex><br>
+
-
где Z - нормировочная константа, T - температура, k - параметр.
+
-
Если <tex>J_{ij} = 1 </tex>,то вещество называется ферромагнетиком. Если <tex>J_{ij} = -1</tex>, то вещество называется антиферромагнетиком.
+
'''Начало выполнения задания''': 18 апреля 2012
-
==Вариант 1==
+
'''1-й этап сдачи задания''': {{ins|2 мая 2012, 23:59}}
-
===Описание задания===
+
-
Провести исследование модели Изинга методом Монте-Карло. В качестве алгоритма генерации выборки использовать метод Гиббса.
+
-
Генерацию каждого элемента решетки проводить по следующим формулам:
+
-
<br><tex>
+
-
p(x_i = 1 | X_{/\{i\}}) = \frac{1}{1 + \exp(-2\beta b_i)}, \qquad b_i = \sum_{j: (i, j) \in E} J_{ij}x_j + H_i,
+
-
</tex><br>
+
-
<tex>
+
-
p(x_i = -1 | X_{/\{i\}}) = \frac{\exp(-2\beta b_i)}{1 + \exp(-2\beta b_i)}.
+
-
</tex>
+
-
===Задание===
+
'''2-й этап сдачи задания''': {{ins|9 мая 2012, 23:59}}
-
[[Изображение:BayesML2010_task2_example.PNG‎|200px|thumb|Пример иллюстрации состояния модели Изинга размера 20 на 20.]]
+
-
# Вывести формулы для метода Гиббса генерации выборки методом Гиббса (вывод вставить в отчет).
+
-
# Реализовать процедуру подсчета математического ожидания и дисперсии энергии (нормированной на количество спинов N), математического ожидания квадрата общей намагниченности модели <tex>\mu = \left(\sum_{i=1}^N x_i \right) / N</tex> методов Гиббса (с заданным числом итераций) для заданных параметров <tex>\beta</tex> и заданного внешнего магнитного поля H. (Требования по эффективности реализации: 1000 итераций метода Гиббса для решетки размером 20 на 20 и 100 значений параметра <tex>\beta</tex> должны выполнятся не более 100 секунд.)
+
-
# Построить графики зависимости <tex>\mathbb{E}E, \sqrt{\mathbb{D}E}, \sqrt{\mathbb{E}(\mu^2)}</tex> от температуры для треугольной и четырехугольной систем соседства, ферромагнетика и антиферромагнетика (всего 4 модели). Проинтерпретировать полученные результаты (в частности идентифицировать, локализовать и изучить фазовый переход). Для построения графиков использовать следующие значения параметров:
+
-
#*размер решетки 20 на 20 (N = 400)
+
-
#*<tex>k = 1</tex>
+
-
#*10000 итераций метода Гиббса для каждой из температур
+
-
#*для ферромагнетика <tex>J_{ij} = 1</tex>, для антиферромагнетика <tex>J_{ij} = -1</tex>
+
-
#*внешнее магнитное поле <tex>H_i = 0</tex>
+
-
#*температуры T = 0.5 : 0.1 : 10;
+
-
#Для ферромагнетика с четырехугольной системой связности привести (картинками) характерные состояния для разных температур в окрестности фазового перехода. Проинтерпретировать результаты. Рассмотреть не менее одного примера для не менее 5 разных температур. Параметры генерации те же, что и в пункте 3.
+
-
#Исследовать влияние фазового перехода в ферромагнетике с прямоугольной системой соседства от равномерного внешнего магнитного поля. Параметры модели взять такие же как в пункте 3.
+
-
#Выполнить пункт 4 в присутствии внешнего магнитного поля следующей структуры: на половине решетки H = 1, на другой половине H = -1.
+
-
#Сравнить результаты применения метода Монте-Карло с результатами применения вариационного подхода. Рассмотреть ферромагнетик с прямоугольной системой соседства. Реализацию вариационного подхода взять у товарища, выполняющего вариант 2. Привести графики математического ожидания и дисперсии энергии, корня из математического ожидания намагниченности в одних осях для двух подходов.
+
-
=== Оформление задания ===
+
-
Выполненное задание следует отправить письмом по адресу ''bayesml@gmail.com'' с заголовком письма «Задание 2 <Номер_группы> <ФИО>». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае.
+
Среда реализации для всех вариантов — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
-
В качестве программной среды реализации настоятельно рекомендуется использовать MATLAB. Тем не менее, никаких ограничений на выбор среды реализации не накладывается.
+
=== Сегментация изображений ===
 +
В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон.
 +
В дальнейшем работа осуществляется в терминах небольших сегментов изображения — суперпикселей.
 +
Заметим, что по «суперпиксельной» сегментации изображения можно однозначно построить «попиксельную» сегментацию.
-
Присланный вариант задания должен содержать в себе:
+
Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: <tex> E(X, Y, W) </tex>. Здесь X — признаки, Y — «суперпиксельная» сегментация,
-
* ФИО исполнителя, номер группы и номер варианта задания.
+
W — параметры модели. Функция Е выглядит следующим образом: <br>
-
* Текстовый файл в формате PDF, содержащий описание проведенных исследований.
+
<tex> E(X, Y, W) = \sum_{p \in V} ( \vec{x}_p^T \vec{w}^U) y_p + \sum_{(p, q) \in E} (\vec{x}_{pq}^T \vec{w}^P) [y_p \neq y_q] </tex>
-
* Все исходные коды с необходимыми комментариями.
+
 
-
* Дополнительные комментарии или материалы, если необходимо.
+
Здесь V — множество суперпикселей изображения, Е — система соседства суперпикселей, вообще говоря, не являющаяся регулярной решеткой; переменные <tex>y_p</tex> — метки классов, 0 — фон, 1 — объект; <tex> \vec{x}_p </tex> — векторы унарных признаков для суперпикселей; <tex> \vec{x}_{pq} </tex> — векторы парных признаков для пар соседних суперпикселей; <tex> W = (\vec{w}^U, \vec{w}^P) </tex> — веса унарных и парных признаков.
 +
 
 +
Заметим, что если для всех пар соседних суперпикселей величины <tex> \vec{x}_{pq}^T \vec{w}^P </tex> неотрицательны, то энергию E можно эффективно минимизировать при помощи алгоритма построения минимального разреза графа.
 +
 
 +
Приведенный выше способ записи энергии E отличается от способа записи, разобранного на лекции, в двух местах:
 +
# слагаемые, образующие парные потенциалы, записывались так: <tex>\sum_{(p, q) \in E} \sum_{k, \ell \in \{0, 1\}} (\vec{x}_{pq}^T \vec{w}^P_{k\ell}) [y_p = k][y_q = \ell];</tex> в рамках данного задания для упрощения работы парные потенциалы ограничиваются только обобщенными потенциалами Поттса, что соответствует следующим ограничениям на веса: <tex>\vec{w}^P_{00} = \vec{w}^P_{11} = 0; \; \vec{w}^P_{10} = \vec{w}^P_{01}</tex>;
 +
# слагаемые, образующие унарные потенциалы, записывались так: <tex>\sum_{k\in\{0, 1\}}\sum_{p \in V} ( \vec{x}_p^T \vec{w}^U_k) [y_p = k];</tex> в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект».
 +
 
 +
Ограничения накладываемые на веса, соответствующие парным признаком уменьшают гибкость модели. Упрощение, связанное с унарными потенциалами не влияет на гибкость модели (верно только для случая двух классов).
 +
 
 +
В качестве унарных признаков обычно выбирают гистограммы по мешкам слов, построенных по каким-либо локальным дескрипторам изображений. В качестве парных признаков выбирают различных обобщенные модели Поттса; парный признак, равный одной и той же константе по всем парам соседних суперпикселей, соответствует обычной модели Поттса.
 +
 
 +
Параметры модели W можно настраивать при помощи структурного метода опорных векторов (sSVM), решая оптимизационную задачу при помощи метода отсекающих плоскостей.
 +
 
 +
Поскольку классы не сбалансированы (на изображениях пикселей фона намного больше, чем пикселей объекта), расстояние Хэмминга между произвольной и правильной сегментациями не является адекватной мерой качества сегментации. В рамках данного задания ошибка сегментации определяется количеством неправильно распознанных пикселей каждого класса, взвешенным на общее количество пикселей этого класса на изображении:
 +
 
 +
<tex> error(T, \hat{T}) = \frac{\sum_i [t_i \neq 1][\hat{t}_i = 1]}{\sum_i [\hat{t}_i = 1]} + \frac{\sum_i [t_i \neq 0][\hat{t}_i = 0]}{\sum_i [\hat{t}_i = 0]}</tex>.
 +
 
 +
Здесь T — текущая разметка изображения, <tex>\hat{T} </tex> — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения.
 +
 
 +
=== Задание ===
 +
В рамках 1-го этапа задания необходимо
 +
# выписать формулу для ошибки, усредненной по классам в терминах суперпикселей Y;
 +
# показать как решать задачу <tex> \max_Y (-E(X, Y, W) + error(T(Y), \hat{T}))</tex> при помощи алгоритма построения разреза графа;
 +
# реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений;
 +
# протестировать реализованные процедуры на модельных данных, используя хотя бы 1 парный признак;
 +
# написать отчет в формате PDF с описанием всех проведенных исследований.
 +
 
 +
В рамках 2-го этапа задания необходимо
 +
# придумать не менее 5 различных парных признаков;
 +
# при помощи [[Скользящий контроль| скользящего контроля]] подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке;
 +
# при помощи обученного сегментатора получить разметки тестовой выборки изображения; привести примеры удачных и неудачных сегментаций; студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, получат дополнительные баллы;
 +
# написать отчет в формате PDF с описанием всех проведенных исследований.
 +
 
 +
Для выполнения задания выдается:
 +
# реализация алгоритма построения разреза графов, совместимая с MATLAB;
 +
# реализации структурного метода опорных векторов в библиотеке SVM-struct с интерфейсом под MATLAB: http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html
 +
# исходные изображения: обучающая и тестовая выборки;
 +
# правильная сегментация изображений обучающей выборки;
 +
# суперпиксели изображений обучающей и тестовой выборок, найденные при помощи библиотеки [http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/resources.html BSR];
 +
# признаки для каждого суперпикселя; вектором признаков является гистограмма по мешку из 128 слов, построенному по [http://en.wikipedia.org/wiki/Scale-invariant_feature_transform SIFT]; признаки посчитаны при помощи библиотеки [http://www.vlfeat.org/ VLFeat].
 +
 
 +
=== Описание форматов данных ===
 +
 
 +
Названия файлов, относящихся к каждому объекту обучающей выборки, начинаются с названия объекта: imgTrain_{номер файла}. Для каждого объекта выданы следующие файлы:
 +
*изображение: imgTrain_XXX.png
 +
*правильная разметка изображения: imgTrain_XXX_groundtruth.png
 +
*mat-файлы, содержащие признаки и суперпиксели для изображения: imgTrain_XXX_data.mat. В каждом файле присутствуют следующие переменные:
 +
** superpixelMap — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
 +
** neighborhood — массив типа double размером #(пары соседних супепикселей) x 2; каждая строка содержит номера соседних суперпикселей;
 +
** unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели).
 +
 
 +
Здесь и далее под #(название объекта) обозначается количество объектов.
 +
 
 +
Названия файлов, относящихся к каждому объекту тестовой выборки, начинаются с названия объекта: imgTest_{номер файла}. Для каждого объекта выданы следующие файлы:
 +
*изображение: imgTest_XXX.png
 +
*mat-файлы, содержащие признаки и суперпиксели для изображения: imgTest_XXX_data.mat. В каждом файле присутствуют следующие переменные:
 +
** superpixelMap — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
 +
** neighborhood — массив типа double размером #(пары соседних супепикселей) x 2; каждая строка содержит номера соседних суперпикселей;
 +
** unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели).
 +
 
 +
=== Спецификация реализуемых функций ===
-
Исходные коды должны включать в себя реализацию метода Гиббса для прямоугольной и треугольной систем соседств в виде отдельных функций. Прототипы функций имеют следующий вид:<br>
 
{|class="standard"
{|class="standard"
-
!''Метод Гиббса''
+
!''Обучение''
|-
|-
-
|[E, magnet, samples] = generateIsing4(vS, hS, J, H, iter, betaAll) - прямоугольная система соседства
+
|[model, time] = train_sSVM(X, Y, options)
-
|-
+
-
|[E, magnet, samples] = generateIsing6(vS, hS, J, H, iter, betaAll) - треугольная система соседства
+
|-
|-
|ВХОД
|ВХОД
Строка 72: Строка 99:
|
|
{|border="0"
{|border="0"
-
|vS — размер решетки по вертикали;
+
|X — обучающая выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
|-
|-
-
|hS — размер решетки по горизонтали;
+
|&nbsp;&nbsp; 'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
|-
|-
-
|J - параметр J модели. Все <tex>J_{ij}</tex> одинаковы и равны J.
+
|&nbsp;&nbsp; 'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
|-
|-
-
|H - внешнее магнитное поле, матрица размера vS на hS.
+
|&nbsp;&nbsp; 'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
|-
|-
-
|iter - количество итераций метода Гиббса
+
|Y — ответы на обучающей выборки, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
|-
|-
-
|betaAll - вектор значений параметра <tex>\beta</tex>, для которых надо применить метод Гиббса. Длина вектора - <tex>\beta_0</tex>.
+
|options — набор параметров метода, структура с полями:
 +
|-
 +
|&nbsp;&nbsp; 'С' — параметр C структурного метода опорных векторов;
 +
|-
 +
|&nbsp;&nbsp; 'eps' — порог для добавления ограничений в рамках метода отсекающих плоскостей;
|}
|}
|-
|-
Строка 89: Строка 120:
|
|
{|
{|
-
|E - значения энергий на 1 спин, массив размера iter на <tex>\beta_0</tex>.
+
|model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки).
|-
|-
-
|magnet — значения магнетизации на 1 спин, массив размера iter на <tex>\beta_0</tex>.
+
|time — время работы алгоритма;
 +
|}
 +
|}
 +
 
 +
 
 +
{|class="standard"
 +
!''Предсказание''
 +
|-
 +
|Y = predict_sSVM(X, model)
 +
|-
 +
|ВХОД
 +
|-
 +
|
 +
{|border="0"
 +
|X — выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
|-
|-
-
|samples — примеры положений модели для всех температур, массив размера vS на hS на <tex>\beta_0</tex>.
+
|&nbsp;&nbsp; 'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
-
|}
+
|-
-
|}
+
|&nbsp;&nbsp; 'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
 +
|-
 +
|&nbsp;&nbsp; 'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
 +
|-
 +
|model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки);
 +
|}
 +
|-
 +
|ВЫХОД
 +
|-
 +
|
 +
{|
 +
|Y — ответы на выборке X, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
 +
|}
 +
|}
-
===Рекомендации===
 
-
*Лучше реализовывать метод векторно по параметру <tex>\beta</tex>, то есть проводить вычисления для всех температур сразу.
 
-
*Начинать метод Гиббса лучше с наиболее вероятной для данной модели конфигурации.
 
-
*Для оценки глобальных параметров лучше выкинуть значения, полученные на первой трети итераций метода Гиббса.
 
-
*В качестве примера ситуации можно взять ситуацию, сгенерированную на последней итерации метода Гиббса.
 
 +
{|class="standard"
 +
!''Обучение и предсказание для базы с машинами''
 +
|-
 +
|[train_error, test_Y] = cars()
 +
|-
 +
|ВЫХОД
 +
|-
 +
|
 +
{|
 +
|train_error — ошибка на обучающей выборке;
 +
|-
 +
|test_Y — ответы на тестовой выборке, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения.
 +
|}
 +
|}
 +
 +
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог с данными.
 +
 +
=== Рекомендации по выполнению задания ===
 +
# Библиотека SVM-struct не позволяет установить ограничения на знак весов парных признаков <tex> \vec{w}^P </tex>. Для минимизации получающихся несубмодулярных функций рекомендуется отбрасывать несубмодулярные ребра.
 +
# В качестве модельных данных рекомендуется использовать выборку, состоящую из 2-3 изображений обучающей выборки. При правильной реализации алгоритма точность сегментации изображений, использовавшихся при обучении должна быть высокой (более 97% в терминах ошибки, усредненной по классам).
 +
# Для работы с библиотекой SVM-struct необходимо реализовать функцию поиска наиболее нарушаемого ограничения (CONSTRAINTFN), функцию построения вектора обобщенных признаков (FEATUREN), функцию потерь (LOSSFN). Библиотеку SVMstruct рекомендуется запускать со следующими параметрами: -p 1 -o 2 -w 4 -v 3 -y 0 -c <ваш C> -e <ваш eps>.
 +
# На этапе отладки параметр eps стоит выбрать достаточно большим (например, 10), чтобы уменьшить время работы алгоритма. На этапе экспериментов значение eps стоит уменьшить на несколько порядков.
 +
# При правильной реализации метода одна операция обучение sSVM на полной выборке должна работать не более получаса.
 +
# В качестве процедуры скользящего контроля рекомендуется выбрать схему [[Скользящий контроль| контроля по 2 блокам]] (2-fold CV).
 +
# Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. При этом в крайних значениях нужно получить ситуации недообучения и переобучения. Начинать перебор лучше с заведомо заниженных значений параметра С, поскольку в этом случае метод работает быстрее.
 +
 +
=== Данные для выполнения задания ===
 +
 +
[[Media:GM_GraphCut.zip|graphCut]] — MATLAB интерфейс к разрезам графов.
 +
 +
[https://docs.google.com/open?id=0B_PZC3alifN6WDExQlR6cktSaUU База данных].
 +
 +
[http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html MATLAB библиотека SVM-struct]
 +
 +
=== Оформление задания ===
 +
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 5. ФИО». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
-
==Вариант 2==
+
Письмо должно содержать:
 +
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
 +
*train_sSVM.m, predict_sSVM.m, cars.m
 +
*разметку тестовой выборки в таком же формате, как выдана разметка обучающей выборки
 +
*Набор вспомогательных файлов при необходимости

Текущая версия

Задание находится в разработке.

Не приступайте к выполнению задания пока не убрано это сообщение.


Содержание

Основная статья: Графические модели (курс лекций)

Начало выполнения задания: 18 апреля 2012

1-й этап сдачи задания: 2 мая 2012, 23:59

2-й этап сдачи задания: 9 мая 2012, 23:59

Среда реализации для всех вариантов — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.

Сегментация изображений

В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон. В дальнейшем работа осуществляется в терминах небольших сегментов изображения — суперпикселей. Заметим, что по «суперпиксельной» сегментации изображения можно однозначно построить «попиксельную» сегментацию.

Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: E(X, Y, W) . Здесь X — признаки, Y — «суперпиксельная» сегментация, W — параметры модели. Функция Е выглядит следующим образом:
E(X, Y, W) = \sum_{p \in V} ( \vec{x}_p^T \vec{w}^U) y_p + \sum_{(p, q) \in E} (\vec{x}_{pq}^T \vec{w}^P) [y_p \neq y_q]

Здесь V — множество суперпикселей изображения, Е — система соседства суперпикселей, вообще говоря, не являющаяся регулярной решеткой; переменные y_p — метки классов, 0 — фон, 1 — объект; \vec{x}_p — векторы унарных признаков для суперпикселей; \vec{x}_{pq} — векторы парных признаков для пар соседних суперпикселей; W = (\vec{w}^U, \vec{w}^P) — веса унарных и парных признаков.

Заметим, что если для всех пар соседних суперпикселей величины \vec{x}_{pq}^T \vec{w}^P неотрицательны, то энергию E можно эффективно минимизировать при помощи алгоритма построения минимального разреза графа.

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

  1. слагаемые, образующие парные потенциалы, записывались так: \sum_{(p, q) \in E} \sum_{k, \ell \in \{0, 1\}} (\vec{x}_{pq}^T \vec{w}^P_{k\ell}) [y_p = k][y_q = \ell]; в рамках данного задания для упрощения работы парные потенциалы ограничиваются только обобщенными потенциалами Поттса, что соответствует следующим ограничениям на веса: \vec{w}^P_{00} = \vec{w}^P_{11} = 0; \; \vec{w}^P_{10} = \vec{w}^P_{01};
  2. слагаемые, образующие унарные потенциалы, записывались так: \sum_{k\in\{0, 1\}}\sum_{p \in V} ( \vec{x}_p^T \vec{w}^U_k) [y_p = k]; в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект».

Ограничения накладываемые на веса, соответствующие парным признаком уменьшают гибкость модели. Упрощение, связанное с унарными потенциалами не влияет на гибкость модели (верно только для случая двух классов).

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

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

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

error(T, \hat{T}) = \frac{\sum_i [t_i \neq 1][\hat{t}_i = 1]}{\sum_i [\hat{t}_i = 1]} + \frac{\sum_i [t_i \neq 0][\hat{t}_i = 0]}{\sum_i [\hat{t}_i = 0]}.

Здесь T — текущая разметка изображения, \hat{T} — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения.

Задание

В рамках 1-го этапа задания необходимо

  1. выписать формулу для ошибки, усредненной по классам в терминах суперпикселей Y;
  2. показать как решать задачу \max_Y (-E(X, Y, W) + error(T(Y), \hat{T})) при помощи алгоритма построения разреза графа;
  3. реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений;
  4. протестировать реализованные процедуры на модельных данных, используя хотя бы 1 парный признак;
  5. написать отчет в формате PDF с описанием всех проведенных исследований.

В рамках 2-го этапа задания необходимо

  1. придумать не менее 5 различных парных признаков;
  2. при помощи скользящего контроля подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке;
  3. при помощи обученного сегментатора получить разметки тестовой выборки изображения; привести примеры удачных и неудачных сегментаций; студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, получат дополнительные баллы;
  4. написать отчет в формате PDF с описанием всех проведенных исследований.

Для выполнения задания выдается:

  1. реализация алгоритма построения разреза графов, совместимая с MATLAB;
  2. реализации структурного метода опорных векторов в библиотеке SVM-struct с интерфейсом под MATLAB: http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html
  3. исходные изображения: обучающая и тестовая выборки;
  4. правильная сегментация изображений обучающей выборки;
  5. суперпиксели изображений обучающей и тестовой выборок, найденные при помощи библиотеки BSR;
  6. признаки для каждого суперпикселя; вектором признаков является гистограмма по мешку из 128 слов, построенному по SIFT; признаки посчитаны при помощи библиотеки VLFeat.

Описание форматов данных

Названия файлов, относящихся к каждому объекту обучающей выборки, начинаются с названия объекта: imgTrain_{номер файла}. Для каждого объекта выданы следующие файлы:

  • изображение: imgTrain_XXX.png
  • правильная разметка изображения: imgTrain_XXX_groundtruth.png
  • mat-файлы, содержащие признаки и суперпиксели для изображения: imgTrain_XXX_data.mat. В каждом файле присутствуют следующие переменные:
    • superpixelMap — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
    • neighborhood — массив типа double размером #(пары соседних супепикселей) x 2; каждая строка содержит номера соседних суперпикселей;
    • unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели).

Здесь и далее под #(название объекта) обозначается количество объектов.

Названия файлов, относящихся к каждому объекту тестовой выборки, начинаются с названия объекта: imgTest_{номер файла}. Для каждого объекта выданы следующие файлы:

  • изображение: imgTest_XXX.png
  • mat-файлы, содержащие признаки и суперпиксели для изображения: imgTest_XXX_data.mat. В каждом файле присутствуют следующие переменные:
    • superpixelMap — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
    • neighborhood — массив типа double размером #(пары соседних супепикселей) x 2; каждая строка содержит номера соседних суперпикселей;
    • unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели).

Спецификация реализуемых функций

Обучение
[model, time] = train_sSVM(X, Y, options)
ВХОД
X — обучающая выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
   'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
   'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
   'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
Y — ответы на обучающей выборки, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
options — набор параметров метода, структура с полями:
   'С' — параметр C структурного метода опорных векторов;
   'eps' — порог для добавления ограничений в рамках метода отсекающих плоскостей;
ВЫХОД
model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки).
time — время работы алгоритма;


Предсказание
Y = predict_sSVM(X, model)
ВХОД
X — выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
   'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
   'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
   'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки);
ВЫХОД
Y — ответы на выборке X, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;


Обучение и предсказание для базы с машинами
[train_error, test_Y] = cars()
ВЫХОД
train_error — ошибка на обучающей выборке;
test_Y — ответы на тестовой выборке, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения.

В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог с данными.

Рекомендации по выполнению задания

  1. Библиотека SVM-struct не позволяет установить ограничения на знак весов парных признаков \vec{w}^P . Для минимизации получающихся несубмодулярных функций рекомендуется отбрасывать несубмодулярные ребра.
  2. В качестве модельных данных рекомендуется использовать выборку, состоящую из 2-3 изображений обучающей выборки. При правильной реализации алгоритма точность сегментации изображений, использовавшихся при обучении должна быть высокой (более 97% в терминах ошибки, усредненной по классам).
  3. Для работы с библиотекой SVM-struct необходимо реализовать функцию поиска наиболее нарушаемого ограничения (CONSTRAINTFN), функцию построения вектора обобщенных признаков (FEATUREN), функцию потерь (LOSSFN). Библиотеку SVMstruct рекомендуется запускать со следующими параметрами: -p 1 -o 2 -w 4 -v 3 -y 0 -c <ваш C> -e <ваш eps>.
  4. На этапе отладки параметр eps стоит выбрать достаточно большим (например, 10), чтобы уменьшить время работы алгоритма. На этапе экспериментов значение eps стоит уменьшить на несколько порядков.
  5. При правильной реализации метода одна операция обучение sSVM на полной выборке должна работать не более получаса.
  6. В качестве процедуры скользящего контроля рекомендуется выбрать схему контроля по 2 блокам (2-fold CV).
  7. Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. При этом в крайних значениях нужно получить ситуации недообучения и переобучения. Начинать перебор лучше с заведомо заниженных значений параметра С, поскольку в этом случае метод работает быстрее.

Данные для выполнения задания

graphCut — MATLAB интерфейс к разрезам графов.

База данных.

MATLAB библиотека SVM-struct

Оформление задания

Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 5. ФИО». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.

Письмо должно содержать:

  • PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
  • train_sSVM.m, predict_sSVM.m, cars.m
  • разметку тестовой выборки в таком же формате, как выдана разметка обучающей выборки
  • Набор вспомогательных файлов при необходимости
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Anton/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»
Личные инструменты