Математические основы теории прогнозирования (курс лекций)/2012/Задание СФ

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

(Различия между версиями)

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

Содержание

1 Необходимая теория
2 Формулировка задания
3 Процедура сдачи задания
- 3.1 Оформление задания
- 3.2 Защита задания

Основная статья: Математические основы теории прогнозирования (курс лекций)

Срок сдачи задания: 30 августа 2012, 23:59

Данное практическое задание предназначено, в первую очередь, для студентов Севастопольского филиала, которые имеют задолженность по курсу МОТП и не имеют возможности присутствовать в Москве на пересдачах осенью. Тем не менее, это задание могут выполнять и московские студенты ВМиК, которые имеют задолженность по курсу МОТП. Оценка за это задание будет итоговой оценкой по курсу.

Цель данного задания состоит в том, чтобы студенты познакомились на практике с популярными методами решения задач классификации и кластеризации — методом опорных векторов и методом к-средних, а также с базовыми аспектами, с которыми приходится сталкиваться при решении задач машинного обучения — проблемой переобучения и проблемой подбора структурных параметров алгоритма (таких как коэффициент С и параметры ядровых функций).

Задание выполняется в среде MATLAB.

Вопросы по заданию можно оставлять на вкладке «обсуждение» к этой странице, либо адресовать письмом на bayesml@gmail.com. В название письма просьба добавлять [МОТП12].

Необходимая теория

Метод опорных векторов

Иллюстрация линейного разделения выборки с помощью метода опорных векторов, зелеными кружками отмечены опорные объекты

Рассматривается задача классификации на два класса. Имеется обучающая выборка $\{\vec{x}_n,t_n\}_{n=1}^N$ , где $\vec{x}_n\in\mathbb{R}^d$ — вектор признаков для объекта $n$ , а $t_n\in\{-1,+1\}$ — его метка класса. Задача заключается в предсказании метки класса $t_{new}$ для объекта, представленного своим вектором признаков $\vec{x}_{new}$ .

В методе опорных векторов предсказание метки класса осуществляется по знаку линейной функции:

$t(\vec{x}_{new}) = \begin{cases}+1,\ f(\vec{x}_{new})=\vec{w}^T\vec{x}_{new} + b = \sum_{j=1}^dw_jx_{j,new} + b\ge 0,\\-1,\ f(\vec{x}_{new})<0.\end{cases}$

Для поиска весов $\vec{w}$ и величины сдвига $b$ решается следующая задача квадратичного программирования:

$\sum_{n=1}^N\lambda_n - \frac{1}{2}\sum_{n,m=1}^N\lambda_n\lambda_mt_nt_m\vec{x}_n^T\vec{x}_m\rightarrow\max_{\vec{\lambda}}$

$\sum_n\lambda_nt_n=0,$

$0\le\lambda_n\le C.$

Здесь $C>0$ — параметр алгоритма, который задает компромисс между точностью распознавания обучающей выборки и величиной зазора между данными и гиперплоскостью (надежностью классификации).

После решения задачи квадратичного программирования оптимальный вектор весов вычисляется как

$\vec{w} = \sum_{n=1}^N\lambda_nt_n\vec{x}_n$ .

Очевидно, что только те объекты обучающей выборки, для которых $\lambda_n\neq 0$ , влияют на оптимальный вектор весов. Такие объекты получили название опорных. Пусть $\exist n_*:\ 0<\lambda_{n_*}<C$ . Тогда оптимальная величина сдвига гиперплоскости $b$ определяется как

$b = t_{n_*} - \vec{w}^T\vec{x}_{n_*}$ .

На практике здесь лучше проводить усреднение по всем $n:\ 0<\lambda_n<C$ . Если в оптимальном $\vec{\lambda}$ все коэффициенты равны только нулю и $C$ , то тогда коэффициент $b$ может быть найден перебором путем минимизации ошибки распознавания обучающей выборки.

Использование ядровых функций

Иллюстрация нелинейного разделения выборки с помощью метода опорных векторов с радиальной ядровой функцией, зелеными кружками отмечены опорные объекты

Для построения нелинейных решающих правил с помощью метода опорных векторов вводится понятие ядровой функции. Пусть имеется преобразование из исходного признакового пространства $\mathbb{R}^d$ в новое пространство $H$ , задаваемое функцией $\phi:\mathbb{R}^d\rightarrow H$ . Пусть также имеется ядровая функция $K$ , которая задает скалярное произведение в новом пространстве $H$ :

$K(\vec{x},\vec{y}) = \phi(\vec{x})^T\phi(\vec{y}),\ \forall\vec{x},\vec{y}.$

Тогда для построения линейной разделяющей гиперплоскости в новом пространстве $H$ достаточно знать лишь ядровую функцию $K$ и не требуется знать само преобразование $\phi$ . В этом случае на этапе обучения метода решается следующая задача квадратичного программирования:

$\sum_{n=1}^N\lambda_n - \frac{1}{2}\sum_{n,m=1}^N\lambda_n\lambda_mt_nt_mK(\vec{x}_n,\vec{x}_m)\rightarrow\max_{\vec{\lambda}},$

$\sum_n\lambda_nt_n = 0,$

$0\le \lambda_n\le C.$

При этом скалярное произведение оптимального вектора весов $\vec{w}$ и произвольного объекта $\vec{x}$ определяется как

$\vec{w}^T\vec{x} = \sum_{n=1}^N\lambda_nt_nK(\vec{x}_n,\vec{x}).$

По-прежнему, только опорные объекты (для которых $\lambda_n\neq 0$ ) вносят вклад в значение данного скалярного произведения. Величина сдвига гиперплоскости, как и раньше, определяется как

$b = \frac{\sum_{n:0<\lambda_n<C}(t_n - \vec{w}^T\vec{x}_n)}{\sum_{n:0<\lambda_n<C}1}.$

Если все коэффициенты $\lambda_n$ принимают только крайние значения, то оптимальный сдвиг $b$ находится путем минимизации числа ошибок на обучающей выборке.

Ядровая функция, как правило, выбирается в одном из следующих параметрических семейств:

Линейная: $K(\vec{x},\vec{y}) = \vec{x}^T\vec{y}$ ,
Степенная: $K(\vec{x},\vec{y}) = (\vec{x}^T\vec{y}+1)^r,\ r\in\mathbb{N}$ .
Радиальная: $K(\vec{x},\vec{y}) = \exp\left(-\frac{||\vec{x}-\vec{y}||^2}{2\gamma^2}\right),\ \gamma>0$ .

В случае степенной ядровой функции делается неявное предположение о том, что данные отнормированы на нулевой центр и единичную дисперсию. В этом случае, по неравенству Коши-Буняковского, величина $\vec{x}^T\vec{y}+1$ всегда будет неотрицательной.

Скользящий контроль

В методе опорных векторов параметр регуляризации $C$ , а также параметры ядровых функций (например, параметр $\gamma$ в радиальной ядровой функции) являются структурными параметрами, которые не могут быть настроены путем минимизации числа ошибок на обучающей выборке. Для их настройки используются критерии выбора модели, например, скользящий контроль.

Обозначим обучающую выборку через $Y=(X,\vec{t})$ , а через $a(\vec{x},Y)$ — результат прогноза метки класса для объекта $\vec{x}$ , полученный с помощью алгоритма $a$ , обученного по выборке $Y$ . При $K$ -кратном скользящем контроле обучающая выборка $Y$ разбивается на $K$ равных частей $Y=Y_1\sqcup Y_2\sqcup\dots\sqcup Y_K$ . Общая величина ошибки на $K$ -кратном скользящем контроле вычисляется как

$Error_{cv} = \frac{1}{N}\sum_{k=1}^K\ \sum_{n:\vec{x}_n\in Y_k}I[t_n \neq a(\vec{x}_n, Y_{\backslash k})]$ .

Здесь через $Y_{\backslash k}$ обозначена обучающая выборка без части $Y_k$ , а через $I[t \neq y]$ — индикаторная функция, равная единице при выполнении условия $t \neq y$ .

Наиболее популярная версия скользящего контроля — усреднение $Error_{cv}$ по пяти независимым запускам 2-кратного скользящего контроля. При таком подходе необходимо обучать алгоритм только по половине обучающей выборки (что происходит быстрее, чем обучение, например, по 9/10 от объема обучающей выборки). Во-вторых, здесь требуется всего 10 различных обучений (что гораздо меньше, чем, например, объем обучающей выборки $N$ при разбиении выборки на $K=N$ частей).

Настройка параметра регуляризации $C$ с помощью скользящего контроля производится следующим образом. Выбирается набор возможных значений $C$ , например, $2^{-5},2^{-4},\dots,2^{4},2^{5}$ . Для каждого из этих значений вычисляется величина ошибки скользящего контроля (например, с помощью усреднения по пяти запускам 2-кратного скользящего контроля). В результате выбирается такое значение $C$ , для которого величина ошибки скользящего контроля является наименьшей. В том случае, если требуется настроить два параметра, например $C$ и $\gamma$ в радиальных базисных функциях, то выбирается двухмерная сетка значений параметров и находится та пара, для которой ошибка на скользящем контроле является наименьшей.

Схема решения задач классификации

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

Метод K средних

Кластеризация выборки на 5 кластеров с помощью метода К средних

Рассматривается задача кластеризации. Имеется выборка $\{\vec{x}_n\}_{n=1}^N$ , где $\vec{x}_n\in\mathbb{R}^d$ — вектор признаков для объекта $n$ . Задача состоит в разбиении этой выборки на $K$ непересекающихся групп (кластеров) $C_1,\dots,C_k$ так, чтобы объекты одной группы были похожи друг на друга, а объекты разных групп — отличались друг от друга.

Введем критерий качества кластеризации следующим образом:

$J = \sum_{k=1}^K\sum_{n:\vec{x}_n\in C_k}{||}\vec{x}_n - \vec{m}_k||^2$ , где $m_k = \frac{1}{|C_k|}\sum_{n:\vec{x}_n\in C_k}\vec{x}_n$ .

Метод K средних представляет собой жадный алгоритм минимизации критерия $J$ . Пусть имеется некоторое текущее разбиение выборки на кластеры $C_1,\dots,C_K$ . Тогда одна итерация метода К средних выглядит следующим образом:

Найти центры текущих кластеров $\vec{m}_1,\dots,\vec{m}_K$ : $\vec{m}_k=\frac{1}{|C_k|}\sum_{n:\vec{x}_n\in C_k}\vec{x}_n$ ;
Перераспределить объекты по кластерам путем отнесения к ближайшему центру: $\vec{x}_n\in C_k$ , если $k = \arg\min_k ||\vec{x}_n-\vec{m}_k||^2$ .

Итерационный процесс продолжается до стабилизации значения $J$ . Заметим, что в ходе итераций возможна ситуация, когда объекты перераспределяются не по всем $K$ кластерам. В результате значение $K$ может сократиться.

Очевидно, что представленный алгоритм позволяет найти лишь локальный минимум критерия $J$ . Поэтому на практике алгоритм минимизации запускается из нескольких случайных начальных кластеризаций, а в качестве итоговой кластеризации признается та, для которой значение $J$ оказалось наименьшим.

Формулировка задания

Для выполнения задания на оценку «удовлетворительно» необходимо выполнить следующие пункты:

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

Для выполнения задания на оценку «хорошо» необходимо дополнительно к вышеуказанным пунктам выполнить:

Реализовать процедуру кластеризации по методу к-средних по описанному ниже прототипу;
Продемонстрировать на модельных данных для метода к-средних результаты адекватной и неадекватной кластеризации при условии, что истинное количество кластеров известно (под неадекватной кластеризацией понимается принципиальная негодность метода к-средних для данной выборки, а не локальный минимум функционала $J$ );
Применить метод кластеризации к-средних для задачи распознавания рукописных цифр; сравнить результаты с аналогичными для метода опорных векторов;
Результаты всех проведенных исследований добавить в отчет.

Для выполнения задания на оценку «отлично» необходимо дополнительно к вышеуказанным пунктам выполнить:

Предложить и реализовать процедуру обучения/тестирования/подбора структурных параметров метода опорных векторов для случая многих классов; некоторые идеи обобщения метода опорных векторов на многоклассовый случай изложены здесь и здесь;
Применить многоклассовый метод опорных векторов для практической задачи распознавания рукописных цифр;
Применить метод К средних для задачи распознавания рукописных цифр и сравнить его результаты с аналогичными для многоклассового метода опорных векторов;
Результаты всех проведенных исследований добавить в отчет.

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

Задание выполняется в среде MATLAB. Необходимые алгоритмы должны быть реализованы по прототипам, указанным ниже.

Обучение метода опорных векторов

a = svm_train(X, t, options)

ВХОД

X — обучающая выборка, матрица типа double размера N x D, где N — число объектов, D — число признаков.

t — метки классов для объектов обучения (+1 и -1), вектор типа double размера 1 x N;

options — (необязательный аргумент) набор дополнительных параметров, структура размера 1 x 1, возможны следующие названия полей и их значения:

'С' — значение коэффициента регуляризации (по умолчанию = 1);

'С_tuning' — флаг использования скользящего контроля для настройки коэффициента регуляризации, тип logical, если false, то используется значение для С (по умолчанию = false);

'kernel' — семейство используемых ядровых функций, тип char размера 1 x S, возможные значения 'linear', 'polynomial', 'rbf' (по умолчанию = 'linear');

'kernel_param' — значение параметра для ядровой функции, тип double размера 1 x 1, для семейства 'rbf' здесь задается значение параметра gamma, для семейства 'polynomial' — значение степени (по умолчанию = 1);

'kernel_tuning' — флаг использования скользящего контроля для подбора параметров ядровых функций, тип logical, если false, то используется значение из kernel_param (по умолчанию = false);

'display' — параметр отображения, тип logical, если false, то на экране ничего не отображается, если true, то отображается текущий статус вычислений в произвольной форме (какие значения параметров пробуются, какие ошибки на скользящем контроле получаются, какие итоговые значения параметров оказались наилучшими и т.д.);

ВЫХОД

a — обученный метод опорных векторов, структура размера 1 x 1, поля структуры имеют следующие имена и значения:

'lambdat' — вектор из произведений коэффициентов lambda на метки классов t, вектор типа double размер 1 x M, где M — количество опорных векторов;

'b' — коэффициент сдвига, число;

'support_objects' — опорных объекты, матрица типа double размера M x D;

'kernel' — семейство используемых ядровых функций, совпадает с входным значением 'kernel';

'kernel_param' — параметр ядровой функции, совпадает с входным значением 'kernel_param';

Обратите внимание: параметры N и D определяются неявно по размеру соответствующих элементов.

Тестирование метода опорных векторов

[ErrorRate, Answers, Outputs] = svm_test(a, X, t)

ВХОД

a — обученный метод опорных векторов, структура, которую возвращает функция svm_train;

X — тестовая выборка, матрица типа double размера N_test x D;

t — (необязательный аргумент), истинные значения меток класса для тестовой выборки, вектор типа double размера 1 x N_test.

ВЫХОД

ErrorRate — процент допущенных ошибок классификации, если вектор t задан, и -1 в обратном случае.

Answers — спрогнозированные метки класса для объектов тестовой выборки, вектор типа double размера 1 x N_test;

Outputs — значения линейной функции $f(\vec{x})$ для объектов тестовой выборки, вектор типа double размера 1 x N_test;

Кластеризация по методу К средних

[idx, C] = k_means(X, K, options)

ВХОД

X — входная выборка, матрица типа double размера N x D, где N — число объектов, D — число признаков.

K — количество кластеров, число;

'num_start' — количество случайных начальных кластеризаций, число (по умолчанию = 10);

'max_iter' — максимальное число итераций, число (по умолчанию = 100);

'display' — параметр отображения, тип logical, если false, то на экране ничего не отображается, если true, то отображается текущий статус вычислений в произвольной форме (значения J на каждой итерации, значение J для каждой случайной начальной кластеризации и т.д.);

ВЫХОД

idx — метки кластеров для каждого объекта входной выборки, вектор типа double размера 1 x N;

C — центры найденных кластеров, матрица типа double размера M x D, где M равно или меньше K.

Внимание! Запрещается пользоваться встроенной в MATLAB функцией kmeans.

Описание практической задачи

Примеры изображений рукописных цифр для задачи MNIST

Рассматривается задача распознавания рукописных цифр MNIST. Исходные данные можно скачать здесь. В этой задаче объектами являются черно-белые изображения размера $28{\times}28$ , на каждом из которых представлена одна рукописная цифра, а метками класса являются сами цифры. Таким образом, в данном случае рассматривается задача классификации на 10 классов. Признаковым описанием одного объекта (изображения) являются интенсивности пикселов, вытянутые в вектор. Для устойчивости всех вычислений рекомендуется разделить интенсивности пикселей на 255, чтобы получить значения в диапазоне [0,1].

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

При решении задачи с помощью метода К средних также следует выбрать несколько пар классов и приводить результаты с помощью матрицы точности. При этом необходимо привести примеры пар классов, для которых метод К средних дает хороший результат, и примеры пар классов, для которых кластеризация сильно отличается от истинной классификации.

Процедура сдачи задания

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

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

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

PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел);
Файлы svm_train.m, svm_test.m, k_means.m;
Файлы, с помощью которых осуществлялось построение всех графиков в отчете;
Набор дополнительных файлов при необходимости.

Защита задания

После сдачи выполненного задания и его проверки необходимо будет защитить свое задание. В том случае, если в какой-то части выполненного задания будет обнаружен плагиат с заданием другого студента, то задание не будет засчитано для обоих студентов! Защита задания будет осуществляться с помощью видео-чата для студентов СФ и во время осенних пересдач для московских студентов. Студенту будет предложен ряд вопросов по присланному коду и проведенным исследованиям. Кроме того, возможны задания по небольшой модификации кода в режиме онлайн.

Источник — «http://recognition.su/wiki/index.php?title=%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%BF%D1%80%D0%BE%D0%B3%D0%BD%D0%BE%D0%B7%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29/2012/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A1%D0%A4»

Категория: Учебные курсы

Математические основы теории прогнозирования (курс лекций)/2012/Задание СФ

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

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

Содержание

Необходимая теория

Метод опорных векторов

Использование ядровых функций

Скользящий контроль

Схема решения задач классификации

Метод K средних

Формулировка задания

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

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

Описание практической задачи

Процедура сдачи задания

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

Защита задания

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-{{stop|Внимание! Текст задания находится в стадии формирования. Убедительная просьба не приступать к выполнению данного задания до тех пор, пока это предупреждение не будет удалено.}}
 {{TOCright|300px}}
@@ Строка 7: / Строка 5: @@
 '''Срок сдачи задания''': {{ins|30 августа 2012, 23:59}}
-Данное практическое задание предназначено, в первую очередь, для студентов Севастопольского филиала, которые имеют задолженность по курсу [[МОТП]] и не имеют возможности присутствовать в Москве на пересдачах осенью. Тем не менее, это задание могут выполнять и московские студенты ВМиК, которые имеют задолженность по курсу МОТП. Оценка за это задание будет итоговой оценкой по курсу МОТП.
+Данное практическое задание предназначено, в первую очередь, для студентов Севастопольского филиала, которые имеют задолженность по курсу [[МОТП]] и не имеют возможности присутствовать в Москве на пересдачах осенью. Тем не менее, это задание могут выполнять и московские студенты ВМиК, которые имеют задолженность по курсу МОТП. Оценка за это задание будет итоговой оценкой по курсу.
+Цель данного задания состоит в том, чтобы студенты познакомились на практике с популярными методами решения задач классификации и кластеризации — [[Машина опорных векторов|методом опорных векторов]] и методом к-средних, а также с базовыми аспектами, с которыми приходится сталкиваться при решении задач машинного обучения — проблемой переобучения и проблемой подбора структурных параметров алгоритма (таких как коэффициент С и параметры ядровых функций).
+Задание выполняется в среде [[MATLAB]].
-Цель данного задания состоит в том, чтобы студенты познакомились на практике с простейшим методом решения задач классификации — методом опорных векторов, а также с базовыми аспектами, с которыми приходится сталкиваться при решении задач машинного обучения — проблемой переобучения, проблемой подбора структурных параметров алгоритма (в данном случае в качестве таковых выступают коэффициент С и параметры ядровых функций), проблемой выбора эффективного признакового пространства и др.
+Вопросы по заданию можно оставлять на вкладке «обсуждение» к этой странице, либо адресовать письмом на ''bayesml@gmail.com''. В название письма просьба добавлять [МОТП12].
 == Необходимая теория ==
-=== [[Машина опорных векторов|Метод опорных векторов]] ===
+=== Метод опорных векторов ===
 [[Изображение:MOTP12_svm_linear.jpg|300px|thumb|Иллюстрация линейного разделения выборки с помощью метода опорных векторов, зелеными кружками отмечены опорные объекты]]
 Рассматривается задача классификации на два класса. Имеется обучающая выборка <tex>\{\vec{x}_n,t_n\}_{n=1}^N</tex>, где <tex>\vec{x}_n\in\mathbb{R}^d</tex> — вектор признаков для объекта <tex>n</tex>, а <tex>t_n\in\{-1,+1\}</tex> — его метка класса. Задача заключается в предсказании метки класса <tex>t_{new}</tex> для объекта, представленного своим вектором признаков <tex>\vec{x}_{new}</tex>.
@@ Строка 29: / Строка 31: @@
 <tex>0\le\lambda_n\le C.</tex>
-Здесь <tex>C>0</tex> — параметр алгоритма, который задает компромисс между точностью распознавания обучающей выборки и величиной зазора между данными и гиперплоскостью.
+Здесь <tex>C>0</tex> — параметр алгоритма, который задает компромисс между точностью распознавания обучающей выборки и величиной зазора между данными и гиперплоскостью (надежностью классификации).
 После решения задачи квадратичного программирования оптимальный вектор весов вычисляется как
@@ Строка 35: / Строка 37: @@
 <tex>\vec{w} = \sum_{n=1}^N\lambda_nt_n\vec{x}_n</tex>.
-Очевидно, что только те объекты обучающей выборки, для которых <tex>\lambda_n\neq 0</tex>, влияют на оптимальный вектор весов. Такие объекты получили название ''опорных''. Пусть <tex>\exist n:\ 0<\lambda_n<C</tex>. Тогда оптимальная величина сдвига гиперплоскости <tex>b</tex> определяется как
+Очевидно, что только те объекты обучающей выборки, для которых <tex>\lambda_n\neq 0</tex>, влияют на оптимальный вектор весов. Такие объекты получили название ''опорных''. Пусть <tex>\exist n_*:\ 0<\lambda_{n_*}<C</tex>. Тогда оптимальная величина сдвига гиперплоскости <tex>b</tex> определяется как
-<tex>b = t_n - \vec{w}^T\vec{x}_n</tex>.
+<tex>b = t_{n_*} - \vec{w}^T\vec{x}_{n_*}</tex>.
 На практике здесь лучше проводить усреднение по всем <tex>n:\ 0<\lambda_n<C</tex>. Если в оптимальном <tex>\vec{\lambda}</tex> все коэффициенты равны только нулю и <tex>C</tex>, то тогда коэффициент <tex>b</tex> может быть найден перебором путем минимизации ошибки распознавания обучающей выборки.
 === Использование ядровых функций ===
-[[Изображение:MOTP12_svm_rbf.jpg|300px|thumb|Иллюстрация нелинейного разделения выборки с помощью метода опорных векторов с радиальными ядровыми функциями, зелеными кружками отмечены опорные объекты]]
+[[Изображение:MOTP12_svm_rbf.jpg|300px|thumb|Иллюстрация нелинейного разделения выборки с помощью метода опорных векторов с радиальной ядровой функцией, зелеными кружками отмечены опорные объекты]]
-Рассматривается задача классификации на два класса. Имеется обучающая выборка <tex>\{\vec{x}_n,t_n\}_{n=1}^N</tex>, где <tex>\vec{x}_n\in\mathbb{R}^d</tex> — вектор признаков для объекта <tex>n</tex>, а <tex>t_n\in\{-1,+1\}</tex> — его метка класса. Задача заключается в предсказании метки класса <tex>t_{new}</tex> для объекта, представленного своим вектором признаков <tex>\vec{x}_{new}</tex>.
+Для построения нелинейных решающих правил с помощью метода опорных векторов вводится понятие ядровой функции. Пусть имеется преобразование из исходного признакового пространства <tex>\mathbb{R}^d</tex> в новое пространство <tex>H</tex>, задаваемое функцией <tex>\phi:\mathbb{R}^d\rightarrow H</tex>. Пусть также имеется ядровая функция <tex>K</tex>, которая задает скалярное произведение в новом пространстве <tex>H</tex>:
-В логистической регрессии предсказание метки класса осуществляется по знаку линейной функции:
+<tex>K(\vec{x},\vec{y}) = \phi(\vec{x})^T\phi(\vec{y}),\ \forall\vec{x},\vec{y}.</tex>
-<tex>t(\vec{x}_{new}) = \begin{cases}+1,\ f(\vec{x}_{new})=\sum_{j=1}^Mw_j\phi_j(\vec{x}_{new})\ge 0,\\-1,\ f(\vec{x}_{new})<0.\end{cases}</tex>
+Тогда для построения линейной разделяющей гиперплоскости в новом пространстве <tex>H</tex> достаточно знать лишь ядровую функцию <tex>K</tex> и не требуется знать само преобразование <tex>\phi</tex>. В этом случае на этапе обучения метода решается следующая задача квадратичного программирования:
-Здесь веса <tex>\vec{w}</tex> и базисные функции <tex>\phi</tex> вводятся аналогично случаю линейной регрессии. Веса <tex>\vec{w}</tex> решающего правила настраиваются с помощью минимизации следующего регуляризованного критерия:
+<tex>\sum_{n=1}^N\lambda_n - \frac{1}{2}\sum_{n,m=1}^N\lambda_n\lambda_mt_nt_mK(\vec{x}_n,\vec{x}_m)\rightarrow\max_{\vec{\lambda}},</tex>
-<tex>J = \frac{1}{N}\sum_{n=1}^N\log(1+\exp(-t_nf(\vec{x}_n))) + \lambda||\vec{w}||^2\rightarrow\min_{\vec{w}}</tex>.
+<tex>\sum_n\lambda_nt_n = 0,</tex>
-Здесь <tex>\lambda\ge 0</tex> — задаваемый пользователем параметр регуляризации. Функционал <tex>J</tex> является выпуклой функцией относительно своих параметров <tex>\vec{w}</tex> и поэтому может быть эффективно минимизирован с помощью любого итерационного метода безусловной оптимизации, учитывающего значения градиента и гессиана функции <tex>J</tex>, например, метода Ньютона.
+<tex>0\le \lambda_n\le C.</tex>
+При этом скалярное произведение оптимального вектора весов <tex>\vec{w}</tex> и произвольного объекта <tex>\vec{x}</tex> определяется как
+<tex>\vec{w}^T\vec{x} = \sum_{n=1}^N\lambda_nt_nK(\vec{x}_n,\vec{x}).</tex>
+По-прежнему, только опорные объекты (для которых <tex>\lambda_n\neq 0</tex>) вносят вклад в значение данного скалярного произведения. Величина сдвига гиперплоскости, как и раньше, определяется как
+<tex>b = \frac{\sum_{n:0<\lambda_n<C}(t_n - \vec{w}^T\vec{x}_n)}{\sum_{n:0<\lambda_n<C}1}.</tex>
+Если все коэффициенты <tex>\lambda_n</tex> принимают только крайние значения, то оптимальный сдвиг <tex>b</tex> находится путем минимизации числа ошибок на обучающей выборке.
+Ядровая функция, как правило, выбирается в одном из следующих параметрических семейств:
+# ''Линейная'': <tex>K(\vec{x},\vec{y}) = \vec{x}^T\vec{y}</tex>,
+# ''Степенная'': <tex>K(\vec{x},\vec{y}) = (\vec{x}^T\vec{y}+1)^r,\ r\in\mathbb{N}</tex>.
+# ''Радиальная'': <tex>K(\vec{x},\vec{y}) = \exp\left(-\frac{||\vec{x}-\vec{y}||^2}{2\gamma^2}\right),\ \gamma>0</tex>.
+В случае степенной ядровой функции делается неявное предположение о том, что данные отнормированы на нулевой центр и единичную дисперсию. В этом случае, по неравенству Коши-Буняковского, величина <tex>\vec{x}^T\vec{y}+1</tex> всегда будет неотрицательной.
 === Скользящий контроль ===
-В алгоритмах линейной/логистической регрессии параметр регуляризации <tex>\lambda</tex>, а также параметры базисных функций (например, степень полинома или параметр <tex>\gamma</tex> в радиальных базисных функциях) являются структурными параметрами, которые
+В методе опорных векторов параметр регуляризации <tex>C</tex>, а также параметры ядровых функций (например, параметр <tex>\gamma</tex> в радиальной ядровой функции) являются структурными параметрами, которые
-не могут быть настроены путем минимизации критерия <tex>J</tex> на обучающей выборке. Для их настройки используются ''критерии выбора модели'', например, скользящий контроль.
+не могут быть настроены путем минимизации числа ошибок на обучающей выборке. Для их настройки используются ''критерии выбора модели'', например, [[Скользящий контроль|скользящий контроль]].
-Обозначим обучающую выборку через <tex>Y=(X,\vec{t})</tex>, а через <tex>a(\vec{x},Y)</tex> результат прогноза (значение регрессионной переменной или метки класса) для объекта <tex>\vec{x}</tex>, полученный с помощью алгоритма <tex>a</tex>, обученного по выборке <tex>Y</tex>.
+Обозначим обучающую выборку через <tex>Y=(X,\vec{t})</tex>, а через <tex>a(\vec{x},Y)</tex> — результат прогноза метки класса для объекта <tex>\vec{x}</tex>, полученный с помощью алгоритма <tex>a</tex>, обученного по выборке <tex>Y</tex>.
 При <tex>K</tex>-кратном скользящем контроле обучающая выборка <tex>Y</tex> разбивается на <tex>K</tex> равных частей <tex>Y=Y_1\sqcup Y_2\sqcup\dots\sqcup Y_K</tex>. Общая величина ошибки на <tex>K</tex>-кратном скользящем контроле вычисляется как
-<tex>Error_{cv} = \frac{1}{N}\sum_{k=1}^K\ \sum_{n:\vec{x}_n\in Y_k}error(t_n, a(\vec{x}_n, Y_{\backslash k}))</tex>.
+<tex>Error_{cv} = \frac{1}{N}\sum_{k=1}^K\ \sum_{n:\vec{x}_n\in Y_k}I[t_n \neq a(\vec{x}_n, Y_{\backslash k})]</tex>.
-Здесь через <tex>Y_{\backslash k}</tex> обозначена обучающая выборка без части <tex>Y_k</tex>, а через <tex>error(t, y)</tex> — величина ошибки между предсказанием <tex>y</tex> и истинным значением <tex>t</tex>. Эта ошибка вычисляется как
+Здесь через <tex>Y_{\backslash k}</tex> обозначена обучающая выборка без части <tex>Y_k</tex>, а через <tex>I[t \neq y]</tex> — индикаторная функция, равная единице при выполнении условия <tex>t \neq y</tex>.
-<tex>error(t,y)=(t-y)^2</tex> — для задачи регрессии и <tex>error(t,y)=\begin{cases}0,\ t=y,\\1,\ t\neq y,\end{cases}</tex> — для задачи классификации.
 Наиболее популярная версия скользящего контроля — усреднение <tex>Error_{cv}</tex> по пяти независимым запускам 2-кратного скользящего контроля. При таком подходе необходимо обучать алгоритм только по половине обучающей выборки (что происходит быстрее, чем обучение, например, по 9/10 от объема обучающей выборки). Во-вторых, здесь требуется всего 10 различных обучений (что гораздо меньше, чем, например, объем обучающей выборки <tex>N</tex> при разбиении выборки на <tex>K=N</tex> частей).
-Настройка параметра регуляризации <tex>\lambda</tex> с помощью скользящего контроля производится следующим образом. Выбирается набор возможных значений <tex>\lambda</tex>, например, <tex>2^{-5},2^{-4.9},\dots,2^{4.9},2^{5}</tex>. Для каждого из этих значений вычисляется величина ошибки скользящего контроля (например, с помощью усреднения по пяти запускам 2-кратного скользящего контроля). В результате выбирается такое значение <tex>\lambda</tex>, для которого величина ошибки является наименьшей. В том случае, если требуется настроить два параметра, например <tex>\lambda</tex> и <tex>\gamma</tex> в радиальных базисных функциях, то выбирается двухмерная сетка значений параметров и находится та пара, для которой ошибка на скользящем контроле является наименьшей.
+Настройка параметра регуляризации <tex>C</tex> с помощью скользящего контроля производится следующим образом. Выбирается набор возможных значений <tex>C</tex>, например, <tex>2^{-5},2^{-4},\dots,2^{4},2^{5}</tex>. Для каждого из этих значений вычисляется величина ошибки скользящего контроля (например, с помощью усреднения по пяти запускам 2-кратного скользящего контроля). В результате выбирается такое значение <tex>C</tex>, для которого величина ошибки скользящего контроля является наименьшей. В том случае, если требуется настроить два параметра, например <tex>C</tex> и <tex>\gamma</tex> в радиальных базисных функциях, то выбирается двухмерная сетка значений параметров и находится та пара, для которой ошибка на скользящем контроле является наименьшей.
-=== Схема решения задач классификации/регрессии ===
+=== Схема решения задач классификации ===
-В простейшем случае для решения задачи классификации/регрессии имеющаяся в распоряжении выборка разбивается на три подвыборки: обучающую, валидационную и тестовую. Сначала выбирается некоторая модель алгоритмов, например, линейная регрессия с полиномиальными базисными функциями. По обучающей выборке в скользящем контроле настраиваются все структурные параметры выбранной модели (для линейной регрессии с полиномиальными базисными функциями в качестве таковых выступают коэффициент регуляризации и степень полинома). Затем с выбранными значениями структурных параметров производится обучение модели алгоритмов по обучающей выборке. Полученный алгоритм тестируется на обучающей и валидационной выборке. В том случае, если значения обеих ошибок значимо отличаются друг от друга (следовательно, есть переобучение) или их значения близки между собой и достаточно большие (значит, есть недообучение), то выбранная модель алгоритмов признается неудачной и выбирается другая модель алгоритмов (более простая, если ранее было обнаружено переобучение, или более сложная, если ранее было обнаружено недообучение). После того, как удается найти хорошую модель алгоритмов (у которой нет переобучения и недообучения), обучающая и валидационная выборка объединяются между собой и используются в качестве обучающей для настройки структурных параметров по скользящему контролю и последующего обучения в найденной хорошей модели алгоритмов. Затем полученный алгоритм тестируется на объединенной обучающей и тестовой выборке. Если обе ошибки близки между собой и достаточно маленькие по значению, то такой алгоритм признается оптимальным для решения задачи классификации/регрессии.
+В простейшем случае для решения задачи классификации имеющаяся в распоряжении выборка разбивается на три подвыборки: обучающую, валидационную и тестовую. Сначала выбирается некоторая модель алгоритмов, например, метод опорных векторов с радиальной ядровой функцией. По обучающей выборке в скользящем контроле настраиваются все структурные параметры выбранной модели (для метода опорных векторов с радиальной ядровой функцией в качестве таковых выступают коэффициент регуляризации <tex>C</tex> и параметр <tex>\gamma</tex>). Затем с выбранными значениями структурных параметров производится обучение модели алгоритмов по обучающей выборке. Полученный алгоритм тестируется на обучающей и валидационной выборке. В том случае, если значения обеих ошибок значимо отличаются друг от друга (следовательно, есть переобучение) или их значения близки между собой и достаточно большие (значит, есть недообучение), то выбранная модель алгоритмов признается неудачной и выбирается другая модель алгоритмов (более простая, если ранее было обнаружено переобучение, или более сложная, если ранее было обнаружено недообучение). После того, как удается найти хорошую модель алгоритмов (у которой нет переобучения и недообучения), обучающая и валидационная выборка объединяются между собой и используются в качестве обучающей для настройки структурных параметров по скользящему контролю и последующего обучения в найденной хорошей модели алгоритмов. Затем полученный алгоритм тестируется на обучающей и тестовой выборке. Если обе ошибки близки между собой и достаточно маленькие по значению, то такой алгоритм признается оптимальным для решения задачи классификации.
-Зачастую имеющаяся в распоряжении выборка прецедентов является небольшой по объему и поэтому не может быть разбита на три достаточно репрезентативные подвыборки. В этом случае выборка разбивается только на обучающую и валидационную, и найденная по описанной выше схеме наилучшая модель алгоритмов не тестируется на отдельной тестовой выборке. Такой подход является менее корректным по сравнению с предыдущим, т.к. мерой качества алгоритма здесь выступает величина, которая подвергалась оптимизации на имеющихся данных. Поэтому здесь возможен эффект переобучения на уровне моделей алгоритмов. Тем не менее, во многих практических ситуациях данная схема дает вполне приемлемый результат.
+=== Метод K средних ===
+[[Изображение:MOTP12_kmeans.jpg|300px|thumb|Кластеризация выборки на 5 кластеров с помощью метода К средних]]
+Рассматривается задача кластеризации. Имеется выборка <tex>\{\vec{x}_n\}_{n=1}^N</tex>, где <tex>\vec{x}_n\in\mathbb{R}^d</tex> — вектор признаков для объекта <tex>n</tex>. Задача состоит в разбиении этой выборки на <tex>K</tex> непересекающихся групп (кластеров) <tex>C_1,\dots,C_k</tex> так, чтобы объекты одной группы были похожи друг на друга, а объекты разных групп — отличались друг от друга.
+Введем критерий качества кластеризации следующим образом:
+<tex>J = \sum_{k=1}^K\sum_{n:\vec{x}_n\in C_k}{||}\vec{x}_n - \vec{m}_k||^2</tex>, где <tex>m_k = \frac{1}{|C_k|}\sum_{n:\vec{x}_n\in C_k}\vec{x}_n</tex>.
+Метод K средних представляет собой жадный алгоритм минимизации критерия <tex>J</tex>. Пусть имеется некоторое текущее разбиение выборки на кластеры <tex>C_1,\dots,C_K</tex>. Тогда одна итерация метода К средних выглядит следующим образом:
+# Найти центры текущих кластеров <tex>\vec{m}_1,\dots,\vec{m}_K</tex>: <tex>\vec{m}_k=\frac{1}{|C_k|}\sum_{n:\vec{x}_n\in C_k}\vec{x}_n</tex>;
+# Перераспределить объекты по кластерам путем отнесения к ближайшему центру: <tex>\vec{x}_n\in C_k</tex>, если <tex>k = \arg\min_k ||\vec{x}_n-\vec{m}_k||^2</tex>.
+Итерационный процесс продолжается до стабилизации значения <tex>J</tex>. Заметим, что в ходе итераций возможна ситуация, когда объекты перераспределяются не по всем <tex>K</tex> кластерам. В результате значение <tex>K</tex> может сократиться.
+Очевидно, что представленный алгоритм позволяет найти лишь локальный минимум критерия <tex>J</tex>. Поэтому на практике алгоритм минимизации запускается из нескольких случайных начальных кластеризаций, а в качестве итоговой кластеризации признается та, для которой значение <tex>J</tex> оказалось наименьшим.
 == Формулировка задания ==
-Для выполнения задания необходимо выполнить следующие пункты:
+Для выполнения задания на оценку «удовлетворительно» необходимо выполнить следующие пункты:
-{|style="background:#E0FFE0"
+# Реализовать процедуру обучения/тестирования/подбора структурных параметров метода опорных векторов по описанному ниже прототипу;
- |1. Реализовать процедуру обучения/тестирования/подбора структурных параметров линейной регрессии по описанному ниже прототипу;
+# Продемонстрировать на модельных данных для метода опорных векторов эффект переобучения (маленькая ошибка на обучении, большая ошибка на тесте), эффект недообучения (ошибки на обучении и тесте близки между собой и большие по величине) и ситуацию нормальной работы (ошибки на обучении и тесте близки между собой и маленькие по величине);
- |-
+# Решить с помощью метода опорных векторов практическую задачу распознавания рукописных цифр (описание задачи см. ниже) для нескольких пар цифр; желательно рассмотреть как похожие по начертанию цифры, например, 5 и 6, так и сильно непохожие, например, 2 и 4;
- |2. Продемонстрировать на модельных данных для линейной регрессии эффект переобучения (маленькая ошибка на обучении, большая ошибка на тесте), эффект недообучения (ошибки на обучении и тесте близки между собой и большие по величине) и ситуацию нормальной работы (ошибки на обучении и тесте близки между собой и маленькие по величине);
+# Составить отчет в формате PDF обо всех проведенных исследованиях; данный отчет должен содержать необходимые графики и описание экспериментов, выводы необходимых формул, описание полученных результатов решения практических задач, общие выводы по исследованию.
- |-
- |3. Решить с помощью линейной регрессии практическую задачу прогноза предела прочности бетона (описание задачи см. ниже);
+Для выполнения задания на оценку «хорошо» необходимо дополнительно к вышеуказанным пунктам выполнить:
- |-
+# Реализовать процедуру кластеризации по методу к-средних по описанному ниже прототипу;
- |4. Вывести и вставить в отчет формулы для градиента и гессиана функционала <tex>J</tex> в логистической регрессии по параметрам <tex>\vec{w}</tex>;
+# Продемонстрировать на модельных данных для метода к-средних результаты адекватной и неадекватной кластеризации при условии, что истинное количество кластеров известно (под неадекватной кластеризацией понимается принципиальная негодность метода к-средних для данной выборки, а не локальный минимум функционала <tex>J</tex>);
- |-
+# Применить метод кластеризации к-средних для задачи распознавания рукописных цифр; сравнить результаты с аналогичными для метода опорных векторов;
- |5. Реализовать процедуру обучения/тестирования/подбора структурных параметров логистической регрессии по описанному ниже прототипу;
+# Результаты всех проведенных исследований добавить в отчет.
- |-
- |6. Продемонстрировать на модельных данных для логистической регрессии эффект переобучения (маленькая ошибка на обучении, большая ошибка на тесте), эффект недообучения (ошибки на обучении и тесте близки между собой и большие по величине) и ситуацию нормальной работы (ошибки на обучении и тесте близки между собой и маленькие по величине);
- |-
- |7. Решить с помощью логистической регрессии практическую задачу определения района происхождения вина по данным его химического анализа (описание задачи см. ниже);
- |-
- |8. Составить отчет в формате PDF обо всех проведенных исследованиях; данный отчет должен содержать необходимые графики и описание экспериментов, выводы необходимых формул, описание полученных результатов решения практических задач, общие выводы по исследованию.
- |}
-Для выполнения задания на оценку «удовлетворительно» достаточно реализовать только пункты 4–8 без семейства полиномиальных базисных функций. Для выполнения задания на оценку «хорошо» и «отлично» необходимо выполнить все пункты задания.
+Для выполнения задания на оценку «отлично» необходимо дополнительно к вышеуказанным пунктам выполнить:
+# Предложить и реализовать процедуру обучения/тестирования/подбора структурных параметров метода опорных векторов для случая многих классов; некоторые идеи обобщения метода опорных векторов на многоклассовый случай изложены [[Media:SMAIS11_SSVM.pdf|здесь]] и [http://users.stat.umn.edu/~xshen/paper/One-Against-All-Zheng.pdf здесь];
+# Применить многоклассовый метод опорных векторов для практической задачи распознавания рукописных цифр;
+# Применить метод К средних для задачи распознавания рукописных цифр и сравнить его результаты с аналогичными для многоклассового метода опорных векторов;
+# Результаты всех проведенных исследований добавить в отчет.
 === Спецификация реализуемых функций ===
-Рекомендуемая среда для выполнения задания — MATLAB. При выполнении задания в среде MATLAB необходимые алгоритмы должны быть реализованы по прототипам, указанным ниже. В случае использования других сред для выполнения задания, реализуемые функции должны соответствовать прототипам, описанным ниже. Например, при программировании на языке C набор параметров для обучения должен задаваться в текстовом файле, при этом список параметров и их возможные значения следует брать из прототипов ниже.
+Задание выполняется в среде [[MATLAB]]. Необходимые алгоритмы должны быть реализованы по прототипам, указанным ниже.
 {|class="standard"
- !''Обучение линейной регрессии''
+ !''Обучение метода опорных векторов''
  |-
- |a = linreg_train(X, t, options)
+ |a = '''svm_train'''(X, t, options)
  |-
  |ВХОД
@@ Строка 115: / Строка 143: @@
  |
  {|border="0"
-  |X — обучающая выборка, матрица типа double размера N x M, где N — число объектов, M — число признаков.
+  |X — обучающая выборка, матрица типа double размера N x D, где N — число объектов, D — число признаков.
   |-
-  |t — значение регрессионной переменной, вектор типа double размера 1 x N;
+  |t — метки классов для объектов обучения (+1 и -1), вектор типа double размера 1 x N;
   |-
-  |options — (необязательный аргумент) набор дополнительных параметров, структура размера 1 x 1, названия полей структуры совпадают с названиями параметров. Возможны следующие имена параметров и их значения:
+  |options — (необязательный аргумент) набор дополнительных параметров, структура размера 1 x 1, возможны следующие названия полей и их значения:
   |-
-  |&nbsp;&nbsp;'reg_coef' — значение коэффициента регуляризации (по умолчанию = 1e-6);
+  |&nbsp;&nbsp;'С' — значение коэффициента регуляризации (по умолчанию = 1);
   |-
-  |&nbsp;&nbsp;'reg_coef_tuning' — флаг использования скользящего контроля для настройки коэффициента регуляризации, тип logical, если false, то используется значение из reg_coef (по умолчанию = false);
+  |&nbsp;&nbsp;'С_tuning' — флаг использования скользящего контроля для настройки коэффициента регуляризации, тип logical, если false, то используется значение для С (по умолчанию = false);
   |-
-  |&nbsp;&nbsp;'basis_functions' — семейство используемых базисных функций, тип char размера 1 x S, возможные значения 'initial', 'polynomial', 'rbf' (по умолчанию = 'initial');
+  |&nbsp;&nbsp;'kernel' — семейство используемых ядровых функций, тип char размера 1 x S, возможные значения 'linear', 'polynomial', 'rbf' (по умолчанию = 'linear');
   |-
-  |&nbsp;&nbsp;'basis_functions_param' — значение параметра для базисных функций, тип double размера 1 x 1, для семейства 'rbf' здесь задается значение параметра gamma, для семейства 'polynomial' — степень полинома (по умолчанию = 1);
+  |&nbsp;&nbsp;'kernel_param' — значение параметра для ядровой функции, тип double размера 1 x 1, для семейства 'rbf' здесь задается значение параметра gamma, для семейства 'polynomial' — значение степени (по умолчанию = 1);
   |-
-  |&nbsp;&nbsp;'basis_functions_tuning' — флаг использования скользящего контроля для подбора параметров базисных функций, тип logical, если false, то используется значение из basis_functions_param (по умолчанию = false);
+  |&nbsp;&nbsp;'kernel_tuning' — флаг использования скользящего контроля для подбора параметров ядровых функций, тип logical, если false, то используется значение из kernel_param (по умолчанию = false);
   |-
   |&nbsp;&nbsp;'display' — параметр отображения, тип logical, если false, то на экране ничего не отображается, если true, то отображается текущий статус вычислений в произвольной форме (какие значения параметров пробуются, какие ошибки на скользящем контроле получаются, какие итоговые значения параметров оказались наилучшими и т.д.);
@@ Строка 138: / Строка 166: @@
  |
  {|
-  |a — обученная модель линейной регрессии, структура размера 1 x 1, поля структуры имеют следующие имена и значения:
+  |a — обученный метод опорных векторов, структура размера 1 x 1, поля структуры имеют следующие имена и значения:
   {|border="0"
-   |'w' — веса линейного решающего правила, вектор типа double размера 1 x M1, где M1 — число базисных функций (для базисных функций initial M1=M+1, для базисных функций polynomial <tex>M1 = \sum_{k=1}^KC_M^k+1</tex>, K=basis_functions_param, для базисных функций rbf M1=N+1, единица добавляется в M1 за счет свободного члена, т.е. базисной функции <tex>\phi(\vec{x})\equiv 1</tex>);
+   |'lambdat' — вектор из произведений коэффициентов lambda на метки классов t, вектор типа double размер 1 x M, где M — количество опорных векторов;
    |-
-   |'basis_functions' — семейство используемых базисных функций, совпадает с входным значением 'basis_functions';
+   |'b' — коэффициент сдвига, число;
    |-
-   |'basis_functions_param' — параметр базисных функций, совпадает с входным значением 'basis_functions_param';
+   |'support_objects' — опорных объекты, матрица типа double размера M x D;
    |-
-   |'support_objects' — набор опорных объектов для базисных функций rbf, совпадает с обучающей выборкой, если 'basis_functions' == 'rbf', иначе пусто;
+   |'kernel' — семейство используемых ядровых функций, совпадает с входным значением 'kernel';
    |-
-   |'m' — нормировочные средние значения для каждого признака, вектор типа double размера 1 x M1;
+   |'kernel_param' — параметр ядровой функции, совпадает с входным значением 'kernel_param';
    |-
-   |'s' — нормировочные дисперсии для каждого признака, вектор типа double размера 1 x M1.
    |}
   |}
 |}
-Обратите внимание: параметры N и M определяются неявно по размеру соответствующих элементов.
+Обратите внимание: параметры N и D определяются неявно по размеру соответствующих элементов.
 {|class="standard"
- !''Тестирование линейной регрессии''
+ !''Тестирование метода опорных векторов''
  |-
- |[Outputs, ErrorRate] = linreg_test(a, X, t)
+ |[ErrorRate, Answers, Outputs] = '''svm_test'''(a, X, t)
  |-
  |ВХОД
@@ Строка 165: / Строка 192: @@
  |
  {|border="0"
-  |a — обученная модель линейной регрессии, структура, которую возвращает функция linreg_train;
+  |a — обученный метод опорных векторов, структура, которую возвращает функция svm_train;
   |-
-  |X — тестовая выборка, матрица типа double размера N_test x M;
+  |X — тестовая выборка, матрица типа double размера N_test x D;
   |-
-  |t — (необязательный аргумент), истинные значения целевой переменной для тестовой выборки, вектор типа double размера 1 x N_test.
+  |t — (необязательный аргумент), истинные значения меток класса для тестовой выборки, вектор типа double размера 1 x N_test.
   |}
  |-
@@ Строка 176: / Строка 203: @@
  |
  {|border="0"
-  |Outputs — прогноз значений регрессионной переменной, вектор типа double размера 1 x N_test;
+  |ErrorRate — процент допущенных ошибок классификации, если вектор t задан, и -1 в обратном случае.
+  |-
+  |Answers — спрогнозированные метки класса для объектов тестовой выборки, вектор типа double размера 1 x N_test;
+  |-
+  |Outputs — значения линейной функции <tex>f(\vec{x})</tex> для объектов тестовой выборки, вектор типа double размера 1 x N_test;
   |-
-  |ErrorRate — (если вектор t задан) <tex>\sqrt{\frac{1}{N_{test}}\sum_{n=1}^{N_{test}}(t_n-Outputs_n)^2}</tex>;
   |}
  |}
-Прототип функции обучения логистической регрессии logreg_train целиком повторяет прототип linreg_train. При этом вектор меток класса <tex>\vec{t}</tex> должен содержать значения только 1 и 2.
+&nbsp;
 {|class="standard"
- !''Тестирование логистической регрессии''
+ !''Кластеризация по методу К средних''
  |-
- |[Outputs, Answers, ErrorRate] = logreg_test(a, X, t)
+ |[idx, C] = '''k_means'''(X, K, options)
  |-
  |ВХОД
@@ Строка 193: / Строка 223: @@
  |
  {|border="0"
-  |a — обученная модель логистической регрессии, структура, которую возвращает функция logreg_train;
+  |X — входная выборка, матрица типа double размера N x D, где N — число объектов, D — число признаков.
   |-
-  |X — тестовая выборка, матрица типа double размера N_test x M;
+  |K — количество кластеров, число;
   |-
-  |t — (необязательный аргумент), истинные значения меток класса для тестовой выборки, вектор типа double размера 1 x N_test.
+  |options — (необязательный аргумент) набор дополнительных параметров, структура размера 1 x 1, возможны следующие названия полей и их значения:
+  |-
+  |&nbsp;&nbsp;'num_start' — количество случайных начальных кластеризаций, число (по умолчанию = 10);
+  |-
+  |&nbsp;&nbsp;'max_iter' — максимальное число итераций, число (по умолчанию = 100);
+  |-
+  |&nbsp;&nbsp;'display' — параметр отображения, тип logical, если false, то на экране ничего не отображается, если true, то отображается текущий статус вычислений в произвольной форме (значения J на каждой итерации, значение J для каждой случайной начальной кластеризации и т.д.);
   |}
  |-
@@ Строка 203: / Строка 239: @@
  |-
  |
- {|border="0"
+ {|
-  |Outputs — значения линейной функции <tex>f(\vec{x})</tex> для объектов тестовой выборки, вектор типа double размера 1 x N_test;
+  |idx — метки кластеров для каждого объекта входной выборки, вектор типа double размера 1 x N;
-  |-
-  |Answers — спрогнозированные метки класса для объектов тестовой выборки, вектор типа double размера 1 x N_test;
   |-
-  |ErrorRate — (если вектор t задан) процент допущенных ошибок классификации.
+  |C — центры найденных кластеров, матрица типа double размера M x D, где M равно или меньше K.
   |}
- |}
+|}
+Внимание! Запрещается пользоваться встроенной в MATLAB функцией kmeans.
 === Рекомендации по выполнению задания ===
@@ Строка 218: / Строка 253: @@
     normX = sum(X.^2,2);
     normY = sum(Y.^2,2);
-    diffXY = bsxfun(@plus, bsxfun(@plus, -2*X*Y', normX), normY');
+    diffXY = bsxfun(@plus, bsxfun(@plus, -2*(X*Y'), normX), normY');
 </pre>
+Для быстрого ознакомления со средой MATLAB и особенностью программирования в ней рекомендуется глава 15 [http://www.machinelearning.ru/wiki/images/7/7e/Dj2010up.pdf учебного пособия].
 . При работе с выборками для устойчивости всех производимых вычислений рекомендуется осуществлять нормировку выборки независимо для каждого признака таким образом, чтобы среднее значение по выборке равнялось нулю, а выборочная дисперсия — единице. При этом следует иметь в виду, что для тестовых выборок нужно использовать нормировочные коэффициенты, полученные для обучающих выборок.
-. Проверять корректность реализации обучения и тестирования линейной/логистической регрессии следует, в первую очередь, на модельных данных. Например, для проверки линейной регрессии можно сгенерировать данные с одним признаком, в которых регрессионная переменная вычисляется как значение полинома некоторой степени от значения признака со сгенерированными коэффициентами плюс небольшой нормальный шум. Тогда при обучении линейной регрессии с полиномиальными базисными функциями и правильной степенью полинома результат предсказания должен быть очень хорошим. Эту ситуацию можно отобразить и визуально. Например, для случая полинома первой степени картинка может выглядеть так:
+. Задача квадратичного программирования в среде MATLAB решается с помощью функции ''quadprog'' (рекомендуется пользоваться последней версией MATLAB R2012a). При этом в качестве алгоритма решения задачи квадратичного программирования рекомендуется выбирать ''interior-point-convex'' (метод внутренней точки), а также уменьшать значение параметра точности по удовлетворению ограничениям 'TolCon' до 1e-15, чтобы точнее находить множество опорных объектов.
-[[Изображение:MOTP11_linreg.jpg|200px]]
+. Проверять корректность реализации обучения и тестирования метода опорных векторов следует, в первую очередь, на модельных данных. Например, можно сгенерировать линейно разделимые данные в двухмерном пространстве и визуально отобразить разделяющую поверхность и опорные объекты. Результат должен выглядеть как на картинке внизу, слева. Обучение метода опорных векторов с радиальной ядровой функцией и параметрами <tex>C=4,\ \gamma=0.6</tex> для [[Media:MOTP12_svm_example.rar|этих данных]] должно приводить к результату, показанному на картинке внизу, справа.
-Кроме того, при автоматическом определении степени полинома по скользящему контролю выбираемое значение степени должно совпадать или быть близким к истинному.
-. Эффекты переобучения/недообучения для линейной/логистической регрессии можно продемонстрировать следующим образом. Для линейной регрессии достаточно сгенерировать одномерные данные с полиномом 3-ей степени. Тогда обучение линейной регрессии с полиномиальными базисными функциями первой степени должно приводить к недообучению, >6-ой степени — к переобучению, а 3-ей степени — к адекватному восстановлению зависимости. Для логистической регрессии можно сгенерировать двухмерные данные с существенно нелинейной разделяющей поверхностью. Тогда обучение логистической регрессии с радиальными базисными функциями и маленьким значением <tex>\gamma</tex> должно приводить к недообучению, с большим значением <tex>\gamma</tex> — к переобучению, а некоторое среднее значение <tex>\gamma</tex> будет соответствовать адекватной разделяющей поверхности.
 {|align="left"
- |-valign="top"
+ |[[Изображение:MOTP12_svm_linear.jpg|350px]]
- |[[Изображение:MOTP11_linreg_underoverfitting.jpg|мини|300px|Различные модели линейной регрессии. Зеленая кривая — недообучение, черная кривая — переобучение, голубая кривая — адекватная зависимость]]
+ |[[Изображение:MOTP12_svm_example.jpg|350px]]
- |[[Изображение:MOTP11_logreg_underoverfitting.jpg|мини|300px|Различные модели логистической регрессии. Зеленое решающее правило — недообучение, черное решающее правило — переобучение, голубое решающее правило — адекватное разделение данных]]
  |}<br clear="all" />
-=== Описание практических задач ===
+. Эффекты переобучения/недообучения для метода опорных векторов можно продемонстрировать следующим образом: сгенерировать двухмерные данные с существенно нелинейной разделяющей поверхностью и обучить метод опорных векторов с радиальной ядровой функцией с различными значениями параметра <tex>\gamma</tex>. Тогда большие значения <tex>\gamma</tex> должны приводить к недообучению, маленькие значения <tex>\gamma</tex> — к переобучению, а некоторое среднее значение <tex>\gamma</tex> будет соответствовать адекватной разделяющей поверхности.
-{|class="standard"
+[[Изображение:MOTP12_svm_underoverfit.jpg|мини|left|350px|Различные решающие правила, полученные с помощью метода опорных векторов. Зеленое решающее правило — недообучение, черное решающее правило — переобучение, оранжевое решающее правило — адекватное разделение данных.]]
- ! colspan="2"|Определение предела прочности бетона || colspan="2"|Классификация вин по месту происхождения
+<br clear="all" />
- |-valign="top"
- |[[Изображение:MOTP11_concrete.jpg|thumb|100px]] || width="40%"|Задача состоит в том, чтобы спрогнозировать уровень давления, при котором конкретная бетонная смесь разрушается, в зависимости от процента содержания в ней цемента, воды, возраста смеси и др. показателей. Исходные данные и подробное описание задачи можно скачать [http://archive.ics.uci.edu/ml/datasets/Concrete+Compressive+Strength здесь]. || width="40%"|Имеется набор вин, произведенных в одном регионе Италии, но в трех разных винодельнях. Задача состоит в том, чтобы определить конкретную винодельню (конкретное место происхождения вина) по данным химического анализа вина. Эти данные включают в себя такие параметры как крепость, содержание яблочной кислоты, содержание различных видов флавоноидов и др. Исходные данные и подробное описание задачи можно скачать [http://archive.ics.uci.edu/ml/datasets/Wine здесь]. || [[Изображение:MOTP11_wine.jpg|thumb|200px]]
+=== Описание практической задачи ===
- |}
+[[Изображение:Mnist.jpg|thumb|300px|Примеры изображений рукописных цифр для задачи MNIST]]
+Рассматривается задача распознавания рукописных цифр MNIST. Исходные данные можно скачать [http://yann.lecun.com/exdb/mnist/ здесь]. В этой задаче объектами являются черно-белые изображения размера <tex>28{\times}28</tex>, на каждом из которых представлена одна рукописная цифра, а метками класса являются сами цифры. Таким образом, в данном случае рассматривается задача классификации на 10 классов. Признаковым описанием одного объекта (изображения) являются интенсивности пикселов, вытянутые в вектор. Для устойчивости всех вычислений рекомендуется разделить интенсивности пикселей на 255, чтобы получить значения в диапазоне [0,1].
+При решении данной задачи с помощью двухклассового метода опорных векторов следует выбрать несколько пар классов, например, четверки и девятки или пятерки и шестерки. Также для ускорения вычислений в качестве обучающей выборки можно брать не все имеющиеся данные, а только часть из них, выбранных случайно с сохранением пропорций между классами. В качестве результата классификации на тестовой выборке помимо доли правильно распознанных объектов рекомендуется приводить матрицу точности, в которой в позиции ''(i,j)'' находится количество объектов, отнесенных классификатором к классу ''j'' при том, что на самом деле они принадлежат классу ''i''.
+При решении задачи с помощью метода К средних также следует выбрать несколько пар классов и приводить результаты с помощью матрицы точности. При этом необходимо привести примеры пар классов, для которых метод К средних дает хороший результат, и примеры пар классов, для которых кластеризация сильно отличается от истинной классификации.
 == Процедура сдачи задания ==
@@ Строка 249: / Строка 286: @@
 === Оформление задания ===
-Необходимо {{важно|в срок до 1 сентября 2011}} прислать выполненный вариант задания письмом по адресу ''bayesml@gmail.com'' с темой «Задание СФ, ФИО, номер группы». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
+Необходимо {{важно|в срок до 30 августа 2012}} прислать выполненный вариант задания письмом по адресу ''bayesml@gmail.com'' с темой «[МОТП12] Задание СФ, ФИО, номер группы». Убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
 Письмо должно содержать:
-*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
+*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел);
-*Файлы linreg_train.m, linreg_test.m, logreg_train.m, logreg_test.m или аналогичные им исполняемые файлы
+*Файлы svm_train.m, svm_test.m, k_means.m;
-*Набор вспомогательных файлов при необходимости
+*Файлы, с помощью которых осуществлялось построение всех графиков в отчете;
+*Набор дополнительных файлов при необходимости.
 === Защита задания ===