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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Спецификация реализуемых функций)
Строка 35: Строка 35:
{|class="standard"
{|class="standard"
-
!''Метод золотого сечения''
+
!''Обучение L2-регуляризованной логистической регрессии с помощью верхних оценок''
|-
|-
-
|[x_min, f_min, status] = min_golden(func, interval, param_name1, param_value1, ...)
+
|[w, f] = '''l2logreg_ub'''(X, t, lambda, w0, param_name1, param_value1, ...)
|-
|-
|ВХОД
|ВХОД
Строка 43: Строка 43:
|
|
{|border="0"
{|border="0"
-
|func — указатель на оптимизируемую функцию;
+
|X — обучающая выборка, матрица размера N x D, где N — число объектов, D — число признаков;
|-
|-
-
|interval — границы интервала оптимизации, вектор типа double длины 2;
+
|t — метки классов для обучающей выборки, вектор длины N со значениями +1 и -1;
 +
|-
 +
|lambda — значение параметра регуляризации, число;
 +
|-
 +
|w0 — начальный вектор весов, вектор длины D;
|-
|-
|(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
|(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
Строка 51: Строка 55:
|
|
{|border="0"
{|border="0"
-
|'eps' — точность оптимизации по аргументу, число, по умолчанию = 1e-5;
+
|'LS' — стратегия для решения промежуточных СЛАУ, строка, по умолчанию = 'chol', возможные значения:
|-
|-
-
|'max_iter' — максимальное число итераций, число, по умолчанию = 500;
+
|
 +
{|border="0"
 +
|'chol' — разложение Холецкого, эквивалентно матлабовской операции A\b;
 +
|-
 +
|'cg-full' — метод сопряженных градиентов, в котором операция умножения матрицы A на вектор w выполняется непосредственно;
 +
|-
 +
|'cg-cons' — метод сопряженных градиентов, в котором операция вида <tex>(X^TX + \lambda I)\vec{w}</tex> реализуется как <tex>\vec{w}_1 = X\vec{w},\ \vec{w}_2 = X^T\vec{w}_1,\ \vec{w}_3 = \vec{w}_2+\lambda\vec{w}</tex>.
 +
|}
|-
|-
-
|'display' — режим отображения, true или false, если true, то отображаются номер итерации, текущее значение функции, аргумента, текущая точность и др. показатели, по умолчанию = false;
+
|'eps' — точность оптимизации по функции и аргументу, число, по умолчанию = 1e-5;
 +
|-
 +
|'max_iter' — максимальное число итераций, число, по умолчанию = 100;
 +
|-
 +
|'display' — режим отображения, true или false, если true, то отображаются номер итерации, текущее значение верхней границы, норма разности между весами на последней и предпоследней итерациях и др. показатели, по умолчанию = false;
|-
|-
|}
|}
Строка 65: Строка 80:
|
|
{|
{|
-
|x_min — найденное значение минимума, число;
+
|w — найденное значение весов, вектор длины D;
|-
|-
-
|f_min — значение функции в точке минимума, число;
+
|f — значение верхней границы (совпадает с самой функцией) в точке оптимума w, число.
-
|-
+
-
|status — результаты оптимизации, структура со следующими полями:
+
-
|-
+
-
|
+
-
{|border="0"
+
-
|'flag' — общий результат, число, равно 1, если достигнут оптимум с точностью eps, равно -1, если произошел выход по максимальному числу итераций;
+
-
|-
+
-
|'num_oracle' — количество обращений к оракулу;
+
-
|-
+
-
|}
+
|-
|-
|}
|}
|}
|}
 +
Обратите внимание, что точность решения СЛАУ при использовании метода сопряженных градиентов должна превышать заданную точность eps.
=== Оформление задания ===
=== Оформление задания ===

Версия 15:43, 26 октября 2012

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



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


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

Срок сдачи: 9 ноября (пятница), 23:59

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

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

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

Использование базисных функций

Использование L_1-регуляризации

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

  • Реализовать процедуру обучения логистической регрессии с квадратичной регуляризацией с помощью трех подходов:
    1. Метод Ньютона с ограниченным шагом (damped Newton) и адаптивным подбором длины шага,
    2. Метод L-BFGS с подбором длины шага через backtracking,
    3. Метод на основе верхней оценки Йакколы-Джордана для логистической функции, в котором на этапе решения СЛАУ используется метод сопряженных градиентов;
  • Провести тестирование разработанных методов на модельных данных для различных сочетаний количества объектов и признаков, особое внимание при этом необходимо уделить случаю данных большого объема;
  • Реализовать процедуру обучения L_1-регуляризованной логистической регрессии с помощью двух подходов:
    1. Метод покоординатного спуска с подбором длины шага через backtracking,
    2. Метод с использованием верхней оценки Йаккола-Джордана для логистической функции и квадратичной оценки для функции модуля, в котором на этапе решения СЛАУ используется метод сопряженных градиентов;
  • Провести тестирование разработанных методов на модельных данных для различных сочетаний количества объектов и признаков, особое внимание при этом необходимо уделить ситуации, когда число признаков превосходит число объектов, и случаю данных большого объема;
  • Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен содержать, в частности, необходимые формулы для методов с использованием верхних оценок: вид оптимизируемого функционала и формулы пересчета параметров.

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

Обучение L2-регуляризованной логистической регрессии с помощью верхних оценок
[w, f] = l2logreg_ub(X, t, lambda, w0, param_name1, param_value1, ...)
ВХОД
X — обучающая выборка, матрица размера N x D, где N — число объектов, D — число признаков;
t — метки классов для обучающей выборки, вектор длины N со значениями +1 и -1;
lambda — значение параметра регуляризации, число;
w0 — начальный вектор весов, вектор длины D;
(param_name, param_value) — необязательные параметры, следующие названия и значения возможны:
'LS' — стратегия для решения промежуточных СЛАУ, строка, по умолчанию = 'chol', возможные значения:
'chol' — разложение Холецкого, эквивалентно матлабовской операции A\b;
'cg-full' — метод сопряженных градиентов, в котором операция умножения матрицы A на вектор w выполняется непосредственно;
'cg-cons' — метод сопряженных градиентов, в котором операция вида (X^TX + \lambda I)\vec{w} реализуется как \vec{w}_1 = X\vec{w},\ \vec{w}_2 = X^T\vec{w}_1,\ \vec{w}_3 = \vec{w}_2+\lambda\vec{w}.
'eps' — точность оптимизации по функции и аргументу, число, по умолчанию = 1e-5;
'max_iter' — максимальное число итераций, число, по умолчанию = 100;
'display' — режим отображения, true или false, если true, то отображаются номер итерации, текущее значение верхней границы, норма разности между весами на последней и предпоследней итерациях и др. показатели, по умолчанию = false;
ВЫХОД
w — найденное значение весов, вектор длины D;
f — значение верхней границы (совпадает с самой функцией) в точке оптимума w, число.

Обратите внимание, что точность решения СЛАУ при использовании метода сопряженных градиентов должна превышать заданную точность eps.

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

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

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

  • PDF-файл с описанием проведенных исследований;
  • Файлы min_golden.m, min_quadratic.m, min_cubic.m, min_brent.m, min_fletcher.m;
  • Набор вспомогательных файлов при необходимости.
Источник — «http://www.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_2»
Личные инструменты