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

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (20:11, 19 февраля 2016) (править) (отменить)
(→Учебные материалы)
 
(43 промежуточные версии не показаны)
Строка 1: Строка 1:
{{TOCright}}
{{TOCright}}
-
Спецкурс знакомит студентов с современным состоянием [[теория вычислительного обучения|теории вычислительного обучения]] (computational learning theory, COLT), исследующей проблему качества восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики [[Вапник, Владимир Наумович|{{S|В. Н. Вапник}}]] и [[Червоненкис, Алексей Яковлевич|{{S|А. Я. Червоненкис}}]]. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время развивается очень активно, главным образом, за рубежом.
+
Спецкурс знакомит студентов с [[теория вычислительного обучения|теорией вычислительного обучения]] (computational learning theory, COLT), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики [[Вапник, Владимир Наумович|{{S|В. Н. Вапник}}]] и [[Червоненкис, Алексей Яковлевич|{{S|А. Я. Червоненкис}}]]. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время продолжает развиваться.
-
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными? Как избежать [[Переобучение|переобучения]] — ситуации, когда ответы алгоритма слишком точны на обучающей выборке, но недостаточно точны на новых данных, которые не были известны на этапе обучения? Как управлять [[обобщающая способность|обобщающей способностью]] алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
+
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными, [[предрассудок|предрассудками]]? Как избежать [[Переобучение|переобучения]] — ситуации, когда ответы алгоритма удаётся хорошо подогнать под обучающие данные, но на новых контрольных данных они оказываются существенно менее точными? Как управлять [[обобщающая способность|обобщающей способностью]] алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
-
Цели спецкурса — научить студентов не только строить и применять обучаемые алгоритмы анализа данных, но и оценивать их надёжность; разрабатывать более надёжные алгоритмы; понимать возможные причины ненадёжной работы обучаемых алгоритмов в прикладных задачах классификации, регрессии, прогнозирования.
+
Цели спецкурса — научить студентов оценивать надёжность алгоритмов обучения; использовать оценки обобщающей способности для разработки более надёжных алгоритмов; применять их для решения прикладных задач классификации, регрессии, прогнозирования.
-
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по комбинаторной теории обобщающей способности и [[Слабая вероятностная аксиоматика|слабой вероятностной аксиоматике]].
+
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по [[Расслоение и сходство алгоритмов (виртуальный семинар)|комбинаторной теории переобучения]] и [[Слабая вероятностная аксиоматика|слабой вероятностной аксиоматике]].
-
Спецкурс читается студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года, в дополнение к обязательному кафедральному курсу [[Машинное обучение (курс лекций, К.В.Воронцов)|Математические методы распознавания образов (ММРО)]]. Некоторые лекции спецкурса являются непосредственным продолжением соответствующих лекций ММРО, что специально отмечено в программе.
+
На кафедре [[Математические методы прогнозирования (кафедра ВМиК МГУ)|Математические методы прогнозирования]] [[ВМиК]] [[МГУ]] данный курс читается как математический спецкурс студентам 3—5 курсов с 2007 года, в дополнение к обязательному кафедральному курсу [[Машинное обучение (курс лекций, К.В.Воронцов)|Математические методы распознавания образов (ММРО)]].
-
== Комбинаторные методы в математической статистике ==
+
На кафедре [[Интеллектуальные системы (кафедра МФТИ)|Интеллектуальные системы]] [[ФУПМ]] [[МФТИ]] данный курс является третьей частью трёхсеместрового курса [[Машинное обучение (курс лекций, К.В.Воронцов)|Теория обучения машин]].
-
=== Предсказание частоты события и закон больших чисел ===
+
== Комбинаторная теория переобучения ==
-
* Задача эмпирического предсказания в общей постановке. Понятия наблюдаемой и скрытой выборки. Точность и надёжность предсказаний.
+
 
-
* [[Слабая вероятностная аксиоматика]]. Перенос оценок из слабой аксиоматики в сильную (колмогоровскую). Финитарные и инфинитарные вероятности. Сравнение с колмогоровской аксиоматикой, достоинства, недостатки и границы применимости.
+
=== Проблема переобучения и перестановочная вероятность ===
-
* Задача предсказания частоты события. Примеры приложений: [[выборочный контроль качества]], оценивание качества алгоритма классификации.
+
* Задачи обучения по прецедентам. Примеры прикладных задач и алгоритмов классификации и регрессии.
 +
* Бинарная функция потерь. Матрица ошибок. Понятия наблюдаемой и скрытой выборки. Понятие переобучения.
 +
* [[Слабая вероятностная аксиоматика]].
 +
* Функционалы качества обучения: вероятность переобучения, вероятность большой частоты ошибок на контроле, полный скользящий контроль.
 +
* Понятия точности и надёжности предсказаний. Обращение оценок.
 +
* Способы применения оценок обобщающей способности. Задачи выбора модели, отбора признаков, оптимизации сложности модели, оптимизации размера локальной окрестности.
 +
* Эмпирические оценки скользящего контроля.
 +
* Сравнение слабой и сильной вероятностной аксиоматики. Финитарные и инфинитарные вероятности. Перенос оценок из слабой аксиоматики в сильную.
 +
 
 +
=== Предсказание частоты события и гипергеометрическое распределение ===
 +
* Задача предсказания частоты события. Пример приложения — [[выборочный контроль качества]].
* '''Лемма.''' Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
* '''Лемма.''' Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
-
* '''Теорема.''' Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках. Доказательство теоремы.
+
* '''Теорема.''' Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках.
* Геометрическая интерпретация.
* Геометрическая интерпретация.
-
* Свойства [[Гипергеометрическое распределение|гипергеометрического распределения]]. Методы вычисления гипергеометрического распределения.
+
* Свойства [[Гипергеометрическое распределение|гипергеометрического распределения]]. Способы его вычисления.
* Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.
* Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.
 +
* Переход от ненаблюдаемой оценки к наблюдаемой. Точная интервальная оценка. Вероятность нуль-события.
-
=== Обращение оценок ===
+
=== Элементы теории Вапника-Червоненкиса ===
-
* Парадокс: оценка вероятности большого уклонения зависит от оцениваемой величины — числа ошибок на полной выборке.
+
-
* Экспоненциальная верхняя оценка, её обращение и устранение парадокса.
+
-
* Обращение кусочно-постоянных функций.
+
-
* Обращение точной верхней оценки частоты события на скрытой выборке.
+
-
* Интервальная оценка частоты нуль-события на скрытой выборке.
+
-
* Переход от ненаблюдаемой оценки к наблюдаемой: общая постановка проблемы; одномерный случай.
+
-
 
+
-
=== Оценки равномерного отклонения эмпирических распределений ===
+
-
* Задача оценивания функции распределения как задача эмпирического предсказания.
+
-
* Теоремы Колмогорова и Смирнова (без доказательства).
+
-
* Усечённый треугольник Паскаля. Связь с задачами о случайном блуждании и разорении игрока.
+
-
* '''Теорема.''' Точная оценка вероятности больших отклонений эмпирических распределений. Доказательство теоремы. Геометрические интерпретации.
+
-
* Оценивание функции распределения на полной выборке.
+
-
* Обобщение на случай вариационного ряда со связками. Почему в этом случае задача предсказания намного сложнее.
+
-
 
+
-
=== Непараметрические статистические критерии ===
+
-
* Задачи [[Проверка статистических гипотез|проверки статистических гипотез]].
+
-
* [[Гипотеза однородности]], [[гипотеза сдвига]].
+
-
* Принципиальное различие задач эмпирического предсказания и проверки статистических гипотез.
+
-
* [[Критерий знаков]].
+
-
* [[Критерий Уилкоксона-Манна-Уитни]].
+
-
* [[Критерий серий]].
+
-
* [[Критерий Смирнова]].
+
-
* Доверительное оценивание. Доверительный интервал для медианы.
+
-
 
+
-
== Основы теории статистического обучения (теория Вапника-Червоненкиса) ==
+
-
 
+
-
=== Задача обучения по прецедентам ===
+
-
* Основные понятия: [[алгоритм]], [[метод обучения]], [[переобучение]]. Примеры приложений: кредитный скоринг, медицинская диагностика.
+
-
* Функционал вероятности переобучения в слабой аксиоматике; полный [[скользящий контроль]].
+
-
* [[Коэффициент разнообразия]] (shatter coefficient), профиль разнообразия (shatter profile), [[функция роста]].
+
* [[Принцип равномерной сходимости]].
* [[Принцип равномерной сходимости]].
-
* '''Теорема Вапника-Червоненкиса.''' Доказательство теоремы.
+
* Семейство алгоритмов как подмножество векторов булева куба. [[Коэффициент разнообразия]] и [[функция роста]] семейства алгоритмов.
-
* Обращение оценки.
+
* '''Теорема.''' Оценка Вапника-Червоненкиса через коэффициент разнообразия (shattering coefficient).
-
* Метод [[Структурная минимизация риска|структурной минимизации риска]].
+
* Понятие [[Ёмкость|ёмкости]] (VC-dimension), её связь с функцией роста, ёмкость семейства линейных классификаторов.
-
* Достаточная длина обучающей выборки.
+
* '''Теорема.''' Оценка Вапника-Червоненкиса через ёмкость.
-
* Проблема завышенности оценок. Основные причины завышенности.
+
* Обращение оценки. Метод [[Структурная минимизация риска|структурной минимизации риска]].
-
* Условия, при которых принцип равномерной сходимости не приводит к завышенности оценок для метода минимизации эмпирического риска.
+
* Проблема завышенности оценок. Анализ причин завышенности, эффекты расслоения и связности.
 +
* '''Эксперимент.''' Вычисление достаточной длины обучающей выборки.
 +
* Разновидности методов обучения. Пессимистичная, оптимистичная, рандомизированная минимизация эмпирического риска. Максимизация переобученности.
 +
* Программа для вычисления эмпирических оценок вероятности переобучения [[Метод Монте-Карло|методом Монте-Карло]].
 +
* '''Эксперимент''' с четырьмя модельными семействами алгоритмов для выяснения влияния расслоения и связности на вероятность переобучения.
 +
=== Точные комбинаторные оценки для модельных семейств алгоритмов ===
 +
* '''Теорема.''' Вероятность переобучения полного слоя алгоритмов.
 +
* '''Теорема.''' Вероятность переобучения множества из двух алгоритмов.
 +
* '''Теорема.''' Вероятность переобучения монотонной цепи алгоритмов.
 +
* '''Теорема.''' Вероятность переобучения унимодальной цепи алгоритмов.
 +
* '''Теорема.''' Вероятность переобучения интервала булева куба.
 +
* Вычислительные эксперименты с модельными семействами и интерпретация результатов.
 +
<!---
=== Размерность Вапника-Червоненкиса (ёмкость) ===
=== Размерность Вапника-Червоненкиса (ёмкость) ===
* Понятие [[Ёмкость|ёмкости]].
* Понятие [[Ёмкость|ёмкости]].
* Функция <tex>\Phi_L^h</tex>, её связь с треугольником Паскаля.
* Функция <tex>\Phi_L^h</tex>, её связь с треугольником Паскаля.
-
* '''Лемма''' о функции <tex>\Phi_L^h</tex>. Доказательство леммы.
+
* '''Лемма''' о функции <tex>\Phi_L^h</tex>.
-
* '''Теорема.''' Выражение функции роста через ёмкость. Доказательство теоремы.
+
* '''Теорема.''' Выражение функции роста через ёмкость.
* Ёмкость конечных множеств. [[Принцип минимума длины описания]].
* Ёмкость конечных множеств. [[Принцип минимума длины описания]].
-
* '''Теорема.''' Ёмкость семейства [[Линейный классификатор|линейных разделяющих правил]]. Доказательство теоремы.
+
* '''Теорема.''' Ёмкость семейства [[Линейный классификатор|линейных разделяющих правил]].
* Пример однопараметрического семейства бесконечной ёмкости.
* Пример однопараметрического семейства бесконечной ёмкости.
-
* '''Теорема.''' Ёмкость семейства конъюнкций элементарных пороговых условий. Доказательство теоремы.
+
* '''Теорема.''' Ёмкость семейства конъюнкций элементарных пороговых условий.
* Ёмкость некоторых разновидностей [[Нейронная сеть|нейронных сетей]] (без доказательства).
* Ёмкость некоторых разновидностей [[Нейронная сеть|нейронных сетей]] (без доказательства).
 +
--->
-
=== Неравенства типа Бонферрони ===
+
=== Принцип порождающих и запрещающих множеств ===
-
* Классические неравенства Бонферрони.
+
* Простая гипотеза о множествах порождающих и запрещающих объектов.
-
* Понятие биномиально ограниченной функции. Примеры биномиально ограниченных функций.
+
* '''Лемма''' о вероятности получить заданный алгоритм в результате обучения.
-
* Основная теорема и следствия.
+
* '''Теорема.''' Точная оценка вероятности переобучения.
-
* Применение дерева событий для замены неравенства Буля более точным неравенством Бонферрони при выводе оценок типа Вапника-Червоненкиса.
+
* Общая гипотеза о множествах порождающих и запрещающих объектов.
 +
* '''Теорема.''' Общая гипотеза верна практически всегда.
 +
* '''Лемма''' и '''Теорема''' для общей гипотезы.
 +
* '''Теорема.''' Точная оценка функционала полного скользящего контроля.
 +
* '''Теорема.''' Точные оценки для случая, когда существует корректный алгоритм.
-
=== Эксперименты по эмпирическому измерению факторов завышенности ===
+
=== Оценки расслоения-связности ===
-
* Эмпирическое оценивание вероятности переобучения ([[метод Монте-Карло]]). [[Скользящий контроль]].
+
* Граф расслоения-связности. Верхняя связность, нижняя связность, неполноценность алгоритма.
-
* Разложение степени завышенности оценки Вапника-Червоненкиса в произведение факторов завышенности.
+
* Монотонный метод обучения. Примеры.
-
* [[Логический классификатор|Логические алгоритмы классификации]]. Понятия [[закономерность|закономерности]] и [[информативность|информативности]]. Алгоритм синтеза информативных конъюнкций.
+
* '''Теорема.''' Оценка расслоения-связности для вероятности переобучения.
-
* Обобщение понятий частоты ошибок, метода обучения, коэффициента разнообразия для случая закономерностей. Обобщение теоремы Вапника-Червоненкиса для случая закономерностей.
+
* '''Теорема.''' Оценка расслоения-связности для полного скользящего контроля.
-
* Результаты численных экспериментов. Выводы об относительной значимости факторов завышенности.
+
* Оценки для монотонной и унимодальной цепи.
 +
* Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности.
 +
* Многомерная монотонная сеть алгоритмов. Примеры.
 +
* '''Теорема.''' Оценка расслоения-связности для многомерной монотонной сети алгоритмов.
 +
* Вычислительные эксперименты с многомерными сетями.
 +
* Критерий точности оценок расслоения-связности (без доказательства).
-
=== Влияние различности алгоритмов на вероятность переобучения ===
+
=== Конъюнктивные логические закономерности ===
-
* Понятия цепочки алгоритмов. Связность семейства алгоритмов с непрерывной дискриминантной функцией.
+
* [[Логический классификатор|Логические алгоритмы классификации]] (rule learning). Примеры прикладных задач. Виды [[логическая закономерность|закономерностей]]: конъюнкции, синдромы, шары, полупространства.
-
* Вероятность переобучения для монотонной цепочки алгоритмов.
+
* [[Информативность|Критерии информативности]]. Примеры. Двухкритериальная оптимизация в (p,n)-пространстве.
-
* Постановка эксперимента с методом минимизации эмпирического риска. Результаты экспериментов и выводы.
+
* '''Теорема''' о монотонности метода максимизации информативности.
 +
* '''Теорема.''' Оценка расслоения-связности для частоты ошибок I и II рода.
 +
* Структура классов эквивалентности семейства конъюнкций пороговых предикатов.
 +
* Стандартные представители классов эквивалентности и граничные подмножества объектов.
 +
* Послойный восходящий алгоритм вычисления оценки расслоения-связности.
 +
* Модификация критериев информативности. Применение для отбора признаков. Результаты экспериментов.
 +
<!---
 +
=== Рекуррентное вычисление вероятности переобучения ===
 +
* Идея рекуррентного обновления информации о каждом алгоритме семейства при добавлении нового алгоритма.
 +
* '''Лемма.''' Вычисление информации о добавленном алгоритме. Доказательство леммы.
 +
* '''Теорема.''' Правила обновления информации о предыдущих алгоритмах при добавлении нового.
 +
* '''Теорема.''' Упрощённый рекуррентный алгоритм не уменьшает оценку вероятности переобучения.
-
== Точные комбинаторные оценки обобщающей способности ==
+
=== Блочные и интервальные точные оценки вероятности переобучения ===
 +
* Определение блока объектов.
 +
* '''Теорема.''' Формула для вычисления вероятности переобучения по блокам.
 +
* '''Теорема.''' Вероятность переобучения для пары алгоритмов.
 +
* Вероятность переобучения интервала булева куба и его нижних слоёв.
 +
--->
-
{{well|
+
=== Оценки равномерного отклонения эмпирических распределений ===
-
''Материал по этой части курса:''
+
* Вероятность большого равномерного отклонения эмпирических функций распределения. Задача проверки гипотезы однородности. Задача оценивания функции распределения.
-
* Эффекты расслоения и сходства в семействах алгоритмов и их влияние на вероятность переобучения. 2009. [[Media:Voron09roai2008.pdf|PDF, 354&nbsp;КБ]].
+
* Теоремы Колмогорова и Смирнова (без доказательства).
-
* Точные оценки вероятности переобучения. 2009. [[Media:Voron09exact.pdf|PDF, 336&nbsp;КБ]].
+
* Усечённый треугольник Паскаля. Случайное блуждание.
-
* Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2009. [[Media:Voron09problems.pdf|PDF, 208&nbsp;КБ]].
+
* '''Теорема.''' Точная оценка вероятности большого равномерного отклонения эмпирических распределений. Геометрические интерпретации.
-
}}
+
* Обобщение на случай вариационного ряда со связками. Почему в этом случае задача оценивания функции распределения намного сложнее.
-
 
+
-
=== Общая точная оценка вероятности переобучения ===
+
-
* Понятия производящих, разрушающих и нейтральных объектов для данного алгоритма.
+
-
* Гипотеза о множествах производящих и разрушающих объектов (простой случай).
+
-
* '''Лемма''' о вероятности получить заданный алгоритм в результате обучения. Доказательство леммы.
+
-
* '''Теорема.''' Точная оценка вероятности переобучения. Доказательство теоремы.
+
-
* Гипотеза о семействах множеств производящих и разрушающих объектов (сложный случай). Аналогично: Лемма и Теорема.
+
-
 
+
-
=== Монотонные и унимодальные цепочки алгоритмов ===
+
-
* Понятие монотонной цепочки. Пример.
+
-
* '''Теорема''' о монотонной цепочке.
+
-
* Обсуждение результатов численного расчёта.
+
-
* Понятие унимодальной цепочки. Пример.
+
-
* '''Теорема''' об унимодальной цепочке.
+
-
* Открытые проблемы. Влияние размерности пространства параметров на вероятность переобучения.
+
-
=== Пары и тройки алгоритмов ===
+
=== Радемахеровская сложность ===
-
* Постановка задачи.
+
* [[Принцип равномерной сходимости]], задача оценивания вероятности большого равномерного отклонения частот. Метод обучения, максимизирующий переобученность.
-
* '''Теорема''' о вероятности переобучения для двухэлементного семейства алгоритмов. Доказательство теоремы.
+
* Понятие [[Радемахеровская сложность|радемахеровской сложности]], его связь с вероятностью переобучения.
-
* '''Теорема''' о вероятности переобучения для трёхэлементного семейства алгоритмов (без доказательства).
+
* Оценка равномерной сходимости через принцип порождающих и запрещающих множеств.
-
* Частные случаи и обсуждение результатов численного расчёта.
+
* Оценка равномерной сходимости через цепные разложения.
 +
* Точная оценка равномерной сходимости для монотонной цепи алгоритмов через случайное блуждание.
=== Оценки скользящего контроля для метода ближайших соседей ===
=== Оценки скользящего контроля для метода ближайших соседей ===
-
* [[Метрический классификатор|метрические алгоритмы классификации]], [[метод ближайших соседей]].
+
* [[Метрический классификатор|Метрические алгоритмы классификации]], [[метод ближайших соседей]].
-
* Понятие профиля компактности.
+
* Понятие [[Профиль компактности|профиля компактности]].
-
* '''Теорема.''' Точное выражение функционала полного скользящего контроля для метода одного ближайшего соседа (1NN). Доказательство теоремы.
+
* '''Теорема.''' Точное выражение функционала полного скользящего контроля для метода одного ближайшего соседа (1NN).
-
* Свойства профилей компактности.
+
-
* Разделение объектов на шумовые, эталонные и неинформативные. Алгоритм выделения эталонных объектов.
+
* '''Теорема.''' Точное выражение функционала полного скользящего контроля для метода ''k'' ближайших соседей (''k''NN).
* '''Теорема.''' Точное выражение функционала полного скользящего контроля для метода ''k'' ближайших соседей (''k''NN).
 +
* Свойства профилей компактности.
 +
* Алгоритм выделения эталонных объектов (prototype learning). Функция вклада объекта и её эффективное вычисление. Прямые и обратные окрестности. Метрические деревья.
 +
* Разделение объектов на шумовые, эталонные и неинформативные.
 +
* Вычислительные эксперименты с методом ближайших эталонов.
=== Оценки скользящего контроля для монотонных классификаторов ===
=== Оценки скользящего контроля для монотонных классификаторов ===
-
* Монотонные алгоритмы классификации.
+
* Монотонные алгоритмы классификации. Монотонные корректирующие операции в [[Композиция алгоритмов|композициях классификаторов]].
* Понятие клина объекта. Профиль монотонности выборки.
* Понятие клина объекта. Профиль монотонности выборки.
-
* '''Теорема.''' Верхняя оценка скользящего контроля. Доказательство теоремы.
+
* '''Теорема.''' Верхняя оценка полного скользящего контроля.
-
* Монотонные корректирующие операции в алгоритмических композициях.
+
* Монотонный классификатор ближайшего соседа. Взаимосвязь между профилями компактности и монотонности.
-
* Критерии настройки базовых алгоритмов на основе оценок обобщающей способности.
+
* '''Теорема.''' Точная оценка полного скользящего контроля для монотонного классификатора ближайшего соседа (в случае монотонной выборки).
-
 
+
* '''Теорема.''' Верхняя оценка полного скользящего контроля для монотонного классификатора ближайшего соседа (в общем случае).
-
== Вероятностная байесовская теория обобщающей способности ==
+
* Критерии настройки базовых алгоритмов на основе оценок обобщающей способности. Вычислительные эксперименты с монотонными композициями классификаторов.
-
 
+
<!---
-
=== Простейшие оценки вероятности ошибки классификации ===
+
=== Непараметрические статистические критерии ===
-
* Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
+
* Задачи [[Проверка статистических гипотез|проверки статистических гипотез]].
-
* [[Биномиальное распределение]].
+
* [[Гипотеза однородности]], [[гипотеза сдвига]].
-
* Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
+
* Принципиальное различие задач эмпирического предсказания и проверки статистических гипотез.
-
* Обращение оценок.
+
* [[Критерий знаков]].
-
* '''Теорема.''' Оценка вероятности ошибки фиксированного алгоритма (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://http://hunch.net/~jl
+
-
|год = 2005
+
-
|страниц = 28
+
-
}}
+
-
 
+
-
=== Применение теории PAC-Bayes к линейным классификаторам ===
+
-
* Линейный классификатор, понятие отступа (margin), распределение отступов.
+
-
* Принцип минимизации эмпирического риска и принцип максимизации отступов. Замена пороговой функции потерь на её непрерывную аппроксимацию.
+
-
* Краткая история обоснований принципа максимизации отступов. О завышенности оценок обобщающей способности.
+
-
* '''Теорема.''' Конкретизация основной теоремы теории PAC-Bayes для линейных классификаторов. Доказательство теоремы. Выбор априорного и апостериорного распределений. Следствие: ещё одна аппроксимация пороговой функции потерь.
+
-
* Проблема правомерности переноса результатов, полученных для стохастических классификаторов, на обычные классификаторы.
+
-
* Усреднённый классификатор (Averaging classifier) — композиция бесконечного множества стохастических линейных классификаторов путём усреднения по всему апостериорному распределению.
+
-
* '''Теорема.''' Усреднённый классификатор является обычным (не стохастическим) линейным классификатором. Доказательство теоремы.
+
-
* '''Теорема.''' Вероятность ошибки усреднённого классификатора не превышает удвоенной ожидаемой вероятности ошибки стохастического классификатора. Доказательство теоремы.
+
-
 
+
-
'''Литература:'''
+
-
# {{книга
+
-
|автор = Langford J.
+
-
|заглавие = Tutorial on Practical Prediction Theory for Classification
+
-
|ссылка = http://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). Доказательство теоремы.
+
-
* Оценивание расслоения методом Монте-Карло.
+
-
* '''Теорема.''' Оценка по случайной равномерной выборке алгоритмов. Доказательство теоремы.
+
-
* '''Теорема.''' Обобщение на случай бесконечного семейства алгоритмов. Без доказательства.
+
-
'''Литература:'''
+
== Учебные материалы ==
-
# {{книга
+
* '''Учебное пособие по курсу ТНОП:''' [[Media:Voron-2011-tnop.pdf|Voron-2011-tnop.pdf, 3 МБ]] {{важно|(обновление 24 мая 2013)}}.
-
|автор = Langford J.
+
* '''Две лекции:''' [[Media:Voron15-tnop-2lectures.pdf|Voron15-tnop-2lectures.pdf, 1,9 МБ]] {{важно|(обновление 1 апреля 2015)}}.
-
|заглавие = Quantitatively Tight Sample Complexity Bounds (Chapter 8)
+
* '''Обзорная лекция в НМУ 13.04.2013'''. Презентация: '''[[Media:Vorontsov-13apr2013.pdf|(PDF,&nbsp;3.5&nbsp;МБ)]]'''. Дополнение: ''Евгений Соколов''. Линейные классификаторы и случайные блуждания. '''[[Media:Sokolov-13apr2013.pdf|(PDF,&nbsp;380&nbsp;KБ)]]'''. Видео: [http://www.youtube.com/watch?v=37i_Qn9LsGg YouTube].
-
|ссылка = http://citeseer.ist.psu.edu/langford02quantitatively.html
+
-
|издание = Carnegie Mellon Thesis
+
-
|год = 2002
+
-
|страниц = 124
+
-
}}
+
-
== Прочее ==
+
== Ссылки ==
 +
* [[Расслоение и сходство алгоритмов (виртуальный семинар)]]
 +
* [[Предсказывающие неравенства в задаче эмпирической минимизации риска (виртуальный семинар)]]
 +
<!---* Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2010. [[Media:Voron09problems.pdf|PDF, 183&nbsp;КБ]].--->
-
=== Анализ смещения и разброса ===
+
== Программы прошлых лет ==
-
* Разложение ошибки на смещение и разброс (bias-variance decomposition) для случая регрессии.
+
* [[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)/2010]]
-
* Обобщения на случай классификации.
+
* [[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)/2011]]
-
* Оценки для метода ''k'' ближайших соседей и для линейных композиций.
+
-
=== Оценки вероятности ошибки в задачах регрессии ===
+
<!-- Закомментировал пока, чтобы оставить прямую ссылку (см. выше). Иначе целевая страница считается сиротой. Чехович.
-
* [[Линейная регрессия]].
+
{{Служебная:Prefixindex/Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)/}} -->
-
* Оценка матожидания ошибки для многомерной линейной регрессии.
+
-
* '''Теорема.''' [[Информационный критерий Акаике]]. Доказательство теоремы.
+
-
* '''Теорема.''' [[Байесовский информационный критерий]]. Доказательство теоремы.
+
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Текущая версия

Содержание

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

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

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

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

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

На кафедре Интеллектуальные системы ФУПМ МФТИ данный курс является третьей частью трёхсеместрового курса Теория обучения машин.

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

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

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

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

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

Элементы теории Вапника-Червоненкиса

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

Точные комбинаторные оценки для модельных семейств алгоритмов

  • Теорема. Вероятность переобучения полного слоя алгоритмов.
  • Теорема. Вероятность переобучения множества из двух алгоритмов.
  • Теорема. Вероятность переобучения монотонной цепи алгоритмов.
  • Теорема. Вероятность переобучения унимодальной цепи алгоритмов.
  • Теорема. Вероятность переобучения интервала булева куба.
  • Вычислительные эксперименты с модельными семействами и интерпретация результатов.

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

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

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

  • Граф расслоения-связности. Верхняя связность, нижняя связность, неполноценность алгоритма.
  • Монотонный метод обучения. Примеры.
  • Теорема. Оценка расслоения-связности для вероятности переобучения.
  • Теорема. Оценка расслоения-связности для полного скользящего контроля.
  • Оценки для монотонной и унимодальной цепи.
  • Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности.
  • Многомерная монотонная сеть алгоритмов. Примеры.
  • Теорема. Оценка расслоения-связности для многомерной монотонной сети алгоритмов.
  • Вычислительные эксперименты с многомерными сетями.
  • Критерий точности оценок расслоения-связности (без доказательства).

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

  • Логические алгоритмы классификации (rule learning). Примеры прикладных задач. Виды закономерностей: конъюнкции, синдромы, шары, полупространства.
  • Критерии информативности. Примеры. Двухкритериальная оптимизация в (p,n)-пространстве.
  • Теорема о монотонности метода максимизации информативности.
  • Теорема. Оценка расслоения-связности для частоты ошибок I и II рода.
  • Структура классов эквивалентности семейства конъюнкций пороговых предикатов.
  • Стандартные представители классов эквивалентности и граничные подмножества объектов.
  • Послойный восходящий алгоритм вычисления оценки расслоения-связности.
  • Модификация критериев информативности. Применение для отбора признаков. Результаты экспериментов.

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

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

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

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

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

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

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

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

Учебные материалы

Ссылки

Программы прошлых лет

Источник — «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»
Личные инструменты