Вопросы комитетной полиэдральной отделимости конечных множеств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

ПОВЕРИЙ МАРИЯ ИВАНОВНА

ВОПРОСЫ КОМИТЕТНОЙ ПОЛИЭДРАЛЬНОЙ ОТДЕЛИМОСТИ КОНЕЧНЫХ МНОЖЕСТВ

01.01.09 — дискретная математика и математическая кибернетика

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

1 9 МАЙ 2011

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

4847367

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

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

доктор физико-математических наук, профессор В.Л.Баранский.

доктор физико-математических наук, старший научный сотрудник A.B. Кельманов

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

Защита состоится " 2011г. в часов на

заседании диссертационного совета Д 004:006.04 по защите диссертаций на соискание степени кандидата наук Института математики и механики УрО РАН РАН (620990, г. Екатеринбург, ул. С. Ковалевской, 16).

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

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

Научный руководитель:

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

Ученый секретарь

диссертационного совета

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

(^/тВ-Д- Скарин

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

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

Несовместные системы ограничений (уравнений или неравенств)

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

Второй подход к коррекции несовместных систем ограничений

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

Понятие комитета впервые появилось в работах по распознаванию образов: в совместной статье Эйблоу и Кейлора3 было введено понятие комитетного решения для системы строгих однородных ли-

1Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. - М.: Наука, 197У.

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

3Ab]ow С.М., Kaylor D.J. Inconsistent Homogeneous Linear Inequalities // Bull. Amer. Math. Soc., 1965, vol. 71, no. 5, p. 724.

нейных неравенств

(с,-,х)>0 ОбМт). (1)

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

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

Каждой комитетной конструкции соответствует понятие разделяющей комитетной конструкции и алгоритм распознавания. Согласно введенному Вл.Д. Мазуровым определению, разделяющим комитетом (большинства) для конечных множеств А, В из К" называется последовательность функций £) = (Д, /2,..., /9), принадлежащих заданному параметрическому семейству

Р={Д;с) : с 6 С} С {Ж"-К},

таких, что в каждой точке множества А более половины функций последовательности С} принимает положительное значение, а в каждой точке множества В, напротив, отрицательное. При этом коми-тетный алгоритм распознавания (решающее правило) подразумевает принятие решения об отнесении объекта, к одному из дьух классов на основе значения не одной функции из класса Р. а последовательности функций <5 С Г. Для произвольного объекта, .в 6 5 с результатом измерений х(й) £ К™ вычисляется </ значений (¿¿(я) е И ~ {0,1} по правилу

Г 1, если /г(х) > 0 \ 0, если Л (ж) < 0,

4Мазуров Вл.Д. Теория и приложения комитетных конструкций // Методы для нестационарных задач математического программирования. — Свердловск: УНЦ АН СССР, 1979. С.31-63.

после чего объект относится к первому классу, если большинство чисел u>i(s) принимает значение 1, и ко второму — в противном случае, то есть решение принимается по правилу простого большинства. Заметим, что каждая из функций /¿, рассматриваемая в отдельности, порождает алгоритм распознавания, который, в свою очередь, может оказаться некорректным, в то время как построенный из этих функций комитетный алгоритм распознавания безошибочно классифицирует множество объектов с результатами измерений из множества А U В, то есть является корректным па этом множестве.

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

Актуальность темы. С 80-х годов прошлого века у исследователей возник интерес к изучению вычислительной сложности комбинаторных задач, связанных с процедурой обучения распознаванию образов. Приведем общую постановку задачи обучения распознаванию образов, для чего зафиксируем измеримое пространство (X х Ü, А, Р), где X — множество результатов измерений, il = {0,1} — множество названий образов (классов), Р — вероятностная мера, и зададимся множеством Т — {/(•,£*) : X —> Г2 : а G Л} решающих правил, причем

Sa ~ {(z,w) : f(x,a) / Л),

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

min Р(а) = min [ (f(x,a)-uj)2dP{x,uj), (2)

о£Л а£Л J

Л'хП

где вероятностная мера Р считается неизвестной и заданной с точностью до конечной выборки (xi,u>i)____,(xi,u>i). Для алпроксима-

5Журавлев Ю.И. Корректные алгебры над множествами некорректных алгоритмов. 1-Ш /,/ Кибернетика. 1977, №4, С. 14-21; 1977, №6, С. 21-27; 1978, №2, С. 35-43.

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

где (xi,wi),... ,(xi,wi) — заданная выборка, Т — {/(-,£*) : а £ Л} — класс решающих правил. Как известно6, точность аппроксимации монотонно убывает с ростом емкости VCD класса решающих правил. В рамках алгебраического подхода к решению задач распознавания исследуются классы, содержащие корректные на выборке решающие правила. Для таких классов повышение качества обучения может быть связано с минимизацией емкости класса, то есть с решением задачи

Исследуемая в работе задача о минимальном аффинном разделяющем комитете (МАБС) является частным случаем задачи (-1). в котором класс Т является классом комнтстпых кусо'то-лчпсйных решающих правил.

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

Заданы конечные множества А, В С 0>п, А = {ах,..., ат1} и В = {¿1,..., Ьт2}. Требуется указать аффинный комитет с наименьшим числом элементов, разделяющий множества А и В.

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

Вычислительная сложность задачи о минимальном по числу элементов комитете впервые была исследована М.Ю. Хачаем. Им доказана труднорешаемость задачи в общем случае и основных ее специальных случаев: задачи о минимальном комитете системы конечных множеств (МСГБ). задачи о минимальном комитете системы линейных неравенств (МСЬЕ) и тесно связанной с ней задачи МАБС. Ряд

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

(3)

mm{KC£>(.F') : min{«/(a) / £ = 0, 7' С Т). (4)

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

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

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

7Khachai M.Yu. Computational and Approximation^ Complexity of Combinatorial Problems Related to the Committee Polyhedral Separability of Finite Sets , / Pattern Recognition and ¡mage Analysis, 2008, vol. 18, no. 2. pp. 237-242.

!

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

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

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

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

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

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

Доказана МAX-SNP-трудность задач о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN-РС) и о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности для множеств в общем положении (MASC-GP(n)). Таким образом обоснована невозможность построения для этих задач полиномиальной аппроксимационной схемы, в предположении Р ф NP.

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

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

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

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

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

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

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

Апробация работы. Результаты работы обсуждались на семинаре "Математическое программирование" ИММ УрО РАН под руководством академика И.И.Еремина, докладывались на международных и всероссийских конференциях: 20-th EURO Mini-Conference "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 страницы.

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

Краткое содержание работы

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

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

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

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

хеБ, (5)

т

Система (5) называется несовместной, если

.7 = 1

Определение 1.1.2. Комитетным решением (комитетом (большинства)) системы (5) называется конечная последовательность — (х1гХ2, ■ - • ,хч), XI € X, такая, что для каждого ] е Мт выполняется неравенство |{г: £ О,-}! >

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

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

Во втором параграфе вводится понятие разделяющего комитета и обсуждаются условия его существования. Пусть заданы конечные множества Л и В из К" и класс функций Р = {/(•:£■■) : с 6 С} С {Ж" —> К}. Задача разделения множеств А и В состоит в отыскании такой функции / = /(■; с) (параметра с 6 С), что

/(а;с)>0 (а 6 А)

/(Ь;с) < о (ЬеВ).

Определение 1.2.1. Разделяющим множества А и В комитетом (р-комитетом) называется последовательность функций С} — (/('! с1)> /("; С2), ■ • ■, /(•; сд)) такая, что соответствующая последовательность параметров (с1, сг, ■.., сч) является комитетом (р-комитетом) системы неравенств (6).

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

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

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

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

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

Определение 2.2.1. Множество D С Kn, \D\ > п. находится в общем положении, если для каждого подмножества D' С D мощ-

8Papadiraitriou С., Yannakakis М. Optimization, approximation, and complexity classes // J. Comput. System Sci. 1991, vol. 43, no. 3. pp. 425-440.

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

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

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

ности п+ 1 справедливо соотношение сНтай(1>') = п.

Доказательство труднорсшаемости задачи М АБС-СР (п) при п > 1, очевидно, достаточно провести на плоскости, дли чего обоснуем полиномиальную сводимость к задаче МАБС-СР (2), сформулированной в виде задачи верификации свойства (назовем ее РАБС-йР), известной12 Л^Р-полпой (в сильном смысле) задачи о покрытии конечного множества точек плоскости множеством прямых (РС).

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

Заданы конечное множество точек плоскости Р = {р\...., Рк} с целочисленными координатами и число в 6 N. Существует ли покрытие Ь множества Р, не превосходящее по мощности в ?

Пусть далее условие частной задачи РС определяется конечным множеством Р из к целочисленных точек и некоторым натуральным числом в. Определим числа р и £ по формулам

р = тахЩрЦг : р € Р}, е = ^ +\} + 1. (7)

Зафиксируем двумерные векторы ант так, что ЦстЦг = |т||2 = 1, <ттт = 0 и для любых {г,]} С Р^ пары отрезков [рг — ес^ + ест] и [р^ — ев, ру + ео) , & —£т,р1+ет] и [р., — ег, р^ + ет] не лежат на одной прямой. Сопоставим исходной задаче РС частную задачу РАБС-вР, определяемую соотношениями

А= {р±^-т : р 6 Р), В = {р±е(р)а :ре Р) и « = 2в + 1.

Числа г(р) е (0, е) и М > 0 выберем так, чтобы выполнялось условие

£(р)

тах —-—< нпие(р) РбР М РеР

и множество Л и В находилось в общем положении.

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

l2Megiddo 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. Множество Р = {рь..., Рк} С 1? обладает покрытием из 5 прямых в том и только в том случае, когда соответствующие ему множества А = {р± г : р 6 Р] и В = {р±е(р)сг: р € Р} отделимы аффинным комитетом из 2в + 1 элемента.

Следствие. Задача РАБС-йР является NP-noлнoй в сильном смысле. Задачи МАЯС-СР(п) и МАБС-СР являются ЫР-трудными в сильном смысле.

В третьем параграфе представлен и обоснован новый полиномиальный приближенный алгоритм для решения задачи МЛ8С-ОР(п), обладающий в общем случае точностью 0(т/п), а при некотором естественном предположении — точностью 0(106 тп). При этом процесс построения решении для задачи МАЗС-СР(п) описывается в терминах графа максимальных аффинно разделимых подмножеств множества X — А и В с О71.

Подмножество ¿Г' = А' и В\ где А! Я; А, В' С. В, называется аффинно разделимым подмножеством (множества Z), если существует вектор се К" и число б! € К такие, что

( сТа-с1> 0, (а 6 А'), \стЬ-сК 0, (ЬеВ').

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

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

Определение 2.3.1. Конечный граф С г = (V, Е) называется графом максимальных аффинно разделимых подмножеств множества 2, если V = Ш(2) и для каждой пары {2[,2'2} С V,

{2[,2'2} е е и = г.

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

Предположение. Для аффинно неразделимого множества 2 = АиВ и некоторого £ существуют подмножества 2'0,2[,..., 221 6 V (не обязательно попарно различные) такие, что

и для произвольных (с,, с1г) £ г = 0,1,..., 24, последователь-

ность

<5 = (с£х — (10 ,с[х - ¿1,..., с^х - (¿2г)

является минимальным аффинным разделяющим комитетом для множеств А и В.

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

Справедливо следующее утверждение

Утверждение. Пусть множество Z = А и В С <0>'\ \2\ = гп, определяет частную постановку задачи МА8С-СР(п). Тогда предложенный алгоритм обладает вычислительно11 сложностью . °((™)"+ет)'

где @ — вычислительная сложность решения совместной системы из не более чем т линейных неравенств от п + 1 переменной. При этом алгоритм имеет точность 0(тп/п).

Если для множества У. выполняется предположение, то алгоритм обладает точностью 0(]ogm).

В четвертом параграфе доказывается, что задача о минимальном покрытии конечного множества точек плоскости множеством прямых (М1К-РС) и задача МАЗС-СР(п) (при произвольном фиксированном п > 1) МАХ-БЫР-трудны. Для этого рассматривается MAX-SNP-полная задача МАХ-ЗБАТ^) (это задача МАХ-ЗЙАТ при дополнительном ограничении, что каждая переменная может входить в булеву формулу не более £ раз) и строится схема полиномиального сведения этой задачи к задачам М11М-РС и МДйС-СР(2).

Теорема 2.4.1. Существует схема полиномиального сведения задачи МАХ-ЗЗАТ(Ь) к задаче МШ-РС, преобразующая булеву формулу 1р к частной постановке, задачи МШ-РС так., ■что

• если ОРТ((р) = т, то ОРТ(РС) = тй,

• если ОРТ{ф) = гп' < (1 - е)т, то ОРТ(РС) > пг + [еп/6], где (р = Е\ Л ... Л Ет булева формула от п переменных, е > 0.

Поскольку задача МАХ-38АТ(£) является МАХ-БМР-полной, то теорема доказывет, что задача МШ-РС М АХ-БNР-трудра.

Теорема 2.4.2. Существует схема полиномиального сведения задачи MAX-3SAT(t) к задаче MASC-GP(2), преобразующая булеву формулу <р к частной постановке задачи MASC-GP(2) так, что • если ОРТ(р) = m, то OPT{MASC - GP(2)) = 2nt + 1, . • если ОРТ{<р) = m' < (1 - e)m, то OPT(AIASC - GP(2)) > 2nt + \еп/3] + 1,

где ip — Ei Л ... Л Ern - булева формула от п переменных, е > 0.

Последняя теорема доказывает M AX-SNP-трудность задачи MASC-GP(2), а следовательно, и задачи MASC-GP(n) при произвольном п > 1. Принадлежность классу MAX-SNP-трудных задач MIN-PC и MASC-GP(ra) влечет невозможность построения для них полиномиальной аппроксимационной схемы, если Р ф NP.

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

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

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

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

д<2ГЦУСР(Ъ)-п + 1)/21 п

УСП(ГЧ) < 4{п + 1) (10)

и, следовательно, УСО{Тч) = О(дп).

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

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

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

[2] Khachay М., Poberii М. Complexity and approximability of committee polyhedral separability of sets in general position // Informática. 2009. Vol. 20, no 2. pp. 217-234.

[3] Поберий М.И. О принадлежности классу MAX-SNP-трудных

. задач MIN-PC и MASC-GP(n) // Труды Института

математики и механики УрО РАН, 2010. т. 16, .\°3, С. 210-215.

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

[5j Khachay М.. Poberii М. Computational Complexity and Approximability of Computational Optimization Problems Connected with Committee Polyhedral Separability of finite 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 М. МAX-SNP-harducñs 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 Russian Federation, pp. 157-160.

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

[9] Поберий М.И. О МЛ^-^Л^Р-трудности задач МШ-РС и МАЗС-СР(п) // Информационный бюллетень № 12 Ассоциации математического программирования. Тезисы XIV Всероссийской конференции "Математическое программирование и приложения". -Екатеринбург: УрО РАН. 2011. С. 126-127.

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

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

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

[13] Поберий М.И. О принадлежности классу МАХ-БЫР задач МШ-РС и МАЗС-СР(п) // Труды 41 Всероссийской Молодежной конференции "Проблемы теоретической и прикладной математики.". -Екатеринбург: УрО РАН. 2010. С. 390-395.

Подписано в печать Формат 60x84 1/16.

Плоская печать.

Бумага писчая. Тираж 100 экз. Заказ 173

Рюография НИЧ УрФУ, 620002, Екатеринбург, ул. Мира, 19

Введение

1 Комитетные решения несовместных систем ограничений

1.1 Понятие комитетного решения и условия его существования

1.2 Разделяющие комитетные конструкции.

1.3 Элементы теории вычислительной сложности алгоритмов.

1.3.1 Классы Р и NP.

1.3.2 Понятие iVP-полноты.

1.3.3 Класс А^Р-трудных задач.

1.3.4 Приближенные алгоритмы.

1.3.5 L-редукция и класс задач MAX-SNP.

1.4 Постановка задачи о минимальном аффинном разделяющем комитете (MASC) и связанные с ней задачи комбинаторной оптимизации

1.5 Вычислительная сложность и аппроксимируемость задачи о минимальном аффинном разделяющем комитете (MASC)

2 Задача о минимальном аффинном разделяющем комитете (MASC) в пространствах фиксированной размерности

2.1 Трудношаемость задачи MASC в пространствах фиксированной размерности

2.2 Трудношаемость задачи MASC: случай общего положения

2.3 Приближенный алгоритм решения задачи MASC-GP(n).

2.4 MAX-SNP-трудность задач MIN-PC и MASC-GP(n)

2.4.1 Схема сведения задачи MAX-3SAT(í) к задаче MIN-PC.

2.4.2 MAX-SNP-TpyflfiocTb задачи MASC-GP(n).

3 Задача обучения распознаванию образов в классе аффинных коми-тетных решающих правил

3.1 Основы сложностной теории обучения распознаванию образов.

3.2 Емкость класса аффинных комитетных решающих правил с ограниченным числом элементов.

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

Несовместные системы ограничений (уравнений или неравенств), возникающие при решении задач принятия решений, оптимизации и классификации, математического программирования и распознавания образов, экономической и медицинской диагностики, приводят к необходимости обобщения классического понятия решения. Традиционным является подход, восходящий к работам П.Л. Чебышева, основанный на непрерывной аппроксимации и заключающийся в ослаблении ограничений исходной задачи, при котором достигается их совокупная непротиворечивость [15]-[20], [52]-[54]. Тогда в качестве обобщенного решения рассматривается решение скорректированной задачи. Однако такой вид обобщения обладает существенным недостатком: строящееся точное решение скорректированной задачи может не удовлетворять ни одному из условий исходной.

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

Понятие комитета впервые появилось в работах по распознаванию образов: в совместной статье Эйблоу и Кейлора [77] было введено понятие комитетного решения для системы строгих однородных линейных неравенств ц,х)>о С?еМт). (1)

Конечная последовательность (х\,. ,хд) С Мп называется комитетом системы (2), если всякому неравенству удовлетворяет более половины ее элементов. В работе тех же авторов [78] сформулировано без доказательства достаточное условие существования комитета системы (2) и приведено его геометрическое обоснование.

В более общем виде различные виды обобщения понятия решения на случай несовместных систем были введены в екатеринбургской школе распознавания. Современная теория комитетных конструкций опирается на результаты, полученные Вл.Д. Мазуровым [29]-[32]. Им было доказано необходимое и достаточное условие существования комитета несовместной системы линейных неравенств, получены первые оценки числа членов минимального комитета; введены обобщения понятия комитета (р-комитет, (г,р)-комитет, г-решение и т.д.) и получены условия существования этих конструкций для систем линейных неравенств и некоторых более общих систем включений; предложены и обоснованы вычислительные схемы для построения р-комитетов, в том числе минимальных.

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

Э=(/ь/2,.,/в), принадлежащих заданному параметрическому семейству = {/(-;с) : с € С} С {М™ —> Ж}, таких, что соответствующая данным функциям последовательность значений параметров с1,с2, • • • ,Сд) является комитетным решением системы неравенств а; с) > 0 (а <Е А) ДЬ;с)< 0 (ЬеВ).

Тогда в каждой точке множества А более половины функций последовательности $ принимает положительное значение, а в каждой точке множества В, напротив, отрицательное, то есть г е N. : Ма) > 0}| > | (о € А), г<ЕМ9: /4(Ь)<0}| > | (ЬеВ).

При этом комитетный алгоритм распознавания (решающее правило) подразумевает принятие решения об отнесении объекта к одному из двух классов на основе значения не одной функции из класса Р, а последовательности функций (3 С Р. Для произвольного объекта в 6 <5 с результатом измерений х(з) £ Мп вычисляется q значений € ^ = {0,1} ио правилу | если > 0

1 0, если /г(ж) < О, после чего объект относится к первому классу, если большинство чисел принимает значение 1, и ко второму классу — в противном случае, то есть решение принимается по правилу простого большинства. Заметим, что каждая из функций рассматриваемая в отдельности, порождает алгоритм распознавания, который, в свою очередь, может оказаться некорректным, в то время как построенный из этих функций комитетный алгоритм распознавания безошибочно классифицирует множество объектов с результатами измерений из множества А и В, то есть является корректным на этом множестве.

Кроме комитетных алгоритмов распознавания, основанных на логике болыпинаства, в ряде работ рассматривались алгоритмы, основанные на других логиках: старшинства, единогласия и т.д. [33, 107]. Однако сведение задачи построения разделяющих комитетов с такими логиками к задаче построения комитета системы неравенств (включений) не столь очевидно, как в случае логики большинства. Исследованием вопроса о разделяющих возможностях комитетов с различными логиками при решении задач дискриминантного анализа и при реализации геометрических предикатов занимался Н.Г. Белецкий (см., например, [1]).

Известный алгебраический подход к решению задач распознавания образов опирается на фундаментальные результаты Ю.И. Журавлева. В середине 70-х годов ХХ-го века был опубликован цикл его работ, в которых важное место занимает проблема построения корректных алгоритмов распознавания над множествами некорректных [22, 23]. Им также были введены методы расширения класса алгоритмов при помощи алгебраических операций, позволяющие строить полное семейство алгоритмов, то ссть такое, в котором есть корректный алгоритм. Развитие алгебраического подхода к синтезу корректных алгоритмов распознавания было продолжено в работах К.В. Рудакова [47, 48], В.В. Рязанова [50, 51], Е.В. Дюковой [13, 14], К.В. Воронцова [4]-[6] и др.

Ю.А. Зуев предложил метод повышения надежности классификации путем объединения нескольких различных алгоритмов распознавания в комитет. В работах [24, 25] описан байесовский подход к построению корректора, принимающего решение о выборе класса, при котором работа алгоритма описывается вероятностным законом, и на основе обучающей информации оцениваются вероятности принадлежности объекта к одному из нескольких классов. /

Для теории комитетов и, в частности, для задачи построения минимального комитета большую роль играет метод фундаментального свертывания, развитый и обоснованный С.Н. Черниковым [75, 76]. Этот метод позволяет находить максимальные по включению совместные подсистемы (МСП) для исходной несовместной системы линейных неравенств. В работе Вл.Д. Мазурова [31] показано, что из существования ко-митетиой конструкции для несовместной системы линейных неравенств следует существование соответствующего решения, составленного из решений МСП исходной системы. Это позволяет ограничиться исследованием комитетов, составленных из решений МСП, и объясняет значимость метода фундаментального свертывания для теории комитетных решений.

Условия комитетной разрешимости системы несовместных включений удобно формулировать в терминах теории графов. В работе [55] было введено понятие графа МСП для системы строгих однородных линейных неравенств, а в [7, 8] данное понятие было распространено на системы ограничений более общего вида и изучены свойства графа МСП.

Позднее понятие графа МСП было обобщено в работах М.Ю. Хачая [56, 57, 85, 91], а именно, введено понятие гиперграфа МСП, на основе анализа свойств которого удалось получить более тонкие условия существования комитета. В частности, был доказан критерий существования комитетного решения с заданным числом элементов для системы абстрактных включений и проведена классификация минимальных ко-митетных решений на основе изоморфизма соответствующих им подги-перграфов гиперграфа МСП.

С 80-х годов прошлого века у исследователей возник интерес к изучению вычислительной сложности комбинаторных задач, связанных с процедурой обучения распознаванию образов. Приведем общую постановку задачи обучения распознаванию образов, для чего зафиксируем измеримое пространство (X х f2, Л, Р), где X — множество результатов измерений, Г) = {0,1} — множество названий образов (классов), Р — вероятностная мера, и зададимся множеством

Т — {/(•,се) решающих правил, причем

Sa = {{х,ои) : f(x, а) ф uj} G Л {a G Л), то есть является событием.

Задачей обучения распознаванию образов называется оптимизационная задача minP(o;)=mm / (f(x,a)—ca)2dP(x,uj), (2) абЛ а€Л J

ХхП где вероятностная мера Р считается неизвестной и заданной с точностью до конечной выборки a:i,wi), ■ • ■, {xi, toi).

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

1 ' пшаМа) = у - Я**' о))2}- (3) 1

Как известно [2], точность аппроксимации (обобщающая способность результирующего решающего правила /* = f(-,a*), где а* = arg min(3), монотонно убывает с ростом емкости УСО{Т') класса решающих правил Т.

Напомним, что емкостью УСО{Т) класса решающих правил Т называется наибольшее Н Е М, для которого существует такой набор х{Ь) — (жь . . . ,Хн), Хг е X, что для произвольного ш(1г) = . . . , Ш}г), и>1 Е О, найдется а (Е А, для которого я?,-, К].

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

Ж1,0>1),., (Х1,Ш1) решающие правила, то есть такие функции /(•, а) Е Т^ для которых

О;, а) = е М/. ,

Для таких классов оптимальное значение задачи (3) равно нулю, и повы-'" шение качества обучения может быть связано с минимизацией емкости класса, то есть с решением задачи тт{УСО{Т') : шт{г/(а) : / € Т'} = О, Т' С Г}. (4)

Исследуемая в работе задача о минимальном аффинном разделяющем комитете (МАЭС) является частным случаем задачи (4), в котором класс Т является классом комитетных кусочно-линейных решающих правил.

Задача "Минимальный аффинный разделяющий комитет" (МАЭС).

Заданы конечные множества А, В О (0>п, А = {ах,., ат1} и В — {61,., Ьт2}. Требуется указать аффинный комитет с наименьшим числом, элементов, разделяющий множества А и В.

Вычислительная сложность задачи о минимальном по числу элементов комитете впервые была исследована М.Ю. Хачаем. Им доказана труднорешаемость задачи в общем случае и основных ее специальных случаев [60, 73]: задачи о минимальном комитете системы конечных множеств (MCFS), задачи о минимальном комитете системы линейных неравенств (MCLE) и тесно связанной с ней задачи о минимальном аффинном разделяющем комитете (MASC), занимающей центральное место в настоящей работе. Ряд работ посвящен изучению вопроса эффективной аппроксимируемости обозначенных выше задач: получена оценка порога аппроксимируемости для задач MCFS [71] и MASC [95], разработаны и обоснованы полиномиальные приближенные алгоритмы решения задач MCLE [68], MASC [74] и некоторых их частных случаев.

Как было отмечено выше, задача о минимальном аффинном разделяющем комитете (MASC) в общем случае является труднорешаемой. Также известно (см., напр., [104]), что задача MASC, заданная в одномерном пространстве может быть решена за полиномиальное время. До недавнего времени открытым оставался вопрос о вычислительной сложности задачи MASC в пространствах фиксированной размерности, большей единицы. В работе [95] показано, что задача MASC остается iVP-труд-ной, будучи сформулированной в пространстве фиксированной размерности п > 1 — задача MASC(n). Однако при получении всех этих результатов, касающихся труднорешаемости задачи MASC, существенно использовалась вырожденность разделяемых множеств: рассматриваемые при доказательстве частные случаи задачи MASC были построены таким образом, что разделяемые множества находились не в общем положении. В связи с этим естественно возникает вопрос о вычислительной сложности задачи MASC, если исключить из рассмотрения подобные ее частные случаи. Ответ на него содержится во второй главе настоящей работы, в которой доказано, что задача о минимальном аффинном разделяющем комитете, сформулированная в пространстве фиксированной размерности, большей единицы, при условии общности положения разделяемых множеств (MASC-GP(n)) остается труднорешаемой. Условие общности положения разделяемых множеств заключается в том, что каждое подмножество из п+ 1 элемента множества Ли В, определяющего частную постановку задачи MASC, аффинно независимо.

Традиционный для теории вычислительной сложности подход [10, 11, 27, 28, 86, 108, 112] к исследованию NP-трудных задач комбинаторной оптимизации предполагает анализ аппроксимационных свойств задачи, разработку и обоснование приближенных алгоритмов для ее решения. В общем случае задача MASC является трудноаппроксимируемой [95]. В настоящей работе был дан ответ на вопрос об аппроксимируемости задачи MASC в пространстве фиксированной размерности п > 1 при дополнительном условии общности положения разделяемых множеств (MASC-GP(n)). Предложен новый полиномиальный приближенный алгоритм для решения задачи MASC-GP(n), обладающий, при некотором естественном предположении, точностью аппроксимации O(logm). Таким образом, алгоритм позволил сократить разрыв между полученной ранее границей аппроксимируемости для задачи о минимальном аффинном разделяющем комитете для конечных множеств O(logloglogm) [95] и лучшей точностью аппроксимации 0(т) известного полиномиального аппроксимационного алгоритма [74], где т — \А U В\ — мощность множества, определяющего частную задачу MASC.

Следующий круг вопросов, рассмотренный в работе, посвящен классу задач MAX-SNP. Этот класс был впервые определен в совместной работе X. Пападимитриу и М. Яннакакиса [109] и состоит из оптимизационных задач, обладающих приближенными алгоритмами с постоянной точностью. Во второй главе диссертации доказано, что задачи о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN-PC) и о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности п > 1 при условии общности положения разделяемых множеств (MASC-GP(n)) МАХ-.!?./VP-трудны. Это позволило сделать вывод о невозможности построения для задач MIN-PC и MASC-GP(n) аппроксимационной схемы, в предположении P^NP.

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

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

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

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

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

3. Доказана МЛХ-й'ЛГР-трудность задач о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN-РС) и о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности при условии общности положения разделяемых множеств (MASC-GP(n)) и, следовательно, невозможность построения для этих задач полиномиальной аппроксимацион-ной схемы, если Р ф N Р.

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

Публикации. Представленные в диссертации результаты опубликованы в работах [38], [40]-[45], [58], [59], [96], [97], [110].

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

- XIII Всероссийская конференция "Математическое программирование и приложения", 26.02.2007 - 02.03.2007, Екатеринбург.

- 38 Молодежная Школа-конференция "Проблемы теоретической и прикладной математики". 29.01.2007- 02.02.2007, Екатеринбург.

- 20-th EURO Mini-Conference "Continuous Optimization and Knowledge-Based Technologies" (EurOPT-2008), May 20-23, 2008, Neringa, Lithuania.

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

- 39 Всероссийская Молодежная конференция "Проблемы теоретической и прикладной математики". 28.01.2008 - 01.02.2008, Екатеринбург.

- 40 Всероссийская Молодежная конференция "Проблемы теоретической и прикладной математики". 26.01.2009 - 30.01.2009, Екатеринбург.

- 41 Всероссийская Молодежная конференция "Проблемы теоретической и прикладной математики". 01.02.2010 - 05.02.2010, Екатеринбург.

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

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

- XIV Всероссийская конференция "Математическое программирование и приложения", 28.02.2011 - 04.03.2011, Екатеринбург.

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

Заключение —----

1. Белецкий Н.Г. Разделяющие возможности комитетов с различными логиками. - Свердловск: УНЦ АН СССР, 1984. 23 с.

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

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

4. Воронцов К.В. Предварительная обработка данных для решения специального класса задач распознавания // ЖВМ и МФ. 1995. т. 35, № 10. С. 1565-1575.

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

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

7. Гайнанов Д.Н. О графах максимальных совместных подсистем несовместных систем линейных неравенств. -Москва, 1981. 46 с. Деп.ВИНИТИ, № 229-81.

8. Гайнанов Д.Н., Новокшенов В.А., Тягунов Л.И. О графах, порождаемых несовместными системами линейных неравенств // Мат. заметки. 1983. -Т. 33, вып. 2., С. 293-300.

9. Гейл Д. Соседние вершины на выпуклом многогрпннике. Линейные неравенства и смео!сиые вопросы, сборник статей под редакцией Г. У. Кун а и А.У.Таккера, Москва, 1959 рр. 355 362.

10. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации. Сб. "Проблемы кибернетики", вып. 31. М.: Наука, 1975. С. 35-42.

11. Гимади Э.Х. Асимптотически точный алгоритм отыскания одного и двух реберно непересекающихся маршрутов коммивояжера максимального веса в евклидовом пространстве / / Труды Института математики и механики УрО РАН, 2008. т. 14, №2, С. 23-32.

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

13. Дюкова Е.В. О сложности реализации некоторых процедур распознавания // ЖВМ и МФ. 1987. т. 27, № 1. С. 114-127.

14. Дюкова Е.В., Журавлев Ю.И., Рудаков К.В. Об алгебро-ло-гическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // ЖВМ и МФ. 1996. т. 36, № 8. С. 215223.

15. Евтушенко Ю.Г., Голиков А.И. Новый метод решения систем линейных равенств и неравенств. Доклады Академии Наук, 2001. т. 381, № 4, С. 444-447.

16. Евтушенко Ю.Г., Голиков А.И. Двойственный подход к решению систем линейных равенств и неравенств. Труды XII Байкальской международной конференции. Пленарные доклады, 2001. С. 91-99.

17. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 192 с.

18. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. 288 с.

19. Еремин И.И.Противоречивые модели оптимального планирования- Москва: Наука. 1988. 160 с.

20. Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998. 248 с.

21. Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: «У-Фактория», 2000. 280 с.

22. Журавлев Ю.И. Корректные алгебры над множествами некорректных алгоритмов. I-III // Кибернетика. 1977, №4, С. 14-21; 1977, №6, С. 21-27; 1978, №2, С. 35-43.

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

24. Зуев Ю.А. Метод повышения надежности классификации при наличии нескольких классификаторов, основанный на принципе монотонностиЦЖВМ и МФ, 1981. т.21. №1. С.157-167.

25. Зуев Ю.А. Вероятностная модель комитета классификаторов// ЖВМ и МФ, 1986. т.26. №2. С.276-292.

26. Качалков A.B., Рыбин А.И., Хачай М.Ю. Технология создания вычислительного сайта «Квазар-Онлайн» // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-6-2002». Новгород: НовГУ, 2002. С. 258-262.

27. Кельманов A.B., Пяткин A.B. О сложности одного из вариантов задачи выбора подмножества похожих векторов // ДАН. 2008. т. 421, №5. С. 590-592.

28. Кельманов A.B. О сложности некоторых задач анализа данных // ЖВМ и МФ. 2010. т. 50, № 11. С. 2045-2051.

29. Мазуров Вл.Д. О построении комитета системы выпуклых неравенств // Кибернетика, 1967. №2. С. 56-59.

30. Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика, 1971. №3. С. 140-146.

31. Мазуров Вл.Д. Несовместные системы неравенств в задачах распознавания // Метод комитетов в распознавании образов. Свердловск: УНЦ АН СССР, 1974. С. 3-9.

32. Мазуров Вл.Д., Тягунов Л.И. Метод комитетов в распознавании образов // Метод комитетов в распознавании образов. -Свердловск: УНЦ АН СССР, 1974. С.10-40.

33. Мазуров Вл.Д. Теория и приложения комитетных конструкций // Методы для нестационарных задач математического программирования. Свердловск: УНЦ АН СССР, 1979. С.31-63.

34. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации- М.: Наука, 1990. 248 с.

35. Мазуров Вл.Д., Хачай М.Ю. Комитетные конструкции // Известия УрГУ, 1999, вып. 14. С. 76-108.

36. Мазуров Вл.Д., Хачай М.Ю. Комитетные конструкции как обобщение решений противоречивых задач исследования операций // Дискретный анализ и исследование операций. 2003. Т. 10, Сер. 2, №2. С. 56-66.

37. Мазуров Вл.Д., Хачай М.Ю. Комитеты систем линейных неравенств /¡Автоматика и телемеханика, 2004. вып. 2, С. 43-54.

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

39. Пападимитриу К., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. 512 с.

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

41. Поберий М.И. О труднорешаемости задачи о минимальном аффинном разделяющем комитете на плоскости / / Труды 39 Всероссийской Молодежной конференции "Проблемы теоретической и прикладной математики". -Екатеринбург: УрО РАН. 2008. С. 337-342.

42. Поберий М.И. О принадлежности классу МАХ-вЫР задач МШ-РС и МА8С-СР(7г) //Труды 41 Всероссийской Молодеэ/сной конференции "Проблемы теоретической и прикладной математики". -Екатеринбург: УрО РАН. 2010. С. 390-395.

43. Поберий М.И. О принадлежности классу МАХ-вИР-трудных задач МШ-РС и МАЗС-СР(п) // Труды Института математики и механики УрО РАН, 2010. т. 16, №3, С. 210-215.

44. Рудаков К.В. О некоторых классах алгоритмов распознавания (общие результаты). М.: ВЦ РАН СССР, 1980. 66 с.

45. Рудаков К.В. О некоторых классах алгоритмов распознавания (параметрические модели). М.: ВЦ РАН СССР, 1981. 48 с.

46. Рыбин А.И. Об оценках минимального комитета. Москва, 2000. 35с. Деп. в ВИНИТИ 28 ноября 2000г., 3029-В00.

47. Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации // ЖВМ и МФ. 1981. т. 21, № 6. С. 1533-1543.

48. Рязанов В.В. О синтезе классифицирующих алгоритмов на конечных множествах алгоритмов классификации (таксономии) // ЖВМ и МФ. 1982. т. 22, № 2. С. 429-440.

49. Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования // ЖВМ и МФ. 1986. т. 26, № 3, С. 439-448

50. Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Труды Института математики и механики УрО РАН, 2008. т. 14, №2, С. 115-128.

51. Скарин В.Д. Об одном общем подходе к оптимальной коррекции несобственных задач выпуклого программирования // Труды Института математики и механики УрО РАН, 2010. т. 16, № 3, С. 265-275.

52. Хачай М.Ю. О существовании комитета большинства // Дискретная математика, 1997. т. 9, вып. 3. С. 82-95.

53. Хачай М.Ю. Об оценке числа членов минимального комитета системы линейных неравенств // ЖВМ и МФ, 1997. т. 37, № 11. С. 1399-1404.

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

55. Хачай М.Ю., Рыбин А.И. О комитетном решении с минимальным числом членов системы линейных неравенств // Труды XI меоЫу-народной Байкальской школы-семинара «Методы оптимизации и их приложения». Иркутск: ИСЭ СО РАН, 1998. С. 26-40.

56. Хачай М.Ю. Об оценке емкости класса комитетных решающих функций // Доклады IX Всероссийской конференции «Математические методы распознавания образов». 1999, Москва, ВЦ РАН, С. 121-123.

57. Хачай М.Ю. Об одной комбинаторной задаче, связанной с понятием минимального комитета // Труды Международной конференцииРаспознавание образов и анализ изображений РОАИ-5-2000». — Самара: ИСОИ РАН. 2000. С. 167-169.

58. Хачай М.Ю. О достаточной длине обучающей выборки для коми-тетного решающего правила // Искусственный интеллект. 2000, №2, С. 219-223.

59. Хачай М.Ю. Об одном соотношении, связанном с процедурой принятия решений большинством голосов // ДАН. 2001. т. 381, №6. С. 748-752.

60. Хачай М.Ю. Об одном соотношении, связанном с голосованием большинством // Труды Международной конференции «Математическое моделирование (ММ-2001)». Самара: ИСОИ РАН. 2001. С. 41-44.

61. Хачай М.Ю. Об одной игре с природой, связанной с принятием решений большинством голосов // Доклады X Всероссийской конференции «Математические методы распознавания образов». -Москва: ВЦ РАН. 2001. С. 149-153.

62. Хачай М.Ю. Об одной игре с природой, связанной с принятием решений большинством голосов // ЖВМ и МФ. 2002, т. 42, №10, С. 1609-1616.

63. Хачай М.Ю. Приближенный алгоритм решения задачи о минимальном комитете системы линейных неравенств / в сб. «Алгебра и линейная оптимизация», труды международного семинара, посвященного 90-летию С.Н.Черникова. Екатеринбург: УрО РАН. 2002. С. 314-318.

64. Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете // Доклады XI Всероссийской конференции «Математические методы распознавания образов». Москва: ВЦ РАН. 2003. С. 198-201.

65. Хачай М.Ю. Об апроксимационной сложности задачи о минимальном комитете // Таврический вестник информатики и математики. 2004, №1. С. 78-82.

66. Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-7-2004»- — С.-Петербург: ЛЭТИ. 2004.

67. Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете и смежных задач //ДАН, 2006, 406, №6, С. 742-745.

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

69. Черников С.Н. Линейные неравенства. М.: Наука, 1968. 488 с.

70. Черников С.Н. Свертывание конечных систем линейных неравенств // ДАН УССР, 1969, №1, С. 32-35.

71. Ablow С.М., Kaylor D.J. Inconsistent Homogeneous Linear Inequalities // Bull. Amer. Math. Soc., 1965, vol. 71, no. 5, p. 724.

72. Ablow C.M., Kaylor D.J. A Committee solution of the pattern recognition problem // IEEE Trans. Information Theory, 1965, vol. 11, no. 3, pp. 453-455.

73. Arora S., Safra M. Probabilistic Checking of Proofs: A new Characterization of NP // Journal of ACM. 1998. 45(1), pp. 70-122.

74. Blum A.L., Rivest R.L. Training a 3-node Neural Network is NP-complete // Neural Networks. 1992, vol. 5, pp. 117-127.

75. Cook S.A. The complexity of theorem-proving procedures// Proc. 3rd Ann. ACM Symp. on Theory of Computing. ACM. New York. 1971. pp. 151-158.

76. Dinur I., Regev 0. and Smyth C. The hardness of 3-uniform hypergraph coloring. In: Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November 2002.

77. Fagin R. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets // Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings. 1974. V.7. pp. 27-41.

78. Feige U. A Threshold of In n for Approximating Set Cover. Journal of the ACM. 1998, 45(4).

79. Hachai M.Yu. Classification of Committee Solutions of Majority // Pattern Recognition and Image Analysis. 1997. V.7. N2. pp. 260-265.

80. Hochbaum D. ed. Approximation Algorithms for NP-Hard Problems. PWS Publishing, Boston, 1996.

81. Johnson D.S. Approximation algorithms for combinatorial problems // Journal of Computer and System Sciences. 1974, vol. 9(3), pp. 256-278.

82. Kachalkov A.V., Rybin A.I., Khachay M.Yu. Development of the Quasar-Online Computational Site // Pattern Recognition and Image Analysis. 2003, vol. 13, no 2. pp. 217-220.

83. Khachai M.Yu., Rybin A.I. A New Estimate of the Number of Members in a Minimum Committee of a System of Linear Inequalities // Pattern Recognition and Image Analysis, 1998. Vol. 8. No. 4. pp. 491-496.

84. Khachai M.Yu. On the Combinatorial Problem Concerned with the Notion of Minimal Committee // Pattern Recognition and Image Analysis. 2001. V.ll no.l. pp. 45-46.

85. Khachay M.Yu. On an Efficient Approximation Algorithm for the Minimal Committee Problem // Pattern recognition and Image Analysis. 2003. Vol.13, no 1. pp. 43-44.

86. Khachay M.Yu. On Approximate Algorithm of a Minimal Committee of a Linear Inequalities System// Pattern Recognition and Image Analysis. 2003, vol. 13, no 3. pp. 459-464.

87. Khachay M.Yu. On Computational Complexity of the Minimal Committee of Finite Sets Problem // In: Proc. of the 2nd International Workshop 'Discrete Optiomization Methods in Production and Logistics'. Omsk-Irkutsk. 2004. pp. 176-179.

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

89. Khachay M., Poberii M. Complexity and approximability of committee polyhedral separability of sets in general position // Informática. 2009. Vol. 20, no 2. pp. 217-234.

90. Kobylkin K.S. Necessary Condition for Committee Existence // Pattern Recognition and Image Analysis. 2002. vol. 12, no. 1. pp. 26-31.

91. Kumar A., Arya S., Ramesh H. Hardness of Set Cover with Intersection 1// Lecture Notes in Computer Science. 2000, vol. 1853. pp. 624-635.

92. Lin J.H., Vitter J.S. Complexity Results on Learning by Neural Nets // Machine Learning. 1991, vol. 6. pp. 211-230.

93. Mazurov VI.D. Duality in Pattern Recognition // Pattern Recognition and Image Analysis. 1991. v. 1, no. 2. pp. 81-87.

94. Mazurov VI.D. Recognition and Choice in a Multistage Procedure of Modeling Complex Systems.// Pattern Recognition and Image Research. 1994. v.4, no. 2. pp. 87-92.

95. Mazurov VI.D. Generalized Existence in Nonequilibrium Models of Choice in Modeling Complex Systems.// Pattern Recognition and Image Research. 1995. v.5, no. 1. pp. 7-12.

96. Mazurov VI.D., Khachai M.Yu., Rybin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction // Proceedings of the Steklov Institute of mathematics. Suppl. 1, (2002). pp. 67-101.

97. Megiddo N. On the complexity of polyhedral separability // Discrete and Computational Geometry. 1988, no. 3. pp. 325-337.

98. 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.

99. Osborne M.L. The Senjority Logic: A Logic for a Committee Machine // IEEE Trans, on Comp. 1977. v.C-26, no. 12. pp. 1302-1306.У

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

101. Papadimitriou C., Yannakakis M. Optimization, approximation, and complexity classes //J. Comput. System Sci. 1991, vol. 43, no. 3. pp. 425-440.

102. Rybin A.I. On Some Sufficient Conditions of Existence of a Majority Committe // Pattern Recognition and Image Analysis. 2000. vol. 10, no. 3. pp. 297-302.

103. Vazirarri V. Approximation algorithms. Berlin: Springer, 2001. 378 p.