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

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

Версия от 15:33, 27 октября 2012; Kropotov (Обсуждение | вклад)

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

Внимание! Выложено второе практическое задание. Срок сдачи — 9 ноября.

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

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

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

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

В осеннем семестре 2012 года спецкурс читается на ВМК по понедельникам в ауд. 506, начало в 18-05.


Дата	Название лекции	Материалы
10 сентября 2012	Введение в курс
17 сентября 2012	Лекции не будет
24 сентября 2012	Методы одномерной минимизации	Текст (PDF, 185Кб)
1 октября 2012	Базовые методы многомерной оптимизации	Текст (PDF, 1.13Мб)
8 октября 2012	Продвинутые методы многомерной оптимизации
15 октября 2012	Методы оптимизации с использованием глобальных верхних оценок
22 октября 2012	Задачи оптимизации с ограничениями
29 октября 2012	Методы внутренней точки
5 ноября 2012	Лекции не будет (праздничный день)
12 ноября 2012	Разреженные методы машинного обучения
19 ноября 2012	Методы cutting plane и bundle
26 ноября 2012	Стохастическая оптимизация

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

Задание 1. Методы одномерной минимизации.
Задание 2. Методы многомерной минимизации в применении к логистической регрессии.

Оценки

Студент	Группа	Задание 1
Сокурский	317	на проверке
Артюхин	517	на проверке
Елшин	517	на проверке
Зимовнов	517	на проверке
Кириллов	517	на проверке
Некрасов	517	на проверке
Соколов	517	на проверке
Фигурнов	517	на проверке
Сайко	мех-мат	на проверке

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод внутренней точки;
Прямодвойственный метод внутренней точки;
Быстрые алгоритмы умножения матрицы на вектор и их использование в методе внутренней точки.

Разреженные методы машинного обучения, L1-регуляризация

Примеры задач и виды разреженных регуляризаторов;
Проксимальный метод;
Метод покоординатного спуска и блочной покоординатной оптимизации;
Метод внутренней точки.

Методы cutting plane и bundle

Субградиент выпуклой функции;
Метод отсекающей плоскости и его bundle расширение;
Примеры задач распознавания, сводящихся к оптимизации регуляризованных функционалов;
Использование bundle метода для задач оптимизации регуляризованных функционалов;
Добавление одномерного поиска.