Теория статистического обучения (курс лекций, Н. К. Животовский)
Материал из MachineLearning.
м |
м (→Снижение размерности) |
||
(7 промежуточных версий не показаны.) | |||
Строка 86: | Строка 86: | ||
* Активное обучение пороговых классификаторов. | * Активное обучение пороговых классификаторов. | ||
* Коэффициент разногласия. | * Коэффициент разногласия. | ||
- | * Алгоритм CAL. | + | * Алгоритм CAL. Оценка сходимости. |
- | * | + | * Примеры коэффициентов разногласия. |
- | === Снижение размерности === | + | === Снижение размерности и разреженность === |
* [[Метод главных компонент|Метод главных компонент]]. Подход с SVD разложением и без него. | * [[Метод главных компонент|Метод главных компонент]]. Подход с SVD разложением и без него. | ||
* [http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma Лемма Джонсона-Линденштраусса] | * [http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma Лемма Джонсона-Линденштраусса] | ||
* [http://en.wikipedia.org/wiki/Compressed_sensing Compressed sensing] | * [http://en.wikipedia.org/wiki/Compressed_sensing Compressed sensing] | ||
- | * [http://en.wikipedia.org/wiki/Restricted_isometry_property | + | * [http://en.wikipedia.org/wiki/Restricted_isometry_property Restricted isometry property] |
* Условия точного восстановления разреженного вектора. | * Условия точного восстановления разреженного вектора. | ||
+ | * Модель гауссовской последовательности. Hard Thresholding, оценки на риск. | ||
Текст: [[Медиа:SLT,_lecture_8.pdf|Десятая лекция]] | Текст: [[Медиа:SLT,_lecture_8.pdf|Десятая лекция]] | ||
Строка 104: | Строка 105: | ||
Третье: [[Медиа:SLTsetofproblems3.pdf|Задание 3]] | Третье: [[Медиа:SLTsetofproblems3.pdf|Задание 3]] | ||
+ | |||
+ | Четвертое: [[Медиа:SLTsetofproblems4.pdf|Задание 4]] | ||
[https://docs.google.com/spreadsheets/d/1B5ELKtAFoIK3co8dfbikA-9ReZKAadx5UGlOcY6PwAg/edit#gid=0| Выбранные проекты.] | [https://docs.google.com/spreadsheets/d/1B5ELKtAFoIK3co8dfbikA-9ReZKAadx5UGlOcY6PwAg/edit#gid=0| Выбранные проекты.] | ||
Строка 109: | Строка 112: | ||
== Текущие дедлайны == | == Текущие дедлайны == | ||
- | + | Четрвертое задание -- 24 мая, 2.00 Мск. | |
+ | |||
+ | Проверка 3-его задания -- 24 мая, 2.00 Мск. | ||
== Ссылки == | == Ссылки == |
Текущая версия
Курс знакомит студентов с теорией статистического обучения (Statistical Learning Theory), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным.
В весеннем семестре 2017 года на кафедре Интеллектуальные системы ФУПМ МФТИ данный курс читается вместо курса Теория надёжности обучения по прецедентам, являющегося третьей частью трёхсеместрового курса Теория обучения машин, а также как альтернативный курс кафедры МОУ МФТИ.
Примерная программа курса
Постановки задач распознавания
- PAC (Probably Approximately Correct) обучение.
- Задачи классификации, регрессии и общая задача статистического оценивания.
- Функции потерь, риск, избыточный риск.
- No Free Lunch Theorem.
- Онлайн постановка.
- Алгоритм Halving.
Текст: Первая лекция
Неравенства концентрации меры
- Доказательство No Free Lunch Theorem
- Методы, основанные на производящих функциях моментов.
- Неравенства Маркова и Чебышева.
- Неравенство Хеффдинга и Чернова.
- Неравенство ограниченных разностей.
- Доказательство обучаемости конечных классов.
Текст: Вторая лекция
Радемахеровский анализ
- Метод минимизации эмпирического риска.
- Классы Гливенко-Кантелли.
- Равномерные оценки отклонения частоты от вероятности.
- Оценки максимумов случайных величин.
- Верхние оценки избыточного риска.
- Радемахеровская сложность.
- Оценки избыточного риска, основанные на Радемахеровской сложности.
Текст: Третья лекция
Размерность Вапника-Червоненкиса (ёмкость)
- Понятие ёмкости.
- Функция роста семейства алгоритмов.
- Ёмкость семейства линейных разделяющих правил.
- Теорема Радона.
- Доказательство верхней оценки для чисел покрытия в классах с конечной ёмкостью.
- Верхние оценки Радемахеровской сложности классов конечной ёмкости.
- Теорема Дворецкого-Кифера-Вольфовитца
Текст: Четвертая лекция
Условия малого шума
- Энтропийная верхняя оценка Радемахеровской сложности.
- Неравенство Бернштейна.
- Условие малого шума Массара.
- Быстрые порядки обучаемости.
- Бесшумная классификация.
Текст: Пятая лекция
Онлайн обучение I
- Схемы сжатия выборок. Оценки обобщающей способности.
- Размерность Литтлстоуна.
- Оптимальный алгоритм.
- Онлайн алгоритмы и сжатие некоторых классов.
Текст: Шестая лекция
Онлайн обучение II
- Алгоритм экспоненциального большинства.
- Мартингальные неравенства Азумы и Чернова.
- Неправенство Чернова и его применения.
- Online to batch conversion.
Текст: Седьмая лекция
Нижние оценки и выбор модели
- Нижние оценки для метода минимизации эмпирического риска.
- Оракульные неравенства.
- Структурная минимизация эмпирического риска.
Текст: Восьмая лекция
Регуляризация и устойчивость
- Понятие устойчивости в среднем и его связь с переобучением.
- Баланс эмпирического риска и устойчивости.
- Обучаемость ограниченной линейной задачи с выпуклой и липшицевой функцией потерь.
Текст: Девятая лекция
Активное обучение
- Постановка задачи.
- Активное обучение пороговых классификаторов.
- Коэффициент разногласия.
- Алгоритм CAL. Оценка сходимости.
- Примеры коэффициентов разногласия.
Снижение размерности и разреженность
- Метод главных компонент. Подход с SVD разложением и без него.
- Лемма Джонсона-Линденштраусса
- Compressed sensing
- Restricted isometry property
- Условия точного восстановления разреженного вектора.
- Модель гауссовской последовательности. Hard Thresholding, оценки на риск.
Текст: Десятая лекция
Домашние задания
Первое: Задание 1
Второе: Задание 2
Третье: Задание 3
Четвертое: Задание 4
Текущие дедлайны
Четрвертое задание -- 24 мая, 2.00 Мск.
Проверка 3-его задания -- 24 мая, 2.00 Мск.
Ссылки
Основная литература
- Introduction to Statistical Learning Theory // Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Advanced Lectures on Machine Learning. Lecture Notes in Computer Science Volume 3176, 2004, pp 169-207
- Understanding Machine Learning: From Theory to Algorithms // Shai Shalev-Shwartz and Shai Ben-David. Cambridge University Press, 2014
- Prediction, Learning, and Games // Nicolo Cesa-Bianchi and Gábor Lugosi. Cambridge University Press, 2006
- Theory of Classification: a Survey of Some Recent Advances // Olivier Bousquet, Stéphane Boucheron, Gábor Lugosi. ESAIM: Probability and Statistics / Volume 9 / 2005
- Concentration Inequalities: A Nonasymptotic Theory of Independence // Stéphane Boucheron, Gábor Lugosi, Pascal Massart. Oxford University Press, 2013
- A Probabilistic Theory of Pattern Recognition // Luc Devroye, László Györfi, Gábor Lugosi. Springer Verlag, 1997.
- Theory of Disagreement-Based Active Learning // Foundations and Trends in Machine Learning, Volume 7 Issue 2-3, 2014
Дополнительная литература
- High dimensional statistics // M. Wainwright, Cambridge University Press, 2017
- High Dimensional Probability. An Introduction with Applications in Data Science. // Roman Vershynin, 2017
- Concentration Inequalities and Model Selection. // Pascal Massart Ecole d’Et´e de Probabilit´es de Saint-Flour XXXIII – 2003. Springer Verlag, 2007
- Risk bounds for statistical learning // Pascal Massart, Élodie Nédélec. Ann. Statist. Volume 34, Number 5 2006