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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: Спецкурс знакомит студентов с современным состоянием [[теория вычислительного обучения|теории вычис...)
Текущая версия (20:11, 19 февраля 2016) (править) (отменить)
(→Учебные материалы)
 
(65 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
Спецкурс знакомит студентов с современным состоянием [[теория вычислительного обучения|теории вычислительного обучения]] (computational learning theory, COLT), исследующей проблему качества восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики [[Вапник, Владимир Наумович|{{S|В. Н. Вапник}]] и [[Червоненкис, Алексей Яковлевич|{{S|А. Я. Червоненкис}}]]. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время развивается очень активно, главным образом, за рубежом.
+
{{TOCright}}
 +
Спецкурс знакомит студентов с [[теория вычислительного обучения|теорией вычислительного обучения]] (computational learning theory, COLT), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным. Родоначальниками этой теории были советские математики [[Вапник, Владимир Наумович|{{S|В. Н. Вапник}}]] и [[Червоненкис, Алексей Яковлевич|{{S|А. Я. Червоненкис}}]]. В 80-е годы эта теория получила широкую мировую известность, и в настоящее время продолжает развиваться.
-
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными? Как избежать [[Переобучение|переобучения]] — ситуации, когда ответы алгоритма слишком точны на обучающей выборке, но недостаточно точны на новых данных, которые не были известны на этапе обучения? Как управлять [[обобщающая способность|обобщающей способностью]] алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
+
Один из основных вопросов теории COLT — как количественно оценить способность алгоритмов классификации и прогнозирования к обобщению эмпирических фактов. В каких случаях можно утверждать, что общие закономерности, выявленные по частным прецедентам, не окажутся ложными, [[предрассудок|предрассудками]]? Как избежать [[Переобучение|переобучения]] — ситуации, когда ответы алгоритма удаётся хорошо подогнать под обучающие данные, но на новых контрольных данных они оказываются существенно менее точными? Как управлять [[обобщающая способность|обобщающей способностью]] алгоритма на стадии его построения? Эти и другие смежные вопросы рассматриваются в данном спецкурсе.
-
Цели спецкурса — научить студентов не только строить и применять обучаемые алгоритмы анализа данных, но и оценивать их надёжность; разрабатывать более надёжные алгоритмы; понимать возможные причины ненадёжной работы обучаемых алгоритмов в прикладных задачах классификации, регрессии, прогнозирования.
+
Цели спецкурса — научить студентов оценивать надёжность алгоритмов обучения; использовать оценки обобщающей способности для разработки более надёжных алгоритмов; применять их для решения прикладных задач классификации, регрессии, прогнозирования.
-
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по [[Комбинаторная теория обобщающей способности|комбинаторной теории обобщающей способности]] и [[Слабая вероятностная аксиоматика|слабой вероятностной аксиоматике]].
+
В основу курса легли современные результаты, полученные в COLT за последнее десятилетие, а также собственные исследования автора по [[Расслоение и сходство алгоритмов (виртуальный семинар)|комбинаторной теории переобучения]] и [[Слабая вероятностная аксиоматика|слабой вероятностной аксиоматике]].
-
Курс читается студентам кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года.
+
На кафедре [[Математические методы прогнозирования (кафедра ВМиК МГУ)|Математические методы прогнозирования]] [[ВМиК]] [[МГУ]] данный курс читается как математический спецкурс студентам 3—5 курсов с 2007 года, в дополнение к обязательному кафедральному курсу [[Машинное обучение (курс лекций, К.В.Воронцов)|Математические методы распознавания образов (ММРО)]].
-
== Первый семестр ==
+
На кафедре [[Интеллектуальные системы (кафедра МФТИ)|Интеллектуальные системы]] [[ФУПМ]] [[МФТИ]] данный курс является третьей частью трёхсеместрового курса [[Машинное обучение (курс лекций, К.В.Воронцов)|Теория обучения машин]].
-
== Второй семестр ==
+
== Комбинаторная теория переобучения ==
-
=== Задача оценивания обобщающей способности и простейшие верхние оценки ===
+
=== Проблема переобучения и перестановочная вероятность ===
 +
* Задачи обучения по прецедентам. Примеры прикладных задач и алгоритмов классификации и регрессии.
 +
* Бинарная функция потерь. Матрица ошибок. Понятия наблюдаемой и скрытой выборки. Понятие переобучения.
 +
* [[Слабая вероятностная аксиоматика]].
 +
* Функционалы качества обучения: вероятность переобучения, вероятность большой частоты ошибок на контроле, полный скользящий контроль.
 +
* Понятия точности и надёжности предсказаний. Обращение оценок.
 +
* Способы применения оценок обобщающей способности. Задачи выбора модели, отбора признаков, оптимизации сложности модели, оптимизации размера локальной окрестности.
 +
* Эмпирические оценки скользящего контроля.
 +
* Сравнение слабой и сильной вероятностной аксиоматики. Финитарные и инфинитарные вероятности. Перенос оценок из слабой аксиоматики в сильную.
-
* Вероятностная постановка задачи классификации. Понятия эмпирической ошибки и вероятности ошибок.
+
=== Предсказание частоты события и гипергеометрическое распределение ===
-
* Биномиальное распределение.
+
* Задача предсказания частоты события. Пример приложения — [[выборочный контроль качества]].
-
* Аппроксимации хвоста биномиального распределения (неравенства Хёфдинга и Чернова, дивиргенция Кульбака-Лейблера).
+
* '''Лемма.''' Частота события в наблюдаемой выборке подчиняется гипергеометрическому распределению.
-
* Обращение оценок.
+
* '''Теорема.''' Точная оценка вероятности большого уклонения частот события на наблюдаемой и скрытой выборках.
-
* '''Теорема 1.''' Оценка вероятности ошибки фиксированного алгоритма (test set bound). Доказательство теоремы. Три следствия: применение трёх различных аппроксимаций хвоста биномиального распределения.
+
* Геометрическая интерпретация.
-
* Бритва Оккама (Occam Razor), понятие априорного распределения на множестве алгоритмов.
+
* Свойства [[Гипергеометрическое распределение|гипергеометрического распределения]]. Способы его вычисления.
-
* '''Теорема 2.''' Оценка вероятности ошибки для произвольного алгоритма (Occam razor bound). Доказательство теоремы. Три следствия: применение аппроксимаций и оценка Вапника-Червоненкиса.
+
* Экспоненциальные верхние и асимптотические оценки. Закон больших чисел в слабой аксиоматике.
-
* Метод структурной минимизации риска (Вапника-Червоненкиса).
+
* Переход от ненаблюдаемой оценки к наблюдаемой. Точная интервальная оценка. Вероятность нуль-события.
-
* '''Теорема 3.''' Об оптимальном априорном распределении. Доказательство теоремы.
+
-
* Открытые проблемы.
+
-
'''Литература:'''
+
=== Элементы теории Вапника-Червоненкиса ===
-
# {{книга
+
* [[Принцип равномерной сходимости]].
-
|автор = ''Langford J.''
+
* Семейство алгоритмов как подмножество векторов булева куба. [[Коэффициент разнообразия]] и [[функция роста]] семейства алгоритмов.
-
|заглавие = Quantitatively Tight Sample Complexity Bounds
+
* '''Теорема.''' Оценка Вапника-Червоненкиса через коэффициент разнообразия (shattering coefficient).
-
|ссылка = http://citeseer.ist.psu.edu/langford02quantitatively.html
+
* Понятие [[Ёмкость|ёмкости]] (VC-dimension), её связь с функцией роста, ёмкость семейства линейных классификаторов.
-
|издание = Carnegie Mellon Thesis
+
* '''Теорема.''' Оценка Вапника-Червоненкиса через ёмкость.
-
|год = 2002
+
* Обращение оценки. Метод [[Структурная минимизация риска|структурной минимизации риска]].
-
|страниц = 124
+
* Проблема завышенности оценок. Анализ причин завышенности, эффекты расслоения и связности.
-
}}
+
* '''Эксперимент.''' Вычисление достаточной длины обучающей выборки.
 +
* Разновидности методов обучения. Пессимистичная, оптимистичная, рандомизированная минимизация эмпирического риска. Максимизация переобученности.
 +
* Программа для вычисления эмпирических оценок вероятности переобучения [[Метод Монте-Карло|методом Монте-Карло]].
 +
* '''Эксперимент''' с четырьмя модельными семействами алгоритмов для выяснения влияния расслоения и связности на вероятность переобучения.
-
=== Стохастические классификаторы и теория PAC-Bayes ===
+
=== Точные комбинаторные оценки для модельных семейств алгоритмов ===
-
* Стохастические классификаторы. Понятия ожидаемой эмпирической ошибки и ожидаемой вероятности ошибок.
+
* '''Теорема.''' Вероятность переобучения полного слоя алгоритмов.
-
* '''Теорема 1.''' Основная теорема теории PAC-Bayes. Доказательство теоремы.
+
* '''Теорема.''' Вероятность переобучения множества из двух алгоритмов.
 +
* '''Теорема.''' Вероятность переобучения монотонной цепи алгоритмов.
 +
* '''Теорема.''' Вероятность переобучения унимодальной цепи алгоритмов.
 +
* '''Теорема.''' Вероятность переобучения интервала булева куба.
 +
* Вычислительные эксперименты с модельными семействами и интерпретация результатов.
 +
<!---
 +
=== Размерность Вапника-Червоненкиса (ёмкость) ===
 +
* Понятие [[Ёмкость|ёмкости]].
 +
* Функция <tex>\Phi_L^h</tex>, её связь с треугольником Паскаля.
 +
* '''Лемма''' о функции <tex>\Phi_L^h</tex>.
 +
* '''Теорема.''' Выражение функции роста через ёмкость.
 +
* Ёмкость конечных множеств. [[Принцип минимума длины описания]].
 +
* '''Теорема.''' Ёмкость семейства [[Линейный классификатор|линейных разделяющих правил]].
 +
* Пример однопараметрического семейства бесконечной ёмкости.
 +
* '''Теорема.''' Ёмкость семейства конъюнкций элементарных пороговых условий.
 +
* Ёмкость некоторых разновидностей [[Нейронная сеть|нейронных сетей]] (без доказательства).
 +
--->
-
'''Литература:'''
+
=== Принцип порождающих и запрещающих множеств ===
-
# {{книга
+
* Простая гипотеза о множествах порождающих и запрещающих объектов.
-
|автор = ''Langford J.''
+
* '''Лемма''' о вероятности получить заданный алгоритм в результате обучения.
-
|заглавие = Tutorial on Practical Prediction Theory for Classification
+
* '''Теорема.''' Точная оценка вероятности переобучения.
-
|ссылка = http://http://hunch.net/~jl
+
* Общая гипотеза о множествах порождающих и запрещающих объектов.
-
|год = 2005
+
* '''Теорема.''' Общая гипотеза верна практически всегда.
-
|страниц = 28
+
* '''Лемма''' и '''Теорема''' для общей гипотезы.
-
}}
+
* '''Теорема.''' Точная оценка функционала полного скользящего контроля.
 +
* '''Теорема.''' Точные оценки для случая, когда существует корректный алгоритм.
-
=== Применение теории PAC-Bayes к линейным классификаторам ===
+
=== Оценки расслоения-связности ===
-
* Линейный классификатор, понятие отступа (margin), распределение отступов.
+
* Граф расслоения-связности. Верхняя связность, нижняя связность, неполноценность алгоритма.
-
* Принцип минимизации эмпирического риска и принцип максимизации отступов. Замена пороговой функции потерь на её непрерывную аппроксимацию.
+
* Монотонный метод обучения. Примеры.
-
* Краткая история обоснований принципа максимизации отступов. О завышенности оценок обобщающей способности.
+
* '''Теорема.''' Оценка расслоения-связности для вероятности переобучения.
-
* '''Теорема 2.''' Конкретизация основной теоремы теории PAC-Bayes для линейных классификаторов. Доказательство теоремы. Выбор априорного и апостериорного распределений. Следствие: ещё одна аппроксимация пороговой функции потерь.
+
* '''Теорема.''' Оценка расслоения-связности для полного скользящего контроля.
-
* Проблема правомерности переноса результатов, полученных для стохастических классификаторов, на обычные классификаторы.
+
* Оценки для монотонной и унимодальной цепи.
-
* Усреднённый классификатор (Averaging classifier) — композиция бесконечного множества стохастических линейных классификаторов путём усреднения по всему апостериорному распределению.
+
* Профиль расслоения-связности. Гипотеза о сепарабельности профиля расслоения-связности.
-
* '''Теорема 3.''' Усреднённый классификатор является обычным (не стохастическим) линейным классификатором. Доказательство теоремы.
+
* Многомерная монотонная сеть алгоритмов. Примеры.
-
* '''Теорема 4.''' Вероятность ошибки усреднённого классификатора не превышает удвоенной ожидаемой вероятности ошибки стохастического классификатора. Доказательство теоремы.
+
* '''Теорема.''' Оценка расслоения-связности для многомерной монотонной сети алгоритмов.
 +
* Вычислительные эксперименты с многомерными сетями.
 +
* Критерий точности оценок расслоения-связности (без доказательства).
-
'''Литература:'''
+
=== Конъюнктивные логические закономерности ===
-
# {{книга
+
* [[Логический классификатор|Логические алгоритмы классификации]] (rule learning). Примеры прикладных задач. Виды [[логическая закономерность|закономерностей]]: конъюнкции, синдромы, шары, полупространства.
-
|автор = ''Langford J.''
+
* [[Информативность|Критерии информативности]]. Примеры. Двухкритериальная оптимизация в (p,n)-пространстве.
-
|заглавие = Tutorial on Practical Prediction Theory for Classification
+
* '''Теорема''' о монотонности метода максимизации информативности.
-
|ссылка = http://http://hunch.net/~jl
+
* '''Теорема.''' Оценка расслоения-связности для частоты ошибок I и II рода.
-
|год = 2005
+
* Структура классов эквивалентности семейства конъюнкций пороговых предикатов.
-
|страниц = 28
+
* Стандартные представители классов эквивалентности и граничные подмножества объектов.
-
}}
+
* Послойный восходящий алгоритм вычисления оценки расслоения-связности.
-
# {{книга
+
* Модификация критериев информативности. Применение для отбора признаков. Результаты экспериментов.
-
|автор = ''McAllester D.''
+
<!---
-
|заглавие = Simplified PAC-Bayesian Margin Bounds
+
=== Рекуррентное вычисление вероятности переобучения ===
-
|год = 2003
+
* Идея рекуррентного обновления информации о каждом алгоритме семейства при добавлении нового алгоритма.
-
}}
+
* '''Лемма.''' Вычисление информации о добавленном алгоритме. Доказательство леммы.
 +
* '''Теорема.''' Правила обновления информации о предыдущих алгоритмах при добавлении нового.
 +
* '''Теорема.''' Упрощённый рекуррентный алгоритм не уменьшает оценку вероятности переобучения.
 +
 
 +
=== Блочные и интервальные точные оценки вероятности переобучения ===
 +
* Определение блока объектов.
 +
* '''Теорема.''' Формула для вычисления вероятности переобучения по блокам.
 +
* '''Теорема.''' Вероятность переобучения для пары алгоритмов.
 +
* Вероятность переобучения интервала булева куба и его нижних слоёв.
 +
--->
 +
 
 +
=== Оценки равномерного отклонения эмпирических распределений ===
 +
* Вероятность большого равномерного отклонения эмпирических функций распределения. Задача проверки гипотезы однородности. Задача оценивания функции распределения.
 +
* Теоремы Колмогорова и Смирнова (без доказательства).
 +
* Усечённый треугольник Паскаля. Случайное блуждание.
 +
* '''Теорема.''' Точная оценка вероятности большого равномерного отклонения эмпирических распределений. Геометрические интерпретации.
 +
* Обобщение на случай вариационного ряда со связками. Почему в этом случае задача оценивания функции распределения намного сложнее.
 +
 
 +
=== Радемахеровская сложность ===
 +
* [[Принцип равномерной сходимости]], задача оценивания вероятности большого равномерного отклонения частот. Метод обучения, максимизирующий переобученность.
 +
* Понятие [[Радемахеровская сложность|радемахеровской сложности]], его связь с вероятностью переобучения.
 +
* Оценка равномерной сходимости через принцип порождающих и запрещающих множеств.
 +
* Оценка равномерной сходимости через цепные разложения.
 +
* Точная оценка равномерной сходимости для монотонной цепи алгоритмов через случайное блуждание.
 +
 
 +
=== Оценки скользящего контроля для метода ближайших соседей ===
 +
* [[Метрический классификатор|Метрические алгоритмы классификации]], [[метод ближайших соседей]].
 +
* Понятие [[Профиль компактности|профиля компактности]].
 +
* '''Теорема.''' Точное выражение функционала полного скользящего контроля для метода одного ближайшего соседа (1NN).
 +
* '''Теорема.''' Точное выражение функционала полного скользящего контроля для метода ''k'' ближайших соседей (''k''NN).
 +
* Свойства профилей компактности.
 +
* Алгоритм выделения эталонных объектов (prototype learning). Функция вклада объекта и её эффективное вычисление. Прямые и обратные окрестности. Метрические деревья.
 +
* Разделение объектов на шумовые, эталонные и неинформативные.
 +
* Вычислительные эксперименты с методом ближайших эталонов.
 +
 
 +
=== Оценки скользящего контроля для монотонных классификаторов ===
 +
* Монотонные алгоритмы классификации. Монотонные корректирующие операции в [[Композиция алгоритмов|композициях классификаторов]].
 +
* Понятие клина объекта. Профиль монотонности выборки.
 +
* '''Теорема.''' Верхняя оценка полного скользящего контроля.
 +
* Монотонный классификатор ближайшего соседа. Взаимосвязь между профилями компактности и монотонности.
 +
* '''Теорема.''' Точная оценка полного скользящего контроля для монотонного классификатора ближайшего соседа (в случае монотонной выборки).
 +
* '''Теорема.''' Верхняя оценка полного скользящего контроля для монотонного классификатора ближайшего соседа (в общем случае).
 +
* Критерии настройки базовых алгоритмов на основе оценок обобщающей способности. Вычислительные эксперименты с монотонными композициями классификаторов.
 +
<!---
 +
=== Непараметрические статистические критерии ===
 +
* Задачи [[Проверка статистических гипотез|проверки статистических гипотез]].
 +
* [[Гипотеза однородности]], [[гипотеза сдвига]].
 +
* Принципиальное различие задач эмпирического предсказания и проверки статистических гипотез.
 +
* [[Критерий знаков]].
 +
* [[Критерий Уилкоксона-Манна-Уитни]].
 +
* [[Критерий серий]].
 +
* [[Критерий Смирнова]].
 +
* Доверительное оценивание. Доверительный интервал для медианы.
 +
--->
 +
 
 +
== Учебные материалы ==
 +
* '''Учебное пособие по курсу ТНОП:''' [[Media:Voron-2011-tnop.pdf|Voron-2011-tnop.pdf, 3 МБ]] {{важно|(обновление 24 мая 2013)}}.
 +
* '''Две лекции:''' [[Media:Voron15-tnop-2lectures.pdf|Voron15-tnop-2lectures.pdf, 1,9 МБ]] {{важно|(обновление 1 апреля 2015)}}.
 +
* '''Обзорная лекция в НМУ 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].
 +
 
 +
== Ссылки ==
 +
* [[Расслоение и сходство алгоритмов (виртуальный семинар)]]
 +
* [[Предсказывающие неравенства в задаче эмпирической минимизации риска (виртуальный семинар)]]
 +
<!---* Открытые проблемы и задачи по спецкурсу «Теория надёжности обучения по прецедентам». 2010. [[Media:Voron09problems.pdf|PDF, 183&nbsp;КБ]].--->
 +
 
 +
== Программы прошлых лет ==
 +
* [[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)/2010]]
 +
* [[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)/2011]]
 +
 
 +
<!-- Закомментировал пока, чтобы оставить прямую ссылку (см. выше). Иначе целевая страница считается сиротой. Чехович.
 +
{{Служебная: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»
Личные инструменты