WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

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

ОЦЕНКИ ОБОБЩАЮЩЕЙ

СПОСОБНОСТИ

НА ОСНОВЕ ХАРАКТЕРИСТИК

РАССЛОЕНИЯ И СВЯЗНОСТИ

СЕМЕЙСТВ ФУНКЦИЙ

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

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

Москва, 2011

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

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

Официальные оппоненты: доктор физико-математических наук, Дьяконов Александр Геннадьевич кандидат физико-математических наук, Червоненкис Алексей Яковлевич

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

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

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

Автореферат разослан 2011 г.

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации по теме диссертации в изданиях из списка ВАК:

[2, 1]. Другие публикации по теме диссертации: [8, 7, 6, 5, 4, 3].

Текст диссертации доступен на странице автора www.MachineLearning.ru/wiki, Участник:Denis Kochedykov.

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

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

Введение §1.1. Пусть X множество объектов, Y множество допустимых ответов, F параметрическое семейство отображений из X в Y, называемых алгоритмами, X = {x1,..., xL } X фиксированная конечная генеральная совокупность из L объектов, называемая полной выборкой.

Будем называть подмножества X X, |X| = обучающими выборками. Метод обучения µ есть отображение µ : 2X F.

Пусть задана бинарная функция потерь I : F X {0, 1}.

Если I(f, x) = 1, то говорят, что алгоритм f F допускает ошибку на объекте x X.

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

Будем для краткости обозначать (1) как A = I(F, X) и называть векторы из A также алгоритмами, имея ввиду произвольный алгоритм из соответствующего класса эквивалентности на F.

Число ошибок алгоритма a A на X X есть n(a, X) = = card {x X : I(a, x) = 1}, частота ошибок есть (a, X) = = n(a, X)/ |X|. Будем пользоваться сокращенными обозначениями n(a, X) na, n(a, X) na, (a, X) a, (a, X) a.

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

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

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

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

некоторая оценочная функция, значение (0, 1) достаточно близко к нулю. Назначение таких оценок состоит в том, чтобы, минимизируя оценочную функцию (, X, F, µ, ) по F, µ, сконструировать метод обучения µ и семейство F с наилучшей обобщающей способностью.

§1.2. Вводится общий критерий переобучения U (na, na ), рассматриваются некоторые его частные случаи: na /L na / ся вероятность переобучения P[ U (na, na ) ] и процедура обращения оценки вероятности переобучения:

§1.3. Приводится определение и доказываются некоторые свойства гипергеометрического распределения. Пусть имеется L объектов, из которых равновероятно выбирается без возвращения объектов. Если среди L объектов на m объектах алгоритм a делает ошибку, то вероятность того, что в выборку попадут s таких объектов, подчиняется гипергеометрическому распределению: hm (s) = m Lm L пергеометрического распределения Hm (s) = s hm (t).

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

Третий вариант в (2) интерпретируется следующим образом:

алгоритм a переобучен, если число его ошибок na на обучающей выборке меньше -квантили распределения Hna (s). Параметр здесь играет ту же роль, что в критерии a a, и также называется в работе порогом переобучения. Чем меньше, тем более переобучен алгоритм a. Квантильный критерий удобен тем, что вероятность переобучения для одного алгоритма равна независимо от его полного числа ошибок na.

Лемма 1.4.1. Для любого a A и любого (0, 1) справедлива доверительная оценка: P[ na < n ( a, )] Лемма 1.4.2. Для любого a A и любого (0, 1) спрагде ведлива доверительная оценка P[ na > n ( a, )] §1.5. Приводятся комбинаторные аналоги классических оценок Вапника-Червоненкиса и бритвы Оккама (Блумер, 1987).

Теорема 1.5.1. Для любого семейства F, любой полной выборки X, |X| = L, метода обучения µ : [X] F, индикатора ошибки I : X F {0, 1}, и любого (0, 1) верна оценка и доверительная оценка Отметим, что в этой и последующих оценках величина имеет смысл вероятности переобучения, а величина порога переобучения и вероятности переобучения для отдельного алгоритма; для VC-оценки = |A|.

Теорема 1.5.2. Для любого семейства F, любой полной выборки X, |X| = L, метода обучения µ : [X] F, индикатора ошибки I : X F {0, 1}, любого (0, 1) и вектора порогов переобучения = (a : a A) имеет место оценка вероятности переобучения При условии Оценка бритвы Оккама позволяет получать более точные в среднем (по обучающим выборкам) доверительные оценки для na, задавая бльшие пороги a (и, соответственно, полуо чая меньшие оценки n ( a, a )) для тех a, которые чаще являn ются результатом обучения.

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

Лемма 1.6.1. Для любого семейства F, полной выборки X, A = I(F, X) и метода µ, пусть p = P[ µ(X) = a] : a A есть распределение вероятностей получения различных алгоритмов в результате обучения и = q, qa = 1 есть нормированный вектор порогов переобучения. Тогда минимум min E ( ln a ) доq стигается при q = p.

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

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

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

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

Определение 1. Профиль расслоения множества A есть m = = card {a A : na = m}. Будем называть соответствующее подмножество Am = {a A : na = m} m-ым слоем множества A.

Профиль наблюдаемых частот ошибок на обучающей выборке X есть случайная величина s = card {a A : na = s}.

§3.2. Краткий обзор работ, развивающих идею shell-оценок.

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

Теорема 3.3.3. Для любого семейства F, полной выборки X, |X| = L, метода обучения µ, индикатора ошибки I, если профиль расслоения множества A = I(F, X) есть m, то имеет место оценка вероятности переобучения где P (s, ) = m hm (s) верхняя оценка вероятности того, что какой-либо алгоритм из A имеет на обучающей выборке s ошибок и при этом переобучен.

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

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

Теорема 3.4.3. Для любого семейства F, полной выборки X, |X| = L, метода обучения µ, индикатора ошибки I, справедлива доверительная оценка симистичная оценка профиля расслоения, n (s) пессимистичная оценка полного числа ошибок алгоритма с s ошибками на обучающей выборке, §3.5. Как показывают эксперименты, точность shell-оценок не сильно отличается от точности VC-оценок. В эксперименте основная масса алгоритмов в семействе действительно концентрируется в области наихудшей частоты ошибок = 2 и при этом метод обучения µ в основном выбирает алгоритмы из области малых частот ошибок. Таким образом, сложность эффективно используемой части семейства существенно меньше сложности всего семейства F. Именно эти факты приводятся в качестве исходной мотивации shell-оценок. Однако фактически в shell-оценках они учитываются не в полной мере. Shellоценки, как и VC-оценка, основаны на вероятности равномерного отклонения частот по всему семейству F, а не по его части с малыми частотами ошибок. Основной причиной завышенности по-прежнему остаётся неравенство Буля, в котором суммирование вероятностей производится по всему семейству.

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

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

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

мингово расстояние между алгоритмами a и a. Графом 1-сходства множества A = I(F, X) будем называть граф G1 = (A, E) со множеством ребер E = {{a, a } A A : (a, a ) = 1}, соединяющих алгоритмы, векторы ошибок которых отличаются на одном объекте.

§4.2. Приводится краткий обзор известных способов оценивания вероятности конъюнкции событий (или, в контексте обучения, вероятности равномерного отклонения частот) и их приложений. Приводятся другие распространенные способы учета сходства алгоритмов в оценках обобщающей способности, §4.3. Предлагается два способа вычисления вероятностей вида P[ Ua1... Uak ], где Ua есть na sna () условие переобучения алгоритма a. Первый способ опирается на производящую функцию множества подмножеств из X с заданными свойствами. Второй способ основан на представлении условий Ua1... Uak в виде системы линейных неравенств с вектором бинарных неизвестных. Между этими двумя способами устанавливается соответствие.

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

Теорема 4.4.3. Для любого семейства F, любой полной выборки X, метода обучения µ : [X] F и индикатора ошибки I, если граф G1 множества A = I(F, X) связный, то выполняется оценка вероятности переобучения:

Также верна доверительная оценка где () = max { : P () }.

§4.5. Вводятся понятия полустепени связности алгоритма + (a) и профиля расслоения-связности m,q множества A, доказывается оценка обобщающей способности, учитывающая степени связности алгоритмов в A.

Определение 3. Верхняя полустепень связности алгоритма a есть есть число алгоритмов в его верхней единичной окрестности: + (a) = card {a A : (a, a ) = 1, n(a, X) = n(a, X) + 1}.

Профиль расслоения-связности множества A = I(F, X) есть матрица чисел:

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

Теорема 4.5.7. Для любого семейства F, полной выборки X, индикатора ошибки I, если профиль расслоения-связности множества A = I(F, X) есть m,q, то для любого метода обучения µ : [X] F вероятность переобучения оценивается как где N0 число алгоритмов в A с пустой верхней 1-окрестностью, m = Lm Lm < 1. Также верна доверительная оценка где () = max { : P () }.

Поскольку VC-оценка может быть записана как |A| = = m,q, то в последней теореме имеем множители m, < к слагаемым VC-оценки. В эксперименте с семейством линейных классификаторов Главы 6, число N0 алгоритмов без верхних связей в A пренебрежимо мал в сравнении с общим чисо лом алгоритмов, что дает экспоненциальное улучшение оценки последней теоремы относительно неравенства Буля с ростом среднего q. Для модельного случая A = {0, 1}L, N0 = 1, точное вычисление показывает, что последняя оценка улучшает оценку Вапника-Червоненкиса приблизительно в 20. 4L раз.

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

Определение 4. Цепь алгоритмов есть последовательность алгоритмов a1,..., aK, таких, что (ak, ak1 ) = 1. Будем называть цепь монотонной, если nak = nak1 + 1. Будем называть монотонную цепь максимальной, если aK AM, M = max na.

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

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

Теорема 4.6.3. Для любого семейства F, полной выборки X, |X| = L, индикатора ошибки I : F X {0, 1}, если в множестве A = I(F, X) для любого алгоритма a можно найти максимальную цепь, то для любого метода обучения µ : [X] F верна верхняя оценка вероятности переобучения:

ный коэффициент с вектором ограничений длины L m. Также верна доверительная оценка где () = max { : P () }.

Усеченный биномиальный коэффициент определяется по аналогии с обычным: n u = n1 u + n1 u [ k > un ] с граничk k k ными условиями n u = 1.

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

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

с индикатором ошибки I(aw, x) = [ aw (x) = y(x)], где y целевая функция.

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

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

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

Гиперплоскость h(xi ) разделяет W на два полупространства, соответствующие классификаторам, дающим правильный и неправильный ответ на объекте xi. Будем называть первое полупространство положительным, второе отрицательным.

Гиперплоскости H разбивают пространство W на множество ячеек {c(a), a A}, взаимнооднозначно соответствующих алгоритмам в A. Каждая ячейка представляет собой d-мерный многогранный бесконечный конус с вершиной в 0, включающий в себя все свои грани. Грани размерности d1 взаимнооднозначно соответствуют парам смежных (a, a ) = 1 алгоритмов в A.

Будем говорить, что (d 1)-мерная грань ячейки c(a), a A положительна, если ячейка лежит в положительном полупространстве соответствующей гиперплоскости, то есть алгоритм a не допускает ошибки на x, а смежный с ним алгоритм допускает. Тогда значение профиля связности + равно числу ячеq ек в H, имеющих ровно q положительных граней, а значение профиля расслоения m числу ячеек, лежащих ровно в m отрицательных полупространствах.

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

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

Теорема 5.2.2. Пусть F семейство линейных классификаторов (5) с индикатором ошибки (5.2) и объекты выборки X Rp находятся в общем положении. Тогда средняя полустепень связности алгоритмов во множестве A = I(F, X) есть §5.3. Дается определение зоны гиперплоскости в конфигурации гиперплоскостей, приводится лемма о максимальной сложности зоны в неоднородной конфигурации и доказывается лемма о максимальной сложности в однородной конфигурации. Последняя лемма используется в следующем параграфе для получения оценки дисперсии связности алгоритмов в A.

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

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

Теорема 5.4.1. Пусть F есть семейство линейных классификаторов (5) с индикатором ошибки (5.2) и объекты выборки X Rp находятся в общем положении. Тогда дисперсия полустепени связности алгоритмов во множестве A = I(F, X) оценивается сверху как где Z1 (L 1, d) максимальная сложность зоны в конфигурации L 1 однородных гиперплоскостей.

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

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

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

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

Публикации по теме диссертации [1] Kochedykov D. A. A combinatorial approach to hypothesis similarity in generalization bounds // Pattern Recognition and Image Analysis, December 2011 Vol. 21 no. 4.

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

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

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

М.: МФТИ, 2008.

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

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

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

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





Похожие работы:

«Надейкин Иван Викторович МЕТОДЫ КОНТРОЛЯ СЕРОВОДОРОДА И ЛЁГКИХ МЕРКАПТАНОВ ПРИ АТМОСФЕРНОЙ ПЕРЕГОНКЕ НЕФТИ ЮРУБЧЕНОТОХОМСКОГО МЕСТОРОЖДЕНИЯ 05.11.13 – Приборы и методы контроля природной среды, веществ, материалов и изделий АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Красноярск – 2011 2 Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования Сибирский федеральный университет...»

«Ястребов Виктор Владимирович Имитационное моделирование как инструмент управления предпринимательскими рисками Специальность 08.00.05 Экономика и управление народным хозяйством (Экономика предпринимательства) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Москва – 2011 Работа выполнена в Российской Академии предпринимательства Балабанова Анна Владимировна Научный руководитель : доктор экономических наук, профессор Рубе Вера Андреевна,...»

«ГУЗ ЮЛИЯ ВЛАДИСЛАВОВНА ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ БАЗОВЫХ КОНЦЕПТОВ ЦВЕТА (НА МАТЕРИАЛЕ РУССКОГО, АНГЛИЙСКОГО, НЕМЕЦКОГО И КИТАЙСКОГО ЯЗЫКОВ) Специальность 10.02.19 - теория языка АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата филологических наук Барнаул – 2010 Работа выполнена на кафедре русского языка ГОУ ВПО Алтайская государственная академия образования имени В.М. Шукшина Научный руководитель : доктор филологических наук, профессор Трофимова Елена...»

«Юрков Владимир Игоревич Регистрация неравновесных состояний мембраносвязанных ионов водорода в митохондриях и их роль в процессе окислительного фосфорилирования. 03.00.04 – биохимия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата биологических наук Москва – 2008 1 Работа выполнена в НИИ физико-химической биологии им. А.Н. Белозерского Московского Государственного Университета им. М.В. Ломоносова. Научный руководитель : доктор биологических наук, профессор...»

«МАРТЫНОВА Анастасия Владимировна МЕТОДЫ ФОРМИРОВАНИЯ ИМИДЖА ОРГАНИЗАЦИИ В УСЛОВИЯХ КРИЗИСА Специальность 08.00.05 – Экономика и управление народным хозяйством: маркетинг АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Санкт-Петербург 2011 Работа выполнена на кафедре маркетинга и управления проектами ФГБОУ ВПО Санкт-Петербургский государственный инженерноэкономический университет Научный руководитель : Божук Светлана Геннадьевна, доктор...»

«Ильин Владимир Александрович Педагогическая культура будущего юриста и её становление в процессе профессионального образования 13.00.01 - Общая педагогика, история педагогики и образования Автореферат диссертации на соискание ученой степени кандидата педагогических наук Владимир 2000 Работа выполнена на кафедре педагогики начального образования Владимирского государственного педагогического университета. Научный руководитель : Д.С. Яковлева, кандидат педагогических наук,...»

«Святкин Николай Михайлович САМОСОГЛАСОВАННЫЙ МЕТОД РАСЧЁТА ЭЛЕКТРОМАГНИТНЫХ ПОЛЕЙ В БЛИЖНИХ ЗОНАХ ИЗЛУЧАЮЩИХ СТРУКТУР, ГЕОМЕТРИЯ КОТОРЫХ ОПИСЫВАЕТСЯ В ЦИЛИНДРИЧЕСКОЙ СИСТЕМЕ КООРДИНАТ Специальность 01.04.03 – Радиофизика Автореферат диссертации на соискание учёной степени кандидата физикоматематических наук Самара – 2006 Работа...»

«ЛИСАВОЛ Людмила Алексеевна ПЕДАГОГИЧЕСКИЕ УСЛОВИЯ ФОРМИРОВАНИЯ ИНФОРМАЦИОННОЙ КУЛЬТУРЫ БУДУЩЕГО УЧИТЕЛЯ В ПЕДАГОГИЧЕСКОМ КОЛЛЕДЖЕ 13.00.08 – Теория и методика профессионального образования АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата педагогических наук Махачкала - 2009 Научный доктор педагогических наук, профессор руководитель: Савинова Людмила Федоровна доктор педагогических наук, профессор Официальные Везиров Т.Г. (г. Махачкала) оппоненты: доктор...»

«Коровина Ирина Валерьевна ПАРАМЕТРЫ ДЕЙКТИЧЕСКОЙ ПРОЦЕДУРЫ В АНГЛОЯЗЫЧНОЙ НАУЧНОЙ КОММУНИКАЦИИ Специальность 10.02.04 – германские языки АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата филологических наук Иваново 2011 Работа выполнена в ГОУ ВПО Мордовский государственный университет им. Н.П. Огарева Научный руководитель : доктор филологических наук, доцент Свойкин Константин Бертольдович Официальные оппоненты : доктор филологических наук, доцент Бабаева Раиса...»

«Кабакова Наталья Васильевна Государственные и церковные источники о демографических процессах в южных уездах Тобольской губернии в конце XVIII -...»

«Пермяков Антон Викторович Состояния в гражданском праве Специальность: 12.00.03 – Гражданское право; предпринимательское право; семейное право; международное частное право АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата юридических наук Москва – 2013 Работа выполнена на кафедре гражданского права и процесса Института права, экономики и управления Федерального государственного бюджетного образовательного учреждения высшего профессионального образования Тюменский...»

«КОЛОТИЛОВА Наталья Николаевна СТАНОВЛЕНИЕ ЭКОЛОГИЧЕСКОГО НАПРАВЛЕНИЯ В ОТЕЧЕСТВЕННОЙ МИКРОБИОЛОГИИ В ТРУДАХ С.Н.ВИНОГРАДСКОГО, ЕГО СОВРЕМЕННИКОВ И ПОСЛЕДОВАТЕЛЕЙ (КОНЕЦ XIX – СЕРЕДИНА ХХ ВВ.) Специальность 07.00.10 – история наук и и техники (биологические науки) Автореферат диссертации на соискание ученой степени доктора биологических наук Москва 2013 Работа выполнена на кафедре микробиологии биологического факультета Федерального государственного бюджетного образовательного...»

«АМАЛИЕВА ГУЗЕЛЬ ГАДИЛОВНА ЛИЧНЫЕ ДЕЛА СТУДЕНТОВ КАЗАНСКОГО УНИВЕРСИТЕТА (1917 – 1925 ГГ.) КАК ИСТОРИЧЕСКИЙ ИСТОЧНИК Специальность 07. 00. 09. – Историография, источниковедение и методы исторического исследования АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата исторических наук Казань – 2006 Работа выполнена на кафедре историографии и источниковедения государственного образовательного учреждения высшего профессионального образования Казанский государственный...»

«САННИКОВА ИРИНА ВИКТОРОВНА КРЫМСКАЯ-КОНГО ГЕМОРРАГИЧЕСКАЯ ЛИХОРАДКА: КЛИНИКО-ПАТОГЕНЕТИЧЕСКИЕ АСПЕКТЫ И ОПТИМИЗАЦИЯ ЛЕЧЕНИЯ 14.00.10 инфекционные болезни 14.00.05 – внутренние болезни Автореферат диссертации на соискание ученой степени доктора медицинских наук Москва -2009 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Ставропольская государственная медицинская академия Федерального агентства по здравоохранению и...»

«Клосс Юрий Юрьевич РАЗРАБОТКА ПРОБЛЕМНО-МОДЕЛИРУЮЩИХ СРЕД ДЛЯ АНАЛИЗА НЕРАВНОВЕСНЫХ ГАЗОКИНЕТИЧЕСКИХ ПРОЦЕССОВ В МИКРОУСТРОЙСТВАХ НА ОСНОВЕ РЕШЕНИЯ УРАВНЕНИЯ БОЛЬЦМАНА. Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук Москва – 2013 Работа выполнена на кафедре моделирования ядерных процессов и технологий Московского физико-технического института...»

«УДК 621.793 Литвинова Виктория Александровна ОПТИЧЕСКИЕ СВОЙСТВА НАНОРАЗМЕРНЫХ СТЕКЛОВИДНЫХ ПЛЕНОК ОКСИДОВ КРЕМНИЯ И ТАНТАЛА 01.04.04 – Физическая электроника АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Томск 2010 2 Работа выполнена в Томском государственном университете систем управления и радиоэлектроники Научный руководитель доктор технических наук, профессор Смирнов Серафим Всеволодович Официальные оппоненты доктор физико-математических...»

«Малахова Светлана Игоревна СВЯЗЬ ПСИХОМЕТРИЧЕСКОГО ИНТЕЛЛЕКТА С ЛИЧНОСТНОЙ САМОРЕГУЛЯЦИЕЙ СТУДЕНТОВ 19.00.07 - Педагогическая психология (психологические наук и) Автореферат диссертации на соискание ученой степени кандидата психологических наук Москва - 2013 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Московский государственный университет имени М.В.Ломоносова Научный руководитель : Смирнов Сергей...»

«МОСКВИЧЕВ ЕВГЕНИЙ АНАТОЛЬЕВИЧ РАЗРАБОТКА ПРОГРАММЫ СТИМУЛИРОВАНИЯ СБЫТА ПРОДУКЦИИ ПРЕДПРИЯТИЯ (НА ПРИМЕРЕ ЭЛЕКТРОЭНЕРГЕТИЧЕСКОГО КОМПЛЕКСА) Специальность: 08.00.05 – Экономика и управление народным хозяйством (маркетинг) Автореферат диссертации на соискание ученой степени кандидата экономических наук Волгоград – 2007 2 Диссертация выполнена в ГОУ ВПО Волгоградский государственный технический университет. Научный руководитель д-р экон. наук Фомин Павел Алексеевич. Официальные...»

«УЛАСОВ АЛЕКСЕЙ ВАЛЕНТИНОВИЧ Исследование трансфекции клеток наночастицами полиплексов на основе полиэтиленимина Специальность 03.01.03 – молекулярная биология АВТОРЕФЕРАТ Диссертации на соискание ученой степени кандидата биологических наук Москва – 2011 Работа выполнена в лаборатории молекулярной генетики внутриклеточного транспорта Учреждения Российской академии наук Института биологии гена РАН Научный...»

«Есюкова Елена Евгеньевна ПРОСТРАНСТВЕННАЯ СТРУКТУРА И ВНУТРИГОДОВАЯ ИЗМЕНЧИВОСТЬ ГОРИЗОНТАЛЬНОГО ВОДООБМЕНА В БАЛТИЙСКОМ МОРЕ Специальность 25.00.28 – океанология АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата географических наук Калининград – 2009 Работа выполнена в Атлантическом отделении Института океанологии им. П.П. Ширшова Российской Академии Наук, г. Калининград Научный кандидат технических наук руководитель: Ирина Петровна Чубаренко Официальные доктор...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.