Введение к работе
Диссертационная работа посвящена исследованию вычислительной сложности и аппроксимируемости задач комбинаторной оптимизации, связанных с комитетной полиэдральной отделимостью конечных множеств. Кроме того, в работе исследуется вопрос обоснования обобщающей способности комитетных кусочно-линейных решающих правил в терминах классической теории Вапника-Червоненкиса.
Несовместные системы ограничений (уравнений или неравенств)
— типичный объект, возникающий при решении задач принятия ре
шений, оптимизации и классификации, математического программи
рования и распознавания образов, экономической и медицинской ди
агностики и т.д. (см., например, работы И.И.Еремина, Вл.Д. Мазу
рова1, Ю.И. Журавлева2). Во всех перечисленных случаях возника
ет необходимость обобщения классического понятия решения. Тра
диционным является подход, восходящий к работам П.Л. Чебышева,
основанный на непрерывной аппроксимации и заключающийся в ос
лаблении ограничений исходной задачи, при котором достигается
их совокупная непротиворечивость. Тогда в качестве обобщенного
решения рассматривается решение скорректированной задачи. Од
нако такой вид обобщения обладает существенным недостатком: стро
ящееся точное решение скорректированной задачи может не удов
летворять ни одному из условий исходной.
Второй подход к коррекции несовместных систем ограничений
— дискретный, при котором привычное, сосредоточенное в одном
элементе решение заменяется коллективом "квазирешений", каждое
из которых удовлетворяет достаточно большой доле условий иссле
дуемой задачи, являясь, по сути, решением некоторой непротиво
речивой подсистемы исходной системы ограничений. Одной из ма
тематических формализации дискретного подхода является теория
комитетных решений.
Понятие комитета впервые появилось в работах по распознаванию образов: в совместной статье Эйблоу и Кейлора3 было введено понятие комитетного решения для системы строгих однородных ли-
1Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. - М.: Наука, 1979.
Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. Вып. 33. 1978. С. 5—68.
3Ablow СМ., Kaylor D.J. Inconsistent Homogeneous Linear Inequalities // Bull. Amer. Math. Soc, 1965, vol. 71, no. 5, p. 724.
нейных неравенств
(cj,x)>0 (jGNm). (1)
Конечная последовательность (жі,...,жд) С К называется комитетом системы (1), если всякому неравенству удовлетворяет более половины ее элементов.
В более общем виде различные обобщения понятия решения на случай несовместных систем были введены в екатеринбургской школе распознавания. Современная теория комитетных конструкций опирается на результаты, полученные Вл.Д. Мазуровым 4. Им было доказано необходимое и достаточное условие существования комитета несовместной системы линейных неравенств, получены первые оценки числа членов минимального комитета; введены обобщения понятия комитета (р-комитет, (г,р)-комитет, z-решение и т.д.) и получены условия существования этих конструкций для систем линейных неравенств и некоторых более общих систем включений; предложены и обоснованы вычислительные схемы для построения р-ко-митетов, в том числе минимальных.
Каждой комитетной конструкции соответствует понятие разделяющей комитетной конструкции и алгоритм распознавания. Согласно введенному Вл.Д. Мазуровым определению, разделяющим комитетом (большинства) для конечных множеств А, В из R называется последовательность функций Q = (/1,/2,---,/5), принадлежащих заданному параметрическому семейству
F = {!{ с) : сєС}с{М^М},
таких, что в каждой точке множества А более половины функций последовательности Q принимает положительное значение, а в каждой точке множества В, напротив, отрицательное. При этом коми-тетный алгоритм распознавания (решающее правило) подразумевает принятие решения об отнесении объекта к одному из двух классов на основе значения не одной функции из класса F, а последовательности функций Q С F. Для произвольного объекта s Є S с результатом измерений x(s) Є К вычисляется q значений Wj(s) Є О = {0,1} по правилу
J 1, если Мх) > О
I 0, если fi(x) < О,
Мазуров Вл.Д. Теория и приложения комитетных конструкций // Методы, для нестационарных задач математического программирования. — Свердловск: УНЦ АН СССР, 1979. С.31-63.
после чего объект относится к первому классу, если большинство чисел uji(s) принимает значение 1, и ко второму — в противном случае, то есть решение принимается по правилу простого большинства. Заметим, что каждая из функций /j, рассматриваемая в отдельности, порождает алгоритм распознавания, который, в свою очередь, может оказаться некорректным, в то время как построенный из этих функций комитетный алгоритм распознавания безошибочно классифицирует множество объектов с результатами измерений из множества A U В, то есть является корректным на этом множестве.
Известный алгебраический подход к решению задач распознавания образов опирается на фундаментальные результаты Ю.И. Журавлева. Важное место в его работах занимает проблема построения корректных алгоритмов распознавания над множествами некорректных5. Развитие алгебраического подхода к синтезу корректных алгоритмов распознавания было продолжено в работах К.В. Рудакова, В.В. Рязанова, Е.В. Дюковой, К.В. Воронцова и др.
Актуальность темы. С 80-х годов прошлого века у исследователей возник интерес к изучению вычислительной сложности комбинаторных задач, связанных с процедурой обучения распознаванию образов. Приведем общую постановку задачи обучения распознаванию образов, для чего зафиксируем измеримое пространство (X х Сі, А, Р), где X — множество результатов измерений, Сі = {0,1} — множество названий образов (классов), Р — вероятностная мера, и зададимся множеством Т = {/(, а) : X —> Сі : а Є Л} решающих правил, причем
Sa = {(ж, uj) : f(x, а) у^ и;} Є Л (а Є Л),
то есть является событием. Задачей обучения распознаванию образов называется оптимизационная задача
minP(a)=min / [f{x,a)—uj)'2dP{x,uj), (2)
аЄЛ аЄЛ J
где вероятностная мера Р считается неизвестной и заданной с точностью до конечной выборки (жі, wi),..., {xi,uj{). Для аппроксима-
Журавлев Ю.И. Корректные алгебры над множествами некорректных алгоритмов. I-III // Кибернетика. 1977, №4, С. 14-21; 1977, №6, С. 21-27; 1978, №2, С. 35-43.
ции неполностью формализованной задачи (2) традиционно рассматривается задача минимизации эмпирического риска:
1 '
min{z/(a) = - У2(ші - f(xu а))2}, (3)
аЄЛ I z—'
і=1
где (жі, wi),..., {xi,uj{) — заданная выборка, Т = {/(, а) : а Є Л} — класс решающих правил. Как известно6, точность аппроксимации монотонно убывает с ростом емкости VCD класса решающих правил. В рамках алгебраического подхода к решению задач распознавания исследуются классы, содержащие корректные на выборке решающие правила. Для таких классов повышение качества обучения может быть связано с минимизацией емкости класса, то есть с решением задачи
nan{VCD(F') : min{z/(a) : f Є Ґ} = 0, Ґ С J7}. (4)
Исследуемая в работе задача о минимальном аффинном разделяющем комитете (MASC) является частным случаем задачи (4), в котором класс Т является классом комитетных кусочно-линейных решающих правил.
Задача "Минимальный аффинный разделяющий комитет".
Заданы конечные множества А, В С Q, А = {а\,. .., ат1} и В = {&!,. .., Ьт2}. Требуется указать аффинный комитет с наименьшим числом элементов, разделяющий множества А и В.
Таким образом, актуальность исследования задачи MASC подтверждается ее тесной связью с процедурой обучения распознаванию образов и важностью построения оптимальных (с точки зрения теории структурной минимизации риска) комитетных кусочно-линейных решающих правил.
Вычислительная сложность задачи о минимальном по числу элементов комитете впервые была исследована М.Ю. Хачаем. Им доказана труднорешаемость задачи в общем случае и основных ее специальных случаев: задачи о минимальном комитете системы конечных множеств (MCFS), задачи о минимальном комитете системы линейных неравенств (MCLE) и тесно связанной с ней задачи MASC. Ряд
6Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. —М.: Наука, 1974. 416 с.
работ посвящен изучению вопроса эффективной аппроксимируемости обозначенных выше задач: получена оценка порога аппроксимируемости для задач MCFS и MASC, разработаны и обоснованы полиномиальные приближенные алгоритмы решения задач MCLE, MASC и некоторых их частных случаев.
Поскольку в общем случае задача MASC является труднореша-емой и трудноаппроксимируемой, то традиционный для теории вычислительной сложности подход предполагает рассмотрение частных случаев задачи, исследование их вычислительной сложности и поиск полиномиально разрешимых подклассов.
Известно, что многие ЖР-трудные в общем случае задачи комбинаторной оптимизации становятся полиномиально (или псевдо-полиномиально) разрешимыми при дополнительных ограничениях: при фиксации размерности пространства, числа ограничений и т.п. Также известно, что задача MASC, заданная в одномерном пространстве, может быть решена за полиномиальное время. Поэтому интерес вызывает исследование вычислительной сложности задачи о минимальном аффинном разделяющем комитете в пространствах фиксированной размерности, большей единицы (MASC(n)). Ранее показано, что задача MASC(n) ЛГР-трудна , однако для обоснования этого факта рассматриваются частные случаи задачи MASC(n), в которых разделяемые множества находятся не в общем положении, то есть доказательство существенным образом опирается на вырожденность разделяемых множеств. Для того, чтобы исключить из рассмотрения подобные частные случаи задачи MASC(n), в диссертационной работе вводится дополнительное ограничение на разделяемые множества и исследуется вычислительная сложность и аппроксимируемость задачи о минимальном аффинном разделяющем комитете, сформулированной в пространстве фиксированной размерности п > 1, при условии общности положения разделяемых множеств (MASC-GP(n)). Кроме того, актуальность изучения задачи MASC-GP(n) обусловлена указанной ранее связью задачи о минимальном аффинном разделяющем комитете с задачей обучения распознаванию образов, поскольку последняя всегда рассматривается в пространстве фиксированной размерности.
7Khachai 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.
Цель работы. Развитие комбинаторной теории комитетных решений несовместных систем ограничений, подразумевающее:
исследование вычислительной сложности комбинаторной задачи о минимальном по числу элементов аффинном разделяющем комитете в пространствах фиксированной размерности, большей единицы, при условии общности положения разделяемых множеств (MASC-GP(n));
разработку и обоснование полиномиального приближенного алгоритма решения задачи MASC-GP(n);
оценку емкости VCD класса аффинных комитетных решающих правил с ограниченным числом элементов.
Методы исследования. В работе использован математический аппарат теории вычислительной сложности и, в частности, подход, базирующийся на полиномиальной сводимости; математический аппарат теории линейных неравенств, линейного программирования и теории графов; элементы вычислительной геометрии.
Научная новизна. Впервые исследован вопрос о вычислительной сложности задачи о минимальном по числу элементов аффинном разделяющем комитете в пространствах фиксированной размерности, большей единицы, при дополнительном условии общности положения разделяемых множеств (MASC-GP(n)) и доказано, что задача остается труднорешаемой. Разработан и обоснован полиномиальный приближенный алгоритм решения задачи MASC-GP(n).
Доказана МAX-SNР-трудностъ задач о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN-РС) и о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности для множеств в общем положении (MASC-GP(n)). Таким образом обоснована невозможность построения для этих задач полиномиальной аппроксимационной схемы, в предположении Р =/= NP.
Получена новая оценка емкости VCD класса аффинных комитетных решающих правил с ограниченным числом элементов.
На защиту выносятся следующие результаты.
Доказано, что задача об аффинном разделяющем комитете на плоскости для множеств в общем положении, сформулированная в виде задачи верификации свойства, - задача PASC-GP является ЖР-полной в сильном смысле. Обоснована трудноре-шаемость (в сильном смысле) задачи о минимальном аффинном разделяющем комитете в пространствах фиксированной размерности, большей единицы, при условии общности положения разделяемых множеств (MASC-GP(n)).
Разработан и обоснован приближенный алгоритм решения задачи MASC-GP(n), обладающий в общем случае точностью аппроксимации 0{т/п), а при справедливости некоторого дополнительного предположения — точностью O(logm).
Доказана MAX-SWP-трудность задач о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN-PC) и о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности при условии общности положения разделяемых множеств (MASC-GP(n)) и, следовательно, невозможность построения для этих задач полиномиальной аппроксимационной схемы, если Р =/= NP.
Получены верхняя и нижняя оценки емкости VCD{Tq) класса Tq аффинных комитетных решающих правил, состоящих из не более чем 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 страницы.
