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

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (08:55, 7 сентября 2015) (править) (отменить)
 
(4 промежуточные версии не показаны)
Строка 1: Строка 1:
-
__NOTOC__
+
#REDIRECT [[Методы оптимизации в машинном обучении (курс лекций)/2015]]
-
 
+
-
{{notice|Внимание! Выложена формулировка второго практического задания. Срок сдачи - 15 декабря.}}
+
-
 
+
-
Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков не только по подбору подходящего метода для своей задачи, но и по разработке своего метода оптимизации, наиболее полно учитывающего особенности конкретной задачи.
+
-
 
+
-
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
+
-
 
+
-
Автор курса: [[Участник:Kropotov|Д.А. Кропотов]]. Вопросы и комментарии по курсу просьба адресовать письмом на ''bayesml@gmail.com''. В название письма просьба добавлять [МОМО14].
+
-
 
+
-
== Расписание на 2014 учебный год ==
+
-
В осеннем семестре 2014 года спецкурс читается на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 508, начало в 18-10.
+
-
 
+
-
{| class = "standard"
+
-
|+
+
-
! width="10%" | Дата
+
-
! width="60%" | Название лекции
+
-
! width="30%" | Материалы
+
-
|-
+
-
| 15 сентября 2014
+
-
| Введение в курс ||
+
-
|-
+
-
| 22 сентября 2014
+
-
| Методы одномерной минимизации || [[Media:MOMO14_min1d.pdf|Конспект]]
+
-
|-
+
-
| 29 сентября 2014
+
-
| Базовые методы многомерной минимизации ||
+
-
|-
+
-
| 6 октября 2014
+
-
| Метод сопряжённых градиентов ||
+
-
|-
+
-
| 13 октября 2014
+
-
| Неточный (безгессианный) метод Ньютона и квазиньютоновские методы оптимизации ||
+
-
|-
+
-
| 20 октября 2014
+
-
| Методы оптимизации с использованием глобальных верхних оценок ||
+
-
|-
+
-
| 27 октября 2014
+
-
| Задачи оптимизации с ограничениями, метод Ньютона для задач с ограничениями вида равенства ||
+
-
|-
+
-
| 3 ноября 2014
+
-
| ''Лекции не будет. Праздничный день.'' ||
+
-
|-
+
-
| 10 ноября 2014
+
-
| ''Лекции не будет.'' ||
+
-
|-
+
-
| 17 ноября 2014
+
-
| Прямо-двойственный метод Ньютона и метод логарифмических барьеров ||
+
-
|-
+
-
| 24 ноября 2014
+
-
| Прямо-двойственный метод внутренней точки ||
+
-
|-
+
-
| 1 декабря 2014
+
-
| Разреженные методы машинного обучения ||
+
-
|-
+
-
| 8 декабря 2014
+
-
| Стохастическая оптимизация ||
+
-
|-
+
-
| 15 декабря 2014
+
-
| Методы оптимизации для глубинного обучения ||
+
-
|-
+
-
| 22 декабря 2014
+
-
| Экзамен ||
+
-
|-
+
-
|}
+
-
 
+
-
== Система выставления оценок за курс ==
+
-
 
+
-
В рамках курса предполагается два практических задания и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Итоговая оценка за курс получается путем взвешенного суммирования оценок за задания и экзамен с дальнейшим округлением в сторону ближайшего целого. Вес каждого задания составляет 1/3. За каждый день просрочки при сдаче задания начисляется штраф в 0.1 балла, но не более 2 баллов. Для допуска к экзамену необходимо предварительно сдать на положительную оценку оба задания.
+
-
 
+
-
== Практические задания ==
+
-
 
+
-
Задание 1. [[Media:MOMO14_assignment1.pdf| Одномерная оптимизация]]
+
-
 
+
-
Задание 2. [[Media:MOMO14_assignment2.pdf| Методы оптимизации для <tex>L_1</tex>-регуляризованной линейной регрессии]]
+
-
 
+
-
== Программа курса ==
+
-
 
+
-
=== Основные понятия и примеры задач ===
+
-
 
+
-
* Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
+
-
* Матричные разложения, их использование для решения СЛАУ;
+
-
* Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
+
-
* Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации;
+
-
* Примеры оракулов и задач машинного обучения со «сложной» оптимизацией.
+
-
 
+
-
=== Методы одномерной оптимизации ===
+
-
 
+
-
* Минимизация функции без производной: метод золотого сечения, метод парабол;
+
-
* Гибридный метод минимизации Брента;
+
-
* Методы решения уравнения <tex>f^\prime(x)=0</tex>: метод деления отрезка пополам, метод секущей;
+
-
* Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
+
-
* Поиск ограничивающего сегмента;
+
-
* Условия Армихо-Голдштайна-Вольфа для неточного решения задачи одномерной оптимизации;
+
-
* Неточные методы одномерной оптимизации, backtracking.
+
-
 
+
-
=== Методы многомерной оптимизации ===
+
-
 
+
-
* Методы линейного поиска и доверительной области;
+
-
* Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
+
-
* Сходимость общего метода линейного поиска с неточной одномерной минимизацией;
+
-
* Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
+
-
* Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
+
-
* Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
+
-
* Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
+
-
* Применение неточного метода Ньютона для обучения линейного классификатора и нелинейной регрессии, аппроксимация Гаусса-Ньютона и адаптивная стратегия Levenberg-Marquardt;
+
-
* Квазиньютоновские методы оптимизации: DFP, BFGS и L-BFGS;
+
-
 
+
-
=== Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра ===
+
-
 
+
-
* Вероятностная модель линейной регрессии с различными регуляризациями: квадратичной, L1, Стьюдента;
+
-
* Идея метода оптимизации, основанного на использовании глобальных оценок, сходимость;
+
-
* Пример применения метода для обучения LASSO;
+
-
* Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностных моделей линейной регрессии;
+
-
* Построение оценок с помощью касательных и замены переменной;
+
-
* Оценка Jaakkola-Jordan для логистической функции, оценки для распределений Лапласа и Стьюдента;
+
-
* Применение оценок для обучения вероятностных моделей линейной регрессии;
+
-
* Выпукло-вогнутая процедура, примеры использования.
+
-
 
+
-
=== Задачи оптимизации с ограничениями, понятие двойственности ===
+
-
 
+
-
* Векторные и матричные нормы, примеры, двойственная норма;
+
-
* Выпуклые множества и функции, сопряженная функция Фенхеля, понятие двойственности;
+
-
* Двойственная функция Лагранжа, ее связь с сопряженной функцией Фенхеля, двойственная задача оптимизации;
+
-
* Геометрическая интерпретация двойственности;
+
-
* Необходимые и достаточные условия оптимальности в задачах условной оптимизации, теорема Куна-Таккера;
+
-
* Возмущенная задача оптимизации, экономический смысл коэффициентов Лагранжа.
+
-
 
+
-
=== Методы внутренней точки ===
+
-
 
+
-
* Условия Куна-Таккера для выпуклых задач оптимизации, общая структура прямо-двойственных методов оптимизации;
+
-
* Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
+
-
* Прямо-двойственный метод Ньютона;
+
-
* Метод логарифмических барьерных функций, поиск допустимой стартовой точки;
+
-
* Прямо-двойственный метод внутренней точки;
+
-
* Использование методов внутренней точки для обучения SVM.
+
-
 
+
-
=== Разреженные методы машинного обучения ===
+
-
 
+
-
* Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
+
-
* Понятие субградиента выпуклой функции, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации, примеры;
+
-
* Проксимальный метод;
+
-
* Метод покоординатного спуска и блочной покоординатной оптимизации;
+
-
* Метод active set на примере регрессии наименьших углов.
+
-
 
+
-
=== Методы отсекающих плоскостей ===
+
-
 
+
-
* Понятие отделяющего оракула, базовый метод отсекающих плоскостей (cutting plane);
+
-
* Надграфная форма метода отсекающих плоскостей;
+
-
* Bundle-версия метода отсекающих плоскостей, зависимость от настраиваемых параметров;
+
-
* Применение bundle-метода для задачи обучения SVM;
+
-
* Добавление эффективной процедуры одномерного поиска;
+
-
* Реализация метода с использованием параллельных вычислений и в условиях ограничений по памяти.
+
-
 
+
-
=== Стохастическая оптимизация ===
+
-
 
+
-
* Общая постановка задачи стохастической оптимизации, пример использования;
+
-
* Задачи минимизации среднего и эмпирического риска;
+
-
* Метод стохастического градиентного спуска, его отличия от метода градиентного спуска;
+
-
* Стохастический градиентный спуск как метод оптимизации и как метод обучения;
+
-
* Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS);
+
-
* Модели автокодировщика и глубинного автокодировщика, особенности процедуры обучения и использование стохастического градиентного спуска.
+
-
 
+
-
== Литература ==
+
-
# [http://www.ebook3000.com/Programming/General/Optimization-for-Machine-Learning_151684.html Optimization for Machine Learning]. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
+
-
# J. Nocedal, S.J. Wright. [http://www.twirpx.com/file/724235/ Numerical Optimization]. Springer, 2006.
+
-
# S. Boyd, L. Vandenberghe. [http://www.stanford.edu/~boyd/cvxbook/ Convex Optimization], Cambridge University Press, 2004.
+
-
# A. Antoniou, W.-S. Lu. [http://www.twirpx.com/file/602599/ Practical Optimization: Algorithms and Engineering Applications], Springer, 2007.
+
-
# Б. Поляк. [http://premolab.ru/sites/default/files/polyak-optimizationintro.djvu Введение в оптимизацию], Наука, 1983.
+
-
# Ю. Нестеров. [http://premolab.ru/sites/default/files/nesterovfinal.pdf Методы выпуклой оптимизации], МЦМНО, 2010.
+
-
# R. Fletcher. [http://www.twirpx.com/file/515359/ Practical Methods of Optimization], Wiley, 2000.
+
-
# [http://www.twirpx.com/file/1442975/ Numerical Recipes. The Art of Scientific Computing], Cambridge University Press, 2007.
+
-
 
+
-
== Архив ==
+
-
[[Методы оптимизации в машинном обучении (курс лекций)/2012|2012 год]]
+
-
 
+
-
== См. также ==
+
-
[[GM|Курс «Графические модели»]]
+
-
 
+
-
[[Bmmo|Курс «Байесовские методы в машинном обучении»]]
+
-
 
+
-
[[Спецсеминар "Байесовские методы машинного обучения"|Спецсеминар «Байесовские методы машинного обучения»]]
+
-
 
+
-
[[Математические методы прогнозирования (кафедра ВМиК МГУ)]]
+
-
 
+
-
[[Категория:Учебные курсы]]
+

Текущая версия

  1. REDIRECT Методы оптимизации в машинном обучении (курс лекций)/2015
Источник — «http://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_%D0%B2_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%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»