Комбинаторные оценки полного скользящего контроля и методы обучения монотонных классификаторов

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

Содержание
Введение.

Глава 1. Монотонные классификаторы

1.1. Задача обучения по прецедентам

1.2. Ограничения монотонности

1.3. Монотонные корректирующие операции

1.4. Проблема переобучения.

Глава 2. Оценки ССУ для монотонных классификаторов

2.1. Методы вычисления оценок ССУ

2.1.1 Оценка ССУ в худшем случае

2.1.2 Учет структуры монотонного классификатора.

2.2. Одномерная выборка
2.2.1 Состав множества безошибочных выборок.
2.2.2 Мощность множества безошибочных выборок.
2.2.3 Алгоритм расчета оценок ССУ.
2.2.4 Фильтрация шумовых объектов.
2.3. Многомерная выборка.
2.3.1 Метод обучения монотонных классификаторов.
2.3.2 Гибридная оценка ССУ
2.3.3 Экспериментальная проверка точности гибридной оценки Глава 3. Методы построения монотонных композиций классификаторов
3.1. Независимое обучение базовых алгоритмов.
3.1.1 Принципы построения монотонных композиций.
3.1.2 Результаты экспериментов
3.2. Монотонный бустинг
3.2.1 Наивный метод.
3.2.2 Экспериментальная оценка качества наивного метода
3.2.3 Минимизация комбинаторной оценки ССУ
3.2.4 Экспериментальная оценка качества метода минимизации комбинаторной оценки ССУ
3.2.5 Минимизация гибридной оценки ССУ
3.2.6 Экспериментальная оценка качества метода минимизации гибридной оценки ССУ
Заключение.
Список литературы


Результаты вычислительных экспериментов показали, что минимум верхней оценки полного скользящего контроля в этом случае достигается при обнулении весов всех объектов, нарушающих монотонность выборки. Во второй части рассматривается многомерная обучаЕОщая выборка, в которой объекты описываются конечным множеством вещественнозначиых признаков. Для этого случая предлагается вычислительно эффективный метод построения монотонного классификатора, минимизирующего количество ошибок на обучающей выборке. Доказывается новая комбинаторная оценка CCV, названная гибридной, для семейства монотонных алгоритмов, учитывающая как свойства задачи, так и особенности используемого семейства. ССУ. Предложенная оценка на обучающих выборках размерности больше двух оказалась точнее оценок, полученных ранее другими авторами. Третья глава посвящена описанию прикладных методов построениям монотонных алгоритмических композиций и состоит из двух частей. В первой части монотонная композиция строи тся над независимо обученными базовыми алгоритмами. Проводятся вычислительные эксперименты на реальных задачах, которые показали, что даже при таком подходе монотонная композиция способна увеличивать качество классификации по сравнению с базовыми алгоритмами по отдельности, однако она сильно подвержена риску переобучения. Во второй части для уменьшения риска переобучения предлагается три подхода к построению монотонных композиций, в которых обучение базовых алгоритмов не является независимым. Первый подход основан на идее последовательной настройки базовых алгоритмов на объектах с весами. Каждый последующий базовый алгоритм настраивается на объекте обучающей выборке тем сильнее, чем сильнее этот объект нарушает монотонность выборки. Преимуществом построения такой композиции является простота ее реализации. Однако проведенные вычислительные эксперименты показали, что при количестве базовых алгоритмов больше двух, построенная таким способом композиция начинает сильно переобучаться. Для уменьшения риска переобучения описывается второй подход, основанный на минимизации комбинаторной оценки ССУ, доказанной в работе К. В. Воронцова [], при последовательном добавлении базовых алгоритмов в композицию. Недостатком этого подхода является относительно низкое качество классификации построенной с его помощью монотонной композиции. Для этого построение всех базовых алгоритмов происходит одновременно, причем каждый базовый алгоритм настраивается на объектах обучающей выборки с уникальными для него весами. Поэтому, настраиваемыми параметрами является матрица Ьхт весов объектов обучающей выборки, где т - количество алгоритмов в композиции. Метод минимизации гибридной оценки ССУ основан на принципах метода [радиентного спуска, реализованных для дискретного случая. Изначально вся матрица весов объектов инициализируются произвольными значениями из отрезка [1,2]. Аналитически оценивается вклад каждого объекта генеральной выборки в величину текущего значения гибридной оценки ССУ. Эвристически оценивается направление изменения весов для каждого объекта, которое привело бы к максимальному уменьшению гибридной оценки ССУ, если бы веса всех остальных объектов были бы фиксированы. Используя величину вклада объекта в гибридную оценку ССУ в качестве модуля вектора изменения и рассчитанное направление изменения, проводится итеративный пересчет весов. Процедура останавливается, когда не удается улучшить гибридную оценку ССУ больше, чем заданное число итераций подряд. Для всех подходов приводятся результаты вычислительных экспериментов по оценке качества классификации на модельных задачах различной степени трудности, а также реальных задачи из различных прикладных областей. Результаты экспериментов показали, что при числе базовых алгоритмов большем трех, риск переобучения для построенной с помощью третьего подхода монотонной композиции практически отсутствует. При этом сама композиция позволяет качественно классифицировать очень трудные для базовых алгоритмов задачи. РАН Константину Владимировичу Рудакову за помощь на всех этапах выполнения данной работы.