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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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