Содержание к диссертации
Введение
1 Комитетные решения несовместных систем ограничений 29
1.1 Основные понятия и определения 31
1.2 Условия существования комитетного решения абстрактной системы включений 37
1.3 Гиперграф максимальных совместных подсистем 40
1.4 Условия существования комитетного решения системы линейных неравенств 59
1.5 Экстремальное свойство гиперграфа м.с.п. однородной системы линейных неравенств 69
1.6 Равномерно распределенные системы неравенств 77
2 Необходимые условия существования комитета в игровой постановке 85
2.1 Постановка задачи 86
2.2 Основная теорема 88
2.3 Предельные соотношения 95
2.4 Замечания 100
3 Задача о минимальном комитете 101
3.1 Элементы теории сложности алгоритмов 103
3.2 Постановка задачи о минимальном комитете 113
3.3 Вычислительная сложность задачи о минимальном комитете 115
3.3.1 Труднорешаемость задачи MCFS 115
3.3.2 Порог аппроксимируемости для задачи MCFS 120
3.4 Задача о минимальном комитете системы линейных неравенств 124
3.4.1 Вычислительная сложность задачи MCLE 127
3.4.2 Приближенный алгоритм 133
4 Комитетные алгоритмы распознавания 141
4.1 Разделяющие комитетные конструкции 143
4.2 О минимизации эмпирического риска в классе комитетных решающих правил 149
4.2.1 Комитетные решающие правила 150
4.2.2 Оценка скорости сходимости частоты к вероятности по классу комитетных событий 156
Заключение 163
Литература 165
- Условия существования комитетного решения абстрактной системы включений
- Экстремальное свойство гиперграфа м.с.п. однородной системы линейных неравенств
- Постановка задачи о минимальном комитете
- Задача о минимальном комитете системы линейных неравенств
Введение к работе
Диссертационная работа посвящена исследованию ряда вопросов существования и оптимальности специального класса обобщенных решений несовместных систем ограничений, называемых комитетными. Кроме того в ней подробно изучаются методы и вычислительная сложность построения таких решений, а также приложения теории комитетных решений в распознавании образов.
Актуальность темы. Известно (см., например, [9, 14, 31, 99, 100]), что несовместная система ограничений (уравнений или неравенств) —
типичный объект, с которым приходится иметь дело при решении задач принятия решений, оптимизации, распознавания образов, интерпретации результатов измерений, экономической и медицинской диагностики. Во всех перечисленных случаях исследователи сталкиваются с необходимостью обобщения классического понятия решения. Широко известен подход, восходящий к работам П.Л.Чебышева, связанный с ослаблением исходных ограничений и рассмотрением решений полученной таким образом скорректированной задачи ([9, 10, 11]). К сожалению, у него имеются ограничения, одно из которых обусловлено тем, что получаемое в результате решение скорректированной задачи может не удовлетворять ни одному из условий исходной. Введение же дополнительных условий, предъявляемых к искомому решению, нередко приводит к комбинаторным постановкам, обладающим высокой вычислительной сложностью.
Наряду с традиционным подходом в течение последних 40 лет активно развивается другой, дискретный подход к коррекции несовместных систем, базирующийся на замене единичного решения коллективом "псевдорешений", каждое из которых удовлетворяет достаточно большой доле условий исследуемой задачи. Теория комитетных решений является од-
Введение
ной из математических формализации этого подхода.
Истоки понятия комитета можно найти в ранних работах по теории голосования (см., например, [71, 73]). Строгая же математическая формулировка понятия комитетного решения (комитета большинства), по-видимому, впервые была дана в работе Эйблоу и Кейлора [62] для случая системы линейных неравенств. Вместо одной точки х Є 1", удовлетворяющей всем неравенствам несовместной системы, в работе предлагалось искать конечную последовательность (х1, х2,..., xq), именуемую ее коми-тетным решением и обладающую свойством: каждому неравенству удовлетворяет более половины элементов последовательности. В том же году исследования в этом направлении начал Вл.Д. Мазуров, чьи работы заложили фундамент развивающейся теории. В частности, им была доказана теорема существования комитетного решения несовместной системы линейных неравенств и получена точная верхняя оценка числа элементов минимального комитета системы в однородном случае [27]; были введены различные обобщения понятия комитета: р-комитет, (г,р)-решение и т.п., и доказаны первые теоремы существования этих конструкций для отдельных систем ограничений.
На основании понятия комитетного решения им введено понятие разделяющего комитета [28] конечных множеств А и В в W1. Разделяющим комитетом большинства для множеств А, В была названа последовательность функций (/i, f2,..., fq), каждый элемент которой fi( ) = /(; сг) принадлежит некоторому заранее заданному параметрическому семейству функций F = {/(-;с) : Жп —> М|с Є С}, а последовательность значений параметров (с1, с2,..., cq) является комитетным решением системы неравенств
/(о; с) > 0 (а Є Л)
/(Ь;с)<0 (6 Є В).
Таким образом, разделяющий комитет обладает свойством: для каждого а Є А неравенство flip) > О выполняется для более чем q/2 его элементов; аналогично, неравенство /j(6) < 0 выполнено при любом Ь Є В более чем для половины элементов комитета. Тем самым, был предложен новый коллективный алгоритм двуклассового распознавания: в семействе F выбирается не одна, а несколько разделяющих функций и строится q однотипных алгоритмов распознавания, каждый из которых может оказаться некорректным. Алгоритм с номером г Є Ng сопоставляет
Введение
объекту S с описанием х = I(S) Є Шп число al(S) Є {0,1} (указывает принадлежность тому или иному классу) по правилу
{
1, если fi(x) > 0 0, если fi(x) < 0.
Классификация объекта, чье описание удовлетворяет уравнению fi(x) = 0, может быть произведена различными способами. В нашем случае удобно договориться, что при этом условии объект также относится классификатором fa ко второму классу.
Комитетный же алгоритм относит объект в одному из двух классов на основе правила простого большинства: к первому классу, если большинство чисел al(S) равно 1, и ко второму — в противном случае. По построению, введенный алгоритм безошибочно классифицирует множество объектов с векторами описаний из множества A U В, т.е. является корректным. Подробно проблема построения оптимальных корректных алгоритмов распознавания на базе множеств некорректных исследуется в работах, посвященных алгебраическому подходу в распознавании, опирающихся на фундаментальные статьи Ю.И. Журавлева и К.В.Рудакова [13, 14, 37, 38].
Предложенный Вл.Д. Мазуровым комитетный метод формирования алгоритмов распознавания оказался продуктивным и активно изучался рядом исследователей. Так, в работах А.И. Кривоногова [23, 24] изучались вопросы разделения аффинным комитетом не обязательно конечных множеств; Ю.А. Зуев [16]-[19] исследовал вероятностные характеристики комитета не обязательно однотипных классификаторов; В.В. Рязанов [108] предложил новые комитетные алгоритмы таксономии; в работах [1, 105] изучались комитетные алгоритмы распознавания с различными логиками подсчета голосов; в работе Н.Г. Белецкого [1] изучались также свойства геометрических предикатов, тесно связанных с комитетными конструкциями; в работах Г.С.Лбова, Н.Г. Старцевой и В.М.Неделько [25, 26] исследовалась устойчивость распознавания в классе логических решающих правил; работы [110, 112] посвящены изучению близкой к разделяющему комитету конструкции — байесовского комитетного алгоритма (bayesian committee machine), также являющейся коллективным алгоритмом распознавания (вероятностного типа), основное отличие которого от разделяющего комитета состоит в том, что члены коллектива
Введение
классификаторов обучаются независимо друг от друга и как правило на различных выборках. Комитетные алгоритмы распознавания были успешно реализованы B.C. Казанцевым в серии программных комплексов под общим названием "Квазар" [20].
Как показано в работе [29], при исследовании комитетных решений несовместной системы ограничений достаточно ограничиться комитетами, составленными из решений ее максимальных по включению совместных подсистем (м.с.п.) Работы [4, 5] посвящены изучению множества м.с.п. несовместной системы линейных неравенств, в терминах графа ее м.с.п, определение которого мы дадим ниже. В частности, в этих работах удалось связать проблему поиска комитетного решения с задачей поиска цикла нечетной длины в графе м.с.п. несовместных систем ограничений. Вл.Д. Мазуровым в работе [98] аппарат м.с.п. несовместных систем линейных неравенств был успешно применен для анализа многомерных сцен. В работах [63]-[66] исследуется вычислительная сложность задачи поиска наибольшей м.с.п. несовместной системы линейных уравнений и неравенств в терминах гиперграфа ее минимальных несовместных подсистем. Отметим, что введенное в первой главе диссертации понятие гиперграфа м.с.п. построено на принципиально иной основе и обобщает понятие графа м.с.п. [4]. В работах [40,109] получены новые достаточные условия существования комитетных решений различных систем ограничений.
Перечисленные результаты подтверждают тесную связь теории комитетных решений с другими активно развивающимися отраслями современной теоретической информатики: распознаванием образов, комбинаторной оптимизацией, теорией принятия решений и др., обосновывая актуальность темы настоящего исследования.
Цель работы. Развитие комбинаторной теории комитетных решений несовместных систем ограничений, подразумевающее:
вывод новых условий существования комитетных решений несовместных систем ограничений: в общем случае — произвольной системы абстрактных включений и, в частности, для системы линейных алгебраических неравенств;
исследование вычислительной сложности комбинаторной задачи о
Введение
минимальном по числу элементов комитетном решении: доказательство ее труднорешаемости, разбор основных специальных случаев, вывод условий эффективной аппроксимируемости, разработка полиномиальных приближенных алгоритмов и т.д.
- создание и обоснование новых комитетных алгоритмов распознавания.
Научная новизна. В работе предложен новый подход к доказательству условий существования комитетных решений несовместных систем ограничений, основанный на анализе свойств гиперграфа м.с.п. изучаемой системы. Предложенный подход позволил, в частности, получить критерий существования комитетного решения системы с заданным числом элементов и провести классификацию минимальных комитетных решений на основе изоморфизма соответствующих им подгиперграфов гиперграфа м.с.п.
С использованием аппарата линейных неравенств получены новые достаточные условия существования комитетного решения с ограниченным сверху числом элементов для несовместной системы линейных алгебраических неравенств.
Доказан критерий равномерной распределенности системы однородных линейных неравенств; решена задача о минимальном комитете в классе таких систем.
Впервые применен игровой подход для вывода условий существования комитетных решений несовместных систем ограничений. В результате решения подходящей антагонистической игры получена серия новых необходимых условий существования комитета.
Впервые исследована вычислительная сложность задачи о минимальном комитете. Доказана труднорешаемость задачи в общем виде, а также важных ее специальных случаев: задачи о минимальном комитете системы конечных множеств (MCFS), задачи о минимальном комитете системы линейных неравенств (MCLE) и некоторых других близких задач. Получена оценка порога аппроксимируемости для задачи MCFS; разработан и обоснован полиномиальный приближенный алгоритм для задачи MCLE, который затем применен для приближенного решения задачи о минимальном линейном разделяющем комитете.
Введение
Получена новая оценка емкости класса линейных комитетных решающих правил; доказано достаточное условие равномерной сходимости частот к вероятностям по классу комитетных событий.
На защиту выносятся следующие положения.
Разработан подход к доказательству условий существования и классификации комитетных решений, основанный на анализе свойств гиперграфов м.с.п. несовместных систем ограничений.
Доказаны достаточные условия существования комитета с ограниченным сверху числом элементов для несовместной системы линейных неравенств. Как следствие, получены достаточные условия существования линейного и аффинного разделяющего комитета.
Доказано необходимое и достаточное условие того, что заданная система линейных однородных неравенств равномерно распределена (по Гейлу). решена задача о минимальном комитете в классе равномерно распределенных систем неравенств.
Для произвольных натуральных чисел к и д, связанных соотношением к < q элементов, получена нижняя оценка наибольшей по мощности подсистемы, разрешимой комитетом из к элементов; оценка совпадает с верхней ценой подходящей антагонистической игры двух лиц, которую удалось решить в смешанных стратегиях; получены также асимптотические формулы для вычисления предельных значений оценок при к = q — n, q —У сх>и фиксированном натуральном п.
В рамках традиционного для теории вычислительной сложности подхода к исследованию задач комбинаторной оптимизации
показано, что задачи MCFS и MCLE — JVP-трудны, обоснована труднорешаемость некоторых близких к ним задач;
получены оценки порога эффективной аппроксимативное для задачи MCFS;
разработан и обоснован приближенный алгоритм решения задачи MCLE.
Введение
6. Получена оценка емкости класса линейных комитетных решающих правил; доказано достаточное условие равномерной сходимости частот к вероятностям по классу комитетных событий.
Методы исследования. В работе использован математический аппарат теории линейных неравенств и линейного программирования, теории графов, теории вычислительной сложности алгоритмов, теории комитетных решений, а также элементы алгебраического подхода в распознавании, теории вероятностей и теории игр.
Практическая значимость. Результаты работы по большей части носят теоретический характер и могут быть полезны специалистам по теоретической информатике. Тем не менее, некоторые результаты, например, приближенный алгоритм построения минимального разделяющего комитета, нашли применение на практике. Реализованный автором совместно с А.В.Качалковым и А.И.Рыбиным в виде СОМ-объекта qtGUN.dll, алгоритм вошел в библиотеку прикладных программ Quasar-Toolkit, разрабатываемую в секторе распознавания образов отдела математического программирования ИММ УрО РАН и представляющую собой ядро вычислительного сайта Quasar-Online (), предназначенного для решения задач распознавания "в сети". Известно несколько успешных случаев его применения при решении прикладных задач в области медицинской и геологической диагностики.
Апробация работы. Результаты работы обсуждались на семинаре "Математическое программирование" под руководством академика И.И. Еремина, докладывались на международных и всероссийских конференциях:
Международной Байкальской школе-семинаре "Методы оптимизации и их приложения" (1998, Иркутск);
Международных конференциях "Распознавание образов и анализ изображений РОАИ" (1997, Нижний Новгород), (2000, Самара), (2002, Новгород);
Международной конференции "Математическое моделирование (ММ-2001)" (2001, Самара);
Введение
Международных конференциях " Интеллектуализация обработки информации (ИОИ-2000 и ИОИ-2004)" (2000, 2004, Алушта);
Международной конференции "Алгебра и линейная оптимизация", посвященной 90-летию С.Н.Черникова (2001, Екатеринбург);
International Workshop 'Discrete Optimization Methods in Production and Logistics (DOM'2004)' (2004, Омск);
Всероссийских конференциях " Математические методы распознавания образов (ММРО)" (1997, Москва), (1999, Москва), (2001, Звенигород) и (2003, Пушино);
Всероссийских конференциях "Математическое программирование и приложения" (1997, 1999, 2003 Екатеринбург);
Всероссийской конференции "Дискретный анализ и исследование операций" (2002, Новосибирск);
Всероссийских конференциях "Алгоритмический анализ неустойчивых задач" (2001, 2004, Екатеринбург).
Публикации. Основные результаты диссертации опубликованы в работах [12], [21], [32]-[35], [45]-[59], [81], [87]-[92], [103], [104].
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, объединяющих 16 параграфов и содержащих 14 рисунков, заключения и списка литературы из 113 наименований. Объем работы составляет 175 страниц.
Введение
Краткое содержание работы. В диссертации изучаются три круга вопросов, относящихся к теории комитетов. Первый из них, рассматриваемый в главах 1 и 2, связан с выводом необходимых или достаточных условий существования комитетных решений несовместных систем ограничений. Отдельно разобраны два специальных случая: случай системы абстрактных включений
xeDj (iNm) (1)
и системы линейных неравенств.
Условия существования комитетного решения абстрактной системы включений
В параграфе приводятся теоремы существования комитетов и обобщающих их конструкций для абстрактных систем ограничений. Доказательства большинства из них конструктивны, попутно в них указываются различные верхние оценки числа элементов минимальных комитетов (коллективных решений, р-комитетов и т.д.) рассматриваемых систем включений. Большинство из приведенных в параграфе утверждений являются известными результатами, в некоторых случаях для удобства чтения они сопровождены доказательствами. В таких случаях доказательство является авторским, а утверждение снабжено ссылкой на оригинальную работу. Теорема 1.2.1 ([32]). Пусть Q = (х1, х2,... ,xq) — коллективное решение (обобщенное решение, (z,p)-комитет и т.д.) системы (1.1.1). Существует одноименное решение Q = (у1, у2,... ,yq) системы, составленное из решений ее м.с.п. Доказательство. Приведем доказательство для наиболее общего случая, когда Q является коллективным решением системы. Обозначим через Li множество L{ = {j : Pj(xl) = 1}, а через ЗІ — индексное множество объемлющей м.с.п. (Li С Jj). Пусть у1 произвольное решение м.с.п. Jj. Последовательность Q = (у1, у2,..., yq) — искомое коллективное решение системы (1.1.1). В самом деле, по выбору множеств Jj, Pj(yl) Фз(х%) Для всех і и Зі следовательно, Теорема позволит нам, в частности, в задаче (1.1.7) поиска минимального комитета системы (1.1.1) понизить размерность пространства, полагая ненулевыми лишь те компоненты вектора z, для которых векторы if1 попарно несравнимы, то есть удовлетворяют условию: (V i ф і2) (Зі Є Nm) : ipj = 1, P? = -I Следствием приведенной ниже теоремы является нечетность числа элементов минимального комитетного решения произвольной несовместной системы ограничений. В дальнейших рассуждениях мы также иногда будем полагать, что рассматриваемые нами комитетные решения имеют нечетное число элементов. Теорема 1.2.2 ([27]). Пусть Q — (ж1, ж2,..., х2к) при к Є N — комитет системы (1.1.1). Последовательность Q = (ж1, я2,..., x2k l) также является комитетом этой системы. Определение 1.2.1. Системой представителей для множеств D\, ..., Dm называется конечная последовательность М = (ж1, ..., хт), хг Є X такая, что Xі Д. Система представителей М называется системой различных представителей, если хг ф ж-7 для каждых і ф j. Обозначим через L(M) = {хг г Є Nm} множество элементов М. Числом элементов системы представителей М назовем L(M). Система (1.1.1), очевидно, совместна тогда и только тогда, когда найдется система представителей М множеств Di,..., Dm, состоящая из одного элемента. Справедливо и более общее утверждение. Теорема 1.2.3 ([31],[104]). Если для всякого j Є Nm найдется система представителей Mj множеств D\ П D ..., Dm П Dj из не более чем г элементов (г 1), то система (1.1.1) разрешима р-комитетом при р = (1/г). В частности, при г = 2 система (1.1.1) разрешима комитетом из не более чем 2т — 1 элемента. Доказательство. Пусть Mi,...,Mm — системы представителей, указанные в условии теоремы. Пусть L(Mj) = {ж],..., я -J}, rj г.
Убедимся что последовательность: 1.2. Условия существования комитетного решения абстрактной системы включений 39 является р-комитетом системы (1.1.1) при р = (1/V). Заметим, что по выбору Mj, равенство j( ) = 1 справедливо при произвольном j Є Nm и А; Є Nr.. Кроме того для каждого і Є Nm \ {j} найдется номер k = k(i,j) такой, что у(жг- ) = 1. Обозначим элементы Q через у1,..., угтп. По определению р-комитета достаточно для каждого j Nm проверить выполнение неравенства: приведенных выше рассуждений следует, что гтп X] Vibf) г + m - 1 - (тп - 1)(г - 1) = т(2 - г) + 2 (г - 1) т(2 - г), г=1 что завершает доказательство первого утверждения теоремы. Доказательство второго утверждения следует из первого и теоремы 1.2.2. Теорема 1.2.4 ([31]). Если любые к множеств системы (1.1.1) пересекаются и к/т р, то система разрешима р-комитетом. Нетрудно показать, что условия теорем 1.2.1 и 1.2.3 не являются необходимыми для существования р-комитета. Действительно, рассмотрим, например, систему (1.1.1) с множествами: D\ = {1,2,3}, 1 — {1,4}, D3 = {2,4}, 4 = {3,4}. Видно, что Q = (1,2,3,4,4) является ее комитетом (р-комитетом при р = (3/5) — є и произвольном є 0), тем не менее для системы не выполнено условие теоремы 1.2.1 при Г = 2 И теоремы 1.2.3 при к = 3. Сформулируем также простое необходимое условие существования р-комитета. Теорема 1.2.5 ([32]). Пусть последовательность К = (x1,...,xq) — р-комитет системы (1.1.1), тогда она содержит элемент такой хг, что \{j : Xі GDj}\ рт. Доказательство. Пусть, от противного, \{j : х1 Є Dj}\ pm для каждого і Є Ng. Как обычно, сопоставим каждому х1 вектор рг Є {-1,1}771 такой, что Поскольку К является р-комитетом, то Y l=i f) (2р— 1) 7 для каждого І Є Nm. Следовательно, ХЛІї ]СІ=І У7} п(2р — 1) ?. С другой стороны, по предположению, YlT=i P) — (2p — l)m для каждого і Є N9, значит, Ю=і S =i V3} #(2p — l)m. Таким образом, предположение неверно, что и доказывает утверждение. Замечание 1.2.1. Из теоремы непосредственно следует наличие в системе, разрешимой р-комитетом максимальной совместной подсистемы мощности, большей, чем pm, а в системе, разрешимой комитетом из 2k — 1 элемента — м.с.п. мощности, не меньшей к/(2к — 1)пг. В главе 2 мы рассмотрим обобщение теоремы для случая р-комитета при р = 1/2. в которой не все множества Dj пусты, тесно связана с задачей изучения структуры множества ее максимальных совместных подсистем (м.с.п.). Последнюю задачу удобно формулировать в терминах теории графов. Определим понятие гиперграфа м.с.п. системы (1.3.1) и рассмотрим некоторые его свойства, связанные с комитетной разрешимостью исследуемой системы включений. Определение 1.3.1. Гиперграфом м.с.п. системы (1.3.1) назовем конечный гиперграф G = (V, Е), где V = {J\,..., JT} — множество индексов
Экстремальное свойство гиперграфа м.с.п. однородной системы линейных неравенств
В этом параграфе мы опишем свойства гиперграфа м.с.п. системы линейных однородных неравенств, заданной на плоскости. Пусть задана система: где а,-, х Є М2 и среди векторов а, нет нулевых и противоположно направленных. Пусть {її, І2,..., 1Р} — множество индексов м.с.п. системы (1.5.1). Как упоминалось ранее, р нечетно и равно числу элементов минимального комитета, разрешающего систему, будем полагать его равным 2t + 1. Пусть Gi = (V2, Е2) — гиперграф м.с.п. системы (1.5.1). Ниже мы покажем, что он обладает своего рода экстремальным свойством относительно числа элементов минимального комитета системы: множество его ребер максимально по включению среди множеств ребер гиперграфов порядка р м.с.п. произвольных систем (1.1.1), разрешимых минимальным комитетом из р элементов. Рассмотрим булеву матрицу М размера m х р, элемент rriji которой определяется соотношением: Перенумеруем неравенства и индексы м.с.п. системы (1.5.1) так, чтобы матрица М приобрела удобный для рассмотрения вид. Для этого сопоставим каждому неравенству единичный направляющий вектор Cj прямой выбрав из двух возможных тот, при движении в направлении которого по указанной прямой полуплоскость {х \ (dj,x) 0} остается справа. Обозначим индексы м.с.п. системы (1.5.1) символами І\, І2,..., Ір в порядке возрастания полярного угла направляющего вектора левой границы конуса решений соответствующей м.с.п.. Пронумеруем неравенства системы (1.5.1) натуральными числами 1, 2,.. . m в порядке возрастания полярного угла сопоставленных им направляющих векторов Cj, считая, что номер 1 присвоен направляющему вектору левой границы конуса решений м.с.п. с индексом 1\ (см. Рис. 1.5.4). При выбранной нумерации неравенств и индексов м.с.п. системы (1.5.1) матрица М примет следующий вид: Видно, что каждое неравенство входит ровно в t 4- 1 индекс м.с.п., причем, поскольку в матрице М ровно р = 2t + 1 попарно различных строк, то неравенства системы (1.5.1) разбиваются пар классов эквивалентности. А именно, неравенства с номерами j\ и J2 входят в одни и те же индексы м.с.п. тогда и только тогда, когда они являются представителями одного класса (соответственно, когда строки матрицы В с номерами з\ и ji совпадают). Пронумеруем классы эквивалентности неравенств системы (1.5.1) в естественном порядке числами 1,2,... ,р. Итак, G i = (1 2,-) — гиперграф м.с.п. системы (1.5.1) на плоскости, Уі — {1\, Ip\- Для описания множества Еч достаточно оставить в рассмотрении по одному неравенству из каждого класса эквивалентности, рассматривая вместо матрицы М квадратную булеву матрицу М размера р х р : Легко видеть, что, например, вершина Д входит в двухэлементные ребра {Д, It+i} и {Д, Д+г}- Следующее простое предложение определяет условие на номера вершин, входящих в некоторое подмножество и С V2, необходимое и достаточное для того, чтобы и Є Еі. Ниже всегда будем полагать, что запись: и = {1 ,..., Д8} подразумевает выполнение неравенств Д «2 is Утверждение 1.5.1 ([46]). Подмножество вершин {Д1? Д2..., /г-5} гиперграфа G2 является его ребром тогда и только тогда, когда для каою-дого fcGNs выполняется условие Доказательство. Достаточность очевидна ввиду особенности строения матрицы М .
Необходимость. Пусть {Дг,..., Ug] Є 2- Тогда UJUi - т по определению Gi- Покажем, например, что i i — Д t + 1. Заметим, что в м.с.п. с индексом Д входят все неравенства-представители классов с номерами: к, (к (mod р)) + 1,..., (к + (t — 1)) (mod р) + 1 и только они. Рассмотрим произвольное неравенство с номером г из класса ((Д + t) (mod р)) + 1. Видно, что т 1 , значит, найдется к Є {2, 3,..., s}, что г Є Іік. Следовательно, все неравенства из указанного класса входят в м.с.п. с индексом 1{к, т.е. либо Д = ((Д +1) (mod р)) + 1, либо найдется с Є {0,1, ..., —1} такое, что ((Д+с) (mod р)) + 1 = ((Д+) (mod р)) + 1. В первом случае Д — 1 = (Д — 1) (mod р) = (Д + t) (mod р), откуда Д — г-! = (Д — Д) (mod р) = (t + 1) (mod р) = t + 1. Во втором Д — Д = Из доказанного утверждения следует, в частности, что если число р достаточно велико, то / содержит ребра, не содержащие в себе двухэ Ц лементных ребер. Например, гиперграф м.с.п. системы, изображенной на рис. 1.5.4, содержит ребро {/1,/4,/7}) не содержащее в себе двухэлементные ребра. Теорема 1.5.1 ([46]). Пусть ф — гомоморфизм гиперграфа Gi м.с.п. системы линейных однородных неравенств (1.5.1) на плоскости в гиперграф G = (V:E) м.с.п. системы включений (1.1.1) и существует {Ikl, 42..., ha} С V2 такое, что {/ ,/ ..., hs} І Е2, а {ф(Ікі), , ф(Ікз) } Є Е, тогда число элементов минимального комитета, разрешающего систему (1.1.1), меньше р. Доказательство. Воспользуемся следующим легко проверяемым пред ложением: пусть J\, J2,..., J2S+1 — цепь в гиперграфе G, т.е. Е содержит ( ребра {Ji, J2}, ... ,{Js_i, Js}. Тогда система (1.1.1) разрешима комитетом, составленным из решений м.с.п.-вершин цепи, взятых для каждой по одному тогда и только тогда, когда {J\, J3,..., J2s+i} Є Е. Пусть {Ikl, Ik2, ...,hs}cV2 такое, что {Ikl, Ik2,..., Iks} E2 и {ф(Ікі),ф(Ік2), - , Ф(Ік3)} Є Е. В силу утверждения 1.5.1, найдется такое j Ns, что ( (mod 8))+1) - kj) (mod p) t + 1. Поскольку p = 2t + 1, то такое j единственно. He уменьшая общности, (\ можно полагать, что 1 = к\ к2 ... ks = к и (1 — к) (mod р) +1, тем самым, к t. Рассмотрим вершины гиперграфа G2 : /1, It+2, /2,---, It+k, Ik- Нетрудно видеть, что они образуют в нем простую цепь (Е2 содержит ребра {/i, It+2}, {It+2, /2}, - -, {It+k, h}), следовательно,
Постановка задачи о минимальном комитете
Пусть заданы множество X и набор D\, D2,..., Dm его непустых подмножеств. Рассмотрим, как и ранее, абстрактную систему включений Система (3.2.1) не обязательно совместна, т.е. допустимо выполнение соотношения Р) Dj = 0. Как и в предыдущих главах, назовем комитетным решением с q элементами системы (3.2.1) (или просто комитетом) конечную последовательность Q = [х1, х2,..., re9) , удовлетворяющую условию при каждом j Є NTO. Введем в рассмотрение несколько задач комбинаторной оптимизации. Заданы множество X и набор его непустых подмножеств Di, D2, ...,Dm. Требуется найти комитетное решение системы (3.2.1) с наименьшим возможным q (или установить, что система не имеет комитетных решений). Удобно вслед за [31] переформулировать задачу МС в терминах целочисленного линейного программирования. Пусть множества J\, J2,..., J? суть индексные множества всех максимальных по включению совместных подсистем (м.с.п.) системы (3.2.1). Очевидно, система совместна тогда и только тогда, когда Т = 1, в противном случае 1 Т 2т. Определим две тп х Т матрицы инциденций А и В по правилу Здесь ей/ — векторы из единиц, принадлежащие пространствам Ет и Ет соответственно. Известна следующая Теорема 3.2.1 ([9]). Задачи МС, (3.2.2) и (3.2.3) разрешимы или неразрешимы одновременно. Множества оптимальных решений задач (3.2.2) и (3.2.3) изоморфно вкладываются в множество решений задачи МС (минимальных по числу элементов комитетных решений). Наряду с задачей МС мы рассмотрим два ее частных случая 1. Задачу МС, в которой множество X и все его подмножества Dj — конечны (мы будем называть такую задачу задачей MCFS). В параграфе 3.3 мы покажем, что для нее теорема 3.2.1 может быть уточнена. Там же мы покажем, что этот частный случай задачи о минимальном комитете является JV-P-трудной задачей, откуда, в частности, будет следовать труднорешаемость задачи МС и общем случае. Кроме того мы покажем, что труднорешаемой является и задача ее приближенного решения с заданной точностью. 2. Задачу МС, в которой множество X является конечномерным числовым пространством Qn, а подмножества Dj — его полупространствами. Эту задачу мы назовем задачей о минимальном комитете системы линейных неравенств или сокращенно MCLE. В параграфе 3.4 мы покажем, что она также iVP-трудна, рассмотрим приближенный алгоритм ее решения и перечислим ее полиномиально разрешимые подклассы. В этом параграфе мы обоснуем труднорешаемость задачи МС. Для этого мы покажем, что труднорешаемым является ее частный случай — задача MCFS, в которой все включения задаются конечными множествами. Далее, мы покажем, что эта задача и соответствующие ей задачи (3.2.2) и (3.2.3) в некотором смысле "одинаково труднорешаемы".
В завершении параграфа мы покажем, что при разумном предположении такая задача не может быть решена приближенно за полиномиальное время с достаточной точностью и укажем соответствующую границу. (3.2.1) с минимальным числом элементов (или показать, что система не имеет комитетных решений). Договоримся о способе кодирования условия и решения задачи. Пусть условие индивидуальной задачи MCFS задается т х р матрицей С из 1 и —1, причем Без ограничения общности, можем полагать, что для произвольного комитета Q = (у1, у2,..., yq) найдутся натуральные числа к р, В дальнейших рассуждениях нас не будет интересовать порядок элементов последовательности Q, поэтому договоримся представлять ее в виде характерном для мультимножеств. Здесь числа qj обозначают кратности элементов хгк Теорема 3.3.1 ([47]). Задача MCFS NP-трудна. Доказательство. Достаточно доказать N Р-полноту следующей задачи распознавания свойств: Заданы подмножества D\, D2,..., Dm конечного множества X и число к Є N. Определить, существует ли комитет системы (3.2.1) с числом элементов, не превосходящим 2к — 1. Воспользуемся стандартным приемом доказательства и покажем полиномиальную сводимость к поставленной задаче (по Карпу) задачи "МНОЖЕСТВО ПРЕДСТАВИТЕЛЕЙ", iVP-полнота которой доказана [6]. Заданы подмножества С\,Сч,... ,Сп конечного множества S и число к. Определить, существует ли система представителей М для заданных подмножеств с числом элементов, не большим к. Для доказательства полиномиальной сводимости достаточно для произвольного конечного множества S, набора его подмножеств С\,..., Сп и числа к за полиномиальное время от длины записи исходной задачи указать множество X и его подмножества D\,..., Dm такие, что множества Ci,..., Сп обладают системой представителей с числом элементов не большим к тогда и только тогда, когда система (3.2.1) обладает комитетом с числом элементов, не превосходящим 2к — 1. Итак, пусть S = {s1, s2,..., s }, заданы Сі,..., Сп С S и число А; Є N. Выберем s S и положим X = S U {s0}, а т — п + 1. Положим Эти построения, очевидно, можно проделать за время 0(m-\). В самом деле, не ограничивая общности, можно полагать, что МНОЖЕСТВО ПРЕДСТАВИТЕЛЕЙ задано с помощью n t—разрядных двоичных чисел (необходимо также закодировать число &, но в нашем случае это не принципиально). Для того, чтобы закодировать условие задачи КОМИТЕТ согласно (3.3.2) достаточно приписать к каждому из них 1-й бит и добавить одно число из t установленных битов.
Задача о минимальном комитете системы линейных неравенств
Непосредственными следствиями леммы и теорем 3.3.3, 3.3.4 являются следующие теоремы. Теорема 3.3.5. Если справедлива гипотеза Р Ф" NP, то не существует приближенного алгоритма для задачи MCFS с точностью аппроксимации log(m — 1). Доказательство. В самом деле, предположим от противного, что существует приближенный алгоритм Л, находящий допустимое решение с точностью \ log(m— 1) задачи MCFS с т включениями. Тогда, по лемме, для задачи SET COVER существует приближенный алгоритм, строящий допустимое покрытие, не более чем в log(m — 1) раз превосходящее по мощности оптимальное (при условии \S\ = m — 1), что, по теореме 3.3.3, влечет равенство Р = NP. Найденное противоречие доказывает теорему. Аналогичным образом может быть доказана Теорема 3.3.6 ([58]). Если справедливо условие NP ТШЕ(п0{1оё1оёп)), то для произвольного є 0 не существует приближенного алгоритма решения задачи MCFS с точностью аппроксимации (1 — є) ln(m — 1). Пусть множество X совпадает с множеством Qn векторов с рациональными коэффициентами, а подмножества Dj являются полупространствами: В этом случае система (3.2.1) примет вид Еще одним важным частным случаем задачи МС является Задача "МИНИМАЛЬНЫЙ КОМИТЕТ векторы Требуется найти комитетное решение (комитет) системы (3.4.1) с наименьшим числом элементов (или показать, что система не имеет комитетных решений) Задача MCLE вызывает интерес как минимум по двум причинам. С одной стороны, как мы увидим в следующей главе, она имеет очевидное приложение при обучении распознаванию образов. К задаче MCLE приводит подход к обучению распознаванию образов, связанный с минимизацией емкости класса (VC-dimension) линейных (аффинных) комитет-ных решающих правил. С другой стороны, задача MCLE, в отличие от изученной ранее задачи MCFS, не допускает традиционный подход исследования, основанный на сведении задачи к эквивалентной задаче целочисленной оптимизации (3.2.2) и изучении свойств последней. Нетрудно убедиться, что сводимость задачи MCLE к задаче (3.2.2) (или (3.2.3)) не является полиномиальной. В самом деле, для перехода к задаче (3.2.2) требуется найти все м.с.п. системы (3.4.1). Однако, как известно, задача поиска всех м.с.п. системы линейных неравенств труднорешаема. Задача Требуется найти наибольшую по мощности м.с.п. системы (3.4.1). Справедлива Теорема 3.4.1 ([86]). Задача DENSEST HEMISPHERE NP-трудна.
Таким образом, традиционная схема исследования вычислительной сложности задачи MCLE в общем случае не эффективна. Ниже мы покажем, что задача MCLE iVP-трудна и опишем приближенный полиномиальный алгоритм ее решения, базируясь исключительно на геометрических свойствах семейства полупространств в конечномерном векторном пространстве. Заметим, что традиционный подход, основанный на анализе задач (3.2.2)-(3.2.3) может быть тем не менее применен при исследовании следующей близкой к MCLE задачи комбинаторной оптимизации: Задача и q, векторы так, что последовательность Q = (а;1,ж2,... ,xq) является комитетом системы (3.4.1). Требуется найти комитет Q = (у1, у2,..., yq ) с наименьшим возможным q q, в котором В самом деле, проведем рассуждения, аналогичные проведенным в параграфе 3.2. Рассмотрим m х q матрицы инциденций А и В , элементы которых определим по правилу: Получим матрицы А и В путем исключения попарно доминируемых столбцов матриц А и В\ обозначим через г число их столбцов и рассмотрим задачи аналогичные задачам (3.2.2) и (3.2.3), соответственно. Учитывая, что проведенные построения могут быть произведены за полиномиальное от длины записи задачи COMIMP время, получаем доказываемое аналогично теореме 3.3.2 Утверждение 3.4.1. Задачи COMIMP (3.4.2) и (3.4.3) полиномиально эквивалентны. В этом разделе мы убедимся, что определенная выше задача MCLE в общем случае труднорешаема. Далее мы опишем также некоторые частные случаи, при которых задача полиномиально разрешима и рассмотрим приближенный алгоритм ее решения. Теорема 3.4.2. Задача MCLE NP-mpydna. Доказательство теоремы будет следовать из двух вспомогательных утверждений, при этом нам потребуется рассмотреть несколько дополнительных комбинаторных задач. Задача "КОМИТЕТ ИЗ 3-Х ЭЛЕМЕНТОВ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ" (3-COMLE): Заданы натуральные числа т и п 1 и векторы а1,а2,...,ат Є Qn. Существует ли комитетное решение системы (3.4.1), состоящее из трех элементов? Утверлсдение 3.4.2. Задача 3-C0MLE сводится по Тьюрингу к задаче MCLE. Доказательство. Рассмотрим произвольную индивидуальную задачу задачи 3-C0MLE — задачу поиска комитета из 3-х элементов фиксированной системы (3.4.1). Естественным образом сопоставим ей индивидуальную задачу MCLE — задачу о минимальном комитете той же системы неравенств. Применим произвольный алгоритм решения задачи MCLE. Если система не имеет комитетных решений — то ответ в исходной задаче также "нет". Пусть Q = (х1, х2,..., xq) — минимальный комитет системы (3.4.1), если q 3, то, очевидно, ответ исходной задачи — "нет". Если q — 3, то Q, очевидно, является искомым решением исходной задачи 3-COMLE (ответ в которой в данном случае — "да"). Отдельно рассмотрим случай q = 1, когда Q = (х1) (как отмечалось выше, минимальный комитет не может содержать четное число элементов). Найдем вектор z из условия (aj,z) 0 (iGNm).
Похожие диссертации на Комитетные решения несовместных систем ограничений и методы обучения распознаванию
