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

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

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

Содержание

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

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

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

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

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

На кафедре Интеллектуальные системы ФУПМ МФТИ данный курс является третьей частью трёхсеместрового курса Теория обучения машин.

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

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

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

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

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

Элементы теории Вапника-Червоненкиса

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

Точные комбинаторные оценки для модельных семейств алгоритмов

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

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

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

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

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

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

  • Логические алгоритмы классификации (rule learning). Примеры прикладных задач. Виды закономерностей: конъюнкции, синдромы, шары, полупространства.
  • Критерии информативности. Примеры. Двухкритериальная оптимизация в (p,n)-пространстве.
  • Теорема о монотонности метода максимизации информативности.
  • Теорема. Оценка расслоения-связности для частоты ошибок I и II рода.
  • Структура классов эквивалентности семейства конъюнкций пороговых предикатов.
  • Стандартные представители классов эквивалентности и граничные подмножества объектов.
  • Послойный восходящий алгоритм вычисления оценки расслоения-связности.
  • Модификация критериев информативности. Применение для отбора признаков. Результаты экспериментов.

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

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

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

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

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

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

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

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

Учебные материалы

Ссылки

Программы прошлых лет

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