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

005000803

Гуз Иван Сергеевич

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

Специальность 05.13.17 - теоретические основы информатики

1 7 НОЯ 2011

Автореферат

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

Москва - 2011

005000803

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

Научный руководитель:

доктор физико-математических наук, ВОРОНЦОВ Константин Вячеславович.

Официальные оппоненты:

академик РАН,

доктор физико-математических наук, профессор МАТРОСОВ Виктор Леонидович,

кандидат физико-математических наук РОМАНОВ Михаил Юрьевич.

Ведущая организация:

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

Защита диссертации состоится » 2011 г. в 'S часов на

заседании диссертационного совета Д 002.017.02 в Учреждении Российской академии наук Вычислительного центра им. A.A. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д.40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан «

2011г.

Учёный секретарь диссертационного /Г\ ,

совета Д 002.017.02, д.ф.-м.н., профессор ijbii/j^-^-u^-' В.В.Рязанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

Л

ком смысле. Чем больше оценка, тем с большей уверенностью можно утверждать, что объект принадлежит классу +1.

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

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

Цели диссертационной работы

Целями диссертации являются:

1) Вывод комбинаторных оценок полного скользящего контроля для семейства монотонных алгоритмов

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

Научная новизна работы

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

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

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

Методы исследования

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

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

5

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

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

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

2. Метод построения оптимального монотонного классификатора, минимизирующего эмпирический риск.

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

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

Теоретическая ценность работы

В диссертации развивается теория надёжности обучения по прецедентам К. В. Воронцова: доказывается возможность построения качественных алгоритмических композиций без каких-либо априорных предположений о вероятностной природе распределения объектов обучения.

Практическая ценность работы

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

6

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

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

Апробация и публикации

По теме диссертации опубликовано 7 работ, в том числе две работы [2,3] — в изданиях из списка, рекомендованного ВАК РФ. Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах:

• 15-я Всероссийская конференция «Математические методы распознавания образов», г. Петрозаводск, 2011 г. [1];

• 14-я Всероссийская конференция «Математические методы распознавания образов», г. Суздаль, 2009 г. [4];

• 7-я международная конференция «Интеллектуализация обработки информации», г. Симферополь, 2007 г. [7];

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

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

Структура диссертации

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

1.1. Задача обучения по прецедентам. Пусть задано конечное множество Х = {ХрХ,,...,^}, состоящее из I объектов, в котором каждый объект х1 описывается вектором из п вещественных признаков еК". Этим объектам соответствует множество классов ¥ = {у1,у1,...,у1), в котором значения классов у, е {-1,+1} ■ Назовем множество X генеральной выборкой, и будем считать, что среди объектов нет двух одинаковых.

Если для двух объектов х, е X и х) е X выполняется условие

\/к = \,...,п:х* > х), то будем считать, что х, > х]. Если же 3к,1:х* >х*,х] <х'], то будем считать, что объекты х^ и х] несравнимы и будем обозначать х, |[ х/.

Пусть также задано множество А, элементы которого называются алгоритмами, где каждый алгоритм веЛ:К"->{-1,+1}. Существует бинарная функция /:ЛхХ-»{0,1}, называемая индикатором ошибки. Если 1(а,х) = 1, то алгоритм а еА допускает ошибку на объекте х. Пусть С - фиксированное натуральное число, £<1,. Обозначим через [X]' множество всех (-элементных подмножеств генеральной выборки X.

Задача обучения по прецедентам состоит в выборе на основе некоторой обучающей выборки X с [X]' некоторого алгоритма а е А, определяющего для каждого объекта генеральной выборки X его класс. Выборка X = Х\Х для выбранного на основе обучающей выборки X алгоритма а называется контрольной.

Методом обучения называется отображение ц-.Х А, которое ставит в соответствие обучающей выборке Л" с[Х]' некоторый алгоритм аеА. Метод обучения р называется методом минимизации эмпирического риска (МЭР), если р(Х) £ А(Х) = Лгёгшп(]Г [аЫу, < 0]),

пессимистичным МЭР, если ^'(Х) =а^тах(£[а(х,Ь', <0]) п оптимистичным

МЭР, если р"1"{X) = <0]). Метод обучения называется взее-

аеЛ(Х) „.¡х

шенным МЭР, если он также учитывает веса объектов:

р(Х) € А(Х) = Аг61Шп(]Г м»Ха{х,)у, < 0]).

1.2. Ограничения монотонности. В качестве множества алгоритмов А в работе рассматривается семейство монотонных алгоритмов классификации, то есть аеА<=>(Ух,,х2 еК":х, >х2 =>а(х,)>а(х2)).

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

и. Монотонные корректирующие операции. При решении прикладных

задач классификации часто возникает ситуация, когда ни один из существующих

9

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

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

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

1.4. Проблема переобучения. Семейство монотонных алгоритмов включает в себя большое число различных на обучающей выборке алгоритмов. Поэтому, частота ошибок на обучающей выборке у обученного с помощью МЭР монотонного алгоритма, может быть существенно ниже частоты ошибок на априори неизвестных ему объектах контрольной выборки. В этом случае говорят, что имеет место переобучение (оуегЯй^), то есть чрезмерная настройка алгоритма на обучающую выборку.

Для решения этой проблемы в работе рассматривается функционал полного скользящего контроля (complete cross-validation, CCV), характеризующий среднюю частоту ошибок алгоритма на контрольной выборке X при всевозможных способах разбиения генеральной выборки X на обучающую и контрольную:

ССГ=а(/лХ) = 4 £ v(M(X),X) = ExV(M(nn

СL Л1Л'=Х

В этой формуле символом Ех обозначена операция усреднения по всевозможным разбиениям генеральной выборки X на обучающую и контрольную выборки, a v(a,X) означает частоту ошибок алгоритма а на выборке X:

v m \x\h

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

Глава 2. Оценки полного скользящего контроля для монотонных классификаторов.

2.1. Методы вычисления комбинаторных оценок CCV. В работе предлагается два различных способа расчета верхних оценок CCV.

Первый способ позволяет рассчитать верхнюю и нижнюю оценки взвешенного МЭР за полиномиальное время, если для всех объектов X их веса w( е Z и каждый объект описывается единственным числовым признаком, то есть xi е К.

Для нахождения оценок CCV свяжем с каждым объектом генеральной выборки х, два множества:

1. Множество безошибочных выборок Е°(¡): Е°(0 = {Х:х,еХ, У/^еМ /(М^).*/) = 0}£[Х]'.

2. Множество ошибочных выборок £'(/):

£'(/) = {Х:*, еЛ\ У//еМ ад,1;) = 1}с[Х]'. Теорема 2.1. Справедливы следующие верхняя и нижняя оценки ССУ:

Т^гЬ ^ Д) < ССУ < ао"-,Х) < 1 -—¿I £°(/) I.

^ сд ^ * Ч м

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

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

2.2. Одномерная выборка. В одномерном случае, монотонные алгоритмы имеют вид a(x) = sign(x-cJ и определяются положением порога са. Два алгоритма, у которых векторы ошибок на генеральной выборке X совпадают, являются неразличимыми на этой выборке. Будем полагать, что множество А состоит только из тех алгоритмов, у которых векторы ошибок на X попарно различны. В этом случае |Л|=£ + 1. Пронумеруем алгоритмы множества А = {а1,аг,...,аш) в

соответствии с возрастанием порога и для определенности выберем значение порога с, для каждого алгоритма <х по следующему правилу:

с, = х, -1;

с, =(*,-, +х,)/2, 1 </</,;

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

вид ¡л(Х) = а^ гтпп(^м'[а(х')у' < 0]).

ееА ы\

Без ограничения общности будем считать, что /е{0,1,...,/?} объектов обучающей выборки X с индексами /ру'2,.../( расположены правее объекта х: и £-( объектов с индексами расположены левее объекта х1 (рис. 1).

(1) - Ш-(л,.,.,)••• (п2)

(/-1+1) (/-1+2) ((-!) (О О-О-О-О-

0,) - Иг) - (/м) - (У.) - ((-)

Рис. 1. Расположение объектов обучающей выборки X относительно объекта х:. Под объектами подписаны их индексы в генеральной выборке. Над объектами - номера в обучающей выборке.

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

/ЛХ)= шш

к=(-1* 2.....Ы

1>

/(Х)= шах

.....1-,

/¡=(-,+ 1.....м

■■тШГЛХ)У,

У и'"у" ;/°(Л= тах У и>"у"

= тах(0,/_(*));

ЛР=* У """ ЧР"*

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

13

Теорема 2.2.1. Обучающая выборка X, в которой I объектов лежат правее объекта х,, будет являться безошибочной для этого объекта, тогда и только тогда, когда одновременно выполняются следующие условия:

£°(0 =

X:

(е [гшп(Д I - О, тах(<? -1 + 1,0)]

"/-(*) + №)> 0, если и =+1

/°{Х) + < 0, если у,--\ Теорема 2.2.2. Обучающая выборка X, в которой I объектов лежат правее объекта х,, будет являться ошибочной для этого объекта, тогда и только тогда, когда одновременно выполняются следующие условия:

х,е X

I е [тт(*, I - /"), тах(^ -/+1,0)]

£'(0 =

Х\

/°(Х) + /+(Х)<0,еслиу,=+1 + > 0, если у1 = -1

Для упрощения формулы расчета мощности множеств ошибочных и безошибочных выборок обозначим операцию суммирования по всевозможным выборкам X* с[Х]', лежащим правее объекта символом . Символом обозначим операцию суммирования по всевозможным выборкам с [%]'"', лежащим левее объекта . В этих обозначениях введем функции:

(°лш)==1;[/д-п=«ь

= =-V]; г. а,1,5) = (XI=4

Мощность множеств ошибочных и безошибочных выборок для объекта х, рассчитывается на основе следующих формул:

р= X ['=0]^^(/,^)+[о</<аХ а,(-и)

|«тт(ГД-/Л 1>0 165^ 5->"'

тах((-|+1.0)/ _( >

Значения функций { рассчитываются рекурсивно на основе следующих теорем: Теорема 2.2.3. Ц/,/,*) = Г°(| +1,/ -1.« - + ГД/ + 1,Г,л).

Теорема 2.2.4. Г_0,= — 1,/ -1,5 - и»,_,>>_,) + С(/ -1,1,«). Вычислительная сложность расчета оценок ССУ на основе приведенных формул расчета мощности ошибочных и безошибочных множеств равна

и;). При этом затраты памяти, необходимой для расчета, имеют такую же

Если брать веса объектов из множества м* е {0,1}, то есть принимать решение об использовании того или иного объекта для обучения, то вычислительная сложность процедуры вычисления ССУ будет порядка 0(1.1}), а затраты памяти -

0(а2).

Основываясь на этой процедуре, был предложен и реализован метод жадного спуска для подбора оптимального набора весов объектов из множества {0,1}, минимизирующего значение верхней оценки ССУ. Результаты экспериментов на модельных задачах показали, что предложенный метод действительно позволяет фильтровать шумовые объекты, тем самым уменьшая риск переобучения.

2.3. Многомерная выборка. Аналогично одномерному случаю будем считать, что все монотонные алгоритмы из множества А различимы на генеральной выборке Хс К", то есть их векторы ошибок на выборке X попарно различны. В этом случае любой монотонный алгоритм аеА полностью определяется двумя непересекающимися множествами:

I

I:

оценку

Я={хеХ:а(л) = +1}; П ={хбХ:ф) = -1}.

Эти множества должны обладать свойством, необходимым и достаточным для монотонности алгоритма а: V*, еС1_,\/х2 е:х2 >х1 Vх21|х{.

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

Назовем пару индексов (;',/) дефектной, если выполняется одно из условий

> ХР У, < У > или < хр У, > У) ■

Теорема 2.3.1. Вычислительная сложность обучения монотонного алгоритма а, минимизирующего эмпирический риск, имеет порядок О(т-Л), где т -число дефектных пар, образованных объектами генеральной выборки X, а с! ~ число объектов генеральной выборки, образующих дефект.

Доказательство этой теоремы основано на конструктивном методе нахождения оптимального монотонного алгоритма с помощью сведения исходной задачи к задаче поиска минимального вершинного покрытия в графе, образованном всеми дефектными парами исходной генеральной выборки. Поскольку этот граф является двудольным, то для решения этой задачи существует эффективный алгоритм Хопкрофта-Карпа. В худшем случае, вычислительная сложность нахождения оптимального монотонного алгоритма с помощью Теоремы 2.3.1 есть 0{Предложенный метод находит монотонный алгоритм с помощью МЭР быстрее наилучшего из существовавших ранее методов, сложность которого оценивается как 0(<Р).

Назовем объект х, дефектным, если он входит хотя бы в одну дефектную пару и бездефектным, если он не входит ни в одну дефектную пару. Обозначим О0 - множество всех дефектных объектов генеральной выборки. Назовем клином объекта х) е X множество:

Бездефектным клином объекта л; еХ назовем множество W{xl) = W(xl)jDa. Обозначим w, мощность клина объекта х,, а w- мощность бездефектного клина объекта .

Для устранения неопределенности в выборе оптимального алгоритма с помощью МЭР, рассмотрим подсемейство монотонных классификаторов ближайшего соседа, имеющих вид:

а(х) = Xargminp(^,x)),

где U — некоторая монотонная подвыборка X, функция расстояния от классифицируемого объекта х до объекта х. е U зависит от класса объекта х} и определяется следующим образом:

fmax(jrJ -х\...,х" >>(*,) = +1

P{X,Xj) y{Xj) = -Г

В работах К.В. Воронцова было доказано, что построенный таким образом алгоритм а(х) будет монотонным на R", если он является монотонным на всех объектах X.

Множество объектов X, на которых алгоритм ju(X), минимизирующий эмпирический риск, ошибается, называется множеством немонотонности. Обозначим его D. Степень немонотонности 8 генеральной выборки X определяется как \D\lL.

Заметим, что выборка X/D является монотонной, то есть Vx,, х2 е X/ D: х, >х2 =>у, >у2. Для каждого объекта х,еХ удалим из генеральной выборки множество £>/{*,}. Обозначим Ц мощность множества D/{x,}, то есть Ц =| £> | -{х, е D]. Оставшиеся объекты упорядочим по возрастанию расстояния от объекта пронумеровав их двойными индексами: xn,...,xI L_x_D:. Таким образом, Р(х,, )<р(х„х,г)<...< р(х,, ).

Обозначим 1т(х,) ошибку, возникающую, если правильный ответ у, заменить ответом на его т -ом соседе :

Используя введенные обозначения, доказывается верхняя оценка (XV.

Теорема 2.3.2. Если метод р минимизирует эмпирический риск в классе всех монотонных алгоритмов, то:

Доказанная оценка состоит из двух слагаемых. Первое слагаемое объясняет зависимость ССУ от степени немонотонности генеральной выборки. Чем больше мощность множества немонотонности £>, тем больший вклад вносит это слагаемое в оценку ССУ. Поэтому, назовем первое слагаемое немонотонной частью оценки ССУ. Второе слагаемое объясняет зависимость ССУ от структуры монотонного алгоритма. Его значение тем больше, чем больше объектов оказывается рядом в смысле введенного с помощью функции р расстояния. Поэтому, назовем второе слагаемое некомпактной частью оценки ССУ. Поскольку оценка ССУ учитывает как свойства выборки, так и структуру алгоритмов, то назовем ее гибридной. Основное преимущество гибридной оценки в том, что чем более монотонная выборка, тем ближе эта оценка к точному значению ССУ. Если генеральная выборка является монотонной, то есть | £)|=0, то гибридная оценка совпадает с точным значением ССУ.

Проведенные численные эксперименты на модельных задачах показали, что точность гибридной оценки ССУ превосходит точность другой комбинаторной оценки ССУ, полученной К. В. Воронцовым, если размерность признакового описания объектов больше двух. Причем чем больше размерность признакового описания объектов, тем гибридная оценка ССУ становится более точной.

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

классификаторов.

3.1 Монотонная коррекция при независимом обучении базовых алгоритмов является самым простым способом построения монотонной композиции. Все

1«1 ¿'^¿»тахи.О.+г.-И-И

С* С

С'

базовые алгоритмы обучаются независимо на обучающей выборке, и в пространстве их оценок принадлежности объектов к классу +1 на основе Теоремы 2.2.1 строится монотонный классификатор ближайшего соседа.

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

В качестве базовых алгоритмов использовались следующие классические алгоритмы: решающие деревья С50, CART, QUEST, CHAID; нейронная сеть на основе многослойного персептрона; к-ближайших соседей, логистическая регрессия и SVM с автоматическим выбором функции ядра.

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

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

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

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

19

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

Третий подход основан на идее построения базовых алгоритмов таким образом, чтобы в пространстве оценок гибридная оценка ССУ монотонного классификатора, доказанная в Теореме 2.3.2, была минимальна. Для этого построение всех базовых алгоритмов происходит одновременно, причем каждый базовый алгоритм настраивается на объектах генеральной выборки с уникальными для него весами. Поэтому, параметрами МЭР является матрица Ly.ni весов объектов обучающей выборки, где т - количество алгоритмов в композиции.

Метод минимизации гибридной оценки ССУ основан на принципах метода градиентного спуска, реализованных для дискретного случая. Изначально вся матрица весов объектов инициализируются произвольными значениями из отрезка [1,2]. Аналитически оценивается вклад каждого объекта генеральной выборки в величину текущего значения гибридной оценки ССУ. Эвристически оценивается направление изменения весов для каждого объекта, которое привело бы к максимальному уменьшению гибридной оценки ССУ, если бы веса всех остальных объектов были бы фиксированы. Используя величину вклада объекта в гибридную оценку ССУ в качестве модуля вектора изменения и рассчитанное направление изменения, проводится итеративный пересчет весов. Процедура останавливается, когда не удается улучшить гибридную оценку ССУ больше, чем заданное число итераций подряд.

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

Результаты экспериментов показали, что монотонный бустинг, построенный с помощью третьего подхода, превосходит по качеству как алгоритмы, построенные с помощью первых двух подходов, так и алгоритм бустинга А<1аВоо51. Он

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

20

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1) Гуз И. С. Гибридные оценки полного скользящего контроля для монотонных классификаторов. // Докл. всеросс. конф. Математические методы распознавания образов-15. — М.: МАКС Пресс, 2011. — С. 98-103.

2) Гуз И. С. Минимизация эмпирического риска при построении монотонных композиций классификаторов // Труды МФТИ -2011,- Т.З, №3 (11) - С. 115121.

3) Гуз И. С. Конструктивные оценки полного скользящего контроля для пороговой классификации II Математическая биология и биоинформатика. — Т.6. — В.2. —2011. —http://www.matbio.org/2011/Guz2011(6_173).pdf

4) Гуз И.С. Исследование обобщающей способности семейства монотонных функций // Моделирование и обработка информации: Сб.ст./Моск.физ.-тех. ин-т. -М„ 2008.-С. 114-120.

5) Гуз И. С. Обобщающая способность монотонных композиций классификаторов // Докл. межд. конф. Интеллектуализация обработки информации, ИОИ-7, — Симферополь. 2008, — С. 75-77.

6) Гуз И. С. Нелинейные монотонные композиции классификаторов // Докл. всеросс. конф. Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 111-114.

7) Гуз И. С. Алгоритмические композиции с монотонными и выпуклыми корректирующими операциями //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLV научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2006. - С. 282-283.

ГУЗ Иван Сергеевич

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

Автореферат

Подписано в печать 31.10.2011 г. Формат 60x90 1/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 524. Отпечатано в типографии «Реглет» 119526, г. Москва, Страстной бульвар, д.6,стр. 1 (495) 978-43-34; www.reglet.ru

Введение.

Глава 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 Экспериментальная оценка качества метода минимизации гибридной оценки ССУ.

Проблема синтеза алгоритмов на основе обучения по конечным выборкам прецедентов и изучения их качества на всем множестве прецедентов является одним из важнейших вопросов теории обучения по прецедентам. В качестве прецедентов рассматриваются пары: объект, описанный набором признаков, и класс, к которому принадлежит объект. Задача классификации, являющаяся подклассом более общего класса задач обучения по прецедентам, состоит в том, чтобы на основании известного конечного множества прецедентов научиться определять априори неизвестную принадлежность объектов к классам. Обучение или настройка параметров алгоритма на обучающей выборке происходит путем решения задачи численной оптимизации. Практика показала, что при решении прикладных задач классификации очень часто возникает ситуация, когда ни один из существующих алгоритмов в отдельности не решает задачу с достаточным качеством. В таких случаях, согласно алгебраическому подходу [18, 19, 20] к проблеме распознавания, развиваемого школой академика РАН* Ю.И. Журавлева, пытаются учесть сильные стороны каждого отдельного алгоритма за счет построения из них некоторой композиции.

В работе рассматривается проблема повышения качества классификации при помощи построения алгоритмических композиций для задач, описываемых некоторой выборкой объектов, где каждый объект принадлежит одному из двух непересекающихся классов, -1 и +1. Подобные задачи встречаются на практике очень часто и носят название задач бинарной классификации. Задачи, в которых объект описывается большим числом классов, могут быть сведены к последовательному решению нескольких задач бинарной классификации. Предполагается, что существует набор базовых алгоритмов, причем каждый базовый алгоритм определяет для каждого объекта не только его класс, но и оценку принадлежности классу +1. Этим свойством обладают многие известные алгоритмы классификации, например, байесовские классификаторы [30], нейронные сети [X], логистическая регрессия [25], деревья решений [27] и другие. В байесовских классификаторах оценка принадлежности интерпретируется как апостериорная вероятность того, что объект принадлежит классу +1. Однако в данной работе никаких предположений о вероятностной природе данных не делается, и оценки принадлежности интерпретируются в более широком смысле. Чем больше оценка, тем с большей уверенностью можно утверждать, что объект принадлежит классу +1.

В качестве алгоритмической композиции в работе рассматривается монотонная корректирующая операция [22], которая является монотонным классификатором в пространстве оценок принадлежности. Использование монотонного классификатора оправдано естественным требованием, что если для одного объекта оценки принадлежности не меньше, чем для другого, то и оценка принадлежности первого объекта, рассчитанная с помощью композиции, должна быть не меньше, чем для второго. Монотонные корректирующие операции образуют более широкое семейство по сравнению с выпуклыми (линейными с неотрицательными коэффициентами), используемыми в методах голосования, в частности, в бустинге. Это позволяет точнее настраиваться на данные и использовать существенно меньшее число базовых алгоритмов, но одновременно с этим, повышает риск переобучения.

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

В диссертации, развивается теория надёжности обучения по прецедентам К.В. Воронцова: доказывается возможность построения качественных алгоритмических композиций без каких-либо априорных предположений о вероятностной природе распределения объектов обучения.

Работа состоит из трех глав.

В первой главе формализуется задача обучения по прецедентам, и описываются прикладные области применения монотонных алгоритмов классификации, называемых в работе монотонными классификаторами. Описывается алгебраический подход к решению задач бинарной классификации с помощью построения монотонных корректирующих операций над базовыми алгоритмами. Вводится понятие метода обучения на объектах с весами. Формализуется понятие риска переобучения с помощью определения функционала полного скользящего контроля (complete cross-validation, CCV).

Вторая глава состоит из двух частей.

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

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

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

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

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

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

Для уменьшения риска переобучения описывается второй подход, основанный на минимизации комбинаторной оценки ССУ, доказанной в работе К. В. Воронцова [10], при последовательном добавлении базовых алгоритмов в композицию. Недостатком этого подхода является относительно низкое качество классификации построенной с его помощью монотонной композиции.

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

Метод минимизации гибридной оценки ССУ основан на принципах метода градиентного спуска, реализованных для дискретного случая. Изначально вся матрица весов объектов инициализируются произвольными значениями из отрезка [1,2]. Аналитически оценивается вклад каждого объекта генеральной выборки в величину текущего значения гибридной оценки ССУ. Эвристически оценивается направление изменения весов для каждого объекта, которое привело бы к максимальному уменьшению гибридной оценки ССУ, если бы веса всех остальных объектов были бы фиксированы. Используя величину вклада объекта в гибридную оценку ССУ в качестве модуля вектора изменения и рассчитанное направление изменения, проводится итеративный пересчет весов. Процедура останавливается, когда не удается улучшить гибридную оценку ССУ больше, чем заданное число итераций подряд.

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

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

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

Заключение

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

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

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

Таким образом, основные результаты диссертационной работы следующие:

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

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

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

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

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

2. Воронцов К. В. Комбинаторные обоснования обучаемых алгоритмов. ЖВМ и МФ. 2004. Т. 44, № 11. С. 2099-2112.

3. Воронцов К. В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания. ЖВМ и МФ. 2000. Т. 40 № 1. С. 166-176

4. Воронцов К.В. Качество восстановления зависимостей по эмпирическим данным // Математические методы распознавания образов—VII: Тез. докл. М. 1995.

5. Воронцов К.В. О проблемно-ориентированной оптимизации базисов задач распознавания // ЖВМ и МФ. 1998. Т. 38, № 5. С. 870-880.

6. Воронцов К.В. О синтезе проблемно-ориентированных базисов в задачах распознавания // Математические методы распознавания образов-УШ: Тез. докл. М. 1997. ' 4

7. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания //ЖВМ и МФ.

8. Воронцов К. В. Комбинаторная теория надёжности обучения по прецедентам — Диссертация на соискание ученой степени д.ф.-м.н., М.: ВЦ РАН — 2010.

9. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики. — 2004. —N0. 13. — С. 5— 36.

10. Воронцов К. В. Локальные базисы в алгебраическом подходе к проблеме распознавания — Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН— 1999.

11. Гуз И. С. Гибридные оценки полного скользящего контроля для монотонных классификаторов. // Докл. всеросс. конф. Математические методы распознавания образов-15. — М.: МАКС Пресс, 2011. — С. 98-103.

12. Гуз И. С. Конструктивные оценки полного скользящего контроля для пороговой классификации // Математическая биология и биоинформатика. — Т.6. — В.2. —2011. http://www.matbio.org/2011/Guz2011(6173).pdf

13. Гуз И. С. Минимизация эмпирического риска при построении монотонных композиций классификаторов // Труды МФТИ -2011.- Т.З, №3 (11) С. 115121.

14. Гуз И. С. Нелинейные монотонные композиции классификаторов // Докл. всеросс. конф. Математические методы распознавания образов-13. — М:: МАКС Пресс, 2007. — С. 111-114.

15. Гуз И. С. Обобщающая способность монотонных композиций классификаторов // Докл. межд. конф. Интеллектуализация обработки информации, ИОИ-7, — Симферополь. 2008, — С. 75-77.

16. Гуз И.С. Исследование обобщающей способности семейства монотонных функций // Моделирование и обработка информации: Сб.ст./Моск.физ.-тех. ин-т. М., 2008. - С. 114-120.

17. Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации*// Проблемы кибернетики. — 1978. — Т. 33. — С. 5-68.

18. Журавлёв Ю.И., Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. М. Наука. 1987. С. 187-198.

19. Журавлёв Ю. И. Корректные алгебры над множеством некорректных (эвристических) алгоритмов. I-III // Кибернетика. 1977. №4 С. 14-21. 1997 №6 . С. 21-27. 1978. №2 С. 35-43.

20. Махина Г. А. Оценка обобщающей способности для монотонных алгоритмов классификации // 16-я международная конференция. Проблемы теоретической кибернетики. Нижний Новгород, 20-25 июня 2011

21. Рудаков К.В. Монотонные и унимодальные корректирующие операции для алгоритмов распознавания // Математические методы распознавания обра-зов-VII: Тез. докл. М. 1995.

22. Рудаков К.В., Воронцов К.В. О методах оптимизации и монотонной коррекции в алгебраическом» подходе к проблеме распознавания. Доклады РАН. 1999. Т. 367, №3. С. 314-317.

23. Рудаков К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания. — Диссертация на соискание учёной степени д.ф.-м.н., М.: ВЦ РАН. — 1992.

24. Agresti A. Building and applying logistic regression models. An Introduction to Categorical Data Analysis. Hoboken, New Jersey: Wiley, p. 138.

25. Blake C., Merz C. UCI repository of machine learning Department of Information and Computer Science, University CA, 1998. http://www.ics.uci.edu/~mlearn/MLRepository.html.

26. Breiman L.; Friedman J.H., Olshen R.A., Stone C.J. Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. 1984

27. Cortes C., Vapnik V. Support-Vector Networks, Machine Learning, 20, 1995.

28. Cover T.M., Hart P.E. Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13 (1): 21-27.

29. Domingos, Pedro & Michael Pazzani (1997) «On the optimality of the simple Bayesian classifier under zero-one loss». Machine Learning, 29:103-137.

30. Fine T.L. Feedforward Neural Network Methodology, 3rd ed. New York: Springer-Verlag. 1999.

31. Hastie T., Tibshirani R., Friedman J. The elements of statistical learning. — Springer-Verlag, 2001.

32. Hopcroft J.E., Karp R.M. An n5/2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing 2 (4): 225-231

33. Kass G.V. An Exploratory Technique for Investigating Large Quantities of Categorical Data. Applied Statistics, Vol. 29, No. 2, 1980, pp. 119-127.i

34. König D. Gräfok es mätrixok. Matematikai es Fizikai Lapok 38: 116-119.

35. Loh W.-Y., Shih Y.-S. Split selection-methods for classification trees, Statistica Sinica, vol. 7, 815-840, 1997

36. Marina Velikova. Monotone Prediction Models in Data Mining. VDM Verlag Dr. Müller, 2008

37. Mullin M., Sukthankar R. Complete cross-validation for nearest neighbor classifiers // Proceedings of International Conference on Machine Learning. 2000. http://citeseer.ist.psu.edu/309025.html.

38. Quinlan R. 2011, http://rulequest.com/see5-win.html

39. Vapnik V. The nature of statistical learning theory. — 2 edition. — SpringerVerlag, New York, 2000.