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

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

< Участник:Anton(Различия между версиями)
Перейти к: навигация, поиск
 
(90 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''Критерии согласия''' - это критерии проверки гипотез о законе распределения вероятностей.
+
{{stop|
-
Такие критерии подразделяются на два класса:
+
'''Задание находится в разработке.'''<br/>
-
# '''Общие критерии согласия''' применимы к самой общей формулировке гипотезы, а именно к гипотезе о согласии наблюдаемых результатов с любым априорно предполагаемым распределением вероятностей.
+
Не приступайте к выполнению задания пока не убрано это сообщение.
-
# '''Специальные критерии согласия''' предполагают специальные нулевые гипотезы, формулирующие согласие с определенной формой распределения вероятностей.
+
}}
-
=Общие критерии согласия=
+
{{TOCright|300px}}
-
'''Нулевая гипотеза''' <tex>H_0: F_n(x) = F(x)</tex>, где <tex>F_n(x)</tex> - эмпирическая функция распределения вероятностей;
+
-
<tex>F(x)</tex> - гипотетическая функция распределения вероятностей.
+
-
Группы общих критериев согласия:
+
{{Main|Графические модели (курс лекций)}}
-
*критерии, основанные на изучении разницы между теоретической плотностью распределения и эмпирической гистограммой;
+
-
*критерии, основанные на расстоянии между теоретической и эмпирической функциями распределения вероятностей;
+
-
==Критерии, основанные на сравнении теоретической плотности распределения и эмпирической гистограммы==
+
[[Изображение:GM12 task4 intro.png‎ | 600px]]
-
*[[Критерий хи-квадрат|Критерий согласия хи-квадрат]] <ref>''Karl Pearson.'' On the Criterion that a Given System of Deviations from the Probable in the Case of Correlated System of Variables is such that it can be Reasonably Supposed to have Arisen from Random Sampling, Philosophical Magazine, 50, 157-175, 1900. </ref>
+
-
*[[Критерий числа пустых интервалов]] <ref>''Идье В., Драйад Д., Джеймс Ф., Рус М., Садуле Б.'' Статистические методы в экспериментальной физике. — М.:&nbsp;Атомиздат, 1976.</ref>
+
-
*[[Квартильный критерий Барнетта-Эйсена]] <ref>''Barnett A., Eisen E.'' A quartile test for differences in distribution. JASA. 1982. V. 77, №377. P. 47-51</ref>
+
-
==Критерии, основанные на сравнении теоретической и эмпирической функций распределения вероятностей==
+
'''Начало выполнения задания''': 18 апреля 2012
-
Расстояние между эмпирической и теоретической функциями распределения вероятностей является весьма эффективной статистикой для проверки гипотез о виде закона распределения вероятностей случайной величины.
+
-
Критерии согласия, использующие различные варианты анализа расстояния между теоретической (<tex>\Phi(x)</tex>) и эмпирической (<tex>F(x)</tex>) функциями распределения:
+
'''1-й этап сдачи задания''': {{ins|2 мая 2012, 23:59}}
 +
 
 +
'''2-й этап сдачи задания''': {{ins|9 мая 2012, 23:59}}
 +
 
 +
Среда реализации для всех вариантов — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
 +
 
 +
=== Сегментация изображений ===
 +
В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон.
 +
В дальнейшем работа осуществляется в терминах небольших сегментов изображения — суперпикселей.
 +
Заметим, что по «суперпиксельной» сегментации изображения можно однозначно построить «попиксельную» сегментацию.
 +
 
 +
Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: <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>
 +
 
 +
Здесь 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 #(суперпиксели).
 +
 
 +
=== Спецификация реализуемых функций ===
{|class="standard"
{|class="standard"
-
! Название критерия
+
!''Обучение''
-
! Функционал расстояния
+
|-
|-
-
| [[Критерий Джини]]
+
|[model, time] = train_sSVM(X, Y, options)
-
| <tex> \int | F(x) - \Phi(x) | dx </tex>
+
|-
|-
-
| [[Критерий Крамера-фон Мизеса]]
+
|ВХОД
-
| <tex> \int \{ F(x) - \Phi(x) \}^2 dx </tex>
+
|-
|-
-
| [[Критерий Колмогорова-Смирнова]] <ref>''Kolmogorov A. N.'' Confidence limits for an unknown distribution function. AMS. 1941. V. 12. P. 461-463.</ref> <ref>''Смирнов Н.В.'' Оценка расхождения между эмпирическими кривыми распределений в двух независимых выборках. Бюллетенеь МГУ. Сер. А. Вып.2. 1939. С. 13-14.</ref>
+
|
-
| <tex> \sup_{-\infty < x < \infty} |F(x) - \Phi(x)| </tex>
+
{|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' — порог для добавления ограничений в рамках метода отсекающих плоскостей;
 +
|}
|-
|-
-
| [[Критерий Реньи| Критерий Реньи (R-критерий)]] <ref> ''Renyi A.'' On the theory of order statistics. Acta Mathem. Acad. Scientarium Hungarical. 1953. V. 4. P. 191-232.</ref>
+
|ВЫХОД
-
| <tex> \sup_{F(x) > a} \frac{|F(x) - \Phi(x)|}{F(x)} </tex>
+
|-
|-
-
| [[Критерий омега-квадрат|Критерий Смирнова-Крамера-фон Мизеса (Критерий омега-квадрат)]] <ref>''Смирнов Н.В.'' О критерии Крамера-фон Мизеса. Успехи матем. наук (новая серия). 1949. Т. 4. №4(32). С. 196-197.</ref> <ref>''Мартынов Г.В.'' Критерии омега-квадрат. - М.:Наука. 1978.</ref>
+
|
-
| <tex> \int \{ F(x) - \Phi(x) \}^2 d\Phi(x) </tex>
+
{|
 +
|model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки).
 +
|-
 +
|time — время работы алгоритма;
 +
|}
 +
|}
 +
 
 +
 
 +
{|class="standard"
 +
!''Предсказание''
|-
|-
-
| [[Критерий Андерсона-Дарлинга]] <ref> ''Anderson T.W., Darling D.A.'' A test for goodness-of-fit. JASA. 1954. V. 49. P. 765-769. </ref>
+
|Y = predict_sSVM(X, model)
-
| <tex> \int \frac{\{ F(x) - \Phi(x) \}^2}{\Phi(x)\{1 - \Phi(x)\}}d\Phi(x) </tex>
+
|-
|-
-
| [[Критерий Купера]] <ref>''Kuiper N.H.'' Tests concerning random points on a circle. Proc. Konikl. Nederl. Akad. Van Wettenschappen. 1960. S. A. V. 63. P. 38-47.</ref>
+
|ВХОД
-
| <tex> \sup_{-\infty < x < \infty} \{F(x) - \Phi(x)\} + \sup_{-\infty < x < \infty} \{ \Phi(x) - F(x) \} </tex>
+
|-
|-
-
| [[Критерий Ватсона]] <ref>''Watson G.S.'' Googness-of-fit tests on a circle. Biometrika. 1961. V. 48. № 1-2. P. 109-114.</ref>
+
|
-
| <tex> \int \left\{ F(x) - \Phi(x) - \int \left[ F(x) - \Phi(x) \right]d\Phi(x) \right\} d\Phi(x) </tex>
+
{|border="0"
 +
|X — выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
 +
|-
 +
|&nbsp;&nbsp; 'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
 +
|-
 +
|&nbsp;&nbsp; 'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
 +
|-
 +
|&nbsp;&nbsp; 'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
 +
|-
 +
|model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки);
 +
|}
|-
|-
-
| [[Критерий Фроцини]] <ref>''Frozini B. V.'' On the distribution and power of a goodness-of-fit statistic with parametric and nonparametric applications. "Goodness-of-fit". Ed. by Revesz P., Sarkadi K., Sen P.K., Amsterdam-Oxford- New York: North-Holland. Publ. Comp., 1987, P. 133-154.</ref>
+
|ВЫХОД
-
| <tex> \int | F(x) - \Phi(x) | d\Phi(x) </tex>
+
|-
|-
 +
|
 +
{|
 +
|Y — ответы на выборке X, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
 +
|}
|}
|}
-
Другие критерии:
 
-
*[[Критерии согласия Дарбина]] <ref>''Darling J.'' The Kolmogorov-Smirnov, Cramer-von Mises tests. AMS. 1957. V. 28. P. 823-838.</ref> <ref>''Durbin J.'' Some methods of constructing exact tests. Biometrika. 1961. V. 48. № 1-2. P. 41-57.</ref>
 
-
=Специальные критерии согласия=
+
{|class="standard"
-
==Нормальное распределение==
+
!''Обучение и предсказание для базы с машинами''
-
Нормальный закон распределения вероятностей получил наибольшее распространение в практических задачах обработки экспериментальных данных. Большинство прикладных методов математической статистики исходит из предположения нормальности распределения вероятностей изучаемых случайных величин.
+
|-
-
Широкое распространения этого распределения вызвало необходимость разработки [[Критерии нормальности|специальных критериев согласия эмпирических распределений с нормальным]].
+
|[train_error, test_Y] = cars()
-
Существуют как модификации общих критериев согласия, так и критерии, созданные специально для проверки нормальности.
+
|-
-
 
+
|ВЫХОД
-
==Экспоненциальное распределение==
+
|-
-
Экспоненциальный закон распределения вероятностей является базовым законом, используемым в теории надежности. Его аналитическая простота делает его привлекательным для инженеров и исследователей.
+
|
 +
{|
 +
|train_error — ошибка на обучающей выборке;
 +
|-
 +
|test_Y — ответы на тестовой выборке, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения.
 +
|}
 +
|}
-
Существует большое количество специальных критериев согласия для экспоненциального распределения:
+
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог с данными.
-
*Критерий Шапиро-Уилка для экспоненциального распределения <ref>''Shapiro S.S., Wilk M.B.'' An analisys of variance test for the exponential distribution (complete samples). Technometrics. 1972. V. 14. P. 355-370. </ref>
+
-
*Критерии типа Колмогорова-Смирнова <ref>''Spinelli J.J., Stephens M.A.'' Tests for exponentiality when origin and scale paramters are unknown. Technometrics. 1987. V. 29. № 4. P. 471-476.</ref> <ref>''Spurrier J.D.'' On overview of tests of exponentiality. Commun. Stat.-Theor. Meth. 1984. V. 13. P. 1635-1654.</ref>
+
-
*Критерии типа Смирнова-Крамера-фон Мизеса для цензурированных данных. <ref>''Pettit A.N.'' Tests for the exponentionality distribution with censored data using Cramer-von Mises statistics. Biometrika. 1977. V. 64. № 3. P. 629-632.</ref>
+
-
*Критерий Фроцини для экспоненциального распределения. <ref>''Frozini B. V.'' On the distribution and power of a goodness-of-fit statistic with parametric and nonparametric applications. "Goodness-of-fit". Ed. by Revesz P., Sarkadi K., Sen P.K., Amsterdam-Oxford- New York: North-Holland. Publ. Comp., 1987, P. 133-154.</ref>
+
-
*Корреляционный критерий экспоненциальности <ref>''Spinelli J.J., Stephens M.A.'' Tests for exponentiality when origin and scale paramters are unknown. Technometrics. 1987. V. 29. № 4. P. 471-476.</ref>
+
-
*Регрессионный критерий Брейна-Шапиро <ref>''Brain C.W., Shapiro S.S.'' A regression test for exponentiality: censored and complete samples. Technometrics. 1983. V. 25. № 1. P. 69-76.</ref>
+
-
*Критерий Кимбера-Мичела. <ref>''Kimber A.C.'' Tests for the exponential, Weibull and Gumbel distributions based on the stabilized probability plot. Biometrika. 1985. V. 72. № 3. P. 661-663.</ref>
+
-
*Критерий Фишера для экспоненциального распределения. <ref>''Кобзарь А. И.'' Прикладная математическая статистика. — М.:&nbsp;Физматлит, 2006. Стр. 293.</ref>
+
-
*Критерий Бартлетта-Морана. <ref>''Moran P. A. P.'' The randomdivision of an interval, 11, JRSS, 1951, V. 13, P. 147-150.</ref> <ref>''Кокс С., Льюис П.'' Статистический анализ последовательностей событий. Пер. с англ. - М.: Мир. 1969.</ref>
+
-
*Критерий Климко-Антла-Радемакера-Рокетта <ref>''Klimko L. A., Antle C. E., Rademaker A. W., Rockette H. E.'' Upper bounds for the power of invariant tests for the exponential distribution with Weibull alternative. Tachnometrics. 1975. V. 17. № 3. P. 357-360.</ref>
+
-
*Критерий Холлендера-Прошана <ref>''Hollander M., Proshan F.'' Testing whether new is better than used. AMS. 1972. V. 43. P. 1136-1146.</ref> <ref>''Sturges H. A.'' The choice of a class interval. JASA. 1926. V .21. P. 65-66.</ref>
+
-
*Критерий Кочара <ref>''Kochar S. C.'' Testing exponentiality against monotone failure rate average. Commun. Stat.-Theor. Meth. 1985. № 2. P. 381-392.</ref>
+
-
*Критерий Эппса-Палли-Чёрго-Уэлча <ref>''Epps T.W., Pulley L.B.'' A test of exponentiality vs. monotone-hazard alternatives from the emphirical characteristics function. JRSS. Sec. B. 1986. V. 48. № 2. P. 206-216.</ref>
+
-
*Критерий Бергмана <ref>''Bergman B.'' Crossing in the total time on test plot. Scand. J. Statist. 1977. V. 4. P. 171-177.</ref>
+
-
*Критерий Шермана <ref>''Sherman B.'' Percentiles of the <tex>\omega_n</tex> statistic. AMS. 1957. V. 28. № 1. P. 257-261.</ref>
+
-
*Критерий наибольшего интервала <ref>''Гнеденко Б. В., Беляев Ю. К., Соловьев А. Д.'' Математические методы в теории надежности. - М.: Наука, 1965.</ref>
+
-
*Критерий Хартли <ref>''Hartley H. O.'' The maximum F-ratio as a short-cut test of heterogeneity of variance. Biometrika. 1950. V. 37. P. 308-312.</ref>
+
-
*Критерий показательных меток <ref>''Кокс С., Льюис П.'' Статистический анализ последовательностей событий. Пер. с англ. - М.: Мир. 1969.</ref>
+
-
*Ранговый критерий независимости интервалов <ref>''Wald. A., Wolfowitz J.'' An exact test of randomness in the nonparametric case based on serial correlation. AMS 1943. V. 14. P. 378-388.</ref> <ref>''Кокс С., Льюис П.'' Статистический анализ последовательностей событий. Пер. с англ. - М.: Мир. 1969.</ref>
+
-
*Критерии, основанные на трансформации экспоненциального распределения в равномерное
+
-
**Критерии <tex> \overline{U}, \widetilde{U}</tex> <ref> ''Кобзарь А. И.'' Прикладная математическая статистика. — М.:&nbsp;Физматлит, 2006. Стр. 308. </ref>
+
-
**Критерий Гринвуда <ref>''Greenwood V.'' The statistical study of infection discase. JRSS. Sec. A. 1946. V. 109. P. 85-110.</ref>
+
-
*Критерий Манн-Фертига-Шуера для распределения Вейбулла <ref>''Капур К., Ламберсон Л.'' Надежность и проектирование в технике. - М.: Мир. 1980.</ref>
+
-
*Критерий Дешпанде <ref>''Deshpande J. V.'' A class of tests for exponentiality against increasing failure rate average alternatives. Biometrika. 1983. V. 70. P. 514-518.</ref>
+
-
*Критерий Лоулесса <ref>''Lawless J. F.'' Statistical models and methods for lifetime data. - N.Y.: J. Welley, 1982.</ref>
+
-
==Равномерное распределение==
+
=== Рекомендации по выполнению задания ===
-
Если <tex>x_1, \dots, x_n </tex> - выборка из распределения вероятностей с функцией <tex>F(x)</tex>, то случайная величина <tex> y_i = F(x_i) </tex> распределена равномерно на интервале [0,1]. Поэтому установление равномерности распределения является по существу критерием согласия наблюдаемых данных с любым теоретическим распределением. Этим и объясняется повышенный интерес к поиску простых в вычислительном отношении и эффективных критериев равномерности распределения.
+
# Библиотека SVM-struct не позволяет установить ограничения на знак весов парных признаков <tex> \vec{w}^P </tex>. Для минимизации получающихся несубмодулярных функций рекомендуется отбрасывать несубмодулярные ребра.
-
*Критерий Кимбела <ref>''Kimball B F.'' Some basic theorems for developing tests of fit for the case of the nonparametric probability distribution function. 1. AMS. 1947. V. 18. P. 540-548.</ref>
+
# В качестве модельных данных рекомендуется использовать выборку, состоящую из 2-3 изображений обучающей выборки. При правильной реализации алгоритма точность сегментации изображений, использовавшихся при обучении должна быть высокой (более 97% в терминах ошибки, усредненной по классам).
-
*Критерий Морана <ref>''Moran P. A. P.'' The random division of an intervals. JRSS. 1947. Sec. B. V. 9. P. 92-98.</ref>
+
# Для работы с библиотекой SVM-struct необходимо реализовать функцию поиска наиболее нарушаемого ограничения (CONSTRAINTFN), функцию построения вектора обобщенных признаков (FEATUREN), функцию потерь (LOSSFN). Библиотеку SVMstruct рекомендуется запускать со следующими параметрами: -p 1 -o 2 -w 4 -v 3 -y 0 -c <ваш C> -e <ваш eps>.
-
*Критерий омега-квадрат <ref>''Smirnoff N.'' Sur la distribution de <tex>n\omega^2</tex>. Compte Rendus de l'Academie des Sciences. Paris. 1932. № 202. P. 449.</ref>
+
# На этапе отладки параметр eps стоит выбрать достаточно большим (например, 10), чтобы уменьшить время работы алгоритма. На этапе экспериментов значение eps стоит уменьшить на несколько порядков.
-
*Критерий Шермана <ref>''Sherman B.'' A random variable related to the spacing of sample values. AMS. 1950. V. 21. № 3. P. 339-361.</ref>
+
# При правильной реализации метода одна операция обучение sSVM на полной выборке должна работать не более получаса.
-
*Критерий Ченга-Спиринга <ref>''Cheng S. W., Spiring F. A.'' A test to identify the uniform distribution with applications to probability plotting and other distributions. IEEE Trans. Reliability. 1987. V. R-36. № 1. P. 98-105.</ref>
+
# В качестве процедуры скользящего контроля рекомендуется выбрать схему [[Скользящий контроль| контроля по 2 блокам]] (2-fold CV).
-
*Критерий Саркади-Косика <ref>''Kosik P., Sarkadi K.'' A new goodness-of-fit test. Proc. of 5-th Pannonian Symp. of Math. Stat., Visegrad. Hungary. 20-24 May, 1985, P. 267-272.</ref>
+
# Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. При этом в крайних значениях нужно получить ситуации недообучения и переобучения. Начинать перебор лучше с заведомо заниженных значений параметра С, поскольку в этом случае метод работает быстрее.
-
*Энтропийный критерий Дудевича-ван дер Мюлена <ref>''Dudewiez E. J., van der Meulen E. C.'' Entropy-based tests of uniformity. JASA. 1981. V. 76. № 376. P. 967-974.</ref>
+
-
*Критерий равномерности Хегахи-Грина <ref>''Hegazy Y. A. S., Green J. R.'' Some new goodness-of-fit tests using order statistics. Appl. Statist. 1975. V. 24. № 3. P. 299-308.</ref>
+
-
*Критерий Янга <ref>''Young D. L.'' The linear nearest neighbour statistic. Biometrika. 1982. V. 69. № 2.P. 477-480.</ref>
+
-
*Критерии типа Колмогорова-Смирнова <ref>''Кобзарь А. И.'' Прикладная математическая статистика. — М.:&nbsp;Физматлит, 2006. Стр. 330</ref>
+
-
*Критерий Фроцини для равномерного распределения <ref>''Frozini B. V.'' On the distribution and power of a goodness-of-fit statistic with parametric and nonparametric applications. "Goodness-of-fit". Ed. by Revesz P., Sarkadi K., Sen P.K., Amsterdam-Oxford- New York: North-Holland. Publ. Comp., 1987, P. 133-154.</ref>
+
-
*Критерий Гринвуда-Кэсенберри-Миллера <ref>Quesenberry C. P., Miller F. L.'' Power studies of some tests for uniformity. J. Statist. Comput. Simul. 1977. V. 5. P. 169-191.</ref>
+
-
*"Сглаженный" критерий Неймана-Бартона <ref>''Neyman J.'' "Smooth" tests for goodness-of-fit. Scand. Aktuarietidsrift. 1937. V. 20. P. 149-199.</ref>
+
-
==Критерии симметрии==
+
=== Данные для выполнения задания ===
-
Если отсутствуют предпосылки для проверки согласия эмпирического распределения с каким-либо теоретическим, то выявление даже самых общих свойств эмпирического распределения дает некоторую информацию для выбора приемов и методов обработки экспериментального материала.
+
-
Одним из таких практически важных свойств распределения является его симметричность относительно центра группирования значений случайной величины.
+
[[Media:GM_GraphCut.zip|graphCut]] — MATLAB интерфейс к разрезам графов.
-
Существует много критериев, проверяющих симметрию:
+
-
*"Быстрый" критерий Кенуя <ref>''Кенуй М. Г.'' Быстрые статистические вычисления. Упрощенные методы оценивания и проверки. - М.: Статистика. 1979.</ref>
+
-
*Критерий симметрии Смирнова <ref>''Смирнов Н. В.'' О критерии симметрии закона распределения случайной величины. ДАН СССР. 1947. Т. 56. № 1. С. 13-16.</ref>
+
-
*Знаковый критерий симметрии <ref>''Кобзарь А. И.'' Прикладная математическая статистика. — М.:&nbsp;Физматлит, 2006. Стр. 337. </ref>
+
-
*Одновыборочный критерий Вилкоксона <ref>''Wilcoxon F.'' Individual comparisons by ranking methods. Biometrics, Bull. 1945. V. 1. P. 80-83.</ref>
+
-
*Критерий Антилла-Керстинга-Цуккини <ref>''Antille A., Kersting G., Zicchini W.'' Testing symmetry. JASA. 1982. V. 77. № 379. P. 639-646.</ref>
+
-
*Критерий Бхатачарья-Гаствирта-Райта (модифицированный критерий Вилкоксона) <ref>''Bhattachrya P. K. Gastwirth J. L. Wright A. L.'' Two modified Wilcoxon tests for symmetry about an unknown location parameters. Biometrika. 1982. V. 69. № 2. P. 377-382.</ref>
+
-
*Критерий Финча <ref>''Finch S. J.'' Robust univariate test of symmetry. JASA. 1977. V. 72. № 358. P. 387-392.</ref>
+
-
*Критерий Бооса <ref>''Boos D. D.'' A test for summetry assotiated with the Hodges-Lehmann estimator. JASA. 1982. V. 77. № 379. P. 647-651.</ref>.
+
-
*Критерий Гупты <ref>''Gupta M. K.'' An asymptotically nonparametric test of symmetry. AMS. 1967. V. 38. P. 849-866.</ref>
+
-
*Критерий Фрезера <ref>''Fraser D. A. S.'' Most powerfull rank-type tests. AMS. 1957. V. 28. P. 1040-1043.</ref>
+
 +
[https://docs.google.com/open?id=0B_PZC3alifN6WDExQlR6cktSaUU База данных].
-
=Ссылки=
+
[http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html MATLAB библиотека SVM-struct]
-
<references/>
+
-
=Литература=
+
=== Оформление задания ===
-
# ''Кобзарь А. И.'' Прикладная математическая статистика. — М.:&nbsp;Физматлит, 2006. — 816&nbsp;с.
+
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 5. ФИО». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
-
# ''Лагутин М. Б.'' Наглядная математическая статистика. В двух томах. — М.: П-центр, 2003. — 204-209 с.
+
-
{{Задание|Anton|Vokov|8 января 2010}}
+
Письмо должно содержать:
 +
*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://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»
Личные инструменты