авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Вопросы комитетной полиэдральной отделимости конечных множеств

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

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

ПОБЕРИЙ МАРИЯ ИВАНОВНА ВОПРОСЫ КОМИТЕТНОЙ ПОЛИЭДРАЛЬНОЙ ОТДЕЛИМОСТИ КОНЕЧНЫХ МНОЖЕСТВ 01.01.09 дискретная математика и математическая кибернетика

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

Екатеринбург 2011

Работа выполнена в отделе математического программирования Ин ститута математики и механики УрО РАН.

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

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

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

Защита состоится "31" мая 2011 г. в 14 часов на заседании диссерта ционного совета Д 004.006.04 по защите диссертаций на соискание степени кандидата наук Института математики и механики УрО РАН РАН (620990, г. Екатеринбург, ул. С. Ковалевской, 16).

С диссертацией можно ознакомиться в библиотеке Института мате матики и механики УрО РАН.

Автореферат разослан "27" апреля 2011 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук В.Д. Скарин

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

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

Несовместные системы ограничений (уравнений или неравенств) типичный объект, возникающий при решении задач принятия ре шений, оптимизации и классификации, математического программи рования и распознавания образов, экономической и медицинской ди агностики и т.д. (см., например, работы И.И. Еремина, Вл.Д. Мазу рова1, Ю.И. Журавлева2 ). Во всех перечисленных случаях возника ет необходимость обобщения классического понятия решения. Тра диционным является подход, восходящий к работам П.Л. Чебышева, основанный на непрерывной аппроксимации и заключающийся в ос лаблении ограничений исходной задачи, при котором достигается их совокупная непротиворечивость. Тогда в качестве обобщенного решения рассматривается решение скорректированной задачи. Од нако такой вид обобщения обладает существенным недостатком: стро ящееся точное решение скорректированной задачи может не удов летворять ни одному из условий исходной.

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

Понятие комитета впервые появилось в работах по распознава нию образов: в совместной статье Эйблоу и Кейлора3 было введено понятие комитетного решения для системы строгих однородных ли 1 Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. - М.: Наука, 1979.

2 Журавлев Ю.И. Об алгебраическом подходе к решению задач рaспознавания или классификации // Проблемы кибернетики. Вып. 33. 1978. С. 5–68.

3 Ablow C.M., Kaylor D.J. Inconsistent Homogeneous Linear Inequalities // Bull.

Amer. Math. Soc., 1965, vol. 71, no. 5, p. 724.

нейных неравенств (cj, x) 0 (j Nm ). (1) n Конечная последовательность (x1,..., xq ) R называется коми тетом системы (1), если всякому неравенству удовлетворяет более половины ее элементов.

В более общем виде различные обобщения понятия решения на случай несовместных систем были введены в екатеринбургской шко ле распознавания. Современная теория комитетных конструкций опирается на результаты, полученные Вл.Д. Мазуровым 4. Им было доказано необходимое и достаточное условие существования коми тета несовместной системы линейных неравенств, получены первые оценки числа членов минимального комитета;

введены обобщения понятия комитета (p-комитет, (z,p)-комитет, z-решение и т.д.) и получены условия существования этих конструкций для систем ли нейных неравенств и некоторых более общих систем включений;

пред ложены и обоснованы вычислительные схемы для построения p-ко митетов, в том числе минимальных.

Каждой комитетной конструкции соответствует понятие разде ляющей комитетной конструкции и алгоритм распознавания. Сог ласно введенному Вл.Д. Мазуровым определению, разделяющим ко митетом (большинства) для конечных множеств A, B из Rn назы вается последовательность функций Q = (f1, f2,..., fq ), принадле жащих заданному параметрическому семейству F = {f ( · ;

c) : c C} {Rn R}, таких, что в каждой точке множества A более половины функций последовательности Q принимает положительное значение, а в каж дой точке множества B, напротив, отрицательное. При этом коми тетный алгоритм распознавания (решающее правило) подразумевает принятие решения об отнесении объекта к одному из двух классов на основе значения не одной функции из класса F, а последовательнос ти функций Q F. Для произвольного объекта s S с результатом измерений x(s) Rn вычисляется q значений i (s) = {0, 1} по правилу 1, если fi (x) i (s) = 0, если fi (x) 0, 4 Мазуров Вл.Д. Теория и приложения комитетных конструкций // Методы для нестационарных задач математического программирования. – Свердловск: УНЦ АН СССР, 1979. С.31–63.



после чего объект относится к первому классу, если большинство чи сел i (s) принимает значение 1, и ко второму в противном случае, то есть решение принимается по правилу простого большинства. За метим, что каждая из функций fi, рассматриваемая в отдельности, порождает алгоритм распознавания, который, в свою очередь, мо жет оказаться некорректным, в то время как построенный из этих функций комитетный алгоритм распознавания безошибочно клас сифицирует множество объектов с результатами измерений из мно жества A B, то есть является корректным на этом множестве.

Известный алгебраический подход к решению задач распознава ния образов опирается на фундаментальные результаты Ю.И. Жу равлева. Важное место в его работах занимает проблема построения корректных алгоритмов распознавания над множествами некоррект ных5. Развитие алгебраического подхода к синтезу корректных ал горитмов распознавания было продолжено в работах К.В. Рудакова, В.В. Рязанова, Е.В. Дюковой, К.В. Воронцова и др.

Актуальность темы. С 80-х годов прошлого века у исследова телей возник интерес к изучению вычислительной сложности ком бинаторных задач, связанных с процедурой обучения распознава нию образов. Приведем общую постановку задачи обучения рас познаванию образов, для чего зафиксируем измеримое пространство (X, A, P ), где X множество результатов измерений, = {0, 1} множество названий образов (классов), P вероятностная мера, и зададимся множеством F = {f (·, ) : X : } решающих правил, причем S = {(x, ) : f (x, ) = } A ( ), то есть является событием. Задачей обучения распознаванию образов называется оптимизационная задача (f (x, ) )2 dP (x, ), min P () = min (2) X где вероятностная мера P считается неизвестной и заданной с точ ностью до конечной выборки (x1, 1 ),..., (xl, l ). Для аппроксима 5 Журавлев Ю.И. Корректные алгебры над множествами некорректных алгоритмов. I-III // Кибернетика. 1977, №4, С. 14–21;

1977, №6, С. 21–27;

1978, №2, С. 35–43.

ции неполностью формализованной задачи (2) традиционно рассмат ривается задача минимизации эмпирического риска:

l (i f (xi, ))2 }, min{() (3) l i= где (x1, 1 ),..., (xl, l ) заданная выборка, F = {f (·, ) : } класс решающих правил. Как известно6, точность аппроксимации монотонно убывает с ростом емкости V CD класса решающих правил.





В рамках алгебраического подхода к решению задач распознавания исследуются классы, содержащие корректные на выборке решающие правила. Для таких классов повышение качества обучения может быть связано с минимизацией емкости класса, то есть с решением задачи min{V CD(F ) : min{() : f F } = 0, F F}. (4) Исследуемая в работе задача о минимальном аффинном разделя ющем комитете (MASC) является частным случаем задачи (4), в котором класс F является классом комитетных кусочно-линейных решающих правил.

Задача “Минимальный аффинный разделяющий комитет”.

Заданы конечные множества A, B Qn, A = {a1,..., am1 } и B = {b1,..., bm2 }. Требуется указать аффинный комитет с наименьшим числом элементов, разделяющий множества A и B.

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

Вычислительная сложность задачи о минимальном по числу эле ментов комитете впервые была исследована М.Ю. Хачаем. Им дока зана труднорешаемость задачи в общем случае и основных ее специ альных случаев: задачи о минимальном комитете системы конечных множеств (MCFS), задачи о минимальном комитете системы линей ных неравенств (MCLE) и тесно связанной с ней задачи MASC. Ряд 6 Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. –М.: Наука, 1974. 416 с.

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

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

Известно, что многие N P -трудные в общем случае задачи ком бинаторной оптимизации становятся полиномиально (или псевдо полиномиально) разрешимыми при дополнительных ограничениях:

при фиксации размерности пространства, числа ограничений и т.п.

Также известно, что задача MASC, заданная в одномерном про странстве, может быть решена за полиномиальное время. Поэтому интерес вызывает исследование вычислительной сложности задачи о минимальном аффинном разделяющем комитете в пространствах фиксированной размерности, большей единицы (MASC(n)). Ранее показано, что задача MASC(n) N P -трудна7, однако для обоснова ния этого факта рассматриваются частные случаи задачи MASC(n), в которых разделяемые множества находятся не в общем положении, то есть доказательство существенным образом опирается на вырож денность разделяемых множеств. Для того, чтобы исключить из рассмотрения подобные частные случаи задачи MASC(n), в диссер тационной работе вводится дополнительное ограничение на разде ляемые множества и исследуется вычислительная сложность и ап проксимируемость задачи о минимальном аффинном разделяющем комитете, сформулированной в пространстве фиксированной раз мерности n 1, при условии общности положения разделяемых мно жеств (MASC-GP(n)). Кроме того, актуальность изучения задачи MASC-GP(n) обусловлена указанной ранее связью задачи о мини мальном аффинном разделяющем комитете с задачей обучения рас познаванию образов, поскольку последняя всегда рассматривается в пространстве фиксированной размерности.

7 Khachai M.Yu. Computational and Approximational Complexity of Combina torial Problems Related to the Committee Polyhedral Separability of Finite Sets // Pattern Recognition and Image Analysis, 2008, vol. 18, no. 2. pp. 237–242.

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

- исследование вычислительной сложности комбинаторной зада чи о минимальном по числу элементов аффинном разделяю щем комитете в пространствах фиксированной размерности, большей единицы, при условии общности положения разделя емых множеств (MASC-GP(n));

- разработку и обоснование полиномиального приближенного ал горитма решения задачи MASC-GP(n);

- оценку емкости V CD класса аффинных комитетных решаю щих правил с ограниченным числом элементов.

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

математический ап парат теории линейных неравенств, линейного программирования и теории графов;

элементы вычислительной геометрии.

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

Доказана M AX-SN P -трудность задач о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN PC) и о минимальном аффинном разделяющем комитете в простран стве фиксированной размерности для множеств в общем положении (MASC-GP(n)). Таким образом обоснована невозможность постро ения для этих задач полиномиальной аппроксимационной схемы, в предположении P = N P.

Получена новая оценка емкости V CD класса аффинных коми тетных решающих правил с ограниченным числом элементов.

На защиту выносятся следующие результаты.

1. Доказано, что задача об аффинном разделяющем комитете на плоскости для множеств в общем положении, сформулирован ная в виде задачи верификации свойства, – задача PASC-GP является N P -полной в сильном смысле. Обоснована трудноре шаемость (в сильном смысле) задачи о минимальном аффин ном разделяющем комитете в пространствах фиксированной размерности, большей единицы, при условии общности поло жения разделяемых множеств (MASC-GP(n)).

2. Разработан и обоснован приближенный алгоритм решения за дачи MASC-GP(n), обладающий в общем случае точностью аппроксимации O(m/n), а при справедливости некоторого до полнительного предположения точностью O(log m).

3. Доказана M AX-SN P -трудность задач о минимальном покры тии конечного множества точек плоскости множеством прямых (MIN-PC) и о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности при условии общ ности положения разделяемых множеств (MASC-GP(n)) и, сле довательно, невозможность построения для этих задач полино миальной аппроксимационной схемы, если P = N P.

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

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

Апробация работы. Результаты работы обсуждались на семина ре "Математическое программирование" ИММ УрО РАН под ру ководством академика И.И. Еремина, докладывались на междуна родных и всероссийских конференциях: 20-th EURO Mini-Confe rence "Continuous Optimization and Knowledge-Based Technologies" (EurOPT-2008) (Neringa, Lithuania, 2008);

7-ой Международной конференции "Интеллектуализация обработки информации" (ИОИ 2008) (Алушта, Украина, 2008);

10-ой Международной конферен ции "Распознавание образов и анализ изображений: новые инфор мационные технологии" (РОАИ-10-2010) (Санкт-Петербург, 2010);

Всероссийских конференциях "Математическое программирование и приложения" (Екатеринбург, 2007, 2011);

38 Молодежной Школе конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2007);

Всероссийских Молодежных конференциях "Проблемы теоретической и прикладной математики" (Екатерин бург, 2008, 2009, 2010);

Весенней конференции молодых ученых ИММ УрО РАН 2010 года (Екатеринбург, 2010).

Публикации. Основные результаты диссертации опубликованы в 13 научных работах, первые 3 из которых в журналах, входящих в список ВАК. В совместных работах диссертанту принадлежат до казательства основных утверждений.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 112 наиме нований. Объем работы составляет 122 страницы.

Автор выражает глубокую благодарность своему научному ру ководителю Хачаю Михаилу Юрьевичу за постоянное внимание и проявленный интерес к работе, а также всем участникам семинара "Математическое программирование" за полезные обсуждения ре зультатов работы и поддержку.

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

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

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

Пусть задано множество X и набор его непустых подмножеств D1, D2,..., Dm. Рассмотрим систему включений:

x Dj (j Nm ). (5) m Система (5) называется несовместной, если Dj =.

j= Определение 1.1.2. Комитетным решением (комитетом (большинства)) системы (5) называется конечная последователь ность Q = (x1, x2,..., xq ), xi X, такая, что для каждого j Nm q выполняется неравенство |{i : xi Dj }| 2.

При этом число q называется числом элементов комитета Q. Мини мальным называется комитет с наименьшим возможным для данной системы числом элементов.

Далее формулируются достаточные условия существования ко митетов и p-комитетов для произвольной системы включений (5).

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

Во втором параграфе вводится понятие разделяющего комитета и обсуждаются условия его существования. Пусть заданы конечные множества A и B из Rn и класс функций F = {f ( · ;

c) : c C} {Rn R}. Задача разделения множеств A и B состоит в отыскании такой функции f = f ( · ;

c) (параметра c C), что f (a;

c) 0 (a A) (6) f (b;

c) 0 (b B).

Определение 1.2.1. Разделяющим множества A и B комите том (p-комитетом) называется последовательность функций Q = (f ( · ;

c1 ), f ( · ;

c2 ),..., f ( · ;

cq )) такая, что соответствующая последо вательность параметров (c1, c2,..., cq ) является комитетом (p-коми тетом) системы неравенств (6).

Далее приводятся известные условия существования разделяющего комитета для конечных множеств A, B Rn, являющиеся, по сути, следствиями соответствующих теорем предыдущего параграфа.

В третьем параграфе вводятся основные понятия теории вычис лительной сложности алгоритмов: определяются классы задач P и N P, понятия N P -полноты и труднорешаемости, обсуждаются воп росы аппроксимируемости. Кроме того, вслед за Х. Пападимитриу и М. Яннакакисом8 вводится класс задач M AX-SN P, понятие M AX SN P -полноты, обсуждаются свойства задач из данного класса. Об зор построен на основе работ М. Гэри и Д. Джонсона 9 и Х. Папади митриу10.

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

Постановки этих задач и известные результаты относительно их вы числительной сложности также даны в третьем параграфе.

Пятый параграф содержит доказательство труднорешаемости и трудноаппроксимируемости задачи MASC в общем случае11.

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

Определение 2.2.1. Множество D Rn, |D| n, находится в общем положении, если для каждого подмножества D D мощ 8 Papadimitriou C., Yannakakis M. Optimization, approximation, and complexity classes // J. Comput. System Sci. 1991, vol. 43, no. 3. pp. 425–440.

9 Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.

- М.: Мир, 1982.

10 Papadimitriou Ch. Computational Complexity. – Addison-Wesley. 1995, 523p.

11 Хачай М. Ю. О вычислительной и аппроксимационной сложности задачи о минимальном аффинном разделяющем комитете // Таврический вестник информатики и математики, 2006, №1, С. 34–43.

ности n + 1 справедливо соотношение dim a(D ) = n.

Доказательство труднорешаемости задачи MASC-GP(n) при n 1, очевидно, достаточно провести на плоскости, для чего обосну ем полиномиальную сводимость к задаче MASC-GP(2), сформули рованной в виде задачи верификации свойства (назовем ее PASC GP), известной12 NP-полной (в сильном смысле) задачи о покрытии конечного множества точек плоскости множеством прямых (PC).

Задача “Покрытие прямыми конечного множества точек плос кости” (PC).

Заданы конечное множество точек плоскости P = {p1,..., pk } с целочисленными координатами и число s N. Сущест вует ли покрытие L множества P, не превосходящее по мощности s?

Пусть далее условие частной задачи PC определяется конечным множеством P из k целочисленных точек и некоторым натуральным числом s. Определим числа и по формулам = max{ p : p P }, =. (7) 6(2 + 1) + Зафиксируем двумерные векторы и так, что 2 = | 2 = 1, T = 0 и для любых {i, j} Nk пары отрезков [pi, pi + ] и [pj, pj + ], [pi, pi + ] и [pj, pj + ] не лежат на одной прямой. Сопоставим исходной задаче PC частную задачу PASC-GP, определяемую соотношениями (p) A = {p ± : p P }, B = {p ± (p) : p P } и t = 2s + 1.

M Числа (p) (0, ) и M 0 выберем так, чтобы выполнялось условие (p) max min (p) pP M pP и множество A B находилось в общем положении.

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

12 Megiddo N., Tamir A. On the complexity of locating linear facilities in the plane // Operations research letters. 1982, vol. 1, no. 5. pp. 194–197.

Теорема 2.2.1. Множество P = {p1,..., pk } Z2 обладает покры тием из s прямых в том и только в том случае, когда соответ ствующие ему множества A = {p ± (p) : p P } и B = {p ± (p) :

M p P } отделимы аффинным комитетом из 2s + 1 элемента.

Следствие. Задача PASC-GP является N P -полной в сильном смыс ле. Задачи MASC-GP(n) и MASC-GP являются N P -трудными в сильном смысле.

В третьем параграфе представлен и обоснован новый полиноми альный приближенный алгоритм для решения задачи MASC-GP(n), обладающий в общем случае точностью O(m/n), а при некотором естественном предположении точностью O(log m). При этом про цесс построения решения для задачи MASC-GP(n) описывается в терминах графа максимальных аффинно разделимых подмножеств множества Z = A B Qn.

Подмножество Z = A B, где A A, B B, называется аффинно разделимым подмножеством (множества Z), если сущест вует вектор c Rn и число d R такие, что cT a d 0, (a A ), (8) cT b d 0, (b B ).

Множество решений системы (8) обозначим через S(Z ). При этом аффинно разделимое подмножество Z называется максимальным (по включению) аффинно разделимым подмножеством множества Z, если для каждого z Z \ Z справедливо S(Z {z}) =.

Обозначим через M(Z) множество всех максимальных аффинно разделимых подмножеств множества Z.

Определение 2.3.1. Конечный граф GZ = (V, E) называется графом максимальных аффинно разделимых подмножеств множества Z, если V = M(Z) и для каждой пары {Z1, Z2 } V, {Z1, Z2 } E Z1 Z2 = Z.

Далее нам потребуется следующее предположение.

Предположение. Для аффинно неразделимого множества Z = AB и некоторого t существуют подмножества Z0, Z1,..., Z2t V (не обязательно попарно различные) такие, что {Z2j1, Z2j } E (j Nt ) и для произвольных (ci, di ) S(Zi ), i = 0, 1,..., 2t, последователь ность Q = (cT x d0, cT x d1,..., cT x d2t ) 0 1 2t является минимальным аффинным разделяющим комитетом для множеств A и B.

Условие предположения кажется слишком сильным, однако сле дует отметить, что примеры задачи MASC, используемые в извест ных доказательствах труднорешаемости данной задачи (в частности, в доказательстве теоремы 2.2.1), удовлетворяют ему.

Справедливо следующее утверждение Утверждение. Пусть множество Z = A B Qn, |Z| = m, определяет частную постановку задачи MASC-GP(n). Тогда пред ложенный алгоритм обладает вычислительной сложностью m O + m, n где вычислительная сложность решения совместной системы из не более чем m линейных неравенств от n + 1 переменной. При этом алгоритм имеет точность O(m/n).

Если для множества Z выполняется предположение, то алго ритм обладает точностью O(log m).

В четвертом параграфе доказывается, что задача о минимальном покрытии конечного множества точек плоскости множеством пря мых (MIN-PC) и задача MASC-GP(n) (при произвольном фикси рованном n 1) M AX-SN P -трудны. Для этого рассматривает ся M AX-SN P -полная задача MAX-3SAT(t) (это задача MAX-3SAT при дополнительном ограничении, что каждая переменная может входить в булеву формулу не более t раз) и строится схема полино миального сведения этой задачи к задачам MIN-PC и MASC-GP(2).

Теорема 2.4.1. Существует схема полиномиального сведения за дачи MAX-3SAT(t) к задаче MIN-PC, преобразующая булеву формулу к частной постановке задачи MIN-PC так, что • если OP T () = m, то OP T (P C) = nt, • если OP T () = m (1 )m, то OP T (P C) nt + n/6, где = E1... Em булева формула от n переменных, 0.

Поскольку задача MAX-3SAT(t) является M AX-SN P -полной, то теорема доказывет, что задача MIN-PC M AX-SN P -трудна.

Теорема 2.4.2. Существует схема полиномиального сведения за дачи MAX-3SAT(t) к задаче MASC-GP(2), преобразующая булеву формулу к частной постановке задачи MASC-GP(2) так, что • если OP T () = m, то OP T (M ASC GP (2)) = 2nt + 1, • если OP T () = m (1 )m, то OP T (M ASC GP (2)) 2nt + n/3 + 1, где = E1... Em булева формула от n переменных, 0.

Последняя теорема доказывает M AX-SN P -трудность задачи MASC GP(2), а следовательно, и задачи MASC-GP(n) при произвольном n 1. Принадлежность классу M AX-SN P -трудных задач MIN-PC и MASC-GP(n) влечет невозможность построения для них полино миальной аппроксимационной схемы, если P = N P.

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

В первом параграфе дается содержательная постановка задачи обучения распознаванию образов (задача (2)), приводятся получен ные В.Н. Вапником и А.Я. Червоненкисом достаточные условия кор ректности аппроксимации данной задачи задачей минимизации эм пирического риска (задача (3)).

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

Теорема 3.2.1. Емкость класса Fq комитетных решающих правил, состоящих из не более чем q аффинных функций, удовлетворяет соотношениям (V CD(Fq ) n + 1)/ q2, (9) n V CD(Fq ) q(n + 1) (10) и, следовательно, V CD(Fq ) = O(qn).

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

Публикации по теме диссертации [1] Вл.Д.Мазуров, М.Ю.Хачай, М.И.Поберий. Задачи комбинаторной оптимизации, связанные с полиэдральной комитетной отделимостью конечных множеств // Труды Института математики и механики УрО РАН, 2008. т. 14, №2, С. 89–102.

[2] Khachay M., Poberii M. Complexity and approximability of com mittee polyhedral separability of sets in general position // Infor matica. 2009. Vol. 20, no 2. pp. 217–234.

[3] Поберий М.И. О принадлежности классу M AX-SN P -трудных задач MIN-PC и MASC-GP(n) // Труды Института математики и механики УрО РАН, 2010. т. 16, №3, С.

210–215.

[4] Хачай М.Ю., Поберий М.И. Вычислительная сложность задач комитетной полиэдральной отделимости в пространствах фиксированной размерности // Таврический вестник информатики и математики. – Крымский научный центр национальной Академии наук и Министерства образования и науки Украины, 2008. №2. С. 218–227.

[5] Khachay M., Poberii M. Computational Complexity and Approx imability of Computational Optimization Problems Connected with Committee Polyhedral Separability of nite Sets // Proc. of 20-th EURO Mini-Conference "Continuous Optimization and Knowledge Based Technologies" (EurOPT-2008), May 20-23, 2008. Neringa, Lithuania, pp. 42–47.

[6] Хачай М.Ю., Поберий М.И. Вычислительная сложность задачи о минимальном аффинном разделяющем комитете при фиксированной размерности пространства // в кн. "Методы оптимизации и их приложения", труды XIV Байкальской школы-семинара. 2008. т. 1. С. 542–549.

[7] Poberiy M. M AX-SN P -hardness of MIN-PC and MASC-GP(n) problems // Proc. of 10-th International Conference "Pattern Recognition and Image Analysis: New Information Technologies" (PRIA-10-2010), December 5-12, 2010. St. Petersburg, The Rus sian Federation, pp. 157–160.

[8] Поберий М.И. Емкость класса аффинных разделяющих комитетов с ограниченным числом элементов // Информационный бюллетень № 11 Ассоциации математического программирования. Тезисы XIII Всероссийской конференции "Математическое программирование и приложения". –Екатеринбург: УрО РАН. 2007. С. 70–71.

[9] Поберий М.И. О M AX-SN P -трудности задач MIN PC и MASC-GP(n) // Информационный бюллетень № 12 Ассоциации математического программирования.

Тезисы XIV Всероссийской конференции "Математическое программирование и приложения". –Екатеринбург: УрО РАН.

2011. С. 126–127.

[10] Поберий М.И. Оценки емкости класса аффинных разделяющих комитетов с ограниченным числом элементов // Труды Молодежной Школы-конференции "Проблемы теоретической и прикладной математики". –Екатеринбург: УрО РАН. 2007. С.

111–115.

[11] Поберий М.И. О труднорешаемости задачи о минимальном аффинном разделяющем комитете на плоскости // Труды 39 Всероссийской Молодежной конференции "Проблемы теоретической и прикладной математики". –Екатеринбург:

УрО РАН. 2008. С. 337–342.

[12] Поберий М.И. Аппроксимируемость задачи о минимальном аффинном разделяющем комитете в пространствах фиксированной размерности // Труды 40 Всероссийской Молодежной конференции "Проблемы теоретической и прикладной математики". –Екатеринбург: УрО РАН. 2009. С.

317–321.

[13] Поберий М.И. О принадлежности классу M AX-SN P задач MIN-PC и MASC-GP(n) // Труды 41 Всероссийской Молодежной конференции "Проблемы теоретической и прикладной математики". –Екатеринбург: УрО РАН. 2010. С.

390–395.



 

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





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

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