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

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

ПяЛ

ФРЕЙ АЛЕКСАНДР ИЛЬИЧ

ТЕОРЕТИКО-ГРУППОВОИ ПОДХОД В КОМБИНАТОРНОЙ ТЕОРИИ ПЕРЕОБУЧЕНИЯ

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

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

2 Я НОЯ 2013

005540184

Москва — 2013

005540184

Работа выполнена на кафедре «Интеллектуальные системы» факультета управления и прикладной математики Федерального государственного образовательного учреждения высшего профессионального образования «Московский физико-технический институт (государственный университет)».

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

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

доктор физико-математических наук, Хачай Михаил Юрьевич, Федеральное государственное бюджетное учреждение науки Институт математики и механики им. Н. Н. Красовского Уральского отделения Российской академии наук, зав. отделом математического программирования;

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

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. А. А. Харкевича Российской академии наук.

Защита диссертации состоится 19 декабря 2013 г. в 14:30 на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении «Вычислительный центр им. А. А. Дородницына Российской академии наук», расположенном по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

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

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

Д 002.017.02, д.ф.-м.н., профессор Рязанов В.В.

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

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

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

Степень разработанности темы. Основы статистической теории обучения были заложены в работах В. Н. Вапника и А. Я. Червоненкиса в конце 60-х годов. Ими была доказана состоятельность обучения по прецедентам и получены количественные оценки, связывающие обобщающую способность метода обучения с длиной обучающей выборки и сложностью семейства алгоритмов. Основной проблемой этих оценок является их завы-шенность. Для устранения завышенности предлагалось строить оценки, зависящие от выборки (D. Haussier, 1992); учитывать ширину зазора, разделяющего классы (P. Bartlett, 1998); строить оценки на основе локальной радемахеровской сложности семейства алгоритмов (V. Koltchinskii, 1998); учитывать априорные распределения на множестве алгоритмов (L. Valiant, 1982; D. McAllester, 1999; J. Langford, 2005); а также ряд других подходов.

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

мействах алгоритмов (К. В. Воронцов, 2010). Была получена оценка расслоения-связности, справедливая для широкого класса семейств, представимых в виде связного графа (К. В. Воронцов, А. А. Ивахненко, И. М. Решетняк, 2010). Для некоторых модельных частных случаев было показано, что этого достаточно для получения неулучшаемых (точных) оценок. Таким образом, комбинаторная теория переобучения является новым перспективным подходом. Данная работа направлена на ее дальнейшее развитие: расширение границ применимости, разработку новых методов вывода оценок обобщающей способности и повышение точности этих оценок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Международная конференция «25th European Conference on Operational Research», 2012 r.

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

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

Публикации по теме диссертации в изданиях из списка ВАК РФ — одна [7]. Другие публикации по теме диссертации: [1, 2, 3, 4, 5, 8, 6].

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

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

Глава 1. Теория статистического обучения

Глава содержит краткий обзор современного состояния теории статистического обучения (statistical learning theory). Обсуждается проблема завышенное™ классических оценок переобучения, приводятся мотивации перехода от классических теоретико-вероятностных постановок задач к комбинаторным.

Глава 2. Комбинаторный подход

2.1. Основные определения. Пусть задана конечная генеральная выборка X = {х\,...,xl}, состоящая из L объектов. Пусть А — некоторое множество алгоритмов. Каждый алгоритм классификации а £ А, примененный к выборке X, порождает бинарный вектор ошибок а = (/(a, Xi))i=i, где I(a,Xi) € {0,1} — индикатор ошибки алгоритма о на объекте Х{. Для произвольной подвыборки X с X обозначим через п(а, X) = ^ 1(а, х)

х&Х

число ошибок, а через и(а,Х) — п(а, Х)/\Х\ — частоту ошибок алгоритма а на выборке X.

Методом обучения называют отображение вида р: 2х —/1. Результатом обучения по выборке X С X называется алгоритм а = ß(X), обозначаемый также а = ßX или а = ß(A,X).

Метод обучения ß называется минимизацией эмпирического риска (МЭР), если

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

абЛ

и методом пессимистической минимизации эмпирического риска (ПМЭР), если

иХ е Arg max п(а,Х).

абЛ(Х)

Обозначим через [Х]^ множество всех разбиений генеральной выборки X на обучающую выборку X длины I и контрольную выборку X длины k — L — t. Если для выборки X 6 [Х]£ уклонение частот ö(a,X) = и(а,Х) — и(а,Х) превосходит фиксированный порог е > 0, то говорят, что алгоритм а — ßX является переобученным. Нашей целью является получение оценок вероятности переобучения:

Qe{ß, X) = Р [5{ßX, v(£), где Р = ^ £ , (2.1)

L хе[х]<

где квадратные скобки означают [истина] = 1, [ложь] = 0.

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

2.2. Расслоение и связность. Определим естественное отношение порядка на алгоритмах: а ^ Ь тогда и только тогда, когда 1(а, х) ^ 1(Ь, х) для всех х Е X. Определим метрику на алгоритмах как хэммингово расстояние между их векторами ошибок:

ь

р(а,Ь) = 1Аа!х) ~ сс)|. Определим отношение предшество-

г=1

вания а -< Ь если а < Ь и р(а, Ъ) = 1.

Для каждого а £ А рассмотрим порождающее и запрещающее множества:

Ха = {ж € X | ЗЬ £ А: 1(а,х) < 1(Ь,х), а -< Ь}, Х'а = {х еХ\ЗЬ е А: 1(Ь,х) < 1{а, х), Ъ ^ о}.

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

Теорема 2.1 (Воронцов, Ивахненко, Решетняк, 2010).

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

^ Е ^В"^ Ша,Х)-ек)),

аеА

, И Сг се-г

где II ¿а (я) = ™ Л'™ — функция гипергеометрического распределения.

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

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

Глава 3. Теоретико-групповой подход

3.1. Рандомизированный метод обучения и РМЭР. При

минимизации эмпирического риска может возникать неоднозначность— несколько алгоритмов из А{Х) = Arg min п(а,Х)

а^А

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

Определение 3.1. Путь А = {0,1}L—множество всех бинарных векторов ошибок. Рандомизированный метод обучения произвольному множеству алгоритмов А С А и произвольной обучающей выборке X € [Х]€ ставит в соответствие функцию распределения весов на множестве алгоритмов:

/х:2Ах [Х]^{/:А-> [0,1]}. (3.1)

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

Методы обучения вида /л: 2х —>• А далее будем называть детерминированными.

Рандомизированный метод минимизации эмпирического риска (РМЭР) выбирает произвольный алгоритм из множества случайно и равновероятно:

, , ч [ае А(Х)} 9

Для РМЭР определение вероятности переобучения Qe(A) соответствующим образом модифицируется:

QÁA) = EWXV\ S [S(a,X)>e],rmE = ^r £ . (3.2)

1 ^ >l aGA(X) ¿ Х6[Х](

Также возможна запись Qe{A) = Qe{(i,A), где Q£(a, А) —

аеА

вклад алгоритма а Е А в вероятность переобучения:

3.2. Перестановки объектов. Пусть Sl — {тг: X —> X}— симметрическая группа из L! элементов, действующая на генеральную выборку перестановками объектов. Действие произвольной перестановки ir G Sl на алгоритм a G А определено перестановкой координат вектора ошибок: (тга)(х{) — а(ir~1Xi). Для произвольной выборки X G [Х]£ и множества алгоритмов А

С {0,1} действия ттХ и -кА определены следующим образом: тгХ — {7гх: х G X}, тгА = {ira: а G А}.

Лемма 3.1. Свойства действия произвольной перестановки ir G Sl:

1 ) 1(тга, их) = 1(а, х) для любых a G А и х G X;

2) n(ira, X) = тг(а, X) для любого a G А;

3) n(ira, тгХ) — n(a, X) для любых a G А и X С X;

4) 5(-ка, ттХ) — S(a, X) для любых a G А и X С X;

5) [a G А(Х)} — [ira G {irA)(irX)] для любых а € А и X С. X;

6) |Л(Х)| = \{irA){irX)\ для любых А и X Ç X;

7) р(а, а') — p(ira, -па') для любых a, a' G А.

Для построения функций, инвариантных относительной действия Sl, введем следующую классификацию функций:

• Симметричной функцией первого рода будем называть д: А х [Х]' -> К, такую, что для всех п Е вь выполнено д(а,Х) = д(тга,тгХ);

• Симметричной функцией второго рода будем называть С: 2А х [Х]г —> 2а, такую, что для всех п Е Бь выполнено тгв(А,Х) = в(-кА,-кХ)-

• Симметричной функцией третьего рода будем называть /: 2А х —» К, такую, что для всех тг Е 5ь выполнено

Лемма 3.1 утверждает, что функции п{а,Х) и г/(а,Х) являются симметричными функциями первого рода, а А{Х), как функция А и X, является симметричной функцией второго рода. Теорема 3.2. Пусть д\, д2,..., др — симметричные функции первого рода, /х, /2,..., /р — симметричные функции третьего рода, Р: Мр —> М — произвольная функция многих переменных. Тогда ^(<71, (72, •••, Эр) —вновь симметричная функция первого рода, ^(/ь /2, • • •, /р) —симметричная функция третьего рода.

Теорема 3.3. Пусть д — симметричная функция первого рода, С — симметричная функция второго рода. Тогда

/(А,Х) = \С(А,Х)\и/(А,Х)= ]Г д(а,Х)

аеО(А,Х)

являются симметричными функциями третьего рода.

3.3. Группа симметрии множества алгоритмов.

Определение 3.2. Группой симметрии, Бут(Л) множества алгоритмов А будем называть его стационарную подгруппу:

Зут(Л) = {тг е : тгА = А}.

Пусть далее С? С 8ут(А) — произвольная подгруппа группы 8ут(Л). Для любой перестановки тг £ (?и любого алгоритма

а 6 А алгоритм -па снова лежит в Л. В таких случаях говорят, что группа действует на множестве А.

Орбитой алгоритма а 6 А называется множество алгоритмов (5а = {7га: 7г € С}. Множество А разбивается на непересекающиеся подмножества — орбиты:

А = у и = У шеП(л) шеп(л)

где П(А)— множество всех орбит в А, аи — произвольный представитель орбиты ш.

Лемма 3.4. Алгоритмы из одной орбиты имеют равные вклады в вероятность переобучения:

С,)£(а, А) = <Зе(7га, А) для всех тг 6 б.

Теорема 3.5. Для любой генеральной выборки X, любого множества алгоритмов А с попарно различными векторами ошибок и любого е £ [0,1] справедлива формула разложения вероятности переобучения по орбитам множества А:

де(А) = £ М [6Ы (3.3)

шеп(л) ' ^

где П(Л) —множество всех орбит в А, аш —произвольный представитель орбиты си.

По аналогии с действием группы С? С Зут(А) на множестве алгоритмов рассматривается действие С? на множестве [Х]^ всех разбиений выборки на обучение и контроль.

Теорема 3.6 (Толстихин, Фрей, 2010). В условиях теоремы 3.5 справедлива формула разложения (¿Е(А) по орбитам множества [Х]^:

Яе(А) = -^¡г £ Е (3.4)

£ г£П[Х]« 1 V тЛ аеА(Хт) 12

где —множество всех орбит в [Х]г, Хт—произвольный

представитель орбиты т.

Теоремы 3.5 и З.б являются основным инструментом для вывода оценок вероятности переобучения симметричных семейств алгоритмов. Оценки (3.3) и (3.4) являются точными равенствами и, следовательно, неулучшаемы.

3.4. Покрытия множества алгоритмов.

Лемма 3.7. Пусть множество алгоритмов А представлено в виде разбиения А — А\ и Л 2 и • • • и ^. Тогда для вероятности переобучения детерминированного метода ПМЭР справедлива верхняя оценка

г=1

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

Для вычисления <2£(^4г) предлагается дополнить каждое множество А{ до множества В; Э А; с известной точной оценкой вероятности переобучения и применить неравенство1

Яе(Аг) ^ <2е(Вг),

справедливое для ПМЭР при условии равенства числа ошибок алгоритмов в множестве В¿.

3.5. Теоремы о порождающих и запрещающих множествах.

Метод порождающих и запрещающих множеств (ПЗМ), предложенный К.В.Воронцовым, основан на гипотезе, что для любого

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

алгоритма а € А можно записать необходимое и достаточное условие того, что он будет выбран методом обучения ц по выборке X. В данном параграфе метод ПЗМ обобщается по двум направлениям: во-первых, на случай разложения множества алгоритмов на кластеры, во-вторых, на случай РМЭР.

Гипотеза 3.1. Пусть множество алгоритмов А представлено в виде разбиения на непересекающиеся подмножества А = А\ и А2 и • • • и Пусть выборка X и детерминированный метод обучения рь таковы, что для каждого г = можно

указать пару непересекающихся подмножеств Хг С X и Х[ С X, удовлетворяющую условию

[м(А,Х) € Л] < С Х][Х[ с X) для всех X 6 [Х]£.

Пусть, кроме этого, все алгоритмы а 6 А{ не допускают ошибок на Хг и ошибаются на всех объектах из Х[.

Множество Хг будем называть порождающим, множество Х[ — запрещающим для А¿. Гипотеза 3.1 означает, что результат обучения может принадлежать А, только в том случае, если в обучающей выборке X находятся все порождающие объекты и ни одного запрещающего. Все остальные объекты ¥г = Х\Х^\Х-будем называть нейтральными для А^.

Пусть Ц=Ь- |Хг| - \ХЦ = кг = к - |Хг'|. Обо-

значим через ¥г) вероятность переобучения на множестве

нейтральных объектов Уг:

ОГМиЪ) =Е [тах<5(а,У) > е],

¿г а€ г

где — множество разбиений на обучающую выборку У длины £г и контрольную выборку У длины кг = Ь.1 — 1г.

Теорема 3.8 (ПЗМ для кластеров). Пусть выполнена гипотеза 3.1, а на разбиение А — А\ и Ло и • • • и /Ц наложено дополнительное ограничение: внутри каждого кластера все

алгоритмы допускают равное число ошибок тпг. Тогда

ь

г=1

гпр р. _ пЬ ¡г<е. г. _ и ек , /-, »¡^ш^ где - ег - ^х6 + I1 Т[ 1ЕГ'

Лемма 3.9. Пусть ц — детерминированный ПМЭР. Тогда множества

Хг= р| {х £ X: 36 6 А: а -< Ь,1(а,х) < 7(6,ж)}, х[ = р| {х еХ: 36 € А: Ъ < а, /(6, х) < 1(а,х)}

а&Аг

являются, соответственно, порождающим и запрещающим множествами для кластера А{ в смысле гипотезы 3.1.

Лемма 3.9 позволяет в явном виде построить множество порождающих и запрещающих объектов и применить теорему 3.8 к детерминированному ПМЭР. Аналогичный результат для РМ-ЭР представлен гипотезой 3.2 и теоремой 3.10.

Гипотеза 3.2. Обозначим 21 (А) = {А(Х): X £ [Х]€}. Пусть множество А и выборка X таковы, что для каждого а 6 21 {А) можно указать пару непересекающихся подмножеств Ха с X и Х'а С X, удовлетворяющую условию

[А{Х) = а] = [X С X] [Х'а С X] для всех X £ [Х]€. (3.7)

Теорема 3.10. Если справедлива гипотеза 3.2, то вероятность переобучения рандомизированного метода минимизации эмпирического риска есть

аеЛаеа(Л) ь

15

где введены следующие обозначения:

La = L — \Xa \ — \Xa\; t-a = £ ~~ \Xa\;

maa = n(a, X\Xa\X'ay, saa(e) = £ (n(a, X) - ek) - n{a, Xa).

Глава 4. Точные оценки вероятности переобучения для РМЭР

В данной главе получены точные оценки вероятности переобучения РМЭР для девяти модельных семейств алгоритмов:

• монотонная цепь;

• унимодальная цепь;

• пучок монотонных цепей;

• монотонная сеть;

• унимодальная сеть;

• разреженная монотонная сеть;

• разреженная унимодальная сеть;

• слой хэммингова шара;

• слой интервала булева куба.

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

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

Определение 4.1. Центральным слоем шара радиуса г называют множество алгоритмов, заданное следующим условием:

Вг(ао) — {а £ А: п(а,Х) = п(ао,Х) и р(а,ао) ^ г},

где ао — фиксированный алгоритм, р(а, а')—расстояние Хэм-минга между векторами ошибок алгоритмов а, а'.

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

Определение 4.2. Пусть все объекты генеральной выборки X разделены на три непересекающихся множества: надежно классифицируемые объекты Хо, ошибочно классифицируемые объекты X} и пограничные объекты Хг. Пусть \ХГ\ = г и |Хх| = т, р — целочисленный параметр, р ^ г. Слоем интервала булева куба будем называть множество В™р, удовлетворяющее следующим условиям:

• Щ'^р содержит все алгоритмы, допускающие ровно р ошибок на объектах из Хг,

• ни один алгоритм из В™р не ошибается на объектах из Хо,

• все алгоритмы из В™р ошибаются на всех объектах из Х\.

Теорема 4.1 (Толстихин, 2010). Вероятность переобучения ПМЭР для центрального слоя шара Вг (ао):

Яе{Вг{а0)) = #£т(£(го -еАг) + [г/2]) • [т > ек]. (4.1)

В настоящей работе приводится более простое доказательство Теоремы 4.1.

Теорема 4.2. Вероятность переобучения ПМЭР для слоя интервала булева куба Вггпр:

ЯеФ™р) = ^1 £ Е С1С1С^_г5{1,з)>е , (4.2)

тт(тге,£) тт(г,£—г)

С

ь 1=0

3=0

где <(г, з)=1 + тах(0, р - г - ¿) и ¿(г, 3) = - .

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

В данной главе описываются вычислительные эксперименты на реальных данных из репозитория иС1. В экспериментах сравнивается завышенность уже известных комбинаторных оценок вероятности переобучения и новой оценки (З.б), в которой вероятность переобучения каждого кластера оценивается сверху с помощью (4.2). Показывается, что построенная таким образом оценка в ряде случаев оказывается менее завышенной по сравнению с другими комбинаторными оценками. Кроме того, новая оценка эффективно вычислима для семейств с существенно большим числом алгоритмов, т.к. сумма (3.6) содержит меньшее число слагаемых из-за кластеризации алгоритмов с близкими векторами ошибок.

Заключение

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

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

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

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

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

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

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

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

2. Фрей А. И. Точные оценки вероятности переобучения для симметричных семейств алгоритмов // Труды 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Часть II. Управление и прикладная математика. — М.: МФТИ, 2009. — С. 106-109.

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

4. Фрей А. И. Метод порождающих и запрещающих множеств для рандомизированного метода минимизации эмпирического риска // Всеросс. конф. Математические методы распознавания образов-15. — М.: МАКС Пресс, 2011. — С. 60-63.

5. Фрей А. И., Ивахненко А. А., Решетник И. М. Применение комбинаторных оценок вероятности переобучения в простом голосовании пороговых конъюнкций // Межд. конф. Интеллектуализация обработки информации ИОИ-9. — М.: МАКС Пресс, 2012. - С. 86-89.

6. Фрей А. И., Толстихин И. О. Комбинаторные оценки вероятности переобучения на основе кластеризации и покрытий множества алгоритмов // Machine learning and data analysis. — 2013. - Т. 1(6). - С. 751-767.

7. Frei A. I. Accurate estimates of the generalization ability for symmetric set of predictors and randomized learning algorithms // Pattern Recognition and Image Analysis. — 2010. — V. 20, no. 3. — P. 241-250.

8. Vorontsov K., Frey A. I., Sokolov E. Computable combinatorial overfitting bounds // Machine learning and data analysis. — 2013. — V. 1(6). — P. 724-733.

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

• проведены эксперименты по исследованию обобщающей способности логических алгоритмов классификации [5];

• получена оценка вероятности переобучения, обобщающая оценку метода порождающих и запрещающих множеств на случай произвольного разбиения множества алгоритмов на кластеры [6];

• проведены эксперименты по сравнению комбинаторных и PAC-Bayes оценок переобучения; экспериментально исследованы кривые обучения логистической регрессии [8].

Фрей Александр Ильич

ТЕОРЕТИКО-ГРУППОВОЙ ПОДХОД В КОМБИНАТОРНОЙ ТЕОРИИ ПЕРЕОБУЧЕНИЯ

АВТОРЕФЕРАТ

Подписано в печать: 11.11.2013. Формат 60 х 84 1/гб.

Печать трафаретная. Объем: 1,0 усл. печ. л.

Тираж - 100 экз. Заказ № 339.

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

Отдел оперативной полиграфии «Физтех-полиграф»

141700, Московская обл., г. Долгопрудный, Институтский пер., 9.

Федеральное государственное образовательное учреждение высшего профессионального образования «Московский физико технический институт (государственный университет)»

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

04201 451 91$

УДК 519.22

Фрей Александр Ильич

ТЕОРЕТИКО-ГРУППОВОЙ ПОДХОД В КОМБИНАТОРНОЙ ТЕОРИИ ПЕРЕОБУЧЕНИЯ

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

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

Научный руководитель: д. ф.-м. п. Воронцов Константин Вячеславович

Москва 2013

Оглавление

Введение 4

1 Теория статистического обучения 9

1.1 Основные определения ЭЬТ..........................................................9

1.2 Неравенства концентрации меры ..................................................10

1.3 Теория Вапника-Червоненкиса......................................................12

1.4 Радемахеровский процесс............................................................14

1.5 Неравенство Талаграна..............................................................16

1.6 Локальные оценки избыточного риска ............................................16

1.7 РАС-Вауев оценки....................................................................18

1.8 Основные выводы....................................................................21

2 Комбинаторный подход 22

2.1 Основные определения ..............................................................22

2.2 Расслоение и связность..............................................................26

2.3 Основные выводы и постановка задачи............................................30

3 Теоретико-групповой подход 31

3.1 Рандомизированный метод обучения и РМЭР....................................31

3.2 Перестановки объектов..............................................................33

3.3 Группа симметрии множества алгоритмов........................................37

3.4 Покрытия множества алгоритмов..................................................42

3.5 Теоремы о порождающих и запрещающих множествах (ПЗМ) ................44

3.5.1 ПЗМ для разложения множества алгоритмов на подмножества .... 45

3.5.2 ПЗМ для рандомизированного метода обучения..........................48

3.6 Основные выводы....................................................................51

4 Точные оценки вероятности переобучения для РМЭР 52

4.1 Монотонные и унимодальные цепи ................................................52

4.1.1 Монотонная цепь ............................................................53

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

4.2 Многомерные семейства алгоритмов ..............................................57

4.2.1 Пучок монотонных цепей....................................................57

4.2.2 Многомерная монотонная сеть алгоритмов................................61

4.2.3 Многомерная унимодальная сеть алгоритмов............................65

4.2.4 Разреженные монотонные и унимодальные сети..........................68

4.3 Плотные семейства ..................................................................73

4.3.1 Слой хэммингова шара......................................................73

4.3.2 Слой интервала булева куба................................................74

4.4 Основные выводы....................................................................76

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

5.1 Эффективное вычисление БС-оценки..............................................77

5.2 Применение комбинаторных оценок к логическим алгоритмам................79

5.3 Проблема сэмплирования алгоритмов..............................................85

5.4 Прогноз кривых обучения логистической регрессии..............................88

5.5 Экспериментальное сравнение комбинаторных оценок..........................93

Заключение 96

Список литературы 97

Введение

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

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

Степень разработанности темы. Основы статистической теории обучения были заложены в работах В. Н. Вапника и А. Я. Червоненкиса в конце 60-х годов. Ими была доказана состоятельность обучения по прецедентам и получены количественные оценки, связывающие обобщающую способность метода обучения с длиной обучающей выборки и сложностью семейства алгоритмов. Основной проблемой этих оценок является их завышенность. Для устранения завышенное™ предлагалось строить оценки, зависящие от выборки (D. Haussier, 1992); учитывать ширину зазора, разделяющего классы (P. Bartlett, 1998); строить оценки на основе локальной радемахеровской сложности семейства алгоритмов (V. Koltchinskii, 1998); учитывать априорные распределения на множестве алгоритмов (L. Valiant, 1982; D. McAllester, 1999; J. Langford, 2005); а также ряд других подходов.

Комбинаторная теория переобучения показала, что для повышения точности оценок и сокращения переобучения необходимо одновременно учитывать эффекты расслоения и сходства в семействах алгоритмов (К. В. Воронцов, 2010). Была получена оценка расслоения-связности, справедливая для широкого класса семейств, представимых в виде связного графа (К. В. Воронцов, А. А. Ивахненко, И. М. Решетняк, 2010). Для некоторых модельных частных случаев было показано, что этого достаточно для получения неулуч-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Международная конференция «25th European Conference on Operational Research», 2012 r.

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

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

Публикации по теме диссертации в изданиях из списка ВАК РФ —одна [54]. Другие публикации по теме диссертации: [31, 32, 33, 34, 35, 72, 36].

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

Краткое содержание работы по главам. В главе 1 дается краткий обзор современного состояния теории статистического обучения (statistical learning theory). Обсуждается проблема завышенное™ классических оценок переобучения, приводятся мотивации перехода от классических теоретико-вероятностных постановок задач к комбинаторным.

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

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

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

на множестве алгоритмов или на множестве разбиений выборки, а также теорема о порождающих и запрещающих множеств для РМЭР.

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

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

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

Глава 1. Теория статистического обучения

В данной главе приводится обзор общепринятого подхода к оценке обобщающей способности, который основан на классическом определении вероятности [49, 52]. Настоящий обзор не претендует на полноту изложения. Основное внимание будет уделено оценкам, использующим понятие УС-размерности, локальным оценкам избыточного риска и РАС-Вауев оценкам переобучения, применимым к линейным решающим правилам.

В данном разделе мы будем придерживаться обозначений, введенных в [59]. Пусть (Г2, Е, V) — вероятностное пространство, а X, Хх,..., Хп — одинаково распределенные случайные величины, принимающие значения в измеримом пространстве (Б,^) с общим распределением Р. Через Рп обозначим эмпирическое распределение, построенное по п наблюдениям:

где 5Х, х £ 5 — дельта-функция Дирака. Пусть Ж = {/: 5 —> [0,1]}—класс измеримых функций. В дальнейшем мы будем интерпретировать значения функций / е & как «потери», а математическое ожидание /(X),

как риск, связанный с определенным «решающим правилом».

Пример 1.1. Рассмотрим задачу классификации. Пусть X множество объектов, а ¥-множество вещественных (или целочисленных) ответов. Положим Б = X х ¥. Для произвольного алгоритма классификации д: X ¥ и прецедента (х, у) € 5 определим величину потерь как /(х,у) = (д(х) — у)2. После нормировки эти потери можно рассматривать как функцию /: 5 —»■ [0,1]. Тогда класс функций потерь & получится, если перебрать все классификаторы д из определенного семейства (например, из семейства всех линейных классификаторов в исходном признаковом пространстве задачи). В дальнейшем для краткости обозначений нам будет удобнее забыть об этой структуре множеств

1.1 Основные определения ЯЬТ

¿=1

Нас будет интересовать задача минимизации риска

Pf -»■ min, / е (1.1)

в условиях неизвестного распределения Р. Поэтому вместе с задачей (1.1) будет также рассматриваться задача минимизации эмпирического риска

- it Л*;) = [ fdPn = Pnf min, (1.2)

n j=l Js

Определение 1.1. Избыточным риском функции f Е & назовем величину

£{f) = Pf-MPg.

Обозначим через / = /„ Е Arg min Pnf решение задачи минимизации эмпирического риска (1.2). Функция /„ используется как приближенное решение задачи минимизации истинного риска (1.1), а значит, избыточный риск £(fn) является естественной мерой ошибки приближенного решения. Кроме избыточного риска полезно рассматривать уклонение Pf — Pnf, показывающее, как точно эмпирический риск приближает истинный риск.

Семейство случайных величин {(Р — Pn)f}fe& называют эмпирическим процессом, индексированным классом &. Нормой эмпирического процесса называют величину \\Р - Рп\\^ = sup \(Р - Pn)f\.

В дальнейшем нас будут интересовать оценки следующего вида:

Рп {Pfn - Pjn > е) < В2(е, п, а также доверительные интервалы при заданном уровне надежности rj:

(1-4)

Р" {Pfn - Pnfn > £2(Г], П, J^H 7?.

Во всех оценках (1.3) и (1.4) вероятность Рп = Р®" соответствует реализациям выборки (Xi,..., Хп) с S.

1.2 Неравенства концентрации меры

Неравенства концентрации меры [48, 51, 65] играют большую роль при выводе оценок вида (1.3) и (1.4). В данном параграфе мы рассмотрим простейший случай (класс

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

п

1

Заметим, что Р/ — Рп/ = Е/(Х) ~ Следовательно, по закону больших чисел

1=1

эмпирический риск хорошо аппроксимирует истинный риск при больших значениях п:

1 п

рп{ ^ -£№)-е/(*) = О} = 1-

V п->оо П £—' }

3=1

Неравенство Хевдинга дает количественную оценку на скорость этой сходимости. Теорема 1.1 (Хевдинг). Пусть Х\,...,Хп — независимые одинаково распределенные случайные величины, принимающие значения на отрезке [а,Ъ\. Тогда для всех е > О выполнено

Р" {Е/(Х) - £ е] < ехр ( - (1.5)

.7=1 ^ '

Обозначим правую часть (1.5) через 8 и выразим е через 5. Получим, что с вероятностью не менее 1 — 6 выполнено следующее:

(1.6)

Более точную оценку можно получить из неравенства Бернштейпа. Оно уточняет неравенство Хевдинга благодаря учету дисперсии случайных величин Хх,..., Хп. Теорема 1.2 (Бернштейн). Пусть Х\,..., Хп —независимые (но не обязательно одинаково распределенные) случайные величины с нулевым математическим ожиданием, принимающие значения на отрезке [—с, с]. Пусть

а2

1

Тогда для любого е > О выполнено

п 3=1

При использовании неравенства Бернштейна получим следующую оценку, выполненную с вероятностью не менее 1 — 5:

V п 3 в

где а2 = Df(X).

К сожалению, неравенства (1.6) и (1.7) оказываются верными лишь для фиксированной функции /, и оказываются неверными, если функция выбирается из класса & по данным (Хь ..., Хп).

1.3 Теория Вапника-Червоненкиса

Чтобы справиться с ситуацией > 1, величину Pfn — Pnfn для функции / £ & ограничивают сверху супремумом по всему классу функций [4, 5]:

Pfn - Pnfn < SUP Pf - Pnf.

Для конечного клас