Методы оптимизации в машинном обучении (курс лекций)/2012/Задание 3

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

(Различия между версиями)
Перейти к: навигация, поиск
(релиз)
 
(8 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
{{stop|Текст задания находится в стадии формирования. Просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.}}
 
-
 
__NOTOC__
__NOTOC__
Строка 7: Строка 5:
[[Image:MOMO12_IPM.png|300px]]
[[Image:MOMO12_IPM.png|300px]]
-
'''Начало выполнения задания''': 24 ноября 2012
+
'''Начало выполнения задания''': 23 ноября 2012
-
'''Срок сдачи''': {{ins|7 декабря 2012 (пятница), 23:59}}
+
'''Срок сдачи''': {{ins|6 декабря 2012 (четверг), 23:59}}
Среда реализации задания – MATLAB.
Среда реализации задания – MATLAB.
=== Модель <tex>L_1</tex>-регуляризованной линейной регрессии ===
=== Модель <tex>L_1</tex>-регуляризованной линейной регрессии ===
 +
 +
==== Формулировка метода ====
 +
 +
Рассматривается задача восстановления регрессии. Имеется обучающая выборка <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\mathbb{R}</tex> — его регрессионное значение. Задача заключается в прогнозировании регрессионного значения <tex>t_{new}</tex> для нового объекта, представленного своим вектором признаков <tex>\vec{x}_{new}</tex>.
 +
 +
В линейной регрессии прогнозирование осуществляется с помощью линейной функции:
 +
 +
<tex>t(\vec{x}_{new}) = \sum_{d=1}^Dw_dx_{new,d} = \vec{w}^T\vec{x}_{new}</tex>,
 +
 +
где <tex>\vec{w}\in\mathbb{R}^D</tex> — некоторые веса. Настройка весов осуществляется путем минимизации следующего регуляризованного критерия:
 +
 +
<tex>J = \frac{1}{2}\sum_{n=1}^N(t_n - \vec{w}^T\vec{x}_n)^2 + \lambda\sum_{d=1}^D|w_d| = \frac{1}{2}||\vec{t} - X\vec{w}||^2 + \lambda||\vec{w}||_1\rightarrow\min_{\vec{w}}.\qquad (1)</tex>
 +
 +
Здесь <tex>\lambda\ge 0</tex> — задаваемый пользователем параметр регуляризации. Использование <tex>L_1</tex>-регуляризации позволяет, во-первых, снизить вероятность переобучения алгоритма, а во-вторых, получить т.н. разреженное решение. В разреженном решении часть компонент оптимального вектора весов <tex>\vec{w}</tex> равно нулю. Нулевые веса для некоторых признаков равносильны их исключению из модели (признание их неинформативными).
 +
 +
==== Двойственная задача ====
 +
 +
Рассмотрим получение двойственной задачи оптимизации для задачи (1). Для этого рассмотрим эквивалентную постановку данной задачи в виде задачи условной оптимизации:
 +
 +
<tex>\begin{cases}&\frac{1}{2}\vec{z}^T\vec{z} + \lambda ||\vec{w}||_1\rightarrow\min_{\vec{z},\vec{w}},\\ &X\vec{w}-\vec{t} = \vec{z}.\end{cases}</tex>
 +
 +
Далее можно показать, что двойственной к данной задаче выпуклой оптимизации будет следующая:
 +
 +
<tex>\begin{cases}&-\frac{1}{2}\vec{\mu}^T\vec{\mu} - \vec{\mu}^T\vec{t}\rightarrow\max_{\vec{\mu}},\\ &||X^T\vec{\mu}||_{\infty}\le\lambda.\end{cases}\qquad (2)</tex>
 +
 +
Здесь под <tex>||\vec{y}||_{\infty}</tex> понимается <tex>\max(|y_1|,\dots,|y_D|)</tex>.
 +
 +
==== Гладкая задача ====
 +
 +
Задачу выпуклой негладкой оптимизации (1) можно эквивалентно представить в виде задачи гладкой условной минимизации:
 +
 +
<tex>\begin{cases}&\frac{1}{2}||\vec{t}-X\vec{w}||^2 + \lambda\sum_{d=1}^Du_d\rightarrow\min_{\vec{w},\vec{u}},\\ &-u_d\le w_d\le u_d,\ \forall d = 1,\dots,D.\end{cases}\qquad (3)</tex>
=== Формулировка задания ===
=== Формулировка задания ===
-
* Вывести двойственную задачу оптимизации для задачи обучения <tex>L_1</tex>-регуляризованной линейной регрессии;
+
* Вывести двойственную задачу оптимизации (2); записать, как по решению двойственной задачи (2) можно получить решение прямой задачи (1);
-
* Для полученной двойственной задачи предложить формулу вычисления допустимой двойственной точки по заданной прямой точке, на ее основе записать верхнюю оценку на зазор между решениями прямой и двойственной задач;
+
* Для задачи (2) предложить формулу вычисления допустимой двойственной точки <tex>\vec{\mu}</tex> по заданной прямой точке <tex>\vec{w}</tex>, на ее основе записать верхнюю оценку на зазор между решениями прямой задачи (1) и двойственной задачи (2);
-
* Вывести необходимые формулы для решения гладкой задачи обучения (*) с помощью метода барьерных функций; предложить свой способ эффективного решения соответствующей СЛАУ, необходимые для этого формулы вставить в отчет;
+
* Вывести необходимые формулы для решения гладкой задачи обучения (3) с помощью метода барьерных функций; предложить свой способ эффективного решения соответствующей СЛАУ, необходимые для этого формулы вставить в отчет;
-
* Реализовать метод барьерных функция для решения задачи (*);
+
* Реализовать метод барьерных функций для решения задачи (3); в качестве критерия останова использовать полученную верхнюю оценку на зазор;
-
* Вывести необходимые формулы для решения двойственной задачи с помощью прямо-двойственного метода внутренней точки; предложить свой способ эффективного решения возмущенной ККТ-системы, необходимые для этого формулы вставить в отчет;
+
* Вывести необходимые формулы для решения задачи (2) с помощью прямо-двойственного метода внутренней точки; предложить свой способ эффективного решения возмущенной ККТ-системы, необходимые для этого формулы вставить в отчет;
-
* Реализовать прямо-двойственный метод внутренней точки для двойственной задачи;
+
* Реализовать прямо-двойственный метод внутренней точки для задачи (2); в качестве критерия останова использовать норму правой части возмущенной ККТ-системы;
-
* Реализовать на выбор проксимальный или покоординатный метод для решения задачи обучения <tex>L_1</tex>-регуляризованной линейной регрессии;
+
* Реализовать на выбор проксимальный или покоординатный метод для решения задачи обучения (1);
-
* Провести экспериментальное сравнение трех реализованных методов на предмет скорости работы при 1) различных соотношений количества объектов и признаков в данных и 2) различных значений параметра точности <tex>\varepsilon</tex>;
+
* Провести экспериментальное сравнение трех реализованных методов (метод барьеров для задачи (1), прямо-двойственный метод внутренней точки для задачи (2) и проксимальный/покоординатный метод для задачи (1)) на предмет скорости работы при 1) различных соотношениях между количеством объектов и признаков в данных и 2) различных значениях параметра точности <tex>\varepsilon</tex>;
-
* Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен содержать, в частности, количество обращений к оракулу при всех запусках итерационных процессов оптимизации.
+
* Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен содержать, в частности, необходимые формулы для всех методов. Также во всех приведенных экспериментах должно быть указано количество итераций, точность, параметры и время работы методов.
=== Спецификация реализуемых функций ===
=== Спецификация реализуемых функций ===
{|class="standard"
{|class="standard"
-
!''Метод золотого сечения''
+
!''Обучение методом штрафных функций''
|-
|-
-
|[x_min, f_min, status] = min_golden(func, interval, param_name1, param_value1, ...)
+
|w = '''l1linreg_barrier'''(X, t, lambda, param_name1, param_value1, ...)
|-
|-
|ВХОД
|ВХОД
Строка 37: Строка 67:
|
|
{|border="0"
{|border="0"
-
|func указатель на оптимизируемую функцию;
+
|X обучающая выборка, матрица размера NxD;
|-
|-
-
|interval границы интервала оптимизации, вектор типа double длины 2;
+
|t регрессионные значения, вектор длины N;
 +
|-
 +
|lambda — параметр регуляризации, число;
|-
|-
|(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
|(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
Строка 45: Строка 77:
|
|
{|border="0"
{|border="0"
-
|'eps' — точность оптимизации по аргументу, число, по умолчанию = 1e-5;
+
|'eps' — точность оптимизации по зазору, число, по умолчанию = 1e-5;
|-
|-
-
|'max_iter' — максимальное число итераций, число, по умолчанию = 500;
+
|'max_iter' — максимальное число внешних итераций, число, по умолчанию = 100;
|-
|-
-
|'display' — режим отображения, true или false, если true, то отображаются номер итерации, текущее значение функции, аргумента, текущая точность и др. показатели, по умолчанию = false;
+
|'max_iter2' — максимальное число внутренних итераций, число, по умолчанию = 10;
|-
|-
-
|}
+
|'t_params' — стратегия увеличения параметра центрирования <tex>\tau</tex>, вектор из двух чисел <tex>[\tau_{start},\ v]</tex>, по умолчанию = [1 10];
-
|-
+
-
|}
+
-
|-
+
-
|ВЫХОД
+
-
|-
+
-
|
+
-
{|
+
-
|x_min — найденное значение минимума, число;
+
-
|-
+
-
|f_min — значение функции в точке минимума, число;
+
-
|-
+
-
|status — результаты оптимизации, структура со следующими полями:
+
-
|-
+
-
|
+
-
{|border="0"
+
-
|'flag' — общий результат, число, равно 1, если достигнут оптимум с точностью eps, равно -1, если произошел выход по максимальному числу итераций;
+
-
|-
+
-
|'num_oracle' — количество обращений к оракулу;
+
-
|-
+
-
|}
+
-
|-
+
-
|}
+
-
|}
+
-
 
+
-
Прототипы функций min_parabolic для метода парабол, min_qubic для кубических аппроксимаций и min_brent для метода Брента выглядят аналогично. В методе Брента добавляется параметр 'use_gradient' с возможными значениями true и false для учета случая оптимизации с производной и без. При отображении в методе Брента необходимо указывать способ выбора очередной точки на каждой итерации (golden/parabolic или bisection/parabolic).
+
-
 
+
-
{|class="standard"
+
-
!''Метод Флетчера''
+
-
|-
+
-
|[alpha_min, f_min, status] = min_fletcher(func, x, d, param_name1, param_value1, ...)
+
-
|-
+
-
|ВХОД
+
-
|-
+
-
|
+
-
{|border="0"
+
-
|func — указатель на оптимизируемую функцию;
+
-
|-
+
-
|x — текущая точка, вектор типа double;
+
-
|-
+
-
|d — направление минимизации, вектор типа double;
+
-
|-
+
-
|(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
+
-
|-
+
-
|
+
-
{|border="0"
+
-
|'params' — параметры метода [rho sigma tau xi], по умолчанию = [0.1 0.7 0.1 9];
+
|-
|-
-
|'max_iter' — максимальное число итераций, число, по умолчанию = 100;
+
|'b_params' — параметры для стратегии backtracking при поиске длины шага, вектор из трех чисел [alpha, beta, rho], по умолчанию = [1 0.5 0.1];
|-
|-
-
|'display' — режим отображения, true или false, по умолчанию = false;
+
|'display' — режим отображения, true или false, если true, то отображаются текущие показатели метода на каждой итерации, по умолчанию = false;
|-
|-
|}
|}
Строка 111: Строка 97:
|
|
{|
{|
-
|alpha_min найденное значение минимума для alpha, число;
+
|w найденные веса, вектор длины D.
-
|-
+
-
|f_min — значение функции в точке минимума, число;
+
-
|-
+
-
|status — результаты оптимизации, структура со следующими полями:
+
-
|-
+
-
|
+
-
{|border="0"
+
-
|'flag' — общий результат, число, равно 1, если достигнут неточный оптимум, равно -1, если произошел выход по максимальному числу итераций;
+
-
|-
+
-
|'num_oracle' — количество обращений к оракулу;
+
-
|-
+
-
|}
+
-
|-
+
|}
|}
|}
|}
 +
 +
Аналогично выглядят прототипы функций ''l1linreg_pd'' для прямо-двойственного метода решения двойственной задачи, ''l1linreg_prox'' для проксимального метода и ''l1linreg_cd'' для метода покоординатного спуска.
=== Оформление задания ===
=== Оформление задания ===
Строка 134: Строка 109:
Письмо должно содержать:
Письмо должно содержать:
*PDF-файл с описанием проведенных исследований;
*PDF-файл с описанием проведенных исследований;
-
*Файлы min_golden.m, min_quadratic.m, min_cubic.m, min_brent.m, min_fletcher.m;
+
*Файлы l1linreg_barrier, l1linreg_pd, l1linreg_prox или l1linreg_cd;
*Набор вспомогательных файлов при необходимости.
*Набор вспомогательных файлов при необходимости.
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

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


Начало выполнения задания: 23 ноября 2012

Срок сдачи: 6 декабря 2012 (четверг), 23:59

Среда реализации задания – MATLAB.

Модель L_1-регуляризованной линейной регрессии

Формулировка метода

Рассматривается задача восстановления регрессии. Имеется обучающая выборка \{\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_{d=1}^Dw_dx_{new,d} = \vec{w}^T\vec{x}_{new},

где \vec{w}\in\mathbb{R}^D — некоторые веса. Настройка весов осуществляется путем минимизации следующего регуляризованного критерия:

J = \frac{1}{2}\sum_{n=1}^N(t_n - \vec{w}^T\vec{x}_n)^2 + \lambda\sum_{d=1}^D|w_d| = \frac{1}{2}||\vec{t} - X\vec{w}||^2 + \lambda||\vec{w}||_1\rightarrow\min_{\vec{w}}.\qquad (1)

Здесь \lambda\ge 0 — задаваемый пользователем параметр регуляризации. Использование L_1-регуляризации позволяет, во-первых, снизить вероятность переобучения алгоритма, а во-вторых, получить т.н. разреженное решение. В разреженном решении часть компонент оптимального вектора весов \vec{w} равно нулю. Нулевые веса для некоторых признаков равносильны их исключению из модели (признание их неинформативными).

Двойственная задача

Рассмотрим получение двойственной задачи оптимизации для задачи (1). Для этого рассмотрим эквивалентную постановку данной задачи в виде задачи условной оптимизации:

\begin{cases}&\frac{1}{2}\vec{z}^T\vec{z} + \lambda ||\vec{w}||_1\rightarrow\min_{\vec{z},\vec{w}},\\ &X\vec{w}-\vec{t} = \vec{z}.\end{cases}

Далее можно показать, что двойственной к данной задаче выпуклой оптимизации будет следующая:

\begin{cases}&-\frac{1}{2}\vec{\mu}^T\vec{\mu} - \vec{\mu}^T\vec{t}\rightarrow\max_{\vec{\mu}},\\ &||X^T\vec{\mu}||_{\infty}\le\lambda.\end{cases}\qquad (2)

Здесь под ||\vec{y}||_{\infty} понимается \max(|y_1|,\dots,|y_D|).

Гладкая задача

Задачу выпуклой негладкой оптимизации (1) можно эквивалентно представить в виде задачи гладкой условной минимизации:

\begin{cases}&\frac{1}{2}||\vec{t}-X\vec{w}||^2 + \lambda\sum_{d=1}^Du_d\rightarrow\min_{\vec{w},\vec{u}},\\ &-u_d\le w_d\le u_d,\ \forall d = 1,\dots,D.\end{cases}\qquad (3)

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

  • Вывести двойственную задачу оптимизации (2); записать, как по решению двойственной задачи (2) можно получить решение прямой задачи (1);
  • Для задачи (2) предложить формулу вычисления допустимой двойственной точки \vec{\mu} по заданной прямой точке \vec{w}, на ее основе записать верхнюю оценку на зазор между решениями прямой задачи (1) и двойственной задачи (2);
  • Вывести необходимые формулы для решения гладкой задачи обучения (3) с помощью метода барьерных функций; предложить свой способ эффективного решения соответствующей СЛАУ, необходимые для этого формулы вставить в отчет;
  • Реализовать метод барьерных функций для решения задачи (3); в качестве критерия останова использовать полученную верхнюю оценку на зазор;
  • Вывести необходимые формулы для решения задачи (2) с помощью прямо-двойственного метода внутренней точки; предложить свой способ эффективного решения возмущенной ККТ-системы, необходимые для этого формулы вставить в отчет;
  • Реализовать прямо-двойственный метод внутренней точки для задачи (2); в качестве критерия останова использовать норму правой части возмущенной ККТ-системы;
  • Реализовать на выбор проксимальный или покоординатный метод для решения задачи обучения (1);
  • Провести экспериментальное сравнение трех реализованных методов (метод барьеров для задачи (1), прямо-двойственный метод внутренней точки для задачи (2) и проксимальный/покоординатный метод для задачи (1)) на предмет скорости работы при 1) различных соотношениях между количеством объектов и признаков в данных и 2) различных значениях параметра точности \varepsilon;
  • Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен содержать, в частности, необходимые формулы для всех методов. Также во всех приведенных экспериментах должно быть указано количество итераций, точность, параметры и время работы методов.

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

Обучение методом штрафных функций
w = l1linreg_barrier(X, t, lambda, param_name1, param_value1, ...)
ВХОД
X — обучающая выборка, матрица размера NxD;
t — регрессионные значения, вектор длины N;
lambda — параметр регуляризации, число;
(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
'eps' — точность оптимизации по зазору, число, по умолчанию = 1e-5;
'max_iter' — максимальное число внешних итераций, число, по умолчанию = 100;
'max_iter2' — максимальное число внутренних итераций, число, по умолчанию = 10;
't_params' — стратегия увеличения параметра центрирования \tau, вектор из двух чисел [\tau_{start},\ v], по умолчанию = [1 10];
'b_params' — параметры для стратегии backtracking при поиске длины шага, вектор из трех чисел [alpha, beta, rho], по умолчанию = [1 0.5 0.1];
'display' — режим отображения, true или false, если true, то отображаются текущие показатели метода на каждой итерации, по умолчанию = false;
ВЫХОД
w — найденные веса, вектор длины D.

Аналогично выглядят прототипы функций l1linreg_pd для прямо-двойственного метода решения двойственной задачи, l1linreg_prox для проксимального метода и l1linreg_cd для метода покоординатного спуска.

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

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

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

  • PDF-файл с описанием проведенных исследований;
  • Файлы l1linreg_barrier, l1linreg_pd, l1linreg_prox или l1linreg_cd;
  • Набор вспомогательных файлов при необходимости.
Личные инструменты