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

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

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

Лектор: Д.А. Кропотов
Семинарист: А.О. Родоманов

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

Занятия проходят на ВМК по понедельникам в ауд. 612, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.

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

В рамках курса предполагается четыре практических задания, несколько домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. В итоговой оценке 45% составляют баллы за практические задания, 25% — баллы за домашние задания и 30% — оценка за экзамен. Для получения финального результата (0, 3, 4, 5) итоговая оценка по курсу округляется в большую сторону. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла, но суммарно не более 3 баллов.

Таблица с оценками.

Экзамен

Экзамен по курсу состоится 19 января в ауд. 508, начало в 12-00. На экзамене при подготовке билета можно пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя. Просьба обратить внимание на теоретический минимум. Незнание ответов на вопросы из теор. минимума автоматически влечёт неудовлетворительную оценку за экзамен.

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

Домашние задания

Задание 1. Скорости сходимости и дифференцирование. Срок сдачи: 12 сентября (понедельник), 10:30.
Задание 2. Задачи условной оптимизации. Срок сдачи: 31 октября (понедельник), 10:30.
Задание 3. Субградиенты. Срок сдачи: 14 ноября (понедельник), 10:30.
Задание 4. Сопряженные функции и проекции. Срок сдачи: 21 ноября (понедельник), 10:30.
Бонусное задание. Проекция на симплекс. Срок сдачи: 5 декабря (понедельник), 23:59. Выполняется по желанию.

Объявление: Все домашние задания и контрольные проверены. Если у Вас не стоит оценки (или стоит неправильная), сообщите нам об этом по e-mail.

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

Задание 1. (Вариант 1) (Вариант 2). Срок сдачи: 28 сентября (среда), 23:59. Вариант для выполнения выбирается самостоятельно.
Задание 2. Срок сдачи: 19 октября (среда), 23:59.
Задание 3. Срок сдачи: 30 ноября (среда), 23:59.
Задание 4. Срок сдачи: 28 декабря (среда), 23:59.

Расписание


Дата	Занятие	Материалы
5 сентября 2016	Введение в курс. Скорости сходимости и дифференцирование	(Скорости сходимости) [Nocedal-Wright, pp. 617-620] (Дифференцирование) [Ben-Tal-Nemirovski, Section A.6]
12 сентября 2016	Методы одномерной оптимизации. Неточная одномерная оптимизация	(Одномерная оптимизация) Текст (Неточная одномерная оптимизация) [Nocedal-Wright, pp. 30-37] + [Ben-Tal-Nemirovski, pp. 164-166]
19 сентября 2016	Базовые методы многомерной оптимизации	[Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5]
26 сентября 2016	Методы сопряженных градиентов	Презентация + [Nocedal-Wright, Chapter 5]
3 октября 2016	Неточный метод Ньютона. Автоматическое дифференцирование	(Неточный метод Ньютона) [Nocedal-Wright, pp. 184-189] (Автоматическое дифференцирование) [Nocedal-Wright, Section 8.2]
10 октября 2016	Квазиньютоновские методы. Метод L-BFGS	(Квазиньютоновские методы) [Nocedal-Wright, Section 6] (Метод L-BFGS) [Nocedal-Wright, pp. 176-180]
17 октября 2016	Задачи условной оптимизации: теория.	[Поляк, Глава 9] + [Boyd-Vandenberghe, Sections 4 and 5]
24 октября 2016	Метод Ньютона для задач с ограничениями вида равенств, метод барьеров	[Boyd-Vandenberghe, pp. 521-531, 561-571]
31 октября 2016	Прямо-двойственный метод внутренней точки	[Boyd-Vandenberghe, pp. 609-615]
7 ноября 2016	Негладкая безусловная оптимизация. Субградиентный метод	[Поляк, Разделы 5.1-5.3] + [Nesterov, Sections 3.1-3.2.3]
14 ноября 2016	Проксимальный градиентный метод. Сопряженные функции по Фенхелю	(Проксимальный градиентный метод) Слайды (Сопряженные функции) [Boyd-Vandenberghe, Section 3.3] + Слайды
21 ноября 2016	Суррогатная оптимизация	Текст
28 ноября 2016	Рандомизированные методы оптимизации: SGD, SAG, SVRG и RCDM	(SGD) Nemirovski (Sections 14.0-14.1) (SAG) Schmidt et al., 2015 (SVRG) Johnson-Zhang, 2013 + Презентация (RCDM) Nesterov, 2010
5 декабря 2016	Быстрый градиентный метод Нестерова	Нестеров, 2013 (Разделы 1.2.2 и 2.3.4) + Текст
12 декабря 2016	Доклады студентов
19 декабря 2016	Переписывание контрольных работ и разбор практических заданий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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