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

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

Содержание 1 Комбинаторные методы в математической статистике 1.1 Предсказание частоты события и закон больших чисел 1.2 Обращение оценок 1.3 Оценки равномерного отклонения эмпирических распределений 1.4 Непараметрические статистические критерии 2 Основы теории статистического обучения (теория Вапника-Червоненкиса) 2.1 Задача обучения по прецедентам 2.2 Размерность Вапника-Червоненкиса (ёмкость) 2.3 Микровыборы и статистические запросы 2.4 Неравенства типа Бонферрони 2.5 Эксперименты по эмпирическому измерению факторов завышенности 2.6 Влияние различности алгоритмов на вероятность переобучения 3 Точные комбинаторные оценки обобщающей способности 3.1 Общая точная оценка вероятности переобучения 3.2 Монотонные и унимодальные цепочки алгоритмов 3.3 Пары и тройки алгоритмов 3.4 Оценки скользящего контроля для метода ближайших соседей 3.5 Оценки скользящего контроля для монотонных классификаторов 4 Вероятностная байесовская теория обобщающей способности 4.1 Простейшие оценки вероятности ошибки классификации 4.2 Бритва Оккама (Occam Razor) 4.3 Стохастические классификаторы и теория PAC-Bayes 4.4 Применение теории PAC-Bayes к линейным классификаторам 4.5 Применение теории PAC-Bayes к голосованию правил 4.6 Расслоение семейства алгоритмов (Shell bounds) 5 Прочее 5.1 Анализ смещения и разброса 5.2 Оценки вероятности ошибки в задачах регрессии

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эксперименты по эмпирическому измерению факторов завышенности

• Эмпирическое оценивание вероятности переобучения (метод Монте-Карло). Скользящий контроль.
• Разложение степени завышенности оценки Вапника-Червоненкиса в произведение факторов завышенности.
• Логические алгоритмы классификации. Понятия закономерности и информативности. Алгоритм синтеза информативных конъюнкций.
• Обобщение понятий частоты ошибок, метода обучения, коэффициента разнообразия для случая закономерностей. Обобщение теоремы Вапника-Червоненкиса.
• Численные результаты экспериментов. Выводы об относительной значимости факторов завышенности.

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

• Понятия цепочки алгоритмов и связности семейства алгоритмов с непрерывностью дискриминантной функции.
• Вероятность переобучения для цепочки алгоритмов. Постановка эксперимента с методом минимизации эмпирического риска. Результаты экспериментов и выводы.
• Условия, при которых принцип равномерной сходимости не приводит к завышенности оценок для метода минимизации эмпирического риска.

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

Материал по этой части курса: Эффекты расслоения и сходства в семействах алгоритмов и их влияние на вероятность переобучения. 2009. PDF, 354 КБ. Точные оценки вероятности переобучения. 2009. PDF, 336 КБ. Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2009. PDF, 180 КБ.

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

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

Монотонные и унимодальные цепочки алгоритмов

• Понятие монотонной цепочки. Пример.
• Теорема о монотонной цепочке.
• Обсуждение результатов численного расчёта.
• Понятие унимодальной цепочки. Пример.
• Теорема об унимодальной цепочке.
• Открытые проблемы. Влияние размерности пространства параметров на вероятность переобучения.

Пары и тройки алгоритмов

• Постановка задачи.
• Теорема о вероятности переобучения для двухэлементного семейства алгоритмов. Доказательство теоремы.
• Теорема о вероятности переобучения для трёхэлементного семейства алгоритмов (без доказательства).
• Частные случаи и обсуждение результатов численного расчёта.

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

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

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

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

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

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

• Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
• Биномиальное распределение.
• Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
• Обращение оценок.
• Теорема. Оценка вероятности ошибки фиксированного алгоритма (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 с.

Стохастические классификаторы и теория 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 ближайших соседей и для линейных композиций.

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

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