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

БОТОВ ПАВЕЛ ВАЛЕНТИНОВИЧ

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

05.13.17 — теоретические основы информатики

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

- 0 ДЕК 2011

Москва, 2011

005004971

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

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

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

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

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

Матросов Виктор Леонидович

кандидат физико-математических наук, Докукин Александр Александрович

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

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

Защита диссертации состоится «22» декабря 2011 г. в ^ на заседании диссертационного совета Д002.017.02 в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

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

Автореферат разослан « _» ноября 2011 г.

Учёный секретарь диссертационного совета Д 002.017.02, д.ф.-м.п., профессор /Ц]

В. В. Рязанов

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод послойного разложения семейства (глава 2) может быть применён для получения оценок вероятности переобучения в более широком классе семейств.

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

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

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

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

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

• Результаты работы неоднократно докладывались на семинарах отдела Интеллектуальных систем ВЦ РАН.

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

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

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

Глава 1. Комбинаторная теория переобучения

1.1. Основные понятия и обозначения. Пусть задано множество объектов X = {хь ... ,xi}, называемое генеральной выборкой, конечное семейство алгоритмов А и бинарная функция ошибки /: А х X {0,1}. Если 1(а,х) = 1, то говорят, что алгоритм а ошибается на объекте х. Вектором ошибок алгоритма о называется бинарный вектор (I(a, Xi))^=v Число ошибок алгоритма а

на выборке X С X есть п(а,Х) = ]Г) 1{а,х). Частота ошибок

хех

алгоритма а на выборке X С X есть и(а, X) = п(а, Х)/\Х\.

Методом обучения называется отображение р: 2х Л, которое произвольной обучающей выборке X С X ставит в соответствие некоторый алгоритм. Частоту ошибок u(ßX,X) называют эмпирическим риском. Метод, обучения //, называется минимизацией эмпирического риска (МЭР), если \iX 6 А{Х) = Arg min п(а, X)

аВЛ

для любой обучающей выборки X. Метод МЭР называется пессимистичным, если иХ Е Arg max п(а,Х).

аеЛ(Х)

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

Допустим, что все разбиений генеральной выборки X = ХйХ на наблюдаемую обучающую выборку X длины I и скрытую контрольную X длины к = L - £ равновероятны. Вероятностью переобучения метода /л иа выборке X называется величина

L х

Здесь и далее означает суммирование по всем ¿-элементным

подмножествам X С X генеральной выборки; логическое выражение в квадратных скобках означает: [истина] = 1 и [ложь] — 0.

Если множество А — {а} одноэлементно, то точное значение Qe задаётся функцией гипергеометрического распределения:

Q£ = Him(sm(e)), где H^(z) = £

s=so L

sm(e) = |(m - ek), s0 = max{0, m - к}, [z\ — округление г до ближайшего целого, не большего

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

2.1. Послойный метод. Множество At = {а € А: п{а,X) = t+v называется t-слоем множества алгоритмов А относительно выборки X, где т — min п(а, X) — число ошибок лучшего алгоритма.

Теорема 1.1. Если А — семейство алгоритмов, ц — метод обучения, векторы ошибок всех алгоритмов а 6 А попарно различны, то для каждого 1,-слоя А,, можно указать такое множество индексов Уь, и для каждого V & У1 такую пару непересекающихся подмножеств Х1г,,Х^, С X и такой коэффициент с1у е К, что

е л,] = с С XI.

Гипотеза 1.1. Множества Х1у и Х[у можно выбрать так, что п(а, Х1у) = 0 и п(а, Х{„) = £ для всех а € Д.

Введём обозначения: ¿^ = I — ЬЬу — Ь — — |Х4'„|.

Теорема 1.2. Пусть верны условия теоремы 1.1, тогда вероятность получить алгоритм из ¿-слоя:

1

Теорема 1.3. Пусть верны условия теоремы 1.1, а также верна

гипотеза 1.1, тогда вероятность переобучения есть «

где суммирование производится по всем слоям алгоритмов, а вклады ¿-слоев в вероятность переобучения определяются как

_ п^

ьеК ь

Обозначим через п* математическое ожидание числа ошибок

к

на генеральной выборке: п* = 2

4=0

2.2. Метод индикаторов. Удобно ввести следующие определения для часто используемых бинарных выражений:

[Ха С X][XS С X] — элементарный индикатор, где Ха и Х^ — пара из порождающего и запрещающего множеств;

[ßX — а] — индикатор алгоритма а;

[(лХ £ At] = [/хХ = а] — индикатор t-слоя.

a&At

Бинарное выражение [Ха С Х][Хг С X] будем называть просто индикатором, если про Ха и Хд не известно, являются ли они парой из запрещающего и порождающего множеств.

Согласно теореме 1.1, индикатор слоя может быть представлен как сумма элементарных индикаторов. Определим вклады элементарного индикатора в вероятность получения алгоритма а (или слоя At) и в вероятность переобучения семейства:

Qt-\Xa\

Р[ха с x\[xs с х] = L4Xc"l~lXsl, QeAxa С Х]\Хв сх} = Ые)).

L

Введём редукцию ß(a,b) как сокращённую запись индикатора [X* С X][XS С X], где а = |Х„|. b = , при условии, что Ха П Xs = 0.

Поскольку вклады зависят не от самих множеств Ха, Xs, а только от их мощностей (а,Ь), удобно ввести обозначения:

Pß(a, Ь) = Р[Ха С X][XS С X] = Qe,tß(a, b) = Qe,t[Xe С X][Xä С X] = Щ±Н1~_Ть Ш) .

Две редукции Р(а,Ь) и /3(с, ¿) будем считать равными, если РР(а,Ь) = РР{с,(1) и дЕ1ф(а,Ь) = С)£,ф(с,(1). Индикаторы этих редукций будем называть эквивалентными.

Некоторые свойства редукций.

1. Свойство суммы: р/3(а, Ь) + д/3(а, Ь) = (р + я)13{а> Ь).

2. Свойство произведения: /3(а, Ь) ■ /3(с, й) = ¡3(а + с,Ь + <1).

ь

3. Упрощение суммы: = Р(с ~ 1)а) ~ Р(с - М + !)•

г=а

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

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

В данной главе вводятся модельные семейства алгоритмов, для них доказываются теоремы о вероятности переобучения и о вероятности Д выбора алгоритма из ¿-слоя, предлагаются эффективные алгоритмы вычисления величин С]Е и 1\. Приводятся результаты численных экспериментов по методу Монте-Карло, показывающие, что величины <3Е и Ри вычисленные по полученным формулам, совпадают с точными значениями.

В данной главе модельные семейств вводятся по единой схеме.

1. Определение модельного семейства, пример бинарной матрицы «алгоритм» х «объект», диаграмма семейства;

2. Лемма о редукции индикатора слоя семейства алгоритмов;

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

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

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

Двухэлементное семейство изучено в работах К. В. Воронцова. В данной работе та же оценка получена методом индикаторов.

Теорема 1.4 (О паре алгоритмов). Пусть А = {яъ^г}, тъ ГП2 и то — число объектов, яа которых, ошибается, соответственно, йь а<2 и оба алгоритма вместе. Пусть ц — пессимистическая минимизация эмпирического риска. Тогда вероятность при обучении выбрать алгоритмы аг и а2 есть

7712 ¿2

¿2=011=0 ¿2=041=12 + 1

гдеР(г 1,г2) = С% !Сь■ Вероятность переобучения се-

мейства есть С}6 = <Эе,01 ГДе вклады каждого из алгоритмов

ГП2 ¿2

Е Р^Н^Х^Н^ + гпг-ке)-^, ¿2=0 ¿1=0 т.2 ГП1

<гад = Е Е + т2 - ке) - г2).

¿2=0 ¿1 =¿2+1

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

3.2. Монотонная и унимодальная цепи

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

3.2.1. Монотонная цепь. Цепью алгоритмов называется семейство алгоритмов, элементы которого можно выстроить в последовательность так, чтобы любые два соседних алгоритма различались только на одном объекте.

Цеггь алгоритмов А — {«о, а.%, а2).... с/,д} называется монотонной цепью высоты Д если п{аа, X) — т + (1 для всех (I = 0,..., I) при некотором т ^ 0. Алгоритм а о называется лучшим в цепи.

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

Теорема 1.5 (О вероятности выбора алгоритма). Пусть А — монотонная цепь высоты Б, //, — пессимистическая минимизация эмпирического риска и выполнено условие О ^ к. Тогда вероятность выбора алгоритмов из слоя f выражается в виде

= где *=[« = £>].

Теорема 1.6 (О вероятности переобучения). Пусть А —монотонная цепь высоты О, ц — пессимистическая минимизация

эмпирического риска и выполнено условие D ^ к. Тогда веро-

D

ятность переобучения семейства есть Qe = Yj Qe,t> БКлаДы слоёв

i=0

Qe,t выражаются в виде

Qejt =

где st(e) = j(m1 - ek) и x=[t = D].

3.2.2. Унимодальная цепь. Цепь А = {а_в,..., а0, • ■ •

называется унимодальной цепью алгоритмов высоты D, если

1. n(ad,X) = m + |d| при некотором m ^ 0; алгоритм а0 называется лучшим в цепи А\

2. если d и d! одного знака и \d\ < (<f то х) ^ /(а^, х) для всех х Е X;

3. если dud! имеют разные знаки, то существует лишь m объектов, на которых ошибаются оба алгоритма.

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

Теорема 1.7 (О вероятности выбора алгоритма). Пусть А — унимодальная цепь высоты D, ц — пессимистичная минимизация эмпирического риска и выполнено условие D ^ к. Тогда вероятность выбора алгоритма из слоя t выражается через

ъ = (Ct-lt2, + 2С&*1ж - 2Ct\U„) ICl где x=[t< D}.

Теорема 1.8 (О вероятности переобучения). Пусть А—унимодальная цепь высоты О, //, — пессимистичная минимизация эмпирического риска, к -—[(, < О], и выполнено условие В < к. Тогда вероятность переобучения семейства есть С}? — где вклады евыражаются через

3.3. Многомерные симметричные модели

Вектором индексов будем называть вектор <1 — ((к)ы\ с целыми компонентами. Положим |(1| = ^¿=1 №1- множестве векторов индексов естественным образом введём частичный порядок: с! < с!' тогда и только тогда, когда (1г ^ (1'г для всех г € 1,... и хотя бы одно из неравенств строгое. Неотрицательным вектором индексов будем называть вектор индексов с1 с с/г ^ О, г € 1,..., /г.

3.3.3. Монотонная сеть. Множество алгоритмов А — {аа}, где вектор индексов с1 с неотрицательными компонентами имеет размерность /г и |с!| ^ £>, называется монотонной к-мерной сетью алгоритмов высоты Б, если выполнены условия:

1. если с! < сГ, то для всех ж 6 X выполнено х) ^ х), причём ровно |с1 — <1'| неравенств строгие;

2. п(аа,Х) — гп + |с1( при некотором т ^ 0 для всех аА е А. Алгоритм «о называется лучшим.

Монотонная сеть является моделью /ьмерного параметрического семейства классификаторов с непрерывной по параметрам дис-

криминантной функцией. Это модельное семейство, обладающее одновременно свойствами расслоения, связности и размерности. Теорема 1.9 (О вероятности выбора алгоритма). Пусть А — ¡¡.-мерная монотонная сеть высоты В, ¡1 — пессимистичная минимизация эмпирического риска и выполнено условие О < к. Тогда вероятность выбора алгоритма из ¿-слоя,

Сш-1

(-¡¿ — К

П-1

Е Ри ¿=0

t<D■, Ь = В.

Теорема 1.10 (О вероятности переобучения). Пусть А — Н-мерная монотонная сеть высоты В, ц — пессимистичная минимизация эмпирического риска и выполнено условие I) ^ к. Тогда

Б

вероятность переобучения семейства есть (¿е = <3<м гДе

{=0

с

яГ

Ые)) ~ Е Он

¿=0

* < £>; В.

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

3.3.4. Связка цепей.

Определение 1.1. Множество {аьЛ: Ь = 1,..., к, с? = 0,..., В} называется связкой Н монотонных цепей высоты В, если

1. существует алгоритм а* е А, называемый лучшим в связке, такой, что а* = а'', для всех Ь;

2. X) = т + (I при некотором пг ^ 0, любом Ь £ {I,.... /1} и любом (1 ^ /3;

3. есля > (/, то 1(а^,х) > 1(а#,х), причём ровно в! — с? неравенств строгие;

4. если 1(аьа,х) = 1(а%,,х) — \,Ьф Ь', для некоторого объекта х, то 1(а*,х) = 1.

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

3.3.5. Унимодальная сеть. Множество алгоритмов А — {яа}; где вектор индексов (1 имеет размерность !г и |с1| называ-

ется унимодальной 1г-мерной сетью алгоритмов высоты если выполнены условия:

1. если 0 < с! < с!' или с1' < (1 ^ 0, то для всех х € X выполнено 1(аС1,х) ^ 1(а#,х), причём ровно \(1 — <1'\ неравенств строгие.

2. п(а,-], X) = т -(-- |с!| при некотором то ^ 0 для всех ад € А. Алгоритм а0 называется лучшим.

Унимодальная сеть отличается от монотонной снятием ограничения на неотрицательность компонент вектора индексов <1. Она является более адекватной моделью /?,-параметрического семейства классификаторов, поскольку допускает отклонения от лучшего алгоритма в обе стороны по каждому из параметров.

3.3.6. О некоторых свойствах многомерных семейств.

Если доя семейств алгоритмов А и А' при фиксированных Ь, £, е выполнены неравенства п*(А) ^ п*(А') и (¿е{А) ^ Яе{А!), то будем говорить, что семейство А' мажорирует А и записывать А -< А'.

Теорема 1.11 (О мажорируемости). Унимодальная сеть размерности к мажорирует связку цепей размерности 2/г и мажорируется монотонной сеть размерности 2Н:

(связка цепей) 2П -< (унимодальная сеть)п -< (монотонная сеть)2к.

Каждое из этих семейств мажорируется семействами большей размерности /г или большей высоты И.

3.4. Несимметричные модели

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

3.4.1. Монотонная несимметричная сеть. Множество алгоритмов А = {аа: 0 ^ с! ^ Б, |(1| < Д)}, проиндексированное вектором высот Б и общей высотой Д), называется монотонной несимметричной Н-мерпой сетью алгоритмов, если

1. из с1 < (1' следует 1(а<1,х) < 1(а&,х) для всех х е X, причём ровно \(1 — (1'\ неравенств строгие;

2. п(аа,Х) = гп + |<1| при некотором т ^ О для всех аА е А. Алгоритм ао называется лучшим.

3.4.2. Несимметричная связка цепей. Множество алгоритмов А = {а^: Ь = 1,..., к, й — 0,..., А,}, называется несимметричной связкой К монотонных цепей высот Д...., Дп если

1. существует алгоритм а* Е А, называемый лучшим в связке, такой, что а* — а'(\ для всех 6;

2. п{аъЛ, X) = то + (1 при некотором тп > 0, любом Ь € {1,..., И} и любом й ^ Д;

3. подмножество Аь — : (1 — 0,..., Д) является монотонной цепыо для всех Ь £ {1,..., /г.};

4. если /(¿4,х) = 1(аь^,х) = 1,6^ 6', для некоторого объекта х то1(а*,х) = 1.

3.4.3. Унимодальная несимметричная сеть. Множество Л — : —"\У~ ^ ^ |\\г| ^ И-'о}, задаваемое двумя векторами высот — ^ 0 ^ и общей высотой \>У0, называется унимодальной несимметричной Ь-мерной сетью алгоритмов (УНС), если выполнены условия:

1. если 0 ^ < или < ^ 0, то для всех х € X выполнено 1(а^,х) ^ х), причём ровно ¡го — го'| неравенств строгие.

2. п(ате,Х) = т + (лу| при некотором т ^ О для всех а„ £ А. Алгоритм ао называется лучшим.

3.4.4. О некоторых свойствах несимметричных многомерных семейств. Унимодальная несимметричная сеть является несимметричным обобщением ранее рассмотренной унимодальной

(симметричной) сети, которая, в свою очередь, является многомерным обобщением унимодальной цепи. С другой стороны, при W- = О У НС вырождается в несимметричную монотонную сеть.

УНС с векторами высот W* мажорирует и мажорируется симметричными унимодальными сетями с высотами, соответственно

D_ = minmin(W.", Wf) и D+- maxmax(W~, Wf). j i

УНС с векторами высот W* мажорируется УНС с векторами высот W*', о которых известно, что W*' > W*. Теорема 1.12 (О мажорируемости). Несимметричная унимодальная сеть размерности h с векторами высот w± = (wj)^! мажорирует несимметричную связку цепей размерности 2h с высотами Wf, Wi ,..., Whl Wfl и мажорируется несимметричной монотонной сетью размерности 2h с высотами (W^, W*,..., И7,", W,f) и общей для всех семейств главной высотой \¥0: (связка цепей)2h -< (унимодальная ссть)к -< (монотонная сеTb)2h.

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

4.1. Аппроксимация семейств. Показано, что зависимости вероятности переобучения Qe от е для четырёх стандартных семейств классификаторов (наивный байесовский, SVM, решающее дерево, нейронная сеть), порождаемые на реальных данных (5 реальных задачах из репозитория UCI), хорошо аппроксимируются зависимостями Qf: от е многомерных модельных семейств при подборе параметра размерности h. В частности, для задачи breast- cancer-Wisconsin наилучшая аппроксимация получена для монотонной цепи, что согласуется с априорной информацией, что в данной задаче информативен только один признак.

Предложен эвристический метод подбора параметров т, к, с целью получения унимодальной несимметричной сети, вероятности Pf и которой могут быть использованы для аппроксимации вероятностей и С)£ реального семейства, порождаемого заданной выборкой (УНС-аппроксимация).

Эксперименты на реальных данных показали, что при УНС-ап-проксимации оценка п* —т завышается на 5-10% для одномерных семейств, на 10-30% для двумерных и до 50% для трёхмерных. Более чем в половине случаев одномерные семейства аппроки-мируются без ошибок, поскольку окрестность лучшего алгоритма радиуса б оказывается унимодальной цепью.

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

В экспериментах функционал п* вычислялся двумя способами: эмпирически методом Монте-Карло и с помощью УНС-аппроксимации. Эксперименты на реальных задачах из репози-

тория UCI показали, что метод МПР увеличивает обобщающую способность решающих деревьев, по сравнению с методом МЭР. Улучшение наблюдалось при использовании как метода Монте-Карло, так и УНС-аппроксимации. Однако вычисление УНС-аппроксимации на порядки быстрее.

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

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

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

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

3. Botox1 Р. V. Exact estimates of the probability of overfitting for multidimensional modeling families of algorithms // ISSN 10546618, Pattern Recognition and Image Analysis, 2010, Vol. 20, No. 4, pp. 52-65. - Pleiades Publishing, Ltd., 2010.

4. Ботов П. В. Уменьшение вероятности переобучения итерационных методов статистического обучения // Докл. всеросс. конф. Математические методы распознавания образов-15. — М.: МАКС Пресс, 2011,- С. 44-47.

Подписано в печать:

18.11.2011

Заказ № 6302 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www. autoreferat. ru

Введение

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

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

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

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

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

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

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

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

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

3.2 Монотонная и унимодальная цепи.

3.2.1 Монотонная цепь

3.2.2 Унимодальная цепь.

3.3 Многомерные симметричные модели.

3.3.1 Единичная окрестность.

3.3.2 Единичный гиперкуб.

3.3.3 Монотонная сеть.

3.3.4 Связка цепей.

3.3.5 Унимодальная сеть.

3.3.6 Мажорируемость многомерных семейств.

3.4 Несимметричные модели.

3.4.1 Монотонная несимметричная сеть.

3.4.2 Несимметричная связка цепей.

3.4.3 Унимодальная несимметричная сеть.

3.4.4 Мажорируемость многомерных семейств.

4 Применение модельных семейств алгоритмов в эксперименте

4.1 Аппроксимация семейств.

4.1.1 Аппроксимация унимодальной сети монотонной сетью удвоенной размерности.

4.1.2 Отбрасывание старших слоев семейства.

4.1.3 Сопоставление графиков <2е полученных в эксперименте с графиками <3£ от монотонных сетей.

4.1.4 Аппроксимация семейств, получаемых на практике, унимодальной несимметричной сетью.

4.1.5 Использование метода Монте-Карло для оценки вероятности переобучения семейств.

4.2 Метод минимизации предсказанного риска.

4.2.1 Бинарное решающее дерево

4.2.2 Эксперимент на реальных данных.

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

Актуальность темы. Проблема переобучения является одной из важнейших при решении задач восстановления зависимостей по эмпирическим данным. [24] Она заключается в том, что частота ошибок на независимой контрольной выборке как правило, оказывается несколько выше частоты ошибок на обучающей выборке. Получением количественных оценок обобщающей способности, то есть вероятностного распределения величины этого смещения, занимается статистическая теория обучения. Многие подходы, разработанные в рамках этой теории, дают сильно завышенные оценки переобучения, поэтому их практическое применение не всегда приводит к улучшению качества восстановления зависимости. В комбинаторной теории надёжности обучения по прецедентам, предложенной К.В.Воронцовым [7, 8, 9, 10], показано, что для получения точных оценок необходимо* совместно учитывать свойства расслоения и связности семейства алгоритмов. Под расслоением семейства имеется в виду распределение алгоритмов по частоте ошибок, порождаемое заданной выборкой. Связность предполагает, что для каждого алгоритма в семействе найдётся множество похожих алгоритмов, отличающихся от него только на одном объекте выборки. Семейства, не обладающие свойствами расслоения и связности, могут переобучаться настолько сильно, что их практическое применение становится нецелесообразным.

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

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

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

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

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

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

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

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

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

Метод послойного разложения семейства (глава 2) может быть применён для получения оценок вероятности переобучения в более широком классе семейств.

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

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

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

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

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

• Результаты работы неоднократно докладывались на семинарах отдела Интеллектуальных систем ВЦ РАН.

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

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

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

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

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

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

Благодарности Автор выражает глубокую признательность научному руководителю д. ф.-м. н. Константину Вячеславовичу Воронцову за постановку задачи и постоянную поддержку в ходе исследований. А также Александру Фрею и Андрею Ивахненко за плодотворные дискуссии.

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

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

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

3. Предложен метод аппроксимации оценок вероятности переобучения реальных семейств точными оценками вероятности переобучения модельных семейств;

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

Заключение

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

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

3. Botov P. V. Exact estimates of the probability of overfitting for multidimensional modeling families of algorithms // ISSN 1054-6618, Pattern Recognition and Image Analysis, 2010, Vol. 20, No. 4, pp. 52-65. — Pleiades Publishing, Ltd., 2010.

4. Ботов П. В. Уменьшение вероятности переобучения итерационных методов статистического обучения // Докл. всеросс. конф. Математические методы распознавания образов-15. — М.: МАКС Пресс, 2011.— С. 44-47.

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

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

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

8. Graham R. L., Knuth D. E., Patashnik 0. Concrete Mathematics: A Foundation for Computer Science // ISBN 0-201-55802-5, Massachusetts: Addison-Wesley-Professional, 1994.

9. Asuncion A., Newman D.J. UCI Machine Learning Repository // University of California, Irvine, School of Information and Computer Sciences, 2007.

10. Дьяконов А. Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования) // М.: МАКС Пресс, 2010.

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

12. Breslow L. A., Aha D. W. Simplifying decision trees: a survey // Knowledge Engineering Review.—1997.—Vol. 12, no. 1,—Pp. 1-40.

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

14. Ивахненко А. А. Комбинаторные оценки вероятности переобучения и их применение в логических алгоритмах классификации // Диссертация на соискание учёной степени к.ф.-м.н., — 2010

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

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

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

18. Prey A. I. Accurate estimates of the generalization ability for symmetric sets of predictors and randomized learning algorithms // Pattern Recognition and Image Analysis.-2010,— Vol. 20, No. 3. — Pp. 241-250.

19. Фрей А. И. Точные оценки вероятности переобучения для симметричных семейств алгоритмов // Докл. всеросс. конф. Математические методы распознавания образов-14. — М.: МАКС Пресс, 2009. — С. 66-69.

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

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

22. Ваппик В. Н. Восстановление зависимостей по эмпирическим данным. // М.: Наука, 1979.

23. Хайкин С. Нейронные сети. Полный курс. // 2-е изд., испр.: Пер. с англ.— М.: ООО «И. Д. Вильяме», 2006. —1104 с.

24. Jackson J., Shamir Е., Shwartzman С. Learning with queries corrupted by classification noise // Discrete Applied Mathematics.—1999.— Vol. 92, no. 2-3.— Pp. 157-175.

25. Kearns M. Efficient noise-tolerant learning from statistical queries // Proceedings of the 25-th annual ACM symposium on Theory of computing, May 16-18, 1993, San Diego, California, United States —ACM, 1993.—Pp. 392-401.

26. Kearns M. Efficient noise-tolerant learning from statistical queries // Journal of the ACM.-1998.—Vol. 45, no. 6.—Pp. 983-1006.

27. Jackson J. On the efficiency of noise-tolerant рас algorithms derived from statistical queries // Annals of Mathematics and Artificial Intelligence. — 2003.— Vol. 39, no. 3.-Pp. 291-313.

28. Langford J. Quantitatively Tight Sample Complexity Bounds: Ph.D. thesis / Carnegie Mellon Thesis — 2002.

29. Langford J. Tutorial on practical prediction theory for classification // // Journal of Machine Learning Research —2005—Vol. 6—Pp. 273-306.

30. Langford J., Blum A. Microchoice bounds and self bounding learning algorithms // Computational Learing Theory—1999—Pp. 209-214.

31. Shawe-Taylor J., Bartlett P. L. Structural risk minimization over data-dependent hierarchies // IEEE Trans, on Information Theory —1998—Vol. 44, no. 5.—Pp. 1926-1940.

32. Herbrich R., C.Williamson R. Algorithmic luckiness // Journal of Machine Learning Research—2002 —no. 3—Pp. 175-212.

33. Philips P. Data-Dependent Analysis of Learning Algorithms: Ph.D. thesis / The Australian National University, Canberra.— 2005.

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

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

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

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

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

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

40. Wai-Ho Au, Keith С. С. Chan, Xin Yao A novel evolutionary data mining algorithm with applications to churn prediction // IEEE Trans. Evolutionary Computation—Vol.7—no. 6—2003,—Pp. 532-545.