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

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

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

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

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

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

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

Оценки

Студент	Группа	Задание 1
Сокурский	317	на проверке
Артюхин	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.

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

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

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

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

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

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

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

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

Методы cutting plane и bundle

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