Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)
Материал из MachineLearning.
Спецкурс знакомит студентов с современным состоянием теории вычислительного обучения (computational learning theory, COLT), исследующей проблему качества восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики В. Н. Вапник и А. Я. Червоненкис. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время развивается очень активно, главным образом, за рубежом.
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными? Как избежать переобучения — ситуации, когда ответы алгоритма слишком точны на обучающей выборке, но недостаточно точны на новых данных, которые не были известны на этапе обучения? Как управлять обобщающей способностью алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
Цели спецкурса — научить студентов не только строить и применять обучаемые алгоритмы анализа данных, но и оценивать их надёжность; разрабатывать более надёжные алгоритмы; понимать возможные причины ненадёжной работы обучаемых алгоритмов в прикладных задачах классификации, регрессии, прогнозирования.
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по комбинаторной теории обобщающей способности и слабой вероятностной аксиоматике.
Спецкурс читается студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года, в дополнение к обязательному кафедральному курсу Математические методы распознавания образов (ММРО). Некоторые лекции спецкурса являются непосредственным продолжением соответствующих лекций ММРО, что специально отмечено в программе.
Часть I. Надёжность эмпирических предсказаний
Предсказание частоты события и закон больших чисел
- Задача эмпирического предсказания в общей постановке. Понятия наблюдаемой и скрытой выборки. Точность и надёжность предсказаний.
- Слабая вероятностная аксиоматика. Перенос оценок из слабой аксиоматики в сильную (колмогоровскую). Сравнение с колмогоровской аксиоматикой, достоинства, недостатки и границы применимости.
- Задача предсказания частоты события. Примеры приложений: выборочный контроль качества, оценивание качества алгоритма классификации.
- Лемма. Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
- Теорема. Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках. Доказательство теоремы.
- Геометрическая интерпретация.
- Асимптотическая оценка. Закон больших чисел в слабой аксиоматике.
- Свойства гипергеометрического распределения. Алгоритм табулирования гипергеометрического распределения.
Обращение оценок
- Проблема: оценка вероятности большого уклонения зависит от оцениваемой величины — числа ошибок на полной выборке. Что с этим делать?
- Определение обратной функции для кусочно-постоянных функций.
- Лемма об обращении оценок.
- Обращение точной оценки вероятности большого уклонения частот события на наблюдаемой и скрытой выборках.
- Алгоритм вычисления верхней оценки частоты события на скрытой выборке.
- Экспоненциальная верхняя оценка и её обращение.
Задача обучения по прецедентам
- Основные понятия: алгоритм, метод обучения, переобучение. Примеры приложений: кредитный скоринг, медицинская диагностика.
- Функционал вероятности переобучения в слабой аксиоматике; полный скользящий контроль.
- Коэффициент разнообразия (shatter coefficient), профиль разнообразия (shatter profile), функция роста.
- Теорема Вапника-Червоненкиса. Доказательство теоремы.
- Обращение оценки.
- Метод структурной минимизации риска.
- Достаточная длина обучающей выборки.
- Проблема завышенности оценок. Основные причины завышенности.
Размерность Вапника-Червоненкиса (ёмкость)
- Понятие ёмкости.
- Функция
, её связь с треугольником Паскаля.
- Лемма о функции
- Теорема. Выражение функции роста через ёмкость. Доказательство теоремы.
- Ёмкость конечных множеств. Принцип минимума длины описания.
- Теорема. Ёмкость семейства линейных разделяющих правил. Доказательство теоремы.
- Пример однопараметрического семейства бесконечной ёмкости.
- Теорема. Ёмкость семейства конъюнкций элементарных пороговых условий. Доказательство теоремы.
- Ёмкость некоторых разновидностей нейронных сетей (без доказательства).
Эксперименты по эмпирическому измерению факторов завышенности
- Логические алгоритмы классификации. Понятия закономерности и информативности. Алгоритм синтеза конъюнкций.
- Обобщение понятий частоты ошибок, метода обучения, коэффициента разнообразия для случая закономерностей. Обобщение теоремы Вапника-Червоненкиса.
- Эмпирическое оценивание вероятности переобучения (метод Монте-Карло). Скользящий контроль.
- Разложение степени завышенности оценки Вапника-Червоненкиса в произведение четырёх факторов завышенности.
- Численные результаты экспериментов.
Влияние различности алгоритмов на вероятность переобучения
- Теорема. Оценка вероятности переобучения для пары алгоритмов. Доказательство теоремы.
- Понятие цепочки алгоритмов, связь цепочки с непрерывностью дискриминантной функции по параметрам.
- Вероятность переобучения для цепочки алгоритмов. Постановка эксперимента с методом минимизации эмпирического риска. Результаты экспериментов и выводы.
- Условия, при которых принцип равномерной сходимости не приводит к завышенности оценок для метода минимизации эмпирического риска.
- Открытые проблемы. Влияние размерности пространства параметров на вероятность переобучения.
- О неравенствах типа Бонферрони.
Микровыборы и статистические запросы
- Упрощённое доказательство теоремы Вапника-Червоненкиса. Принцип равномерной сходимости частоты к вероятности. Принцип бритвы Оккама.
- Оценка надёжности обучения по контрольным данным (test set bound).
- Методы обучения, основанные на статистических запросах (statistical queries learning).
- Примеры алгоритмов. Решающие списки и решающие деревья.
- Дерево микровыборов.
- Оценки вероятности переобучения, основанные на микровыборах (microchoice bounds).
- Адаптивные оценки, основанные на микровыборах (adaptive microchoice bounds).
- Самоограничивающие методы обучения (self-bounding по Фройнду).
Задача о равномерном отклонении эмпирических распределений
- Задача оценивания функции распределения как задача эмпирического предсказания.
- Теоремы Колмогорова и Смирнова (без доказательства).
- Усечённый треугольник Паскаля. Связь с задачами о случайном блуждании и разорении игрока.
- Теорема. Точная оценка вероятности больших отклонений эмпирических распределений. Доказательство теоремы. Геометрические интерпретации.
- Оценивание функции распределения на полной выборке.
- Обобщение на случай вариационного ряда со связками.
- Критерий Смирнова.
Непараметрические статистические критерии
- Задачи проверки статистических гипотез.
- Гипотеза однородности, гипотеза сдвига.
- Доверительное оценивание.
- Доверительный интервал для медианы.
- Критерий знаков.
- Критерий Уилкоксона-Манна-Уитни.
- Критерий серий.
Часть II. Комбинаторная теория обобщающей способности
Оценки скользящего контроля для метода ближайших соседей
Связь с курсом ММРО: метрические алгоритмы классификации, метод ближайших соседей.
- Понятие профиля компактности.
- Теорема. Точное выражение функционала полного скользящего контроля для метода одного ближайшего соседа (1NN). Доказательство теоремы.
- Свойства профилей компактности.
- Разделение объектов на шумовые, эталонные и неинформативные. Алгоритм выделения эталонных объектов.
- Теорема. Точное выражение функционала полного скользящего контроля для метода k ближайших соседей (kNN).
Оценки скользящего контроля для монотонных классификаторов
- Монотонные алгоритмы классификации.
- Понятие клина объекта. Профиль монотонности выборки.
- Теорема. Верхняя оценка скользящего контроля. Доказательство теоремы.
- Монотонные корректирующие операции в алгоритмических композициях.
- Критерии настройки базовых алгоритмов на основе оценок обобщающей способности.
Часть III. Вероятностная теория обобщающей способности
Простейшие оценки вероятности ошибки классификации
- Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
- Биномиальное распределение.
- Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
- Обращение оценок.
- Теорема. Оценка вероятности ошибки фиксированного алгоритма (test set bound). Доказательство теоремы. Три следствия: применение трёх различных аппроксимаций хвоста биномиального распределения.
Литература:
- Langford J. Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.
Бритва Оккама (Occam Razor)
- Понятия априорного распределения на множестве алгоритмов.
- Теорема. Оценка вероятности ошибки для произвольного алгоритма (Occam razor bound). Доказательство теоремы. Три следствия: применение аппроксимаций и оценка Вапника-Червоненкиса.
- Метод структурной минимизации риска (Вапника-Червоненкиса).
- Теорема. Об оптимальном априорном распределении. Доказательство теоремы.
- Открытые проблемы.
Литература:
- Langford J. Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.
Стохастические классификаторы и теория PAC-Bayes
- Стохастические классификаторы. Понятия ожидаемой эмпирической ошибки и ожидаемой вероятности ошибок.
- Теорема. Основная теорема теории PAC-Bayes. Доказательство теоремы.
Литература:
- Langford J. Tutorial on Practical Prediction Theory for Classification. — 2005. — 28 с.
Применение теории PAC-Bayes к линейным классификаторам
- Линейный классификатор, понятие отступа (margin), распределение отступов.
- Принцип минимизации эмпирического риска и принцип максимизации отступов. Замена пороговой функции потерь на её непрерывную аппроксимацию.
- Краткая история обоснований принципа максимизации отступов. О завышенности оценок обобщающей способности.
- Теорема. Конкретизация основной теоремы теории PAC-Bayes для линейных классификаторов. Доказательство теоремы. Выбор априорного и апостериорного распределений. Следствие: ещё одна аппроксимация пороговой функции потерь.
- Проблема правомерности переноса результатов, полученных для стохастических классификаторов, на обычные классификаторы.
- Усреднённый классификатор (Averaging classifier) — композиция бесконечного множества стохастических линейных классификаторов путём усреднения по всему апостериорному распределению.
- Теорема. Усреднённый классификатор является обычным (не стохастическим) линейным классификатором. Доказательство теоремы.
- Теорема. Вероятность ошибки усреднённого классификатора не превышает удвоенной ожидаемой вероятности ошибки стохастического классификатора. Доказательство теоремы.
Литература:
- Langford J. Tutorial on Practical Prediction Theory for Classification. — 2005. — 28 с.
- McAllester D. Simplified PAC-Bayesian Margin Bounds. — 2003.
Применение теории PAC-Bayes к голосованию правил
- Понятия логического правила (rule), закономерности, покрывающего набора правил (ruleset), ансамбля покрывающих наборов. Примеры прикладных задач.
- Стохастический алгоритм синтеза покрывающего набора. Конкретизация основной теоремы теории PAC-Bayes для ансамбля покрывающих наборов. Эмпирическая оценка апостериорного распределения по конкретному ансамблю покрывающих наборов.
- Теорема. Вероятность ошибки ансамбля покрывающих наборов оценивается сверху суммарной (по всем классам) ожидаемой вероятностью ошибки стохастического алгоритма.
- Теорема. Оценка обобщающей способности улучшается, если классификатору разрешено отказываться (abstain) от классификации.
- О практическом оценивании дивиргенции Кульбака-Лейблера между априорным и апостериорным распределениями. Эмпирическая оценка апостериорного распределения, основанная на модели белого шума.
Литература:
- 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). Доказательство теоремы.
- Оценивание расслоения методом Монте-Карло.
- Теорема. Оценка по случайной равномерной выборке алгоритмов. Доказательство теоремы.
- Теорема. Обобщение на случай бесконечного семейства алгоритмов. Без доказательства.
Литература:
- Langford J. Quantitatively Tight Sample Complexity Bounds (Chapter 8). — Carnegie Mellon Thesis. — 2002. — 124 с.
Прочее
Анализ смещения и разброса
- Разложение ошибки на смещение и разброс (bias-variance decomposition) для случая регрессии.
- Обобщения на случай классификации.
- Оценки для метода k ближайших соседей и для линейных композиций.
Оценки вероятности ошибки в задачах регрессии
Связь с курсом ММРО: линейная регрессия.
- Оценка матожидания ошибки для многомерной линейной регрессии.
- Теорема. Информационный критерий Акаике. Доказательство теоремы.
- Теорема. Байесовский информационный критерий. Доказательство теоремы.
