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

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

Перейти к: навигация, поиск
Внимание! Текст задания находится в стадии формирования. Убедительная просьба не приступать к выполнению данного задания до тех пор, пока это предупреждение не будет удалено.


Содержание

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

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

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

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

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

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

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

Рассматривается задача классификации на два класса. Имеется обучающая выборка \{\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 находится путем минимизации числа ошибок на обучающей выборке.

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

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

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

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

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

Обозначим обучающую выборку через 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}error(t_n, a(\vec{x}_n, Y_{\backslash k})).

Здесь через Y_{\backslash k} обозначена обучающая выборка без части Y_k, а через error(t, y) — величина ошибки между предсказанием y и истинным значением t. Эта ошибка вычисляется как

error(t,y)=(t-y)^2 — для задачи регрессии и error(t,y)=\begin{cases}0,\ t=y,\\1,\ t\neq y,\end{cases} — для задачи классификации.

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

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

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

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

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

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

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

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

Для выполнения задания на оценку «удовлетворительно» достаточно реализовать только пункты 4–8 без семейства полиномиальных базисных функций. Для выполнения задания на оценку «хорошо» и «отлично» необходимо выполнить все пункты задания.

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

Рекомендуемая среда для выполнения задания — MATLAB. При выполнении задания в среде MATLAB необходимые алгоритмы должны быть реализованы по прототипам, указанным ниже. В случае использования других сред для выполнения задания, реализуемые функции должны соответствовать прототипам, описанным ниже. Например, при программировании на языке C набор параметров для обучения должен задаваться в текстовом файле, при этом список параметров и их возможные значения следует брать из прототипов ниже.

Обучение линейной регрессии
a = linreg_train(X, t, options)
ВХОД
X — обучающая выборка, матрица типа double размера N x M, где N — число объектов, M — число признаков.
t — значение регрессионной переменной, вектор типа double размера 1 x N;
options — (необязательный аргумент) набор дополнительных параметров, структура размера 1 x 1, названия полей структуры совпадают с названиями параметров. Возможны следующие имена параметров и их значения:
  'reg_coef' — значение коэффициента регуляризации (по умолчанию = 1e-6);
  'reg_coef_tuning' — флаг использования скользящего контроля для настройки коэффициента регуляризации, тип logical, если false, то используется значение из reg_coef (по умолчанию = false);
  'basis_functions' — семейство используемых базисных функций, тип char размера 1 x S, возможные значения 'initial', 'polynomial', 'rbf' (по умолчанию = 'initial');
  'basis_functions_param' — значение параметра для базисных функций, тип double размера 1 x 1, для семейства 'rbf' здесь задается значение параметра gamma, для семейства 'polynomial' — степень полинома (по умолчанию = 1);
  'basis_functions_tuning' — флаг использования скользящего контроля для подбора параметров базисных функций, тип logical, если false, то используется значение из basis_functions_param (по умолчанию = false);
  'display' — параметр отображения, тип logical, если false, то на экране ничего не отображается, если true, то отображается текущий статус вычислений в произвольной форме (какие значения параметров пробуются, какие ошибки на скользящем контроле получаются, какие итоговые значения параметров оказались наилучшими и т.д.);
ВЫХОД
a — обученная модель линейной регрессии, структура размера 1 x 1, поля структуры имеют следующие имена и значения:
'w' — веса линейного решающего правила, вектор типа double размера 1 x M1, где M1 — число базисных функций (для базисных функций initial M1=M+1, для базисных функций polynomial M1 = \sum_{k=1}^KC_M^k+1, K=basis_functions_param, для базисных функций rbf M1=N+1, единица добавляется в M1 за счет свободного члена, т.е. базисной функции \phi(\vec{x})\equiv 1);
'basis_functions' — семейство используемых базисных функций, совпадает с входным значением 'basis_functions';
'basis_functions_param' — параметр базисных функций, совпадает с входным значением 'basis_functions_param';
'support_objects' — набор опорных объектов для базисных функций rbf, совпадает с обучающей выборкой, если 'basis_functions' == 'rbf', иначе пусто;
'm' — нормировочные средние значения для каждого признака, вектор типа double размера 1 x M1;
's' — нормировочные дисперсии для каждого признака, вектор типа double размера 1 x M1.

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

Тестирование линейной регрессии
[Outputs, ErrorRate] = linreg_test(a, X, t)
ВХОД
a — обученная модель линейной регрессии, структура, которую возвращает функция linreg_train;
X — тестовая выборка, матрица типа double размера N_test x M;
t — (необязательный аргумент), истинные значения целевой переменной для тестовой выборки, вектор типа double размера 1 x N_test.
ВЫХОД
Outputs — прогноз значений регрессионной переменной, вектор типа double размера 1 x N_test;
ErrorRate — (если вектор t задан) \sqrt{\frac{1}{N_{test}}\sum_{n=1}^{N_{test}}(t_n-Outputs_n)^2};

Прототип функции обучения логистической регрессии logreg_train целиком повторяет прототип linreg_train. При этом вектор меток класса \vec{t} должен содержать значения только 1 и 2.

Тестирование логистической регрессии
[Outputs, Answers, ErrorRate] = logreg_test(a, X, t)
ВХОД
a — обученная модель логистической регрессии, структура, которую возвращает функция logreg_train;
X — тестовая выборка, матрица типа double размера N_test x M;
t — (необязательный аргумент), истинные значения меток класса для тестовой выборки, вектор типа double размера 1 x N_test.
ВЫХОД
Outputs — значения линейной функции f(\vec{x}) для объектов тестовой выборки, вектор типа double размера 1 x N_test;
Answers — спрогнозированные метки класса для объектов тестовой выборки, вектор типа double размера 1 x N_test;
ErrorRate — (если вектор t задан) процент допущенных ошибок классификации.

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

1. Эффективное программирование под MATLAB предполагает активнейшее использование векторных и матричных операций. В частности, по возможности следует избегать любых циклов. Например, для вычисления матрицы попарных расстояний между набором объектов, задаваемых матрицами X и Y, можно воспользоваться свойством ||\vec{x}-\vec{y}||^2=||\vec{x}||^2 - 2\vec{x}^T\vec{y} + ||\vec{y}||^2, что в MATLAB может быть реализовано как 

    normX = sum(X.^2,2);
    normY = sum(Y.^2,2);
    diffXY = bsxfun(@plus, bsxfun(@plus, -2*X*Y', normX), normY');

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

3. Проверять корректность реализации обучения и тестирования линейной/логистической регрессии следует, в первую очередь, на модельных данных. Например, для проверки линейной регрессии можно сгенерировать данные с одним признаком, в которых регрессионная переменная вычисляется как значение полинома некоторой степени от значения признака со сгенерированными коэффициентами плюс небольшой нормальный шум. Тогда при обучении линейной регрессии с полиномиальными базисными функциями и правильной степенью полинома результат предсказания должен быть очень хорошим. Эту ситуацию можно отобразить и визуально. Например, для случая полинома первой степени картинка может выглядеть так:

Кроме того, при автоматическом определении степени полинома по скользящему контролю выбираемое значение степени должно совпадать или быть близким к истинному.

4. Эффекты переобучения/недообучения для линейной/логистической регрессии можно продемонстрировать следующим образом. Для линейной регрессии достаточно сгенерировать одномерные данные с полиномом 3-ей степени. Тогда обучение линейной регрессии с полиномиальными базисными функциями первой степени должно приводить к недообучению, >6-ой степени — к переобучению, а 3-ей степени — к адекватному восстановлению зависимости. Для логистической регрессии можно сгенерировать двухмерные данные с существенно нелинейной разделяющей поверхностью. Тогда обучение логистической регрессии с радиальными базисными функциями и маленьким значением \gamma должно приводить к недообучению, с большим значением \gamma — к переобучению, а некоторое среднее значение \gamma будет соответствовать адекватной разделяющей поверхности.

Различные модели линейной регрессии. Зеленая кривая — недообучение, черная кривая — переобучение, голубая кривая — адекватная зависимость
Различные модели линейной регрессии. Зеленая кривая — недообучение, черная кривая — переобучение, голубая кривая — адекватная зависимость
Различные модели логистической регрессии. Зеленое решающее правило — недообучение, черное решающее правило — переобучение, голубое решающее правило — адекватное разделение данных
Различные модели логистической регрессии. Зеленое решающее правило — недообучение, черное решающее правило — переобучение, голубое решающее правило — адекватное разделение данных

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

Определение предела прочности бетона Классификация вин по месту происхождения
Задача состоит в том, чтобы спрогнозировать уровень давления, при котором конкретная бетонная смесь разрушается, в зависимости от процента содержания в ней цемента, воды, возраста смеси и др. показателей. Исходные данные и подробное описание задачи можно скачать здесь. Имеется набор вин, произведенных в одном регионе Италии, но в трех разных винодельнях. Задача состоит в том, чтобы определить конкретную винодельню (конкретное место происхождения вина) по данным химического анализа вина. Эти данные включают в себя такие параметры как крепость, содержание яблочной кислоты, содержание различных видов флавоноидов и др. Исходные данные и подробное описание задачи можно скачать здесь.

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

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

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

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

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

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

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

Источник — «http://machinelearning.ru/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»
Личные инструменты