Методы оптимизации (курс лекций)
Материал из MachineLearning.
(→Семинары) |
|||
(7 промежуточных версий не показаны.) |
Текущая версия
Методы оптимизации лежат в основе решения многих задач компьютерных наук. Например, в машинном обучении задачу оптимизации необходимо решать каждый раз при настройке какой-то модели алгоритмов по данным. Причём от эффективности решения соответствующей задачи оптимизации зависит практическая применимость самого метода машинного обучения. Данный курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.
Занятия проходят на ФКН ВШЭ.
Лектор: Кропотов Дмитрий Александрович. Лекции проходят по вторникам в ауд. 622 с 13:40 до 15:00.
Семинаристы:
Группа | Семинарист | Расписание | Почта для ДЗ |
---|---|---|---|
141 (МОП) | Родоманов Антон Олегович | вторник, 15:10 – 16:30, ауд. 513 | opt.homework+141@gmail.com |
142 (МОП) | Хальман Михаил Анатольевич | вторник, 15:10 – 16:30, ауд. 501 | opt.homework+142@gmail.com |
145 (РС) | Дойков Никита Владимирович | вторник, 15:10 – 16:30, ауд. 503 | opt.homework+145@gmail.com |
Система выставления оценок по курсу в 3-м модуле
- В рамках курса в 3-м модуле (непрерывная оптимизация) предполагается три практических задания, четыре домашних заданий и коллоквиум. Каждое задание и коллоквиум оцениваются по десятибалльной шкале.
- В оценке за модуль 50% составляют баллы за домашние задания и 50% – баллы за практические задания. Для получения финального результата (0–10) оценка округляется в большую сторону.
- Сдача коллоквиума является необязательной и позволяет получить до 2 дополнительных баллов в оценку за модуль (оценка за коллоквиум берётся с весом 0.2).
- Оценка за модуль не может быть больше, чем 10 баллов.
Формирование итоговой оценки по курсу по итогам 3-го и 4-го модулей
- За 3-й модуль выставляется оценка «Накопленная_непрерывная» как описано выше.
- За 4-й модуль выставляется оценка «Накопленная_дискретная» и проводится экзамен. На экзамене будет спрашиваться только материал 4-го модуля (дискретная оптимизация).
- Итоговая оценка по курсу вычисляется по формуле:
- «Накопленная_итоговая» = 0.625 * «Накопленная_непрерывная» + 0.375 * «Накопленная_дискретная»
- «Итоговая_оценка» = 0.8 * «Накопленная_итоговая» + 0.2 * «Экзамен»
- При вычислении итоговой оценки проводится округление к ближайшему целому (.5 округляется к единице)
Правила сдачи заданий
В рамках курса предполагается сдача нескольких домашних и практических заданий. Домашнее задание сдаётся к началу очередного семинара на листочках или (по согласованию с семинаристом) по почте в виде скана или pdf-файла. Домашние задания после срока сдачи не принимаются. Практические задания сдаются по почте. Эти задания могут быть присланы после срока сдачи, при этом начисляется штраф из расчёта 0.2 балла в день, но суммарно не более 6 баллов.
Все домашние и практические задания выполняются самостоятельно. Если задание выполнялось сообща или использовались какие-либо сторонние коды и материалы, то об этом должно быть написано в отчёте. В противном случае «похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) будут сурово наказаны.
Лекции
№ п/п | Дата | Занятие | Материалы |
---|---|---|---|
1 | 10 января 2017 | Введение в курс. Необходимое условие экстремума. Оракулы, скорости сходимости итерационных процессов. | |
2 | 17 января 2017 | Точная одномерная оптимизация. | |
3 | 24 января 2017 | Неточная одномерная оптимизация. Классы функций для оптимизации. Метод градиентного спуска. | |
4 | 31 января 2017 | Матричные разложения и их использование для решения СЛАУ. Метод Ньютона для выпуклых и невыпуклых задач. | |
5 | 7 февраля 2017 | Линейный метод сопряжённых градиентов. | |
6 | 14 февраля 2017 | Неточный метод Ньютона. Разностные производные. | |
7 | 21 февраля 2017 | Квазиньютоновские методы. Метод L-BFGS. | |
8 | 28 февраля 2017 | Задачи условной оптимизации: условия ККТ. | |
9 | 7 марта 2017 | Выпуклые задачи оптимизации. Двойственность. Метод барьеров. | |
10 | 14 марта 2017 | Негладкая безусловная оптимизация. Субградиентный метод. Проксимальные методы. | |
11 | 21 марта 2017 | Стохастическая оптимизация. |
Семинары
№ п/п | Дата | Занятие | Материалы |
---|---|---|---|
1 | 10 января 2017 | Скорости сходимости. Матричные вычисления. | Конспект |
2 | 17 января 2017 | Производные и условия оптимальности. Теория | Конспект |
3 | 24 января 2017 | Производные и условия оптимальности. Решение задач | Конспект |
4 | 31 января 2017 | Методы градиентного спуска и Ньютона | Конспект |
5 | 7 февраля 2017 | Методы градиентного спуска, Ньютона и сопряженных градиентов. Подготовка к практическому заданию 1 | Презентация |
6 | 14 февраля 2017 | Выпуклые множества и функции | Конспект |
7 | 21 февраля 2017 | Усеченный метод Ньютона. Квазиньютоновские методы | Конспект |
8 | 28 февраля 2017 | Условная оптимизация. Условия ККТ. Эквивалентные преобразования задач. | Конспект |
9 | 7 марта 2017 | Стандартные классы выпуклых задач и двойственность. | Конспект |
10 | 14 марта 2017 | Методы внутренней точки. | - |
11 | 21 марта 2017 | Субградиенты и проксимальные операторы. | - |
Домашние задания
Задание 1. Скорости сходимости и матричные вычисления. Срок сдачи: 17 января 2017 (на семинаре).
Задание 2. Производные и условия оптимальности. Срок сдачи: 31 января 2017 (на семинаре).
Задание 3. Выпуклые множества и функции. Срок сдачи: 22 февраля 2017 (23:59).
Задание 4. Условная оптимизация. Срок сдачи: 22 марта 2017 (23:59).
Практические задания
Задание 1. Методы градиентного спуска и Ньютона. Срок сдачи: 22 февраля 2017 (23:59).
Задание 2. Продвинутые методы безусловной оптимизации. Срок сдачи: 9 марта 2017 (23:59).
Задание 3. Негладкая и условная оптимизация. Срок сдачи: 7 апреля 2017 (23:59).
Литература
- J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
- S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
- S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.
- A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
- Б. Поляк. Введение в оптимизацию, Наука, 1983.
- 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.