Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)
Материал из MachineLearning.
(уточнение, дополнение) |
(→Комбинаторная теория переобучения) |
||
Строка 17: | Строка 17: | ||
=== Проблема переобучения и перестановочная вероятность === | === Проблема переобучения и перестановочная вероятность === | ||
- | * | + | * Задачи обучения по прецедентам. Примеры прикладных задач и алгоритмов классификации и регрессии. |
- | * [[Слабая вероятностная аксиоматика]]. | + | * Бинарная функция потерь. Матрица ошибок. Понятия наблюдаемой и скрытой выборки. Понятие переобучения. |
- | * | + | * [[Слабая вероятностная аксиоматика]]. |
- | * Эмпирические оценки | + | * Функционалы качества обучения: вероятность переобучения, вероятность большой частоты ошибок на контроле, полный скользящий контроль. |
- | * Финитарные и инфинитарные вероятности. | + | * Понятия точности и надёжности предсказаний. Обращение оценок. |
+ | * Способы применения оценок обобщающей способности. Задачи выбора модели, отбора признаков, оптимизации сложности модели, оптимизации размера локальной окрестности. | ||
+ | * Эмпирические оценки скользящего контроля. | ||
+ | * Сравнение слабой и сильной вероятностной аксиоматики. Финитарные и инфинитарные вероятности. Перенос оценок из слабой аксиоматики в сильную. | ||
=== Предсказание частоты события и гипергеометрическое распределение === | === Предсказание частоты события и гипергеометрическое распределение === | ||
- | * Задача предсказания частоты события. [[ | + | * Задача предсказания частоты события. Пример приложения — [[выборочный контроль качества]]. |
* '''Лемма.''' Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению. | * '''Лемма.''' Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению. | ||
* '''Теорема.''' Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках. | * '''Теорема.''' Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках. | ||
* Геометрическая интерпретация. | * Геометрическая интерпретация. | ||
- | * Свойства [[Гипергеометрическое распределение|гипергеометрического распределения]]. | + | * Свойства [[Гипергеометрическое распределение|гипергеометрического распределения]]. Способы его вычисления. |
* Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике. | * Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике. | ||
- | * Переход от ненаблюдаемой | + | * Переход от ненаблюдаемой оценки к наблюдаемой. Точная интервальная оценка. Вероятность нуль-события. |
=== Теория Вапника-Червоненкиса === | === Теория Вапника-Червоненкиса === | ||
* [[Принцип равномерной сходимости]]. | * [[Принцип равномерной сходимости]]. | ||
- | * [[Коэффициент разнообразия]] (shatter coefficient), [[функция роста]]. | + | * Семейство алгоритмов как подмножество векторов булева куба. [[Коэффициент разнообразия]] (shatter coefficient), [[функция роста]]. |
- | * '''Теорема.''' Оценка Вапника-Червоненкиса. | + | * '''Теорема.''' Оценка Вапника-Червоненкиса через коэффициент разнообразия (shattering coefficient). |
+ | * Понятие [[Ёмкость|ёмкости]] (VC-dimension), её связь с размерностью пространства параметров. | ||
+ | * '''Теорема.''' Оценка Вапника-Червоненкиса через ёмкость. | ||
* Обращение оценки. Метод [[Структурная минимизация риска|структурной минимизации риска]]. | * Обращение оценки. Метод [[Структурная минимизация риска|структурной минимизации риска]]. | ||
* Проблема завышенности оценок. Анализ причин завышенности, эффекты расслоения и связности. | * Проблема завышенности оценок. Анализ причин завышенности, эффекты расслоения и связности. | ||
- | * Эксперимент | + | * '''Эксперимент.''' Вычисление достаточной длины обучающей выборки. |
* Разновидности методов обучения. Пессимистичная, оптимистичная, рандомизированная минимизация эмпирического риска. Максимизация переобученности. | * Разновидности методов обучения. Пессимистичная, оптимистичная, рандомизированная минимизация эмпирического риска. Максимизация переобученности. | ||
- | * Программа для вычисления эмпирических оценок вероятности переобучения | + | * Программа для вычисления эмпирических оценок вероятности переобучения [[Метод Монте-Карло|методом Монте-Карло]]. |
- | + | * '''Эксперимент''' с четырьмя модельными семействами алгоритмов для выяснения влияния расслоения и связности на вероятность переобучения. | |
- | * ''' | + | |
+ | === Точные комбинаторные оценки для модельных семейств алгоритмов === | ||
+ | * '''Теорема.''' Вероятность переобучения полного слоя алгоритмов. | ||
+ | * '''Теорема.''' Вероятность переобучения множества из двух алгоритмов. | ||
+ | * '''Теорема.''' Вероятность переобучения монотонной цепи алгоритмов. | ||
+ | * '''Теорема.''' Вероятность переобучения унимодальной цепи алгоритмов. | ||
+ | * '''Теорема.''' Вероятность переобучения интервала булева куба. | ||
+ | * Вычислительные эксперименты с модельными семействами и интерпретация результатов. | ||
+ | |||
+ | <!--- | ||
=== Размерность Вапника-Червоненкиса (ёмкость) === | === Размерность Вапника-Червоненкиса (ёмкость) === | ||
* Понятие [[Ёмкость|ёмкости]]. | * Понятие [[Ёмкость|ёмкости]]. | ||
Строка 54: | Строка 67: | ||
* '''Теорема.''' Ёмкость семейства конъюнкций элементарных пороговых условий. | * '''Теорема.''' Ёмкость семейства конъюнкций элементарных пороговых условий. | ||
* Ёмкость некоторых разновидностей [[Нейронная сеть|нейронных сетей]] (без доказательства). | * Ёмкость некоторых разновидностей [[Нейронная сеть|нейронных сетей]] (без доказательства). | ||
- | + | ---> | |
=== Принцип порождающих и запрещающих множеств === | === Принцип порождающих и запрещающих множеств === | ||
* Простая гипотеза о множествах порождающих и запрещающих объектов. | * Простая гипотеза о множествах порождающих и запрещающих объектов. | ||
Строка 61: | Строка 74: | ||
* Общая гипотеза о множествах порождающих и запрещающих объектов. | * Общая гипотеза о множествах порождающих и запрещающих объектов. | ||
* '''Теорема.''' Общая гипотеза верна практически всегда. | * '''Теорема.''' Общая гипотеза верна практически всегда. | ||
- | * | + | * '''Лемма''' и '''Теорема''' для общей гипотезы. |
- | + | ||
* '''Теорема.''' Точная оценка функционала полного скользящего контроля. | * '''Теорема.''' Точная оценка функционала полного скользящего контроля. | ||
- | + | * '''Теорема.''' Точные оценки для случая, когда существует корректный алгоритм. | |
- | + | ||
- | + | ||
- | * '''Теорема.''' | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
=== Оценки расслоения-связности === | === Оценки расслоения-связности === | ||
- | * Граф расслоения-связности. Верхняя | + | * Граф расслоения-связности. Верхняя связность, нижняя связность, неполноценность алгоритма. |
+ | * Монотонный метод обучения. Примеры. | ||
+ | * '''Теорема.''' Оценка расслоения-связности для вероятности переобучения. | ||
+ | * '''Теорема.''' Оценка расслоения-связности для полного скользящего контроля. | ||
+ | * Оценки для монотонной и унимодальной цепи. | ||
* Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности. | * Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности. | ||
- | * '' | + | * Многомерная монотонная сеть алгоритмов. Примеры. |
+ | * '''Теорема.''' Оценка расслоения-связности для многомерной монотонной сети алгоритмов. | ||
+ | * Вычислительные эксперименты с многомерными сетями. | ||
+ | * Критерий точности оценок расслоения-связности (без доказательства). | ||
=== Конъюнктивные логические закономерности === | === Конъюнктивные логические закономерности === | ||
- | * Логические алгоритмы классификации. Критерии информативности. | + | * Логические алгоритмы классификации (rule learning). Примеры прикладных задач. Виды закономерностей: конъюнкции, синдромы, шары, полупространства. |
+ | * Критерии информативности. Примеры. Двухкритериальная оптимизация в (p,n)-пространстве. | ||
+ | * '''Теорема''' о монотонности метода максимизации информативности. | ||
+ | * '''Теорема.''' Оценка расслоения-связности для частоты ошибок I и II рода. | ||
* Структура классов эквивалентности семейства конъюнкций пороговых предикатов. | * Структура классов эквивалентности семейства конъюнкций пороговых предикатов. | ||
- | * Стандартные представители классов эквивалентности и граничные | + | * Стандартные представители классов эквивалентности и граничные подмножества объектов. |
* Послойный восходящий алгоритм вычисления оценки расслоения-связности. | * Послойный восходящий алгоритм вычисления оценки расслоения-связности. | ||
- | * Модификация критериев информативности. Результаты экспериментов. | + | * Модификация критериев информативности. Применение для отбора признаков. Результаты экспериментов. |
+ | <!--- | ||
=== Рекуррентное вычисление вероятности переобучения === | === Рекуррентное вычисление вероятности переобучения === | ||
* Идея рекуррентного обновления информации о каждом алгоритме семейства при добавлении нового алгоритма. | * Идея рекуррентного обновления информации о каждом алгоритме семейства при добавлении нового алгоритма. | ||
Строка 98: | Строка 112: | ||
* '''Теорема.''' Вероятность переобучения для пары алгоритмов. | * '''Теорема.''' Вероятность переобучения для пары алгоритмов. | ||
* Вероятность переобучения интервала булева куба и его нижних слоёв. | * Вероятность переобучения интервала булева куба и его нижних слоёв. | ||
- | + | ---> | |
=== Оценки равномерного отклонения эмпирических распределений === | === Оценки равномерного отклонения эмпирических распределений === | ||
- | * Вероятность большого равномерного отклонения эмпирических функций распределения. | + | * Вероятность большого равномерного отклонения эмпирических функций распределения. Задача проверки гипотезы однородности. Задача оценивания функции распределения. |
* Теоремы Колмогорова и Смирнова (без доказательства). | * Теоремы Колмогорова и Смирнова (без доказательства). | ||
* Усечённый треугольник Паскаля. Случайное блуждание. | * Усечённый треугольник Паскаля. Случайное блуждание. | ||
* '''Теорема.''' Точная оценка вероятности большого равномерного отклонения эмпирических распределений. Геометрические интерпретации. | * '''Теорема.''' Точная оценка вероятности большого равномерного отклонения эмпирических распределений. Геометрические интерпретации. | ||
- | * Обобщение на случай вариационного ряда со связками. Почему в этом случае задача | + | * Обобщение на случай вариационного ряда со связками. Почему в этом случае задача оценивания функции распределения намного сложнее. |
=== Радемахеровская сложность === | === Радемахеровская сложность === | ||
* Метод обучения, максимизирующий переобученность. | * Метод обучения, максимизирующий переобученность. | ||
- | * Понятие Радемахеровской сложности. | + | * Понятие Радемахеровской сложности, его связь с вероятностью переобучения. |
* Оценка через принцип порождающих и запрещающих множеств. | * Оценка через принцип порождающих и запрещающих множеств. | ||
* Оценка через цепные разложения. | * Оценка через цепные разложения. | ||
Строка 119: | Строка 133: | ||
* '''Теорема.''' Точное выражение функционала полного скользящего контроля для метода ''k'' ближайших соседей (''k''NN). | * '''Теорема.''' Точное выражение функционала полного скользящего контроля для метода ''k'' ближайших соседей (''k''NN). | ||
* Свойства профилей компактности. | * Свойства профилей компактности. | ||
- | * Алгоритм выделения эталонных объектов. Функция вклада объекта и её эффективное вычисление. Метрические деревья. | + | * Алгоритм выделения эталонных объектов (prototype learning). Функция вклада объекта и её эффективное вычисление. Прямые и обратные окрестности. Метрические деревья. |
- | * Разделение объектов на шумовые, эталонные и неинформативные. | + | * Разделение объектов на шумовые, эталонные и неинформативные. |
+ | * Вычислительные эксперименты с методом ближайших эталонов. | ||
=== Оценки скользящего контроля для монотонных классификаторов === | === Оценки скользящего контроля для монотонных классификаторов === | ||
- | * Монотонные алгоритмы классификации. | + | * Монотонные алгоритмы классификации. Монотонные корректирующие операции в алгоритмических композициях. |
* Понятие клина объекта. Профиль монотонности выборки. | * Понятие клина объекта. Профиль монотонности выборки. | ||
- | * '''Теорема.''' Верхняя оценка скользящего контроля. | + | * '''Теорема.''' Верхняя оценка полного скользящего контроля. |
- | * | + | * Монотонный классификатор ближайшего соседа. Взаимосвязь между профилями компактности и монотонности. |
+ | * '''Теорема.''' Точная оценка полного скользящего контроля для монотонного классификатора ближайшего соседа (в случае монотонной выборки). | ||
+ | * '''Теорема.''' Верхняя оценка полного скользящего контроля для монотонного классификатора ближайшего соседа (в общем случае). | ||
* Критерии настройки базовых алгоритмов на основе оценок обобщающей способности. | * Критерии настройки базовых алгоритмов на основе оценок обобщающей способности. | ||
Версия 16:58, 4 февраля 2012
Спецкурс знакомит студентов с теорией вычислительного обучения (computational learning theory, COLT), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики В. Н. Вапник и А. Я. Червоненкис. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время продолжает развиваться.
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными, предрассудками? Как избежать переобучения — ситуации, когда ответы алгоритма удаётся хорошо подогнать под обучающие данные, но на новых контрольных данных они оказываются существенно менее точными? Как управлять обобщающей способностью алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
Цели спецкурса — научить студентов оценивать надёжность алгоритмов обучения; использовать оценки обобщающей способности для разработки более надёжных алгоритмов; применять их для решения прикладных задач классификации, регрессии, прогнозирования.
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по комбинаторной теории переобучения и слабой вероятностной аксиоматике.
Спецкурс читается студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года, в дополнение к обязательному кафедральному курсу Математические методы распознавания образов (ММРО).
Учебное пособие по курсу ТНОП: Voron-2011-tnop.pdf, 3 МБ (черновая версия). |
Комбинаторная теория переобучения
Проблема переобучения и перестановочная вероятность
- Задачи обучения по прецедентам. Примеры прикладных задач и алгоритмов классификации и регрессии.
- Бинарная функция потерь. Матрица ошибок. Понятия наблюдаемой и скрытой выборки. Понятие переобучения.
- Слабая вероятностная аксиоматика.
- Функционалы качества обучения: вероятность переобучения, вероятность большой частоты ошибок на контроле, полный скользящий контроль.
- Понятия точности и надёжности предсказаний. Обращение оценок.
- Способы применения оценок обобщающей способности. Задачи выбора модели, отбора признаков, оптимизации сложности модели, оптимизации размера локальной окрестности.
- Эмпирические оценки скользящего контроля.
- Сравнение слабой и сильной вероятностной аксиоматики. Финитарные и инфинитарные вероятности. Перенос оценок из слабой аксиоматики в сильную.
Предсказание частоты события и гипергеометрическое распределение
- Задача предсказания частоты события. Пример приложения — выборочный контроль качества.
- Лемма. Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
- Теорема. Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках.
- Геометрическая интерпретация.
- Свойства гипергеометрического распределения. Способы его вычисления.
- Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.
- Переход от ненаблюдаемой оценки к наблюдаемой. Точная интервальная оценка. Вероятность нуль-события.
Теория Вапника-Червоненкиса
- Принцип равномерной сходимости.
- Семейство алгоритмов как подмножество векторов булева куба. Коэффициент разнообразия (shatter coefficient), функция роста.
- Теорема. Оценка Вапника-Червоненкиса через коэффициент разнообразия (shattering coefficient).
- Понятие ёмкости (VC-dimension), её связь с размерностью пространства параметров.
- Теорема. Оценка Вапника-Червоненкиса через ёмкость.
- Обращение оценки. Метод структурной минимизации риска.
- Проблема завышенности оценок. Анализ причин завышенности, эффекты расслоения и связности.
- Эксперимент. Вычисление достаточной длины обучающей выборки.
- Разновидности методов обучения. Пессимистичная, оптимистичная, рандомизированная минимизация эмпирического риска. Максимизация переобученности.
- Программа для вычисления эмпирических оценок вероятности переобучения методом Монте-Карло.
- Эксперимент с четырьмя модельными семействами алгоритмов для выяснения влияния расслоения и связности на вероятность переобучения.
Точные комбинаторные оценки для модельных семейств алгоритмов
- Теорема. Вероятность переобучения полного слоя алгоритмов.
- Теорема. Вероятность переобучения множества из двух алгоритмов.
- Теорема. Вероятность переобучения монотонной цепи алгоритмов.
- Теорема. Вероятность переобучения унимодальной цепи алгоритмов.
- Теорема. Вероятность переобучения интервала булева куба.
- Вычислительные эксперименты с модельными семействами и интерпретация результатов.
Принцип порождающих и запрещающих множеств
- Простая гипотеза о множествах порождающих и запрещающих объектов.
- Лемма о вероятности получить заданный алгоритм в результате обучения.
- Теорема. Точная оценка вероятности переобучения.
- Общая гипотеза о множествах порождающих и запрещающих объектов.
- Теорема. Общая гипотеза верна практически всегда.
- Лемма и Теорема для общей гипотезы.
- Теорема. Точная оценка функционала полного скользящего контроля.
- Теорема. Точные оценки для случая, когда существует корректный алгоритм.
Оценки расслоения-связности
- Граф расслоения-связности. Верхняя связность, нижняя связность, неполноценность алгоритма.
- Монотонный метод обучения. Примеры.
- Теорема. Оценка расслоения-связности для вероятности переобучения.
- Теорема. Оценка расслоения-связности для полного скользящего контроля.
- Оценки для монотонной и унимодальной цепи.
- Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности.
- Многомерная монотонная сеть алгоритмов. Примеры.
- Теорема. Оценка расслоения-связности для многомерной монотонной сети алгоритмов.
- Вычислительные эксперименты с многомерными сетями.
- Критерий точности оценок расслоения-связности (без доказательства).
Конъюнктивные логические закономерности
- Логические алгоритмы классификации (rule learning). Примеры прикладных задач. Виды закономерностей: конъюнкции, синдромы, шары, полупространства.
- Критерии информативности. Примеры. Двухкритериальная оптимизация в (p,n)-пространстве.
- Теорема о монотонности метода максимизации информативности.
- Теорема. Оценка расслоения-связности для частоты ошибок I и II рода.
- Структура классов эквивалентности семейства конъюнкций пороговых предикатов.
- Стандартные представители классов эквивалентности и граничные подмножества объектов.
- Послойный восходящий алгоритм вычисления оценки расслоения-связности.
- Модификация критериев информативности. Применение для отбора признаков. Результаты экспериментов.
Оценки равномерного отклонения эмпирических распределений
- Вероятность большого равномерного отклонения эмпирических функций распределения. Задача проверки гипотезы однородности. Задача оценивания функции распределения.
- Теоремы Колмогорова и Смирнова (без доказательства).
- Усечённый треугольник Паскаля. Случайное блуждание.
- Теорема. Точная оценка вероятности большого равномерного отклонения эмпирических распределений. Геометрические интерпретации.
- Обобщение на случай вариационного ряда со связками. Почему в этом случае задача оценивания функции распределения намного сложнее.
Радемахеровская сложность
- Метод обучения, максимизирующий переобученность.
- Понятие Радемахеровской сложности, его связь с вероятностью переобучения.
- Оценка через принцип порождающих и запрещающих множеств.
- Оценка через цепные разложения.
- Точная оценка для монотонной цепи алгоритмов через случайное блуждание.
Оценки скользящего контроля для метода ближайших соседей
- Метрические алгоритмы классификации, метод ближайших соседей.
- Понятие профиля компактности.
- Теорема. Точное выражение функционала полного скользящего контроля для метода одного ближайшего соседа (1NN).
- Теорема. Точное выражение функционала полного скользящего контроля для метода k ближайших соседей (kNN).
- Свойства профилей компактности.
- Алгоритм выделения эталонных объектов (prototype learning). Функция вклада объекта и её эффективное вычисление. Прямые и обратные окрестности. Метрические деревья.
- Разделение объектов на шумовые, эталонные и неинформативные.
- Вычислительные эксперименты с методом ближайших эталонов.
Оценки скользящего контроля для монотонных классификаторов
- Монотонные алгоритмы классификации. Монотонные корректирующие операции в алгоритмических композициях.
- Понятие клина объекта. Профиль монотонности выборки.
- Теорема. Верхняя оценка полного скользящего контроля.
- Монотонный классификатор ближайшего соседа. Взаимосвязь между профилями компактности и монотонности.
- Теорема. Точная оценка полного скользящего контроля для монотонного классификатора ближайшего соседа (в случае монотонной выборки).
- Теорема. Верхняя оценка полного скользящего контроля для монотонного классификатора ближайшего соседа (в общем случае).
- Критерии настройки базовых алгоритмов на основе оценок обобщающей способности.
Непараметрические статистические критерии
- Задачи проверки статистических гипотез.
- Гипотеза однородности, гипотеза сдвига.
- Принципиальное различие задач эмпирического предсказания и проверки статистических гипотез.
- Критерий знаков.
- Критерий Уилкоксона-Манна-Уитни.
- Критерий серий.
- Критерий Смирнова.
- Доверительное оценивание. Доверительный интервал для медианы.
Литература
- Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр РАН, 2010. — 271 с. (подробнее).
- Воронцов К. В. Слабая вероятностная аксиоматика. 2009. PDF, 832 КБ.
- Воронцов К. В. Эффекты расслоения и сходства в семействах алгоритмов и их влияние на вероятность переобучения. 2009. PDF, 354 КБ.
- Воронцов К. В. Точные оценки вероятности переобучения. 2009. PDF, 542 КБ.
Ссылки
- Расслоение и сходство алгоритмов (виртуальный семинар)
- Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2010. PDF, 183 КБ.