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

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

Версия от 10:08, 19 октября 2015; Kropotov (Обсуждение | вклад)

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

Выложена формулировка первого практического задания. Срок сдачи — 4 ноября (среда).

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

Автор курса: Д.А. Кропотов. Вопросы и комментарии по курсу просьба адресовать письмом на 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 баллов. Для допуска к экзамену необходимо предварительно сдать на положительную оценку оба задания.

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

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

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

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

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

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

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

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

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

Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра

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

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

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

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

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

Методы отсекающих плоскостей

Понятие отделяющего оракула, базовый метод отсекающих плоскостей (cutting plane);
Надграфная форма метода отсекающих плоскостей;
Bundle-версия метода отсекающих плоскостей, зависимость от настраиваемых параметров;
Применение bundle-метода для задачи обучения SVM;
Добавление эффективной процедуры одномерного поиска;
Реализация метода с использованием параллельных вычислений и в условиях ограничений по памяти.

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

Общая постановка задачи стохастической оптимизации, пример использования;
Задачи минимизации среднего и эмпирического риска;
Метод стохастического градиентного спуска, две фазы итерационного процесса, использование усреднения и инерции;
Стохастический градиентный спуск как метод оптимизации и как метод обучения;
Метод SAG;
Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS);

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

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