Методи оптимізації в машинному навчанні (курс лекцій) / 2012

1. Матеріал з MachineLearning. Курс присвячений класичним і сучасним методам вирішення завдань безперервної...
2. практичні завдання
3. іспит
4. оцінки
5. Система виставлення оцінок за курс
6. програма курсу
7. Див. також

Матеріал з MachineLearning.

Курс присвячений класичним і сучасним методам вирішення завдань безперервної оптимізації, а також особливостям їх застосування в задачах оптимізації, що виникають в машинному навчанні. Основний акцент у викладі робиться на практичні аспекти реалізації і використання методів. Метою курсу є вироблення у слухачів навичок не тільки по підбору підходящого методу для свого завдання, а й по розробці свого методу оптимізації, найбільш повно враховує особливості конкретного завдання.

Курс розрахований на студентів старших курсів і аспірантів. Знання основ машинного навчання вітається, але не є обов'язковим - всі необхідні поняття вводяться в ході лекцій.

Автор курсу: Д.А. Кропотов . Питання і коментарі по курсу прохання залишати на вкладці «обговорення» до цієї сторінки або адресувати листом на [email protected]. У назву листа прохання додавати [МОМО12].

Розклад на 2012 навчальний рік

В осінньому семестрі 2012 року спецкурс читається на ВМК по понеділках в ауд. 506, початок о 18-10.

Дата Назва лекції Матеріали 10 вересня 2012 Введення в курс 17 вересня 2012 Лекції не було 24 вересня 2012 Методи одновимірної мінімізації Текст (PDF, 185Кб) 1 жовтня 2012 Базові методи багатовимірної оптимізації Текст (PDF, 1.13Мб) 8 жовтня 2012 Просунуті методи багатовимірної оптимізації Текст (PDF, 667Кб) 15 жовтня 2012 Методи оптимізації з використанням глобальних верхніх оцінок Текст (PDF, 248Кб) 22 жовтня 2012 Завдання оптимізації з обмеженнями 29 жовтня 2012 Методи внутрішньої точки Текст (PDF, 241Кб) 5 листопада 2012 Лекції не було (святковий день) 12 листопада 2012 Приклади застосування методів внутрішньої точки 19 листопада 2012 Методи оптимізації для розріджених лінійних моделей класифікації і регресії Текст (PDF, 229Кб) 26 листопада 2012 Методи відтинають площин 3 грудня 2012 Стохастическая оптимізація 10 грудня 2012 Лекції не було 17 грудня 2012 Іспит Питання до іспиту (PDF, 99Кб)

практичні завдання

Завдання 1. Методи одновимірної мінімізації .

Завдання 2. Методи багатовимірної мінімізації для логістичної регресії .

Завдання 3. Методи внутрішньої точки для лінійної регресії .

іспит

Іспит відбудеться 17 грудня в ауд. 506, початок о 16-20. До іспиту допускаються тільки ті студенти, хто успішно виконав не менше одного практичного завдання. На іспиті при підготовці дозволяється користуватися будь-якими матеріалами.

Питання до іспиту + теоретичний мінімум (PDF, 99Кб)

оцінки

Студент Група Завдання 1 Завдання 2 Завдання 3 Іспит Підсумок Сокурскій 317 - Чистякова 422 4.0 5 5 Артюхін 517 4.9 Єлшин 517 - Зімовнов 517 5.0 4.3 4.4 5 Кирилов 517 4.0 Некрасов 517 3.8 3 3 Новіков П. 517 3.8 4 4 Соколов 517 5.0 4.8 4.4 5 Фигурнов 517 - Сайко хутро-мат 3.6

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

В рамках курсу передбачається три практичних завдання і іспит. Кожне завдання і іспит оцінюються за п'ятибальною шкалою. Підсумкова оцінка за курс виходить шляхом виваженого підсумовування оцінок за завдання і іспит з подальшим округленням у бік найближчого цілого. Вага кожного завдання становить 1/3. Таким чином, якщо студент успішно виконав всі три практичних завдання, то він отримує оцінку за курс без іспиту. Мінімально студент повинен виконати одну практичні завдання. У цьому випадку він складає іспит, оцінка за який йде в підсумкову суму з вагою 2/3. Якщо студент виконав два практичних завдання, то він також здає іспит, але за полегшеною схемою (менше питань у квитку, менше додаткових питань). В цьому випадку оцінка за іспит йде в підсумкову суму з вагою 1/3. За кожен день прострочення при здачі завдання нараховується штраф в 0.1 бала, але не більше 2 балів.

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

Основні поняття і приклади завдань

• Градієнт і гессіан функції багатьох змінних, їх властивості, необхідні і достатні умови безумовного екстремуму;
• Матричні обчислення, приклади;
• Матричні розкладання, їх використання для вирішення СЛАР;
• Структура ітераційного процесу в оптимізації, поняття оракула;
• Приклади оракулів і завдань машинного навчання зі «складною» оптимізацією.

Методи одновимірної оптимізації

Методи багатовимірної оптимізації

• Метод покоордінатного спуску;
• Методи градієнтного спуску: найшвидшого спуску, спуск з неточною одновимірної оптимізацією, залежність від шкали вимірювань ознак;
• Метод Ньютона, підбір довжини кроку;
• Теоретичні результати щодо швидкості збіжності градієнтного спуску і методу Ньютона;
• Фази ітераційного процесу, LDL-розкладання, гібридний метод Ньютона;
• Метод Levenberg-Marquardt, його використання для навчання нелінійної регресії;
• Метод сполучених градієнтів для вирішення систем лінійних рівнянь;
• Метод сполучених градієнтів для оптимізації неквадратічних функцій, залежність від точної одновимірної оптимізації;
• Квазі-ньютонівські методи оптимізації: DFP, BFGS і L-BFGS;
• Співвідношення між різними методами рішення СЛАР.

Методи оптимізації з використанням глобальних верхніх оцінок, що залежать від параметра

• Імовірнісна модель лінійної регресії з різними регуляризації: квадратичної, L1, Стьюдента;
• Ідея методу оптимізації, заснованого на використанні глобальних оцінок, збіжність;
• Приклад застосування методу для навчання LASSO;
• Побудова глобальних оцінок за допомогою нерівності Йєнсена, ЕМ-алгоритм, його застосування для імовірнісних моделей лінійної регресії;
• Побудова оцінок за допомогою дотичних і заміни змінної;
• Оцінка Jakkola-Jordan для логістичної функції, оцінки для розподілів Лапласа і Стьюдента;
• Застосування оцінок для навчання імовірнісних моделей лінійної регресії;
• Опукло-увігнута процедура, приклади використання.

Завдання оптимізації з обмеженнями, поняття подвійності

• Векторні і матричні норми, приклади, двоїста норма;
• Опуклі безлічі і функції, сполучена функція Фенхелю, поняття подвійності;
• Подвійна функція Лагранжа, її зв'язок з сполученої функцією Фенхелю, двоїста задача оптимізації;
• Геометрична інтерпретація подвійності;
• Необхідні і достатні умови оптимальності в задачах умовної оптимізації, теорема Куна-Таккера;
• Обурена завдання оптимізації, економічний сенс коефіцієнтів Лагранжа.

Методи внутрішньої точки

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

Розріджені методи машинного навчання

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

Методи відтинають площин

• Поняття відокремлює оракула, базовий метод відтинають площин (cutting plane);
• Надграфная форма методу відтинають площин;
• Bundle-версія методу відтинають площин, залежність від параметрів, що настроюються;
• Застосування bundle-методу для задачі навчання SVM;
• Додавання ефективної процедури одновимірного пошуку;
• Реалізація методу з використанням паралельних обчислень і в умовах обмежень по пам'яті.

стохастична оптимізація

• Загальна постановка задачі стохастичною оптимізації, приклад використання;
• Завдання мінімізації середнього і емпіричного ризику;
• Метод стохастичного градієнтного спуску, його відмінності від методу градієнтного спуску;
• Стохастичний градієнтний спуск як метод оптимізації і як метод навчання;
• Застосування стохастичного градієнтного спуску для SVM (алгоритм PEGASOS);
• Моделі автокодіровщіка і глибинного автокодіровщіка, особливості процедури навчання і використання стохастичного градієнтного спуску.

література

1. Optimization for Machine Learning . Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011 року.
2. S. Boyd, L. Vandenberghe. Convex Optimization , Cambridge University Press, 2004.
3. A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications , Springer, 2007.
4. Б. Поляк. Введення в оптимізацію , Наука, 1983.
5. Ю. Нестеров. Методи опуклою оптимізації , МЦМНО 2010.
6. R. Fletcher. Practical Methods of Optimization , Wiley, 2000..
7. Numerical Recipes. The Art of Scientific Computing , 1992.

Див. також

Курс «Графічні моделі»

Курс «Байєсовські методи в машинному навчанні»

Спецсемінар «Байєсовські методи машинного навчання»

Математичні методи прогнозування (кафедра ВМиК МГУ)