Методы оптимизации в машинном обучении (курс лекций)/2016
Материал из MachineLearning.
Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности. Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
Лектор: Д.А. Кропотов
Семинарист: А.О. Родоманов
Вопросы и комментарии по курсу просьба адресовать письмом на bayesml@gmail.com. В название письма просьба добавлять [ВМК МОМО16].
Занятия проходят на ВМК по понедельникам в ауд. 612, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
Система выставления оценок по курсу
В рамках курса предполагается четыре практических задания, несколько домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. В итоговой оценке 45% составляют баллы за практические задания, 25% — баллы за домашние задания и 30% — оценка за экзамен. Для получения финального результата (0, 3, 4, 5) итоговая оценка по курсу округляется в большую сторону. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла, но суммарно не более 3 баллов.
Домашние задания
- Задание 1. Скорости сходимости и дифференцирование. Срок сдачи: 12 сентября (понедельник), 10:30.
- Задание 2. Задачи условной оптимизации. Срок сдачи: 31 октября (понедельник), 10:30.
- Задание 3. Субградиенты. Срок сдачи: 14 ноября (понедельник), 10:30.
- Задание 4. Сопряженные функции и проекции. Срок сдачи: 21 ноября (понедельник), 10:30.
- Бонусное задание. Проекция на симплекс. Срок сдачи: 5 декабря (понедельник), 23:59. Выполняется по желанию.
Практические задания
- Задание 1. (Вариант 1) (Вариант 2). Срок сдачи: 28 сентября (среда), 23:59. Вариант для выполнения выбирается самостоятельно.
- Задание 2. Срок сдачи: 19 октября (среда), 23:59.
- Задание 3. Срок сдачи: 30 ноября (среда), 23:59.
- Задание 4. Срок сдачи: 28 декабря (среда), 23:59.
Расписание
| Дата | Занятие | Материалы |
|---|---|---|
| 5 сентября 2016 | Введение в курс. Скорости сходимости и дифференцирование | (Скорости сходимости) [Nocedal-Wright, pp. 617-620] (Дифференцирование) [Ben-Tal-Nemirovski, Section A.6] |
| 12 сентября 2016 | Методы одномерной оптимизации. Неточная одномерная оптимизация | (Одномерная оптимизация) Текст (Неточная одномерная оптимизация) [Nocedal-Wright, pp. 30-37] + [Ben-Tal-Nemirovski, pp. 164-166] |
| 19 сентября 2016 | Базовые методы многомерной оптимизации | [Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5] |
| 26 сентября 2016 | Методы сопряженных градиентов | Презентация + [Nocedal-Wright, Chapter 5] |
| 3 октября 2016 | Неточный метод Ньютона. Автоматическое дифференцирование | (Неточный метод Ньютона) [Nocedal-Wright, pp. 184-189] (Автоматическое дифференцирование) [Nocedal-Wright, Section 8.2] |
| 10 октября 2016 | Квазиньютоновские методы. Метод L-BFGS | (Квазиньютоновские методы) [Nocedal-Wright, Section 6] (Метод L-BFGS) [Nocedal-Wright, pp. 176-180] |
| 17 октября 2016 | Задачи условной оптимизации: теория. | [Поляк, Глава 9] + [Boyd-Vandenberghe, Sections 4 and 5] |
| 24 октября 2016 | Метод Ньютона для задач с ограничениями вида равенств, метод барьеров | [Boyd-Vandenberghe, pp. 521-531, 561-571] |
| 31 октября 2016 | Прямо-двойственный метод внутренней точки | [Boyd-Vandenberghe, pp. 609-615] |
| 7 ноября 2016 | Негладкая безусловная оптимизация. Субградиентный метод | [Поляк, Разделы 5.1-5.3] + [Nesterov, Sections 3.1-3.2.3] |
| 14 ноября 2016 | Проксимальный градиентный метод. Сопряженные функции по Фенхелю | (Проксимальный градиентный метод) Слайды (Сопряженные функции) [Boyd-Vandenberghe, Section 3.3] + Слайды |
| 21 ноября 2016 | Суррогатная оптимизация | Текст |
| 28 ноября 2016 | Рандомизированные методы оптимизации: SGD, SAG, SVRG и RCDM | (SGD) Nemirovski (Sections 14.0-14.1) (SAG) Schmidt et al., 2015 (SVRG) Johnson-Zhang, 2013 + Презентация (RCDM) Nesterov, 2010 |
Программа курса
Основные понятия и примеры задач
- Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
- Матричные разложения, их использование для решения СЛАУ;
- Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
- Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации.
Методы одномерной оптимизации
- Минимизация функции без производной: метод золотого сечения, метод парабол;
- Гибридный метод минимизации Брента;
- Методы решения уравнения
: метод деления отрезка пополам, метод секущей;
- Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
- Поиск ограничивающего сегмента;
- Условия Армихо и Вольфа для неточного решения задачи одномерной оптимизации;
- Неточные методы одномерной оптимизации, backtracking.
Методы многомерной оптимизации
- Методы линейного поиска и доверительной области;
- Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
- Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
- Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
- Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
- Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
- Квазиньютоновские методы оптимизации: SR1, BFGS и L-BFGS.
Методы внутренней точки
- Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера;
- Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
- Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
- Прямо-двойственный метод Ньютона, неточный вариант метода;
- Метод логарифмических барьерных функций;
- Прямо-двойственный метод внутренней точки;
- Методы первой фазы.
Разреженные методы машинного обучения
- Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
- Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
- Метод наискорейшего субградиентного спуска;
- Проксимальный метод, вычисление prox-оператора для L1- и L1/L2-регуляризаторов.
Стохастическая оптимизация
- Задачи минимизации среднего и эмпирического риска;
- Метод стохастического градиентного спуска, две фазы итерационного процесса, использование инерции;
- Метод SAG;
- Комбинирование стохастической оптимизации и проксимального метода.
Суррогатная оптимизация
- Вероятностная модель логистической регрессии;
- Общая идея метода суррогатной оптимизации;
- Применение метода для стохастической оптимизации: метод MISO;
- Пример применения метода для обучения LASSO;
- Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностной модели логистической регрессии;
- Построение оценок с помощью касательных и замены переменной;
- Оценка Jaakkola-Jordan для логистической функции, её применение для обучения вероятностной модели логистической регрессии;
- Выпукло-вогнутая процедура, примеры использования.
Методы оптимизации для глубинного обучения
- Адаптивная стратегия Левенберга-Марквардта для задачи минимизации суммы квадратов;
- Модель глубинного автокодировщика;
- Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
- Неточный метод Ньютона с предобуславливанием через L-BFGS.
Литература
- S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.
- J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
- A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
- Б. Поляк. Введение в оптимизацию, Наука, 1983.
- S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
- Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.
- R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
- A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
- W. Press et al.. Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, 2007.
Архив
См. также
Курс «Байесовские методы в машинном обучении»
