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

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

(Различия между версиями)
Перейти к: навигация, поиск
м
(+ ауд. для экзамена)
 
(7 промежуточных версий не показаны.)
Строка 6: Строка 6:
== Расписание на 2015 учебный год ==
== Расписание на 2015 учебный год ==
-
В осеннем семестре 2015 года спецкурс читается на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 607, начало в 18-10. Первое занятия — 14 сентября.
+
В осеннем семестре 2015 года спецкурс читается на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 607, начало в 18-10. Первое занятие — 14 сентября.
{| class = "standard"
{| class = "standard"
Строка 21: Строка 21:
|-
|-
| 28 сентября 2015
| 28 сентября 2015
-
| Методы одномерной минимизации || [[Media:MOMO14_min1d.pdf|Конспект]]
+
| Методы одномерной минимизации || [[Media:momo15_l02_show.pdf|Презентация]]<br> [[Media:MOMO12_min1d.pdf|Текст]]
|-
|-
| 5&nbsp;октября&nbsp;2015
| 5&nbsp;октября&nbsp;2015
-
| Градиентные методы и метод Ньютона ||
+
| Градиентные методы и метод Ньютона || [[Media:momo15_l03_show.pdf|Презентация]]<br> [[Media:MOMO12_minnd_basic.pdf|Текст]]
|-
|-
| 12&nbsp;октября&nbsp;2015
| 12&nbsp;октября&nbsp;2015
-
| Метод сопряжённых градиентов, предобуславливание ||
+
| Метод сопряжённых градиентов для квадратичной функции, предобуславливание || [[Media:momo15_l04_show.pdf|Презентация]]<br> [[Media:MOMO12_minnd_advanced.pdf|Текст]]
|-
|-
| 19&nbsp;октября&nbsp;2015
| 19&nbsp;октября&nbsp;2015
-
| Неточный (безгессианный) метод Ньютона и квазиньютоновские методы оптимизации ||
+
| Оптимизация в пространстве большой размерности: общий метод сопряжённых градиентов и неточный (безгессианный) метод Ньютона || [[Media:Momo15_l05_show.pdf|Презентация]]
|-
|-
| 26&nbsp;октября&nbsp;2015
| 26&nbsp;октября&nbsp;2015
-
| Методы оптимизации с использованием глобальных верхних оценок ||
+
| Оптимизация в пространстве большой размерности: квазиньютоновские методы оптимизации ||
|-
|-
| 2&nbsp;ноября&nbsp;2015
| 2&nbsp;ноября&nbsp;2015
Строка 42: Строка 42:
|-
|-
| 16&nbsp;ноября&nbsp;2015
| 16&nbsp;ноября&nbsp;2015
-
| Прямо-двойственный метод внутренней точки ||
+
| Прямо-двойственный метод внутренней точки || [[Media:MOMO12_ipm.pdf|Текст]]
|-
|-
| 23&nbsp;ноября&nbsp;2015
| 23&nbsp;ноября&nbsp;2015
-
| Разреженные методы машинного обучения ||
+
| Разреженные методы машинного обучения || [[Media:MOMO12_sparse_methods.pdf|Текст]]
|-
|-
| 30&nbsp;ноября&nbsp;2015
| 30&nbsp;ноября&nbsp;2015
Строка 51: Строка 51:
|-
|-
| 7&nbsp;декабря&nbsp;2015
| 7&nbsp;декабря&nbsp;2015
-
| Методы оптимизации для глубинного обучения ||
+
| Суррогатная оптимизация || [[Media:MOMO12_upper_bounds.pdf|Текст]]
|-
|-
| 14&nbsp;декабря&nbsp;2015
| 14&nbsp;декабря&nbsp;2015
-
| Экзамен ||
+
| Методы оптимизации для глубинного обучения ||
|-
|-
|}
|}
Строка 61: Строка 61:
В рамках курса предполагается два практических задания и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Итоговая оценка за курс получается путем взвешенного суммирования оценок за задания и экзамен с дальнейшим округлением в сторону ближайшего целого. Вес каждого задания составляет 1/3. За каждый день просрочки при сдаче задания начисляется штраф в 0.1 балла, но не более 2 баллов. Для допуска к экзамену необходимо предварительно сдать на положительную оценку оба задания.
В рамках курса предполагается два практических задания и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Итоговая оценка за курс получается путем взвешенного суммирования оценок за задания и экзамен с дальнейшим округлением в сторону ближайшего целого. Вес каждого задания составляет 1/3. За каждый день просрочки при сдаче задания начисляется штраф в 0.1 балла, но не более 2 баллов. Для допуска к экзамену необходимо предварительно сдать на положительную оценку оба задания.
 +
 +
== Экзамен ==
 +
Первая итерация экзамена по спецкурсу состоится 21 декабря (понедельник) в ауд. 678, начало в 16-20. Вторая итерация состоится 21 января (четверг) в ауд. 682, начало в 12-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами.
 +
 +
[[Media:MOMO15_exam_questions.pdf|Вопросы к экзамену]]
 +
 +
== Практические задания ==
 +
 +
Задание 1. [[Media:MOMO15_assignment1.pdf|Неточный метод Ньютона для <tex>l_2</tex>-регуляризованной логистической регрессии]]
 +
 +
Задание 2. [[Media:MOMO15_assignment2.pdf|Методы внутренней точки для <tex>l_1</tex>-регуляризованной линейной регрессии]]
== Программа курса ==
== Программа курса ==
Строка 69: Строка 80:
* Матричные разложения, их использование для решения СЛАУ;
* Матричные разложения, их использование для решения СЛАУ;
* Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
* Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
-
* Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации;
+
* Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации.
-
* Примеры оракулов и задач машинного обучения со «сложной» оптимизацией.
+
=== Методы одномерной оптимизации ===
=== Методы одномерной оптимизации ===
Строка 79: Строка 89:
* Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
* Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
* Поиск ограничивающего сегмента;
* Поиск ограничивающего сегмента;
-
* Условия Армихо-Голдштайна-Вольфа для неточного решения задачи одномерной оптимизации;
+
* Условия Армихо и Вольфа для неточного решения задачи одномерной оптимизации;
* Неточные методы одномерной оптимизации, backtracking.
* Неточные методы одномерной оптимизации, backtracking.
Строка 86: Строка 96:
* Методы линейного поиска и доверительной области;
* Методы линейного поиска и доверительной области;
* Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
* Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
-
* Сходимость общего метода линейного поиска с неточной одномерной минимизацией;
 
* Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
* Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
* Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
* Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
* Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
* Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
* Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
* Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
-
* Применение неточного метода Ньютона для обучения линейного классификатора и нелинейной регрессии, аппроксимация Гаусса-Ньютона и адаптивная стратегия Levenberg-Marquardt;
+
* Квазиньютоновские методы оптимизации: SR1, BFGS и L-BFGS.
-
* Квазиньютоновские методы оптимизации: DFP, BFGS и L-BFGS;
+
-
 
+
-
=== Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра ===
+
-
 
+
-
* Вероятностная модель линейной регрессии с различными регуляризациями: квадратичной, L1, Стьюдента;
+
-
* Идея метода оптимизации, основанного на использовании глобальных оценок, сходимость;
+
-
* Пример применения метода для обучения LASSO;
+
-
* Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностных моделей линейной регрессии;
+
-
* Построение оценок с помощью касательных и замены переменной;
+
-
* Оценка Jaakkola-Jordan для логистической функции, оценки для распределений Лапласа и Стьюдента;
+
-
* Применение оценок для обучения вероятностных моделей линейной регрессии;
+
-
* Выпукло-вогнутая процедура, примеры использования.
+
=== Методы внутренней точки ===
=== Методы внутренней точки ===
-
* Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера и условия Джона, соотношение между ними;
+
* Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера;
* Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
* Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
* Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
* Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
* Прямо-двойственный метод Ньютона, неточный вариант метода;
* Прямо-двойственный метод Ньютона, неточный вариант метода;
-
* Метод логарифмических барьерных функций, поиск допустимой стартовой точки;
+
* Метод логарифмических барьерных функций;
-
* Методы первой фазы;
+
* Прямо-двойственный метод внутренней точки;
* Прямо-двойственный метод внутренней точки;
-
* Использование методов внутренней точки для обучения SVM.
+
* Методы первой фазы.
=== Разреженные методы машинного обучения ===
=== Разреженные методы машинного обучения ===
Строка 121: Строка 117:
* Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
* Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
* Метод наискорейшего субградиентного спуска;
* Метод наискорейшего субградиентного спуска;
-
* Проксимальный метод;
+
* Проксимальный метод, вычисление prox-оператора для L1- и L1/L2-регуляризаторов.
-
* Метод покоординатного спуска и блочной покоординатной оптимизации.
+
-
 
+
-
=== Методы отсекающих плоскостей ===
+
-
 
+
-
* Понятие отделяющего оракула, базовый метод отсекающих плоскостей (cutting plane);
+
-
* Надграфная форма метода отсекающих плоскостей;
+
-
* Bundle-версия метода отсекающих плоскостей, зависимость от настраиваемых параметров;
+
-
* Применение bundle-метода для задачи обучения SVM;
+
-
* Добавление эффективной процедуры одномерного поиска;
+
-
* Реализация метода с использованием параллельных вычислений и в условиях ограничений по памяти.
+
=== Стохастическая оптимизация ===
=== Стохастическая оптимизация ===
-
* Общая постановка задачи стохастической оптимизации, пример использования;
 
* Задачи минимизации среднего и эмпирического риска;
* Задачи минимизации среднего и эмпирического риска;
-
* Метод стохастического градиентного спуска, две фазы итерационного процесса, использование усреднения и инерции;
+
* Метод стохастического градиентного спуска, две фазы итерационного процесса, использование инерции;
-
* Стохастический градиентный спуск как метод оптимизации и как метод обучения;
+
* Метод SAG;
* Метод SAG;
-
* Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS);
+
* Комбинирование стохастической оптимизации и проксимального метода.
 +
 
 +
=== Суррогатная оптимизация ===
 +
 
 +
* Вероятностная модель логистической регрессии;
 +
* Общая идея метода суррогатной оптимизации;
 +
* Применение метода для стохастической оптимизации: метод MISO;
 +
* Пример применения метода для обучения LASSO;
 +
* Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностной модели логистической регрессии;
 +
* Построение оценок с помощью касательных и замены переменной;
 +
* Оценка Jaakkola-Jordan для логистической функции, её применение для обучения вероятностной модели логистической регрессии;
 +
* Выпукло-вогнутая процедура, примеры использования.
=== Методы оптимизации для глубинного обучения ===
=== Методы оптимизации для глубинного обучения ===
 +
* Адаптивная стратегия Левенберга-Марквардта для задачи минимизации суммы квадратов;
* Модель глубинного автокодировщика;
* Модель глубинного автокодировщика;
-
* Стандартный подход к глубинному обучению: стохастический градиент + мини-батчи + предобучение + drop-out;
 
* Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
* Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
* Неточный метод Ньютона с предобуславливанием через L-BFGS.
* Неточный метод Ньютона с предобуславливанием через L-BFGS.

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

Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности. Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.

Автор курса: Д.А. Кропотов. Вопросы и комментарии по курсу просьба адресовать письмом на bayesml@gmail.com. В название письма просьба добавлять [МОМО15].

Расписание на 2015 учебный год

В осеннем семестре 2015 года спецкурс читается на ВМК по понедельникам в ауд. 607, начало в 18-10. Первое занятие — 14 сентября.

Дата Название лекции Материалы
14 сентября 2015 Введение в курс
21 сентября 2015 Лекции не будет
28 сентября 2015 Методы одномерной минимизации Презентация
Текст
5 октября 2015 Градиентные методы и метод Ньютона Презентация
Текст
12 октября 2015 Метод сопряжённых градиентов для квадратичной функции, предобуславливание Презентация
Текст
19 октября 2015 Оптимизация в пространстве большой размерности: общий метод сопряжённых градиентов и неточный (безгессианный) метод Ньютона Презентация
26 октября 2015 Оптимизация в пространстве большой размерности: квазиньютоновские методы оптимизации
2 ноября 2015 Задачи оптимизации с ограничениями, метод Ньютона для задач с ограничениями вида равенства
9 ноября 2015 Прямо-двойственный метод Ньютона и метод логарифмических барьеров
16 ноября 2015 Прямо-двойственный метод внутренней точки Текст
23 ноября 2015 Разреженные методы машинного обучения Текст
30 ноября 2015 Стохастическая оптимизация
7 декабря 2015 Суррогатная оптимизация Текст
14 декабря 2015 Методы оптимизации для глубинного обучения

Система выставления оценок за курс

В рамках курса предполагается два практических задания и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Итоговая оценка за курс получается путем взвешенного суммирования оценок за задания и экзамен с дальнейшим округлением в сторону ближайшего целого. Вес каждого задания составляет 1/3. За каждый день просрочки при сдаче задания начисляется штраф в 0.1 балла, но не более 2 баллов. Для допуска к экзамену необходимо предварительно сдать на положительную оценку оба задания.

Экзамен

Первая итерация экзамена по спецкурсу состоится 21 декабря (понедельник) в ауд. 678, начало в 16-20. Вторая итерация состоится 21 января (четверг) в ауд. 682, начало в 12-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами.

Вопросы к экзамену

Практические задания

Задание 1. Неточный метод Ньютона для l_2-регуляризованной логистической регрессии

Задание 2. Методы внутренней точки для l_1-регуляризованной линейной регрессии

Программа курса

Основные понятия и примеры задач

  • Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
  • Матричные разложения, их использование для решения СЛАУ;
  • Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
  • Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации.

Методы одномерной оптимизации

  • Минимизация функции без производной: метод золотого сечения, метод парабол;
  • Гибридный метод минимизации Брента;
  • Методы решения уравнения f^\prime(x)=0: метод деления отрезка пополам, метод секущей;
  • Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
  • Поиск ограничивающего сегмента;
  • Условия Армихо и Вольфа для неточного решения задачи одномерной оптимизации;
  • Неточные методы одномерной оптимизации, backtracking.

Методы многомерной оптимизации

  • Методы линейного поиска и доверительной области;
  • Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
  • Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
  • Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
  • Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
  • Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
  • Квазиньютоновские методы оптимизации: SR1, BFGS и L-BFGS.

Методы внутренней точки

  • Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера;
  • Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
  • Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
  • Прямо-двойственный метод Ньютона, неточный вариант метода;
  • Метод логарифмических барьерных функций;
  • Прямо-двойственный метод внутренней точки;
  • Методы первой фазы.

Разреженные методы машинного обучения

  • Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
  • Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
  • Метод наискорейшего субградиентного спуска;
  • Проксимальный метод, вычисление prox-оператора для L1- и L1/L2-регуляризаторов.

Стохастическая оптимизация

  • Задачи минимизации среднего и эмпирического риска;
  • Метод стохастического градиентного спуска, две фазы итерационного процесса, использование инерции;
  • Метод SAG;
  • Комбинирование стохастической оптимизации и проксимального метода.

Суррогатная оптимизация

  • Вероятностная модель логистической регрессии;
  • Общая идея метода суррогатной оптимизации;
  • Применение метода для стохастической оптимизации: метод MISO;
  • Пример применения метода для обучения LASSO;
  • Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностной модели логистической регрессии;
  • Построение оценок с помощью касательных и замены переменной;
  • Оценка Jaakkola-Jordan для логистической функции, её применение для обучения вероятностной модели логистической регрессии;
  • Выпукло-вогнутая процедура, примеры использования.

Методы оптимизации для глубинного обучения

  • Адаптивная стратегия Левенберга-Марквардта для задачи минимизации суммы квадратов;
  • Модель глубинного автокодировщика;
  • Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
  • Неточный метод Ньютона с предобуславливанием через L-BFGS.

Литература

  1. Optimization for Machine Learning. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
  2. J. Nocedal, S.J. Wright. Numerical Optimization. Springer, 2006.
  3. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
  4. A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
  5. Б. Поляк. Введение в оптимизацию, Наука, 1983.
  6. Ю. Нестеров. Методы выпуклой оптимизации, МЦМНО, 2010.
  7. R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
  8. Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, 2007.

Архив

2014 год

2012 год

См. также

Курс «Графические модели»

Курс «Байесовские методы в машинном обучении»

Спецсеминар «Байесовские методы машинного обучения»

Математические методы прогнозирования (кафедра ВМиК МГУ)

Источник — «http://www.recognition.su/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/2015»