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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 61: Строка 61:
!''Обучение''
!''Обучение''
|-
|-
-
|[model] = train_sSVM(unary, vertC, horC, metric)
+
|[model, time] = train_sSVM(X, Y, options)
|-
|-
|ВХОД
|ВХОД
Строка 67: Строка 67:
|
|
{|border="0"
{|border="0"
-
|unary — унарные потенциалы, массив типа double размера N x M x K, где N — высота решетки, M — ширина решетки, K — количество меток.
+
|X — обучающая выборка, массив типа cell размера N x 1, где N - размер обучающей выборки; каждая элемент содержит путь к файлу XXX_data.png для соответствующего изображения;
|-
|-
-
|vertC — коэффициенты <tex> c_{pq}</tex>, соответствующие вертикальным ребрам, массив типа double размера (N — 1) x M;
+
|Y — ответы на обучающей выборки, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
|-
|-
-
|horC — коэффициенты <tex> c_{pq}</tex>, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
+
|options — набор параметров метода, структура с полями:
|-
|-
-
|metric - расстояние между метками соседних переменных, массив типа double размера K x K;
+
|&nbsp;&nbsp; 'С' — параметр C структурного метода опорных векторов
|-
|-
-
|options — (необязательный аргумент) набор дополнительных параметров, массив типа '''cell''' вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
+
|&nbsp;&nbsp; 'eps' — порог для добавления ограничений в рамках метода отсекающих плоскостей
-
|-
+
-
|&nbsp;&nbsp;'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
+
-
|-
+
-
|&nbsp;&nbsp;'argEps' — порог сходимости по аргументу;
+
-
|-
+
-
|&nbsp;&nbsp;'display' — параметр типа logical: если true, то на каждой итерации нужно выводить на экран номер итерации, текущее значение энергии и нижней границы;
+
|}
|}
|-
|-
Строка 88: Строка 82:
|
|
{|
{|
-
|labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
+
|model — модель, обученная при помощи вашего метода;
|-
|-
-
|energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
+
|time — время работы алгоритма;
-
|-
+
-
|lowerBound — значения нижней границы на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
+
-
|-
+
-
|time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма.
+
|}
|}
|}
|}
-
Обратите внимание: в процедуре trwGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 
{|class="standard"
{|class="standard"
-
!''Стерео''
+
!''Предсказание''
|-
|-
-
|[disparity] = stereo(name)
+
|Y = predict_sSVM(X, model)
|-
|-
|ВХОД
|ВХОД
Строка 108: Строка 97:
|
|
{|border="0"
{|border="0"
-
|name — название стерео пары, строка.
+
|X — выборка, массив типа cell размера N x 1, где N - размер обучающей выборки; каждая элемент содержит путь к файлу XXX_data.png для соответствующего изображения;
-
|}
+
|-
 +
|model — модель, полученная при помощи процедуры train_sSVM;
 +
|}
|-
|-
|ВЫХОД
|ВЫХОД
Строка 115: Строка 106:
|
|
{|
{|
-
|disparity — массив смещений массив типа double размера N x M со значениями -∞,...,∞.
+
|Y — ответы на выборке X, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
|}
|}
-
|}
+
|}
-
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог datasets.
+
-
=== Рекомендации по выполнению задания ===
 
-
1. При разбиении MRF-решетки только на вертикальные и горизонтальные цепочки формулировка несколько упрощается:
 
-
*Каждое ребро графа принадлежит только одному подграфу, а, значит, не нужно вводить двойственные переменные, соответствующие ребрам.
 
-
*Каждая вершина принадлежит только двум деревьям, а, значит, можно ввести |P|K двойственных переменных, соответствующих условиям <tex> y_{pk}^{hor} = y_{pk}^{vert}, \;\; p \in P, \;\; k = 1,\dots,K</tex>, где hor и vert обозначают горизонтальную и вертикальную цепочку, проходящую через p-ю вершину.
 
-
2. Поскольку двойственная функция вогнута и кусочно-линейна, оптимизировать ее можно при помощи алгоритма субградиентного подъема.
+
{|class="standard"
-
Каждый шаг метода субградиентного подъема состоит в пересчете значений двойственных переменных λ по следующему правилу:<br>
+
!''Обучение и предсказание для базы с машинами''
-
<tex>\vec{\lambda}_{new} = \vec{\lambda}_{old} + \alpha_t \vec{g}_t, </tex>
+
|-
-
где <tex>\vec{g}_t</tex> — субградиент в текущей точке, <tex>\alpha_t</tex> — параметр, отвечающий за длину сдвига.
+
|[train_error, test_error] = cars()
-
В рамках данного практического задания можно использовать любой способ субградиентного подъема. Например, можно использовать следующий адаптивный метод выбора длины шага:<br>
+
|-
-
<tex>\alpha_t = \frac{\text{Approx}_t - \text{Dual}_t}{|| \nabla \vec{g}_t|| ^ 2},</tex><br>
+
|ВЫХОД
-
где <tex>\text{Dual}_t</tex> — текущее значение двойственной функции, <tex>\text{Approx}_t</tex> — оценка оптимума двойственной функции, которую можно определять следующим способом:<br>
+
|-
-
<tex>\text{Approx}_t = \text{BestDual}_t + \delta_t,</tex> где <tex>\text{BestDual}_t </tex> — лучшее на данный момент значение двойственной функции, <br>
+
|
-
<tex>\delta_{t+1} = \begin{cases}
+
{|
-
\gamma_0 \delta_t, \;\; \text{Dual}_t > \text{Dual}_{t-1}, \\
+
|train_error — ошибка на обучающей выборке;
-
\max(\gamma_1 \delta_t, \; \varepsilon ), \;\; \text{Dual}_t \leq \text{Dual}_{t-1}. \end{cases}</tex><br>
+
|-
-
<tex>\gamma_0, \; \gamma_1, \; \varepsilon</tex> — параметры метода. Обычно <tex>\gamma_0 > 1, \; 1 > \gamma_1 > 0, \; \varepsilon \to 0+ </tex>. Конкретные значения этих параметров нужно подобрать.
+
|test_error — ошибка на тестовой выборке;
 +
|}
 +
|}
-
Подробнее о методах субградиентного подъема написано в статье:
+
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог datasets.
-
N. Komodakis, N.Paragios and G. Tziritas, MRF Energy Minimization and Beyond via Dual Decomposition, IEEE TPAMI, 33(3):531-552, 2011,
+
-
http://www.csd.uoc.gr/~komod/publications/docs/DualDecomposition_PAMI.pdf
+
-
3. В качестве текущего значения энергии в рамках алгоритма TRW можно выбрать минимум энергий разметок, полученных по только вертикальным и только горизонтальным цепочкам.
+
=== Рекомендации по выполнению задания ===
-
 
+
-
4. При тестировании алгоритма TRW необходимо следить, чтобы наибольшее значение нижней границы было не больше, чем наименьшее значение энергии.
+
-
 
+
-
5. Потенциалы для стереопары tsukuba и примеры работы различных алгоритмов: http://vision.middlebury.edu/MRF/results/tsukuba/index.html
+
=== Данные для выполнения задания ===
=== Данные для выполнения задания ===
-
[[Media:SMAIS11_task2_Converter.zip|rgb2luv]] — конвертер изображений в формат [http://en.wikipedia.org/wiki/YUV YUV].
 
-
 
-
[[Media:GM_Stereo_Datasets.zip‎|datasets]] — стереопары.
 
=== Оформление задания ===
=== Оформление задания ===
-
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 3. ФИО, вариант 1». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
+
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 4. ФИО». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
Письмо должно содержать:
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
-
*trwGridPotts.m
+
*train_sSVM.m, predict_sSVM.m, cars.m
-
*stereoTsukuba.m, stereoTeddy.m, stereoCones.m, stereoArt.m
+
*Набор вспомогательных файлов при необходимости
*Набор вспомогательных файлов при необходимости

Версия 14:01, 17 апреля 2012

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

Не приступайте к выполнению задания до его официальной выдачи.


Содержание

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

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

Срок сдачи: 2 мая 2012, 23:59

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

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

В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон.

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

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

error(Y, \hat{Y}) = \frac{\sum_p [y_p \neq 1][\hat{y}_p = 1]}{\sum_p [\hat{y}_p = 1]} + \frac{\sum_p [y_p \neq 0][\hat{y}_p = 0]}{\sum_p [\hat{y}_p = 0]}.

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

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

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

Для выполнения задания настоятельно рекомендуется использовать реализации структурного метода опорных векторов в библиотеке Торстена Йохимса SVM struct с интерфейсом под MATLAB от Андреа Ведальди: http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html

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

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

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

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

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

Задание

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

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

Обучение
[model, time] = train_sSVM(X, Y, options)
ВХОД
X — обучающая выборка, массив типа cell размера N x 1, где N - размер обучающей выборки; каждая элемент содержит путь к файлу XXX_data.png для соответствующего изображения;
Y — ответы на обучающей выборки, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
options — набор параметров метода, структура с полями:
   'С' — параметр C структурного метода опорных векторов
   'eps' — порог для добавления ограничений в рамках метода отсекающих плоскостей
ВЫХОД
model — модель, обученная при помощи вашего метода;
time — время работы алгоритма;
Предсказание
Y = predict_sSVM(X, model)
ВХОД
X — выборка, массив типа cell размера N x 1, где N - размер обучающей выборки; каждая элемент содержит путь к файлу XXX_data.png для соответствующего изображения;
model — модель, полученная при помощи процедуры train_sSVM;
ВЫХОД
Y — ответы на выборке X, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;


Обучение и предсказание для базы с машинами
[train_error, test_error] = cars()
ВЫХОД
train_error — ошибка на обучающей выборке;
test_error — ошибка на тестовой выборке;

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

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

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

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

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

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

  • PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
  • train_sSVM.m, predict_sSVM.m, cars.m
  • Набор вспомогательных файлов при необходимости
Источник — «http://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»
Личные инструменты