Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)/2011
Материал из MachineLearning.
Программа спецкурса, прочитанного на кафедре ММП ВМК МГУ весной 2011 года.
Комбинаторная теория переобучения
Проблема переобучения и перестановочная вероятность
- Задача обучения по прецедентам. Матрица ошибок. Понятия наблюдаемой и скрытой выборки. Проблема переобучения. Примеры приложений.
- Слабая вероятностная аксиоматика. Вероятности переобучения. Перенос оценок из слабой аксиоматики в сильную (колмогоровскую).
- Точность и надёжность предсказаний. Обращение оценок.
- Эмпирические оценки. Скользящий контроль.
- Финитарные и инфинитарные вероятности. Сравнение с колмогоровской аксиоматикой, достоинства, недостатки и границы применимости.
Предсказание частоты события и гипергеометрическое распределение
- Задача предсказания частоты события. Выборочный контроль качества.
- Лемма. Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
- Теорема. Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках.
- Геометрическая интерпретация.
- Свойства гипергеометрического распределения. Методы вычисления гипергеометрического распределения.
- Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.
- Переход от ненаблюдаемой оцеки к наблюдаемой. Точная интервальная оценка. Вероятность нуль-события.
Теория Вапника-Червоненкиса
- Принцип равномерной сходимости.
- Коэффициент разнообразия (shatter coefficient), функция роста.
- Теорема. Оценка Вапника-Червоненкиса.
- Обращение оценки. Метод структурной минимизации риска.
- Проблема завышенности оценок. Анализ причин завышенности, эффекты расслоения и связности.
- Эксперимент 1. Вычисление достаточной длины обучающей выборки.
- Разновидности методов обучения. Пессимистичная, оптимистичная, рандомизированная минимизация эмпирического риска. Максимизация переобученности.
- Программа для вычисления эмпирических оценок вероятности переобучения. Метод Монте-Карло. Скользящий контроль.
- Эксперимент 2. Вычисление вероятности переобучения для модельных семейств алгоритмов с расслоением и связностью.
- Теорема. Вероятность переобучения семейства без расслоения.
Размерность Вапника-Червоненкиса (ёмкость)
- Понятие ёмкости.
- Функция
, её связь с треугольником Паскаля.
- Лемма о функции
- Теорема. Выражение функции роста через ёмкость.
- Ёмкость конечных множеств. Принцип минимума длины описания.
- Теорема. Ёмкость семейства линейных разделяющих правил.
- Пример однопараметрического семейства бесконечной ёмкости.
- Теорема. Ёмкость семейства конъюнкций элементарных пороговых условий.
- Ёмкость некоторых разновидностей нейронных сетей (без доказательства).
Принцип порождающих и запрещающих множеств
- Простая гипотеза о множествах порождающих и запрещающих объектов.
- Лемма о вероятности получить заданный алгоритм в результате обучения.
- Теорема. Точная оценка вероятности переобучения.
- Общая гипотеза о множествах порождающих и запрещающих объектов.
- Теорема. Общая гипотеза верна практически всегда.
- Аналогично: Лемма и Теорема для общей гипотезы.
- Теорема. Точная оценка вероятности переобучения для случая, когда существует корректный алгоритм.
- Теорема. Точная оценка функционала полного скользящего контроля.
Модельные семейства алгоритмов (семейства простой структуры)
- Монотонная цепь алгоритмов. Примеры.
- Теорема. Вероятность переобучения монотонной цепи.
- Унимодальная цепь алгоритмов. Примеры.
- Теорема. Вероятность переобучения унимодальной цепи.
- Единичная окрестность лучшего алгоритма.
- Теорема. Вероятность переобучения единичной окрестности.
- Пучок h монотонных цепочек алгоритмов.
- Полный слой алгоритмов.
Оценки расслоения-связности
- Граф расслоения-связности. Верхняя и нижняя связность и неоптимальность алгоритмов.
- Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности.
- h-мерная монотонная сеть алгоритмов.
Конъюнктивные логические закономерности
- Логические алгоритмы классификации. Критерии информативности.
- Структура классов эквивалентности семейства конъюнкций пороговых предикатов.
- Стандартные представители классов эквивалентности и граничные пожмножества объектов.
- Послойный восходящий алгоритм вычисления оценки расслоения-связности.
- Модификация критериев информативности. Результаты экспериментов.
Рекуррентное вычисление вероятности переобучения
- Идея рекуррентного обновления информации о каждом алгоритме семейства при добавлении нового алгоритма.
- Лемма. Вычисление информации о добавленном алгоритме. Доказательство леммы.
- Теорема. Правила обновления информации о предыдущих алгоритмах при добавлении нового.
- Теорема. Упрощённый рекуррентный алгоритм не уменьшает оценку вероятности переобучения.
Блочные и интервальные точные оценки вероятности переобучения
- Определение блока объектов.
- Теорема. Формула для вычисления вероятности переобучения по блокам.
- Теорема. Вероятность переобучения для пары алгоритмов.
- Вероятность переобучения интервала булева куба и его нижних слоёв.
Оценки равномерного отклонения эмпирических распределений
- Вероятность большого равномерного отклонения эмпирических функций распределения. Интерпретации: эмпирическое предсказание и проверка гипотезы однородности.
- Теоремы Колмогорова и Смирнова (без доказательства).
- Усечённый треугольник Паскаля. Случайное блуждание.
- Теорема. Точная оценка вероятности большого равномерного отклонения эмпирических распределений. Геометрические интерпретации.
- Обобщение на случай вариационного ряда со связками. Почему в этом случае задача предсказания намного сложнее.
Радемахеровская сложность
- Метод обучения, максимизирующий переобученность.
- Понятие Радемахеровской сложности.
- Оценка через принцип порождающих и запрещающих множеств.
- Оценка через цепные разложения.
- Точная оценка для монотонной цепи алгоритмов через случайное блуждание.
Оценки скользящего контроля для метода ближайших соседей
- Метрические алгоритмы классификации, метод ближайших соседей.
- Понятие профиля компактности.
- Теорема. Точное выражение функционала полного скользящего контроля для метода одного ближайшего соседа (1NN).
- Теорема. Точное выражение функционала полного скользящего контроля для метода k ближайших соседей (kNN).
- Свойства профилей компактности.
- Алгоритм выделения эталонных объектов. Функция вклада объекта и её эффективное вычисление. Метрические деревья.
- Разделение объектов на шумовые, эталонные и неинформативные.
Оценки скользящего контроля для монотонных классификаторов
- Монотонные алгоритмы классификации.
- Понятие клина объекта. Профиль монотонности выборки.
- Теорема. Верхняя оценка скользящего контроля. Доказательство теоремы.
- Монотонные корректирующие операции в алгоритмических композициях.
- Критерии настройки базовых алгоритмов на основе оценок обобщающей способности.
Непараметрические статистические критерии
- Задачи проверки статистических гипотез.
- Гипотеза однородности, гипотеза сдвига.
- Принципиальное различие задач эмпирического предсказания и проверки статистических гипотез.
- Критерий знаков.
- Критерий Уилкоксона-Манна-Уитни.
- Критерий серий.
- Критерий Смирнова.
- Доверительное оценивание. Доверительный интервал для медианы.
Литература
- Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с. (подробнее).
- Воронцов К. В. Слабая вероятностная аксиоматика. 2009. PDF, 832 КБ.
- Воронцов К. В. Эффекты расслоения и сходства в семействах алгоритмов и их влияние на вероятность переобучения. 2009. PDF, 354 КБ.
- Воронцов К. В. Точные оценки вероятности переобучения. 2009. PDF, 542 КБ.
