Методы оптимизации (курс лекций)

Материал из MachineLearning.

(Различия между версиями)

Версия 16:30, 9 января 2017

Страница курса находится в стадии формирования

Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности. Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.

Занятия проходят на ФКН ВШЭ.

Лектор: Кропотов Дмитрий Александрович. Лекции проходят по вторникам в ауд. 622 с 13:40 до 15:00.

Семинаристы:

Группа	Семинарист	Расписание
141 (МОП)	Родоманов Антон Олегович	вторник, 15:10 – 16:30, ауд. 513
142 (МОП)	Хальман Михаил Анатольевич	вторник, 15:10 – 16:30, ауд. 501
145 (РС)	Дойков Никита Владимирович	вторник, 15:10 – 16:30, ауд. 503

Система выставления оценок по курсу

В рамках курса предполагается четыре практических задания, несколько домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. В итоговой оценке 45% составляют баллы за практические задания, 25% — баллы за домашние задания и 30% — оценка за экзамен. Для получения финального результата (0, 3, 4, 5) итоговая оценка по курсу округляется в большую сторону. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла, но суммарно не более 3 баллов.

Лекции


№ п/п	Дата	Занятие
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	Стохастическая оптимизация.

Программа курса

Основные понятия и примеры задач

Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
Матричные разложения, их использование для решения СЛАУ;
Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации.

Методы одномерной оптимизации

Минимизация функции без производной: метод золотого сечения, метод парабол;
Гибридный метод минимизации Брента;
Методы решения уравнения $f^\prime(x)=0$ : метод деления отрезка пополам, метод секущей;
Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
Поиск ограничивающего сегмента;
Условия Армихо и Вольфа для неточного решения задачи одномерной оптимизации;
Неточные методы одномерной оптимизации, 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.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29»

Категория: Учебные курсы

@@ Строка 36: / Строка 36: @@
 | align="center"|1
 | 10&nbsp;января&nbsp;2017
-| Введение в курс. Скорости сходимости и дифференцирование || <b>(Скорости сходимости)</b> [Nocedal-Wright, pp. 617-620] <br /> <b>(Дифференцирование)</b> [Ben-Tal-Nemirovski, Section A.6]
+| Введение в курс. Необходимое условие экстремума. Оракулы, скорости сходимости итерационных процессов. ||
 |-
 | align="center"|2
 | 17&nbsp;января&nbsp;2017
-| Методы одномерной оптимизации. Неточная одномерная оптимизация || <b>(Одномерная оптимизация)</b> [[Media:MOMO16_min1d.pdf|Текст]] <br /> <b>(Неточная одномерная оптимизация)</b> [Nocedal-Wright, pp. 30-37] + [Ben-Tal-Nemirovski, pp. 164-166]
+| Точная одномерная оптимизация. ||
 |-
 | align="center"|3
 | 24&nbsp;января&nbsp;2017
-| Базовые методы многомерной оптимизации || [Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5]
+| Неточная одномерная оптимизация. Классы функций для оптимизации. Метод градиентного спуска. ||
 |-
 | align="center"|4
 | 31&nbsp;января&nbsp;2017
-| Методы сопряженных градиентов || [[Media:Momo16_Sem4_presentation_final.pdf|Презентация]] + [Nocedal-Wright, Chapter 5]
+| Матричные разложения и их использование для решения СЛАУ. Метод Ньютона для выпуклых и невыпуклых задач. ||
 |-
 | align="center"|5
 | 7&nbsp;февраля&nbsp;2017
-| Неточный метод Ньютона. Автоматическое дифференцирование || <b>(Неточный метод Ньютона)</b> [Nocedal-Wright, pp. 184-189] <br /> <b>(Автоматическое дифференцирование)</b> [Nocedal-Wright, Section 8.2]
+| Линейный метод сопряжённых градиентов. ||
 |-
 | align="center"|6
 | 14&nbsp;февраля&nbsp;2017
-| Квазиньютоновские методы. Метод L-BFGS || <b>(Квазиньютоновские методы)</b> [Nocedal-Wright, Section 6] <br /> <b>(Метод L-BFGS)</b> [Nocedal-Wright, pp. 176-180]
+| Неточный метод Ньютона. Разностные производные. ||
 |-
 | align="center"|7
 | 21&nbsp;февраля&nbsp;2017
-| Задачи условной оптимизации: теория. || [Поляк, Глава 9] + [Boyd-Vandenberghe, Sections 4 and 5]
+| Квазиньютоновские методы. Метод L-BFGS. ||
 |-
 | align="center"|8
 | 28&nbsp;февраля&nbsp;2017
-| Метод Ньютона для задач с ограничениями вида равенств, метод барьеров || [Boyd-Vandenberghe, pp. 521-531, 561-571]
+| Задачи условной оптимизации: условия ККТ. ||
 |-
 | align="center"|9
 | 7&nbsp;марта&nbsp;2017
-| Прямо-двойственный метод внутренней точки || [Boyd-Vandenberghe, pp. 609-615]
+| Выпуклые задачи оптимизации. Двойственность. Метод барьеров. ||
 |-
 | align="center"|10
 | 14&nbsp;марта&nbsp;2017
-| Негладкая безусловная оптимизация. Субградиентный метод || [Поляк, Разделы 5.1-5.3] + [Nesterov, Sections 3.1-3.2.3]
+| Негладкая безусловная оптимизация. Субградиентный метод. Проксимальные методы. ||
 |-
 | align="center"|11
 | 21&nbsp;марта&nbsp;2017
-| Проксимальный градиентный метод. Сопряженные функции по Фенхелю || <b>(Проксимальный градиентный метод)</b> [http://www.seas.ucla.edu/~vandenbe/236C/lectures/proxgrad.pdf Слайды] <br /> <b>(Сопряженные функции)</b> [Boyd-Vandenberghe, Section 3.3] + [http://www.seas.ucla.edu/~vandenbe/236C/lectures/conj.pdf Слайды]
+| Стохастическая оптимизация. ||
 |-
 |}