Оценки обобщающей способности на основе характеристик расслоения и связности семейств функций

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

Оглавление
1 Введение

1.1 Обозначения.

1.2 Вероятность перебучения н обращение оценок.

1.3 Гииергеометрическое распределение .

1.4 Оценка для одного алгоритма

1.4.1 Стандартный критерий переобучения

1.4.2 Квантильиый критерий переобучения

1.5 Комбинаторные оценки ВапникаЧсрвоненкиса и бритвы Оккама . .

1. Оптимальный набор весов в оценке .

1.7 Точная оценка вероятности переобучения но методу МонтеКарло .

2 Обзор литературы
2.1 Модель обучения
2.2 Теория ВапникаЧсрвоненкиса
2.3 Оценки концентрации меры
2.4 енокрытия семейства алгоритмов.
2.5 Всществсннозначные семейства и размерность
2. Радемахеровская сложность
2.7 Оценки с использованием понятия отступа
2.8 подход.
3 Оценки на основе характеристик расслоения семейства
3.1 Профили расслоения семейства алгоритмов.
3.2 Обзор работ но теме
3.3 оценки зависящие от полной выборки
3.4 оценка, зависящая от обучающей выборки
3.5 Выводы.
4 Оценки на основе характеристик сходства алгоритмов в семействе
4.1 Мотивация и постановка задачи.
4.2 Обзор работ по теме.
4.3 Вычисление слагаемых в оценках типа Бонферрони
4.4 Оценка с учетом связности семейства
4.5 Оценка с учетом распределения полустепеней связности алгоритмов . .
4.0 Оценка с учетом монотонных цепей алгоритмов.
4.7 Выводы
5 Характеристики связности семейства линейных классификаторов
5.1 Конфигурации гиперплоскостей.
5.2. Средняя связность
5.3 Зона гиперплоскости в конфигурации
5.4 Дисперсия связности .
О Эксперименты с семейством линейных классификаторов
0.1 Оценки профилей расслоениясвязности по методу МонтеКарло
Ъ.2 Процедура сэмплинга алгоритмов из множества А
0.3 Вычисление оценок.
0.3.1 БЬсПоцснки
0.3.2 Оценки с использованием связности
Список литературы


Предложенные методы учета сходства алгоритмов могут применяться дія конкретных семейств как в рамках комбинаторного подхода, так и в рамках классического РАС-нодхода дпя уточнения оценок, использующих неравенство Буля. Основным практическим приложением оценок обобщающей способности является разработка и обоснование новых методов обучения. Они также могут служить источником качественных соображений при выборе семейства. К примеру, основная оценка настоящей работы показывает, что при повышении сложности семейства, существенным фактором, уменьшающим вероятность переобучения, является увеличение степени сходства алгоритмов в семействе, что может служить обоснованием дія применения семейств, непрерывных но параметрам. Согласно формуле специальности «Теоретические основы информатики», к ней относятся, в числе прочего, «. Таким образом, исследование проблемы переобучения соответствует данной специальности. Апробация работы. Математические методы распознавания образов» ММРО-, г. Интеллектуализация обработки информации» ИОИ-С. G г. Математические методы распознавания образов» ММРО-, г. МФТИ «Современные проблемы фундаментальных и прикладных наук» г. МФТИ «Современные проблемы фундаментальных п прикладных наук» г. Математические методы распознавания образов» ММРО-, г. Результаты неоднократно докладывались на семинарах отдела Интеллектуальных систем ВЦ РАН, (рук. РАН Константин Владимирович Рудаков). Публикации но теме диссертации в изданиях из списка ВАК: [, |. Другие публикации по теме диссертации: [, 8, , 9, G, 7]. Текст диссертации доступен на странице aBTopawyu. MachineLeaming. УчастиикгОешя Kochedykov». Структура и объем работы. Работа состоит из оглавления, введения, пяти глав, заключения, списка обозначений, списка литературы. Краткое содержание работы по главам Во введении определится основные обозначения, определяется функционал вероятности переобучения и процедура его обращения для получения доверительных оценок частоты ошибок на контроле. Определяется кваитильный критерий переобучения. Приводятся комбинаторные аналоги оценки Ва и ка- Червонен к и са (УС-оценка) и оценки «бритвы Оккама» и выводится оптимальное априорное распределение па множестве алгоритмов для оценки *бррт-вы Оккама». Глава 2 содержит краткий обзор некоторых известных методов и результатов теории статистического обучения. В главе 3 выводится комбинаторные аналоги оценок обобщающей способности учитывающих расслоение семейства - так называемых вЬеН-оценок [, ), основанных на следующем соображении. Обычно большая часть алгоритмов в Т имеет вероятность ошибки (или частоту ошибок на полной выборке) около %. Если метод обучения выбирает алгоритм с малой частотой ошибок на обучающей выборке, то фактически выбор производится не из всего семейства алгоритмов, а лишь из небольшой его части, состоящей из алгоритмов с малой ве|юятностыо ошибки. Размер этой части семейства существенно ниже размера всего семейства, что предполагает возможность точнее оценить вероятность переобучения по сравнению, скажем, с классическими оценками Ванника-Чсрвонснкиса. В параграфе 3. В параграфе 3. БЙсП-оценка. В главе 4 выводятся оценки обобщающей способности, учитывающие сходство алгоритмов в семействе. Оценки основаны на следующих соображениях. В УС-оценке функционал равномерного отклонения частот оценивается сверху при помощи неравенства Буля. Известно, что оно может был» сильно завышено при большом числе входящих в него событий. Неравенство, очевидно, становится точным, только если все события в нем взаимоисключающие. При оценивании функционала равномерного уклонения частот, составляющие его события вида «алгоритм а переобучился*, наоборот, существенно совместны и их число в неравенстве крайне велико. Как следствие, неравенство Буля представляет собой один из самых существенных факторов завышсниости УС-оцснки. Можно улучшить оценку неравенства Буля учитывая пересечения входящих в него событий. Пример такого учета дает разложение функционала равномерного отклонения частот по принципу включения-исключения.