Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)
Материал из MachineLearning.
Спецкурс знакомит студентов с современным состоянием теории вычислительного обучения (computational learning theory, COLT), исследующей проблему качества восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики {{S|В. Н. Вапник} и А. Я. Червоненкис. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время развивается очень активно, главным образом, за рубежом.
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными? Как избежать переобучения — ситуации, когда ответы алгоритма слишком точны на обучающей выборке, но недостаточно точны на новых данных, которые не были известны на этапе обучения? Как управлять обобщающей способностью алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
Цели спецкурса — научить студентов не только строить и применять обучаемые алгоритмы анализа данных, но и оценивать их надёжность; разрабатывать более надёжные алгоритмы; понимать возможные причины ненадёжной работы обучаемых алгоритмов в прикладных задачах классификации, регрессии, прогнозирования.
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по комбинаторной теории обобщающей способности и слабой вероятностной аксиоматике.
Курс читается студентам кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года.
Содержание |
Первый семестр
Второй семестр
Задача оценивания обобщающей способности и простейшие верхние оценки
- Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
- Биномиальное распределение.
- Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
- Обращение оценок.
- Теорема 1. Оценка вероятности ошибки фиксированного алгоритма (test set bound). Доказательство теоремы. Три следствия: применение трёх различных аппроксимаций хвоста биномиального распределения.
- Бритва Оккама (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.
