Методы оптимизации в машинном обучении (курс лекций)/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}) = \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) предложить формулу вычисления допустимой двойственной точки \vec{\mu} по заданной прямой точке \vec{w}, на ее основе записать верхнюю оценку на зазор между решениями прямой задачи (1) и двойственной задачи (2);
  • Вывести необходимые формулы для решения гладкой задачи обучения (3) с помощью метода барьерных функций; предложить свой способ эффективного решения соответствующей СЛАУ, необходимые для этого формулы вставить в отчет;
  • Реализовать метод барьерных функций для решения задачи (3); в качестве критерия останова использовать полученную верхнюю оценку на зазор;
  • Вывести необходимые формулы для решения задачи (2) с помощью прямо-двойственного метода внутренней точки; предложить свой способ эффективного решения возмущенной ККТ-системы, необходимые для этого формулы вставить в отчет;
  • Реализовать прямо-двойственный метод внутренней точки для задачи (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;
  • Набор вспомогательных файлов при необходимости.
Источник — «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»