Введение к работе
Диссертационная работа относится к математической теории распознавания и классификации и посвящена проблеме повышения обобщающей способности логических алгоритмов классификации, основанных на поиске информативных конъюнктивных закономерностей в массивах прецедентных данных с вещественными, порядковыми и номинальными признаками.
Актуальность темы. Логические алгоритмы классификации широко используются для автоматизации принятия решений в трудноформализуемых областях, таких как медицинская диагностика, геологическое прогнозирование, кредитный скоринг, направленный маркетинг и т.д. Их преимуществом является возможность содержательной интерпретации как внутреннего строения алгоритма, так и принимаемых им решений на естественном языке в терминах предметной области. Однако качество классификации (обобщающая способность) логических алгоритмов, как правило, немного уступает более сложным конструкциям, таким как бустинг или бэггинг над решающими деревьями, которые являются «чёрными ящиками» и не обладают свойством интерпретируемости. Поэтому актуальной задачей является повышение обобщающей способности логических алгоритмов классификации без существенного усложнения их внутреннего строения.
Стандартные подходы теории статистического обучения дают слишком осторожные, пессимистичные оценки обобщающей способности. Эффекты переобучения, возникающие при поиске логических закономерностей, являются относительно слабыми. Они существенно зависят от конкретной выборки данных и потому плохо описываются стандартными оценками. Недав-
но разработанная комбинаторная теория переобучения даёт существенно более точные оценки вероятности переобучения. Актуальность данной диссертационной работы связана ещё и с тем, что она является первым примером практического применения комбинаторной теории переобучения.
Цель работы — получение комбинаторных оценок обобщающей способности логических закономерностей и разработка на их основе новых методов повышения качества логических алгоритмов классификации.
Научная новизна. Получена новая комбинаторная оценка вероятности переобучения, зависящая от характеристик расслоения и связности семейства алгоритмов. Комбинаторные оценки, полученные ранее другими авторами, либо были существенно менее точными, либо опирались на сильные дополнительные предположения о существовании в семействе корректного или хотя бы единственного лучшего алгоритма, что почти невозможно гарантировать на практике.
Впервые описана структура классов эквивалентности конъюнктивных логических закономерностей при разнотипных исходных данных, включающих количественные, порядковые и номинальные признаки.
Предложен новый метод вычисления поправки на переобучение, позволяющий улучшить широкий класс стандартных критериев информативности логических закономерностей.
Методы исследования. Для получения оценок вероятности переобучения использована слабая (перестановочная) вероятностная аксиоматика, комбинаторная теория переобучения, элементы комбинаторки, теории вероятностей и теории графов. Для проверки точности комбинаторных оценок проведены вы-
числительные эксперименты на модельных данных.
Для практического применения полученных оценок вероятности переобучения достаточно встроить процедуру вычисления поправок на переобучение в любой стандартный критерий информативности. Других модификаций не требуется, что позволяет усовершенствовать широкий класс эвристических методов построения логических алгоритмов классификации. Проведены эксперименты на реальных задачах классификации, подтвердившие, что указанная модификация приводит к повышению обобщающей способности алгоритмов классификации.
Положения, выносимые на защиту.
Общая комбинаторная оценка вероятности переобучения, зависящая от характеристик расслоения и связности семейства алгоритмов.
Описание структуры классов эквивалентности семейства пороговых конъюнкций над количественными, порядковыми и номинальными признаками.
Эффективный метод вычисления поправок на переобучение в критериях информативности для широкого класса эвристических алгоритмов поиска логических закономерностей.
Экспериментальное подтверждение того, что предложенный метод приводит к повышению обобщающей способности алгоритмов классификации, представляющих собой композиции логических закономерностей.
Теоретическая значимость. Данная работа вносит существенный вклад в развитие комбинаторной теории переобуче-
ния и является первым успешным примером практического применения комбинаторных оценок вероятности переобучения.
Практическая значимость. Предложенные методы расширяют область применимости логических алгоритмов классификации и повышают качество решения задач классификации в тех предметных областях, где применение логических алгоритмов продиктовано соображениями интерпретируемости.
Апробация работы. Результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих научных конференциях и семинарах:
Всероссийская конференция «Математические методы распознавания образов» ММРО-12, 2005 г. [1];
Международная конференция «Интеллектуализация обработки информации» ИОИ-6, 2006 г. [2];
49-я научная конференция МФТИ, 2006 г. [3];
Всероссийская конференция «Математические методы распознавания образов»ММРО-13, 2007 г. [4, 5, 6];
Международная конференция «Интеллектуализация обработки информации» ИОИ-7, 2008 г. [7];
Всероссийская конференция «Математические методы распознавания образов» ММРО-14, 2009 г. [8].
52-я научная конференция МФТИ, 2009 г. [9];
Международная конференция «Интеллектуализация обработки информации», ИОИ-8, 2010 г. [12, 13].
Научные семинары отдела Интеллектуальных систем Вычислительного центра РАН и кафедры «Интеллектуальные системы» МФТИ, 2006 - 2010 г.г.
Публикации по теме диссертации. Всего публикаций по теме диссертации —13, в том числе в изданиях из Списка, рекомендованного ВАК РФ —одна [11].
Структура и объём работы. Работа состоит из введения, четырёх глав, заключения, списка использованных источников, включающего 58 наименований. Общий объём работы составляет 100 страниц.
