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

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

Версия от 16:12, 9 января 2017; Kropotov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Страница курса находится в стадии формирования



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

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

Лектор: Кропотов Дмитрий Александрович. Лекции проходят по вторникам в ауд. 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 5 сентября 2016 Введение в курс. Скорости сходимости и дифференцирование (Скорости сходимости) [Nocedal-Wright, pp. 617-620]
(Дифференцирование) [Ben-Tal-Nemirovski, Section A.6]
2 12 сентября 2016 Методы одномерной оптимизации. Неточная одномерная оптимизация (Одномерная оптимизация) Текст
(Неточная одномерная оптимизация) [Nocedal-Wright, pp. 30-37] + [Ben-Tal-Nemirovski, pp. 164-166]
3 19 сентября 2016 Базовые методы многомерной оптимизации [Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5]
4 26 сентября 2016 Методы сопряженных градиентов Презентация + [Nocedal-Wright, Chapter 5]
5 3 октября 2016 Неточный метод Ньютона. Автоматическое дифференцирование (Неточный метод Ньютона) [Nocedal-Wright, pp. 184-189]
(Автоматическое дифференцирование) [Nocedal-Wright, Section 8.2]
6 10 октября 2016 Квазиньютоновские методы. Метод L-BFGS (Квазиньютоновские методы) [Nocedal-Wright, Section 6]
(Метод L-BFGS) [Nocedal-Wright, pp. 176-180]
7 17 октября 2016 Задачи условной оптимизации: теория. [Поляк, Глава 9] + [Boyd-Vandenberghe, Sections 4 and 5]
8 24 октября 2016 Метод Ньютона для задач с ограничениями вида равенств, метод барьеров [Boyd-Vandenberghe, pp. 521-531, 561-571]
9 31 октября 2016 Прямо-двойственный метод внутренней точки [Boyd-Vandenberghe, pp. 609-615]
10 7 ноября 2016 Негладкая безусловная оптимизация. Субградиентный метод [Поляк, Разделы 5.1-5.3] + [Nesterov, Sections 3.1-3.2.3]
11 14 ноября 2016 Проксимальный градиентный метод. Сопряженные функции по Фенхелю (Проксимальный градиентный метод) Слайды
(Сопряженные функции) [Boyd-Vandenberghe, Section 3.3] + Слайды
12 21 ноября 2016 Суррогатная оптимизация Текст
13 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
14 5 декабря 2016 Быстрый градиентный метод Нестерова Нестеров, 2013 (Разделы 1.2.2 и 2.3.4) + Текст
15 12 декабря 2016 Доклады студентов
16 19 декабря 2016 Переписывание контрольных работ и разбор практических заданий

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

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

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

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

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

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

  • Методы линейного поиска и доверительной области;
  • Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
  • Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
  • Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
  • Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
  • Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
  • Квазиньютоновские методы оптимизации: SR1, BFGS и L-BFGS.

Методы внутренней точки

  • Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера;
  • Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
  • Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
  • Прямо-двойственный метод Ньютона, неточный вариант метода;
  • Метод логарифмических барьерных функций;
  • Прямо-двойственный метод внутренней точки;
  • Методы первой фазы.

Разреженные методы машинного обучения

  • Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
  • Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
  • Метод наискорейшего субградиентного спуска;
  • Проксимальный метод, вычисление prox-оператора для L1- и L1/L2-регуляризаторов.

Стохастическая оптимизация

  • Задачи минимизации среднего и эмпирического риска;
  • Метод стохастического градиентного спуска, две фазы итерационного процесса, использование инерции;
  • Метод SAG;
  • Комбинирование стохастической оптимизации и проксимального метода.

Суррогатная оптимизация

  • Вероятностная модель логистической регрессии;
  • Общая идея метода суррогатной оптимизации;
  • Применение метода для стохастической оптимизации: метод MISO;
  • Пример применения метода для обучения LASSO;
  • Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностной модели логистической регрессии;
  • Построение оценок с помощью касательных и замены переменной;
  • Оценка Jaakkola-Jordan для логистической функции, её применение для обучения вероятностной модели логистической регрессии;
  • Выпукло-вогнутая процедура, примеры использования.

Методы оптимизации для глубинного обучения

  • Адаптивная стратегия Левенберга-Марквардта для задачи минимизации суммы квадратов;
  • Модель глубинного автокодировщика;
  • Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
  • Неточный метод Ньютона с предобуславливанием через L-BFGS.

Литература

  1. S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.
  2. J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
  3. A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
  4. Б. Поляк. Введение в оптимизацию, Наука, 1983.
  5. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
  6. Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.
  7. R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
  8. A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
  9. W. Press et al.. Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, 2007.