Теория статистического обучения (курс лекций, Н. К. Животовский)
Материал из MachineLearning.
⇆
| В настоящее время страница находится в стадии наполнения. |
Курс знакомит студентов с теорией статистического обучения (Statistical Learning Theory), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным.
В весеннем семестре 2015 года на кафедре Интеллектуальные системы ФУПМ МФТИ данный курс читается вместо курса Теория надёжности обучения по прецедентам, являющегося третьей частью трёхсеместрового курса Теория обучения машин.
Примерная программа курса
Вероятностная постановка задач распознавания
- PAC (Probably Approximately Correct) обучение.
- Задачи классификации, регрессии и общая задача статистического оценивания.
- Функции потерь, риск, избыточный риск.
- No Free Lunch Theorem
Текст: Первая лекция
Неравенства концентрации меры
- Доказательство No Free Lunch Theorem
- Методы, основанные на производящих функциях моментов.
- Неравенства Маркова и Чебышева.
- Неравенство Хеффдинга.
- Неравенство ограниченных разностей.
- Доказательство обучаемости конечных классов.
Текст: Вторая лекция
Радемахеровский анализ
- Метод минимизации эмпирического риска.
- Равномерные оценки отклонения частоты от вероятности.
- Верхние оценки избыточного риска.
- Радемахеровская сложность.
- Оценки избыточного риска, основанные на Радемахеровской сложности.
Текст: Третья лекция
Размерность Вапника-Червоненкиса (ёмкость)
- Понятие ёмкости.
- Функция роста семейства алгоритмов.
- Ёмкость семейства линейных разделяющих правил.
- Верхние оценки Радемахеровской сложности классов конечной ёмкости.
Текст: Четвертая лекция
Условия малого шума
- Энтропийная верхняя оценка Радемахеровской сложности.
- Неравенство Бернштейна.
- Условие малого шума Массара.
- Быстрые порядки обучаемости.
Текст: Пятая лекция
Комбинаторная теория переобучения
- Комбинаторная постановка задачи оценивания вероятности переобучения.
- Одноэлементное семейство. Гипергеометрическое распределение.
- Произвольное семейство. Оценка вапниковского типа.
- Эксперимент с четырьмя модельными семействами алгоритмов. Свойства расслоения и связности.
- Оценка расслоения-связности. Принцип порождающих и запрещающих множеств.
- Частные оценки для модельных семейств алгоритмов.
- Использование комбинаторных оценок для выбора модели и отбора признаков.
- Оценки скользящего контроля для метода ближайших соседей. Понятие профиля компактности.
- Оценки скользящего контроля для монотонных классификаторов.
Учебное пособие по шестой и седьмой лекции: Voron-2011-tnop.pdf, 3МБ. Презентация: Voron-2015-tnop.pdf, 1.9МБ.
Нижние оценки и Выбор моделей
- Фундаментальная теорема PAC обучения.
- Нижние оценки для метода минимизации эмпирического риска.
- Оракульные неравенства.
- Структурная минимизация эмпирического риска.
Текст: Восьмая лекция
Выбор моделей (продолжение)
Снижение размерности
- Метод главных компонент.
- Compressed sensing
- Restricted isometry property
- Условия точного восстановления разреженного вектора.
Композиции алгоритмов
Ссылки
Основная литература
- 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
- Concentration Inequalities: A Nonasymptotic Theory of Independence // Stéphane Boucheron, Gábor Lugosi, Pascal Massart. Oxford University Press, 2013
Дополнительная литература
- Risk bounds for statistical learning // Pascal Massart, Élodie Nédélec. Ann. Statist. Volume 34, Number 5 (2006), 2326-2366.
