Оценки вероятности переобучения многомерных семейств алгоритмов классификации

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

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

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

1.1 Основные понятия и обозначения.

1.2 Постановка задачи.

2 Методы получения комбинаторных оценок вероятности переобучения

2.1 Послойный метод.

2.2 Метод индикаторов.

2.3 Метод МонтеКарло для решения задачи о семействе алгоритмов .

3 Модельные семейства алгоритмов

3.1 Пара алгоритмов.

3.2 Монотонная и унимодальная цепи
3.2.1 Монотонная цепь .
3.2.2 Унимодальная цепь
3.3 Многомерные симметричные модели.
3.3.1 Единичная окрестность
3.3.2 Единичный гиперкуб.
3.3.3 Монотонная сеть
3.3.4 Связка цепей.
33.5 Унимодальная сеть
3.3.б Мажорируемость многомерных семейств
3.4 Несимметричные модели.
3.4.1 Монотонная несимметричная сеть.
3.4.2 Несимметричная связка цепей
3.4.3 Унимодальная несимметричная сеть.
3.4.4 Мажорируемость многомерных семейств
4 Применение модельных семейств алгоритмов в эксперименте
4.1 Аппроксимация семейств
4.1.1 Аппроксимация унимодальной сети монотонной сетью удвоенной размерности.
4.1.2 Отбрасывание старших слоев семейства.
4.1.3 Сопоставление графиков Се полученных в эксперименте с графиками Сс от монотонных сетей.
4.1.4 Аппроксимация семейств, получаемых на практике, унимодальной несимметричной сетью
4.1.5 Использование метода МонтеКарло для оценки шдюятности переобучения семейств.
4.2 Метод минимизации предсказанного риска
4.2.1 Бинарное решающее дерево.
4.2.2 Эксперимент па реальных данных.
Приложение
Заключение
з
Введение
Диссертационная работа относится к математической теории распознавания и классификации и посвящена проблеме повышения обобщающей способности алгоритмов классификации с помощью точных комбинаторных оценок вероятности переобучения для модельных семейств алгоритмов.
Актуальность


Связность предполагает, что для каждого алгоритма в семействе найдётся множество похожих алгоритмов, отличающихся от него только на одном объекте выборки. Семейства, не обладающие свойствами расслоения и связности, могут переобучаться настолько сильно, что их практическое применение становится нецелесообразным. Точные комбинаторные оценки вероятности переобучения были ранее получены для модельных семейств алгоритмов — монотонных и унимодальных цепей, интервалов, шаров и слоев булева куба, обладающих тем или иным видом симметрии. Реальные семейства, порождаемые практическими задачами, как правило, имеют болсс сложную нерегулярную структуру, что препятствует получению точных комбинаторных оценок. Поэтому актуальной теоретической проблемой является построение и изучение таких модельных семейств, которые обладали бы расслоением, связностью, размерностью, несимметричностью, то есть всеми ключевыми свойствами реальных семейств, и могли бы использоваться для их аппроксимации. Актуальной практической проблемой является применение оценок переобучения для повышения качества решения прикладных задач распознавания и классификации. Научная новизна. Предложены и исследованы модельные семейства алгоритмов — связки монотонных цепей, монотонные и унимодальные сети, обладающие свойствами расслоения, связности, размерности и несимметричности. Для всех семейств получены точные комбинаторные формулы вероятности переобучения и математического ожидания частоты ошибок на генеральной выборке. Предложен метод минимизации предсказанного риска (МПР), основанный на замене реального семейства подходящим по структуре модельным семейством, с последующей минимизацией ожидаемой частоты ошибок на генеральной выборке. В отличие от метода минимизации структурного риска, МПР учитывает особенности конкретной выборки. В отличие от скользящего контроля, МПР не требует многократного обучения, и потому вычислительно гораздо более эффективен. Предложена общая методика применения МПР в итерационных методах обучения, показано её применение на примере решающих деревьев. Методы исследования. Для получения оценок вероятности переобучения использовалась перестановочная вероятностная аксиоматика, комбинаторная теория надёжности обучения по прецедентам, элементы комбинаторики и теории вероятностей. Для проверки точности оценок проводились численные эксперименты на модельных данных методом Монте-Карло. Для сравнения предлагаемых методов классификации со стандартными проводились эксперименты на реальных данных из репозитория С1. Положения, выносимые на защиту. Методы получения комбинаторных оценок вероятности переобучения на основе послойного разложения семейства. Оценки вероятности переобучения модельных семейств алгоритмов: связки цепей, монотонной сети, унимодальной сети и их несимметричных аналогов. Методика повышения обобщающей способности итерационных методов обучения с помощью комбинаторных оценок вероятности переобучения. Теоретическая значимость. Данная работа вносит существенный вклад в развитие комбинаторной теории надёжности обучения по прецедентам. Метод послойного разложения семейства (глава 2) может быть применён для получения оценок вероятности переобучения в более широком классе семейств. Практическая значимость. Метод минимизации предсказанного риска (глава 4) может быть применён для повышения качества классификации в широком классе итерационных методов обучения, включая решающие деревья, решающие списки, композиции логических закономерностей, алгоритмы вычисления оценок, и другие. Апробация работы. Всероссийская конференция «Математические методы распознавания образов» ММРО-, г. Международная конференция «Интеллектуализация обработки информации* ИОИ-8, г. Всероссийская конференция «Математические методы распознавания образов» ММРО-, г. Результаты работы неоднократно докладывались на семинарах отдела Интеллектуальных систем ВЦ РАН. Публикации по теме диссертации. Всего публикаций по теме диссертации — четыре, в том числе в изданиях из Списка, рекомендованного ВАК РФ —одна [3|.