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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{stop|Внимание! Текст задания находится в стадии формирования. Просьба не приступать к выполнению зада...)
Строка 12: Строка 12:
Среда реализации задания – MATLAB.
Среда реализации задания – MATLAB.
 +
 +
=== Логистическая регрессия ===
 +
==== Формулировка метода ====
 +
 +
==== Использование базисных функций ====
 +
 +
==== Использование <tex>L_1</tex>-регуляризации ====
=== Формулировка задания ===
=== Формулировка задания ===
-
Для выполнения задания необходимо:
+
* Реализовать процедуру обучения логистической регрессии с квадратичной регуляризацией с помощью трех подходов:
-
* Реализовать алгоритмы одномерной минимизации функции без производной: метод золотого сечения, метод парабол и комбинированный метод Брента;
+
*# Метод Ньютона с ограниченным шагом (damped Newton) и адаптивным подбором длины шага,
-
* Протестировать реализованные алгоритмы на следующем наборе задач оптимизации:
+
*# Метод L-BFGS с подбором длины шага через backtracking,
-
** <tex>f(x) = -5x^5+4x^4-12x^3+11x^2-2x+1</tex> на интервале [-0.5, 0.5];
+
*# Метод на основе верхней оценки Йакколы-Джордана для логистической функции, в котором на этапе решения СЛАУ используется метод сопряженных градиентов;
-
** <tex>f(x) = \ln^2(x-2) + \ln^2(10-x) - x^{0.2}</tex> на интервале [6, 9.9];
+
* Провести тестирование разработанных методов на модельных данных для различных сочетаний количества объектов и признаков, особое внимание при этом необходимо уделить случаю данных большого объема;
-
** <tex>f(x) = -3x\sin 0.75x + \exp(-2x)</tex> на интервале <tex>[0, 2\pi]</tex>;
+
* Реализовать процедуру обучения <tex>L_1</tex>-регуляризованной логистической регрессии с помощью двух подходов:
-
** <tex>f(x) = \exp(3x) + 5\exp(-2x)</tex> на интервале [0, 1];
+
*# Метод покоординатного спуска с подбором длины шага через backtracking,
-
** <tex>f(x) = 0.2x\ln x + (x-2.3)^2</tex> на интервале [0.5, 2.5];
+
*# Метод с использованием верхней оценки Йаккола-Джордана для логистической функции и квадратичной оценки для функции модуля, в котором на этапе решения СЛАУ используется метод сопряженных градиентов;
-
* Протестировать реализованные алгоритмы для задач минимизации многомодальных функций, например, на различных полиномах;
+
* Провести тестирование разработанных методов на модельных данных для различных сочетаний количества объектов и признаков, особое внимание при этом необходимо уделить ситуации, когда число признаков превосходит число объектов, и случаю данных большого объема;
-
* Реализовать метод кубических аппроксимаций (по значениям функции и производной в двух точках) и комбинированный метод Брента c производной, сравнить их работу с методами оптимизации без производной;
+
* Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен содержать, в частности, необходимые формулы для методов с использованием верхних оценок: вид оптимизируемого функционала и формулы пересчета параметров.
-
* Реализовать метод Флетчера для неточной одномерной оптимизации, протестировать метод для минимизации двухмерной функции <tex>f(x) = 0.7x_1^4-8x_1^2+6x_2^2+\cos(x_1x_2)-8x_1</tex> из точки <tex>x_0 = [-\pi, \pi]^T</tex> вдоль направлений <tex>d = [1, -1.3]^T</tex> и <tex>d = [1, -1.1]^T</tex>, сравнить работу метода Флетчера с точными методами одномерной минимизации;
+
-
* Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен содержать, в частности, количество обращений к оракулу при всех запусках итерационных процессов оптимизации.
+
=== Спецификация реализуемых функций ===
=== Спецификация реализуемых функций ===
Строка 69: Строка 74:
{|border="0"
{|border="0"
|'flag' — общий результат, число, равно 1, если достигнут оптимум с точностью eps, равно -1, если произошел выход по максимальному числу итераций;
|'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;
 
-
|-
 
-
|'display' — режим отображения, true или false, по умолчанию = false;
 
-
|-
 
-
|}
 
-
|-
 
-
|}
 
-
|-
 
-
|ВЫХОД
 
-
|-
 
-
|
 
-
{|
 
-
|alpha_min — найденное значение минимума для alpha, число;
 
-
|-
 
-
|f_min — значение функции в точке минимума, число;
 
-
|-
 
-
|status — результаты оптимизации, структура со следующими полями:
 
-
|-
 
-
|
 
-
{|border="0"
 
-
|'flag' — общий результат, число, равно 1, если достигнут неточный оптимум, равно -1, если произошел выход по максимальному числу итераций;
 
|-
|-
|'num_oracle' — количество обращений к оракулу;
|'num_oracle' — количество обращений к оракулу;
Строка 131: Строка 84:
=== Оформление задания ===
=== Оформление задания ===
-
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «[МОМО12] Задание 1. ФИО». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
+
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «[МОМО12] Задание 2. ФИО». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций.
Письмо должно содержать:
Письмо должно содержать:

Версия 23:49, 25 октября 2012

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



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


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

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

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

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

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

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

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

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

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

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

Выполненный вариант задания необходимо прислать письмом по адресу 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»
Личные инструменты