Теория статистического обучения (курс лекций, Н. К. Животовский)
Материал из MachineLearning.
м (→Снижение размерности) |
|||
(50 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | |||
- | |||
- | |||
{{TOCright}} | {{TOCright}} | ||
Курс знакомит студентов с [[теория статистического обучения|теорией статистического обучения]] (Statistical Learning Theory), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным. | Курс знакомит студентов с [[теория статистического обучения|теорией статистического обучения]] (Statistical Learning Theory), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным. | ||
- | В весеннем семестре | + | В весеннем семестре 2017 года на кафедре [[Интеллектуальные системы (кафедра МФТИ)|Интеллектуальные системы]] [[ФУПМ]] [[МФТИ]] данный курс читается вместо курса [[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)|Теория надёжности обучения по прецедентам]], являющегося третьей частью трёхсеместрового курса [[Машинное обучение (курс лекций, К.В.Воронцов)|Теория обучения машин]], а также как альтернативный курс кафедры МОУ МФТИ. |
== Примерная программа курса == | == Примерная программа курса == | ||
- | === | + | === Постановки задач распознавания === |
* [http://en.wikipedia.org/wiki/Probably_approximately_correct_learning PAC (Probably Approximately Correct)] обучение. | * [http://en.wikipedia.org/wiki/Probably_approximately_correct_learning PAC (Probably Approximately Correct)] обучение. | ||
* Задачи классификации, регрессии и общая задача статистического оценивания. | * Задачи классификации, регрессии и общая задача статистического оценивания. | ||
* Функции потерь, риск, избыточный риск. | * Функции потерь, риск, избыточный риск. | ||
- | * No Free Lunch Theorem | + | * No Free Lunch Theorem. |
+ | * Онлайн постановка. | ||
+ | * Алгоритм Halving. | ||
Текст: [[Медиа:SLT,_lecture_1.pdf|Первая лекция]] | Текст: [[Медиа:SLT,_lecture_1.pdf|Первая лекция]] | ||
Строка 20: | Строка 19: | ||
* Методы, основанные на производящих функциях моментов. | * Методы, основанные на производящих функциях моментов. | ||
* Неравенства Маркова и Чебышева. | * Неравенства Маркова и Чебышева. | ||
- | * Неравенство Хеффдинга. | + | * Неравенство Хеффдинга и Чернова. |
* Неравенство ограниченных разностей. | * Неравенство ограниченных разностей. | ||
* Доказательство обучаемости конечных классов. | * Доказательство обучаемости конечных классов. | ||
Строка 27: | Строка 26: | ||
=== Радемахеровский анализ === | === Радемахеровский анализ === | ||
* [[Минимизация эмпирического риска|Метод минимизации эмпирического риска]]. | * [[Минимизация эмпирического риска|Метод минимизации эмпирического риска]]. | ||
+ | * Классы Гливенко-Кантелли. | ||
* Равномерные оценки отклонения частоты от вероятности. | * Равномерные оценки отклонения частоты от вероятности. | ||
+ | * Оценки максимумов случайных величин. | ||
* Верхние оценки избыточного риска. | * Верхние оценки избыточного риска. | ||
* [[Радемахеровская сложность|Радемахеровская сложность]]. | * [[Радемахеровская сложность|Радемахеровская сложность]]. | ||
Строка 37: | Строка 38: | ||
* [[Функция роста]] семейства алгоритмов. | * [[Функция роста]] семейства алгоритмов. | ||
* Ёмкость семейства [[Линейный классификатор|линейных разделяющих правил]]. | * Ёмкость семейства [[Линейный классификатор|линейных разделяющих правил]]. | ||
+ | * Теорема Радона. | ||
+ | * Доказательство верхней оценки для чисел покрытия в классах с конечной ёмкостью. | ||
* Верхние оценки Радемахеровской сложности классов конечной ёмкости. | * Верхние оценки Радемахеровской сложности классов конечной ёмкости. | ||
+ | * Теорема Дворецкого-Кифера-Вольфовитца | ||
Текст: [[Медиа:SLT,_lecture_4.pdf|Четвертая лекция]] | Текст: [[Медиа:SLT,_lecture_4.pdf|Четвертая лекция]] | ||
Строка 45: | Строка 49: | ||
* Условие малого шума Массара. | * Условие малого шума Массара. | ||
* Быстрые порядки обучаемости. | * Быстрые порядки обучаемости. | ||
+ | * Бесшумная классификация. | ||
Текст: [[Медиа:SLT,_lecture_5.pdf|Пятая лекция]] | Текст: [[Медиа:SLT,_lecture_5.pdf|Пятая лекция]] | ||
- | === | + | === Онлайн обучение I === |
- | * | + | * Схемы сжатия выборок. Оценки обобщающей способности. |
- | + | * Размерность Литтлстоуна. | |
- | * | + | * Оптимальный алгоритм. |
- | * | + | * Онлайн алгоритмы и сжатие некоторых классов. |
- | * | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | === | + | Текст: [[Медиа:SLT,_lecture_85.pdf|Шестая лекция]] |
+ | |||
+ | === Онлайн обучение II === | ||
+ | * Алгоритм экспоненциального большинства. | ||
+ | * Мартингальные неравенства Азумы и Чернова. | ||
+ | * Неправенство Чернова и его применения. | ||
+ | * Online to batch conversion. | ||
+ | |||
+ | Текст: [[Медиа:SLT,_lecture_9new.pdf|Седьмая лекция]] | ||
+ | |||
+ | === Нижние оценки и выбор модели === | ||
+ | * Нижние оценки для метода минимизации эмпирического риска. | ||
+ | * Оракульные неравенства. | ||
* Структурная минимизация эмпирического риска. | * Структурная минимизация эмпирического риска. | ||
- | |||
- | |||
- | |||
- | === Снижение размерности === | + | Текст: [[Медиа:SLT,_lecture_6,_new.pdf|Восьмая лекция]] |
- | * [[Метод главных компонент|Метод главных компонент]]. | + | |
+ | === Регуляризация и устойчивость === | ||
+ | * Понятие устойчивости в среднем и его связь с переобучением. | ||
+ | * Баланс эмпирического риска и устойчивости. | ||
+ | * Обучаемость ограниченной линейной задачи с выпуклой и липшицевой функцией потерь. | ||
+ | |||
+ | Текст: [[Медиа:SLT,_lecture_7,_new.pdf|Девятая лекция]] | ||
+ | |||
+ | === Активное обучение === | ||
+ | * Постановка задачи. | ||
+ | * Активное обучение пороговых классификаторов. | ||
+ | * Коэффициент разногласия. | ||
+ | * Алгоритм CAL. Оценка сходимости. | ||
+ | * Примеры коэффициентов разногласия. | ||
+ | |||
+ | === Снижение размерности и разреженность === | ||
+ | * [[Метод главных компонент|Метод главных компонент]]. Подход с SVD разложением и без него. | ||
+ | * [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|Десятая лекция]] |
+ | |||
+ | == Домашние задания == | ||
+ | Первое: [[Медиа:SLTsetofproblems1.pdf|Задание 1]] | ||
+ | |||
+ | Второе: [[Медиа:SLTsetofproblems2.pdf|Задание 2]] | ||
+ | |||
+ | Третье: [[Медиа:SLTsetofproblems3.pdf|Задание 3]] | ||
+ | |||
+ | Четвертое: [[Медиа:SLTsetofproblems4.pdf|Задание 4]] | ||
+ | |||
+ | [https://docs.google.com/spreadsheets/d/1B5ELKtAFoIK3co8dfbikA-9ReZKAadx5UGlOcY6PwAg/edit#gid=0| Выбранные проекты.] | ||
+ | |||
+ | == Текущие дедлайны == | ||
+ | |||
+ | Четрвертое задание -- 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 | # 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 | # 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 | # 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 | ||
'''Дополнительная литература''' | '''Дополнительная литература''' | ||
- | # Risk bounds for statistical learning // Pascal Massart, Élodie Nédélec. Ann. Statist. Volume 34, Number 5 | + | # 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 | ||
[[Категория:Учебные курсы]] | [[Категория:Учебные курсы]] |
Текущая версия
Курс знакомит студентов с теорией статистического обучения (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