Теоретико-групповой подход в комбинаторной теории переобучения

• Автор: Фрей, Александр Ильич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 102 с. : ил.

Оглавление
Введение
1 Теория статистического обучения
1.1 Основные определения ЭЬТ
1.2 Неравенства концентрации меры
1.3 Теория Вапника-Червоненкиса
1.4 Радемахеровский процесс
1.5 Неравенство Талаграна
1.6 Локальные оценки избыточного риска
1.7 РАС-Вауев оценки
1.8 Основные выводы
2 Комбинаторный подход
2.1 Основные определения
2.2 Расслоение и связность
2.3 Основные выводы и постановка задачи
3 Теоретико-групповой подход
3.1 Рандомизированный метод обучения и РМЭР
3.2 Перестановки объектов
3.3 Группа симметрии множества алгоритмов
3.4 Покрытия множества алгоритмов
3.5 Теоремы о порождающих и запрещающих множествах (ПЗМ)
3.5.1 ПЗМ для разложения множества алгоритмов на подмножества
3.5.2 ПЗМ для рандомизированного метода обучения

3.6 Основные выводы
4 Точные оценки вероятности переобучения для РМЭР
4.1 Монотонные и унимодальные цепи
4.1.1 Монотонная цепь
4.1.2 Унимодальная цепь
4.2 Многомерные семейства алгоритмов
4.2.1 Пучок монотонных цепей
4.2.2 Многомерная монотонная сеть алгоритмов
4.2.3 Многомерная унимодальная сеть алгоритмов
4.2.4 Разреженные монотонные и унимодальные сети
4.3 Плотные семейства
4.3.1 Слой хэммингова шара
4.3.2 Слой интервала булева куба
4.4 Основные выводы
5 Вычислительные эксперименты на реальных данных
5.1 Эффективное вычисление вС-оценки
5.2 Применение комбинаторных оценок к логическим алгоритмам
5.3 Проблема сэмплирования алгоритмов
5.4 Прогноз кривых обучения логистической регрессии
5.5 Экспериментальное сравнение комбинаторных оценок
Заключение
Список литературы

Введение
Диссертационная работа посвящена проблеме повышения точности комбинаторных оценок вероятности переобучения.
Актуальность темы. При решении задач обучения по прецедентам, восстановления зависимостей по эмпирическим данным, классификации, распознавания образов, прогнозирования часто возникает проблема переобучения. Она состоит в том, что решающая функция (алгоритм), построенная по конечной обучающей выборке, может допускать ошибки на объектах контрольной выборки существенно чаще, чем па объектах обучающей выборки. Для контроля переобучения на этапе построения алгоритма необходимо иметь оценки вероятности переобучения. Такие оценки известны в статистической теории обучения, однако они либо сильно завышены, либо имеют слишком узкую область применимости.
Степень разработанности темы. Основы статистической теории обучения были заложены в работах В. Н. Вапника и А. Я. Червоненкиса в конце 60-х годов. Ими была доказана состоятельность обучения по прецедентам и получены количественные оценки, связывающие обобщающую способность метода обучения с длиной обучающей выборки и сложностью семейства алгоритмов. Основной проблемой этих оценок является их завышенность. Для устранения завышенности предлагалось строить оценки, зависящие от выборки (D. Haussier, 1992); учитывать ширину зазора, разделяющего классы (P. Bartlett, 1998); строить оценки на основе локальной радемахеровской сложности семейства алгоритмов (V. Koltchinskii, 1998); учитывать априорные распределения на множестве алгоритмов (L. Valiant, 1982; D. McAllester, 1999; J. Langford, 2005); а также ряд других подходов.
Комбинаторная теория переобучения показала, что для повышения точности оценок и сокращения переобучения необходимо одновременно учитывать эффекты расслоения и сходства в семействах алгоритмов (К. В. Воронцов, 2010). Выла получена оценка расслоения-связности, справедливая для широкого класса семейств, представимых в виде связного графа (К. В. Воронцов, А. А. Ивахненко, И. М. Решетняк, 2010). Для некоторых модельных частных случаев было показано, что этого достаточно для получения неулуч-

В дальнейшем нам будет нужно доказывать утверждения, аналогичные лемме 3.1, но для более сложных функций. Чтобы упростить эту задачу, введем следующую классификацию функций.
• Симметричной функцией первого рода будем называть д: Ах [X]* —у М, такую что для всех ж € выполнено д(а,Х) = д(жа,жХ)
• Симметричной функцией второго рода будем называть С: 2А х [Х]г —у 2А, такую что для всех Ж 6 выполнено 7Г(?(Л, X) = £(тгЛ, 7гХ);
• Симметричной функцией третьего рода будем называть /: 2А х [Х]^ -у Е, такую что для всех ж £ 6’г, выполнено /(Л, X) = /{ж Л, яХ).
Лемма 3.1 утверждает, что функции п(а,Х) и Да, X) являются симметричными функциями первого рода, а Л(Х) как функция Л и X является симметричной функцией второго рода.
Две следующие теоремы позволяют строить новые симметричные функции из уже имеющихся:
Теорема 3.2. Пусть дт, д2, ■.., др - симметричные функции первого рода, Д, /2,..., }р — симметричные функции третьего рода, Р: Мр —У М — произвольная функция многих переменных. Тогда Р(у, у2, ■ ■ ■., УР) - вновь симметричная функции первого рода, Я/ь/2,..., /р) — симметричная функция третьего рода.
Доказательство. Проведя элементарные выкладки, получим
Р(жа,жХ) = Р(д1(жа,жХ),.. .,др(тта, жХ)) = Р(д1(а,Х),.. .,др(а, X)) = F(а,X), и аналогично для функций третьего рода. ■
Теорема 3.3. Пусть д симметричная функция первого рода, С — симметричная функция второго рода. Тогда
ДЛ,Х) = |С(Л,Х)|н/(Л,Х)= д(а,Х)
а^А.Х)
являются симметричными функциями третьего рода.
Доказательство. Заметим, что для любого Л С А выполнено |Л| = |7ГЛ|, поскольку ж, как элемент группы, является биекцией. Следовательно,
|С(Л,Х)| = |тгС(Л,Х)| = |С(тгЛ,тгХ)|