Теория статистического обучения (курс лекций, Н. К. Животовский)

Материал из MachineLearning.

⇆

В настоящее время страница находится в стадии наполнения.

Содержание 1 Примерная программа курса 1.1 Вероятностная постановка задач распознавания 1.2 Неравенства концентрации меры 1.3 Радемахеровский анализ 1.4 Размерность Вапника-Червоненкиса (ёмкость) 1.5 Условия малого шума 1.6 Комбинаторная теория переобучения 1.7 Выбор моделей 1.8 Снижение размерности 1.9 Композиции алгоритмов 2 Ссылки

Курс знакомит студентов с теорией статистического обучения (Statistical Learning Theory), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным.

В весеннем семестре 2015 года на кафедре Интеллектуальные системы ФУПМ МФТИ данный курс читается вместо курса Теория надёжности обучения по прецедентам, являющегося третьей частью трёхсеместрового курса Теория обучения машин.

Примерная программа курса

Вероятностная постановка задач распознавания

• PAC (Probably Approximately Correct) обучение.
• Задачи классификации, регрессии и общая задача статистического оценивания.
• Функции потерь, риск, избыточный риск.
• No Free Lunch Theorem

Текст: Первая лекция‎

Неравенства концентрации меры

• Доказательство No Free Lunch Theorem
• Методы, основанные на производящих функциях моментов.
• Неравенства Маркова и Чебышева.
• Неравенство Хеффдинга.
• Неравенство ограниченных разностей.
• Доказательство обучаемости конечных классов.

Текст: Вторая лекция‎

Радемахеровский анализ

• Метод минимизации эмпирического риска.
• Равномерные оценки отклонения частоты от вероятности.
• Верхние оценки избыточного риска.
• Радемахеровская сложность.
• Оценки избыточного риска, основанные на Радемахеровской сложности.

Текст: Третья лекция‎

Размерность Вапника-Червоненкиса (ёмкость)

• Понятие ёмкости.
• Функция роста семейства алгоритмов.
• Ёмкость семейства линейных разделяющих правил.
• Верхние оценки Радемахеровской сложности классов конечной ёмкости.

Текст: Четвертая лекция‎

Условия малого шума

• Энтропийная верхняя оценка Радемахеровской сложности.
• Неравенство Бернштейна.
• Условие малого шума Массара.
• Быстрые порядки обучаемости.

Комбинаторная теория переобучения

• Комбинаторная постановка задачи оценивания вероятности переобучения.
• Одноэлементное семейство. Гипергеометрическое распределение.
• Произвольное семейство. Оценка вапниковского типа.
• Эксперимент с четырьмя модельными семействами алгоритмов. Свойства расслоения и связности.
• Оценка расслоения-связности. Принцип порождающих и запрещающих множеств.
• Частные оценки для модельных семейств алгоритмов.
• Использование комбинаторных оценок для выбора модели и отбора признаков.
• Оценки скользящего контроля для метода ближайших соседей. Понятие профиля компактности.
• Оценки скользящего контроля для монотонных классификаторов.

Хорошо бы сделать две лекции — К.В.Воронцов 04:10, 4 февраля 2015 (MSK)

Выбор моделей

• Структурная минимизация эмпирического риска.
• Регуляризация и fitting-stability tradeoff.
• Отбор признаков.
• AIC, BIC.

Снижение размерности

• Метод главных компонент.
• Compressed sensing
• Restricted isometry property
• Условия точного восстановления разреженного вектора.

Композиции алгоритмов

Ссылки

Основная литература

1. 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
2. Understanding Machine Learning: From Theory to Algorithms // Shai Shalev-Shwartz and Shai Ben-David. Cambridge University Press, 2014
3. Concentration Inequalities: A Nonasymptotic Theory of Independence // Stéphane Boucheron, Gábor Lugosi, Pascal Massart. Oxford University Press, 2013

Дополнительная литература

1. Risk bounds for statistical learning // Pascal Massart, Élodie Nédélec. Ann. Statist. Volume 34, Number 5 (2006), 2326-2366.