Методы оптимизации в машинном обучении (курс лекций)
Материал из MachineLearning.
(Различия между версиями)
м (→Оценки) |
м |
||
| Строка 1: | Строка 1: | ||
| - | |||
| - | |||
__NOTOC__ | __NOTOC__ | ||
| Строка 89: | Строка 87: | ||
| Сокурский || align="center"|317 || на проверке || || || || | | Сокурский || align="center"|317 || на проверке || || || || | ||
|- | |- | ||
| - | | Чистякова || align="center"|422 || align="center"|4.0 || || || | + | | Чистякова || align="center"|422 || align="center"|4.0 || || || align="center"|5 || align="center"|5 |
|- | |- | ||
| Артюхин || align="center"|517 || align="center"|4.9 || || || || | | Артюхин || align="center"|517 || align="center"|4.9 || || || || | ||
Версия 15:34, 17 декабря 2012
| Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков не только по подбору подходящего метода для своей задачи, но и по разработке своего метода оптимизации, наиболее полно учитывающего особенности конкретной задачи.
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций. |
Автор курса: Д.А. Кропотов. Вопросы и комментарии по курсу просьба оставлять на вкладке «обсуждение» к этой странице или адресовать письмом на bayesml@gmail.com. В название письма просьба добавлять [МОМО12].
Расписание на 2012 учебный год
В осеннем семестре 2012 года спецкурс читается на ВМК по понедельникам в ауд. 506, начало в 18-10.
| Дата | Название лекции | Материалы |
|---|---|---|
| 10 сентября 2012 | Введение в курс | |
| 17 сентября 2012 | Лекции не было | |
| 24 сентября 2012 | Методы одномерной минимизации | Текст (PDF, 185Кб) |
| 1 октября 2012 | Базовые методы многомерной оптимизации | Текст (PDF, 1.13Мб) |
| 8 октября 2012 | Продвинутые методы многомерной оптимизации | Текст (PDF, 667Кб) |
| 15 октября 2012 | Методы оптимизации с использованием глобальных верхних оценок | Текст (PDF, 248Кб) |
| 22 октября 2012 | Задачи оптимизации с ограничениями | |
| 29 октября 2012 | Методы внутренней точки | Текст (PDF, 241Кб) |
| 5 ноября 2012 | Лекции не было (праздничный день) | |
| 12 ноября 2012 | Примеры применения методов внутренней точки | |
| 19 ноября 2012 | Методы оптимизации для разреженных линейных моделей классификации и регрессии | Текст (PDF, 229Кб) |
| 26 ноября 2012 | Методы отсекающих плоскостей | |
| 3 декабря 2012 | Стохастическая оптимизация | |
| 10 декабря 2012 | Лекции не было | |
| 17 декабря 2012 | Экзамен | Вопросы к экзамену (PDF, 99Кб) |
Практические задания
Задание 1. Методы одномерной минимизации.
Задание 2. Методы многомерной минимизации для логистической регрессии.
Задание 3. Методы внутренней точки для линейной регрессии.
Экзамен
Экзамен состоится 17 декабря в ауд. 506, начало в 16-20. К экзамену допускаются только те студенты, кто успешно выполнил не менее одного практического задания. На экзамене при подготовке разрешается пользоваться любыми материалами.
Вопросы к экзамену + теоретический минимум (PDF, 99Кб)
Оценки
| Студент | Группа | Задание 1 | Задание 2 | Задание 3 | Экзамен | Итог |
|---|---|---|---|---|---|---|
| Сокурский | 317 | на проверке | ||||
| Чистякова | 422 | 4.0 | 5 | 5 | ||
| Артюхин | 517 | 4.9 | ||||
| Елшин | 517 | на проверке | ||||
| Зимовнов | 517 | 5.0 | 4.3 | 4.4 | 5 | |
| Кириллов | 517 | 4.0 | ||||
| Некрасов | 517 | 3.8 | ||||
| Новиков П. | 517 | 3.8 | ||||
| Соколов | 517 | 5.0 | 4.8 | 4.4 | 5 | |
| Фигурнов | 517 | на проверке | ||||
| Сайко | мех-мат | 3.6 |
Система выставления оценок за курс
В рамках курса предполагается три практических задания и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Итоговая оценка за курс получается путем взвешенного суммирования оценок за задания и экзамен с дальнейшим округлением в сторону ближайшего целого. Вес каждого задания составляет 1/3. Таким образом, если студент успешно выполнил все три практических задания, то он получает оценку за курс без экзамена. Минимально студент должен выполнить одно практические задание. В этом случае он сдает экзамен, оценка за который идет в итоговую сумму с весом 2/3. Если студент выполнил два практических задания, то он также сдает экзамен, но по облегченной схеме (меньше вопросов в билете, меньше дополнительных вопросов). В этом случае оценка за экзамен идет в итоговую сумму с весом 1/3. За каждый день просрочки при сдаче задания начисляется штраф в 0.1 балла, но не более 2 баллов.
Программа курса
Основные понятия и примеры задач
- Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
- Матричные вычисления, примеры;
- Матричные разложения, их использование для решения СЛАУ;
- Структура итерационного процесса в оптимизации, понятие оракула;
- Примеры оракулов и задач машинного обучения со «сложной» оптимизацией.
Методы одномерной оптимизации
- Минимизация функции без производной: метод золотого сечения, метод парабол;
- Гибридный метод минимизации Брента;
- Методы решения уравнения
: метод деления отрезка пополам, метод секущей;
- Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
- Поиск ограничивающего сегмента;
- Условия Голдштайна-Деккера-Флетчера для неточного решения задачи одномерной оптимизации;
- Неточные методы одномерной оптимизации, backtracking.
Методы многомерной оптимизации
- Метод покоординатного спуска;
- Методы градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, зависимость от шкалы измерений признаков;
- Метод Ньютона, подбор длины шага;
- Теоретические результаты относительно скорости сходимости градиентного спуска и метода Ньютона;
- Фазы итерационного процесса, LDL-разложение, гибридный метод Ньютона;
- Метод Levenberg-Marquardt, его использование для обучения нелинейной регрессии;
- Метод сопряженных градиентов для решения систем линейных уравнений;
- Метод сопряженных градиентов для оптимизации неквадратичных функций, зависимость от точной одномерной оптимизации;
- Квази-ньютоновские методы оптимизации: DFP, BFGS и L-BFGS;
- Соотношения между различными методами решения СЛАУ.
Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра
- Вероятностная модель линейной регрессии с различными регуляризациями: квадратичной, L1, Стьюдента;
- Идея метода оптимизации, основанного на использовании глобальных оценок, сходимость;
- Пример применения метода для обучения LASSO;
- Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностных моделей линейной регрессии;
- Построение оценок с помощью касательных и замены переменной;
- Оценка Jakkola-Jordan для логистической функции, оценки для распределений Лапласа и Стьюдента;
- Применение оценок для обучения вероятностных моделей линейной регрессии;
- Выпукло-вогнутая процедура, примеры использования.
Задачи оптимизации с ограничениями, понятие двойственности
- Векторные и матричные нормы, примеры, двойственная норма;
- Выпуклые множества и функции, сопряженная функция Фенхеля, понятие двойственности;
- Двойственная функция Лагранжа, ее связь с сопряженной функцией Фенхеля, двойственная задача оптимизации;
- Геометрическая интерпретация двойственности;
- Необходимые и достаточные условия оптимальности в задачах условной оптимизации, теорема Куна-Таккера;
- Возмущенная задача оптимизации, экономический смысл коэффициентов Лагранжа.
Методы внутренней точки
- Условия Куна-Таккера для выпуклых задач оптимизации, общая структура прямо-двойственных методов оптимизации;
- Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
- Прямо-двойственный метод Ньютона;
- Метод логарифмических барьерных функций, поиск допустимой стартовой точки;
- Прямо-двойственный метод внутренней точки;
- Использование методов внутренней точки для обучения SVM.
Разреженные методы машинного обучения
- Модели линейной/логистической регрессии с регуляризациями L1 и L2/L1;
- Понятие субградиента выпуклой функции, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации, примеры;
- Проксимальный метод;
- Метод покоординатного спуска и блочной покоординатной оптимизации;
- Метод active set на примере регрессии наименьших углов.
Методы отсекающих плоскостей
- Понятие отделяющего оракула, базовый метод отсекающих плоскостей (cutting plane);
- Надграфная форма метода отсекающих плоскостей;
- Bundle-версия метода отсекающих плоскостей, зависимость от настраиваемых параметров;
- Применение bundle-метода для задачи обучения SVM;
- Добавление эффективной процедуры одномерного поиска;
- Реализация метода с использованием параллельных вычислений и в условиях ограничений по памяти.
Стохастическая оптимизация
- Общая постановка задачи стохастической оптимизации, пример использования;
- Задачи минимизации среднего и эмпирического риска;
- Метод стохастического градиентного спуска, его отличия от метода градиентного спуска;
- Стохастический градиентный спуск как метод оптимизации и как метод обучения;
- Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS);
- Модели автокодировщика и глубинного автокодировщика, особенности процедуры обучения и использование стохастического градиентного спуска.
Литература
- Optimization for Machine Learning. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
- S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
- A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
- Yu. Nesterov. Introductory Lectures on Convex Programming, Kluwer, 2004.
- R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
- Numerical Recipes. The Art of Scientific Computing, 1992.
См. также
Курс «Байесовские методы в машинном обучении»
