Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)
Материал из MachineLearning.
(Различия между версиями)
м |
|||
| Строка 172: | Строка 172: | ||
}} | }} | ||
| + | == Список подстраниц (wiki-лекции) == | ||
| + | |||
| + | {{Служебная:Prefixindex/Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)/}} | ||
[[Категория:Учебные курсы]] | [[Категория:Учебные курсы]] | ||
Версия 20:30, 15 апреля 2008
Спецкурс знакомит студентов с современным состоянием теории вычислительного обучения (computational learning theory, COLT), исследующей проблему качества восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики В. Н. Вапник и А. Я. Червоненкис. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время развивается очень активно, главным образом, за рубежом.
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными? Как избежать переобучения — ситуации, когда ответы алгоритма слишком точны на обучающей выборке, но недостаточно точны на новых данных, которые не были известны на этапе обучения? Как управлять обобщающей способностью алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
Цели спецкурса — научить студентов не только строить и применять обучаемые алгоритмы анализа данных, но и оценивать их надёжность; разрабатывать более надёжные алгоритмы; понимать возможные причины ненадёжной работы обучаемых алгоритмов в прикладных задачах классификации, регрессии, прогнозирования.
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по комбинаторной теории обобщающей способности и слабой вероятностной аксиоматике.
Курс читается студентам кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года.
Первый семестр
Задачи эмпирического предсказания
- Понятия наблюдаемой и скрытой выборки.
- Точность и надёжность предсказаний.
- Примеры задач эмпирического предсказания в теории вероятностей, математической статистике, в прикладных областях.
- Слабая вероятностная аксиоматика. Сравнение с колмогоровской аксиоматикой, достоинства, недостатки и границы применимости.
Задача предсказания частоты события
- Теорема 1. Точная оценка частоты события на скрытой выборке в слабой аксиоматике. Доказательство теоремы.
- Свойства гипергеометрического распределения.
- Оценивание частоты события на полной выборке.
Задача о равномерном отклонении эмпирических распределений
- Теоремы Колмогорова и Смирнова (без доказательства).
- Усечённый треугольник Паскаля. Связь с задачами о случайном блуждании и разорении игрока.
- Теорема 2. Точная оценка в слабой аксиоматике. Доказательство теоремы. Геометрические интерпретации.
Задача обучения по прецедентам
- Понятие обобщающей способности, принцип скользящего контроля.
- Понятиия коэффициента разнообразия и профиля разнообразия. Локальная и глобальная функция роста.
- Теорема 3 (Вапника-Червоненкиса). Оценка надёжности обучения по контрольным данным. Доказательство теоремы.
- Обращение оценки.
- Метод структурной минимизации риска. Связь проблемы переобучения со сложностью алгоритма и сложностью выборки. Проблема завышенности оценок.
Ёмкость некоторых семейств алгоритмов
- Ёмкость конечных множеств, принцип минимума длины описания.
- Теорема 4. Ёмкость семейства конъюнкций элементарных пороговых условий. Доказательство теоремы.
- Теорема 5. Ёмкость семейства линейных разделяющих правил. Доказательство теоремы.
- Пример однопараметрического семейства бесконечной ёмкости.
- Ёмкость нейронных сетей (без доказательства).
Комбинаторные оценки скользящего контроля для метода ближайших соседей
- Метод ближайших соседей.
- Понятие профиля компактности.
- Теорема 6. Точная оценка скользящего контроля для метода одного ближайшего соседа (1NN). Доказательство теоремы.
- Разделение объектов на шумовые, опорные и неинформативные.
- Точная оценка скользящего контроля для метода k ближайших соседей (kNN).
Комбинаторные оценки скользящего контроля для монотонных классификаторов
- Монотонные алгоритмы классификации.
- Понятие клина объекта. Профиль монотонности выборки.
- Теорема 7. Верхняя оценка скользящего контроля. Доказательство теоремы.
- Монотонные корректирующие операции в алгоритмических композициях.
- Критерии настройки базовых алгоритмов на основе оценок обобщающей способности.
Анализ смещения и разброса (bias and variance)
- Анализ смещения и разброса (bias and variance).
- Оценки для метода k ближайших соседей и для линейных композиций.
Второй семестр
Задача оценивания обобщающей способности и простейшие верхние оценки
- Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
- Биномиальное распределение.
- Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
- Обращение оценок.
- Теорема 1. Оценка вероятности ошибки фиксированного алгоритма (test set bound). Доказательство теоремы. Три следствия: применение трёх различных аппроксимаций хвоста биномиального распределения.
Литература:
- Langford J. Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.
Бритва Оккама (Occam Razor)
- Понятия априорного распределения на множестве алгоритмов.
- Теорема 2. Оценка вероятности ошибки для произвольного алгоритма (Occam razor bound). Доказательство теоремы. Три следствия: применение аппроксимаций и оценка Вапника-Червоненкиса.
- Метод структурной минимизации риска (Вапника-Червоненкиса).
- Теорема 3. Об оптимальном априорном распределении. Доказательство теоремы.
- Открытые проблемы.
Литература:
- Langford J. Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.
Стохастические классификаторы и теория PAC-Bayes
- Стохастические классификаторы. Понятия ожидаемой эмпирической ошибки и ожидаемой вероятности ошибок.
- Теорема 1. Основная теорема теории PAC-Bayes. Доказательство теоремы.
Литература:
- Langford J. Tutorial on Practical Prediction Theory for Classification. — 2005. — 28 с.
Применение теории PAC-Bayes к линейным классификаторам
- Линейный классификатор, понятие отступа (margin), распределение отступов.
- Принцип минимизации эмпирического риска и принцип максимизации отступов. Замена пороговой функции потерь на её непрерывную аппроксимацию.
- Краткая история обоснований принципа максимизации отступов. О завышенности оценок обобщающей способности.
- Теорема 2. Конкретизация основной теоремы теории PAC-Bayes для линейных классификаторов. Доказательство теоремы. Выбор априорного и апостериорного распределений. Следствие: ещё одна аппроксимация пороговой функции потерь.
- Проблема правомерности переноса результатов, полученных для стохастических классификаторов, на обычные классификаторы.
- Усреднённый классификатор (Averaging classifier) — композиция бесконечного множества стохастических линейных классификаторов путём усреднения по всему апостериорному распределению.
- Теорема 3. Усреднённый классификатор является обычным (не стохастическим) линейным классификатором. Доказательство теоремы.
- Теорема 4. Вероятность ошибки усреднённого классификатора не превышает удвоенной ожидаемой вероятности ошибки стохастического классификатора. Доказательство теоремы.
Литература:
- 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 для ансамбля покрывающих наборов. Эмпирическая оценка апостериорного распределения по конкретному ансамблю покрывающих наборов.
- Теорема 5. Вероятность ошибки ансамбля покрывающих наборов оценивается сверху суммарной (по всем классам) ожидаемой вероятностью ошибки стохастического алгоритма.
- Теорема 6. Оценка обобщающей способности улучшается, если классификатору разрешено отказываться (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%), и крайне маловероятно, что для них будет наблюдаться малая эмпирическая ошибка.
- Теорема 1. Оценка, основанная на ненаблюдаемой информации (full knowledge bound). Доказательство теоремы.
- Теорема 2. Оценка по наблюдаемой информации является верхней. Доказательство на следующей лекции.
- Теорема 3. Оценка по случайной равномерной выборке алгоритмов. Доказательство теоремы.
Литература:
- Langford J. Chapter 8 // Quantitatively Tight Sample Complexity Bounds. — Carnegie Mellon Thesis. — 2002. — 124 с.
