Математические основы теории прогнозирования (курс лекций, Ю.И. Журавлев, Д.П. Ветров)/2011/Задание СФ

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

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

Версия 14:50, 28 июня 2011

Текст задания находится в стадии формирования. Убедительная просьба не приступать к выполнению задания до тех пор, пока это сообщение не будет удалено.

Содержание

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

Перейти к основной странице курса

Срок сдачи задания: 1 сентября 2011, 23:59

Данное практическое задание предназначено для студентов Севастопольского филиала, которые имеют задолженность по курсу МОТП — Талалуева Кирилла, Пантелеева Ивана, Щербаткина Егора, Клименко Александра и Сребняка Ивана. Цель данного задания состоит в том, чтобы студенты познакомились на практике с простейшими методами решения задач регрессии и классификации — линейной и логистической регрессией соответственно, а также с базовыми аспектами, с которыми приходится сталкиваться при решении задач машинного обучения — проблемой переобучения и проблемой подбора структурных параметров алгоритмов (в данном случае в качестве таковых выступают коэффициенты регуляризации и параметры базисных функций).

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

Линейная регрессия

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

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

$t(\vec{x}_{new}) = \sum_{j=1}^Mw_j\phi_j(\vec{x}_{new})$ ,

где $w_j\in\mathbb{R}$ — веса линейного решающего правила, а $\phi_j:\mathbb{R}^d\rightarrow\mathbb{R}$ — фиксированные базисные функции (новые признаки). Примеры базисных функций:

Исходные признаки: $\phi_j(\vec{x})=x_j$ ;
Степени признаков: $\phi_j(\vec{x})=x_{j_1}x_{j_2}\dots x_{j_k},\ j_1,\dots,j_k\in\{1,\dots,d\},\ 1\le k\le K,\ K$ — степень полинома;
Радиальные базисные функции: $\phi_j(\vec{x})=\exp(-\gamma||\vec{x}-\vec{x}_j||^2)$ , где $\gamma>0$ , а $\vec{x}_j$ — некоторые заранее выбранные опорные объекты, например, объекты обучающей выборки.

Веса $\vec{w}$ линейного решающего правила настраиваются с помощью минимизации регуляризованного критерия наименьших квадратов:

$J = \frac{1}{N}\sum_{n=1}^N\biggl[t_n-\sum_{j=1}^Mw_j\phi_j(\vec{x}_n)\biggr]^2 + \lambda||\vec{w}||^2 = \frac{1}{N}||\vec{t}-\Phi\vec{w}||^2 + \lambda||\vec{w}||^2\rightarrow\min_{\vec{w}}$ .

Здесь $\lambda\ge 0$ — задаваемый пользователем параметр регуляризации. Данный функционал может быть минимизирован аналитически:

$\vec{w}_{opt}=\Biggl(\frac{1}{N}\Phi^T\Phi + \lambda I\Biggr)^{-1}\frac{1}{N}\Phi^T\vec{t}$ .

Логистическая регрессия

Рассматривается задача классификации на два класса. Имеется обучающая выборка $\{\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})=\sum_{j=1}^Mw_j\phi_j(\vec{x}_{new})\ge 0,\\-1,\ f(\vec{x}_{new})<0.\end{cases}$

Здесь веса $\vec{w}$ и базисные функции $\phi$ вводятся аналогично случаю линейной регрессии. Веса $\vec{w}$ решающего правила настраиваются с помощью минимизации следующего регуляризованного критерия:

$J = \frac{1}{N}\sum_{n=1}^N\log(1+\exp(-t_nf(\vec{x}_n))) + \lambda||\vec{w}||^2\rightarrow\min_{\vec{w}}$ .

Здесь $\lambda\ge 0$ — задаваемый пользователем параметр регуляризации. Функционал $J$ является выпуклой функцией относительно своих параметров $\vec{w}$ и поэтому может быть эффективно минимизирован с помощью любого итерационного метода безусловной оптимизации, учитывающего значения градиента и гессиана функции $J$ , например, метода Ньютона.

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

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

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

$Error_{cv} = \sum_{k=1}^K\ \sum_{n:\vec{x}_n\in X_k}error(t_n, a(\vec{x}_n, X_{\backslash k}))$ .

Здесь через $X_{\backslash k}$ обозначена обучающая выборка без части $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, для базисных функций polynomial $M1 = \sum_{k=0}^KC_M^k$ , K=basis_functions_param, для базисных функций rbf M1=N);

'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}$ ;

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

ZIP архив с MATLAB реализацией конвертера изображений.

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

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

Необходимо в срок до 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%2C_%D0%AE.%D0%98._%D0%96%D1%83%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%B2%2C_%D0%94.%D0%9F._%D0%92%D0%B5%D1%82%D1%80%D0%BE%D0%B2%29/2011/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A1%D0%A4»

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

@@ Строка 22: / Строка 22: @@
 где <tex>w_j\in\mathbb{R}</tex> — веса линейного решающего правила, а <tex>\phi_j:\mathbb{R}^d\rightarrow\mathbb{R}</tex> — фиксированные базисные функции (новые признаки). Примеры базисных функций:
 # ''Исходные признаки'': <tex>\phi_j(\vec{x})=x_j</tex>;
-# ''Степени признаков'': <tex>\phi_j(\vec{x})=x^j</tex>;
+# ''Степени признаков'': <tex>\phi_j(\vec{x})=x_{j_1}x_{j_2}\dots x_{j_k},\ j_1,\dots,j_k\in\{1,\dots,d\},\ 1\le k\le K,\ K</tex> — степень полинома;
 # ''Радиальные базисные функции'': <tex>\phi_j(\vec{x})=\exp(-\gamma||\vec{x}-\vec{x}_j||^2)</tex>, где <tex>\gamma>0</tex>, а <tex>\vec{x}_j</tex> — некоторые заранее выбранные опорные объекты, например, объекты обучающей выборки.