Методы оптимизации в машинном обучении (курс лекций)
Материал из MachineLearning.
(Различия между версиями)
(→Разреженные методы машинного обучения) |
(→Программа курса) |
||
| Строка 117: | Строка 117: | ||
* Применение оценок для обучения вероятностных моделей линейной регрессии; | * Применение оценок для обучения вероятностных моделей линейной регрессии; | ||
* Выпукло-вогнутая процедура, примеры использования. | * Выпукло-вогнутая процедура, примеры использования. | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
=== Методы внутренней точки === | === Методы внутренней точки === | ||
| - | * | + | * Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера и условия Джона, соотношение между ними; |
| + | * Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации; | ||
* Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона; | * Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона; | ||
| - | * Прямо-двойственный метод Ньютона; | + | * Прямо-двойственный метод Ньютона, неточный вариант метода; |
* Метод логарифмических барьерных функций, поиск допустимой стартовой точки; | * Метод логарифмических барьерных функций, поиск допустимой стартовой точки; | ||
| + | * Методы первой фазы; | ||
* Прямо-двойственный метод внутренней точки; | * Прямо-двойственный метод внутренней точки; | ||
* Использование методов внутренней точки для обучения SVM. | * Использование методов внутренней точки для обучения SVM. | ||
| Строка 157: | Строка 150: | ||
* Общая постановка задачи стохастической оптимизации, пример использования; | * Общая постановка задачи стохастической оптимизации, пример использования; | ||
* Задачи минимизации среднего и эмпирического риска; | * Задачи минимизации среднего и эмпирического риска; | ||
| - | * Метод стохастического градиентного спуска, | + | * Метод стохастического градиентного спуска, две фазы итерационного процесса, использование усреднения и инерции; |
* Стохастический градиентный спуск как метод оптимизации и как метод обучения; | * Стохастический градиентный спуск как метод оптимизации и как метод обучения; | ||
| + | * Метод SAG; | ||
* Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS); | * Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS); | ||
| - | * | + | |
| + | === Методы оптимизации для глубинного обучения === | ||
| + | |||
| + | * Модель глубинного автокодировщика; | ||
| + | * Стандартный подход к глубинному обучению: стохастический градиент + мини-батчи + предобучение + drop-out; | ||
| + | * Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор; | ||
| + | * Неточный метод Ньютона с предобуславливанием через L-BFGS. | ||
== Литература == | == Литература == | ||
Версия 12:45, 15 декабря 2014
| Внимание! Выложена формулировка второго практического задания. Срок сдачи - 15 декабря. |
Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков не только по подбору подходящего метода для своей задачи, но и по разработке своего метода оптимизации, наиболее полно учитывающего особенности конкретной задачи.
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
Автор курса: Д.А. Кропотов. Вопросы и комментарии по курсу просьба адресовать письмом на bayesml@gmail.com. В название письма просьба добавлять [МОМО14].
Расписание на 2014 учебный год
В осеннем семестре 2014 года спецкурс читается на ВМК по понедельникам в ауд. 508, начало в 18-10.
| Дата | Название лекции | Материалы |
|---|---|---|
| 15 сентября 2014 | Введение в курс | |
| 22 сентября 2014 | Методы одномерной минимизации | Конспект |
| 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. Одномерная оптимизация
Задание 2. Методы оптимизации для -регуляризованной линейной регрессии
Программа курса
Основные понятия и примеры задач
- Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
- Матричные разложения, их использование для решения СЛАУ;
- Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
- Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации;
- Примеры оракулов и задач машинного обучения со «сложной» оптимизацией.
Методы одномерной оптимизации
- Минимизация функции без производной: метод золотого сечения, метод парабол;
- Гибридный метод минимизации Брента;
- Методы решения уравнения
: метод деления отрезка пополам, метод секущей;
- Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
- Поиск ограничивающего сегмента;
- Условия Армихо-Голдштайна-Вольфа для неточного решения задачи одномерной оптимизации;
- Неточные методы одномерной оптимизации, backtracking.
Методы многомерной оптимизации
- Методы линейного поиска и доверительной области;
- Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
- Сходимость общего метода линейного поиска с неточной одномерной минимизацией;
- Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
- Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
- Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
- Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
- Применение неточного метода Ньютона для обучения линейного классификатора и нелинейной регрессии, аппроксимация Гаусса-Ньютона и адаптивная стратегия Levenberg-Marquardt;
- Квазиньютоновские методы оптимизации: DFP, BFGS и L-BFGS;
Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра
- Вероятностная модель линейной регрессии с различными регуляризациями: квадратичной, L1, Стьюдента;
- Идея метода оптимизации, основанного на использовании глобальных оценок, сходимость;
- Пример применения метода для обучения LASSO;
- Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностных моделей линейной регрессии;
- Построение оценок с помощью касательных и замены переменной;
- Оценка Jaakkola-Jordan для логистической функции, оценки для распределений Лапласа и Стьюдента;
- Применение оценок для обучения вероятностных моделей линейной регрессии;
- Выпукло-вогнутая процедура, примеры использования.
Методы внутренней точки
- Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера и условия Джона, соотношение между ними;
- Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
- Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
- Прямо-двойственный метод Ньютона, неточный вариант метода;
- Метод логарифмических барьерных функций, поиск допустимой стартовой точки;
- Методы первой фазы;
- Прямо-двойственный метод внутренней точки;
- Использование методов внутренней точки для обучения SVM.
Разреженные методы машинного обучения
- Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
- Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
- Метод наискорейшего субградиентного спуска;
- Проксимальный метод;
- Метод покоординатного спуска и блочной покоординатной оптимизации.
Методы отсекающих плоскостей
- Понятие отделяющего оракула, базовый метод отсекающих плоскостей (cutting plane);
- Надграфная форма метода отсекающих плоскостей;
- Bundle-версия метода отсекающих плоскостей, зависимость от настраиваемых параметров;
- Применение bundle-метода для задачи обучения SVM;
- Добавление эффективной процедуры одномерного поиска;
- Реализация метода с использованием параллельных вычислений и в условиях ограничений по памяти.
Стохастическая оптимизация
- Общая постановка задачи стохастической оптимизации, пример использования;
- Задачи минимизации среднего и эмпирического риска;
- Метод стохастического градиентного спуска, две фазы итерационного процесса, использование усреднения и инерции;
- Стохастический градиентный спуск как метод оптимизации и как метод обучения;
- Метод SAG;
- Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS);
Методы оптимизации для глубинного обучения
- Модель глубинного автокодировщика;
- Стандартный подход к глубинному обучению: стохастический градиент + мини-батчи + предобучение + drop-out;
- Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
- Неточный метод Ньютона с предобуславливанием через L-BFGS.
Литература
- Optimization for Machine Learning. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
- J. Nocedal, S.J. Wright. Numerical Optimization. Springer, 2006.
- S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
- A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
- Б. Поляк. Введение в оптимизацию, Наука, 1983.
- Ю. Нестеров. Методы выпуклой оптимизации, МЦМНО, 2010.
- R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
- Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, 2007.
Архив
См. также
Курс «Байесовские методы в машинном обучении»
