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

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

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



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

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

Срок сдачи: 7 декабря 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}) = \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)

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

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

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

Метод золотого сечения
[x_min, f_min, status] = min_golden(func, interval, param_name1, param_value1, ...)
ВХОД
func — указатель на оптимизируемую функцию;
interval — границы интервала оптимизации, вектор типа double длины 2;
(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
'eps' — точность оптимизации по аргументу, число, по умолчанию = 1e-5;
'max_iter' — максимальное число итераций, число, по умолчанию = 500;
'display' — режим отображения, true или false, если true, то отображаются номер итерации, текущее значение функции, аргумента, текущая точность и др. показатели, по умолчанию = false;
ВЫХОД
x_min — найденное значение минимума, число;
f_min — значение функции в точке минимума, число;
status — результаты оптимизации, структура со следующими полями:
'flag' — общий результат, число, равно 1, если достигнут оптимум с точностью eps, равно -1, если произошел выход по максимальному числу итераций;
'num_oracle' — количество обращений к оракулу;

Прототипы функций min_parabolic для метода парабол, min_qubic для кубических аппроксимаций и min_brent для метода Брента выглядят аналогично. В методе Брента добавляется параметр 'use_gradient' с возможными значениями true и false для учета случая оптимизации с производной и без. При отображении в методе Брента необходимо указывать способ выбора очередной точки на каждой итерации (golden/parabolic или bisection/parabolic).

Метод Флетчера
[alpha_min, f_min, status] = min_fletcher(func, x, d, param_name1, param_value1, ...)
ВХОД
func — указатель на оптимизируемую функцию;
x — текущая точка, вектор типа double;
d — направление минимизации, вектор типа double;
(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
'params' — параметры метода [rho sigma tau xi], по умолчанию = [0.1 0.7 0.1 9];
'max_iter' — максимальное число итераций, число, по умолчанию = 100;
'display' — режим отображения, true или false, по умолчанию = false;
ВЫХОД
alpha_min — найденное значение минимума для alpha, число;
f_min — значение функции в точке минимума, число;
status — результаты оптимизации, структура со следующими полями:
'flag' — общий результат, число, равно 1, если достигнут неточный оптимум, равно -1, если произошел выход по максимальному числу итераций;
'num_oracle' — количество обращений к оракулу;

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

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

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

  • PDF-файл с описанием проведенных исследований;
  • Файлы min_golden.m, min_quadratic.m, min_cubic.m, min_brent.m, min_fletcher.m;
  • Набор вспомогательных файлов при необходимости.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B2_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B8_%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_3»
Личные инструменты