Методы оптимизации (курс лекций)
Материал из MachineLearning.
(→Семинары) |
(→Семинары) |
||
Строка 122: | Строка 122: | ||
| Выпуклые множества и функции || [[Media:MO17_seminar6.pdf|Конспект]] | | Выпуклые множества и функции || [[Media:MO17_seminar6.pdf|Конспект]] | ||
|- | |- | ||
- | | align="center"| | + | | align="center"|7 |
| 21 февраля 2017 | | 21 февраля 2017 | ||
| Метод сопряженных градиентов, неточный метод Ньютона и L-BFGS. || - | | Метод сопряженных градиентов, неточный метод Ньютона и L-BFGS. || - |
Версия 23:34, 28 февраля 2017
Методы оптимизации лежат в основе решения многих задач компьютерных наук. Например, в машинном обучении задачу оптимизации необходимо решать каждый раз при настройке какой-то модели алгоритмов по данным. Причём от эффективности решения соответствующей задачи оптимизации зависит практическая применимость самого метода машинного обучения. Данный курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.
Занятия проходят на ФКН ВШЭ.
Лектор: Кропотов Дмитрий Александрович. Лекции проходят по вторникам в ауд. 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-м модуле
- В рамках курса предполагается три практических задания, четыре домашних заданий и экзамен. Каждое задание и экзамен оцениваются по десятибалльной шкале.
- В итоговой оценке 50% составляют баллы за домашние задания и 50% – баллы за практические задания. Для получения финального результата (0, 4–10) итоговая оценка по курсу округляется в большую сторону.
- Сдача экзамена является необязательной и позволяет получить до 2 дополнительных баллов в итоговую оценку.
- Для получения итоговой оценки >= 8 баллов необходимо сдать все домашние и практические задания на положительный балл, для получения итоговой оценки >= 6 баллов необходимо сдать не менее двух практических и трех домашних заданий, для получения итоговой оценки >= 4 баллов необходимо сдать не менее одного практического и двух домашних заданий.
Формирование итоговой оценки по курсу по итогам 3-го и 4-го модулей
- За каждый из двух модулей выставляется независимая оценка в шкале 0, 4-10.
- Итоговая оценка по курсу вычисляется как среднее арифметическое двух оценок за каждый из модулей с дальнейшим округлением к ближайшему целому (.5 округляется к единице).
- Если по одному из модулей оценка 0 баллов, то итоговая оценка за курс – также 0 баллов.
Правила сдачи заданий
В рамках курса предполагается сдача нескольких домашних и практических заданий. Домашнее задание сдаётся к началу очередного семинара на листочках или (по согласованию с семинаристом) по почте в виде скана или 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 | Метод сопряженных градиентов, неточный метод Ньютона и L-BFGS. | - |
Домашние задания
Задание 1. Скорости сходимости и матричные вычисления. Срок сдачи: 17 января 2017 (на семинаре).
Задание 2. Производные и условия оптимальности. Срок сдачи: 31 января 2017 (на семинаре).
Задание 3. Выпуклые множества и функции. Срок сдачи: 22 февраля 2017 (23:59).
Практические задания
Задание 1. Методы градиентного спуска и Ньютона. Срок сдачи: 22 февраля 2017 (23:59).
Задание 2. Продвинутые методы безусловной оптимизации. Срок сдачи: 9 марта 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.