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

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

Перейти к: навигация, поиск

Содержание

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

Программа спецкурса, прочитанного на кафедре ММП ВМК МГУ весной 2010 года.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература:

  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).
  • Свойства профилей компактности.
  • Алгоритм выделения эталонных объектов. Функция вклада объекта и её эффективное вычисление. Метрические деревья.
  • Разделение объектов на шумовые, эталонные и неинформативные.

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

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

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

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

  • Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 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 ближайших соседей и для линейных композиций.

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

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BD%D0%B0%D0%B4%D1%91%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BF%D0%BE_%D0%BF%D1%80%D0%B5%D1%86%D0%B5%D0%B4%D0%B5%D0%BD%D1%82%D0%B0%D0%BC_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A._%D0%92._%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2%29/2010»