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

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

(Различия между версиями)
Перейти к: навигация, поиск
(структура категорий)
(→Спецификация реализуемых функций)
Строка 84: Строка 84:
{|class="standard"
{|class="standard"
-
!''Алгоритм TRW''
+
!''Обучение линейной регрессии''
|-
|-
-
|[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC)
+
|a = linreg_train(X, t, options)
-
|-
+
-
|[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC, options)
+
|-
|-
|ВХОД
|ВХОД
Строка 94: Строка 92:
|
|
{|border="0"
{|border="0"
-
|unary — унарные потенциалы, массив типа double размера N x M x K, где N — высота решетки, M — ширина решетки, K — количество меток.
+
|X — обучающая выборка, матрица типа double размера N x M, где N — число объектов, M — число признаков.
|-
|-
-
|vertC — коэффициенты <tex> c_{pq}</tex>, соответствующие вертикальным ребрам, массив типа double размера (N — 1) x M;
+
|t — значение регрессионной переменной, вектор типа double размера 1 x N;
|-
|-
-
|horC — коэффициенты <tex> c_{pq}</tex>, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
+
|options — (необязательный аргумент) набор дополнительных параметров, структура размера 1 x 1, названия полей структуры совпадают с названиями параметров. Возможны следующие имена параметров и их значения:
|-
|-
-
|options — (необязательный аргумент) набор дополнительных параметров, массив типа '''cell''' вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
+
|&nbsp;&nbsp;'reg_coef' — значение коэффициента регуляризации (по умолчанию = 1e-6);
|-
|-
-
|&nbsp;&nbsp;'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
+
|&nbsp;&nbsp;'reg_coef_tuning' — флаг использования скользящего контроля для настройки коэффициента регуляризации, тип logical, если false, то используется значение из reg_coef (по умолчанию = false);
|-
|-
-
|&nbsp;&nbsp;'argEps' — порог сходимости по аргументу;
+
|&nbsp;&nbsp;'basis_functions' — семейство используемых базисных функций, тип char размера 1 x S, возможные значения 'initial', 'polynomial', 'rbf' (по умолчанию = 'initial');
|-
|-
-
|&nbsp;&nbsp;'display' — параметр типа logical: если true, то на каждой итерации нужно выводить на экран номер итерации, текущее значение энергии и нижней границы;
+
|&nbsp;&nbsp;'basis_functions_param' — значение параметра для базисных функций, тип double размера 1 x 1, для семейства 'rbf' здесь задается значение параметра gamma, для семейства 'polynomial' — степень полинома (по умолчанию = 1);
 +
|-
 +
|&nbsp;&nbsp;'basis_functions_tuning' — флаг использования скользящего контроля для подбора параметров базисных функций, тип logical, если false, то используется значение из basis_functions_param (по умолчанию = false);
 +
|-
 +
|&nbsp;&nbsp;'display' — параметр отображения, тип logical, если false, то на экране ничего не отображается, если true, то отображается текущий статус вычислений в произвольной форме (какие значения параметров пробуются, какие ошибки на скользящем контроле получаются, какие итоговые значения параметров оказались наилучшими и т.д.);
|}
|}
|-
|-
Строка 113: Строка 115:
|
|
{|
{|
-
|labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
+
|a — обученная модель линейной регрессии, структура размера 1 x 1, поля структуры имеют следующие имена и значения:
-
|-
+
{|border="0"
-
|energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
+
|'w' — веса линейного решающего правила, вектор типа double размера 1 x M1, где M1 — число базисных функций.
-
|-
+
|-
-
|lowerBound — значения нижней границы на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
+
|}
-
|-
+
-
|time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма.
+
|}
|}
|}
|}

Версия 18:51, 27 июня 2011

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


Содержание

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

Срок сдачи задания: 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} — фиксированные базисные функции (новые признаки). Примеры базисных функций:

  1. Исходные признаки: \phi_j(\vec{x})=x_j;
  2. Степени признаков: \phi_j(\vec{x})=x^j;
  3. Радиальные базисные функции: \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 в радиальных базисных функциях, то выбирается двухмерная сетка значений параметров и находится та пара, для которой ошибка на скользящем контроле является наименьшей.

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

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

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

Для выполнения задания на оценку «удовлетворительно» достаточно реализовать только пункты, связанные с логистической регрессией, а также написать отчет. Для выполнения задания на оценку «хорошо» необходимо выполнить все пункты задания. При этом, в случае прекрасного выполнения всех пунктов задания, возможна оценка «отлично».

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

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

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

Сегментация изображений
[segmentation] = segmentImage(image, seeds)
ВХОД
image — изображение, массив типа double размера N x M x 3 (все значения в этом массиве в интервале от 0 до 1).
seeds — семена, заданные пользователем, массив типа logical размера N x M x K, элементы массива принимают значения true или false;
ВЫХОД
segmentation — сегментация изображения, массив типа double размера N x M со значениями 1,...,K;

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

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

1. При разбиении MRF-решетки только на вертикальные и горизонтальные цепочки формулировка несколько упрощается:

  • Каждое ребро графа принадлежит только одному подграфу, а, значит, не нужно вводить двойственные переменные, соответствующие ребрам.
  • Каждая вершина принадлежит только двум деревьям, а, значит, можно ввести |P|K двойственных переменных, соответствующих условиям y_{pk}^{hor} = y_{pk}^{vert}, \;\; p \in P, \;\; k = 1,\dots,K, где hor и vert обозначают горизонтальную и вертикальную цепочку, проходящую через p-ю вершину.

2. Поскольку двойственная функция вогнута и кусочно-линейна, оптимизировать ее можно при помощи алгоритма субградиентного подъема. Каждый шаг метода субградиентного подъема состоит в пересчете значений двойственных переменных λ по следующему правилу:
\vec{\lambda}_{new} = \vec{\lambda}_{old} + \alpha_t \vec{g}_t, где \vec{g}_t — субградиент в текущей точке, \alpha_t — параметр, отвечающий за длину сдвига. В рамках данного практического задания можно использовать любой способ субградиентного подъема. Например, можно использовать следующий адаптивный метод выбора длины шага:
\alpha_t = \frac{\text{Approx}_t - \text{Dual}_t}{|| \nabla \vec{g}_t|| ^ 2},
где \text{Dual}_t — текущее значение двойственной функции, \text{Approx}_t — оценка оптимума двойственной функции, которую можно определять следующим способом:
\text{Approx}_t = \text{BestDual}_t + \delta_t, где \text{BestDual}_t — лучшее на данный момент значение двойственной функции,
\delta_{t+1} = \begin{cases} \gamma_0 \delta_t, \;\; \text{Dual}_t > \text{Dual}_{t-1}, \\ \max(\gamma_1 \delta_t, \; \varepsilon ), \;\; \text{Dual}_t \leq \text{Dual}_{t-1}. \end{cases}
\gamma_0, \; \gamma_1, \; \varepsilon — параметры метода. Обычно \gamma_0 > 1, \; 1 > \gamma_1 > 0, \; \varepsilon \to 0+ . Конкретные значения этих параметров нужно подобрать.

3. В качестве текущего значения энергии в рамках алгоритма TRW можно выбрать минимум энергий разметок, полученных по только вертикальным и только горизонтальным цепочкам.

4. При тестировании алгоритма TRW необходимо следить, чтобы наибольшее значение нижней границы было не больше, чем наименьшее значение энергии.

5. Для генерации масок семян для сегментации изображений можно использовать любой редактор растровой графики (например, Paint). На изображении нужно определенным цветом закрасить пиксели, относящиеся к маске, и, впоследствии, выделить их в MATLAB.

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

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

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

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

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

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

  • PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
  • trwGridPotts.m
  • segmentImage.m
  • Набор вспомогательных файлов при необходимости
Источник — «http://www.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»
Личные инструменты