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

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

Версия от 15:26, 4 октября 2016; Anton.rodomanov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

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

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

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

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

Задание 1. Скорости сходимости и дифференцирование. Срок сдачи: 12 сентября (понедельник), 10:30.

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

Задание 1. (Вариант 1) (Вариант 2). Срок сдачи: 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]

Таблица оценок

Подробная таблица.

Студент	Домашние задания	Практические задания
Студент	№1	№1
Амелин Владислав	3.5
Андрейцев Антон	3.5
Викулин Всеволод	4.5
Вихрева Мария	-
Гетоева Аида	3.4
Журавлёв Вадим	3.9
Иванов Олег	4.5
Камалов Руслан	3.3
Кудрявцев Георгий	3.2
Оспанов Аят	3.7
Попов Николай	4.2
Романов Никита	3.6
Рысьмятова Анастасия	4
Садекова Таснима	2
Скробот Дмитрий	-
Стёпина Александра	4.7
Тлеубаев Адиль	2.6
Чиркова Надежда	4.9
Шаповалов Никита	5
Сендерович Никита	5
Славнов Константин	3.5
Якубовский Илья	3.4
Чабаненко Владислав	3.6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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