Комбинаторные оценки вероятности переобучения и их применение в логических алгоритмах классификации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

004618905

На правах рукописи

ИВАХНБНКО АНДРЕЙ АЛЕКСАНДРОВИЧ

КОМБИНАТОРНЫЕ ОЦЕНКИ ВЕРОЯТНОСТИ ПЕРЕОБУЧЕНИЯ И ИХ ПРИМЕНЕНИЕ В ЛОГИЧЕСКИХ АЛГОРИТМАХ КЛАССИФИКАЦИИ

01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 ЗЯНВ2011

Москва — 2010

004618905

Работа выполнена на кафедре интеллектуальных систем Московского физико-технического института (государственного университета)

Научный руководитель: доктор физико-математических наук,

Воронцов Константин Вячеславович

Официальные оппоненты: доктор физико-математических наук,

профессор,

Каркищенко Александр Николаевич

кандидат физико-математических наук, Чехович Юрий Викторович

Ведущая организация: Московский государственный университет

им. М.В. Ломоносова, факультет ВМК

Защита диссертации состоится « . » ЧЯ^О-О^ 2010 г.

, „ АС.

в ЛЛ_ час. на заседании диссертационного совета Д 212.156.05

при Московском физико-техническом институте (государственном университете) по адресу: 141700, г.Долгопрудный Московской обл., Институтский пер. д.9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ). Автореферат разослан « » ^ 2010 г.

Учёный секретарь диссертационного совета Д 212.156.05

О. С. Федько

Общая характеристика работы

Диссертационная работа относится к математической теории распознавания и классификации и посвящена проблеме повышения обобщающей способности логических алгоритмов классификации, основанных на поиске информативных конъюнктивных закономерностей в массивах прецедентных данных с вещественными, порядковыми и номинальными признаками.

Актуальность темы. Логические алгоритмы классификации широко используются для автоматизации принятия решений в трудноформализуемых областях, таких как медицинская диагностика, геологическое прогнозирование, кредитный скоринг, направленный маркетинг и т.д. Их преимуществом является возможность содержательной интерпретации как внутреннего строения алгоритма, так и принимаемых им решений на естественном языке в терминах предметной области. Однако качество классификации (обобщающая способность) логических алгоритмов, как правило, немного уступает более сложным конструкциям, таким как бустинг или бэггинг над решающими деревьями, которые являются «чёрными ящиками» и не обладают свойством интерпретируемости. Поэтому актуальной задачей является повышение обобщающей способности логических алгоритмов классификации без существенного усложнения их внутреннего строения.

Стандартные подходы теории статистического обучения дают слишком осторожные, пессимистичные оценки обобщающей способности. Эффекты переобучения, возникающие при поиске логических закономерностей, являются относительно слабыми. Они существенно зависят от конкретной выборки данных и потому плохо описываются стандартными оценками. Недав-

но разработанная комбинаторная теория переобучения даёт существенно более точные оценки вероятности переобучения. Актуальность данной диссертационной работы связана ещё и с тем, что она является первым примером практического применения комбинаторной теории переобучения.

Цель работы — получение комбинаторных оценок обобщающей способности логических закономерностей и разработка на их основе новых методов повышения качества логических алгоритмов классификации.

Научная новизна. Получена новая комбинаторная оценка вероятности переобучения, зависящая от характеристик расслоения и связности семейства алгоритмов. Комбинаторные оценки, полученные ранее другими авторами, либо были существенно менее точными, либо опирались на сильные дополнительные предположения о существовании в семействе корректного или хотя бы единственного лучшего алгоритма, что почти невозможно гарантировать на практике.

Впервые описана структура классов эквивалентности конъюнктивных логических закономерностей при разнотипных исходных данных, включающих количественные, порядковые и номинальные признаки.

Предложен новый метод вычисления поправки на переобучение, позволяющий улучшить широкий класс стандартных критериев информативности логических закономерностей.

Методы исследования. Для получения оценок вероятности переобучения использована слабая (перестановочная) вероятностная аксиоматика, комбинаторная теория переобучения, элементы комбинаторки, теории вероятностей и теории графов. Для проверки точности комбинаторных оценок проведены вы-

числительные эксперименты на модельных данных.

Для практического применения полученных оценок вероятности переобучения достаточно встроить процедуру вычисления поправок на переобучение в любой стандартный критерий информативности. Других модификаций не требуется, что позволяет усовершенствовать широкий класс эвристических методов построения логических алгоритмов классификации. Проведены эксперименты на реальных задачах классификации, подтвердившие, что указанная модификация приводит к повышению обобщающей способности алгоритмов классификации.

Положения, выносимые на защиту.

1. Общая комбинаторная оценка вероятности переобучения, зависящая от характеристик расслоения и связности семейства алгоритмов.

2. Описание структуры классов эквивалентности семейства пороговых конъюнкций над количественными, порядковыми и номинальными признаками.

3. Эффективный метод вычисления поправок на переобучение в критериях информативности для широкого класса эвристических алгоритмов поиска логических закономерностей.

4. Экспериментальное подтверждение того, что предложенный метод приводит к повышению обобщающей способности алгоритмов классификации, представляющих собой композиции логических закономерностей.

Теоретическая значимость. Данная работа вносит существенный вклад в развитие комбинаторной теории переобуче-

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

Практическая значимость. Предложенные методы расширяют область применимости логических алгоритмов классификации и повышают качество решения задач классификации в тех предметных областях, где применение логических алгоритмов продиктовано соображениями интерпретируемости.

Апробация работы. Результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих научных конференциях и семинарах:

• Всероссийская конференция «Математические методы распознавания образов» ММРО-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 страниц.

Краткое содержание работы по главам

Глава 1. Проблема обобщающей способности в логических алгоритмах классификации

1.1. Задача классификации. Пусть имеется пространство объектов X и конечное множество классов ¥. Объекты описываются набором п признаков : X —> ] — 1,..., п, где — множество допустимых значений ]-го признака. Таким образом, произвольному объекту х € X соответствует признаковое описание (Д(а;),..., 1п(х))- В зависимости от множества признаки делятся на типы: бинарные = {0,1}), номинальные {П^ — конечное множество), порядковые (И^ — конечное упорядоченное множество), количественные (Dj = Ж). Целевой признак у*: X —» ¥ известен только на объектах обучающей выборки X = {х^=1 С X, у{ — у*(х{). Требуется построить алгоритм классификации — функцию а: X —» У, которая но признаковому описанию произвольного объекта х предсказывала бы его

класс у*(х), то есть приближала бы неизвестную функцию у* на всём множестве X.

Методом обучения называется отображение ¡л\ (XxY)£ —> А, которое произвольной конечной выборке X С X с известными классификациями ставит в соответствие алгоритм а — ßX из заданного семейства алгоритмов классификации А.

Задана бинарная функция 1(а,х), называемая индикатором ошибки. Если 1(а,х) — 1, то говорят, что алгоритм а ошибается на объекте х. Обычно полагается 1(а,х) = [а(ж) ф у*(ж)].

Обозначим через п(а,Х) — £ Па>х) число ошибок, а че-

хех

рез ь>(а,Х) — п(а, Х)/\Х\ —частоту ошибок алгоритма а на выборке X. Метод обучения ß называется минимизацией эмпирического риска (МЭР), если

ßX € А(Х) = Arg min п(а,Х),

ае А

и пессимистичным методом МЭР, если цХ = arg max п(а, X).

аеА(Х)

1.2. Проблема переобучения. Если алгоритм а доставляет минимум функционалу v(a,X) на заданной обучающей выборке X, то это ещё не гарантирует, что он будет хорошо приближать целевую зависимость на произвольной контрольной выборке X = (х'г, у'^. Когда качество работы алгоритма на новых объектах, не вошедших в состав обучения, оказывается существенно хуже, чем на обучающей выборке, говорят, что имеет место переобучение или переподгонка (overfitting).

В комбинаторной теории переобучения предполагается, что X —конечное множество из L = I + к объектов, и все его разби-

ения на обучающую выборку длины (I и контрольную длины к равновероятны. Основной задачей является получение как можно более точной верхней оценки вероятности переобучения

< Ф) = РПцХ,Х) - ^Х,Х) > е]. (1.1)

Коль скоро такая оценка получена, можно утверждать, что и(цХ,Х) ^ и(^Х,Х) + е(гу) с вероятностью 1 — 77, достаточно близкой к единице, где е(г}) — функция, обратная к г}(е).

1.3. Логические алгоритмы классификации представляют собой композиции информативных логических правил.

Логическое правило — это функция вида г: X —> {0,1} из некоторого параметрического семейства функций Л. Обычно к правилам предъявляют требование интерпретируемости: правило должно зависеть от небольшого числа признаков и допускать запись на естественном языке. В данной работе рассматривается наиболее распространённый тип правил — конъюнкции пороговых предикатов:

г(х) = г(а:;с1,...,сп) = П[^^с'], (1.2)

где х = (ж1,...,!") € К" — признаковое описание объекта х, ш С {1,... ,п} — подмножество признаков, с? € —порог по З-му признаку, - одна из операций сравнения: для

количественных и порядковых признаков, = для номинальных.

Говорят, что правило г выделяет объект х, если г{х) — 1.

Логическая закономерность — это правило, удовлетворяющее требованию информативности — оно должно выделять достаточно много объектов одного из классов у € У, и практически не выделять объекты других классов. Для поиска правил

класса у по обучающей выборке X С X в семействе г € К решается задача двухкритериальной оптимизации:

На практике двухкритериальную задачу сводят к однокритери-альиой и оптимизируют критерий информативности H(P,N). Известны десятки различных критериев: энтропийный, индекс Джини, точный тест Фишера, тест х2> тест и)2 и другие. Однако ни один из них нельзя назвать безусловно предпочтительным. Выбор критерия информативности является эвристикой.

Поскольку каждая закономерность выделяет лишь часть выборки, алгоритм классификации строится как композиция закономерностей. Одной из наиболее распространённых конструкций является взвешенное голосование закономерностей:

а(х) = arg max ^ wrr(x),

где Пу — множество правил класса у, гиг ^ 0 — вес правила г.

1.4. Постановка задачи. Чтобы алгоритм классификации не был переобучен, составляющие его закономерности также не должны быть переобучены. Поэтому первая задача, которая ставится в данной работе — получить оценки вероятности переобучения для семейства правил вида (1.2). Вторая задача — применить полученные оценки для улучшения стандартных критериев информативности.

Глава 2. Комбинаторные оценки вероятности переобучения для пороговых конъюнкций

2.1. Оценки расслоения-связности. Метод порождающих и запрещающих множеств, предложенный К. В. Воронцовым, основан на гипотезе, что для любого алгоритма а Е А можно записать необходимое и достаточное условие того, что он будет выбран методом обучения ц по выборке X. В данной работе предлагается более простое необходимое условие, которое приводит к верхней оценке вероятности переобучения.

Пусть X = {х\,..., Х1} множество А состоит из алгоритмов а с попарно различными векторами ошибок (/(а, Гипотеза 2.1. Множество А, выборка X и метод /х таковы, что для каждого алгоритма а е А можно указать два множества: порождающее Ха С X и запрещающее Х'а С X такие, что

[^=а] < [ХаСХ][Х'аСХ]. (2.1)

Р т С3

Введём гипергеметрическое распределение Н/т (з) =

Ы

и его функцию распределения II¿т (г) = £ ¡1{т (з).

з=0

Теорема 2.1. Если гипотеза 2.1 верна, то для любого с 6 (0,1) справедлива верхняя оценка вероятности переобучения

< ]Г Р«Нь:т" (Ф)); Р[мА=а] = (2.2)

где Ьа = Ь- \Ха\ - \Х'а\, £а = \Ха\, та = п(а,Х\Ха\Х'а), ва{£) = ъ(п(а,Х) - ек) - п(а,Ха).

Определим отношение порядка на алгоритмах а ^ 6 как

естественное отношение порядка на их векторах ошибок: I(a, х) ^ I(b, х) для всех х 6 X. Определим метрику на алгоритмах как хэммингово расстояние между их векторами ошибок:

L

р(а,Ь) = - I(b,x)\. Алгоритмы а и Ъ называются

■i=1

связанными, если а ^Ь и р(а, 6) = 1.

Лемма 2.2. Если ц — метод пессимистичной минимизации эмпирического риска, то (2.1) выполнено, если положить

Xa = {х Е X | 3b е Л: /(а,ж) < /(6,ж), а О, /?(а,6) = l}, Х'а = {xeX\3beA: 1(Ъ,х) < 1(а,х), Ь < а}.

Величину q(a) = |Ха| будем называть связностью, а величину г(а) = — подчинённостью алгоритма а.

Теорема 2.3. Если ¡л—метод пессимистичной минимизации эмпирического риска, то для вероятности переобучения справедлива оценка сверху:

QÍ~q{a)

X) < ^ ^¡^Hl( í (n(e> X) - е*)) .

обЛ L

Если в этой оценке положить q(a) = r(a) = 0 для всех а, то получится оценка, известная в теории Вапника-Червоненкиса:

QM^Y,^^ (ÍHa,X) - ek)),

аеА

частично учитывающая расслоение семейства алгоритмов по числу ошибок n(a, X), и совсем не учитывающая связность.

2.2. Структура классов эквивалентности семейства пороговых конъюнкций. Оценки вероятности переобучения,

полученные выше для алгоритмов классификации, легко переносятся на логические правила, если соответствующим образом определить индикатор ошибки: 1(г, ж;) = [r(xi) ф [yj=y]].

Допустим, что значения х\ каждого признака j £ со попарно различны на объектах Х( е X. Тогда без ограничения общности можно предполагать, что все признаки принимают целые значения 1,..., L, и никакие два объекта не имеют равных значений одного признака. Значения порогов cJ в правилах (1.2) также имеет смысл выбирать только из целых значений 0,..., L.

Пусть и и V — произвольные объекты из X. Будем говорить, что объект и доминируется множеством объектов S С X (запись: и -< S), если для каждого j е ш существует объект s 6 5, такой, что и3 < s-7.

Определение 2.1. Подмножество S С X называется педо-минирующимся, если любой объект s € S не доминируется подмножеством S\s.

Введём множество всех недоминирующихся подмножеств мощности q, Mq= {S С X: \S\ = q,VstS s^ S\s}. Лемма 2.4. Для любого объекта х из недоминирующегося подмножества S найдется хотя бы один признак j € oj, для которого х3 = max s3. причём

ses

п

IJ Arg max(sJ) = S. l se

Поставим в соответствие подмножеству S правило

rix, S) = г(х: шаха:1,... ,тахх").

4 ' у xes xes

Правила эквивалентны, если их векторы ошибок совпадают.

Лемма 2.5. Пусть Е с R — класс эквивалентности правил, с>(г) —j-й параметр правила г. Классу Е принадлежит правило

rE(x) — rixjmin^fr'), • • •, min с" (г')).

w v r'eß ' r'eE '

Будем называть правило ге{х) стандартным представителем класса эквивалентности Е.

Теорема 2.6. Существует взаимно однозначное соответствие между множеством всех классов эквивалентности и множеством всех недоминирующихся подмножеств.

Для каждого класса эквивалентности Е существует единственное недоминирующееся подмножество S: ге{х) = r(x,S).

п

Число классов эквивалентности равно Yh

g=0

Полученные результаты обобщаются на случай, когда признак может принимать одинаковые значения на различных объектах, а также на порядковые и номинальные признаки.

2.3. Эффективные методы перебора классов эквивалентности и вычисления оценок вероятности переобучения.

Для эффективного вычисления оценки вероятности переобучения по Теореме 2.3 предлагается послойный алгоритм перебора классов эквивалентности. Вклады слоев в вероятность переобучения быстро убывают с ростом номера слоя, равного числу ошибок правила n(r, X). Поэтому для вычисления оценки достаточно обойти лишь несколько нижних слоёв, содержащих небольшую долю всех классов эквивалентности, и тем самым избежать перебора основной массы классов эквивалентности.

2.4. Информативность пороговых конъюнкций с поправкой на переобучение. Стандартные критерии информативно-

сти строятся исключительно по обучающей выборке и не учитывают эффект переобучения. При фиксированном подмножестве признаков ш переобучение возникает вследствие оптимизации порогов С], ] € и. Оно проявляется в том, что значения критериев Р(г,Х) и Х(г,Х) на обучающей выборке X оказываются оптимистично смещёнными относительно Р(г,Х) и Ы(г,Х) на контрольной выборке X. Предположим, что оценка Р(г,Х) завышена на АР, оценка Ат{г,Х) занижена на AN. Предлагается с помощью оценок вероятности переобучения, и затем обращения этих оценок, оценить величину смещений АР, АХ, чтобы при отборе закономерностей пользоваться модифицированным критерием информативности Н(Р - АР, N 4- ДАТ). Величина смещений АР, АМ нетривиальным образом зависит от выборки, поэтому введение таких поправок может существенно влиять на отбор закономерностей во множества Яу.

2.5. Эксперименты на модельных данных. Генерируются две модельные выборки длины Ь — 200 с п = 2 признаками. В первой выборке существует единственная наилучшая закономерность и эффект расслоения проявляется максимально четко. Вторая выборка несколько зашумлена, в ней также существует наилучшая закономерность, но эффект расслоения выражен значительно слабее. Выборки подобраны таким образом, чтобы при обучении по случайным подвыборкам длины £ = 100 информативности найденных в обеих выборках закономерностей в среднем совпадали. На контрольных подвыборках длины к = Ь—£, информативность найденной закономерности в первой подвыборке оказывается заметно выше чем во второй. Таким образом, метод оптимизации информативности сильнее переобучается на второй выборке. Однако стандартные критерии информативности не позволяют выявить эти различия. После

введения поправки описанным выше методом модифицированный критерий информативности начинает надёжно отличать более информативную выборку от менее информативной.

Глава 3. Методы построения логических алгоритмов классификации

В данной главе рассматриваются эвристические методы поиска логических закономерностей и построения логических алгоритмов классификации как композиций закономерностей, реализованные автором в рамках библиотеки Рогесзуэ ЪодгсРго. Для всех методов приводятся их описания в виде псевдокода, показывающего ключевые идеи программной реализации, но скрывающего второстепенные технические детали.

3.1. Методы оценивания информативности правил.

Рассматриваются критерии информативности, реализованные в библиотеке Ьо§1сРго: е, ¿-критерий, гипергеометрический критерий (точный тест Фишера), энтропийный, индекс Джини.

3.2. Методы поиска информативных конъюнкций. Рассматриваются следующие методы: случайный поиск, случайный поиск с адаптацией, усечённый поиск в ширину, построение Парето-оптимального фронта и Парето-расслоения по двум критериям (Р, И). Кроме того, рассматривается алгоритм бинаризации исходных данных, применяемый на подготовительной стадии перед поиском конъюнкций, а также методы стабилизации и редукции, применяемые после поиска конъюнкций для улучшения их качества, удаления переобученных и дублирующих конъюнкций.

3.3. Методы построения композиций информативных правил. Рассматриваются следующие методы построения алгоритмов классификации: жадный алгоритм покрытий для построения решающего списка (комитета старшинства), алгоритм бустинга для построения взвешенного голосования, алгоритм построения простого или взвешенного голосования.

3.4. Методы оценивания апостериорных вероятностей.

Во многих практических задачах требуется, чтобы алгоритм классификации не только относил объект к тому или иному классу, но и выдавал оценки апостериорных вероятностей принадлежности объекта классу. Для взвешенного голосования эта задача решается с помощью калибровки Платта, однако когда объект покрывается малым числом закономерностей, точность данной оценки может оказаться невысокой. В случае решающего списка данный метод вообще неприменим. В обоих случаях проблема решается путём оценивания апостериорной вероятности для каждого правила в отдельности.

Пусть гу{х) — закономерность класса у. Оценку апостериорной вероятности того, что объект х принадлежит классу с Е У при условии, что он выделяется закономерностью гу, в данной работе предлагается вычислять по формуле

РМ м 1>_ Рс(Гу)-&Рс

| Гу(Х) I) _ ДРс) + + АНсу

где ДРс и ДЛ^с — поправки на переобучение, вычисляемые по описанной выше методике. Без этих поправок оценка была бы смещённой (оптимистично завышенной в случае с — у или пессимистично заниженной при с фу).

Глава 4. Вычислительные эксперименты на реальных данных

В данной главе описываются вычислительные эксперименты на реальных данных из репозитория 1101, в которых сравниваются различные эвристические алгоритмы построения логических алгоритмов классификации. Показывается, что введение поправок на переобучение практически во всех задачах и для всех критериев информативности приводит к улучшению обобщающей способности отдельных закономерностей, и, как следствие, алгоритма классификации в целом.

В Заключении приведены основные результаты работы.

Основные результаты диссертации:

1. Получена общая комбинаторная оценка вероятности переобучения, зависящая от характеристик расслоения и связности семейства алгоритмов.

2. Описана структура классов эквивалентности семейства пороговых конъюнкций над количественными, порядковыми и номинальными признаками.

3. Предложен эффективный метод вычисления поправок на переобучение в критериях информативности для широкого класса эвристических алгоритмов поиска логических закономерностей.

4. Экспериментально показано, что предложенный метод приводит к повышению обобщающей способности алгоритмов классификации, представляющих собой композиции логических закономерностей.

Публикации по теме диссертации

1. Кочедыков Д. А., Ивахнеико А. А., Воронцов К. В. Система кредитного скоринга на основе логических алгоритмов классификации // Докл. всеросс. конф. Математические методы распознавания образов-12. — М.: МАКС Пресс,

2005. - С. 349-353.

2. Воронцов К. В., Ивахненко А. А. Эмпирические оценки локальной функции роста в задачах поиска логических закономерностей // Искусственный Интеллект. — Донецк,

2006. - С. 281-284.

3. Ивахненко А. А. Обобщающая способность логических закономерностей // Труды 49-й научной конференции МФТИ. Часть VII. - 2006. - С. 286-287.

4. Ивахненко А. А., Воронцов К. В. Верхние оценки переобученное™ и профили разнообразия логических закономерностей // Докл. всеросс. конф. Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 33-37.

5. Кочедыков Д. А., Ивахненко А. А., Воронцов К. В. Применение логических алгоритмов классификации в задачах кредитного скоринга и управления риском кредитного портфеля банка // Докл. всеросс. конф. Математические методы распознавания образов-13.— М.: МАКС Пресс, 2007. — С. 484-488.

6. Кузнецов М. Р., ТуркинП.Ю., Воронцов К. В., Дьяконов А. Г., Ивахненко А. А., Сиваченко Е. А. Прогнозирование результатов хирургического лечения атеросклероза на основе анализа клинических и иммунологических данных // Докл. всеросс. конф. Математические методы распознава-

ния образов-13. - М.: МАКС Пресс, 2007. - С. 537-539.

7. Воронцов К. В., Ивахнепко A.A. Мета-обучение критериев информативности логических закономерностей // Докл. межд. конф. Интеллектуализация обработки информации, ИОИ-7. - Симферополь, 2008. - С. 52-54.

8. Воронцов К. В., Ивахненко А. А., Инякип А. С., Лисица А. В., Минаев П. Ю. «Полигон» — распределённая система для эмпирического анализа задач и алгоритмов классификации // Докл. всеросс. конф. Математические методы распознавания образов-14. — М.: МАКС Пресс, 2009.-С. 503-506.

9. Ивахненко А. А. Верхняя оценка вероятности переобучения логических закономерностей // Труды 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». — 2009. — С. 64-67.

10. Ивахненко А. А. Точная верхняя оценка вероятности переобучения для корректных логических правил //В сборнике «Модели и методы обработки информации». — М.: МФТИ., 2009.-С. 62-64.

11. Ивахненко А. А. Точная верхняя оценка вероятности переобучения для корректных логических правил // Труды МФТИ.-Том 2-ДО 3-М.: МФТИ., 2010. - С. 81-87.

12. Ивахненко А. А. О вероятности переобучения пороговых конъюнкций // Докл. межд. конф. Интеллектуализация обработки информации, ИОИ-8. — М.: МАКС Пресс, 2010. — С. 57-60.

13. Лисица A.B., Воронцов К.В., Ивахненко A.A., ИнякинА.С., Синцова В. В. Системы тестирования алгоритмов машинного обучения: MLcomp, Tunedlt и Полигон // Докл.

межд. конф. Интеллектуализация обработки информации,

ИОИ-8. - М.: МАКС Пресс, 2010. - С. 157-160.

В работах с соавторами лично соискателем сделано следующее:

• разработана и реализована библиотека логических алгоритмов Гогесзуэ 1^юРго [1, 5, 6];

• реализована система тестирования алгоритмов классификации и расчета статистик [8, 13];

• проведены эксперименты по исследованию обобщающей способности логических алгоритмов классификации, построению профиля разнообразия закономерностей ¡2, 4];

• проведены эксперименты по изучению зависимости обобщающей способности логических закономерностей от их параметров, таких как длинна закономерности, ранг по информативности и пр. [7]

ИВАХНЕНКО АНДРЕЙ АЛЕКСАНДРОВИЧ

КОМБИНАТОРНЫЕ ОЦЕНКИ ВЕРОЯТНОСТИ ПЕРЕОБУЧЕНИЯ И ИХ ПРИМЕНЕНИЕ В ЛОГИЧЕСКИХ АЛГОРИТМАХ КЛАССИФИКАЦИИ

Автореферат Подписано в печать: 15.11.2010 Заказ № 4522 Тираж - 100 экз. Печать трафаретная. Объем: 1 усл.п.л. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www. au tor eferat. ru

Введение

1 Обобщающая способность

1.1 Задача классификации.

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

1.3 Логические алгоритмы классификации.

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

2 Комбинаторные оценки вероятности переобучения

2.1 Метод порождающих и запрещающих множеств

2.2 Оценки расслоения-связности.

2.3 Структура классов эквивалентности

2.4 Обобщение на случай номинальных и порядковых признаков

2.5 Численные методы оценивания вероятности переобучения.

2.6 Информативность с поправкой на переобучение.

2.7 Численные эксперименты на модельных данных

2.7.1 Анализ завышенное™ оценки расслоения-связности.

2.7.2 Экспериментальное подтверждение методики.

3 Построение логических алгоритмов классификации

3.1 Методы оценивания информативности правил.

3.1.1 Эвристический пороговый е, 5-критерий.

3.1.2 Гипергеометрический критерий (точный тест Фишера)

3.1.3 Энтропийный критерий и индекс Джини.

3.1.4 Парето-оптимальный фронт по паре критериев (р, п).

3.2 Методы поиска информативных конъюнкций.

3.2.1 Бинаризация исходной информации.

3.2.2 Стабилизация набора правил.

3.2.3 Случайный поиск.

3.2.4 Случайный поиск с адаптацией.

3.2.5 Усеченный поиск в ширину.

3.3 Методы построения композиций информативных правил

3.3.1 Решающий список.

3.3.2 Взвешенное голосование

3.3.3 Логистическая регрессия.

3.4 Методы оценивания апостериорных вероятностей.

4 Вычислительные эксперименты на реальных данных

4.1 Модифицированный критерий информативности.

4.2 Анализ переобученное™ правил.

4.3 Уменьшение переобученности

4.4 Оценивание апостериорной вероятности

Диссертационная работа относится к математической теории распознавания и классификации и посвящена проблеме повышения обобщающей способности логических алгоритмов классификации, основанных на поиске информативных конъюнктивных закономерностей в массивах прецедентных данных с вещественными, порядковыми и номинальными признаками.

Актуальность темы. Логические алгоритмы классификации широко используются для автоматизации принятия решений в трудноформализуемых областях, таких как медицинская диагностика, геологическое прогнозирование, кредитный скоринг, направленный маркетинг и т.д. Их преимуществом является возможность содержательной интерпретации как внутреннего строения алгоритма, так и принимаемых им решений на естественном языке в терминах предметной области. Однако качество классификации (обобщающая способность) логических алгоритмов, как правило, немного уступает более сложным конструкциям, таким как бустинг или бэггинг над решающими деревьями, которые являются «чёрными ящиками» и не обладают свойством интерпретируемости. Поэтому актуальной задачей является повышение обобщающей способности логических алгоритмов классификации без существенного усложнения их внутреннего строения.

Стандартные подходы теории статистического обучения дают слишком осторожные, пессимистичные оценки обобщающей способности. Эффекты переобучения, возникающие при поиске логических закономерностей, являются относительно слабыми. Они существенно зависят от конкретной выборки данных и потому плохо описываются стандартными оценками. Недавно разработанная комбинаторная теория переобучения даёт существенно более точные оценки вероятности переобучения. Актуальность данной диссертационной работы связана ещё и с тем, что она является первым примером практического применения комбинаторной теории переобучения.

Цель работы — получение комбинаторных оценок обобщающей способности логических закономерностей и разработка на их основе новых методов повышения качества логических алгоритмов классификации.

Научная новизна. Получена новая комбинаторная оценка вероятности переобучения, зависящая от характеристик расслоения и связности семейства алгоритмов. Комбинаторные оценки, полученные ранее другими авторами, либо были существенно менее точными, либо опирались на сильные дополнительные предположения о существовании в семействе корректного или хотя бы единственного лучшего алгоритма, что почти невозможно гарантировать на практике.

Впервые описана структура классов эквивалентности конъюнктивных логических закономерностей при разнотипных исходных данных, включающих количественные, порядковые и номинальные признаки.

Предложен новый метод вычисления поправки на переобучение, позволяющий улучшить широкий класс стандартных критериев информативности логических закономерностей.

Методы исследования. Для получения оценок вероятности переобучения использована слабая (перестановочная) вероятностная аксиоматика, комбинаторная теория переобучения, элементы комбинаторки, теории вероятностей и теории графов. Для проверки точности комбинаторных оценок проведены вычислительные эксперименты на модельных данных. Для практического применения полученных оценок вероятности переобучения предлагается встраивать вычисление поправок на переобучение в стандартные критерии информативности, что позволяет усовершенствовать широкий класс эвристических методов построения логических алгоритмов классификации. Для проверки данного подхода проведены эксперименты на реальных задачах классификации.

Положения, выносимые на защиту.

1. Общая комбинаторная оценка вероятности переобучения, зависящая от характеристик расслоения и связности семейства алгоритмов.

2. Описание структуры классов эквивалентности семейства пороговых конъюнкций над количественными, порядковыми и номинальными признаками.

3. Эффективный метод вычисления поправок на переобучение в критериях информативности для широкого класса эвристических алгоритмов поиска логических закономерностей.

4. Экспериментальное подтверждение того, что предложенный метод приводит к повышению обобщающей способности алгоритмов классификации, представляющих собой композиции логических закономерностей.

Теоретическая значимость. Данная работа вносит существенный вклад в развитие комбинаторной теории переобучения и является первым успешным примером практического применения комбинаторных оценок вероятности переобучения.

Практическая значимость. Предложенные методы расширяют область применимости логических алгоритмов классификации и повышают качество решения задач классификации в тех предметных областях, где применение логических алгоритмов продиктовано соображениями интерпретируемости.

Апробация работы. Результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих научных конференциях и семинарах:

• Всероссийская конференция «Математические методы распознавания образов» ММРО-12, 2005 г. [24];

• Международная конференция «Интеллектуализация обработки информации» ИОИ-6, 2006 г. [11];

• 49-я научная конференция МФТИ, 2006 г. [18];

• Всероссийская конференция «Математические методы распознавания образов»ММРО-13, 2007 г. [22, 25, 26];

• Международная конференция «Интеллектуализация обработки информации» ИОИ-7, 2008 г. [12];

• Всероссийская конференция «Математические методы распознавания образов» ММРО-14, 2009 г, [13].

• 52-я научная конференция МФТИ, 2009 г. [19];

• Международная конференция «Интеллектуализация обработки информации», ИОИ-8, 2010 г. [20, 28].

• Международная конференция «Распознавание образов и анализ изображений: новые информационные технологии», РОАИ-Ю, 2010 г. [58].

• Научные семинары отдела Интеллектуальных систем Вычислительного центра РАН и кафедры «Интеллектуальные системы» МФТИ, 2006 - 2010 г.г.

Публикации по теме диссертации. Всего публикаций по теме диссертации — 13, в том числе в изданиях из Списка, рекомендованного ВАК РФ — одна [21].

Краткое содержание работы по главам. Работа состоит из четырёх глав.

В первой главе вводятся определения и обозначения, необходимые для дальнейшего рассмотрения задач классификации, проблемы переобучения и логических алгоритмов классификации. Приводится краткий обзор литературы по данным вопросам. Глава завершается формальной постановкой основной задачи данной работы — получения оценок вероятности переобучения для логических закономерностей и использования этих оценок для улучшения обобщающей способности логических алгоритмов классификации.

Во второй главе предлагается новая оценка вероятности переобучения, учитывающая свойства расслоения и связности семейства алгоритмов. Эта оценка, исходно сформулированная для алгоритмов классификации, распространяется на параметрическое семейство конъюнктивных правил. Описывается структура классов эквивалентности данного семейства и эффективный алгоритм вычисления оценки расслоения-связности. Предлагается использовать эту оценку для модификации стандартных критериев информативности правил. Модификация сводится к введению «поправки на переобученность». Приводятся результаты экспериментов на модельных данных, показывающие, что модифицированные критерии, в отличие от стандартных, позволяют избежать переобучения, возникающего в результате оптимизации порогов в термах, составляющих конъюнкцию.

В третьей главе описываются алгоритмы, реализованные автором в рамках библиотеки логических алгоритмов классификации Forecsys Logic Pro, в их числе: градация вещественных признаков, синтез информативных закономерностей, построение множеств Парето-оптимальных закономерностей и расслоения Парето, построение композиций закономерностей.

В четвёртой главе приводятся результаты экспериментов на реальных данных, показывающие, что применение критериев информативности с поправкой на переобучение, как правило, улучшает обобщающую способность логических алгоритмов классификации.

Благодарности

Автор выражает глубокую признательность научному руководителю д. ф.-м, н. Константину Вячеславовичу Воронцову за постановку задачи и постоянную поддержку в ходе исследований, заведующему кафедрой «Интеллектуальные системы» чл.-корр. РАН Константину Владимировичу Рудакову за ценные замечания, к. ф.-м. н. Вадиму Викторовичу Стрижову за внимание к работе, помощь в поиске литературы и подборе данных для экспериментов, к. ф.-м. н. Ольге Сергеевне Федько за организационную помощь, коллегам по работе и учёбе в аспирантуре МФТИ за плодотворные обсуждения работы и моральную поддержку.

Основные результаты диссертации:

1. Получена общая комбинаторная оценка вероятности переобучения, зависящая от характеристик расслоения и связности семейства алгоритмов.

2. Описана структура классов эквивалентности семейства пороговых конъюнкций над количественными, порядковыми и номинальными признаками.

3. Предложен эффективный метод вычисления поправок на переобучение в критериях информативности для широкого класса эвристических алгоритмов поиска логических закономерностей.

4. Экспериментально показано, что предложенный метод приводит к повышению обобщающей способности алгоритмов классификации, представляющих собой композиции логических закономерностей.

Заключение

1. Ботов П. В. Точные оценки вероятности переобучения для монотонных и унимодальных семейств алгоритмов // Всеросс. конф. Математические методы распознавания образов-14. — М.: МАКС Пресс, 2009.— С. 7-10.

2. Ботов П. В. Точные оценки вероятности переобучения для несимметричных многомерных семейств алгоритмов // Межд. конф. Интеллектуализация обработки информации ИОИ-8. — М.: МАКС Пресс, 2010. — С. 20-23.

3. Бушманов О. Н., Дюкова Е. В., Журавлёв Ю. И., Кочетков Д. В., Рязанов В. В. Система анализа и распознавания образов // Распознавание, классификация, прогноз. — 1989. — Т. 2. — С. 250-273.

4. Вапник В. Н., Червоненкис А. Я. О равномерной сходимости частот появления событий к их вероятностям // ДАН СССР,— 1968.— Т. 181, № А. — С. 781-784.

5. Вапник В. Н., Червоненкис А. Я. О равномерной сходимости частот появления событий к их вероятностям // Теория вероятностей и ее применения. — 1971. Т. 16, № 2. - С. 264-280.

6. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.

7. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. Т. 13. — С. 5-36.

8. Воронцов К. В. Комбинаторный подход к проблеме переобучения // Всеросс. конф. Математические методы распознавания образов-14. — М.: МАКС Пресс, 2009.- С. 18-21.

9. Воронцов К. В. Точные оценки вероятности переобучения // Доклады РАН. — 2009. Т. 429, № 1. - С. 15-18.

10. Воронцов К. В., Ивахненко А. А. Эмпирические оценки локальной функции роста в задачах поиска логических закономерностей // Искусственный Интеллект. — 2006. — С. 281-284.

11. Воронцов К. В., Ивахненко А. А. Мета-обучение критериев информативности логических закономерностей // Межд. конф. Интеллектуализация обработки информации ИОИ-7. — М.: МАКС Пресс, 2008. С. 52-54.

12. Донской В. И, Вашта А. И. Дискретные модели принятия решений при неполной информации. — Симферополь: Таврия, 1992. — 166 с.

13. Журавлёв Ю. И., Рязанов В. В., Сенъко О. В. «Распознавание». Математические методы. Программная система. Практические применения.— М.: Фазис, 2006.

14. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999.

15. Загоруйко Н. Г., Елкина В. Н., Лбов Г. С. Алгоритмы обнаружения эмпирических закономерностей. — Новосибирск: Наука, 1985.

16. Ивахненко А. А. Обобщающая способность логических закономерностей // Труды 49-й научной конференции МФТИ сСовременные проблемы фундаментальных и прикладных наук>. Часть VII. Управление и прикладная математика. М.: МФТИ, 2006. — С. 286-287.

17. Ивахпвнко А, А. О вероятности переобучения пороговых конъюнкций // Межд. конф. Интеллектуализация обработки информации ИОИ-8.— М.: МАКС Пресс, 2010. С. 57-60.

18. Ивахненко А. А. Точная верхняя оценка вероятности переобучения для корректных логических правил // Труды МФТИ. — 2010. — Т. 2, № 3. — С. 5762.

19. Ивахненко А. А., Воронцов К. В. Верхние оценки переобученности и профили разнообразия логических закономерностей // Математические методы распознавания образов-13. М.: МАКС Пресс, 2007. — С. 33-37.

20. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ, 2-ое издание. — Вильяме, 2006. — 1296 с.

21. Кочедыков Д. А., Ивахненко А. А., Воронцов К. В. Система кредитного скоринга на основе логических алгоритмов классификации // Математические методы распознавания образов-12. — М.: МАКС Пресс, 2005. — С. 349-353.

22. Лбов Г. С. Методы обработки разнотипных экспериментальных данных. — Новосибирск: Наука, 1981.

23. Лисица А. В., Воронцов К. В., Ивахненко А. А., Инякин А. С., Синцова В. В. Системы тестирования алгоритмов машинного обучения: М1сошр, ЬипесШ и полигон // Межд. конф. Интеллектуализация обработки информации ИОИ-8.-М.: МАКС Пресс, 2010,- С. 157-160.

24. Толстихин И. О. Вероятность переобучения плотных и разреженных семейств алгоритмов // Межд. конф. Интеллектуализация обработки информации ИОИ-8. — М.: МАКС Пресс, 2010.- С. 83-86.

25. Asuncion A., Newman D. UCI machine learning repository: Tech. rep.: University of California, Irvine, School of Information and Computer Sciences, 2007.

26. Au W.-H., Chan К. С. C., Yao X. A novel evolutionary data mining algorithm with applications to churn prediction // IEEE Trans. Evolutionary Computation. — 2003. Vol. 7, no. 6. - Pp. 532-545.

27. Bartlett P. L., Mendelson S. Rademacher and Gaussian complexities: Risk bounds and structural results // COLT: 14th Annual Conference on Computational Learning Theory. Vol. 2111. — Springer, Berlin, 2001. — Pp. 224-240.

28. Boucheron S., Bousquet O., Lugosi G. Theory of classification: A survey of some recent advances // ESAIM: Probability and Statistics. — 2005. — no. 9. — Pp. ,323-375.

29. Breiman L. Technical note: Some properties of splitting criteria // Machine Learning. — 1996. — Vol. 24. Pp. 41-47.

30. Cohen W. W. Fast effective rule induction // Proc. of the 12th International Conference on Machine Learning, Tahoe City, CA. — Morgan Kaufmann, 1995. — Pp. 115-123.

31. Cohen W. W., Singer Y. A simple, fast and effective rule learner // Proc. of the 16 National Conference on Artificial Intelligence. — 1999. — Pp. 335-342.

32. Dubner P. N. Statistical tests for feature selection in KORA recognition algorithms // Pattern Recognition and Image Analysis. — 1994. — Vol. 4, no. 4. — P. 396.

33. Frank E., Witten I. H. Generating accurate rule sets without global optimization // Proc. 15th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 1998. Pp. 144-151.

34. Frei A. I. Accurate estimates of the generalization ability for symmetric set of predictors and randomized learning algorithms // Pattern Recognition and Image

35. Analysis. — 2010. Vol. 20, no. 3. — P. 241-250.

36. Freund Y., Schapire R. E. A decision-theoretic generalization of on-line learning and an application to boosting // European Conference on Computational Learning Theory. — 1995. Pp. 23-37.

37. Fürnkranz J. Modeling rule precision // LWA / Ed. by A. Abecker, S. Bickel, U. Brefeld, I. Drost, N. Henze, O. Herden, M. Minor et al. — Humbold-Universitat Berlin, 2004. Pp. 147-154.

38. Fürnkranz J., Flach P. A. Roc 'n' rule learning-towards a better understanding of covering algorithms // Machine Learning. — 2005. — Vol. 58, no. 1. — Pp. 39-77.

39. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. — 533 pp.

40. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning, 2nd ed. — Springer, 2009.

41. Janssen F., Fürnkranz J. On trading off consistency and coverage in inductive rule learning // LWA / Ed. by K.-D. Althoff, M. Schaaf. Vol. 1. - University of Hildesheim, Institute of Computer Science, 2006. — Pp. 306-313.

42. Janssen F., Fürnkranz J. Meta-learning rule learning heuristics // LWA / Ed. by A. Hinneburg. — Martin-Luther-University Halle-Wittenberg, 2007. — Pp. 167174.

43. Langford J., Shawe-Taylor J. PAC-Bayes and margins // Advances in Neural Information Processing Systems 15. — MIT Press, 2002. — Pp. 439-446.

44. Martin J. K. An exact probability metric for decision tree splitting and stopping // Machine Learning. — 1997. — Vol. 28, no. 2-3. — Pp. 257-291.

45. Quinlan J. Induction of decision trees // Machine Learning.— 1986.— Vol. 1, no. 1.- Pp. 81-106.

46. Quinlan J. R. C4.5: Programs for machine learning. — Morgan Kaufmann, San Francisco, CA, 1993.

47. Quinlan J. R. Bagging, boosting, and C4.5 // AAAI/IAAI, Vol. 1.— 1996.— Pp. 725-730.

48. Schapire R. E., Singer Y. Improved boosting using confidence-rated predictions // Machine Learning. — 1999. — Vol. 37, no. 3. — Pp. 297-336.

49. Vayatis N., Azencott R. Distribution-dependent Vapnik-Chervonenkis bounds // Lecture Notes in Computer Science. — 1999. — Vol. 1572. — Pp. 230-240.

50. Vorontsov К. V. Combinatorial probability and the tightness of generalization bounds // Pattern Recognition and Image Analysis. — 2008.— Vol. 18, no. 2.— Pp. 243-259.

51. Vorontsov К. V. On the influence of similarity of classifiers on the probability of overfitting // Pattern Recognition and Image Analysis: new information technologies (PRIA-9). — Vol. 2. — Nizhni Novgorod, Russian Federation, 2008. — Pp. 303-306.

52. Vorontsov К. V. Splitting and similarity phenomena in the sets of classifiers and their effect on the probability of overfitting // Pattern Recognition and Image Analysis. — 2009. Vol. 19, no. 3. - Pp. 412-420.

53. Vorontsov К. V. Exact combinatorial bounds on the probability of overfitting for empirical risk minimization // Pattern Recognition and Image Analysis. — 2010. — Vol. 20, no. 3. P. 269-285.