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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Ссылки: переделал ссылку)
м Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)» переименована в «[[Теория надёжности обучения по прецедентам (кур)

Версия 09:57, 16 апреля 2011

Содержание

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

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

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

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

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


Учебное пособие по курсу ТНОП: Voron-2011-tnop.pdf, 2 МБ (черновая версия).


Комбинаторная теория переобучения

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

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

Предсказание частоты события и гипергеометрическое распределение

  • Задача предсказания частоты события. Выборочный контроль качества.
  • Лемма. Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
  • Теорема. Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках.
  • Геометрическая интерпретация.
  • Свойства гипергеометрического распределения. Методы вычисления гипергеометрического распределения.
  • Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.
  • Переход от ненаблюдаемой оцеки к наблюдаемой. Точная интервальная оценка. Вероятность нуль-события.

Теория Вапника-Червоненкиса

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

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

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

Принцип порождающих и запрещающих множеств

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

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

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

Оценки расслоения-связности

  • Граф расслоения-связности. Верхняя и нижняя связность и неоптимальность алгоритмов.
  • Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности.
  • h-мерная монотонная сеть алгоритмов.

Конъюнктивные логические закономерности

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

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

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

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

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

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

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

Радемахеровская сложность

  • Метод обучения, максимизирующий переобученность.
  • Понятие Радемахеровской сложности.
  • Оценка через принцип порождающих и запрещающих множеств.
  • Оценка через цепные разложения.
  • Точная оценка для монотонной цепи алгоритмов через случайное блуждание.

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

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

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

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

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

Литература

Ссылки

См. также

Личные инструменты