Методы оптимизации в машинном обучении (курс лекций)/2018
Материал из MachineLearning.
Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности. Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
Лектор: Д.А. Кропотов
Семинарист: А.О. Родоманов
Ассистент: Н.А. Шаповалов
Занятия проходят: по понедельникам в ауд. 637, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
Инвайт в AnyTask: EyxQPxD.
Внимание! В понедельник 10 сентября занятий по курсу не будет.
Система выставления оценок по курсу
В рамках курса предполагается четыре практических задания, четыре домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Домашнее задание после срока сдачи не принимается. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла, через две недели после срока сдачи практическое задание не принимается.
Итоговая оценка за курс вычисляется с помощью округления вверх взвешенной суммы оценки за экзамен (вклад 40%), оценки за практические задания (вклад 40%) и оценки за домашние задания (вклад 20%). При этом для получения итоговой оценки 5 необходимо сдать на положительный балл все практические и все домашние задания, а также набрать на экзамене не ниже 4 баллов; для получения итоговой оценки 4 необходимо сдать любые три практических задания и любые два домашних задания; для получения итоговой оценки 3 необходимо сдать любые два практических задания и любое одно домашнее задание.
При выполнении каждого задания можно получить бонусные баллы за необязательные пункты, но при этом итоговые оценки за практическую часть курса и за домашнюю часть курса не могут превысить соответствующих максимальных оценок без учета бонусов. Например, если используется пятибальная шкала и количество (скажем, домашних) заданий равно четырем, то за счет бонусов оценки за задания могут быть следующими: 1) 5.5, 4, 4, 4; или 2) 5.5, 5, 5, 5. В первом случае итоговая оценка за домашние задания составляет 17.5, а во втором --- 20.0.
Лекции
| № п/п | Занятие | Материалы |
|---|---|---|
| 1 | Введение в курс. Классы функций в оптимизации. Скорости сходимости | (Скорости сходимости) [Nocedal-Wright, pp. 617-620] |
| 2 | Неточная одномерная оптимизация. Метод градиентного спуска, выбор длины шага. | [Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5] |
| 3 | Метод Ньютона. Способы коррекции гессиана до положительно-определённой матрицы | |
| 4 | Метод сопряженных градиентов | |
| 5 | Неточный/безгессианный метод Ньютона | |
| 6 | Квазиньютоновские методы. Метод L-BFGS | |
| 7 | Условия Каруша-Куна-Таккера. Двойственность Лагранжа. | |
| 8 | Метод внутренней точки | |
| 9 | Прямо-двойственный метод внутренней точки | |
| 10 | Негладкая оптимизация. Субградиентный метод | |
| 11 | Разреженные линейный модели. Проксимальные методы. | |
| 12 | Ускоренный градиентный метод | |
| 13 | Стохастическая оптимизация | |
| 14 | Ускоренный метод для минимизации конечных сумм (Katyusha) |
Семинары
| № п/п | Занятие | Материалы |
|---|---|---|
| 1 | Матрично-векторное дифференцирование (часть 1) | |
| 2 | Матрично-векторное дифференцирование (часть 2). Условия оптимальности. | |
| 3 | Методы градиентного спуска и Ньютона. Детали реализации и примеры работы | |
| 4 | Выпуклые множества и функции (часть 1) | |
| 5 | Выпуклые множества и функции (часть 2) | |
| 6 | Квазиньютоновские методы | |
| 7 | Условия Каруша-Куна-Таккера. Двойственность Лагранжа. | |
| 8 | Сопряженные функции. Двойственность Фенхеля. | |
| 9 | Стандартные классы выпуклых задач (LP, QP, QCQP, SOCP, SDP). Сводимость. | |
| 10 | Субдифференциальное исчисление | |
| 11 | Вычисление проекций и проксимальных отображений | |
| 12 | Техника сглаживания | |
| 13 | Рандомизированные покоординатные методы, SDCA | |
| 14 | Ускоренные рандомизированные покоординатные методы, ASDCA |
Домашние задания
Задание 1. Дифференцирование (TeX).
Литература
- J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
- A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
- Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.
- Ю.Е. Нестеров. Методы выпуклой оптимизации, МЦНМО, 2010
- S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
- D. Bertsekas. Convex Analysis and Optimization, Athena Scientific, 2003.
- Б.Т. Поляк. Введение в оптимизацию, Наука, 1983.
- J. Duchi. Introductory Lectures on Stochastic Optimization, Graduate Summer School Lectures, 2016.
- S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.
Архив
См. также
Курс «Байесовские методы в машинном обучении»
