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

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

< Участник:Anton(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Введение == === Постановка математической задачи === Рассмотрим задачу вычисления второй производной <...)
 
(143 промежуточные версии не показаны)
Строка 1: Строка 1:
-
== Введение ==
+
{{stop|
-
=== Постановка математической задачи ===
+
'''Задание находится в разработке.'''<br/>
-
Рассмотрим задачу вычисления второй производной <tex>\frac{d^2}{d x^2}</tex> функции <tex>y(x)</tex>.
+
Не приступайте к выполнению задания пока не убрано это сообщение.
-
Если задачу точно решить либо не удаётся, либо слишком сложно, то приходится использовать методы численного дифференцирования.
+
}}
-
В данном отчёте теоретически обосновываются приближенные формулы для вычисления производной:
+
{{TOCright|300px}}
-
{{ eqno | 1 }}
+
-
::<tex>y''(x)=(y(x+h)-2y(x)+y(x-h))/h^2+O(h^2)</tex>.
+
-
{{ eqno | 2 }}
+
{{Main|Графические модели (курс лекций)}}
-
::<tex>y''(x)=(-y(x+2h)+16y(x+h)-30y(x)+16y(x-h)-y(x-2h))/(12h^2)+O(h^4)</tex>
+
-
Эти формулы можно использовать и для вычисления частной производной функции многих переменных.
+
[[Изображение:GM12 task4 intro.png‎ | 600px]]
-
После этого приводятся оценки ошибок формул {{eqref|1}} и {{eqref|1}}, а также рассматривается вопрос о выборе оптимального шага <tex>h</tex>.
+
'''Начало выполнения задания''': 18 апреля 2012
-
== Изложение метода ==
+
'''1-й этап сдачи задания''': {{ins|2 мая 2012, 23:59}}
-
=== Определения ===
+
-
Пусть в некоторой окрестности точки <tex>x_0 \in \mathbb{R}</tex> определена функция <tex>y: U(x_0) \subset \mathbb{R} \to \mathbb{R}</tex>. Производной функции <tex>y(x)</tex> в точке <tex>x_0</tex> называется предел, если он существует,
+
-
<tex>y'(x_0)=\lim_{x\to x_0} \frac{y(x)-y(x_0)}{x-x_0}</tex>.
+
'''2-й этап сдачи задания''': {{ins|9 мая 2012, 23:59}}
-
Второй производной функции <tex>y(x)</tex> в точке <tex>x_0</tex> называется производная функции <tex>y'(x)</tex> в точке <tex>x_0</tex>. Аналогично определяются производные и более высоких порядков.
+
Среда реализации для всех вариантов — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
-
+
-
=== Полиномиальные формулы ===
+
-
При численном дифференцировании функцию <tex>y(x)</tex> аппроксимируют легко вычисляемой функцией <tex>\varphi(x)</tex> и приближенно полагают <tex>y^{(k)}(x)\approx\varphi^{(k)}(x)</tex>. При этом можно использовать различные способы аппроксимации. Рассмотрим простейший случай - аппроксимацию интерполяционным многочленом Ньютона.
+
-
Пусть задана сетка <tex>x_0<x_1<\dots<x_N. y(x)</tex> - исследуемая функция. Введем обозначение <tex>\xi_i=x-x_i</tex> и введем понятие разделенные разности <tex>y(x_0,x_1,\dots,x_k)</tex>, определяемые следующим образом:
+
=== Сегментация изображений ===
 +
В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон.
 +
В дальнейшем работа осуществляется в терминах небольших сегментов изображения — суперпикселей.
 +
Заметим, что по «суперпиксельной» сегментации изображения можно однозначно построить «попиксельную» сегментацию.
-
::<tex>y(x_i,x_j)=\frac{y(x_i) - y(x_j)}{x_i - x_j}</tex>,
+
Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: <tex> E(X, Y, W) </tex>. Здесь X — признаки, Y — «суперпиксельная» сегментация,
 +
W — параметры модели. Функция Е выглядит следующим образом: <br>
 +
<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>
-
::<tex>y(x_i,x_j,x_k) = \frac{y(x_i,x_j)-y(x_j,x_k)}{x_i-x_k}</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 можно эффективно минимизировать при помощи алгоритма построения минимального разреза графа.
-
::<tex>y(x_0,x_1,\dots,x_k) = \sum_{p=0}^{k}y_p \prod_{i=0, i\neq p}^k {(x_p-x_i)}^{-1}</tex>.
+
Приведенный выше способ записи энергии 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> в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект».
-
Запишем интерполяционный многочлен Ньютона и продифференцируем его почленно:
+
Ограничения накладываемые на веса, соответствующие парным признаком уменьшают гибкость модели. Упрощение, связанное с унарными потенциалами не влияет на гибкость модели (верно только для случая двух классов).
-
::<tex>\varphi(x)=y(x_0)+\xi_0 y(x_0,x_1)+\xi_0\xi_1 y(x_0,x_1,x_2) + \xi_0\xi_1\xi_2 y(x_0,x_1,x_2,x_3)+\dots</tex>
+
В качестве унарных признаков обычно выбирают гистограммы по мешкам слов, построенных по каким-либо локальным дескрипторам изображений. В качестве парных признаков выбирают различных обобщенные модели Поттса; парный признак, равный одной и той же константе по всем парам соседних суперпикселей, соответствует обычной модели Поттса.
-
::<tex>\varphi'(x)=y(x_0,x_1)+(\xi_0+\xi_1) y(x_0,x_1,x_2) + (\xi_0\xi_1+\xi_0\xi_2 +\xi_1\xi_2) y(x_0,x_1,x_2,x_3)+\dots</tex>
+
Параметры модели W можно настраивать при помощи структурного метода опорных векторов (sSVM), решая оптимизационную задачу при помощи метода отсекающих плоскостей.
-
::<tex>\varphi''(x)=2 y(x_0,x_1,x_2) + 2(\xi_0+\xi_1 +\xi_2) y(x_0,x_1,x_2,x_3)+\dots</tex>
+
Поскольку классы не сбалансированы (на изображениях пикселей фона намного больше, чем пикселей объекта), расстояние Хэмминга между произвольной и правильной сегментациями не является адекватной мерой качества сегментации. В рамках данного задания ошибка сегментации определяется количеством неправильно распознанных пикселей каждого класса, взвешенным на общее количество пикселей этого класса на изображении:
-
Общая формула примет следующий вид:
+
<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>.
-
{{ eqno | 3 }}
+
-
::<tex> \varphi^{(k)}(x)=k!\left[ y(x_0,x_1,\dots,x_k) + \left( \sum_{i=0}^k \xi_i \right) y(x_0,x_1,\dots,x_{k+1}) + \left( \sum_{i>j\geq 0}^{i=k+1}\xi_i\xi_j\right)y(x_0,x_1,\dots,x_{k+2}) + \left( \sum_{i>j>l\geq 0}^{i=k+2}\xi_i\xi_j\xi_l\right)y(x_0,x_1,\dots,x_{k+3}) +\dots\right] </tex>
+
-
Обрывая ряд на некотором числе членов, получим приближенное выражение для соответствующей производной. Наиболее простые выражения получим, оставляя в формуле {{eqref|3}} только первый член:
+
Здесь T — текущая разметка изображения, <tex>\hat{T} </tex> — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения.
-
::<tex>y'(x)\approx y(x_0,x_1) = \frac{y(x_0)-y(x_1)}{x_0-x_1}</tex>,
+
=== Задание ===
 +
В рамках 1-го этапа задания необходимо
 +
# выписать формулу для ошибки, усредненной по классам в терминах суперпикселей Y;
 +
# показать как решать задачу <tex> \max_Y (-E(X, Y, W) + error(T(Y), \hat{T}))</tex> при помощи алгоритма построения разреза графа;
 +
# реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений;
 +
# протестировать реализованные процедуры на модельных данных, используя хотя бы 1 парный признак;
 +
# написать отчет в формате PDF с описанием всех проведенных исследований.
-
{{ eqno | 4 }}
+
В рамках 2-го этапа задания необходимо
-
::<tex>\frac{1}{2}y''(x)\approx y(x_0,x_1,x_2) = \frac{1}{x_0-x_2}\left( \frac{y_0-y_1}{x_0-x_1}- \frac{y_1-y_2}{x_1-x_2}\right)</tex>,
+
# придумать не менее 5 различных парных признаков;
 +
# при помощи [[Скользящий контроль| скользящего контроля]] подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке;
 +
# при помощи обученного сегментатора получить разметки тестовой выборки изображения; привести примеры удачных и неудачных сегментаций; студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, получат дополнительные баллы;
 +
# написать отчет в формате PDF с описанием всех проведенных исследований.
-
::<tex>\frac{1}{k!} y^{(k)}(x) \approx y(x_0,x_1,\dots,x_k) = \sum_{p=0}^{k}y_p \prod_{i=0, i\neq p}^k {(x_p-x_i)}^{-1}</tex>
+
Для выполнения задания выдается:
 +
# реализация алгоритма построения разреза графов, совместимая с 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].
-
Исследование точности полученных выражений при численных расчётах удобно делать при помощи апостериорной оценки, по скорости убывания членов ряда {{eqref|3}}. Если шаг сетки достаточно мал, то погрешность близка к первому отброшенному члену. Пусть мы используем узлы <tex>x_i, i=1\dots n</tex>. Тогда первый отброшенный член содержит разделенную разность <tex>y(x_0,x_1,\dots,x_{n+1})</tex>, которая согласно {{eqref|4}} примерно равна <tex>y^{(n+1)}(x)/(n+1)!</tex>. Перед ней стоит сумма произведений различных множителей <tex>\xi_i </tex>; каждое произведение содержит <tex>n+1-k</tex> множителей, а вся сумма состоит из <tex>C_{n+1}^k</tex> слагаемых. Отсюда следует оценка погрешности формулы {{eqref|3}} с <tex> n+1 </tex> узлами:
+
=== Описание форматов данных ===
-
{{eqno|5}}
+
Названия файлов, относящихся к каждому объекту обучающей выборки, начинаются с названия объекта: imgTrain_{номер файла}. Для каждого объекта выданы следующие файлы:
-
::<tex>R_n^{(k)}\leq\frac{M_{n+1}}{(n+1-k)!}\max_i {|\xi_i|}^{n+1-k},\; M_{n+1}=\max{|y^{(n+1)}|}</tex>
+
*изображение: imgTrain_XXX.png
 +
*правильная разметка изображения: imgTrain_XXX_groundtruth.png
 +
*mat-файлы, содержащие признаки и суперпиксели для изображения: imgTrain_XXX_data.mat. В каждом файле присутствуют следующие переменные:
 +
** superpixelMap — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
 +
** neighborhood — массив типа double размером #(пары соседних супепикселей) x 2; каждая строка содержит номера соседних суперпикселей;
 +
** unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели).
-
В частности, если сетка равномерная, то <tex>M_{n+1}=\max{|\xi_i|}\leq nh</tex>, откуда
+
Здесь и далее под #(название объекта) обозначается количество объектов.
-
{{eqno|6}}
+
-
::<tex>R_n^{(k)}<M_{n+1} {\left( \frac{en}{n+1-k}h \right)}^{n+1-k}=O(h^{n+1-k}) </tex>.
+
-
Стоит заметить, что строгое априорное исследование погрешности формулы {{eqref|3}}, аналогичное выводу остаточного члена многочлена Ньютона в форме Коши, для произвольного расположения узлов приводит к той же оценке {{eqref|5}}.
+
Названия файлов, относящихся к каждому объекту тестовой выборки, начинаются с названия объекта: imgTest_{номер файла}. Для каждого объекта выданы следующие файлы:
 +
*изображение: imgTest_XXX.png
 +
*mat-файлы, содержащие признаки и суперпиксели для изображения: imgTest_XXX_data.mat. В каждом файле присутствуют следующие переменные:
 +
** superpixelMap — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
 +
** neighborhood — массив типа double размером #(пары соседних супепикселей) x 2; каждая строка содержит номера соседних суперпикселей;
 +
** unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели).
-
Таким образом, порядок точности формулы {{eqref|3}} по отношению к шагу сетки равен числу оставленных в ней членов, или, что то же самое, он равен числу узлов интерполяции минус порядок производной. Поэтому минимальное число узлов, необходимое для вычисления <tex>k</tex>-й производной, равно <tex>k+1</tex>; оно приводит к формулам {{eqref|4}} и обеспечивает первый порядок точности. Эти выводы соответствуют общему принципу: при почленном дифференцировании ряда скорость его сходимости уменьшается.
+
=== Спецификация реализуемых функций ===
-
=== Простейшие формулы (случай равномерной сетки)===
+
{|class="standard"
 +
!''Обучение''
 +
|-
 +
|[model, time] = train_sSVM(X, Y, options)
 +
|-
 +
|ВХОД
 +
|-
 +
|
 +
{|border="0"
 +
|X — обучающая выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
 +
|-
 +
|&nbsp;&nbsp; 'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
 +
|-
 +
|&nbsp;&nbsp; 'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
 +
|-
 +
|&nbsp;&nbsp; 'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
 +
|-
 +
|Y — ответы на обучающей выборки, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
 +
|-
 +
|options — набор параметров метода, структура с полями:
 +
|-
 +
|&nbsp;&nbsp; 'С' — параметр C структурного метода опорных векторов;
 +
|-
 +
|&nbsp;&nbsp; 'eps' — порог для добавления ограничений в рамках метода отсекающих плоскостей;
 +
|}
 +
|-
 +
|ВЫХОД
 +
|-
 +
|
 +
{|
 +
|model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки).
 +
|-
 +
|time — время работы алгоритма;
 +
|}
 +
|}
-
Рассмотрим равномерную сетку <tex>x_0<x_1<\dots<x_N,\; x_{i+1}-x_i=h=const,\; y_i=y(x_i). </tex>
 
-
При этом вид формул {{eqref|3}} заметно упрощается, а точность нередко повышается.
 
-
Рассмотрим сначала причину повышения точности. Остаточный член общей формулы {{eqref|3}} - это многочлен <tex>\sum\prod(x-x_i)</tex> степени <tex>n+1-k</tex> относительно <tex>x</tex>. Если <tex>x</tex> равен корню этого многочлена, то главный остаточный член обращается в нуль, то есть в этой точке формула имеет порядок точности на еденицу больше, чем согласно оценке {{eqref|6}}. Эти точки повышенной точности будем обозначать <tex>x_k^{(p)}</tex>, где <tex>k</tex> - порядок производной, а <tex>p=n+1-k</tex> - число оставленных в формуле {{eqref|3}} членов. Очевидно, <tex>p</tex>-членная формула имеет p точек повышенной точности.
+
{|class="standard"
-
 
+
!''Предсказание''
-
У одночленной формулы {{eqref|4}} для <tex>k</tex>-й производной точка повышенной точности на произвольной сетке определяется учловием <tex>\sum \xi_i=\sum(x-x_i)=0</tex>, что дает
+
-
 
+
-
{{eqno|7}}
+
-
::<tex>x_k^{(1)}=(x_0+x_1+\dots+x_k)/(k+1)</tex>;
+
-
 
+
-
в этой точке одночленная формула имеет погрешность <tex>O(h^2)</tex> вместо обычной <tex>O(h)</tex>. Для двучленной формулы задача нахождения точек повышенной точности приводит к квадратному уравнению, корни которого действительны, но формула для их нахождения громоздка. Если <tex>p>2</tex>, то найти точки повышенной точности очень сложно, за исключением одного частного случая, который мы сейчас и рассмотрим.
+
-
 
+
-
'''Утверждение.''' Пусть <tex>p</tex> нечетно, а узлы в формуле {{eqref|4}} выбраны так, что они расположены симметрично относительно точки <tex>x</tex>; тогда <tex>x</tex> является одной из точек повышенной точности <tex>x_k^{(p)}</tex>.
+
-
 
+
-
На произвольной сетке условие симметрии реализуется только в исключительных случаях. Но если сетка равномерна, то каждый ее узел симметрично окружен соседними узлами. Это позволяется составить несложные формулы хорошей точности для вычисления производных в узлах сетки.
+
-
 
+
-
Например, возьмем три соседний узла <tex>x_0</tex>, <tex>x_1</tex> и <tex>x_2</tex>. и вычислим первую и вторую производную в среднем узле. Выражая в одночленных формулах {{eqref|4}} разделенные разности через узловые значения функции, легко получим:
+
-
 
+
-
::<tex>y'(x_1)=(y_2-y_0)/2h+O(h_2),\; h=x_{i+1}-x_i=const,\; y_i=y(x_i)</tex>,
+
-
 
+
-
{{eqno|8}}
+
-
::<tex>y''(x_1)=(y_2-2y_1+y_0)/h^2+O(h^2)</tex>.
+
-
 
+
-
Аналогично можно вывести формулы более высокого порядка или для более выслких производных. Например, формула для второй производной в центральной точке по пяти узлам:
+
-
 
+
-
{{eqno|9}}
+
-
::<tex>y''(x_2)=(-y_4+16y_3-30y_2+16y_1-y_0)/(12h^2)+O(h^4)</tex>
+
-
 
+
-
Заметим, что формулы {{eqref|8}} и {{eqref|9}} написаны для случая равномерной сетки; применение их на неравномерной сетке приведет к грубой ошибке. Также формулы {{eqref|8}}и {{eqref|9}} совпадают с формулами {{eqref|1}} и {{eqref|2}}.
+
-
 
+
-
На равномерной сетке для априоной оценки точности формул часто применяют способ разложения по формуле Тейлора-Макрорена. Предположим, например, что функция <tex>y(x)</tex> имеет непрерыную четвертую производную, и выразим значения функции в узлах <tex>x_{i\pm 1}</tex> через значения функции и ее производных в центре симметрии узлов (в данном случае этим центром является узел <tex>x_i</tex>):
+
-
 
+
-
::<tex>y(x_{i\pm 1})=y(x_i \pm h)= y_i \pm h y_i'+\frac{1}{2}h^2 y_i'' \pm \frac{1}{6}h^3 y_i''' + \frac{1}{24}h^4 y^{(4)}(\eta_\pm)</tex>,
+
-
 
+
-
где <tex>\eta_{+}</tex> - некая точка интервала <tex>(x_i, x_{i+1})</tex>, а <tex>\eta_{-}</tex> - некоторая точка итервала <tex>(x_{i-1},x_i)</tex>. Подставляя эти разложения во вторую разность, стоящую в правой части формулы {{eqref|8}} для второй производной имеем:
+
-
 
+
-
::<tex>\frac{1}{h^2}(y_{i+1}-2y_i+y_{i-1})=y_i''+\frac{h^2}{24}[y^{(4)}(\eta_{+})+y^{(4)}(\eta_{-})]= y_i'' +O(h^2) </tex>.
+
-
 
+
-
Это подтверждает ранее сделанную оценку и уточняет величину остаточного члена, который оказался равен <tex>h^2y^{(4)}(\eta)/12</tex>. Такой способ получения остаточного члена проще, чем непосредственное вычисление по формуле {{eqref|3}}.
+
-
 
+
-
=== Выбор оптимального шага (Регуляризация метода) ===
+
-
[[Изображение:Derives.PNG|thumb|200px|Рис.1]]
+
-
При численном дифференцированиии приходится вычитать друг из друга близкие значения функций. Это приводит к уничтожению первых значащих цифр, то есть к потере части достоверных знаков чила. Если значения функции известны с малой точностью, то встает вопрос - останется ли в ответе хотя один достоверный знак?
+
-
 
+
-
Для ответа на этот вопрос исследуем ошибки при численном дифференцировании. При интерполировании обобщенным многочленом производная <tex>k</tex>-го порядка определяется согласно {{eqref|4}}, {{eqref|5}} формулой типа
+
-
 
+
-
::<tex>y^{(k)}(x)=h^{-k}\sum_q C_q(x)y(x_q) +R_k(x).\; C_q(x)=O(1)</tex>.
+
-
 
+
-
Если формула имеет порядок точности <tex>p</tex>, то, значит, ее остаточный член равен <tex>R_k(x)\approx C(x)h^p</tex>. Этот остаточный член определяет погрешность метода, и он неограниченно убывает при <tex>h\to 0</tex>. Его зависимость от шага изображена на рис.1 жирной линией.
+
-
 
+
-
Но есть еще неустарнимая погрешность, связанная с погрешностью функции <tex>\delta y(x)</tex>. Поскольку точный вид этой погрешности неизвестен, можно оценить только мажоранту неустранимой погрешности <tex>r_k=\delta*h^{-k}\sum_q|C_q|</tex>; она неограниченно возрастает при <tex>h \to 0</tex> (тонкая линия на рис.1). Фактически же неустранимая погрешность будет нерегулярно зависеть от величины шага, беспорядочно осцилируя в границах, определяемых мажорантой (точки на рис.1).
+
-
 
+
-
Пока шаг достаточно велик, при его убывании неустранимая погрешность мала по сравнению с погрешностью метода; поэтому полная погрешность убывает. При дальнейшем уменьшении шага неустранимая погрешность становится заметной, что проявляется в не вполне регулярной зависимости результатов вычислений от величины шага. Наконец, при достаточно малом шаге неустранимая погрешность становится преобладающей, и при дальнейшем уменьшении шага результат вычислений становится все меньше достоверным.
+
-
 
+
-
Полная погрешность мажорируется суммой <tex>R_k+r_k</tex> (штриховая кривая на рис.1). Оптимальным будет шаг, соответсвующий этой кривой. Нетрудно подсчитать, что
+
-
 
+
-
{{eqno|10}}
+
-
::<tex>h_0(\delta)={\left( \frac{k\delta \sum|C_q|}{pC} \right)}^{\frac{1}{p+k}}=O(\delta^{\frac{1}{p+k}})</tex>.
+
-
 
+
-
::<tex>\min(R_k+r_k)=Ch_0^p \left( 1+\frac{p}{k} \right) =O\left(\delta^{\frac{p}{p+k}} \right) </tex>.
+
-
 
+
-
Меньший шаг невыгоден, а меньшая погрешность, вообще говоря, недостижима (хотя отдельные вычисления случайно окажутся более точными, но мы не сможем этого узнать). Эта минимальная ошибка тем менее, чем меньше погрешность входных данных и порядок вычисляемой производной и чем выше порядок точности формулы.
+
-
 
+
-
Очевидно, при <tex>\delta y(x)\to 0</tex> можно получить сколь угодно высокую точность результата, если шаг стремится к нулю, будучи всегда не менее <tex>h_0(\delta)</tex>. Но если допустить <tex>h<h_0(\delta)</tex>, то результат предельного перехода может быть неправильным.
+
-
 
+
-
Эта тонкость связана с некорректностью задачи дифференцирования. Рассмотрим погрешность входных данных вида <tex>\delta y(x)= m^{-1}\sin (m^2 x)</tex>. Она приводит к погрешности первой производной <tex>\delta y'(x) = m \cos (m^2 x)</tex>. При <tex>m \to \infty</tex> погрешность функции неограниченно убывает, а погрешность производной в той же норме неограниченно растет. Значит, нет непрерывной зависимости производной от функции, то есть дифференцирование некорректно. Особенно сильно это сказывается при нахождении производных высокого порядка.
+
-
 
+
-
Изложенный выше способ определения оптимального шага и запрещение вести расчет шагом меньше оптимального есть некоторый способ регуляризации дифференцирования, так называемая регуляризация по шагу.
+
-
 
+
-
Стоит заметить, что с ростом <tex>p</tex>, количества узлов в сетке для вычисления производных, константы <tex>C_q</tex> и <tex>C</tex> в формулах {{eqref|10}} повышаются, поэтому увеличение <tex>p</tex> разумно лишь в определенных пределах.
+
-
 
+
-
== Числовые примеры ==
+
-
=== Пример 1 ===
+
-
Пример приведен в качестве иллюстрации некорректности задачи численного дифференцирования. Вторая производная функции <tex>y(x)=x^4</tex> в точке <tex>x=1</tex> была вычислена с разными значениями шага <tex>h</tex> по формулам {{eqref|1}} и {{eqref|2}}. Полученный результат сравнивается с вычисленным аналитически значением производной: <tex> y''(x)|_{x=1}=12x^2|_{x=1}=12</tex>. Результаты приведены в таблице.
+
-
::{| border=1
+
-
! Значение <tex>h</tex>|| Результат формулы {{eqref|1}}|| Относительная ошибка {{eqref|1}}||Результат формулы {{eqref|2}}|| Относительная ошибка {{eqref|2}}
+
|-
|-
-
| 1e-2 || 12.0002 || 1.7e-5 || 12 || 2e-15
+
|Y = predict_sSVM(X, model)
|-
|-
-
| 1e-4 || 12.0000001|| 1.7e-9 || 12 || 4e-11
+
|ВХОД
|-
|-
-
| 1e-6 || 11.9997 || 2.2e-5 || 11.9994 || 5e-5
+
|
 +
{|border="0"
 +
|X — выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
 +
|-
 +
|&nbsp;&nbsp; 'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
 +
|-
 +
|&nbsp;&nbsp; 'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
 +
|-
 +
|&nbsp;&nbsp; 'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
 +
|-
 +
|model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки);
 +
|}
|-
|-
-
| 1e-8 || 6.66 || 0.8 || 4.6 || 1.6
+
|ВЫХОД
|-
|-
-
| 1e-9 || 444 || 0.97 || 666 || 0.98
+
|
-
|}
+
{|
-
Вычисления проводились в стандартном типе [http://en.wikipedia.org/wiki/Double_precision double] (позволяет хранить 15 значащих десятичных цифр) языка [http://ru.wikipedia.org/wiki/C%2B%2B C++].
+
|Y — ответы на выборке X, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
 +
|}
 +
|}
-
Видно, что при слишком малом шаге полученные значения неадекватны.
 
-
=== Пример 2 ===
+
{|class="standard"
-
Этот пример иллюстрирует то, что при выборе оптимального шага, соответсвующего теоретическим выкладкам, получаются неплохие результаты.
+
!''Обучение и предсказание для базы с машинами''
-
 
+
|-
-
::{| border=1
+
|[train_error, test_Y] = cars()
-
! width=55%|Анализируемая функция
+
|-
-
| width=15%|<tex>x^4</tex>
+
|ВЫХОД
-
| width=15%|<tex>e^x</tex>
+
|-
-
| width=15%|<tex>\sin x</tex>
+
|
-
|-
+
{|
-
!Точка анализа
+
|train_error — ошибка на обучающей выборке;
-
| 1
+
|-
-
| 7
+
|test_Y — ответы на тестовой выборке, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения.
-
| 0
+
|}
-
|-
+
-
!Значение второй производной
+
-
| 12
+
-
| 1096.6331584
+
-
| 0
+
-
|-
+
-
!Результат метода {{eqref|1}}
+
-
| 12.0000002
+
-
| 1096.6335
+
-
| -1.8e-13
+
-
|-
+
-
!Выбранный шаг метода {{eqref|1}}
+
-
| 0.00032
+
-
| 0.0018
+
-
| 0.0046
+
-
|-
+
-
!Теоретическая ошибка метода {{eqref|1}}
+
-
| 4e-7
+
-
| 0.014
+
-
| 4e-7
+
-
|-
+
-
! Реальная ошибка метода {{eqref|1}}
+
-
| 2e-7
+
-
| 0.0003
+
-
| 1.8e-13
+
-
|-
+
-
!Результат метода {{eqref|2}}
+
-
| 12.00000000
+
-
| 1096.6331578
+
-
| 3e-14
+
-
|-
+
-
!Выбранный шаг метода {{eqref|2}}
+
-
| 0.0046
+
-
| 0.015
+
-
| 0.0046
+
-
|-
+
-
!Теоретическая ошибка метода {{eqref|2}}
+
-
| 3e-8
+
-
| 0.003
+
-
| 3e-8
+
-
|-
+
-
!Реальная ошибка метода {{eqref|2}}
+
-
| 1.6e-11
+
-
| 6e-7
+
-
| 3e-14
+
|}
|}
-
Вычисления проводились в стандартном типе [http://en.wikipedia.org/wiki/Double_precision double] (позволяет хранить 15 значащих десятичных цифр) языка [http://ru.wikipedia.org/wiki/C%2B%2B C++].
+
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог с данными.
-
 
+
-
Оба метода дают хорошую точность, не превосходящую теоретические оценки.
+
-
 
+
-
Сравнивая работу двух метотов вычисления производной, можно заметить, что второй из них получает ответ с большей точностью при меньшем шаге. Это соответсвует теоретическим выкладкам.
+
-
== Рекомендации программисту ==
+
=== Рекомендации по выполнению задания ===
 +
# Библиотека 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).
 +
# Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. При этом в крайних значениях нужно получить ситуации недообучения и переобучения. Начинать перебор лучше с заведомо заниженных значений параметра С, поскольку в этом случае метод работает быстрее.
-
При программировании не стоит забывать что полученные оценки погрешности и шага {{eqref|10}} зависят от оценок значений функции и производных соответсвующих порядков. Поэтому константа в асимтотической оценке может быть достаточно большая (в реализации автора - это произведение суммы коэффициентов формул {{eqref|1}} или {{eqref|2}} и значений функции в исследуемой точке).
+
=== Данные для выполнения задания ===
-
== Заключение ==
+
[[Media:GM_GraphCut.zip|graphCut]] — MATLAB интерфейс к разрезам графов.
-
В данном отчете получены теоретически и проверены практически два метода вычисления второй производной по одной переменной ({{eqref|1}} и {{eqref|2}} ).
+
-
И теоретические выкладки, и эксперименты показывают, что вопрос выбора шага - очень важный. Для его разрешения можно взять оптимальный шаг {{eqref|10}}.
+
-
Экспериментально подтверждено, что оба метода дают неплохие результаты и могут быть использованы при практическом вычислении второй производной по одной переменной.
+
[https://docs.google.com/open?id=0B_PZC3alifN6WDExQlR6cktSaUU База данных].
-
== Ссылки ==
+
[http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html MATLAB библиотека SVM-struct]
-
* [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]]
+
-
* [[Media:DeriveExample1.zip| Код примеров 1 и 2, ZIP [3Кб]]]
+
-
== Список литературы ==
+
=== Оформление задания ===
-
* ''А.А.Самарский, А.В.Гулин.''&nbsp; Численные методы. Москва «Наука», 1989.
+
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 5. ФИО». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
-
* ''Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков.''&nbsp; Численные методы. Лаборатория Базовых Знаний, 2003.
+
-
* ''Н.Н.Калиткин.''&nbsp; Численные методы. Москва «Наука», 1978.
+
-
{{stub}}
+
Письмо должно содержать:
-
[[Категория:Численное дифференцирование]]
+
*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»
Личные инструменты