Методы оптимизации в машинном обучении (курс лекций)/2015
Материал из MachineLearning.
(Новая: __NOTOC__ Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а такж...) |
(+ ауд. для экзамена) |
||
(9 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
__NOTOC__ | __NOTOC__ | ||
- | Курс посвящен | + | Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности. |
- | + | ||
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций. | Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций. | ||
Строка 7: | Строка 6: | ||
== Расписание на 2015 учебный год == | == Расписание на 2015 учебный год == | ||
- | В осеннем семестре 2015 года спецкурс читается на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 607, начало в 18-10. | + | В осеннем семестре 2015 года спецкурс читается на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 607, начало в 18-10. Первое занятие — 14 сентября. |
{| class = "standard" | {| class = "standard" | ||
Строка 22: | Строка 21: | ||
|- | |- | ||
| 28 сентября 2015 | | 28 сентября 2015 | ||
- | | Методы одномерной минимизации || [[Media: | + | | Методы одномерной минимизации || [[Media:momo15_l02_show.pdf|Презентация]]<br> [[Media:MOMO12_min1d.pdf|Текст]] |
|- | |- | ||
| 5 октября 2015 | | 5 октября 2015 | ||
- | | | + | | Градиентные методы и метод Ньютона || [[Media:momo15_l03_show.pdf|Презентация]]<br> [[Media:MOMO12_minnd_basic.pdf|Текст]] |
|- | |- | ||
| 12 октября 2015 | | 12 октября 2015 | ||
- | | Метод сопряжённых градиентов || | + | | Метод сопряжённых градиентов для квадратичной функции, предобуславливание || [[Media:momo15_l04_show.pdf|Презентация]]<br> [[Media:MOMO12_minnd_advanced.pdf|Текст]] |
|- | |- | ||
| 19 октября 2015 | | 19 октября 2015 | ||
- | | | + | | Оптимизация в пространстве большой размерности: общий метод сопряжённых градиентов и неточный (безгессианный) метод Ньютона || [[Media:Momo15_l05_show.pdf|Презентация]] |
|- | |- | ||
| 26 октября 2015 | | 26 октября 2015 | ||
- | | | + | | Оптимизация в пространстве большой размерности: квазиньютоновские методы оптимизации || |
|- | |- | ||
| 2 ноября 2015 | | 2 ноября 2015 | ||
Строка 43: | Строка 42: | ||
|- | |- | ||
| 16 ноября 2015 | | 16 ноября 2015 | ||
- | | Прямо-двойственный метод внутренней точки || | + | | Прямо-двойственный метод внутренней точки || [[Media:MOMO12_ipm.pdf|Текст]] |
|- | |- | ||
| 23 ноября 2015 | | 23 ноября 2015 | ||
- | | Разреженные методы машинного обучения || | + | | Разреженные методы машинного обучения || [[Media:MOMO12_sparse_methods.pdf|Текст]] |
|- | |- | ||
| 30 ноября 2015 | | 30 ноября 2015 | ||
Строка 52: | Строка 51: | ||
|- | |- | ||
| 7 декабря 2015 | | 7 декабря 2015 | ||
- | | | + | | Суррогатная оптимизация || [[Media:MOMO12_upper_bounds.pdf|Текст]] |
|- | |- | ||
| 14 декабря 2015 | | 14 декабря 2015 | ||
- | | | + | | Методы оптимизации для глубинного обучения || |
|- | |- | ||
|} | |} | ||
Строка 62: | Строка 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>-регуляризованной линейной регрессии]] | ||
== Программа курса == | == Программа курса == | ||
Строка 70: | Строка 80: | ||
* Матричные разложения, их использование для решения СЛАУ; | * Матричные разложения, их использование для решения СЛАУ; | ||
* Структура итерационного процесса в оптимизации, понятие оракула, критерии останова; | * Структура итерационного процесса в оптимизации, понятие оракула, критерии останова; | ||
- | * Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации | + | * Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации. |
- | + | ||
=== Методы одномерной оптимизации === | === Методы одномерной оптимизации === | ||
Строка 80: | Строка 89: | ||
* Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента; | * Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента; | ||
* Поиск ограничивающего сегмента; | * Поиск ограничивающего сегмента; | ||
- | * Условия Армихо | + | * Условия Армихо и Вольфа для неточного решения задачи одномерной оптимизации; |
* Неточные методы одномерной оптимизации, backtracking. | * Неточные методы одномерной оптимизации, backtracking. | ||
Строка 87: | Строка 96: | ||
* Методы линейного поиска и доверительной области; | * Методы линейного поиска и доверительной области; | ||
* Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков; | * Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков; | ||
- | |||
* Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы; | * Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы; | ||
* Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание; | * Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание; | ||
* Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации; | * Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации; | ||
* Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента; | * Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента; | ||
- | + | * Квазиньютоновские методы оптимизации: SR1, BFGS и L-BFGS. | |
- | * Квазиньютоновские методы оптимизации: | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
=== Методы внутренней точки === | === Методы внутренней точки === | ||
- | * Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера | + | * Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера; |
* Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации; | * Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации; | ||
* Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона; | * Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона; | ||
* Прямо-двойственный метод Ньютона, неточный вариант метода; | * Прямо-двойственный метод Ньютона, неточный вариант метода; | ||
- | * Метод логарифмических барьерных функций | + | * Метод логарифмических барьерных функций; |
- | + | ||
* Прямо-двойственный метод внутренней точки; | * Прямо-двойственный метод внутренней точки; | ||
- | * | + | * Методы первой фазы. |
=== Разреженные методы машинного обучения === | === Разреженные методы машинного обучения === | ||
Строка 122: | Строка 117: | ||
* Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации; | * Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации; | ||
* Метод наискорейшего субградиентного спуска; | * Метод наискорейшего субградиентного спуска; | ||
- | * Проксимальный метод | + | * Проксимальный метод, вычисление prox-оператора для L1- и L1/L2-регуляризаторов. |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
=== Стохастическая оптимизация === | === Стохастическая оптимизация === | ||
- | |||
* Задачи минимизации среднего и эмпирического риска; | * Задачи минимизации среднего и эмпирического риска; | ||
- | * Метод стохастического градиентного спуска, две фазы итерационного процесса, использование | + | * Метод стохастического градиентного спуска, две фазы итерационного процесса, использование инерции; |
- | + | ||
* Метод SAG; | * Метод SAG; | ||
- | * Применение | + | * Комбинирование стохастической оптимизации и проксимального метода. |
+ | |||
+ | === Суррогатная оптимизация === | ||
+ | |||
+ | * Вероятностная модель логистической регрессии; | ||
+ | * Общая идея метода суррогатной оптимизации; | ||
+ | * Применение метода для стохастической оптимизации: метод MISO; | ||
+ | * Пример применения метода для обучения LASSO; | ||
+ | * Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностной модели логистической регрессии; | ||
+ | * Построение оценок с помощью касательных и замены переменной; | ||
+ | * Оценка Jaakkola-Jordan для логистической функции, её применение для обучения вероятностной модели логистической регрессии; | ||
+ | * Выпукло-вогнутая процедура, примеры использования. | ||
=== Методы оптимизации для глубинного обучения === | === Методы оптимизации для глубинного обучения === | ||
+ | * Адаптивная стратегия Левенберга-Марквардта для задачи минимизации суммы квадратов; | ||
* Модель глубинного автокодировщика; | * Модель глубинного автокодировщика; | ||
- | |||
* Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор; | * Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор; | ||
* Неточный метод Ньютона с предобуславливанием через 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. Неточный метод Ньютона для -регуляризованной логистической регрессии
Задание 2. Методы внутренней точки для -регуляризованной линейной регрессии
Программа курса
Основные понятия и примеры задач
- Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
- Матричные разложения, их использование для решения СЛАУ;
- Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
- Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации.
Методы одномерной оптимизации
- Минимизация функции без производной: метод золотого сечения, метод парабол;
- Гибридный метод минимизации Брента;
- Методы решения уравнения : метод деления отрезка пополам, метод секущей;
- Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
- Поиск ограничивающего сегмента;
- Условия Армихо и Вольфа для неточного решения задачи одномерной оптимизации;
- Неточные методы одномерной оптимизации, backtracking.
Методы многомерной оптимизации
- Методы линейного поиска и доверительной области;
- Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
- Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
- Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
- Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
- Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
- Квазиньютоновские методы оптимизации: SR1, BFGS и L-BFGS.
Методы внутренней точки
- Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера;
- Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
- Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
- Прямо-двойственный метод Ньютона, неточный вариант метода;
- Метод логарифмических барьерных функций;
- Прямо-двойственный метод внутренней точки;
- Методы первой фазы.
Разреженные методы машинного обучения
- Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
- Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
- Метод наискорейшего субградиентного спуска;
- Проксимальный метод, вычисление prox-оператора для L1- и L1/L2-регуляризаторов.
Стохастическая оптимизация
- Задачи минимизации среднего и эмпирического риска;
- Метод стохастического градиентного спуска, две фазы итерационного процесса, использование инерции;
- Метод SAG;
- Комбинирование стохастической оптимизации и проксимального метода.
Суррогатная оптимизация
- Вероятностная модель логистической регрессии;
- Общая идея метода суррогатной оптимизации;
- Применение метода для стохастической оптимизации: метод MISO;
- Пример применения метода для обучения LASSO;
- Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностной модели логистической регрессии;
- Построение оценок с помощью касательных и замены переменной;
- Оценка Jaakkola-Jordan для логистической функции, её применение для обучения вероятностной модели логистической регрессии;
- Выпукло-вогнутая процедура, примеры использования.
Методы оптимизации для глубинного обучения
- Адаптивная стратегия Левенберга-Марквардта для задачи минимизации суммы квадратов;
- Модель глубинного автокодировщика;
- Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
- Неточный метод Ньютона с предобуславливанием через L-BFGS.
Литература
- Optimization for Machine Learning. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
- J. Nocedal, S.J. Wright. Numerical Optimization. Springer, 2006.
- S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
- A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
- Б. Поляк. Введение в оптимизацию, Наука, 1983.
- Ю. Нестеров. Методы выпуклой оптимизации, МЦМНО, 2010.
- R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
- Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, 2007.
Архив
См. также
Курс «Байесовские методы в машинном обучении»