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

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

Версия от 15:24, 21 августа 2014; Kropotov (Обсуждение | вклад)

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

Страница курса находится в стадии разработки. Архив 2012 года находится здесь.

Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков не только по подбору подходящего метода для своей задачи, но и по разработке своего метода оптимизации, наиболее полно учитывающего особенности конкретной задачи.

Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.

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

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

В осеннем семестре 2014 года спецкурс читается на ВМК по ??? в ауд. ???, начало в ???.


Дата	Название лекции	Материалы
?? сентября 2014	Введение в курс

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

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

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

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

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

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

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

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

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

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

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

Задачи оптимизации с ограничениями, понятие двойственности

Векторные и матричные нормы, примеры, двойственная норма;
Выпуклые множества и функции, сопряженная функция Фенхеля, понятие двойственности;
Двойственная функция Лагранжа, ее связь с сопряженной функцией Фенхеля, двойственная задача оптимизации;
Геометрическая интерпретация двойственности;
Необходимые и достаточные условия оптимальности в задачах условной оптимизации, теорема Куна-Таккера;
Возмущенная задача оптимизации, экономический смысл коэффициентов Лагранжа.

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

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

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

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

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

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

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

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