Методы оптимизации в машинном обучении (курс лекций)
Материал из MachineLearning.
(Различия между версиями)
(+ задание 1) |
(→Методы одномерной оптимизации) |
||
| Строка 79: | Строка 79: | ||
* Минимизация функции без производной: метод золотого сечения, метод парабол; | * Минимизация функции без производной: метод золотого сечения, метод парабол; | ||
* Гибридный метод минимизации Брента; | * Гибридный метод минимизации Брента; | ||
| - | * | + | * Методы решения уравнения <tex>f^\prime(x)=0</tex>: метод деления отрезка пополам, метод секущей; |
| + | * Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента; | ||
* Поиск ограничивающего сегмента; | * Поиск ограничивающего сегмента; | ||
| - | * Условия Голдштайна-Деккера для | + | * Условия Голдштайна-Деккера-Флетчера для неточного решения задачи одномерной оптимизации; |
* Неточные методы одномерной оптимизации, backtracking. | * Неточные методы одномерной оптимизации, backtracking. | ||
Версия 13:39, 29 сентября 2012
| Внимание! Выложено первое практическое задание. Срок сдачи — 11 октября. |
| Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков не только по подбору подходящего метода для своей задачи, но и по разработке своего метода оптимизации, наиболее полно учитывающего особенности конкретной задачи.
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций. |
Автор курса: Д.А. Кропотов. Вопросы и комментарии по курсу просьба оставлять на вкладке «обсуждение» к этой странице или адресовать письмом на bayesml@gmail.com. В название письма просьба добавлять [МОМО12].
Расписание на 2012 учебный год
В осеннем семестре 2012 года спецкурс читается на ВМК по понедельникам в ауд. 506, начало в 18-05.
| Дата | Название лекции | Материалы |
|---|---|---|
| 10 сентября 2012 | Введение в курс | |
| 17 сентября 2012 | Лекции не будет | |
| 24 сентября 2012 | Методы одномерной минимизации | Текст (PDF) |
| 1 октября 2012 | Базовые методы многомерной оптимизации | |
| 8 октября 2012 | Продвинутые методы многомерной оптимизации | |
| 15 октября 2012 | Методы оптимизации с использованием глобальных верхних оценок | |
| 22 октября 2012 | Задачи оптимизации с ограничениями | |
| 29 октября 2012 | Методы внутренней точки | |
| 5 ноября 2012 | Лекции не будет (праздничный день) | |
| 12 ноября 2012 | Разреженные методы машинного обучения | |
| 19 ноября 2012 | Методы cutting plane и bundle | |
| 26 ноября 2012 | Стохастическая оптимизация |
Практические задания
Задание 1. Методы одномерной минимизации.
Оценка за курс
В рамках курса студентам предлагается выполнить ряд практических заданий. Для получения допуска к экзамену необходимо успешно выполнить не менее двух заданий.
Программа курса
Основные понятия и примеры задач
- Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
- Матричные вычисления, примеры;
- Матричные разложения, их использование для решения СЛАУ;
- Структура итерационного процесса в оптимизации, понятие оракула;
- Примеры оракулов и задач машинного обучения со «сложной» оптимизацией.
Методы одномерной оптимизации
- Минимизация функции без производной: метод золотого сечения, метод парабол;
- Гибридный метод минимизации Брента;
- Методы решения уравнения
: метод деления отрезка пополам, метод секущей;
- Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
- Поиск ограничивающего сегмента;
- Условия Голдштайна-Деккера-Флетчера для неточного решения задачи одномерной оптимизации;
- Неточные методы одномерной оптимизации, backtracking.
Методы многомерной оптимизации
- Метод покоординатного спуска;
- Методы градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, зависимость от шкалы измерений признаков;
- Метод Ньютона, подбор длины шага;
- Фазы итерационного процесса, LDL-разложение, гибридный метод Ньютона;
- Метод Levenberg-Marquardt, его использование для обучения нелинейной регрессии.
- Квази-ньютоновские методы оптимизации: BFGS и L-BFGS.
- Метод сопряженных градиентов;
- Метод сопряженных градиентов с предопределением, его использование для решения разреженных СЛАУ большого объема.
Методы оптимизации с использованием глобальных верхних оценок
- Идея метода, сходимость;
- Построение оценок с помощью неравенства Йенсена, ЕМ-алгоритм, вариационный подход;
- Построение оценок с помощью касательных, оценка Jaakkola-Jordan, nu-trick;
- Применение оценок для обучения L1-регуляризованной линейной/логистической регрессии;
- Выпукло-вогнутая процедура для задач безусловной и условной оптимизации, примеры использования.
Задачи оптимизации с ограничениями
- Выпуклые множества и функции;
- Двойственная функция Лагранжа и Фенхеля, их основные свойства.
- Необходимые и достаточные условия оптимальности в задачах условной оптимизации, теорема Куна-Таккера.
- Двойственная задача, графическая интерпретация, смысл коэффициентов Лагранжа.
- Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона.
Методы внутренней точки
- Метод внутренней точки;
- Прямодвойственный метод внутренней точки;
- Быстрые алгоритмы умножения матрицы на вектор и их использование в методе внутренней точки.
Разреженные методы машинного обучения, L1-регуляризация
- Примеры задач и виды разреженных регуляризаторов;
- Проксимальный метод;
- Метод покоординатного спуска и блочной покоординатной оптимизации;
- Метод внутренней точки.
Методы cutting plane и bundle
- Субградиент выпуклой функции;
- Метод отсекающей плоскости и его bundle расширение;
- Примеры задач распознавания, сводящихся к оптимизации регуляризованных функционалов;
- Использование bundle метода для задач оптимизации регуляризованных функционалов;
- Добавление одномерного поиска.
Стохастическая оптимизация
Литература
- Optimization for Machine Learning. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
- S. Boyd. Convex Optimization, Cambridge University Press, 2004.
- A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
- R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
- Numerical Recipes. The Art of Scientific Computing, 1992.
См. также
Курс «Байесовские методы в машинном обучении»
