Комитетные решения несовместных систем ограничений и методы обучения распознаванию

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

Актуальность темы

Известно (см., например, [9, 14, 31, 99, 100]), что несовместная система ограничений (уравнений или неравенств) — типичный объект, с которым приходится иметь дело при решении задач принятия решений, оптимизации, распознавания образов, интерпретации результатов измерений, экономической и медицинской диагностики. Во всех перечисленных случаях исследователи сталкиваются с необходимостью обобщения классического понятия решения. Широко известен подход, восходящий к работам П. Л. Чебышева, связанный с ослаблением исходных ограничений и рассмотрением решений полученной таким образом скорректированной задачи ([9, 10, 11]). К сожалению, у него имеются ограничения, одно из которых обусловлено тем, что получаемое в результате решение скорректированной задачи может не удовлетворять ни одному из условий исходной.

Введение

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

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

Истоки понятия комитета можно найти в ранних работах по теории голосования (см., например, [71, 73]). Строгая же математическая формулировка понятия комитетного решения (комитета большинства), по-видимому, впервые была дана в работе Эйблоу и Кейлора [62] для случая системы линейных неравенств. Вместо одной точки ж0 G М&trade-, удовлетворяющей всем неравенствам несовместной системы, в работе предлагалось искать конечную последовательность (х1, х2,., xq), именуемую ее коми-тетным решением и обладающую свойством: каждому неравенству удовлетворяет более половины элементов последовательности. В том же году исследования в этом направлении начал Вл.Д. Мазуров, чьи работы заложили фундамент развивающейся теории. В частности, им была доказана теорема существования комитетного решения несовместной системы линейных неравенств и получена точная верхняя оценка числа элементов минимального комитета системы в однородном случае [27]- были введены различные обобщения понятия комитета: р-комитет, (г, р)-решение и т. п., и доказаны первые теоремы существования этих конструкций для отдельных систем ограничений.

На основании понятия комитетного решения им введено понятие разделяющего комитета [28] конечных множеств, А и В в М&trade-. Разделяющим комитетом большинства для множеств А, В была названа последовательность функций (/i, /2,., fq), каждый элемент которой /Д •) = /(•- сг) принадлежит некоторому заранее заданному параметрическому семейству функций F = {/(•-с): К&trade- —" М|с Е С}, а последовательность значений параметров (с1, с2,., cq) является комитетным решением системы неравенств.

Г /(ос) >0 (а е А).

Ь-с)<0 (be В).

Таким образом, разделяющий комитет обладает свойством: для каждого, а? А неравенство fi (a) > 0 выполняется для более чем qf2 его элементованалогично, неравенство fi (b) < 0 выполнено при любом Ъ G В более чем для половины элементов комитета. Тем самым, был предложен новый коллективный алгоритм двуклассового распознавания: в семействе F выбирается не одна, а несколько разделяющих функций и строится q однотипных алгоритмов распознавания, каждый из которых может оказаться некорректным. Алгоритм с номером г G Ng сопоставляет объекту S с описанием х = I (S)? Шп число al (S)? {0,1} (указывает принадлежность тому или иному классу) по правилу.

1, если fi (x) > 0 0, если fi (х) < 0.

Классификация объекта, чье описание удовлетворяет уравнению fi (x) = 0, может быть произведена различными способами. В нашем случае удобно договориться, что при этом условии объект также относится классификатором fi ко второму классу.

Комитетный же алгоритм относит объект в одному из двух классов на основе правила простого большинства: к первому классу, если большинство чисел 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, который затем применен для приближенного решения задачи о минимальном линейном разделяющем комитете.

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

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

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

2. Доказаны достаточные условия существования комитета с ограниченным сверху числом элементов для несовместной системы линейных неравенств. Как следствие, получены достаточные условия существования линейного и аффинного разделяющего комитета.

3. Доказано необходимое и достаточное условие того, что заданная система линейных однородных неравенств равномерно распределена (по Гейлу). решена задача о минимальном комитете в классе равномерно распределенных систем неравенств.

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

5. В рамках традиционного для теории вычислительной сложности подхода к исследованию задач комбинаторной оптимизации.

— показано, что задачи MCFS и MCLE — iVP-трудны, обоснована труднорешаемость некоторых близких к ним задач;

— получены оценки порога эффективной аппроксимативности для задачи MCFS;

— разработан и обоснован приближенный алгоритм решения задачи MCLE.

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

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

Практическая значимость. Результаты работы по большей части носят теоретический характер и могут быть полезны специалистам по теоретической информатике. Тем не менее, некоторые результаты, например, приближенный алгоритм построения минимального разделяющего комитета, нашли применение на практике. Реализованный автором совместно с А. В. Качалковым и А. И. Рыбиным в виде СОМ-объекта qtGUN. dll, алгоритм вошел в библиотеку прикладных программ Quasar-Toolkit, разрабатываемую в секторе распознавания образов отдела математического программирования ИММ УрО РАН и представляющую собой ядро вычислительного сайта Quasar-Online (http://pria.uran.ru), предназначенного для решения задач распознавания «в сети». Известно несколько успешных случаев его применения при решении прикладных задач в области медицинской и геологической диагностики.

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

— Международной Байкальской школе-семинаре «Методы оптимизации и их приложения» (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. Введено новое понятие гиперграфа максимальных совместных подсистем (м.с.п.) несовместной системы абстрактных включенийдоказан критерий того, что конечный гиперграф является гиперграфом м.с.п. подходящей системы включений (с точностью до изоморфизма) — доказано необходимое и достаточное условие существования комитетного решения с заданным числом элементов, выраженное в терминах гиперграфа м.с.п. системы включенийпровес дена классификация минимальных комитетов с числом элементов 3 и 5 на основе изоморфизма соответствующих им подгиперграфов гиперграфа м.с.п.- отдельно исследовано экстремальное свойство гиперграфа м.с.п. несовместной системы линейных однородных неравенств, заданной на плоскости, с его помощью получена оценка числа элементов минимального комитета системы неоднородных неравенств.

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

Ц разделяющих комитетов.

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

4. Сформулирована и доказана серия необходимых условий существования комитетных решений несовместной системы включений. Для произвольных натуральных чисел к и q, связанных соотношением к < q и произвольной системы включений, обладающей комитетным решением из q элементов, получена нижняя оценка наибольшей по мощности подсистемы, разрешимой комитетом из к элементовоценка совпадает с верхней ценой подходящей антагонистической игры двух лиц, которую удалось решить в смешанных стратегияхполучены также асимптотические формулы для вычисления предельных значений оценок при к = q — га, q —> оо и фиксированном натуральном п.

5. Исследована задача комбинаторной оптимизации «Минимальный комитет (МС)». Отдельно изучены два ее важных специальных случая: задача MCFS, в которой система включений определяется набором конечных множеств, и задача MCLE — о минимальном комитете системы линейных неравенств. При этом.

— показано, что задачи MCFS и MCLE ./VP-трудны, труднореша-емыми также являются и некоторые близкие к ним задачи;

— найдены оценки порога аппроксимации для задачи MCFS;

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

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