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

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

Версия 11:59, 20 августа 2008

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

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

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

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

Спецкурс читается студентам кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года.

Спецкурс читается параллельно с основным кафедральным курсом Математические методы распознавания образов (ММРО). Некоторые лекции спецкурса смыкаются с соответствующими лекциями курса ММРО или опираются на ихматериал, что специально отмечено в программе.

Первый семестр

Лекция 1. Задачи эмпирического предсказания

Связь с курсом ММРО: задача обучения по прецедентам, принцип полного скользящего контроля, вероятностная постановка задачи.

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

Лекция 2. Задача предсказания частоты события

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

Лекция 3. Задача о равномерном отклонении эмпирических распределений

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

Лекция 4. Ранговые статистики и критерии

• Ещё раз о задачах проверки статистических гипотез: гипотеза однородности, гипотеза сдвига.
• Доверительное оценивание.
• Доверительный интервал для медианы.
• Критерий знаков.
• Критерий Уилкоксона-Манна-Уитни.
• Критерий серий.

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

Связь с курсом ММРО: метрические алгоритмы классификации, метод ближайших соседей.

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

Лекция 6. Задача обучения по прецедентам

• Понятия обобщающей способности, вероятности переобучения. Принцип полного скользящего контроля.
• Оценка надёжности обучения по контрольным данным (test set bound).
• Профиль разнообразия (shatter profile), коэффициент разнообразия (shatter coefficient), функция роста.
• Теорема Вапника-Червоненкиса. Доказательство теоремы.
• Обращение оценки.
• Метод структурной минимизации риска.
• Принцип равномерной сходимости частоты к вероятности.
• Проблема завышенности оценок.

Лекция 7. Ёмкость некоторых семейств алгоритмов

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

Лекция 8. Микровыборы и статистические запросы

• Методы обучения, основанные на статистических запросах (statistical queries learning).
• Примеры алгоритмов. Решающие списки и решающие деревья.
• Дерево микровыборов.
• Оценки вероятности переобучения, основанные на микровыборах (microchoice bounds).
• Адаптивные оценки, основанные на микровыборах (adaptive microchoice bounds).
• Самоограничивающие методы обучения (self-bounding по Фройнду).

Лекция 9. Расслоение семейства алгоритмов

• Расслоение (shell) семейства алгоритмов по качеству.
• Теорема. Оценка ненаблюдаемого расслоения (unobservable shell bound). Доказательство теоремы.
• Теорема. Оценка наблюдаемого расслоения (observable shell bound). Доказательство теоремы.
• Оценивание расслоения методом Монте-Карло.

Лекция 10. Влияние различности алгоритмов на вероятность переобучения

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

Лекция 11. Анализ смещения и разброса

• Разложение ошибки на смещение и разброс (bias-variance decomposition) для случая регрессии.
• Обобщения на случай классификации.
• Оценки для метода k ближайших соседей и для линейных композиций.

Лекция 12. Оценки переобучения для многомерной линейной регрессии

Связь с курсом ММРО: линейная регрессия.

• Оценка матожидания ошибки для многомерной линейной регрессии.
• Теорема. Информационный критерий Акаике. Доказательство теоремы.
• Теорема. Байесовский информационный критерий. Доказательство теоремы.

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

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

Второй семестр

Задача оценивания обобщающей способности и простейшие верхние оценки

• Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
• Биномиальное распределение.
• Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
• Обращение оценок.
• Теорема. Оценка вероятности ошибки фиксированного алгоритма (test set bound). Доказательство теоремы. Три следствия: применение трёх различных аппроксимаций хвоста биномиального распределения.

Текст лекции

Литература:

1. Langford J. Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.

Бритва Оккама (Occam Razor)

• Понятия априорного распределения на множестве алгоритмов.
• Теорема. Оценка вероятности ошибки для произвольного алгоритма (Occam razor bound). Доказательство теоремы. Три следствия: применение аппроксимаций и оценка Вапника-Червоненкиса.
• Метод структурной минимизации риска (Вапника-Червоненкиса).
• Теорема. Об оптимальном априорном распределении. Доказательство теоремы.
• Открытые проблемы.

Текст лекции

Литература:

1. Langford J. Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.

Стохастические классификаторы и теория PAC-Bayes

• Стохастические классификаторы. Понятия ожидаемой эмпирической ошибки и ожидаемой вероятности ошибок.
• Теорема. Основная теорема теории PAC-Bayes. Доказательство теоремы.

Текст лекции

Литература:

1. Langford J. Tutorial on Practical Prediction Theory for Classification. — 2005. — 28 с.

Применение теории PAC-Bayes к линейным классификаторам

• Линейный классификатор, понятие отступа (margin), распределение отступов.
• Принцип минимизации эмпирического риска и принцип максимизации отступов. Замена пороговой функции потерь на её непрерывную аппроксимацию.
• Краткая история обоснований принципа максимизации отступов. О завышенности оценок обобщающей способности.
• Теорема. Конкретизация основной теоремы теории PAC-Bayes для линейных классификаторов. Доказательство теоремы. Выбор априорного и апостериорного распределений. Следствие: ещё одна аппроксимация пороговой функции потерь.
• Проблема правомерности переноса результатов, полученных для стохастических классификаторов, на обычные классификаторы.
• Усреднённый классификатор (Averaging classifier) — композиция бесконечного множества стохастических линейных классификаторов путём усреднения по всему апостериорному распределению.
• Теорема. Усреднённый классификатор является обычным (не стохастическим) линейным классификатором. Доказательство теоремы.
• Теорема. Вероятность ошибки усреднённого классификатора не превышает удвоенной ожидаемой вероятности ошибки стохастического классификатора. Доказательство теоремы.

Текст лекции

Литература:

1. Langford J. Tutorial on Practical Prediction Theory for Classification. — 2005. — 28 с.
2. McAllester D. Simplified PAC-Bayesian Margin Bounds. — 2003.

Применение теории PAC-Bayes к алгоритму голосования по наборам правил

• Понятия логического правила (rule), закономерности, покрывающего набора правил (ruleset), ансамбля покрывающих наборов. Примеры прикладных задач.
• Стохастический алгоритм синтеза покрывающего набора. Конкретизация основной теоремы теории PAC-Bayes для ансамбля покрывающих наборов. Эмпирическая оценка апостериорного распределения по конкретному ансамблю покрывающих наборов.
• Теорема. Вероятность ошибки ансамбля покрывающих наборов оценивается сверху суммарной (по всем классам) ожидаемой вероятностью ошибки стохастического алгоритма.
• Теорема. Оценка обобщающей способности улучшается, если классификатору разрешено отказываться (abstain) от классификации.
• О практическом оценивании дивиргенции Кульбака-Лейблера между априорным и апостериорным распределениями. Эмпирическая оценка апостериорного распределения, основанная на модели белого шума.

Текст лекции

Литература:

1. Ruckert U., Kramer S. Towards Tight Bounds for Rule Learning. — Proc. 21th International Conference on Machine Learning, Banff, Canada. — 2004. — 90 с.

Расслоение семейства алгоритмов (Shell bounds)

• Основная идея расслоения: подавляющее большинство алгоритмов имеют высокую вероятность ошибки (около 50%), и крайне маловероятно, что для них будет наблюдаться малая эмпирическая ошибка.
• Теорема. Оценка, основанная на ненаблюдаемой информации (full knowledge bound). Доказательство теоремы.
• Теорема. Оценка по наблюдаемой информации является верхней. Доказательство теоремы.
• Теорема. Оценка по случайной равномерной выборке алгоритмов. Доказательство теоремы.
• Теорема. Обобщение на случай бесконечного семейства алгоритмов. Без доказательства.

Текст лекции

Литература:

1. Langford J. Quantitatively Tight Sample Complexity Bounds (Chapter 8). — Carnegie Mellon Thesis. — 2002. — 124 с.

Список подстраниц (wiki-лекции)