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

КОЧЕДЫКОВ ДЕНИС АЛЕКСЕЕВИЧ

ОЦЕНКИ ОБОБЩАЮЩЕЙ СПОСОБНОСТИ НА ОСНОВЕ ХАРАКТЕРИСТИК РАССЛОЕНИЯ И СВЯЗНОСТИ СЕМЕЙСТВ ФУНКЦИЙ

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

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

- 8 ДЕК 2011

Москва, 2011

005004974

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

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

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

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

Дьяконов Александр Геннадьевич

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

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

(государственный университет)

_2011

Защита диссертации состоится на заседании диссертациониого совета .02 в Учреждении

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

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

См С

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

2011 г.

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

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

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

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

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

В предположении, что все обучающие выборки заданного размера равновероятны, ставится задача оценивания вероятности переобучения метода. В англоязычной литературе такая постановка для бесконечной генеральной совокупности носит название РАС-обучения (probably approximately correct learning, Valiant 1984; Boucheron, Bousquet, Lugosi, 2004). Случай конечной генеральной совокупности рассматривается в комбинаторной теории надежности обучения по прецедентам (Воронцов, 2010).

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

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

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

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

Научная новизна. В работе развивается два метода получения оценок обобщающей способности. Оценки, использующие расслоение семейства по частоте ошибок, рассматривались ранее в контексте классической РАС-теории. В данной работе выводятся их комбинаторные аналоги с некоторыми улучшениями. Второй метод — оценки, учитывающие сходство алгоритмов в смысле расстояния Хэмминга между векторами ошибок алгоритмов. Он основан на неравенствах типа Бонферрони, оценивающих вероятность конъюнкции большого числа событий через вероятности дизъюнкции их различных комбинаций и технику производящих функций. Данный метод является новым. Основная оценка параграфа 4.5 вводит понятие степени связности алгоритма а — числа алгоритмов на единичном расстоянии от а и понятие профиля связности семейства — распределение степени связности в семействе. Оценка улучшает базовую оценку Вапника-Червоненкиса на множитель, экспоненциальный по средней степени связности алгоритмов в семействе (для линейных классификаторов — по размерности пространства параметров). Для семейства линейных классификаторов в работе получены оценки среднего значения и дисперсии профиля связности.

Методы исследования. Основными методами исследования в работе являются комбинаторная теория надежности обучения но прецедентам, оценки концентрации вероятностной меры,

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

Результаты, выносимые на защиту.

1. Получены комбинаторные аналоги вЬеИ-оценок Лэигфор-да-МакАллистера, показано, что они являются аналогом классических оценок Вапника-Червоненкиса и «бритвы Ок-кама» Влумера, и имеют ту же степень завышенное™.

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

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

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

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

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

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

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

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

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

• научная конференция МФТИ 50 «Современные проблемы фундаментальных и прикладных наук» 2007 г. [5];

• научная конференция МФТИ 51 «Современные проблемы фундаментальных и прикладных паук» 2008 г. [4];

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

Результаты неоднократно докладывались на семинарах отдела Интеллектуальных систем ВЦ РАН (руководитель — чл.-корр. РАН Константин Владимирович Рудаков).

Публикации по теме диссертации в изданиях из списка ВАК: [2, 1]. Другие публикации по теме диссертации: [8, 7, 6, 5, 4, 3]. Текст диссертации доступен на странице автора wuw.MachineLearning.ru/wiki, «УчастниюБешэ Kochedykov».

Структура и объём работы. Работа состоит из оглавления, введения, пяти глав, заключения, списка обозначений, списка литературы (66 пунктов). Общий объём работы —101 стр.

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

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

Введение

§1.1. Пусть X — множество объектов, Y — множество допустимых ответов, J- — параметрическое семейство отображений из X в Y, называемых алгоритмами, X = {a,'i,..., Xj,} С X — фик-

сированная конечная генеральная совокупность из Ь объектов, называемая полной выборкой.

Будем называть подмножества ХсХ, \Х\= I обучающими выборками. Метод обучения ц есть отображение 2х

Пусть задана бинарная функция потерь I: Т х X —>• {0,1}. Если /(/,ж) = 1, то говорят, что алгоритм / е Т допускает ошибку на объекте х Е X.

Вводится множество ¿-мерных бинарных векторов ошибок алгоритмов из Т на полной выборке X:

Будем для краткости обозначать (1) как А = 1(7", X) и называть векторы из А также «алгоритмами», имея ввиду произвольный алгоритм из соответствующего класса эквивалентности на Т. Число ошибок алгоритма а € Л на X С X есть п(а,Х) =

— card {х € X: 1(а,х) — 1}, частота ошибок есть i'(а,Х) = = п(а, Х)/\Х\. Будем пользоваться сокращенными обозначениями n(a, X) = па, п(а,Х) = па, и(а,Х) = иа, и(а,Х) = va.

Будем обозначать через и, v (без индекса а) допустимые значения частоты на полной/обучающей выборке, через т, s

— допустимые значения числа ошибок на полной/обучающей выборке.

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

где [X]* — множество всех ¿-элементных подмножеств X.

(1)

P[vW] = щ Е

(■> хер]«

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

Р[vä < 9(ä,X,J:,ß,a)] ^ 1-а,

где i) — некоторая оценочная функция, значение a G (0,1) достаточно близко к нулю. Назначение таких оценок состоит в том, чтобы, минимизируя оценочную функцию v(ä, X, J-, ß, а) по J7, /х, сконструировать метод обучения ß и семейство Т с наилучшей обобщающей способностью.

§1.2. Вводится общий критерий переобучения U(na,ña) > рассматриваются некоторые его частные случаи: па/L — ñ0Jí ^ е, (ría - ña)/(L -£)- ñjí ^ е и 1 - Hna{fia) >1-V- Определяется вероятность переобучения Р[(/(na,ña) ^ е] и процедура обращения оценки вероятности переобучения:

Р[U{nä,nä) > е] ^ Р(е) ^ Р[na ^ U'1 {щ, Р'1 (а))] < а.

§1.3. Приводится определение и доказываются некоторые свойства гипергеометрического распределения. Пусть имеется L объектов, из которых равновероятно выбирается без возвращения £ объектов. Если среди L объектов на т объектах алгоритм а делает ошибку, то вероятность того, что в выборку попадут s таких объектов, подчиняется гипергеометрическому распределению: hm(s) = (""') (^ГГ) / (г) ■ Вводится функция гипергеометрического распределения Hm(s) =

§1.4. В классических работах критерий переобучения определяется как va ~ va ^ е, однако можно выбрать и другую меру уклонения ¿>а от иа, в частности, квантилъиый критерий:

Я„в(«а)<»У & na^ñ(ña,r)) ña^sna(r¡), (2)

ñ (na, rj) = min {m: Hm(ña) ^ rj} и s„e(r/) = max{s: ЯПа(я) < г/}.

Третий вариант в (2) интерпретируется следующим образом: алгоритм а переобучен, если число его ошибок ña на обучающей выборке меньше '//-квантили распределения НПа(.з). Параметр r¡ здесь играет ту же роль, что е в критерии иа - ¿>а > е, и также называется в работе порогом переобучения. Чем меньше r¡, тем более переобучен алгоритм а. Квантильный критерий удобен тем, что вероятность переобучения для одного алгоритма равна г] независимо от его полного числа ошибок па.

Лемма 1.4.1. Для любого а е А и любого г) G (0,1) справедлива доверительная оценка: Р[na<ñ (ña, r¡)} ^ 1 — q.

Лемма 1.4.2. Для любого a G А и любого rj 6 (0,1) справедлива доверительная оценка Р[гс„ > n(ña,r¡)] ^ 1 — т?, где n{ña,rj) - max{т: 1 - Hm(ña) ^ 77}.

§1.5. Приводятся комбинаторные аналоги классических оценок Вапника-Червоненкиса и «бритвы Оккама» (Блумер, 1987).

Теорема 1.5.1. Для любого семейства Jг, любой полпой выборки X, |Х| = L, метода обучения /i: [Х]£ -> J7, индикатора ошибки I: X х Т {0,1}, и любого а е (0,1) верна оценка

Р[гга > ñ(ñ&,rj)] < \А\г)

и доверительная оценка

^ а.

Отметим, что в этой и последующих оценках величина а имеет смысл вероятности переобучения, а величина ц — порога переобучения и вероятности переобучения для отдельного алгоритма; для VC-оценки а = \А\т].

Теорема 1.5.2. Для любого семейства J7, любой полной выборки X, |Х| = L, метода обучения /х: \Х]е Т, индикатора

п,

ä ^ п (ña, )

ошибки I: X х Т -л {0,1}, любого о. G (0,1) и вектора порогов переобучения r¡ = (i¡n: a G А) имеет место оценка вероятности переобучения

P[na ^ ñ(ñü,r¡á)) < ^Va-aSA

При условии ]Г 7]а — а, верна также доверительная оценка

аеА

P[na > ñ(ña,7fó)] ^ а. (3)

Оценка «бритвы Оккама» позволяет получать более точные в среднем (по обучающим выборкам) доверительные оценки для щ, задавая большие пороги r¡a (и, соответственно, получая меньшие оценки п(п0,т/0)) для тех а, которые чаще являются результатом обучения.

§1.6. Показывается, что оптимальные (в некотором смысле) пороги переобучения в оценке «бритвы Оккама» должны быть пропорциональны вероятностям получения алгоритмов в результате обучения.

Лемма 1.6.1. Для любого семейства J-, полной выборки X, А = I(J",X) и метода //, пусть р = (P[fi(X) = а] : a G А) есть распределение вероятностей получения различных алгоритмов в результате обучения и rj — qa, Y^ Яа — 1 есть нормированный

а€А

вектор порогов переобучения. Тогда минимум min Е (- 1пг/а) до-

ч

стигается при q = р.

В параграфе показывается, что — In 77а имеет смысл квадрата уклонения (у (n0, r/0) - i>a)2 и характеризует точность оценки «бритвы Оккама» для алгоритма а.

§1.7. Приводится процедура оценивания вероятности переобучения методом Монте-Карло для экспериментального сравнения различных оценок вероятности переобучения.

Глава 2. Обзор литературы

Глава содержит краткий обзор методов и результатов теории статистического обучения (statistical learning theory).

Глава 3. Оценки на основе характеристик расслоения семейства

Оценки обобщающей способности, учитывающие расслоение семейства, называемые «shell-оценками», были предложены в работах (Лэнгфорд, МакАллестер 2000, Лэнгфорд 2002). В данной главе выводятся аналогичные комбинаторные оценки. Оценки выводятся более общим и простым образом, показывается, что shell-оценки являются частным случаем (или вариантом) оценок Вапника-Червоненкиса и «бритвы Оккама».

§3.1. Дается определение профиля расслоения и наблюдаемого профиля расслоения семейства. Приводятся примеры оценок профилей методом Монте-Карло для семейства линейных классификаторов, обсуждаются их свойства.

Определение 1. Профиль расслоения множества А есть Дт = = card {а Е А: па = гп}. Будем называть соответствующее подмножество Ат = {аеЛ:п„ = т} т-ым слоем множества А. Профиль наблюдаемых частот ошибок на обучающей выборке X есть случайная величина Д5 = card {а Е А: па — s}.

§3.2. Краткий обзор работ, развивающих идею shell-оценок. §3.3. Выводятся комбинаторные аналоги двух shell-оценок, зависящих от полной выборки X. Показывается, что обе оценки являются вариантом или частным случаем оценок Вапника-Червоненкиса или «бритвы Оккама», хотя исходно они позиционировались как принципиально более точные благодаря учёту

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

Теорема 3.3.3. Для любого семейства Т, полной выборки X, |Х| = Ь, метода обучения //., индикатора ошибки I, если профиль расслоения множества А — есть Дт, то имеет

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

гдеР(з,т/) = Am/im(s) — верхняя оценка вероятности того,

что какой-либо алгоритм из А имеет па обучающей выборке s ошибок и при этом переобучен.

Кроме того, справедлива доверительная оценка:

P[nâ ^ ñ(ñü,r¡(ñá,a)] ^ а,

где r](s,a) = maxjrç: P{s,r¡) < f}.

§3.4. Выводится комбинаторный вариант shell-оценки, зависящей от обучающей выборки X. Оценка мотивируется более простым и наглядным способом, чем исходная оценка Лэпгфор-да — через верхнюю оценку A^(AS) для истинного профиля расслоения Ат по наблюдаемому профилю расслоения As. Исправляется ошибка в доказательстве исходной shell-оценки — пропущенное неравенство Буля rio Í всевозможным значениям наблюдаемой частоты ошибки г)а. Основной результат параграфа представлен следующей теоремой.

Теорема 3.4.3. Для любого семейства Т, полной выборки X, |Х| = L, метода обучения fi, индикатора ошибки I, справедлива доверительная оценка

е

m~2n (s,r¡)

Р [nü<n(ñá,f¡(ñá,a))] ^ 1 -а,

где 7](s, а) = max Ь: 2P(s, г], < §}, P(s, 6) = £ A*mhm(s) -

то

пессимистичная оценка функции P(s,r]), А*п = ^ As — пес-

s: n*(s)=m

симистичная оценка профиля расслоения, n*(s) — пессимистичная оценка полного числа ошибок алгоритма с s ошибками на обучающей выборке,

n*(s) = min {n (s, J/2), max {й (5, 77), п (s, <5/2)}}.

§3.5. Как показывают эксперименты, точность shell-оценок не сильно отличается от точности VC-оценок. В эксперименте основная масса алгоритмов в семействе действительно концентрируется в области наихудшей частоты ошибок D = | и при этом метод обучения ß в основном выбирает алгоритмы из области малых частот ошибок. Таким образом, сложность эффективно используемой части семейства существенно меньше сложности всего семейства Т. Именно эти факты приводятся в качестве исходной мотивации shell-оценок. Однако фактически в shell-оценках они учитываются не в полной мере. Shell-оценки, как и VC-оценка, основаны на вероятности равномерного отклонения частот по всему семейству J-, а не по его части с малыми частотами ошибок. Основной причиной завышенности по-прежнему остаётся неравенство Буля, в котором суммирование вероятностей производится по всему семейству.

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

Глава 4. Оценки на основе характеристик сходства алгоритмов в семействе

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

§4.1. Приводится несколько точных разложений вероятности равномерного отклонения частот, включая разложение по принципу включения-исключения, как альтернатив неравенству Буля. Для удобства вычисления отдельных слагаемых таких разложений вводится понятие графа 1-сходства множества А.

Определение 2. Пусть р(а, а') - [1(а,я) ф 1(а',ж)] — хэм-

хбХ

мингово расстояние между алгоритмами а и а'. Графом 1-сходства множества А — X) будем называть граф Од = (А, Е) со множеством ребер Е = {{а, а'} в Ах А: р{а,а') = 1}, соединяющих алгоритмы, векторы ошибок которых отличаются на одном объекте.

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

§4.3. Предлагается два способа вычисления вероятностей вида Р[и01 ...иак], где И а есть па гС ,н11а (77) — условие переобучения алгоритма а. Первый способ опирается на производящую функцию множества подмножеств из X с заданными свойствами. Второй способ основан на представлении условий ип1... Х5ак в виде системы линейных неравенств с вектором бинарных неизвестных. Между этими двумя способами устанавливается соответствие.

§4.4. Выводится оценка обобщающей способности, учитывающая связность графа I-сходства А.

Теорема 4.4.3. Для любого семейства J7, любой полной выборки X, метода обучения /г: [Х]г —> Т и индикатора ошибки I, если граф G^ множества А — I(Т, X) связный, то выполняется оценка вероятности переобучения:

P[na ^ ñ(ñá,T])] < P{rj) = Т] + \А\ max hm(em(r})).

m

Также верна доверительная оценка

Р[па ^ ñ(ñ¿,?j(a))] sí а,

где 77(a) = max{??: P(r¡) ^ а}.

§4.5. Вводятся понятия полустепени связности алгоритма р+{а) и профиля расслоения-связности Am,g множества А, доказывается оценка обобщающей способности, учитывающая степени связности алгоритмов в А.

Определение 3. Верхняя полустепень связности алгоритма а есть есть число алгоритмов в его верхней единичной окрестности: р+(а) = card {а' € А: р(а, а') = 1, п(а', X) = п(а, X) + 1}. Профиль расслоения-связности множества А — ¡(J7, X) есть матрица чисел:

A m,q — card {а € А: п(а,Х) = т, />+(а) = q} , т, q G {1,..., L} .

Основной результат параграфа представлен следующей теоремой.

Теорема 4.5.7. Для любого семейства Т, полной выборки X, индикатора ошибки I, если профиль расслоения-связности множества А = I(J", X) есть Лтл, то для любого метода обучения д: [Х]< -> J7 вероятность переобучения оценивается как

L L

Р[па ^ п(па,Г))} < Р(г]) = r¡No + ¿\m,qaqm,

д=1 m—0

где /У0 — число алгоритмов в Ас пустой верхней 1-окрестностью, ат = [ < 1]. Также верна доверительная оценка

Р[па ^ й(Па,г](а))} ^ а, (4)

где г/(а) = тах{?7: Р(т]) ^ а}.

Поскольку УС-оценка может быть записана как г]\А\ — — 'г] ЛТО)?, то в последней теореме имеем множители а'^, а < 1

к слагаемым УС-оценки. В эксперименте с семейством линейных классификаторов Главы 6, число М0 алгоритмов без верхних связей в А пренебрежимо мало в сравнении с общим числом алгоритмов, что дает экспоненциальное улучшение оценки последней теоремы относительно неравенства Буля с ростом среднего д. Для модельного случая А — (0,1}ь, Л^ — 1, точное вычисление показывает, что последняя оценка улучшает оценку Вапника-Червонеикиса приблизительно в 20ЛЬ раз.

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

Определение 4. Цепь алгоритмов есть последовательность алгоритмов ах,..., ак, таких, что аА_х) = 1. Будем называть цепь монотонной, если пак = пак-1 + 1- Будем называть монотонную цепь максимальной, если ак € Ам, М = тахпа.

абА

Наличие цепей в А ~ достаточно естественное предположение для семейств Т, непрерывных по параметрам. Цепь может возникать, если выбирается некоторая «начальная» функция в Т и ее параметры изменяются вдоль некоторого непрерывного пути в пространстве параметров.

Основной результат параграфа представлен следующей теоремой.

Теорема 4.6.3. Для любого семейства F, полной выборки X, |Х| = L, индикатора ошибки I: .FxX —t {0,1}, если в множестве А — ЦТ7, X) для любого алгоритма а можно найти максимальную цепь, то для любого метода обучения ц: [Х]'' —> Т верна верхняя оценка вероятности переобучения:

м

P[na ^ n(nd,iy)] ^ P(rj) = N01] + hrn(sm) Ат(Зт,

т=О

где А» = < 1 * (17JU ~ Усеченный биномиаль-

ный коэффициент с вектором ограничений

и = ((«m+1 - Sm), (sM - Sm), ■ - ■ , (sm - Sm)) длины L — т. Также верна доверительная оценка

^ п(п&, 7](а))} < а,

где 77(a) = max {rj: Р(г/) ^ а}.

Усеченный биномиальный коэффициент определяется по аналогии с обычным: (l)u = ((VL + (Г1)и) х[к>ип] с граничными условиями (д) = 1.

§4.7. Экспериментальное вычисление оценок настоящей главы в главе 6 позволяет предположить, что для существенного улучшения оценки необходим учет сходства алгоритмов не столько «в глубину» (крайним случаем которого является максимальная цепь), сколько «в ширину» (крайним случаем которого является единичная окрестность), то есть, учет окрестностей радиуса р > 1 в А и, в пределе, учет сходства каждого алгоритма со всеми алгоритмами, в которые из него идут монотонные цепи.

Глава 5. Характеристики связности семейства линейных классификаторов

В настоящей главе исследуются среднее и дисперсия профиля связности для семейства линейных классификаторов:

Т = {^(¡е) = вщп<ги, ж): к; 6 Ш = Мр+1, х е {1} х . (5)

с индикатором ошибки 1(аю,х) — [а^х) ф у(х)], где у — целевая функция.

Точная форма профиля связности Т зависит от полной выборки X, однако среднее значение профиля и оценка его дисперсии, полученные в Теоремах 5.2.2, 5.4.1 настоящей главы, не зависят от X и являются комбинаторными свойствами семейства линейных классификаторов.

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

(¿-мерной конфигурацией Н(Х) однородных гиперплоскостей называется множество из Ь проходящих через 0 гиперплоскостей в Ш, взаимнооднозначно соответствующих объектам в X:

ЩХ) = Щх{) :ХгЕХ}, к(х{) = {ш, х{) = 0} .

Гиперплоскость /г(хг) разделяет Ш на два полупространства, соответствующие классификаторам, дающим правильный и неправильный ответ на объекте х%. Будем называть первое полупространство положительным, второе — отрицательным.

Гиперплоскости Н разбивают пространство на множество ячеек {с(а),а е А}, взаимнооднозначно соответствующих алгоритмам в А. Каждая ячейка представляет собой ¿-мерный многогранный бесконечный конус с вершиной в 0, включающий

в себя все свои грани. Грани размерности (1-Л взаимнооднозначно соответствуют парам смежных р(а, а') 1 алгоритмов в А.

Будем говорить, что (с! — 1)-мерная грань ячейки с(а),а 6 А положительна, если ячейка лежит в положительном полупространстве соответствующей гиперплоскости, то есть алгоритм а не допускает ошибки на х, а смежный с ним алгоритм — допускает. Тогда значение профиля связности Д+ равно числу ячеек в 'Я, имеющих ровно с[ положительных граней, а значение профиля расслоения Дт — числу ячеек, лежащих ровно в т отрицательных полупространствах.

Известно, что для X в общем положении полное число ячеек и граней в конфигурации 'Н есть, соответственно (Эдельсбрун-нер, 1987):

С0(Ц = 2 £ (V) > № <0 = 21 £ (V) • (6)

к=0 к=О

§5.2. Выводится точное значение для средней степени связности алгоритмов в А. Для небольших (< Ь/2) размерностей пространства параметров, средняя степень связности равна размерности семейства. Это примерно соответствует уменьшению оценки Теоремы 4.5.7 в 2-р раз в сравнении с УС-оцепкой, и согласуется с результатами экспериментального вычисления оценок в Разделе 6.

Теорема 5.2.2. Пусть Т — семейство линейных классификаторов (5) с индикатором ошибки (5.2) и объекты выборки X С находятся в общем положении. Тогда средняя полустепень связности алгоритмов во множестве А — 1(-7-\ X) есть

г . Т^1 (ь'2\

& = И-^аМ =

I к )

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

§5.4. Выводится верхняя оценка для дисперсии степени связности в множестве А. Дисперсия связности определяется суммой квадратов степеней связности или, иначе говоря, суммарным числом пар положительных связей по алгоритмам в А.

Идея оценки состоит в том, чтобы для каждого объекта ж € X рассмотреть подмножество таких алгоритмов в Л, что для каждого из них в А существует алгоритм, отличающийся от него только на х, и оценить суммарное число связей этих алгоритмов при помощи теоремы о сложности зоны гиперплоскости из предыдущего параграфа. Это число связей в свою очередь равно числу тех из интересующих нас пар связей, в которых одна из связей идет через объект х. Суммируя такие оценки по объектам хеХ получаем требуемое число пар связей.

Теорема 5.4.1. Пусть Т есть семейство линейных классификаторов (5) с индикатором ошибки (5.2) и объекты выборки X с Ер находятся в общем положении. Тогда дисперсия полустепени связности алгоритмов во множестве А = ЦТ7, X)

Уага(р^(а)) = ИГ1Е(/%(«)-Л-)2

аел

оценивается сверху как

Уага(р±(а)) ^ Ь-^-¿^35 с0(М)2'

где г^Ь - М) — максимальная сложность зоны в конфигурации 1-1 однородных гиперплоскостей.

Глава 6. Эксперименты с семейством линейных классификаторов

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

§6.1. Приводится процедура Монте-Карло оценки профилей Дта, Д+, Дт,ч и примеры профилей для случайной полной выборки X. Выдвигается гипотеза о возможности представления профиля Дтл в виде произведения профилей Дт и Д+.

§6.2. Для оценивания профилей методом Монте-Карло требуется равномерный сэмплинг большого числа векторов из множества А. Выбор вектора из {0,1}L и определение его принадлежности А требует решения системы L неравенств на каждом шаге и не может использоваться в методе Монте-Карло.

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

§6.3. Эксперименты показывают, что shell-оцепки незначительно улучшают оценки Вапника-Червопеикиса и «бритвы Ок-кама» и подтверждают, что оценка, учитывающая степени связности алгоритмов, меньше VC-оценки на множитель, экспоненциальный по средней степени связности в А.

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

[1] Kochedykov D. A. A combinatorial approach to hypothesis similarity in generalization bounds // Pattern Recognition and Image Analysis, December 2011 — Vol. 21 no. 4.

[2] Kochedykov D. A. Combinatorial shell bounds for generalization ability // Pattern Recognition and Image Analysis, December 2010 — Vol. 20 no. 4. — Pp. 459-473.

[3] Кочедыков Д. А. Структуры сходства в семействах алгоритмов классификации и оценки обобщающей способности // Докл. 14-й Всеросс. конф. «Математические методы распознавания образов» - М.: МАКС Пресс, 2009. - С. 45-48.

[4] Кочедыков Д. А. Комбинаторные оценки обобщающей способности методов обучения по прецедентам с расслоением по наблюдаемой частоте ошибок // Труды 51-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»: Часть VII. Управление и прикладная математика. — М.: МФТИ, 2008.

[5] Кочедыков Д. А., К определению понятия информативности логических закономерностей в задачах классификации // Труды 50-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»: Часть VII. Управление и прикладная математика. — М.: МФТИ, 2007. — С. 279-281.

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

[7] Кочедыков Д. А., Воронцов К. В. О поиске оптимальпых сочетаний управляющих параметров в логических алгоритмах классификации // Тезисы докл. межд. конф. «Интеллектуализация обработки информации», Симферополь, 2006. — С. 117-118.

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

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

18.11.2011

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

1 Введение

1.1 Обозначения.

1.2 Вероятность перебучения и обращение оценок.

1.3 Гипергеометрическое распределение

1.4 Оценка для одного алгоритма.

1.4.1 Стандартный критерий переобучения.

1.4.2 Квантильный критерий переобучения.

1.5 Комбинаторные оценки Вапника-Червоненкиса и «бритвы Оккама»

1.6 Оптимальный набор весов в оценке Occam razor.

1.7 Точная оценка вероятности переобучения но методу Монте-Карло

2 Обзор литературы

2.1 Модель обучения.

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

2.3 Оценки концентрации меры.

2.4 е-покрытия семейства алгоритмов.

2.5 Вещественно-значные семейства и fat-размерность.

2.6 Радемахеровская сложность.

2.7 Оценки с использованием понятия отступа.

2.8 PAC-Bayes подход.

3 Оценки на основе характеристик расслоения семейства

3.1 Профили расслоения семейства алгоритмов.

3.2 Обзор работ по теме.

3.3 Shell-оценки зависящие от полной выборки.

3.4 Shell-оценка, зависящая от обучающей выборки.

3.5 Выводы.

4 Оценки на основе характеристик сходства алгоритмов в семействе

4.1 Мотивация и постановка задачи.

4.2 Обзор работ но теме.

4.3 Вычисление слагаемых в оценках типа Бонферрони

4.4 Оценка с учетом связности семейства.

4.5 Оценка с учетом распределения полустеиеней связности алгоритмов

4.С Оценка с учетом монотонных цепей алгоритмов.

4.7 Выводы.

5 Характеристики связности семейства линейных классификаторов

5.1 Конфигурации гиперплоскостей.

5.2. Средняя связность.

5.3 Зона гиперплоскости в конфигурации.

5.4 Дисперсия связности

6 Эксперименты с семейством линейных классификаторов

6.1 Оценки профилей расслоения-связности но методу Монте-Карло

6.2 Процедура сэмилинга алгоритмов из множества А.

6.3 Вычисление оценок.

6.3.1 БЬеИ-оценки.

6.3.2 Оценки с использованием связности.

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

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

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

В предположении, что все обучающие выборки заданного размера равновероятны, ставится задача оценивания вероятности переобучения метода. В англоязычной литературе такая постановка для бесконечной генеральной совокупности носит название РЛС-обучения (Probably Approximately Correct learning, [63, 19]) и является развитием теории Вапника-Червоненкиса [65]. Случай конечной генеральной совокупности рассматривается в теории надежности обучения по прецедентам [5].

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

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

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

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

Научная новизна. В работе развиваются два метода получения оценок обобщающей способности. Оценки, использующие расслоение семейства ио частоте ошибок, рассматривались ранее в контексте классической РАС-теории. В данной работе выводятся их комбинаторные аналоги с некоторыми улучшениями. Второй метод — оценки, учитывающие сходство алгоритмов в смысле расстояния Хэммипга между векторами ошибок алгоритмов. Он основан на неравенствах типа Бонферрони, оценивающих вероятность конъюнкции большого числа событий через вероятности дизъюнкции их различных комбинаций и технику производящих функций. Данный метод является новым. Основная оценка параграфа 4.5 вводит понятие степени связности алгоритма о — числа алгоритмов на единичном расстоянии от а и понятие профиля связности семейства — распределение степени связности в семействе. Оценка улучшает базовую оценку Вапника-Червоненкиса на множитель, экспоненциальный но средней степени связности алгоритмов в семействе (для линейных классификаторов — по размерности пространства параметров).

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

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

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

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

Область исследования согласно паспорту специальности 05.13.17— «Теоретические основы информатики»:

• разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных (п. 5);

• моделирование формирования эмпирического знания (п. 7);

• разработка методов обеспечения высоконадежной обработки информации (п. 11).

Согласно формуле специальности «Теоретические основы информатики», к ней относятся, в числе прочего, «. исследования методов преобразования информации в данные и знания; создание и исследование. методов машинного обучения и обнаружения новых знаний. ». Таким образом, исследование проблемы переобучения соответствует данной специальности.

Апробация работы. Результаты работы докладывались на научных семинарах ВЦ РАН, на конференциях ММРО, ИОИ, научной конференции МФТИ:

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

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

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

• научная конференция МФТИ 50 «Современные проблемы фундаментальных и прикладных наук» 2007 г. [9];

• научная конференция МФТИ 51 «Современные проблемы фундаментальных и прикладных наук» 2008 г. [6];

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

Результаты неоднократно докладывались на семинарах отдела Интеллектуальных систем ВЦ РАН, (рук. чл.-корр. РАН Константин Владимирович Рудаков).

Публикации по теме диссертации в изданиях из списка ВАК: [41, 42]. Другие публикации по теме диссертации: [10, 8, 11, 9, 6, 7]. Текст диссертации доступен на странице aBTopawww.MachineLearning.ru/wiki, «Участник:Вешя КосЬес1укоу».

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

Краткое содержание работы по главам. Во введении определяются основные обозначения, определяется функционал вероятности переобучения и процедура его обращения для получения доверительных оценок частоты ошибок на контроле. Определяется квантильный критерий переобучения. Приводятся комбинаторные аналоги оценки Вапника-Червоненкиса (УС-оценка) и оценки «бритвы Оккама» и выводится оптимальное априорное распределение на множестве алгоритмов для оценки «брртV вы Оккама».

Глава 2 содержит краткий обзор некоторых известных методов и результатов теории статистического обучения.

В главе 3 выводятся комбинаторные аналоги оценок обобщающей способности учитывающих расслоение семейства - так называемых вЬеН-оценок [48, 47], основанных на следующем соображении. Обычно большая часть алгоритмов в Т имеет вероятность ошибки (или частоту ошибок на полной выборке) около 50%. Если метод обучения выбирает алгоритм с малой частотой ошибок на обучающей выборке, то фактически выбор производится не из всего семейства алгоритмов, а лишь из небольшой его части, состоящей из алгоритмов с малой вероятностью ошибки. Размер этой части семейства существенно ниже размера всего семейства, что предполагает возможность точнее оценить вероятность переобучения но сравнению, скажем, с классическими оценками Ваиника-Червоненкиса. В параграфе 3.3 выводится комбинаторная вЬеИ-оценка, которая учитывает эффект расслоения семейства по частоте ошибок на полной выборке, но требует знания полной выборки, то есть является ненаблюдаемой. В параграфе 3.4 выводится наблюдаемая комбинаторная вЬеН-оценка, основанная на расслоении семейства по частоте ошибок на обучающей выборке.

В главе 4 выводятся оценки обобщающей способности, учитывающие сходство алгоритмов в семействе. Оценки основаны на следующих соображениях. В УС-оценке функционал равномерного отклонения частот оценивается сверху ири помощи неравенства Буля. Известно, что оно может быть сильно завышено ири большом числе входящих в него событий. Неравенство, очевидно, становится точным, только если все события в нем взаимоисключающие. При оценивании функционала равномерного уклонения частот, составляющие его события вида «алгоритм а переобучился», наоборот, существенно совместны и их число в неравенстве крайне велико. Как следствие, неравенство Буля представляет собой один из самых существенных факторов завышенное™ УС-оценки. Можно улучшить оценку неравенства Буля учитывая пересечения входящих в него событий. Пример такого учета дает разложение функционала равномерного отклонения частот по принципу включения-исключения. Очевидно, что пересечение событий вида «алгоритм а переобучен» составляющих функциомал равномерного отклонения частот определяется сходством соответствующих алгоритмов. В главе рассматривается хэммингово сходство векторов ошибок алгоритмов, определяется граф 1-сходства на множестве векторов ошибок, предлагается способ вычисления вероятностей пересечений соответствующих событий в функционале равномерного отклонения частот и выводятся оценки, учитывающие различные характеристики сходства алгоритмов в семействе. В параграфе 4.4 выводится оценка учитывающая связность графа 1-сходства семейства, в параграфе 4.5 выводится оценка учитывающая распределение полустепеней вершин в графе — профиль связности, в параграфе 4.6 выводится оценка учитывающая наличие цепей в графе.

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

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

1.1 Обозначения

Пусть X некоторое множество объектов и У некоторое множество «ответов» допустимых для объекта из X. Пусть Т некоторое параметрическое семейство отображений из X в У, будем называть их алгоритмами, имея ввиду, что они должны допускать эффективную вычислительную реализацию. Пусть X С А" некоторая фиксированная конечная генеральная совокупность из Ь объектов, будем называть се полной выборкой. Пусть задана бинарная функция потерь I: Т х X —> {0,1}. Если /(/,£') = 1, то говорят, что алгоритм / € ? допускает ошибку на объекте ж € X.

Например, в задачах классификации обычно полагают 1(/,х) = [/(х) ф у(х)]; 7 . Здесь и далее задачах регрессии можно полагать /(/,х) = ^ |/(я) — у{х)\ квадратные скобки обозначают индикаторную функцию, равную 1, если условие в скобках истинно, и 0 иначе.

Рассмотрим конечное множество ¿-мерных бинарных векторов ошибок алгоритмов из Т на полной выборке X:

Допуская несущественную нестрогость в обозначениях, будем далее для краткости обозначать (1.1) как А = X).

Определим отношение эквивалентности на F: f\ ~ /2, если I(fi,x) = /(/2,х) для всех х G X. Элементы множества a G А взаимно однозначно соответствуют классам эквивалентности на J-. Будем говорить, что / £ F представляет алгоритм а е А, если а = (I(/,zi),. ,I(/,xL)).

Для краткости везде далее будем называть векторы ошибок из А также алгоритмами, имея ввиду произвольный алгоритм из соответствующего класса эквивалентности на Т.

Заметим, что мощность А может быть оценена сверху либо как Ylt=о id)' гдс d есть VC-размерность [64] семейства бинарных функций {/(/, •): / € J7}, либо как 2L, если его VC-размерность бесконечна.

Число ошибок алгоритма а 6 А (или любой функции / € Т из соответствующего ему класса эквивалентности) на произвольной выборке X С X определяется как п(а, X) = card {х £ X: 1(а,х) = 1} .

Частота ошибок определяется как v(a, X) = ^j^p-- Будем называть частоту ошибок на полной выборке и(а,Х) истинной частотой ошибок алгоритма а; число ошибок на полной выборке п(а, X) — полным числом ошибок. Частота ошибок алгоритма а на полной выборке X представляет аналог вероятности ошибки алгоритма в стандартном РАС-подходе.

В дальнейшем качество алгоритмов будет характеризоваться только числом или частотой ошибок — величинами, зависящими от бинарного вектора ошибок. Поэтому алгоритмы с одинаковыми векторами ошибок можно считать неразличимыми и рассматривать метод обучения ¡л как отображение ¡л: 2х —» А.

Обозначим через [Х]г множество всех подмножеств из X мощности £:

Будем называть подмножества X € [Х]^ обучающими или наблюдаемыми выборками, и(а, X) — наблюдаемой частотой ошибок, п(а, X) — наблюдаемым числом

1.1)

Х]е ={Х СХ: \X\ = t). ошибок. Будем также пользоваться сокращенными обозначениями п(а, X) = па, п(а, X) = па, и(а,Х) = иа, и(а,Х) = 1>а. Будем обозначать через «>е {?.{} без индекса а)—допустимые значения частоты на полной/обучающей выборке и допустимые значения числа ошибок на полной/обучающей выборке.

Допустим, что все разбиения полной выборки X на две подвыборки, наблюдаемую обучающую X длины I и скрытую контрольную Х\Х длины Ь — £, равновероятны. Это предположение является ослабленным вариантом стандартной гипотезы о независимости объектов выборки при выборе из распределения вероятностей. Будем называть произвольный предикат <р\ [Х]£ —> {истина, ложь} событием. Определим вероятность события (р как долю выборок в [Х]г, для которых <р истинен:

Р[¥>(*)] = Ш Е

V«/ А'€[Х]«

Для произвольных предикатов ^ъУг будем обозначать через щ V<рг<р2, их дизъюнкцию, конъюнкцию и отрицание, соответственно. Для набора предикатов кр\,(рк будем обозначать дизъюнкцию и конъюнкцию как N/¿9, и А; Отметим, чтоР[л*=1^] Ы-.-Ы

Произвольную функцию £: [Х]г где Г1 — некоторое множество, будем называть случайной величиной. В случае Z ~Ш определим математическое ожидание как среднее значение но всем разбиениям: =

Алгоритм а = //(А), получаемый в результате обучения, является случайной величиной, принимающей значения из А.

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

Р[иа < Р(а,Х,Т,1.1,а)] ^ 1-а, где V некоторая оценочная функция и « € (0,1) достаточно близко к нулю. Назначение таких оценок состоит в том, чтобы, минимизируя оценочную функцию p(â, X, F, [i, а) но F, //., выбрать метод обучения /у, и семейство F с наилучшей обобщающей способностью.

Заключение

Результаты, выносимые на защиту:

1. Получены комбинаторные аналоги вЬеН-оценок Лэнгфорда-МакАллпстера, показано, что зЬеИ-оценки являются аналогом стандартных оценок Вашшка-Чер-воненкиса и «бритвы Оккама» Блумера и имеют ту же степень завышенное™.

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

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

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

1. Бернштейп С. Теория вероятностей. — Г&зтехиздат, Москва, 1046.

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

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

4. Agarwal Р. К., Sharir М. Arrangements and their applications // Handbook of Computational Geometry. 1998. - Pp. 49-119.

5. Anthony M., Bartlett P. Neural network learning: theoretical foundations.— Cambridge University Press, 1999.

6. Boucheron S., Bousquet O., Lugosi G. Concentration inequalities // Advanced lectures on machine learning. — Springer, 2004. — Pp. 208-240.

7. Boucheron S., Bousquet 0., Lugosi G. Theory of classification: some recent advances // ES AIM Probability & Statistics. — 2005. — Vol. 9. — Pp. 323-375.

8. Bousquet O., Boucheron S., Lugosi G. Introduction to statistical learning theory // Advanced Lectures in Machine Learning. — Springer, 2004,— Pp. 169-207.

9. Devroye L., Gyôrfi L., Lugosi G. A Probabilistic Theory of Pattern Recognition. — SpringerVerlag, 1996.

10. Devroye L., Lugosi G. Lower bounds in pattern recognition and learning // Pattern Recognition.- 1995.- Vol. 28, no. 7.- Pp. 1011-1018.

11. Diaz J., Petit J., Serna M. A guide to concentration bounds // Handbook on randomized computing. — Vol. II. — Kluwer Press, 2001.- Pp. 457-507.

12. Dohmen K. Improved Bonferroni Inequalities via Abstract Tubes. — Springer-Verlag, 2003. Edelsbrunner H. Algorithms in Combinatorial Geometry. — Springer-Verlag, 1987.

13. Galambos J., Simonelli I. Bonferroni-type Inequalities with Applications. — Springer-Verlag, 1996.

14. Grunbaûm B. Convex Polytopes. — Springer, 2003. Griinbauin B., Klee V. Convex Polytopes. — Springer-Verlag, 2003.

15. Hunter D. An upper bound for the probability of a union // J. Appl.Probab. — 1976. — Vol. 13. Pp. 597-603.

16. Hush D., Scovel C. Concentration of hypergeometric distribution // Statistics & Probability Letters. — 2005. — Vol. 75, no. 2. Pp. 127-132.39. .Johnson N. L., Kotz S., Kemp A. W. Univariate Discrete Distributions.— Wiley-Interscience Publication, 1992.

17. Kochedykov D. A. Combinatorial shell bounds for generalization ability // Pattern Recognition and Image Analysis. — 2010. — Vol. 20. — Pp. 459-473.

18. Kochedykov D. A. A combinatorial approach to hypothesis similarity in generalization bounds // Pattern Recognition and Image Analysis. — 2011, — Vol. 21.

19. Kolmogorov A. N., Tikhomirov V. M. e-entropy and e-capacity of sets in function spaces // Translations of the American Math. Soc. — 1961.

20. Koltchinskii V. Rademacher penalties and structural risk minimization // IEEE Transactions on Information Theory. — 2001.— Vol. 47, no. 5.— Pp. 1902-1914. citeseer. ist. psu.edu/391084.html.

21. Naiman D. Q., Wynn II. P. Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling // The Annals of Statistics. — 1997. — Vol. 25, no. 5. — Pp. 1954-1983.

22. Occam's razor / A. Blumer, A. Ehrenfeucht, D. Haussier, M. K. Warmuth /,/ Inf. Process. Lett. 1987. — Vol. 24. — Pp. 377-380.

23. Peter Orhk II. T. Arrangements of Hyperplanes. — Springer, 2010.

24. Pollai"d D. Convergence of stochastic processes. — Springer-Verlag, 1984.

25. Rigorous learning curve bounds from statistical mechanics / D. Haussier, M. Kearns, H. S. Seung, N. Tishby // Machine Learning. — 1996. —no. 25. — Pp. 195-236.

26. Sill J. Monotonicity and connectedness in learning systems: Ph.D. thesis I CalTech. Univ. — 1998.

27. Stanley R. P. An introduction to hyperplane arrangements // Geometric Combinatorics / Ed. by V. R. E. Miller, B. Sturmfels. 2007.

28. Valiant L. G. A theory of the learnable // Proceedings of the sixteenth annual ACM symposium on Theory of computing. — ACM, 1984.— Pp. 436-445. Vapnik V. N. Statistical Learning Theory. — Wiley, 1998.