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

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

©04600162

ВОРОНЦОВ КОНСТАНТИН ВЯЧЕСЛАВОВИЧ

КОМБИНАТОРНАЯ ТЕОРИЯ НАДЁЖНОСТИ ОБУЧЕНИЯ ПО ПРЕЦЕДЕНТАМ

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

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

1 ДПР 2010

Москва, 2010

004600162

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

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

чл.-корр. РАН

Константин Владимирович Рудаков

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

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

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

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

Алексей Иванович Чуличков

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

Владислав Викторович Сергеев

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

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

Защита диссертации состоится « ^ » 0 2010 г. в ''

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

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан « $ » Жй^ШЦ 2010 г.

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

В. В. Рязанов

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

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

Актуальность темы. Вопрос о качестве восстановления зависимостей по эмпирическим данным является фундаментальной проблемой теории статистического обучения (statistical learning theory, SLT).

Основным объектом исследования в SLT является задача обучения по прецедентам: задана обучающая выборка пар «объект-ответ»; требуется восстановить функциональную зависимость ответов от объектов, т. е. построить алгоритм, способный выдавать адекватный ответ для произвольного объекта. К этому классу задач относятся задачи распознавания образов, классификации, восстановления регрессии, прогнозирования.

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

Возникновение SLT связывают с появлением статистической теории Вапника-Червоненкиса (далее VC-теории) в начале 70-х годов. Основным результатом VC-теории являются верхние оценки вероятности ошибки, зависящие от длины обучающей

выборки и сложности семейства функций, из которого выбирается искомый алгоритм. Согласно УС-теории, для получения надёжных алгоритмов необходимо ограничивать сложность семейства. Естественной мерой сложности конечного семейства является его мощность. Однако на практике гораздо чаще используются бесконечные семейства. Чтобы свести этот случай к конечному, вводится бинарная функция потерь. Тогда лишь конечное число алгоритмов оказываются попарно различимыми на выборке конечной длины. Зависимость этого числа от длины выборки называется функцией роста семейства. В худшем случае она растёт экспоненциально, но если её рост ограничен сверху полиномом фиксированной степени, го оценки являются состоятельными — частота ошибок на обучающей выборке стремится к вероятности ошибки с ростом длины выборки.

Основной проблемой УС-теории является сильная завышен-ность оценок вероятности ошибки. Попытка их практического применения приводит либо к требованию явно избыточного наращивания обучающей выборки, либо к переупрощению семейства алгоритмов. Наиболее интересные случаи —малых выборок и сложных семейств — находятся за границами применимости УС-теории. В частности, сложные алгоритмические композиции на практике могут обеспечивать высокое качество классификации, даже когда УС-оценка вероятности ошибки равна единице. Примерами таких конструкций являются корректные линейные и алгебраические композиции алгоритмов вычисления оценок (Ю. И. Журавлёв, 1977). Нетривиальные оценки вероятности ошибки для таких композиций были получены В. Л. Матросовым в серии работ (1980-1985). Тем самым было показано, что применение сложных композиций не противоречит УС-теории. Однако эти оценки также были сильно завы-

шены, поскольку опирались на УС-теорию. Намного позже широкое распространение получили методы обучения линейных композиций — бустинг (И.Фройнд, Р. Шапир, 1995) и бэггинг (Л. Брейман, 1995). Их статистические обоснования удалось получить П. Бартлетту и др. (1998). Было показано, что верхние оценки вероятности ошибки не зависят от числа базовых алгоритмов в композиции, а только от сложности семейства базовых алгоритмов. Эти оценки опираются на усовершенствованный вариант УС-теории, но также не являются численно точными.

Основной причиной завышенности УС-оценок является их чрезмерная общность. Они справедливы для любой выборки, любой восстанавливаемой зависимости и любого метода обучения, включая худшие случаи, никогда не встречающиеся на практике. Очевидно также, что одна скалярная характеристика сложности семейства, не зависящая от решаемой задачи, не несёт достаточно информации о таком сложном оптимизационном процессе, как обучение по прецедентам. Дальнейшее развитие ЭЬТ шло по пути повышения точности оценок путём учёта индивидуальных особенностей задач и методов обучения. Большое разнообразие исследований в ЭЬТ за последние 40 лет связано с неоднозначностью ответов на вопросы: какие именно характеристики задачи, семейства алгоритмов и метода обучения наиболее существенны, и в то же время достаточно удобны для практического оценивания и управления качеством алгоритма в процессе его обучения. В идеале хотелось бы предсказывать вероятность ошибки примерно с той же точностью, с которой закон больших чисел предсказывает частоту выпадения орла при подбрасывании монеты. Однако проблема получения точных оценок обобщающей способности оказалась гораздо более сложной, и до сих пор не имеет окончательного решения.

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

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

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

Научная новизна. До сих пор вопрос о получении точных оценок в SLT даже не ставился. Задача считалась безнадёжной, и обычно речь шла лишь о «не сильно завышенных» оценках (tight bounds). Для получения точных оценок приходится отказываться от стандартного инструментария SLT — завышенных неравенств Маркова, Хёфдинга, Чернова, МакДиармида, Буля, и др. Комбинаторный подход потребовал радикального пересмотра всей теории, начиная с аксиоматики. Впервые предложена методика эмпирического измерения факторов завышенное™ VC-оценок и локального эффективного коэффициента разнообразия. Предложены новые оценки обобщающей способности на основе порождающих и запрещающих множеств объектов, профилей расслоения, связности, компактности, монотонности.

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

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

Теория надёжности эмпирических предсказаний опирается не на колмогоровскую теоретико-мерную аксиоматику, а на слабую вероятностную аксиоматику, основанную на единственном вероятностном допущении, что все разбиения конечной генеральной выборки на обучающую и контрольную части равновероятны. Этого допущения оказывается достаточно, чтобы получить аналог закона больших чисел, установить сходимость эмпирических распределений и воспроизвести основные результаты УС-теории. Кроме того, в слабой аксиоматике естественным образом строятся непараметрические статистические критерии и доверительные интервалы.

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

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

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

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

1. Слабая вероятностная аксиоматика, основанная на предположении о равной вероятности всех разбиений выборки.

2. УС-оценки вероятности переобучения, учитывающие степень некорректности метода обучения.

3. Методика эмпирического измерения факторов завышенно-сти УС-оценок вероятности переобучения.

4. Блочный метод вычисления вероятности переобучения.

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

6. Рекуррентный алгоритм вычисления точных, верхних и нижних оценок вероятности переобучения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— 7-й открытый немецко-российский семинар «Распознавание образов и понимание изображений», Эттлинген, Германия, 20-25 августа 2007 г. [22];

— ломоносовские чтения, МГУ, 17 апреля, 2008 г.;

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

— международная конференция «Распознавание образов и анализ изображений: новые информационные технологии» РОАИ-9, Нижний Новгород, 2008 г. [21];

— международная конференция «Современные проблемы математики, механики и их приложений», Москва, 30 марта-2 апреля 2009 г.;

— семинар «Знания и онтологии ELSEWHERE 2009», ассоциированный с 17-й международной конференцией по понятийным структурам ICCS-17, Москва, Высшая школа экономики, 21-26 июля 2009 г. [25]; ,

— всероссийская конференция «Математические методы распознавания образов» ММРО-14, 2009 г. [26-28]. Материалы диссертационной работы легли в основу спецкурса «Теория надёжности обучения по прецедентам», читаемого студентам старших курсов на факультете ВМК Московского государственного университета им. М. В. Ломоносова.

Публикации по теме диссертации в изданиях из списка ВАК: [2,3,6-8,22-24]. Другие публикации по теме диссертации: [1,4, 5,9-21,26-28]. Полный текст диссертации доступен на странице автора http: //www. ccas. ru/voron.

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

Общий объём работы — 273 стр.

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

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

Глава 1. Слабая вероятностная аксиоматика

Рассмотрим фундаментальную задачу теории вероятностей, тесно связанную с законом больших чисел: оценить вероятность большого отклонения частоты г/(5, X) события Я на конечной выборке X от вероятности Р(5) данного события:

Ре = Р{К$*)-Р(5)|>е}. (1)

Если вероятностная мера Р неизвестна, то для вычисления вероятности события Р(5) необходимо провести бесконечное число наблюдений, что на практике невозможно. В результате оказывается, что вероятность РЕ не может быть измерена в эксперименте как частота события {X: |гу(5, X) — Р(5)| > е}, поскольку само наступление этого события не может быть точно идентифицировано. Данная проблема не возникает, если вместо вероятности Р(Э) оценивать частоту и (Б, X') события Б на произвольной случайной выборке X':

а = (2)

Если предполагать, что выборки X к X' независимы, то для определения вероятности <2£ не нужно ни бесконечного числа испытаний, ни введения вероятностной меры на исходном пространстве событий. Вероятность С}Е может быть легко измерена в эксперименте или вычислена комбинаторными методами как доля разбиений объединённой выборки X и X' на две подвы-борки, при которых имеет место большое отклонение частот.

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

§1.1. Пусть X = {^1,... — фиксированное множество попарно различных объектов, называемое генеральной выборкой. Обозначим через 57, группу перестановок Ь элементов. Всевозможные перестановки элементов генеральной выборки будем обозначать через гХ, т € 57-

Аксиома 1.1. Все Ы перестановок генеральной выборки тХ, т е 57,1 имеют одинаковые шансы реализоваться.

Пусть задан предикат ф: X1 —> {0,1}. Если ф(тХ) — 1, то будем говорить, что событие ф произошло на перестановке тХ. Вероятность события ф определяется как доля перестановок выборки, на которых оно произошло:

Пусть предикат ф является функцией двух выборок: X С X длины I и её дополнения X = Х\Х длины к = Ь ~ I, причём значение предиката ^(Х) = <р(Х, X) не зависит от порядка элементов в подвыборках X и X. Тогда вероятность определяется

(3)

как доля разбиений выборки X:

Р<р(Х,Х) = ± £ <Р(Х,Х), 1 хещ1

где [Х]^ = [X С X: |Х\=£}.

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

§1.1.1. Задача эмпирического предсказания состоит в том, чтобы, получив выборку X, предсказать некоторые свойства пока ещё неизвестных новых данных X и заранее оценить точность предсказания. Рассмотрим эксперимент, в котором реализуется одно из Сеь равновероятных разбиений генеральной выборки X = X и X. После реализации разбиения наблюдателю сообщается подвыборка X. Не зная скрытой подвыбор-ки X, требуется предсказать значение £ = Т(Х,Х) заданной функции Т: Хк х Xе —> Я, существенно зависящее от скрытой подвыборки X. Для этого строится предсказывающая функция Т: Xе —> И, значение которой на наблюдаемой подвыбор-ке £ = Т(Х) приближало бы неизвестное значение £ = Т(Х,Х). Требуется оценить надёжность предсказаний, указав невозрас-тающую оценочную функцию г)(е) такую, что

Р [й(Т(Х),Т{Х,Х))>е]^г1{е), (4)

где ЛхЛ-» Е — заданная функция, характеризующая величину отклонения I) предсказанного значения í от неизвестного истинного значения Параметр е называется точностью, а величина (1 — г](е)) — надёжностью предсказания. Если в (4) достигается равенство, то т](е) называется точной оценкой.

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

§1.1.2. §1.1.3. §1.1.4. Рассматриваются некоторые базовые приёмы обращения с оценками надёжности эмпирических предсказаний в слабой аксиоматике, а также связь задач эмпирического предсказания и статистической проверки гипотез.

§1.1.5. Рассматривается связь слабой аксиоматики с сильной (колмогоровской) аксиоматикой. Обсуждаются преимущества, недостатки и границы применимости слабой аксиоматики.

§1.2. Пусть 5 С X —некоторое множество объектов; будем называть его «событием». Введём функции числа элементов и частоты события Б на произвольной конечной выборке и С X:

п(С0 = |5пЕ/|, и(и) = п(и)/\и\.

Задача оценивания частоты события состоит в том, чтобы предсказать частоту на скрытой выборке X по частоте на наблюдаемой выборке X и оценить надёжность предсказания:

Р [и(Х)-и(Х)2е]^г1(еУ, (5)

Лемма 1.2. Если п(Х) = тп, то число элементов события Б в наблюдаемой подвыборке п(Х) подчиняются гипергеометрическому распределению:

Р[п(Х)=8]=%т(8) = Щ%^, (6)

где в принимает значения от йо= шах{0, т—к} до й1= тт{£, т}.

Теорема 1.3. Если п(Х) — т, то для любого е £ [О,1)

Р [и{Х)>е]=Н^{[т-ек\)- (7)

Р[и{Х) - К*) И = (Ж™ - , (8)

где 11 ¿т (г) = /г/" (5) — функция гипергеометрического

5=30

распределения.

При пропорциональном увеличении Ь, £ и т относительная ширина гипергеометрического пика уменьшается. Поэтому в пределе при Ь, £, т —> оо возможно сколь угодно точно предсказывать частоту события 5 в скрытой выборке и(Х) по его частоте на наблюдаемой выборке и(Х). Равенство (8) даёт точную оценку скорости сходимости частот (справедлива также аналогичная двусторонняя оценка). Классический закон больших чисел утверждает сходимость частоты события к её вероятности. В слабой аксиоматике понятие «вероятности события 5» не определено, поэтому (8) можно интерпретировать как аналог закона больших чисел в слабой аксиоматике.

§1.3. Рассматривается задача оценивания функции распределения, тесно связанная с двухвыборочным критерием Колмогорова-Смирнова. Выводятся точные формулы для распределения величины равномерного отклонения эмпирических функций распределения на двух выборках. Это распределение описывается усечённым треугольником Паскаля. В рамках слабой аксиоматики критерий Смирнова, обычно формулируемый для случайных величин с непрерывным распределением, легко обобщается и на случай дискретных величин.

§1.4. Демонстрируется возможность получения стандартных статистических критериев и доверительных оценок в рам-

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

§1.5. Задача оценивания вероятности переобучения является основной в данной работе. Задано множество А, элементы которого называются алгоритмами. Существует бинарная функция I: А х X —> {0,1}, называемая индикатором ошибки. Если /(о, х) = 1, то алгоритм а допускает ошибку на объекте х, если же 1(а, х) = 0, то а даёт верный ответ на х. Определяются функции числа ошибок п(а, U) = Y1 (а>х) и частоты ошибок

хеи

и(а, U) = n(a, U)/\U\ алгоритма а на выборке U С X.

Бинарный вектор-столбец а = (I(a,Xi))f=1 называется вектором ошибок алгоритма а. Совокупность всех попарно различных векторов ошибок, порождаемых алгоритмами а (Е А, образует матрицу ошибок размера LxD. Строки этой матрицы соответствуют объектам, столбцы —алгоритмам.

Далее предполагается, что А — это конечное множество алгоритмов с попарно различными векторами ошибок.

Методом обучения называется отображение ц\ 2х —> Д которое произвольной обучающей выборке X С X ставит в соответствие некоторый алгоритм а — цХ из А.

Метод ¡л, называется методом минимизации эмпирического риска, если для любого X С X

цХ <Е А(Х) = Arg min п(а,Х) =

абЛ

= {а е А: п(а,Х) < п(а',Х), У а' е А}. (9)

Переобученностъю метода ¡1 относительно пары выборок X и X называется отклонение частоты ошибок алгоритма а — /лХ на скрытой контрольной выборке X от частоты его ошибок на наблюдаемой обучающей выборке X:

5(1{Х,Х) = и{цХ,Х)-и{цХ,Х).

Если 5^(Х, X) ^ е при некотором достаточно малом е 6 6 (0,1), то говорят, что метод /л переобучен относительно X, X.

Итак, основная задача заключает в том, чтобы оценить вероятность переобучения:

<Зе = <2е{1л,Х) = Р[б11{Х,Х)>е]. (10)

§1.5.3. Вводятся некоторые важные в УС-теории понятия.

А = {а: а £ А}—множество векторов ошибок, порождаемых заданным множеством алгоритмов А.

А(А,Х) = |Л| — коэффициент разнообразия множества алгоритмов А на выборке X. В задачах классификации на два класса коэффициент разнообразия равен числу различных дихотомий (способов разделить выборку X на два класса), реализуемых всевозможными алгоритмами из А.

А1Ь = X) = {цХ: X 6 [X]*} —множество алгоритмов, индуцируемых методом обучения ¡1 на всевозможных обучающих подвыборках X.

Д^ = Д^/л, X) = Д(Л£(//,Х),Х) — локальный коэффициент разнообразия метода ¡л на выборке X.

АЛ(Ь) = тах А(А,Х) — глобальный коэффициент разнообразия или функция роста множества алгоритмов А. Максимум берётся по всевозможным выборкам X С Ж" длины Ь из некоторого (как правило, бесконечного) множества допустимых объектов ЗС. Функция роста является мерой сложности множества

алгоритмов А. В отличие от локального коэффициента разнообразия, она не зависит ни от задачи, ни от метода обучения до.

Ат — {а € А: п(а,Х) = т}—подмножество алгоритмов, называемое т-м слоем множества А. Будем также говорить, что множество А расслаивается по уровням ошибок.

Ат = Дт(до, X) = Д((Л^)те, X) — локальный коэффициент разнообразия т-го слоя множества X). Совокупность величин (Дт)^=0 будем называть профилем расслоения.

§1.5.4. УС-теория переносится в слабую аксиоматику.

Теорема 1.12. Для любых до, X и е £ [0,1]

£ ДтН^{[Цт-ек)\)^

т~\ек]

шах Н^([{(т-ек)\). (11)

Оценка (11) имеет следующую интерпретацию. Вероятность переобучения не превышает вероятности большого отклонения частот для наихудшего алгоритма (максимум Не£т достигается при ттх Ь/2), умноженной на число алгоритмов.

Оценивая локальный коэффициент разнообразия глобальным ДКдо, X) ^ ДЛ(Ь) и заменяя функцию гипергеометрического распределения экспоненциальной верхней оценкой, получаем ещё одну известную классическую УС-оценку:

Следствие 1.12.2. Для любых до, X, в е [0,1) при I — к

а < Аа(2£) ■ ¡е~£2е. (12)

§1.5.5. В УС-теории отдельно рассматривается детерминистская постановка задачи, когда п{р,Х, X) = 0 на любой обучающей выборке X. Однако в общей постановке задачи не делается никаких предположений о величине п([хХ,Х). В данной работе предлагается исследовать и промежуточные ситуации.

Степенью некорректности метода обучения ¡л на выборке X называется максимальная частота ошибок на обучении

сг(д, X) = max uiaX.X).

хе[х)«

Теорема 1.13. Для любых yu, X с ограниченной некорректностью a(fi, X) ^ о и любого е 6 [0,1] справедлива оценка

^ Д1 _ max Him (minflj(m - ek)\ tai}) • (13)

Следствие 1.13.1. Если метод ¡1 корректный на генеральной выборке X, то есть а(ц, X) = 0, то для любых ц, X и е 6 [0,1]

[к+аЦ £ . . £к

Е < < (Ь) . (14)

ТП—

Следствие 1.13.2. Если £ = к и метод (х корректный на генеральной выборке X, то для любых ц, X и е € [0,1]

Я, ^ Дл(2<?) 2~и. (15)

§1.5.6. Основной недостаток УС-оценок в том, что они чрезвычайно завышены — настолько, что их применение практически теряет смысл. Для наглядности в работе приводятся результаты численного расчёта требуемой длины обучающей выборки I как функции от ёмкости /г, точности е и уровня значимости (надёжности) С)Е. Расчётные значения £ на порядки превосходят характерные длины выборок в практических задачах.

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

§1.5.7. Причины завышенности видны из доказательства теоремы 1.12, в котором сделаны три оценки сверху, а при выводе следствия 1.13.1 — ещё две. Те же причины остаются и в теореме 1.13. Всего имеется 5 факторов завышенности.

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

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

3. Пренебрежение профилем расслоения является малозначимым фактором.

4. Пренебрежение эффектом локализации приводит к сильной завышенности, когда локальное подмножество Аеь([1,Х) много меньше всего семейства А.

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

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

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

сические УС-оценки, для которых методика эмпирического измерения завышенное™ разрабатывается сравнительно легко.

Глава 3. Эмпирический анализ факторов завышенное™ \/С-оценок

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

Р£ = Р{ вир(Р(а) - и(а, X)) ^ е }

абА

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

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

= Р{и{^Х,Х) - и(цХ,Х) > е},

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

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

§3.1. Зная эмпирическую оценку можно сказать, какое значение должна была бы иметь функция роста А, чтобы УС-оценка С}е ^ Дт?(£) не была завышенной и обращалась в точное

равенство. Здесь 77(5) — вероятность большого отклонения частот в двух выборках для отдельного алгоритма. Гипотетическое точное значение функции роста Д = Яе/я^) предлагается называть эффективным локальным коэффициентом разнообразия (ЭЛКР). Возможна ещё одна интерпретация ЭЛКР — он показывает, во сколько раз снижается надёжность предсказания качества обучения по сравнению с предсказанием частоты ошибок отдельного алгоритма, которое даёт закон больших чисел.

§3.2. Эксперименты с логическими алгоритмами классификации на реальных задачах из репозитория 11С1 показали, что среди всех факторов завышенности наиболее существенными являются два —это игнорирование свойств расслоения и связности семейства алгоритмов. Каждый из этих двух факторов завышает оценку С}Е в 103-105 раз. На практике ЭЛКР принимает значения порядка 10°—102, тогда как функция роста обычно имеет порядок 105-1010 и выше.

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

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

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

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

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

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

мейств простой структуры. Затем эти оценки были обобщены и обнаружен общий механизм их вывода, основанный на порождающих и разрушающих множествах объектов.

Глава 4.

Точные оценки вероятности переобучения

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

§4.1.1. Обозначим через А(Х) = Arg min п(а, X) множество

аеД

алгоритмов с минимальным числом ошибок на обучении X.

Определение 4.1. Метод ¡л называется минимизацией эмпирического риска (МЭР), если ßX е А(Х) при всех X С X.

Если множество А(Х) содержит более одного элемента, то в методе ¡л возникает проблема неоднозначности выбора алгоритма. Рассмотрим два крайних случая.

Определение 4.2. Минимизация эмпирического риска р называется оптимистичной, если ßX = arg min п(а,Х).

ае А(Х)

Определение 4.3. Минимизация эмпирического риска // называется пессимистичной, если аХ — are max п(а,Х).

аеА(Х)

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

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

Гипотеза 4.1. Множество А, выборка X и метод до. таковы, что для каждого а £ А можно указать пару непересекающихся подмножеств Ха С X и Х'а С X, удовлетворяющую условию

[цХ=а] = [Ха С X] ¡X Я X], VX6 [X]*. (16)

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

Для произвольного а G А введём обозначения:

La = \X\Xa\X'a\-, та = п(а, Х\Ха\Х'а)-

Еа = \X\Xa\-, sa(e) = j;(n(a,X)-ek)-n{a,Xa).

Лемма 4.2. Если гипотеза 4.1 справедлива, то Р(а) = Р[доХ=а] = Cil/Cl

Теорема 4.3. Если гипотеза 4.1 справедлива, то вероятность переобучения вычисляется по формуле

аеА

Гипотеза 4.1 накладывает настолько сильные ограничения на X, Л и до, что теорему 4.3 удаётся применять лишь в специальных случаях. Рассмотрим её естественное обобщение.

Гипотеза 4.2. Множество А, выборка X и метод до таковы, что для каждого аеА можно указать конечное множество индексов Va, и для каждого индекса v G Va можно указать пороэю-дающее множество Xav С X, запрещающее множество X'av С X и коэффициент cav G К, удовлетворяющие условиям

[цХ=а] = Со»[Ха» С х] [Х'т çx], \fX G [Xf. (17)

VGVa

Гипотеза 4.1 является частным случаем гипотезы 4.2, когда все множества Va одноэлементные и cav — 1.

Теорема 4.4. Гипотеза 4.2 верна всегда: для любых X, А и /л существуют множества Va, Xav, X'av, при которых имеет место (17), причём cav = 1 для всех а Е A, v G Va.

Теорема 4.4 является типичной теоремой существования. Использованный при её доказательстве способ построения индексных множеств Va требует явного перебора всех разбиений выборки, что приводит к вычислительно неэффективным оценкам Qe. В общем случае представление (17) не единственно. Отдельной проблемой является поиск представлений с минимальными по мощности множествами Va, Xav, X'av.

Введём для каждого a G А и каждого v £ Va обозначения:

Lm = |Х\ХвД.Щ; mav = n(a, X\Xav\X'av)]

Lv = |X\Xat)|; ' sav(e) = |(n(a,X) - efc) - n{a,Xav)-

Лемма 4.5. Если гипотеза 4.2 верна, то для всех а Е А Р(а) = Р [цХ=а] = £ CavPav] (18)

veva

Pav = Р [хю С X] [X'av С X] = CfcjCl. (19)

Теорема 4.6. Если гипотеза 4.2 справедлива, то вероятность переобучения вычисляется по формуле

a = EE ^PaVH[a::mav (МЮ). (20)

aeA veva

Формула (20) сильно упрощается, если в семействе А содержится корректный алгоритм оо, не допускающий ошибок на генеральной выборке X.

Теорема 4.7. Пусть гипотеза 4.2 справедлива, метод ц минимизирует эмпирический риск, множество А содержит алгоритм а0 такой, что п(а0,Х) — 0. Тогда

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

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

§4.2.1. Рассматривается множество из двух алгоритмов А = = {oi, а2}. Пусть в выборке X имеется ти объектов, на которых оба алгоритма допускают ошибку; тю и moi объектов, на которых, соответственно только ai или только а2 допускает ошибку.

(21)

аеЛ

Теорема 4.9. Пусть /л — пессимистичная минимизация эмпирического риска, А = {а.1, а2}. Тогда при любом £ € [0,1)

тц тю m0i psц fsio fs0i /^¿-sn-sio-soi g _ ^ ^ тц mio^rrapi^ L—mu—mw—moi

sn=0sio=0soi=0

X

X ( [sio < Soi] [su + Sio ^ i (mil + mio - efc)] + + [ею > Soi] [su + Soi ^ £ (mu + moi - £*)])• (22)

§4.2.2. Рассматривается множество A, состоящее из всех С™ алгоритмов с попарно различными векторами ошибок и ровно m ошибками на полной выборке X. Поскольку все возможные векторы ошибок образуют булев куб размерности L, то векторы ошибок множества А — это m-й слой булева куба.

Теорема 4.10. Пусть ¡л — произвольный метод минимизации эмпирического риска, А — m-й слой булева куба. Тогда Q£ — = [ек ^ m ^ £ — е£] для любого е е [0,1].

Хотя оценка вырождена и принимает только два значения, О или 1, из неё следуют два важных вывода. Во-первых, алгоритмы нижних слоёв m < \ек~\ не вносят вклад в переобучение. Во-вторых, никакой слой выше m — \ек~\ не должен целиком содержаться в семействе алгоритмов.

§4.2.3. Рассматривается множество Л, образующее интервал ранга m в L-мерном булевом кубе. Объекты делятся на три категории: т0 «внутренних» объектов, на которых ни один из алгоритмов не допускает ошибок; т\ «шумовых» объектов, на которых все алгоритмы допускают ошибки; и m «пограничных» объектов, на которых реализуются все 2т вариантов допустить ошибки. Интервал булева куба обладает свойствами расслоения и связности и может рассматриваться как модель реального семейства размерности т.

Теорема 4.11. Пусть — пессимистичная МЭР, А — интервал булева куба. Тогда для любого е £ [0,1]

= ЕЕ т1^-т-т1 + ек)].

В работе получена также точная оценка для интервала булева куба при рандомизированной МЭР.

§4.2.4. Рассматривается множество А, образованное £ нижними слоями интервала ранга т в ¿-мерном булевом кубе. Это семейство интересно тем, что оно позволяет исследовать влияние эффекта расслоения на вероятность переобучения, построив зависимость от числа нижних слоев I.

Теорема 4.13. Пусть ^ — пессимистичная МЭР, Л —нижние Ь слоев интервала булева куба. Тогда для любого е е [0,1]

= Е Е - т т1с?-т-т> [а^тг+шш&т-зУек)].

О в!=0 ^

Для множества t нижних слоёв интервала булева куба также получена точная оценка (Зе при рандомизированной МЭР.

§4.2.5. Рассматривается монотонная цепочка алгоритмов, которую можно интерпретировать как простейшую модель од-нопараметрического связного семейства алгоритмов.

Определим расстояние Хэмминга между алгоритмами: ь

р(а,а') — ^¡/(а,^) — 1(а',х{)\, Уа,а' £ А.

г=1

Множество алгоритмов А = {ао, а1}..., а и] называется цепочкой алгоритмов, если — 1 для всех ^ = 1,..., В.

Цепочка алгоритмов А = {ао, ..., ао} называется монотонной, если п(аа, X) — гп + (I при некотором т ^ 0.

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

Теорема 4.16. Пусть А = {ао, а\,..., ад} — монотонная цепочка; Ь ^ т + П. Тогда в случае Б ^ к

а = ЕМО); ^ = ¿ = 0 — .А;

в случае Б <к

Q, = D'£PdHllГ1(sd{e)) + РдЯ^Ые));

<¿=0

£/ I/

где = Р [доХ=асг], »¿(г) = | (т + с? - ек).

§4.2.6. Унимодальная цепочка алгоритмов является более реалистичной моделью однопараметрического связного семейства, по сравнению с монотонной цепочкой.

Множество алгоритмов А = {а0, аг,..., ао, а[,..., а'0,} называется унимодальной цепочкой, если левая ветвь ао, аъ ..., ар и правая ветвь а0, а\,..., а'в, являются монотонными цепочками с общим лучшим алгоритмом ао.

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

§4.2.7. Единичная окрестность лучшего алгоритма является «экстремальным» частным случаем, когда алгоритмы максимально близки друг к другу, и классические оценки, основанные на неравенстве Буля, наиболее завышены.

Множество алгоритмов А = {а0, ах,..., ад} называется единичной окрестностью алгоритма ао, если все векторы ошибок а<г попарно различны, п(аа,Х) = п(а0,Х) + 1 и р(а0,а^) = 1 для

всех d = 1,... ,D. Алгоритм üq называется лучшим в окрестности или центром окрестности.

В работе получены точные оценки вероятности переобучения для единичной окрестности.

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

§4.3. Пусть в А есть корректный на X алгоритм и р — пессимистичный метод МЭР. Задача вычисления Qe сводится к тому, чтобы найти информацию 3(а) = (Xav, X'av, cav)veya для каждого алгоритма а Е А, где Va — индексное множество, Xav — множество порождающих объектов, X'av — множество запрещающих объектов, cav £ IR.

Обозначим через pd метод обучения /i, выбирающий алгоритмы только из подмножества Ad = {а0,..., a.d}. Рассмотрим переход от метода к методу (id при добавлении в Afi~\ алгоритма ad. Допустим, что для всех алгоритмов at, t < d, информация 3(at) относительно метода ра-1 Уже известна. Поставим задачу: вычислить информацию 3(ad) и скорректировать информацию 3(at), t < d, относительно метода pd. Необходимость коррекции вызвана тем, что алгоритм a¿ может «отбирать некоторые разбиения» у каждого из предыдущих алгоритмов at.

Лемма 4.19. Метод ¡i¿ выбирает алгоритм ad тогда и только тогда, когда все объекты, на которых a¿ допускает ошибку, попадают в контрольную выборку:

[pdX=ad] = [X'd С X], X'd = {xj £ X: I{ad, Xi) = 1}.

Лемма 4.20. Корректировка информации 3(at), t < d при добавлении алгоритма ad сводится к проверке для каждого v £ Vt такого, что Xtv П X'd = 0, трёх условий:

1) если Х'й \ Х'1ь — {жг} — одноэлементное множество, то XI присоединяется к Х1у\

2) если \Х'{ \ Х[у\ > 1, то множество индексов К пополняется элементом и], полагая сы = -с1р, Хы, = Х^, Х'ы = Х[у1)Х'а\

3) если \Х'Л \ Х[и | = 0, то из множества индексов 14 удаляется индекс V, а из П(а^) удаляется вся тройка (Х£г1, Х'1л1, сгг)).

Леммы 4.19, 4.20 и теорема 4.7 позволяют рекуррентно вычислять вероятность переобучения (~}£. На каждом ¿-и шаге, (1 = 0,..., Д добавляется алгоритм а^, вычисляется информация З(а^); затем для каждого £ = 0,..., <1 — 1 корректируется информация и вероятности Р^. На основе скорректированной информации обновляется текущая оценка (Зе. По окончании последнего £)-го шага текущая оценка совпадает с точным значением вероятности переобучения. Процедура вычисления точной оценки <ЭЕ описана с помощью псевдокода, облегчающего программную реализацию.

Вычисления могут оказаться неэффективными по времени, если условие 2) леммы 4.20 будет выполняться слишком часто. Каждое его выполнение приводит к добавлению ещё одного слагаемого в сумму (20), причём к новым слагаемым в свою очередь может применяться условие 2), в результате объём вычислений может расти экспоненциально по -О. В работе доказывается, что если в описанной вычислительной процедуре в определённые моменты пропускать проверку условия 2), то можно получать верхние или нижние оценки вероятности переобучения, существенно сокращая объём вычислений. Таким образом, время вычислений удаётся обменивать на точность оценки.

Доказывается, что если проверка условия 2) пропускается всегда, то значение (Зе, вычисляемое такой максимально упрощённой процедурой, будет верхней оценкой вероятности пере-

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

Связностью (¡(а) алгоритма а € А назовём число алгоритмов в следующем слое, допускающих ошибки на тех же объектах, что и а: ц{а) = #{а' е Л(в,х)+1: На,х) ^ 1{а-\х), хеХ}.

Определение 4.12. Профилем 'расслоения и связности множества А называется матрица гДе Дт<? — число алгоритмов в 771-м слое со связностью д.

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

£ (23)

771= [ЕГ£] 9=0 £

Согласно оценке (23) наибольший вклад в вероятность переобучения вносят алгоритмы с малым числом ошибок, начиная с т — | ек]. По мере увеличения т комбинаторный множитель Се£?т_ч/С1 убывает экспоненциально. Увеличение связности q улучшает оценку. Есть основания полагать, что среднее значение связности q определяется размерностью пространства. В общем случае при увеличении размерности пространства возникают два противонаправленных эффекта: с одной стороны, увеличивается число алгоритмов в каждом слое, что приводит к росту с другой стороны, увеличивается связность д, что приводит к уменьшению Второй эффект совершенно не учитывается в классической УС-теории.

Предварительные эксперименты с линейными классификаторами и методом ближайших соседей показали, что профиль расслоения и связности Атд с высокой точностью является се-парабельным: Дт<3 < Дт\, где Дт — коэффициент разнооб-

разия т-го слоя, Хд— доля алгоритмов т-го слоя, имеющих связность ц. Вектор (Ат)т=0,ь предлагается называть профилем расслоения, а вектор (Л9)д=0,г, — профилем связности множества алгоритмов А. В этих терминах немного ослабленная оценка (23) принимает следующий вид:

к лче ь / р \ я

Е Чг^)- (24)

т= [ей] ь <7=0 4 7

V-^-/V-V-'

УС-оценка поправка па связность

Первая часть (24) совпадает с УС-оценкой (14). Вторая часть представляет собой «поправку на связность», экспоненциально убывающую с ростом д, что и делает данную оценку существенно более точной, чем классические УС-оценки (11), (14).

Если профиль Дтд представлен в виде разложения ДтЛд, то вычисления <3£ занимают О(Ь) операций, что вполне приемлемо для практического применения.

Глава 5. Комбинаторные оценки полного скользящего контроля

§5.1. Функционал полного скользящего контроля (ССУ) определяется как средняя частота ошибок на контроле по всевозможным разбиениям генеральной выборки:

ССУ0и,Х) = ^£ и(мХ,Х).

1 (Х,х)

В терминах слабой аксиоматики ССУ есть математическое ожидание частоты ошибок на контроле, ССУ = X).

Недостаток ССУ в том, что он ничего не говорит о возможном разбросе (дисперсии) частоты ошибок р{цХ,Х). Поэтому его нельзя использовать для получения верхних оценок.

§5.2. Рассматриваются задачи классификации с множеством классов ¥. Индикатор ошибки имеет вид 1(а, х) = \у(х) ф а(х)], где у: X —> У — восстанавливаемая зависимость, а: X —> ¥ — алгоритм классификации. Решение задач классификации часто основано на гипотезе компактности — эмпирическом предположении, что классы образуют локализованные «компактные» подмножества объектов, и схожие объекты, как правило, лежат в одном классе. Простейшим методом обучения, построенным на его основе, является метод ближайших соседей.

§5.2.1. Пусть на множестве X определена функция расстояния р(х, х'). Метод ближайшего соседа — это метод обучения ц, который запоминает обучающую выборку X С X и строит алгоритм а = ¡лХ, работающий следующим образом:

а(х;Х) = у(&щттр(х, х')) для всех х € X.

Для каждого объекта х^ г = 1,..., Ь выборки X расположим остальные Ь — 1 объектов в порядке возрастания расстояния до Хг, пронумеровав их двойными индексами: хг = хг0) хц, Хг2, ■ ■ ■, £¿,2,-1. Таким образом,

О = /э(ж», Жю) ^ р(хи хп) ^ • • • ^ р(Хг, £*,£-].).

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

Гт(Хг) = [у(Хг) ф у(хШ)] ] I = 1, . . . , Ц ГП = 1, . . . , Ь - 1.

Определение 5.1. Профилем компактности выборки X называется доля объектов выборки, для которых правильный ответ не совпадает с правильным ответом на т-ом соседе:

1 г-

К(т, X) = — ^ гт(хг)\ т = 1,...,Ь-1.

г—1

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

§5.2.2. Существует связь профиля компактности с качеством классификации методом ближайшего соседа.

Теорема 5.2. Для метода ближайшего соседа ^ и любой X

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

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

Предлагается итерационный процесс минимизации ССУ путём последовательного отсева неэталонных объектов. Эксперименты на модельных данных показывают, что в этом процессе сначала удаляются все шумовые выбросы, при этом функционал ССУ убывает. Затем удаляются неинформативные «внутренние» объекты классов, при этом функционал либо не изменяется, либо увеличивается на ничтожно малую величину. Когда функционал начинает заметно возрастать, процесс уда-

(25)

Комбинаторный множитель 7т = С\

Ь—1-771

/С£_1 убывает с ро-

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

§5.3. Рассматриваются задачи классификации, в которых множество X частично упорядочено, ¥ = {0,1}, индикатор ошибки имеет вид 1(а,х) = [у(х) ф а(з)], и имеется априорная информация о монотонности или почти-монотонности целевой зависимости у(х). Ограничения монотонности могут возникать в различных контекстах. Во-первых, они могут быть результатом формализации экспертных знаний вида «чем больше значение признака /(ж) тем больше значение у(х)». Во-вторых, они возникают в алгоритмических композициях с нелинейной корректирующей операцией, которые являются естественным обобщением линейных выпуклых композиций (взвешенного голосования) алгоритмов классификации.

Допустим, что метод обучения ¡1 выбирает алгоритмы из множества А всех монотонных отображений Р: X —> ¥.

Степеныо немонотонности выборки X называется наименьшая частота ошибок, допускаемых на ней монотонными алгоритмами: #(Х) = шш и(а,Х).

Выборка X называется монотонной, если из х^ ^ х^ следует у(х{) ^ у(х^) для всех г, з — 1,..., Ь. Выборка монотонна тогда и только тогда, когда в(Х) — 0.

Верхним и нижним клином объекта Хг £ X называются, соответственно, множества

Жз(^г) = {х £ X: Жг < х и у(х) — 0} ;

И^г) = {х £ X: X < Хг И у(х) = 1} .

Введём сокращённое обозначение Ж; = №у(х.)(х{).

Мощность клина г^ = (И7^ характеризует глубину погружения объекта х{ в тот класс, которому он принадлежит. Чем меньше ги^, тем ближе объект к границе класса. Объекты, не имеющие своего клина (го* — 0) будем называть граничными.

Определение 5.5. Профилем монотонности выборки X называется функция М(т, X), выражающая долю объектов выборки с клином мощности т:

1 Ь

М(т, X) — — = т]; т = 0, 1.

¿=1

Теорема 5.4. Если метод д минимизирует эмпирический риск в классе всех монотонных функций и степень немонотонности выборки X равна в, то

вЬ+к-1 тт{0Ь,С,т}

ССУ(м,Х)< £ м<го«х) Е V"1""1' (2б)

т=0 з=тах{0,т-А:-Н} 1,-1

Оценка (26) монотонно не убывает по в, достигая наименьшего значения при # = 0, когда выборка монотонна и метод ц является корректным на генеральной выборке X:

ССУМ < (27)

т=0

Оценка (26), в отличие от завышенных сложностных оценок, никогда не превышает 1. Наибольшее значение 1 достигается при 0^ = 0, г = 1,..., Ь. Это тот случай, когда оба класса состоят из попарно несравнимых объектов, и вся выборка распадается на две антицепи. Наименьшее значение достигается, когда выборка монотонна и линейно упорядочена. Тогда ССУ ^ 2/1.

Комбинаторный множитель в (26) убывает с ростом т быстрее геометрической прогрессии. Чтобы обеспечить малое значение функционала ССУ, достаточно потребовать, чтобы функция М(т, X) принимала малые значения при малых т. При больших т её рост компенсируется комбинаторным множителем. Таким образом, качество монотонного классификатора тем выше, чем меньше объектов имеют клинья небольшой мощности. Для этого отношение порядка на множестве объектов X должно быть близко к линейному вблизи границы классов.

Интересно отметить структурное сходство оценок (25) и (27), полученных для таких различных, на первый взгляд, априорных ограничений, как компактность и монотонность.

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

[1] Воронцов К. В. Качество восстановления зависимостей по эмпирическим данным // Математические методы распознавания образов: 7-ая Всерос. конф. Тезисы докл. — Пущино, 1995. — С. 24-26.

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

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

[4] Воронцов К. В. Оценка качества монотонного решающего правила вне обучающей выборки // Интеллектуализация обработки информации: Тез. докл. — Симферополь, 2002. — С. 24-26.

[5] Воронцов К, В. О комбинаторном подходе к оценке качества обучения алгоритмов // Математические методы распознавания образов: 11-ая Всерос. конф. Тезисы докл. — Пущино, 2003. — С. 47-49.

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

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

[8] Воронцов К. В. Комбинаторные оценки качества обучения по прецедентам // Доклады РАН.- 2004,- Т. 394, № 2. С. 175-178.

[9] Воронцов К. В. Обзор современных исследований по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. — 2004. — № 1. — С. 5-24.

[10] Воронцов К. В. Комбинаторный подход к повышению качества логических классификаторов // Интеллектуализация обработки информации: Тезисы докл. — Симферополь, 2004. — С. 44.

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

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

[13] Воронцов К. В., Колосков А. О. Профили компактности и выделение опорных объектов в метрических алгоритмах классификации // Искусственный Интеллект. — 2006. — С. 30-33.

[14] Воронцов К. В. Слабая вероятностная аксиоматика и надёжность эмпирических предсказаний // Докл. всеросс. конф. Ма-

тематические методы распознавания образов-13. — М.: МАКС Пресс, 2007. - С. 21-25.

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

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

[17] Венжега А. В., Умептаев С. А., Орлов А. А., Воронцов К. В. Проблема переобучения при отборе признаков в линейной регрессии с фиксированными коэффициентами // Докл. всеросс. конф. Математические методы распознавания образов-13. - М.: МАКС Пресс, 2007. - С. 90-93.

[18] Ульянов Ф. М., Воронцов К. В. Проблема переобучения функций близости при построении алгоритмов вычисления оценок // Докл. всеросс. конф. Математические методы распознавания образов-13. - М.: МАКС Пресс, 2007. - С. 105-108.

[19] Воронцов К. В., Инякин А. С., Лисица А. В. Система эмпирического измерения качества алгоритмов классификации // Докл. всеросс. конф. Математические методы распознавания образов-13. - М.: МАКС Пресс, 2007,- С. 577-580.

[20] Цюрмасто П. А., Воронцов К. В. Анализ сходства алгоритмов классификации в оценках обобщающей способности // Интеллектуализация обработки информации (ИОИ-2008): Тез. докл. - Симферополь: КНЦ НАН Украины, 2008. - С. 232-234.

[21] Vorontsov К. V. On the influence of similarity of classifiers on the probability of overfitting // Pattern Recognition and Image Analysis: new information technologies (PRIA-9).— Vol. 2.—

Nizhni Novgorod, Russian Federation, 2008. - Pp. 303-306.

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

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

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

[25] Воронцов К. В. Методы машинного обучения, основанные на индукции правил // Труды семинара «Знания и онтологии ELSEWHERE 2009», ассоциированного с 17-й международной конференцией по понятийным структурам ICCS-17, Москва, 21-26 июля. — Высшая школа экономики, 2009. — С. 57-71.

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

[27] Иванов М. Н., Воронцов К. В. Отбор эталонов, основанный на минимизации функционала полного скользящего контроля // Докл. всеросс. конф. Математические методы распознавания образов-14. - М.: МАКС Пресс, 2009. - С. 119-122.

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

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 05.03.2010 г. Формат 60x90 1/16. Усл.печ.л. 2,0. Тираж 150 экз. Заказ 092. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

1 Слабая вероятностная аксиоматика

1.1 Основная аксиома.

1.1.1 Задачи эмпирического предсказания.

1.1.2 Обращение оценок.

1.1.3 Наблюдаемые и ненаблюдаемые оценки

1.1.4 Эмпирическое оценивание вероятности.

1.1.5 Замечания и интерпретации.

1.2 Задача оценивания частоты события.

1.2.1 Свойства гипергеометрического распределения.

1.2.2 Закон больших чисел в слабой аксиоматике.

1.2.3 Проблема неизвестного т и наблюдаемые оценки.

1.3 Задача оценивания функции распределения.

1.3.1 Усечённый треугольник Паскаля

1.3.2 Теорема Смирнова в слабой аксиоматике.

1.3.3 Обобщение на случай вариационного ряда со связками.

1.4 Некоторые непараметрические критерии и доверительные оценки

1.4.1 Доверительное оценивание.

1.4.2 Доверительные интервалы для квантилей.

1.4.3 Критерий знаков.

1.4.4 Критерий Уилкоксона-Манна-Уитни.

1.5 Задача оценивания вероятности переобучения.

1.5.1 Основные понятия и определения.

1.5.2 Простой частный случай: один алгоритм.

1.5.3 Коэффициенты разнообразия и профиль расслоения.

1.5.4 Принцип равномерной сходимости и VC-оценка.

1.5.5 Степень некорректности и её влияние на переобучение.

1.5.6 Проблема завышенное™ VC-оценок.

1.5.7 Причины завышенное™ VC-оценок.

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

Актуальность темы. Вопрос о качестве восстановления зависимостей по эмпирическим данным является фундаментальной проблемой теории статистического обучения1 (statistical learning theory, SLT).

Основным объектом исследования в SLT является задача обучения по прецедентам: задана обучающая выборка пар «объект-ответ»; требуется восстановить функциональную зависимость ответов от объектов, т. е. построить алгоритм, способный выдавать адекватный ответ для произвольного объекта. К этому классу задач относятся задачи распознавания образов, классификации, восстановления регрессии, прогнозирования.

Основной задачей SLT является получение оценок вероятности ошибки построенного алгоритма на объектах, не входивших в обучающую выборку. Эта задача нетривиальна, поскольку частота ошибок на обучающей выборке, как правило, является смещённой (сильно заниженной) оценкой вероятности ошибки. Это явление называют переобучением (overfitting). Способность алгоритмов восстанавливать неизвестную зависимость по конечной выборке данных называют обобщающей способностью (generalization ability).

1 Второе название—теория вычислительного обучения (computational learning theory, COLT). Различия между COLT и SLT, по мнению автора, незначительны и довольно условны. В частности, COLT включает в себя проблематику вычислительной эффективности алгоритмов обучения.

Возникновение БЬТ связывают с появлением в начале 70-х годов статистической теории Вапника-Червоненкиса (далее УС-теория), которая получила широкую мировую известность и признание в середине 80-х [12, 13, 14, 11, 218]. В настоящее время ЭКГ продолжает активно развиваться, постоянно появляются новые направления исследований и новые приложения.

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

Основной проблемой УС-теории является сильная завышенность оценок вероятности ошибки. Попытка их практического применения приводит либо к требованию явно избыточного наращивания обучающей выборки, либо к переупрощению семейства алгоритмов. Наиболее интересные случаи — малых выборок и сложных семейств — находятся за границами применимости УС-теории. В частности, сложные алгоритмические композиции на практике могут обеспечивать высокое качество классификации, даже когда УС-оценка вероятности ошибки равна единице. Примерами таких конструкций являются корректные линейные и алгебраические композиции алгоритмов вычисления оценок [48, 49, 50, 51]. Нетривиальные оценки вероятности ошибки для таких композиций были получены В. Л. Матросовым в серии работ [66, 67, 68, 69, 70, 71]. Однако эти оценки также были сильно завышены, поскольку опирались на УС-теорию. Намного позже широкое распространение получили методы обучения линейных композиций — бустинг [135, 136] и бэггинг [117, 119]. Их статистические обоснования были получены в [199] с помощью техники, разработанной П. Бартлеттом в [104, 100]. Было показано, что верхние оценки вероятности ошибки не зависят от числа базовых алгоритмов в композиции, а только от сложности семейства базовых алгоритмов. Эти оценки опираются на усовершенствованный вариант УС-теории, но также не являются численно точными и дают лишь качественное обоснование линейных композиций, включая бустинг, многослойные нейронные сети и машины опорных векторов.

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

Дальнейшее развитие БЬТ шло по пути повышения точности оценок с учётом индивидуальных особенностей задач и методов обучения. Большое разнообразие исследований в БШ за последние 40 лет связано с неоднозначностью ответов на вопросы: какие именно характеристики задачи, семейства алгоритмов и метода обучения наиболее существенны, и в то же время достаточно удобны для практического оценивания и управления качеством алгоритма в процессе его обучения.

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

Основная трудность в том, что обучение — это оптимизационная процедура, которая способна аппроксимировать не только интересующую нас зависимость, но и ошибки измерения исходных данных, и погрешности модели. Величина смещения может зависеть от различных особенностей обучающей выборки и метода обучения; каких именно — до конца не ясно. Предлагалось учитывать сложность семейства алгоритмов (УС-теория), локальную сложность [202, 226, 169, 112, 113, 167, 106], устойчивость обучения [115, 116, 166], ширину зазора, разделяющего классы [159, 105, 94, 96], оценки скользящего контроля [154, 158, 147], априорную информацию о восстанавливаемой зависимости [91, 209].

Современные оценки основаны, главным образом, на теории эмпирических процессов [212, 162] и неравенствах концентрации вероятностной меры [183, 213, 175, 114, 93, 111]. Несмотря на развитость этих математических техник, они обладают рядом существенных недостатков: в процессе вывода верхних оценок практически невозможно проконтролировать, на каком именно шаге происходит основная потеря точности оценки; в результате трудно выделить истинные причины завышенности; автору не известны работы, в которых устранялись бы одновременно все причины завышенности классических VC-оценок; по всей видимости, сделать это с помощью известных техник очень трудно; наиболее точные на сегодняшний день результаты основаны на байесовском подходе [182, 167, 196], оставляющем значительный произвол при задании априорных распределений; задаются они, как правило, исходя из субъективных и довольно искусственных соображений, а анализ устойчивости оценок относительно априорных распределений практически никогда не производится.

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

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

Научная новизна. До сих пор вопрос о получении точных оценок (exact bounds) вероятности переобучения в SLT даже не ставился. Задача считалась безнадёжной, и обычно речь шла лишь о получении «слабо завышенных» оценок (tight bounds). Для получения точных оценок приходится отказываться от стандартного инструментария SLT — завышенных неравенств Маркова, Хёфдинга, Чернова, МакДиармида, Буля, и др. Комбинаторный подход требует радикального пересмотра всей теории, начиная с аксиоматики.

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

Методы исследования. Вместо завышенных функционалов равномерного отклонения, введённых в УС-теории и применяемых в БЬТ до сих пор, вводится более точный функционал вероятности переобучения, зависящий от задачи и метода обучения, и основанный на принципе полного скользящего контроля.

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

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

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

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

Теоретическая значимость. В настоящее время в теории обобщающей способности наметилась стагнация. Ценой существенного усложнения математического аппарата удаётся добиться лишь незначительного повышения точности оценок. Интерес научного сообщества к проблематике оценок обобщающей способности заметно снизился в последние годы, сместившись к байесовской теории обучения и решению новых типов прикладных задач. Тем временем остаются открытыми фундаментальные проблемы — как преодолеть завышенность оценок, и как их использовать на практике для управления процессом обучения. Сложившаяся ситуация не раз повторялась в истории науки: очевидно, что для дальнейшего развития теории требуются радикально новые идеи и подходы. Данная работа является попыткой выхода из тупика.

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

Область исследования согласно паспорту специальности 05.13.17—«Теоретические основы информатики»: разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных (п. 5); моделирование формирования эмпирического знания (п. 7); разработка методов обеспечения высоконадежной обработки информации (п. 11).

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

Апробация работы. Результаты работы неоднократно докладывались на научных семинарах ВЦ РАН и на конференциях: всероссийская конференция «Математические методы распознавания образов» ММРО-7, 1995 г. [18]; международная конференция «Интеллектуализация обработки информации» ИОИ-4, 2002 г. (21); всероссийская конференция «Математические методы распознавания образов» ММРО-11, 2003 г. [22]; международная конференция «Интеллектуализация обработки информации» ИОИ-5, 2004 г. [26]; всероссийская конференция «Математические методы распознавания образов» ММРО-12, 2005 г. [63]; международная конференция «Интеллектуализация обработки информации» ИОИ-6, 2006 г. [32, 35]; всероссийская конференция «Математические методы распознавания образов» ММРО-13, 2007 г. [28, 64, 57, 15, 84, 34];

7-й открытый немецко-российский семинар «Распознавание образов и понимание изображений», Эттлпнген, Германия, 20-25 августа 2007 г. [222]; ломоносовские чтения, МГУ, 17 апреля, 2008 г.; международная конференция «Интеллектуализация обработки информации» ИОИ-7, 2008 г. [88]; международная конференция «Распознавание образов и анализ изображений: новые информационные технологии» РОАИ-9, Нижний Новгород, 2008 г. [223]; международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В. А. Садовничего, Москва, 30 марта-2 апреля 2009 г.; семинар «Знания и онтологии ELSEWHERE 2009», ассоциированный с 17-й международной конференцией по понятийным структурам ICCS-17, Москва, Высшая школа экономики, 21-26 июля 2009 г.; всероссийская конференция «Математические методы распознавания образов» ММРО-14, 2009 г. [29, 56, 33].

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

Полный текст диссертации доступен на персональной странице автора: http://www.MachineLearning.ru/wiki/index.php?title=y4acTHHK:Vokov.

Публикации по теме диссертации в изданиях списка ВАК: [79, 20, 25, 23, 24, 222, 224, 31]. Другие публикации по теме диссертации: [18, 21, 22, 27, 26, 63, 32, 35, 28, 57, 64, 15, 84, 34, 88, 223, 29, 56, 33]. Отдельные результаты включались в отчёты по проектам РФФИ 01-07-90242, 02-01-00325, 02-01-00326, 04-07-90290, 05-01-00877, 05-07-90410, 08-07-00422, по программам ОМН РАН «Алгебраические и комбинаторные методы математической кибернетики» и «Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения», по программе президиума РАН «Интеллектуальные информационные технологии, математическое моделирование, системный анализ и автоматизация».

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

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

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

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

В главе 3 описывается методика экспериментального количественного измерения факторов завышенности УС-оценок. В рамках УС-теории измерение функционала равномерной сходимости наталкивается на значительные трудности. Однако после перехода в слабую аксиоматику и замены его функционалом вероятности переобучения измерение становится возможным. Эксперимент с логическими алгоритмами классификации на реальных задачах из репозитория ИС1 показывает, что среди всех факторов завышенности наиболее существенны два — это игнорирование таких важных свойств семейства алгоритмов, как расслоение и связность. Расслоение возникает вследствие универсальности применяемых на практике семейств. Как правило, лишь ничтожная доля алгоритмов в семействе подходит для решения данной конкретной задачи. Именно эти алгоритмы имеют наиболее высокие шансы быть полученными в результате обучения. Распределение вероятностей на множестве алгоритмов существенно неравномерно, однако этот факт никак не учитывается классическими УС-оценками. Связность возникает вследствие непрерывности применяемых на практике семейств. Как правило, для любого алгоритма в семействе находится большое число похожих на него алгоритмов. Однако классические УС-оценки ориентированы на «худший случай», когда все алгоритмы существенно различны, что почти невероятно встретить на практике. Второй эксперимент на модельных данных подтверждает необходимость совместного учёта эффектов расслоения и связности. Рассматривается простейшее семейство с расслоением и связностью — монотонная цепочка алгоритмов. Его естественные модификации, не обладающие либо расслоением, либо связностью, сильно переобучаются уже при нескольких десятках алгоритмов в семействе. Третий эксперимент проводится на двухэлементном семействе и показывает, что даже в этом простейшем случае появляется переобучение, а эффекты расслоения и сходства снижают вероятность переобучения.

В главе 4 предлагается несколько способов получения точных оценок вероятности переобучения. Первый способ основан на понятиях порождающих и запрещающих множеств объектов. Порождающее множество — это те объекты, которые обязательно должны присутствовать в обучающей выборке, чтобы данный алгоритм был выбран данным методом обучения. Запрещающее множество — это те объекты, которых не должно быть в обучающей выборке, чтобы данный алгоритм был выбран. Доказывается, что порождающие и запрещающие множества можно указать всегда, а коли они указаны, можно выписать точные формулы вероятности переобучения. Второй способ основан на разбиении генеральной выборки на блоки; соответствующие оценки эффективны только при малом числе алгоритмов в семействе. Третий способ основан на гипотезе, что множество векторов ошибок рассматриваемого семейства алгоритмов образует интервал булева куба. Четвёртый способ основан на рекуррентных формулах, позволяющих корректировать порождающие и запрещающие множества при добавлении в семейство ещё одного алгоритма. Доказано, что путём некоторого упрощения рекуррентной процедуры можно получать и верхние, и нижние оценки вероятности переобучения. При этом точность оценок можно обменивать на время вычислений. При самом простом варианте рекуррентной процедуры верхние оценки выписываются в явном виде. Они похожи на УС-оценки, но содержат «поправку на связность», экспоненциально убывающую с ростом размерности семейства. Вводятся новые понятия профиля расслоения и профиля связности семейства алгоритмов, и некоторые их свойства исследуются экспериментально.

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

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

Благодарности. Автор признателен своему учителю члену-корреспонденту РАН Константину Владимировичу Рудакову за внимание и интерес к работе, академику РАН Юрию Ивановичу Журавлёву за советы и поддержку, аспирантам и студентам Денису Кочедыкову, Андрею Ивахненко, Илье Решетняку, Александру Фрею, Павлу Ботову, Ивану Гузу, Максиму Иванову, Анастасии Зухба за плодотворные дискуссии, экспериментальную работу и дальнейшее развитие комбинаторного подхода.

5.4 Основные выводы

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

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

3. Для задач классификации с априорными ограничениями монотонности (или по-чти-монотонности) целевой зависимости вводится понятие профиля монотонности выборки. Доказываются слабо завышенные верхние оценки функционала ССУ. Описывается метод построения монотонных корректирующих операций, оптимизирующий полученную верхнюю оценку.

Заключение

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

1. Слабая вероятностная аксиоматика, основанная на единственном вероятностном предположении — о независимости наблюдений в конечной выборке. Общая постановка задач эмпирического предсказания.

2. УС-оценки вероятности переобучения, учитывающие степень некорректности метода обучения.

3. Методика эмпирического измерения факторов завышенности УС-оценок вероятности переобучения.

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

5. Рекуррентный алгоритм вычисления точных, верхних и нижних оценок вероятности переобучения.

6. Блочный метод вычисления точных оценок вероятности переобучения.

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

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

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

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

Направления дальнейших исследований.

• Уточнение границ применимости слабой вероятностной аксиоматики.

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

• Получение точных или слабо завышенных оценок вероятности переобучения для реальных семейств в случаях «наихудших» и «типичных» выборок.

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

1. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.

2. Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. — М.: Наука, 1970. — 320 рр.

3. Алимов Ю. И. Альтернатива методу математической статистики. — Знание, 1980.

4. Асарин Е. А. О некоторых свойствах Д-случайных по Колмогорову конечных последовательностей // Теория вероятностей и её применения.— 1987.— Т. 32, № 3.— С. 556-558.

5. Асарин Е. А. О некоторых свойствах случайных в алгоритмическом смысле конечных объектов // ДАН СССР. 1987. - Т. 295, № 4. - С. 782-785.

6. Асарин Е. А. Индивидуальные случайные сигналы: Сложпостпый подход. — Диссертация на соискание учёной степени к.ф.-м.н. — 1988.

7. Беляев Ю. К. Вероятностные методы выборочного контроля.— М.: Наука, 1975.

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

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

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

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

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

13. Венжега А. В., Умептаев С. А., Орлов А. А., Воронцов К. В. Проблема переобучения при отборе признаков в линейной регрессии с фиксированными коэффициентами // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 90-93.

14. Вероятность и математическая статистика: Энциклопедия / Под ред. Ю. В. Прохорова.— М.: Большая российская энциклопедия, 2003.

15. Вовк В. Г., Шейфер Г. Р. Вклад А. Н. Колмогорова в основания теории вероятностей // Проблемы передачи информации. — 2003. — Т. 39, № 1. — С. 24-35.

16. Воронцов К. В. Качество восстановления зависимостей по эмпирическим данным // Математические методы распознавания образов: 7-ая Всерос. конф. Тезисы докл. — Пущино, 1995. — С. 24-26.

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

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

19. Воронцов К. В. Оценка качества монотонного решающего правила вне обучающей выборки // Интеллектуализация обработки информации: Тезисы докл. — Симферополь, 2002.— С. 24-26.

20. Воронцов К. В. О комбинаторном подходе к оценке качества обучения алгоритмов // Математические методы распознавания образов: 11-ая Всерос. конф. Тезисы докл. — Пущино, 2003,— С. 47-49.

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

22. Воронцов К. В. Комбинаторные оценки качества обучения по прецедентам // Докл. РАН. 2004. - Т. 394, № 2. — С. 175-178.

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

24. Воронцов К. В. Комбинаторный подход к повышению качества логических классификаторов // Интеллектуализация обработки информации: Тезисы докл. — Симферополь, 2004. — С. 44.

25. Воронцов К. В. Обзор современных исследований по проблеме качества обучения алгоритмов // Таврический вестник информатики и мателштики. — 2004. — JVS 1. — С. 5-24.

26. Воронцов К. В. Слабая вероятностная аксиоматика и надёжность эмпирических предсказаний // Математические методы распознавания образов-J 3.— М.: МАКС Пресс, 2007.- С. 21-25.

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

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

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

30. Воронцов К. В., Инякин А. С., Лисица А. В. Система эмпирического измерения качества алгоритмов классификации // Математические методы распознавания образов-13. М.: МАКС Пресс, 2007. - С. 577-580.

31. Воронцов К. В., Колосков А. О. Профили компактности и выделение опорных объектов в метрических алгоритмах классификации // Искусственный Интеллект. — 2006. С. 30-33.

32. Гаек Я., Шидак 3. Теория ранговых критериев.— М.: Наука, 1971. Головко В. А. Нейронные сети: обучение, организация и применение. — М.: ИПРЖР, 2001.

33. Дуда Р., Хартп П. Распознавание образов и анализ сцен.— М.: Мир, 1976. Дэйвид Г. Порядковые статистики. — М.: Наука, 1979. — 336 с.

34. Дюличева Ю. Ю. Оценка VCD r-редуцированного эмпирического леса // Таврический вестник информатики и математики. — 2003. — № 1. — С. 31-42. Журавлёв Ю. И. Непараметрические задачи распознавания образов // Кибернетика. — 1976. — № 6.

35. Журавлёв Ю. И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // Доклады АН СССР. Математика.— 1976.— Т. 231, № 3.

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

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

38. Иванов М. Н., Воронцов К. В. Отбор эталонов, основанный на минимизации функционала полного скользящего контроля // Всеросс. копф. Математические методы распознавания образов-14. — М.: МАКС Пресс, 2009,— С. 119-122.

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

40. Катериночкина Н. Н. Методы выделения максимальной совместной подсистемы системы линейных неравенств. Сообщение по прикладной математике. — Москва: Вычислительный центр РАН, 1997.

41. Кобзарь А. И. Прикладная математическая статистика.— М.: Физматлит, 2006.

42. Колмогоров А. Н. Комбинаторные основания теории информации и исчисления вероятностей // Успехи математических наук. — 1983. — Т. 38, № 4. — С. 27—36.

43. Колмогоров А. Н. Теория информации и теория алгоритмов / Под ред. Ю. В. Прохоров. — М.: Наука, 1987. — 304 с.

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

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

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

47. Матросов В. Л. Корректные алгебры ограниченной ёмкости над множествами некорректных алгоритмов // ДАН СССР. — 1980. — Т. 253, № 1. — С. 25-30.

48. Матросов В. Л. О критериях полноты модели алгоритмов вычисления оценок и её алгебраических замыканий // ДАН СССР. — 1981. — Т. 258, № 4. — С. 791-796.

49. Матросов В. Л. Оптимальные алгоритмы в алгебраических замыканиях операторов вычисления оценок // ДАН СССР. — 1982. — Т. 262, № 4. — С. 818-822.

50. Матросов В. Л. Емкость алгебраических расширений модели алгоритмов вычисления оценок // ЖВМиМФ. — 1984. — Т. 24, № 11, — С. 1719-1730.

51. Матросов В. Л. Нижние границы ёмкости многомерных алгебр алгоритмов вычисления оценок // ЖВМиМФ. — 1984. — Т. 24, № 12, — С. 1881-1892.

52. Матросов В. Л. Емкость алгоритмических многочленов над множеством алгоритмов вычисления оценок // ЖВМиМФ. — 1985. — Т. 25, № 1. — С. 122-133.

53. Минский М., Пайперт С. Персепроны. — М.: Мир, 1971.

54. Нейроинформатика / А. Н. Горбань, В. Л. Душш-Барковский, А. Н. Кирдин, Е. М. Миркес, А. Ю. Новоходько, Д. А. Россиев, С. А. Терехов и др. — Новосибирск: Наука, 1998. — 296 с.

55. Норушис А. Построение логических (древообразных) классификаторов методами нисходящего поиска (обзор) // Статистические проблемы управления. Вып. 93 / Под ред. Ш. Раудис. Вильнюс, 1990. — С. 131-158.

56. Орлов А. И. Эконометрика: Учебник для вузов, — М.: Экзамен, 2003.— 576 с.

57. Орлов А. И. Нечисловая статистика.— М.: МЗ-Пресс, 2004.

58. Райгородский А. М. Экстремальные задачи теории графов и анализ данных. — М.: НИЦ «Регулярная и хаотическая динамика», Институт компьютерных исследований, 2008, — 118 с.

59. Растригин Л. А., Эренштейн Р. X. Коллективные правила распознавания.— М.: Энергия, 1981. — 244 рр.

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

61. Рязанов В. В., Сенько О. В. О некоторых моделях голосования и методах их оптимизации // Распознавание, классификация, прогноз.— 1990. — Т. 3. — С. 106-145.

62. Сёмочкин А. Н. Линейные достроения частичного порядка на конечных множествах // Деп. в ВИНИТИ. — 1998. — № 2964-В98. — С. 19.

63. Сёмочкин А. Н. Оценки функционала качества для класса алгоритмов с универсальными ограничениями монотонности // Деп. в ВИНИТИ.— 1998.— № 2965-В98.— С. 20.

64. Смирнов Н. В. Оценка расхождения между эмпирическими кривыми распределения в двух независимых выборках // Вюлл. Московского ун-та, серия А. — 1939. — № 2.— С. 3-14.

65. Ульянов Ф. М., Воронцов К. В. Проблема переобучения функций близости при построении алгоритмов вычисления оценок // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 105-108.

66. Успенский В. А. Четыре алгоримтических лица случайности. — М.: Изд-no МЦНМО, 2009. 48 с.

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

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

69. Цюрмасто П. А., Воронцов К. В. Анализ сходства алгоритмов классификации в оценках обобщающей способности // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ HAH Украины, 2008. — С. 232-234.

70. Шень А. X. Частотный подход к определению понятия случайной последовательности // Семиотика и информатика. — М.: ВИНИТИ, 1982. — Т. 18. — С. 14-42.

71. Эфрон Б. Нетрадиционные методы многомерного статистического анализа. — М: Финансы и статистика, 1988.

72. Abu-Mostafa Y. S. Hints // Neural Computation. — 1995, — Vol. 7, no. 4. — Pp. 639-671.

73. Ambroladze A., Parrado-Hernández E., Shawe-Taylor J. Tighter РАС-Bayes bounds // Advances in Neural Information Processing Systems 19 / Ed. by B. Schölkopf, J. Piatt, T. Hoffman. — Cambridge, MA: MIT Press, 2007. — Pp. 9-16.

74. Anthony M. Uniform glivenko-cantelli theorems and concentration of measure in the mathematical modelling of learning: Tech. Rep. LSE-CDAM-2002-07: 2002.

75. Anthony M., Bartlett P. L. Neural Network Learning: Theoretical Foundations. — Cambridge University Press, Cambridge, 1999.

76. Anthony M., Shawe-Taylor J. A result of Vapnik with applications // Discrete Applied Mathematics. 1993. — Vol. 47, no. 2. — Pp. 207-217.

77. Antos A., Kegl B., Linder T., Lugosi G. Data-dependent margin-based generalization bounds for classification // Journal of Machine Learning Research. — 2002. — Pp. 73-98.

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

79. Audibert J.-Y. PAC-Bayesian Statistical Learning Theory: Ph.D. thesis / Laboratoire de Probabilities et Modèles Aléatoires, Universités Paris 6 and Paris 7. — 2004.

80. Bartlett P. Lower bounds on the Vapnik-Chervonenkis dimension of multi-layer threshold networks // Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory. — ACM Press, New York, NY, 1993. — Pp. 144-150.

81. Bartlett P. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network // IEEE Transactions on Information Theory. — 1998. —Vol. 44, no. 2, — Pp. 525-536.

82. Bartlett P., Bousquet O., Mendelson S. Localized rademacher complexities // COLT: 15th Annual Conference on Computational Learning Theory. — Springer, Berlin, 2002. — Pp. 44-58.

83. Bartlett P., Bousquet O., Mendelson S. Local rademacher complexities.— Vol. 33.— Institute of Mathematical Statistics, 2005. — P. 1497-1537.

84. Bartlett P., Shawe-Taylor J. Generalization performance of support vector machines and other pattern classifiers // Advances in Kernel Methods.— MIT Press, Cambridge, USA, 1999. — Pp. 43-54.

85. Bartlett P. L., Long P. M., Williamson R. C. Fat-shattering and the learnability of real-valued functions // Journal of Computer and System Sciences. — 1996. — Vol. 52, no. 3. — Pp. 434-452.

86. Bartlett P. L., Mendelson S., Philips P. Local complexities for empirical risk minimization // COLT: 17th Annual Conference on Learning Theory / Ed. by J. Shawe

87. Breiman L. Bagging predictors // Machine Learning. — 1996. — Vol. 24, no. 2. — Pp. 123140.

88. Breiman L. Bias, variance, and arcing classifiers: Tech. Rep. 460: Statistics Department, University of California, 1996.

89. Breiman L. Arcing classifiers // The Annals of Statistics.— 1998.— Vol. 26, no. 3.— Pp. 801-849.

90. Breiman L., Friedman J., Stone C. J., Olshen R. A. Classification and Regression Trees. —

91. Belmont, California, U.S.A.: Wadsworth Publishing Company, 1984.

92. Burges C. J. G. A tutorial on support vector machines for pattern recognition // Data

93. Mining and Knowledge Discovery. — 1998. — Vol. 2, no. 2. — Pp. 121-167.

94. Chernoff H. A measure of asymptotic efficiency for tests of a hypothesis based on the sumof observations // Annals of Math. Stat. — 1952. — Vol. 23. — Pp. 493-509.

95. Chvatal V. The tail of the hypergeometric distribution // Discrete Mathematics. — 1979. — Vol. 25, no. 3. — Pp. 285-287.

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

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

98. Cortes C., Vapnik V. Support-vector networks // Machine Learning.— 1995.— Vol. 20, no. 3. — Pp. 273-297.

99. Devroye L. P., Wagner T. J. Distribution-free inequalities for the deleted and holdout error estimates // IEEE Transactions on Information Theory. — 1979. — Vol. 25, no. 2.— Pp. 202-207.

100. Devroye L. P., Wagner T. J. Distribution-free performance bounds for potential function rules // IEEE Transactions on Information Theory. — 1979. — Vol. 25, no. 5. — Pp. 601604.

101. Efron B. The Jackknife, the Bootstrap, and Other Resampling Plans. — SIAM, Philadelphia, 1982.

102. Elisseeff A., Evgeniou T., Pontil M. Stability of randomized learning algorithms // Journal of Machine Learning Research. — 2005. — no. 6. — Pp. 55-79.

103. Evgeniou T., Pontil M., Elisseeff A. Leave one out error, stability, and generalization of voting combinations of classifiers: Tech. Rep. 2001-21-TM: INSEAD, 2001.

104. Freund Y. Boosting a weak learning algorithm by majority // COLT: Proceedings of the Workshop on Computational Learning Theory. — Morgan Kaufmann Publishers, 1990.

105. Freund Y. Self bounding learning algorithms // COLT: Proceedings of the Workshop on Computational Learning Theory, Morgan Kaufmann Publishers. — 1998.

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

107. Freund Y., Schapire R. E. Experiments with a new boosting algorithm // International Conference on Machine Learning.— 1996. — Pp. 148-156.

108. Freund Y., Schapire R. E. Discussion of the paper "Arcing classifiers" by Leo Breiman // The Annals of Statistics. — 1998. — Vol. 26, no. 3. — Pp. 824-832.

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

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

111. Germain P., Laçasse A., Laviolette F., Marchand M. A PAC-Bayes risk bound for general loss functions // Advances in neural information processing systems. — 2007. — no. 19. — Pp. 449-456.

112. Germain P., Laçasse A., Laviolette F., Marchand M. PAC-Bayesian learning of linear classifiers // ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning. — ACM, 2009. — Pp. 353-360.

113. Golea M., Bartlett P., Lee W. S., Mason L. Generalization in decision trees and DNF: Does size matter? // Advances in Neural Information Processing Systems / Ed. by M. I. Jordan, M. J. Kearns, S. A. Solla. — Vol. 10. — The MIT Press, 1998.

114. Grove A. J., Schuurmans D. Boosting in the limit: Maximizing the margin of learned ensembles // AAAI/IAAI. — 1998. — Pp. 692-699.

115. Hebb D. The organization of behavior. — New York: Wiley, 1949.

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

117. Herbrich R., Williamson R. C. Learning and generalization: theoretical bounds. — Cambridge, MA, USA: MIT Press, 2002. — Pp. 619-623.

118. Holden S. B. Cross-validation and the pac learning model: Tech. Rep. RN/96/64: Dept. of CS, Univ. College, London, 1996.

119. Hosmer D. W., Lemeshow S. Applied Logistic Regression, second ed. — New York: Wiley, 2000.

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

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

122. Jacobs R. A., Jordan M. I., Nowlan S. J., Hinton G. E. Adaptive mixtures of local experts // Neural Computation.— 1991. — no. 3. — Pp. 79-87.

123. Karpinski M.f Macintyre A. Polynomial bounds for VC dimension of sigmoidal neural networks // 27th ACM Symposium on Theory of Computing, Las Vegas, Nevada, US.— 1995.- Pp. 200-208.

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

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

126. Kearns M., Valiant L. G. Cryptographic limitations on learning Boolean formulae and finite automata // Proc. of the 21st Annual ACM Symposium on Theory of Computing. — 1989. — Pp. 433-444.

127. Kearns M. J., Mansour Y., Ng A. Y., Ron D. An experimental and theoretical comparison of model selection methods // 8th Conf. on Computational Learning Theory, Santa Cruz, California, US. 1995. - Pp. 21-30.

128. Kearns M. J., Ron D. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation // Computational Learning Theory. — 1997. — Pp. 152-162.

129. Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection // 14th International Joint Conference oil Artificial Intelligence, Palais de Congres Montreal, Quebec, Canada. — 1995. — Pp. 1137-1145.

130. Koltchinskii V. Rademacher penalties and structural risk minimization // IEEE Transactions on Information Theory. — 2001. — Vol. 47, no. 5. — Pp. 1902-1914.

131. Koltchinskii V., Panchenko D. Rademacher processes and bounding the risk of functionlearning // High Dimensional Probability, II / Ed. by D. E. Gine, J.Wellner. — Birkhauser, 1999. — Pp. 443-457.

132. Koltchinskii V., Panchenko D. Empirical margin distributions and bounding the generalization error of combined classifiers // The Annals of Statistics. — 2002. — Vol. 30, no. 1, — Pp. 1-50.

133. Kuncheva L. Combining pattern classifiers.— John Wiley & Sons, Inc., 2004.

134. Kutin S., Niyogi P. The interaction of stability and weakness in AdaBoost: Tech. Rep. TR-2001-30: University of Chicago, Computer Science Department, 2001.

135. Kutin S., Niyogi P. Almost-everywhere algorithmic stability and generalization error: Tech. Rep. TR-2002-03: University of Chicago, Computer Science Department, 2002.

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

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

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

139. Langford J., McAllester D. Computable shell decomposition bounds // Proc. 13th Annu. Conference on Comput. Learning Theory. — Morgan Kaufmann, San Francisco, 2000. — Pp. 25-34.

140. Langford J., Seeger M. Bounds for averaging classifiers: Tech. Rep. CMU-CS-01-102: Carnegie Mellon University, January 2001.

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

142. Laviolette F., Marchand M. PAC-Bayes risk bounds for stochastic averages and majority votes of sample-compressed classifiers // Journal of Machine Learning Research. — 2007. — Vol. 8. Pp. 1461-1487.

143. Laviolette F., Marchand M., Shah M. PAC-Bayes approach to the set covering machine // Journal of Machine Learning Research.— 2006.— no. 18.— Pp. 731-738.

144. Lugosi G. On concentration-of-measure inequalities. — Machine Learning Summer School, Australian National University, Canberra. — 2003.

145. Mann H. B., Whitney D. R. On a test of whether one of two random variables is stochastically larger than the other // The Annals of Mathematical Statistics.— 1947.—

146. Vol. 18, no. 1,— Pp. 50-60.

147. Marchand M., Shawe-Taylor J. Learning with the set covering machine // Proc. 18th International Conf. on Machine Learning.— Morgan Kaufmann, San Francisco, CA, 2001. — Pp. 345-352.

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

149. Mason L., Bartlett P., Baxter J. Direct optimization of margins improves generalization in combined classifiers // Proceedings of the 1998 conference on Advances in Neural Information Processing Systems II. — MIT Press, 1999. — Pp. 288-294.

150. Mason L., Bartlett P., Golea M. Generalization error of combined classifiers: Tech. rep.: Department of Systems Engineering, Australian National University, 1997.

151. Mazurov V., Khachai M., Rybin A. Committee constructions for solving problems of selection, diagnostics and prediction // Proceedings of the Steklov Institute of mathematics. — 2002. — Vol. 1. — Pp. 67-101.

152. McAllester D. PAC-Bayesian model averaging // COLT: Proceedings of the Workshop on Computational Learning Theory. — Morgan Kaufmann Publishers, 1999.

153. McDiarmid C. On the method of bounded differences // In Surveys in Combinatorics, London Math. Soc. Lecture Notes Series. — 1989, — Vol. 141. — Pp. 148-188.

154. Mertens S., Engel A. Vapnik-Chervonenkis dimension of neural networks with binary weights // Phys. Rev. E.— 1997. —Vol. 55, no. 4. — Pp. 4478-4488.

155. Mullin M., Sukthankar R. Complete cross-validation for nearest neighbor classifiers // Proceedings of International Conference on Machine Learning. — 2000. — Pp. 639-646.

156. Ng A. Y. Preventing overfitting of cross-validation data // Proc. 14th International Conference on Machine Learning. — Morgan Kaufmann, 1997. — Pp. 245-253.

157. Osborne M. L. The seniority logic: A logic for a committee machine // IEEE Trans, on Сотр. — 1977. — Vol. C-26, no. 12. — Pp. 1302-1306.

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

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

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

161. Ratsch G., Onoda T., Muller K. R. An improvement of adaboost to avoid overfitting // Advances in Neutral Information Processing Systems, Kitakyushu, Japan. — 1998. — Pp. 506-509.

162. Ratsch, G., Onoda T., Muller K.-R. Soft margins for AdaBoost // Machine Learning.— 2001. Vol. 42, no. 3. — Pp. 287-320.

163. Rivest R. L. Learning decision lists // Machine Learning.— 1987.— Vol. 2, no. 3.— Pp. 229-246.

164. Rogers W., Wagner T. A finite sample distribution-free performance bound for local discrimination rules // Annals of Statistics.— 1978. — Vol. 6, no. 3. — Pp. 506-514,

165. Rosenblatt R. Principles of neuro dynamics.— New York: Spartan books, 1959.

166. Riickert U., Kramer S. Towards tight bounds for rule learning // Proc. 21th International Conference on Machine Learning, Banff, Canada. — 2004. — P. 90.

167. Schapire R. The boosting approach to machine learning: An overview // MSRI Workshop on Nonlinear Estimation and Classification, Berkeley, CA. — 2001.

168. Schapire R. E. The strength of weak learnability // Machine Learning. — 1990. — Vol. 5. — Pp. 197-227.

169. Schapire R. E., Freund Y., Lee W. S., Bartlett P. Boosting the margin: a new explanation for the effectiveness of voting methods // Annals of Statistics. — 1998. — Vol. 26, no. 5. — Pp. 1651-1686.

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

171. Seeger M. PAC-Bayesian generalization error bounds for Gaussian process classification // Journal of Machine Learning Research. — 2002. — Vol. 3. — Pp. 233-269.

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

173. Shawe-Taylor J., Cristianini N. Robust bounds on generalization from the margin distribution: Tech. Rep. NC2-TR-1998-029: Royal Holloway, University of London, 1998.

174. Shawe-Taylor J., Cristianini N. Margin distribution bounds on generalization // EuroCOLT '99: Proceedings of the 4th European Conference on Computational Learning Theory. — Springer-Verlag, 1999.—Pp. 263-273.

175. Shawe-Taylor J., Cristianini N. On the generalization of soft margin algorithms // IEEE

176. Trans, on Information Theory. — 2002. — Vol. 48, no. 10. — Pp. 2721-2735.

177. Sill J. Generalization bounds for connected function classes. — citeseer.ist.psu.edu/127284.html.

178. Sill J. The capacity of monotonie functions // Discrete Applied Mathematics (special issue on VC dimension). — 1998. — Vol. 86. — Pp. 95-107.

179. Sill J. Monotonicity and connectedness in learning systems: Ph.D. thesis / California Institute of Technology. — 1998.

180. Sill J., Abu-Mostafa Y. S. Monotonicity hints // Advances in Neural Information Processing Systems / Ed. by M. C. Mozcr, M. I. Jordan, T. Petsche. — Vol. 9. — The MIT Press, 1997, — P. 634.

181. Smola A., Bartlett P., Scholkopf B., Schuurrnans D. Advances in large margin classifiers. — MIT Press, Cambridge, MA. — 2000.

182. Talagrand. M. Sharper bounds for gaussian and empirical processes // Annals of Probability. — 1994. — no. 22. — Pp. 28-76.

183. Talagrand M. Concentration of measure and isoperimetric inequalities in product space // Publ. Math. I.H.E.S.— 1995. — no. 81. — Pp. 73-205.

184. Tipping M. The relevance vector machine // Advances in Neural Information Processing Systems, San Mateo, CA. — Morgan Kaufmann, 2000.

185. Valiant L. G. A theory of the learnable // Communications of the ACM.— 1984.— Vol. 27. — Pp. 1134-1142.

186. Vapnik V. Estimation of Dependencies Based on Empirical Data. — Springer-Verlag, New York, 1982.

187. Vapnik V. The nature of statistical learning theory. — Springer-Verlag, New York, 1995.

188. Vapnik V. Statistical Learning Theory. — Wiley, New York, 1998.

189. Vapnik V., Levin E., Cun Y. L. Measuring the VC-dimension of a learning machine // Neural Computation. — 1994. — Vol. 6, no. 5. — Pp. 851-876.

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

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

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

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

194. Wilcoxon F. Individual comparisons by ranking methods // Biometrics Bulletin. — 1945. — Vol. 1, no. 6. — Pp. 80-83.

195. Williamson R., Shawe-Taylor J., Scholkopf B., Smola A. Sample based generalization bounds: Tech. Rep. NeuroCOLT Technical Report NC-TR-99-055: 1999.

196. Wolpert D. H. Stacked generalization // Neural Networks. — 1992. — no. 5. — Pp. 241-259.