Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)

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

Версия 11:05, 10 мая 2010

Спецкурс знакомит студентов с современным состоянием теории вычислительного обучения (computational learning theory, COLT), исследующей проблему качества восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики В. Н. Вапник и А. Я. Червоненкис. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время развивается очень активно, главным образом, за рубежом.

Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными? Как избежать переобучения — ситуации, когда ответы алгоритма слишком точны на обучающей выборке, но недостаточно точны на новых данных, которые не были известны на этапе обучения? Как управлять обобщающей способностью алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.

Цели спецкурса — научить студентов не только строить и применять обучаемые алгоритмы анализа данных, но и оценивать их надёжность; разрабатывать более надёжные алгоритмы; понимать возможные причины ненадёжной работы обучаемых алгоритмов в прикладных задачах классификации, регрессии, прогнозирования.

В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по комбинаторной теории обобщающей способности и слабой вероятностной аксиоматике.

Спецкурс читается студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года, в дополнение к обязательному кафедральному курсу Математические методы распознавания образов (ММРО). Некоторые лекции спецкурса являются непосредственным продолжением соответствующих лекций ММРО, что специально отмечено в программе.

Сборник задач по спецкурсу «Теория надёжности обучения по прецедентам»: PDF, 183 КБ.

Комбинаторные методы в математической статистике

Предсказание частоты события и закон больших чисел

• Задача эмпирического предсказания в общей постановке. Понятия наблюдаемой и скрытой выборки. Точность и надёжность предсказаний.
• Слабая вероятностная аксиоматика. Перенос оценок из слабой аксиоматики в сильную (колмогоровскую). Финитарные и инфинитарные вероятности. Сравнение с колмогоровской аксиоматикой, достоинства, недостатки и границы применимости.
• Задача предсказания частоты события. Примеры приложений: выборочный контроль качества, оценивание качества алгоритма классификации.
• Лемма. Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
• Теорема. Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках. Доказательство теоремы.
• Геометрическая интерпретация.
• Свойства гипергеометрического распределения. Методы вычисления гипергеометрического распределения.
• Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.

Обращение оценок

• Парадокс: оценка вероятности большого уклонения частот зависит от оцениваемой величины — числа ошибок на полной выборке.
• Экспоненциальная верхняя оценка вероятности большого уклонения частот, её обращение и «грубое» устранение парадокса.
• Обращение кусочно-постоянных функций.
• Переход от ненаблюдаемой оценки к наблюдаемой: общая постановка проблемы; одномерный случай.
• Обращение точной верхней оценки частоты события на скрытой выборке; «аккуратное» устранение парадокса.
• Интервальная оценка частоты нуль-события на скрытой выборке.

Оценки равномерного отклонения эмпирических распределений

• Задача оценивания функции распределения как задача эмпирического предсказания.
• Теоремы Колмогорова и Смирнова (без доказательства).
• Усечённый треугольник Паскаля. Связь с задачами о случайном блуждании и разорении игрока.
• Теорема. Точная оценка вероятности больших отклонений эмпирических распределений. Доказательство теоремы. Геометрические интерпретации.
• Оценивание функции распределения на полной выборке.
• Обобщение на случай вариационного ряда со связками. Почему в этом случае задача предсказания намного сложнее.

Непараметрические статистические критерии

• Задачи проверки статистических гипотез.
• Гипотеза однородности, гипотеза сдвига.
• Принципиальное различие задач эмпирического предсказания и проверки статистических гипотез.
• Критерий знаков.
• Критерий Уилкоксона-Манна-Уитни.
• Критерий серий.
• Критерий Смирнова.
• Доверительное оценивание. Доверительный интервал для медианы.

Основы теории статистического обучения (теория Вапника-Червоненкиса)

Задача оценивания вероятности переобучения

• Основные понятия: алгоритм, метод обучения, переобучение. Примеры приложений: кредитный скоринг, медицинская диагностика.
• Функционал вероятности переобучения в слабой аксиоматике; полный скользящий контроль.
• Коэффициент разнообразия (shatter coefficient), профиль разнообразия (shatter profile), функция роста.
• Принцип равномерной сходимости.
• Теорема. Условия, при которых функционал равномерной сходимости совпадает с вероятностью переобучения метода минимизации эмпирического риска. Доказательство теоремы.
• Теорема Вапника-Червоненкиса. Доказательство теоремы.
• Обращение оценки.
• Метод структурной минимизации риска.
• Достаточная длина обучающей выборки.
• Проблема завышенности оценок. Эмпирическое оценивание вероятности переобучения (метод Монте-Карло). Скользящий контроль. Эксперименты по эмпирическому измерению факторов завышенности. Основные причины завышенности — пренебрежение эффектами расслоения и связности в семействах алгоритмов.
• Связность семейства алгоритмов с непрерывной дискриминантной функцией.

Влияние различности алгоритмов на вероятность переобучения

• Постановка экспериментов с методом минимизации эмпирического риска. Пессимистичная минимизация эмпирического риска.
• Теорема. Вероятность переобучения для пары алгоритмов. Доказательство теоремы.
• Результаты численного эксперимента: эффекты переобучения, расслоения и сходства для пары алгоритмов.
• Модельные семейства алгоритмов с расслоением и связностью: цепочки алгоритмов (монотонные, унимодальные, стохастические, без расслоения).
• Алгоритм эффективного построения зависимостей вероятности переобучения от числа алгоритмов в семействе. Результаты экспериментов и выводы. Без расслоения и связности переобучение наступает уже при нескольких десятках алгоритмов в семействе.
• Теорема. Вероятность переобучения для монотонной цепочки алгоритмов.

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

• Понятие ёмкости.
• Функция , её связь с треугольником Паскаля.
• Лемма о функции . Доказательство леммы.
• Теорема. Выражение функции роста через ёмкость. Доказательство теоремы.
• Ёмкость конечных множеств. Принцип минимума длины описания.
• Теорема. Ёмкость семейства линейных разделяющих правил. Доказательство теоремы.
• Пример однопараметрического семейства бесконечной ёмкости.
• Теорема. Ёмкость семейства конъюнкций элементарных пороговых условий. Доказательство теоремы.
• Ёмкость некоторых разновидностей нейронных сетей (без доказательства).

Неравенства типа Бонферрони

• Классические неравенства Бонферрони.
• Понятие биномиально ограниченной функции. Примеры биномиально ограниченных функций.
• Основная теорема и следствия.
• Применение дерева событий для замены неравенства Буля более точным неравенством Бонферрони при выводе оценок типа Вапника-Червоненкиса.

Литература:

1. Klaus Dohmen, Peter Tittmann. Bonferroni-type inequalities and binomially bounded functions. — Electronic Notes in Discrete Mathematics (Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications). — 2007 T. 28. — 91–93 с.

Точные комбинаторные оценки обобщающей способности

Общая точная оценка вероятности переобучения

• Понятия порождающих, запрещающих и нейтральных объектов для данного алгоритма.
• Простая гипотеза о множествах порождающих и запрещающих объектов.
• Лемма о вероятности получить заданный алгоритм в результате обучения. Доказательство леммы.
• Теорема. Точная оценка вероятности переобучения. Доказательство теоремы.
• Общая гипотеза о множествах порождающих и запрещающих объектов.
• Теорема. Общая гипотеза верна практически всегда. Доказательство теоремы.
• Аналогично: Лемма и Теорема для общей гипотезы.
• Теорема. Упрощённая оценка вероятности переобучения для случая, когда существует корректный алгоритм. Доказательство теоремы.

Модельные семейства алгоритмов (семейства простой структуры)

• Монотонная цепочка алгоритмов. Примеры.
• Теорема. Вероятность переобучения монотонной цепочки. Доказательство теоремы.
• Унимодальная цепочка алгоритмов. Примеры.
• Теорема. Вероятность переобучения унимодальной цепочки. Доказательство теоремы.
• Единичная окрестность лучшего алгоритма.
• Теорема. Вероятность переобучения единичной окрестности. Доказательство теоремы.
• h-мерная монотонная сетка алгоритмов. Линейная зависимость вероятности переобучения от размерности сетки.
• Пучок h монотонных цепочек алгоритмов.
• Полный слой алгоритмов.

Блочное вычисление вероятности переобучения

• Определение блока объектов.
• Теорема. Формула для вычисления вероятности переобучения по блокам. Доказательство теоремы.
• Теорема. Вероятность переобучения для пары алгоритмов. Доказательство теоремы.
• Условия, при которых блочное вычисление достаточно эффективно.

Рекуррентное вычисление вероятности переобучения

• Идея рекуррентного обновления информации о каждом алгоритме семейства при добавлении нового алгоритма.
• Лемма. Вычисление информации о добавленном алгоритме. Доказательство леммы.
• Теорема. Правила обновления информации о предыдущих алгоритмах при добавлении нового. Доказательство теоремы.
• Теорема. Упрощённый рекуррентный алгоритм не уменьшает оценку вероятности переобучения.

Профиль расслоения и связности

• Степень связности алгоритма. Граф расслоения и связности семейства алгоритмов. Профиль расслоения-связности.
• Теорема. Верхняя оценка вероятности пееобучения через профиль расслоения-связности. Доказательство теоремы.
• Эмпирическая гипотеза о сепарабельности профиля расслоения-связности.
• Эмпирические гипотезы о взаимосвязи средней связности и размерности пространства парамеров.
• Теорема. Верхняя оценка вероятности пееобучения через профиль расслоения и профиль связности. Доказательство теоремы.
• Сравнение с оценками Вапника-Червоненкиса. Эмпирический факт: вероятность переобучения зависит линейно от размерности пространства, тогда как в классических оценках зависимость близка к экспоненциальной.

Оценки скользящего контроля для метода ближайших соседей

• метрические алгоритмы классификации, метод ближайших соседей.
• Понятие профиля компактности.
• Теорема. Точное выражение функционала полного скользящего контроля для метода одного ближайшего соседа (1NN). Доказательство теоремы.
• Теорема. Точное выражение функционала полного скользящего контроля для метода k ближайших соседей (kNN).
• Свойства профилей компактности.
• Алгоритм выделения эталонных объектов. Функция вклада объекта и её эффективное вычисление. Метрические деревья.
• Разделение объектов на шумовые, эталонные и неинформативные.

Оценки скользящего контроля для монотонных классификаторов

• Монотонные алгоритмы классификации.
• Понятие клина объекта. Профиль монотонности выборки.
• Теорема. Верхняя оценка скользящего контроля. Доказательство теоремы.
• Монотонные корректирующие операции в алгоритмических композициях.
• Критерии настройки базовых алгоритмов на основе оценок обобщающей способности.

Литература по предыдущей части курса

• Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с.  (подробнее).
• Воронцов К. В. Слабая вероятностная аксиоматика. 2009. PDF, 832 КБ.
• Воронцов К. В. Эффекты расслоения и сходства в семействах алгоритмов и их влияние на вероятность переобучения. 2009. PDF, 354 КБ.
• Воронцов К. В. Точные оценки вероятности переобучения. 2009. PDF, 542 КБ.

Задачи по предыдущей части курса

• Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2010. PDF, 183 КБ.

Вероятностная байесовская теория обобщающей способности

Простейшие оценки вероятности ошибки классификации

• Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
• Биномиальное распределение.
• Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
• Обращение оценок.
• Теорема. Оценка вероятности ошибки фиксированного алгоритма (test set bound). Доказательство теоремы. Три следствия: применение трёх различных аппроксимаций хвоста биномиального распределения.

Литература:

1. Langford J. Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.

Бритва Оккама (Occam Razor)

• Понятия априорного распределения на множестве алгоритмов.
• Теорема. Оценка вероятности ошибки для произвольного алгоритма (Occam razor bound). Доказательство теоремы. Три следствия: применение аппроксимаций и оценка Вапника-Червоненкиса.
• Метод структурной минимизации риска (Вапника-Червоненкиса).
• Теорема. Об оптимальном априорном распределении. Доказательство теоремы.
• Открытые проблемы.

Литература:

1. Langford J. Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.

Микровыборы и статистические запросы

• Методы обучения, основанные на статистических запросах (statistical queries learning).
• Примеры алгоритмов. Решающие списки и решающие деревья.
• Дерево микровыборов.
• Оценки вероятности переобучения, основанные на микровыборах (microchoice bounds).
• Адаптивные оценки, основанные на микровыборах (adaptive microchoice bounds).
• Самоограничивающие методы обучения (self-bounding по Фройнду).

Стохастические классификаторы и теория PAC-Bayes

• Стохастические классификаторы. Понятия ожидаемой эмпирической ошибки и ожидаемой вероятности ошибок.
• Теорема. Основная теорема теории PAC-Bayes. Доказательство теоремы.

Литература:

1. Langford J. Tutorial on Practical Prediction Theory for Classification. — 2005. — 28 с.

Применение теории PAC-Bayes к линейным классификаторам

• Линейный классификатор, понятие отступа (margin), распределение отступов.
• Принцип минимизации эмпирического риска и принцип максимизации отступов. Замена пороговой функции потерь на её непрерывную аппроксимацию.
• Краткая история обоснований принципа максимизации отступов. О завышенности оценок обобщающей способности.
• Теорема. Конкретизация основной теоремы теории PAC-Bayes для линейных классификаторов. Доказательство теоремы. Выбор априорного и апостериорного распределений. Следствие: ещё одна аппроксимация пороговой функции потерь.
• Проблема правомерности переноса результатов, полученных для стохастических классификаторов, на обычные классификаторы.
• Усреднённый классификатор (Averaging classifier) — композиция бесконечного множества стохастических линейных классификаторов путём усреднения по всему апостериорному распределению.
• Теорема. Усреднённый классификатор является обычным (не стохастическим) линейным классификатором. Доказательство теоремы.
• Теорема. Вероятность ошибки усреднённого классификатора не превышает удвоенной ожидаемой вероятности ошибки стохастического классификатора. Доказательство теоремы.

Литература:

1. Langford J. Tutorial on Practical Prediction Theory for Classification. — 2005. — 28 с.
2. McAllester D. Simplified PAC-Bayesian Margin Bounds. — 2003.

Применение теории PAC-Bayes к голосованию правил

• Понятия логического правила (rule), закономерности, покрывающего набора правил (ruleset), ансамбля покрывающих наборов. Примеры прикладных задач.
• Стохастический алгоритм синтеза покрывающего набора. Конкретизация основной теоремы теории PAC-Bayes для ансамбля покрывающих наборов. Эмпирическая оценка апостериорного распределения по конкретному ансамблю покрывающих наборов.
• Теорема. Вероятность ошибки ансамбля покрывающих наборов оценивается сверху суммарной (по всем классам) ожидаемой вероятностью ошибки стохастического алгоритма.
• Теорема. Оценка обобщающей способности улучшается, если классификатору разрешено отказываться (abstain) от классификации.
• О практическом оценивании дивиргенции Кульбака-Лейблера между априорным и апостериорным распределениями. Эмпирическая оценка апостериорного распределения, основанная на модели белого шума.

Литература:

1. Ruckert U., Kramer S. Towards Tight Bounds for Rule Learning. — Proc. 21th International Conference on Machine Learning, Banff, Canada. — 2004. — 90 с.

Расслоение семейства алгоритмов (Shell bounds)

• Основная идея расслоения: подавляющее большинство алгоритмов имеют высокую вероятность ошибки (около 50%), и крайне маловероятно, что для них будет наблюдаться малая эмпирическая ошибка.
• Теорема. Оценка ненаблюдаемого расслоения (unobservable shell bound). Доказательство теоремы.
• Теорема. Оценка наблюдаемого расслоения (observable shell bound). Доказательство теоремы.
• Оценивание расслоения методом Монте-Карло.
• Теорема. Оценка по случайной равномерной выборке алгоритмов. Доказательство теоремы.
• Теорема. Обобщение на случай бесконечного семейства алгоритмов. Без доказательства.

Литература:

1. Langford J. Quantitatively Tight Sample Complexity Bounds (Chapter 8). — Carnegie Mellon Thesis. — 2002. — 124 с.

Прочее

Анализ смещения и разброса

• Разложение ошибки на смещение и разброс (bias-variance decomposition) для случая регрессии.
• Обобщения на случай классификации.
• Оценки для метода k ближайших соседей и для линейных композиций.

Оценки вероятности ошибки в задачах регрессии

• Линейная регрессия.
• Оценка матожидания ошибки для многомерной линейной регрессии.
• Теорема. Информационный критерий Акаике. Доказательство теоремы.
• Теорема. Байесовский информационный критерий. Доказательство теоремы.