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

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

(Различия между версиями)
Перейти к: навигация, поиск
(литература, обновление сборника задач)
(Курс весна - 2011, ВМК МГУ)
Строка 1: Строка 1:
{{TOCright}}
{{TOCright}}
-
Спецкурс знакомит студентов с современным состоянием [[теория вычислительного обучения|теории вычислительного обучения]] (computational learning theory, COLT), исследующей проблему качества восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики [[Вапник, Владимир Наумович|{{S|В. Н. Вапник}}]] и [[Червоненкис, Алексей Яковлевич|{{S|А. Я. Червоненкис}}]]. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время развивается очень активно, главным образом, за рубежом.
+
Спецкурс знакомит студентов с современным состоянием [[теория вычислительного обучения|теории вычислительного обучения]] (computational learning theory, COLT), исследующей проблему качества восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики [[Вапник, Владимир Наумович|{{S|В. Н. Вапник}}]] и [[Червоненкис, Алексей Яковлевич|{{S|А. Я. Червоненкис}}]]. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время развивается очень активно.
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными? Как избежать [[Переобучение|переобучения]] — ситуации, когда ответы алгоритма слишком точны на обучающей выборке, но недостаточно точны на новых данных, которые не были известны на этапе обучения? Как управлять [[обобщающая способность|обобщающей способностью]] алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными? Как избежать [[Переобучение|переобучения]] — ситуации, когда ответы алгоритма слишком точны на обучающей выборке, но недостаточно точны на новых данных, которые не были известны на этапе обучения? Как управлять [[обобщающая способность|обобщающей способностью]] алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
Строка 8: Строка 8:
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по комбинаторной теории обобщающей способности и [[Слабая вероятностная аксиоматика|слабой вероятностной аксиоматике]].
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по комбинаторной теории обобщающей способности и [[Слабая вероятностная аксиоматика|слабой вероятностной аксиоматике]].
-
Спецкурс читается студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года, в дополнение к обязательному кафедральному курсу [[Машинное обучение (курс лекций, К.В.Воронцов)|Математические методы распознавания образов (ММРО)]]. Некоторые лекции спецкурса являются непосредственным продолжением соответствующих лекций ММРО, что специально отмечено в программе.
+
Спецкурс читается студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года, в дополнение к обязательному кафедральному курсу [[Машинное обучение (курс лекций, К.В.Воронцов)|Математические методы распознавания образов (ММРО)]].
'''Сборник задач''' по спецкурсу «Теория надёжности обучения по прецедентам»: [[Media:Voron09problems.pdf|PDF, 183 КБ]].
'''Сборник задач''' по спецкурсу «Теория надёжности обучения по прецедентам»: [[Media:Voron09problems.pdf|PDF, 183 КБ]].
-
== Комбинаторные методы в математической статистике ==
+
== Комбинаторная теория переобучения ==
-
=== Предсказание частоты события и закон больших чисел ===
+
=== Проблема переобучения и перестановочная вероятность ===
-
* Задача эмпирического предсказания в общей постановке. Понятия наблюдаемой и скрытой выборки. Точность и надёжность предсказаний.
+
* Задача обучения по прецедентам. Матрица ошибок. Понятия наблюдаемой и скрытой выборки. Проблема переобучения. Примеры приложений.
-
* [[Слабая вероятностная аксиоматика]]. Перенос оценок из слабой аксиоматики в сильную (колмогоровскую). Финитарные и инфинитарные вероятности. Сравнение с колмогоровской аксиоматикой, достоинства, недостатки и границы применимости.
+
* [[Слабая вероятностная аксиоматика]]. Вероятности переобучения. Перенос оценок из слабой аксиоматики в сильную (колмогоровскую).
-
* Задача предсказания частоты события. Примеры приложений: [[выборочный контроль качества]], оценивание качества алгоритма классификации.
+
* Точность и надёжность предсказаний. Обращение оценок.
 +
* Эмпирические оценки. Скользящий контроль.
 +
* Финитарные и инфинитарные вероятности. Сравнение с колмогоровской аксиоматикой, достоинства, недостатки и границы применимости.
 +
 
 +
=== Предсказание частоты события и гипергеометрическое распределение ===
 +
* Задача предсказания частоты события. [[Выборочный контроль качества]].
* '''Лемма.''' Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
* '''Лемма.''' Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
-
* '''Теорема.''' Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках. Доказательство теоремы.
+
* '''Теорема.''' Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках.
* Геометрическая интерпретация.
* Геометрическая интерпретация.
* Свойства [[Гипергеометрическое распределение|гипергеометрического распределения]]. Методы вычисления гипергеометрического распределения.
* Свойства [[Гипергеометрическое распределение|гипергеометрического распределения]]. Методы вычисления гипергеометрического распределения.
* Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.
* Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.
 +
* Переход от ненаблюдаемой оцеки к наблюдаемой. Точная интервальная оценка. Вероятность нуль-события.
-
=== Обращение оценок ===
+
=== Теория Вапника-Червоненкиса ===
-
* Парадокс: оценка вероятности большого уклонения частот зависит от оцениваемой величины — числа ошибок на полной выборке.
+
-
* Экспоненциальная верхняя оценка вероятности большого уклонения частот, её обращение и «грубое» устранение парадокса.
+
-
* Обращение кусочно-постоянных функций.
+
-
* Переход от ненаблюдаемой оценки к наблюдаемой: общая постановка проблемы; одномерный случай.
+
-
* Обращение точной верхней оценки частоты события на скрытой выборке; «аккуратное» устранение парадокса.
+
-
* Интервальная оценка частоты нуль-события на скрытой выборке.
+
-
 
+
-
=== Оценки равномерного отклонения эмпирических распределений ===
+
-
* Задача оценивания функции распределения как задача эмпирического предсказания.
+
-
* Теоремы Колмогорова и Смирнова (без доказательства).
+
-
* Усечённый треугольник Паскаля. Связь с задачами о случайном блуждании и разорении игрока.
+
-
* '''Теорема.''' Точная оценка вероятности больших отклонений эмпирических распределений. Доказательство теоремы. Геометрические интерпретации.
+
-
* Оценивание функции распределения на полной выборке.
+
-
* Обобщение на случай вариационного ряда со связками. Почему в этом случае задача предсказания намного сложнее.
+
-
 
+
-
=== Непараметрические статистические критерии ===
+
-
* Задачи [[Проверка статистических гипотез|проверки статистических гипотез]].
+
-
* [[Гипотеза однородности]], [[гипотеза сдвига]].
+
-
* Принципиальное различие задач эмпирического предсказания и проверки статистических гипотез.
+
-
* [[Критерий знаков]].
+
-
* [[Критерий Уилкоксона-Манна-Уитни]].
+
-
* [[Критерий серий]].
+
-
* [[Критерий Смирнова]].
+
-
* Доверительное оценивание. Доверительный интервал для медианы.
+
-
 
+
-
== Основы теории статистического обучения (теория Вапника-Червоненкиса) ==
+
-
 
+
-
=== Задача оценивания вероятности переобучения ===
+
-
* Основные понятия: [[алгоритм]], [[метод обучения]], [[переобучение]]. Примеры приложений: кредитный скоринг, медицинская диагностика.
+
-
* Функционал вероятности переобучения в слабой аксиоматике; полный [[скользящий контроль]].
+
-
* [[Коэффициент разнообразия]] (shatter coefficient), профиль разнообразия (shatter profile), [[функция роста]].
+
* [[Принцип равномерной сходимости]].
* [[Принцип равномерной сходимости]].
-
* '''Теорема.''' Условия, при которых функционал равномерной сходимости совпадает с вероятностью переобучения метода минимизации эмпирического риска. Доказательство теоремы.
+
* [[Коэффициент разнообразия]] (shatter coefficient), [[функция роста]].
-
* '''Теорема Вапника-Червоненкиса.''' Доказательство теоремы.
+
* '''Теорема.''' Оценка Вапника-Червоненкиса.
-
* Обращение оценки.
+
* Обращение оценки. Метод [[Структурная минимизация риска|структурной минимизации риска]].
-
* Метод [[Структурная минимизация риска|структурной минимизации риска]].
+
* Проблема завышенности оценок. Анализ причин завышенности, эффекты расслоения и связности.
-
* Достаточная длина обучающей выборки.
+
* Эксперимент 1. Вычисление достаточной длины обучающей выборки.
-
* Проблема завышенности оценок. Эмпирическое оценивание вероятности переобучения ([[метод Монте-Карло]]). [[Скользящий контроль]]. Эксперименты по эмпирическому измерению факторов завышенности. Основные причины завышенности — пренебрежение эффектами расслоения и связности в семействах алгоритмов.
+
* Разновидности методов обучения. Пессимистичная, оптимистичная, рандомизированная минимизация эмпирического риска. Максимизация переобученности.
-
* Связность семейства алгоритмов с непрерывной дискриминантной функцией.
+
* Программа для вычисления эмпирических оценок вероятности переобучения. [[Метод Монте-Карло]]. [[Скользящий контроль]].
-
 
+
* Эксперимент 2. Вычисление вероятности переобучения для модельных семейств алгоритмов с расслоением и связностью.
-
=== Влияние различности алгоритмов на вероятность переобучения ===
+
* '''Теорема.''' Вероятность переобучения семейства без расслоения.
-
* Постановка экспериментов с методом минимизации эмпирического риска. Пессимистичная минимизация эмпирического риска.
+
-
* '''Теорема.''' Вероятность переобучения для пары алгоритмов. Доказательство теоремы.
+
-
* Результаты численного эксперимента: эффекты переобучения, расслоения и сходства для пары алгоритмов.
+
-
* Модельные семейства алгоритмов с расслоением и связностью: цепочки алгоритмов (монотонные, унимодальные, стохастические, без расслоения).
+
-
* Алгоритм эффективного построения зависимостей вероятности переобучения от числа алгоритмов в семействе. Результаты экспериментов и выводы. Без расслоения и связности переобучение наступает уже при нескольких десятках алгоритмов в семействе.
+
-
* '''Теорема.''' Вероятность переобучения для монотонной цепочки алгоритмов.
+
=== Размерность Вапника-Червоненкиса (ёмкость) ===
=== Размерность Вапника-Червоненкиса (ёмкость) ===
* Понятие [[Ёмкость|ёмкости]].
* Понятие [[Ёмкость|ёмкости]].
* Функция <tex>\Phi_L^h</tex>, её связь с треугольником Паскаля.
* Функция <tex>\Phi_L^h</tex>, её связь с треугольником Паскаля.
-
* '''Лемма''' о функции <tex>\Phi_L^h</tex>. Доказательство леммы.
+
* '''Лемма''' о функции <tex>\Phi_L^h</tex>.
-
* '''Теорема.''' Выражение функции роста через ёмкость. Доказательство теоремы.
+
* '''Теорема.''' Выражение функции роста через ёмкость.
* Ёмкость конечных множеств. [[Принцип минимума длины описания]].
* Ёмкость конечных множеств. [[Принцип минимума длины описания]].
-
* '''Теорема.''' Ёмкость семейства [[Линейный классификатор|линейных разделяющих правил]]. Доказательство теоремы.
+
* '''Теорема.''' Ёмкость семейства [[Линейный классификатор|линейных разделяющих правил]].
* Пример однопараметрического семейства бесконечной ёмкости.
* Пример однопараметрического семейства бесконечной ёмкости.
-
* '''Теорема.''' Ёмкость семейства конъюнкций элементарных пороговых условий. Доказательство теоремы.
+
* '''Теорема.''' Ёмкость семейства конъюнкций элементарных пороговых условий.
* Ёмкость некоторых разновидностей [[Нейронная сеть|нейронных сетей]] (без доказательства).
* Ёмкость некоторых разновидностей [[Нейронная сеть|нейронных сетей]] (без доказательства).
-
=== Неравенства типа Бонферрони ===
+
=== Принцип порождающих и запрещающих множеств ===
-
* Классические неравенства Бонферрони.
+
-
* Понятие биномиально ограниченной функции. Примеры биномиально ограниченных функций.
+
-
* Основная теорема и следствия.
+
-
* Применение дерева событий для замены неравенства Буля более точным неравенством Бонферрони при выводе оценок типа Вапника-Червоненкиса.
+
-
 
+
-
'''Литература:'''
+
-
# {{книга
+
-
|автор = Klaus Dohmen, Peter Tittmann.
+
-
|заглавие = [[Media:bonferroni3.pdf|Bonferroni-type inequalities and binomially bounded functions]]
+
-
|издание = Electronic Notes in Discrete Mathematics (Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications)
+
-
|том = 28
+
-
|год = 2007
+
-
|страниц = 91–93
+
-
}}
+
-
 
+
-
== Точные комбинаторные оценки обобщающей способности ==
+
-
 
+
-
=== Общая точная оценка вероятности переобучения ===
+
-
* Понятия порождающих, запрещающих и нейтральных объектов для данного алгоритма.
+
* Простая гипотеза о множествах порождающих и запрещающих объектов.
* Простая гипотеза о множествах порождающих и запрещающих объектов.
-
* '''Лемма''' о вероятности получить заданный алгоритм в результате обучения. Доказательство леммы.
+
* '''Лемма''' о вероятности получить заданный алгоритм в результате обучения.
-
* '''Теорема.''' Точная оценка вероятности переобучения. Доказательство теоремы.
+
* '''Теорема.''' Точная оценка вероятности переобучения.
* Общая гипотеза о множествах порождающих и запрещающих объектов.
* Общая гипотеза о множествах порождающих и запрещающих объектов.
-
* '''Теорема.''' Общая гипотеза верна практически всегда. Доказательство теоремы.
+
* '''Теорема.''' Общая гипотеза верна практически всегда.
* Аналогично: Лемма и Теорема для общей гипотезы.
* Аналогично: Лемма и Теорема для общей гипотезы.
-
* '''Теорема.''' Упрощённая оценка вероятности переобучения для случая, когда существует корректный алгоритм. Доказательство теоремы.
+
* '''Теорема.''' Точная оценка вероятности переобучения для случая, когда существует корректный алгоритм.
 +
* '''Теорема.''' Точная оценка функционала полного скользящего контроля.
=== Модельные семейства алгоритмов (семейства простой структуры) ===
=== Модельные семейства алгоритмов (семейства простой структуры) ===
-
* Монотонная цепочка алгоритмов. Примеры.
+
* Монотонная цепь алгоритмов. Примеры.
-
* '''Теорема.''' Вероятность переобучения монотонной цепочки. Доказательство теоремы.
+
* '''Теорема.''' Вероятность переобучения монотонной цепи.
-
* Унимодальная цепочка алгоритмов. Примеры.
+
* Унимодальная цепь алгоритмов. Примеры.
-
* '''Теорема.''' Вероятность переобучения унимодальной цепочки. Доказательство теоремы.
+
* '''Теорема.''' Вероятность переобучения унимодальной цепи.
* Единичная окрестность лучшего алгоритма.
* Единичная окрестность лучшего алгоритма.
-
* '''Теорема.''' Вероятность переобучения единичной окрестности. Доказательство теоремы.
+
* '''Теорема.''' Вероятность переобучения единичной окрестности.
-
* ''h''-мерная монотонная сетка алгоритмов. Линейная зависимость вероятности переобучения от размерности сетки.
+
* Пучок ''h'' монотонных цепочек алгоритмов.
* Пучок ''h'' монотонных цепочек алгоритмов.
* Полный слой алгоритмов.
* Полный слой алгоритмов.
-
=== Блочное вычисление вероятности переобучения ===
+
=== Оценки расслоения-сязности ===
-
* Определение блока объектов.
+
* Граф расслоения-связности. Верхняя и нижняя связность и неоптимальность алгоритмов.
-
* '''Теорема.''' Формула для вычисления вероятности переобучения по блокам. Доказательство теоремы.
+
* Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности.
-
* '''Теорема.''' Вероятность переобучения для пары алгоритмов. Доказательство теоремы.
+
* ''h''-мерная монотонная сетка алгоритмов.
-
* Условия, при которых блочное вычисление достаточно эффективно.
+
 
 +
=== Конъюнктивные логические закономерности ===
 +
* Логические алгоритмы классификации.
 +
* Структура классов эквивалентности семейства конъюнкций.
 +
* Свойства граничных пожмножеств.
 +
* Послойный восходящий алгоритм вычисления вероятности переобучения для оценки расслоения-сязности
 +
* Экспериментальные результаты.
=== Рекуррентное вычисление вероятности переобучения ===
=== Рекуррентное вычисление вероятности переобучения ===
Строка 135: Строка 91:
* '''Теорема.''' Упрощённый рекуррентный алгоритм не уменьшает оценку вероятности переобучения.
* '''Теорема.''' Упрощённый рекуррентный алгоритм не уменьшает оценку вероятности переобучения.
-
=== Профиль расслоения и связности ===
+
=== Блочное вычисление вероятности переобучения ===
-
* Степень связности алгоритма. Граф расслоения и связности семейства алгоритмов. Профиль расслоения-связности.
+
* Определение блока объектов.
-
* '''Теорема.''' Верхняя оценка вероятности пееобучения через профиль расслоения-связности. Доказательство теоремы.
+
* '''Теорема.''' Формула для вычисления вероятности переобучения по блокам.
-
* Эмпирическая гипотеза о сепарабельности профиля расслоения-связности.
+
* '''Теорема.''' Вероятность переобучения для пары алгоритмов.
-
* Эмпирические гипотезы о взаимосвязи средней связности и размерности пространства парамеров.
+
* Условия, при которых блочное вычисление достаточно эффективно.
-
* '''Теорема.''' Верхняя оценка вероятности пееобучения через профиль расслоения и профиль связности. Доказательство теоремы.
+
 
-
* Сравнение с оценками Вапника-Червоненкиса. Эмпирический факт: вероятность переобучения зависит линейно от размерности пространства, тогда как в классических оценках зависимость близка к экспоненциальной.
+
=== Оценки равномерного отклонения эмпирических распределений ===
 +
* Задача оценивания функции распределения как задача эмпирического предсказания.
 +
* Теоремы Колмогорова и Смирнова (без доказательства).
 +
* Усечённый треугольник Паскаля. Связь с задачами о случайном блуждании и разорении игрока.
 +
* '''Теорема.''' Точная оценка вероятности больших отклонений эмпирических распределений. Доказательство теоремы. Геометрические интерпретации.
 +
* Оценивание функции распределения на полной выборке.
 +
* Обобщение на случай вариационного ряда со связками. Почему в этом случае задача предсказания намного сложнее.
 +
 
 +
=== Радемахеровская сложность ===
 +
* Метод обучения, максимизирующий переобученность.
 +
* Понятие Радемахеровской сложности.
 +
* Оценка равномерности-связности.
 +
 
 +
=== Непараметрические статистические критерии ===
 +
* Задачи [[Проверка статистических гипотез|проверки статистических гипотез]].
 +
* [[Гипотеза однородности]], [[гипотеза сдвига]].
 +
* Принципиальное различие задач эмпирического предсказания и проверки статистических гипотез.
 +
* [[Критерий знаков]].
 +
* [[Критерий Уилкоксона-Манна-Уитни]].
 +
* [[Критерий серий]].
 +
* [[Критерий Смирнова]].
 +
* Доверительное оценивание. Доверительный интервал для медианы.
 +
 
=== Оценки скользящего контроля для метода ближайших соседей ===
=== Оценки скользящего контроля для метода ближайших соседей ===
Строка 168: Строка 146:
* Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2010. [[Media:Voron09problems.pdf|PDF, 183&nbsp;КБ]].
* Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2010. [[Media:Voron09problems.pdf|PDF, 183&nbsp;КБ]].
-
== Вероятностная байесовская теория обобщающей способности ==
+
{{Служебная:Prefixindex/Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)/}}
-
 
+
-
=== Простейшие оценки вероятности ошибки классификации ===
+
-
* Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
+
-
* [[Биномиальное распределение]].
+
-
* Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
+
-
* Обращение оценок.
+
-
* '''Теорема.''' Оценка вероятности ошибки фиксированного алгоритма (test set bound). Доказательство теоремы. Три следствия: применение трёх различных аппроксимаций хвоста биномиального распределения.
+
-
 
+
-
'''Литература:'''
+
-
# {{книга
+
-
|автор = Langford J.
+
-
|заглавие = Quantitatively Tight Sample Complexity Bounds
+
-
|ссылка = http://citeseer.ist.psu.edu/langford02quantitatively.html
+
-
|издание = Carnegie Mellon Thesis
+
-
|год = 2002
+
-
|страниц = 124
+
-
}}
+
-
 
+
-
=== Бритва Оккама (Occam Razor) ===
+
-
* Понятия априорного распределения на множестве алгоритмов.
+
-
* '''Теорема.''' Оценка вероятности ошибки для произвольного алгоритма (Occam razor bound). Доказательство теоремы. Три следствия: применение аппроксимаций и оценка Вапника-Червоненкиса.
+
-
* Метод структурной минимизации риска (Вапника-Червоненкиса).
+
-
* '''Теорема.''' Об оптимальном априорном распределении. Доказательство теоремы.
+
-
* Открытые проблемы.
+
-
 
+
-
'''Литература:'''
+
-
# {{книга
+
-
|автор = Langford J.
+
-
|заглавие = Quantitatively Tight Sample Complexity Bounds
+
-
|ссылка = http://citeseer.ist.psu.edu/langford02quantitatively.html
+
-
|издание = Carnegie Mellon Thesis
+
-
|год = 2002
+
-
|страниц = 124
+
-
}}
+
-
 
+
-
=== Микровыборы и статистические запросы ===
+
-
* Методы обучения, основанные на [[Статистический запрос|статистических запросах]] (statistical queries learning).
+
-
* Примеры алгоритмов. [[Решающий список|Решающие списки]] и [[Решающее дерево|решающие деревья]].
+
-
* Дерево микровыборов.
+
-
* Оценки вероятности переобучения, основанные на микровыборах (microchoice bounds).
+
-
* Адаптивные оценки, основанные на микровыборах (adaptive microchoice bounds).
+
-
* Самоограничивающие методы обучения (self-bounding по Фройнду).
+
-
 
+
-
=== Стохастические классификаторы и теория PAC-Bayes ===
+
-
* Стохастические классификаторы. Понятия ожидаемой эмпирической ошибки и ожидаемой вероятности ошибок.
+
-
* '''Теорема.''' Основная теорема теории PAC-Bayes. Доказательство теоремы.
+
-
 
+
-
'''Литература:'''
+
-
# {{книга
+
-
|автор = Langford J.
+
-
|заглавие = Tutorial on Practical Prediction Theory for Classification
+
-
|ссылка = http://hunch.net/~jl
+
-
|год = 2005
+
-
|страниц = 28
+
-
}}
+
-
 
+
-
=== Применение теории PAC-Bayes к линейным классификаторам ===
+
-
* Линейный классификатор, понятие отступа (margin), распределение отступов.
+
-
* Принцип минимизации эмпирического риска и принцип максимизации отступов. Замена пороговой функции потерь на её непрерывную аппроксимацию.
+
-
* Краткая история обоснований принципа максимизации отступов. О завышенности оценок обобщающей способности.
+
-
* '''Теорема.''' Конкретизация основной теоремы теории PAC-Bayes для линейных классификаторов. Доказательство теоремы. Выбор априорного и апостериорного распределений. Следствие: ещё одна аппроксимация пороговой функции потерь.
+
-
* Проблема правомерности переноса результатов, полученных для стохастических классификаторов, на обычные классификаторы.
+
-
* Усреднённый классификатор (Averaging classifier) — композиция бесконечного множества стохастических линейных классификаторов путём усреднения по всему апостериорному распределению.
+
-
* '''Теорема.''' Усреднённый классификатор является обычным (не стохастическим) линейным классификатором. Доказательство теоремы.
+
-
* '''Теорема.''' Вероятность ошибки усреднённого классификатора не превышает удвоенной ожидаемой вероятности ошибки стохастического классификатора. Доказательство теоремы.
+
-
 
+
-
'''Литература:'''
+
-
# {{книга
+
-
|автор = Langford J.
+
-
|заглавие = Tutorial on Practical Prediction Theory for Classification
+
-
|ссылка = http://hunch.net/~jl
+
-
|год = 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
+
-
|ссылка = http://www.machinelearning.org/icml2004_proc.html
+
-
|год = 2004
+
-
|страниц = 90
+
-
}}
+
-
 
+
-
=== Расслоение семейства алгоритмов (Shell bounds) ===
+
-
* Основная идея расслоения: подавляющее большинство алгоритмов имеют высокую вероятность ошибки (около 50%), и крайне маловероятно, что для них будет наблюдаться малая эмпирическая ошибка.
+
-
* '''Теорема.''' Оценка ненаблюдаемого расслоения (unobservable shell bound). Доказательство теоремы.
+
-
* '''Теорема.''' Оценка наблюдаемого расслоения (observable shell bound). Доказательство теоремы.
+
-
* Оценивание расслоения методом Монте-Карло.
+
-
* '''Теорема.''' Оценка по случайной равномерной выборке алгоритмов. Доказательство теоремы.
+
-
* '''Теорема.''' Обобщение на случай бесконечного семейства алгоритмов. Без доказательства.
+
-
 
+
-
'''Литература:'''
+
-
# {{книга
+
-
|автор = Langford J.
+
-
|заглавие = Quantitatively Tight Sample Complexity Bounds (Chapter 8)
+
-
|ссылка = http://citeseer.ist.psu.edu/langford02quantitatively.html
+
-
|издание = Carnegie Mellon Thesis
+
-
|год = 2002
+
-
|страниц = 124
+
-
}}
+
-
 
+
-
== Прочее ==
+
-
 
+
-
=== Анализ смещения и разброса ===
+
-
* Разложение ошибки на смещение и разброс (bias-variance decomposition) для случая регрессии.
+
-
* Обобщения на случай классификации.
+
-
* Оценки для метода ''k'' ближайших соседей и для линейных композиций.
+
-
 
+
-
=== Оценки вероятности ошибки в задачах регрессии ===
+
-
* [[Линейная регрессия]].
+
-
* Оценка матожидания ошибки для многомерной линейной регрессии.
+
-
* '''Теорема.''' [[Информационный критерий Акаике]]. Доказательство теоремы.
+
-
* '''Теорема.''' [[Байесовский информационный критерий]]. Доказательство теоремы.
+
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Версия 23:04, 10 февраля 2011

Содержание

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

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

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

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

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

Сборник задач по спецкурсу «Теория надёжности обучения по прецедентам»: PDF, 183 КБ.

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

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

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

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

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

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

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

Размерность Вапника-Червоненкиса (ёмкость)

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

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

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

Модельные семейства алгоритмов (семейства простой структуры)

  • Монотонная цепь алгоритмов. Примеры.
  • Теорема. Вероятность переобучения монотонной цепи.
  • Унимодальная цепь алгоритмов. Примеры.
  • Теорема. Вероятность переобучения унимодальной цепи.
  • Единичная окрестность лучшего алгоритма.
  • Теорема. Вероятность переобучения единичной окрестности.
  • Пучок h монотонных цепочек алгоритмов.
  • Полный слой алгоритмов.

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

  • Граф расслоения-связности. Верхняя и нижняя связность и неоптимальность алгоритмов.
  • Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности.
  • h-мерная монотонная сетка алгоритмов.

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

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

Рекуррентное вычисление вероятности переобучения

  • Идея рекуррентного обновления информации о каждом алгоритме семейства при добавлении нового алгоритма.
  • Лемма. Вычисление информации о добавленном алгоритме. Доказательство леммы.
  • Теорема. Правила обновления информации о предыдущих алгоритмах при добавлении нового. Доказательство теоремы.
  • Теорема. Упрощённый рекуррентный алгоритм не уменьшает оценку вероятности переобучения.

Блочное вычисление вероятности переобучения

  • Определение блока объектов.
  • Теорема. Формула для вычисления вероятности переобучения по блокам.
  • Теорема. Вероятность переобучения для пары алгоритмов.
  • Условия, при которых блочное вычисление достаточно эффективно.

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

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

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

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

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


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

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

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

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

Литература по предыдущей части курса

Задачи по предыдущей части курса

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


Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)/2010
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BD%D0%B0%D0%B4%D1%91%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BF%D0%BE_%D0%BF%D1%80%D0%B5%D1%86%D0%B5%D0%B4%D0%B5%D0%BD%D1%82%D0%B0%D0%BC_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A._%D0%92._%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2%29»
Личные инструменты