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

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

Версия 16:58, 4 февраля 2012

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с.  (подробнее).
• Воронцов К. В. Слабая вероятностная аксиоматика. 2009. PDF, 832 КБ.
• Воронцов К. В. Эффекты расслоения и сходства в семействах алгоритмов и их влияние на вероятность переобучения. 2009. PDF, 354 КБ.
• Воронцов К. В. Точные оценки вероятности переобучения. 2009. PDF, 542 КБ.

Ссылки

• Расслоение и сходство алгоритмов (виртуальный семинар)
• Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2010. PDF, 183 КБ.

См. также

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