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

Хачай, Михаил Юрьевич

Комитетные решения несовместных систем ограничений и методы обучения распознаванию тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Хачай, Михаил Юрьевич АВТОР

доктора физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Екатеринбург МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

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

ХАЧАЙ МИХАИЛ ЮРЬЕВИЧ

КОМИТЕТНЫЕ РЕШЕНИЯ НЕСОВМЕСТНЫХ СИСТЕМ ОГРАНИЧЕНИЙ И МЕТОДЫ ОБУЧЕНИЯ РАСПОЗНАВАНИЮ

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

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

Москва - 2004

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

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

профессор Вл.Д. Мазуров

Официальные оппоненты: доктор физико-математических наук,

чл.-корр. РАН К.В. Рудаков,

доктор технических наук, профессор Г.С. Лбов,

доктор физико-математических наук, Ю.Г. Сметанин

Ведущая организация: Уральский госуниверситет им. A.M. Горького.

Защита состоится

амл

2005г. в

часов на

заседании диссертационного совета Д002.017.02 по защите диссертаций на соискание степени доктора наук Вычислительного центра РАН им. А.А.Дородницына (119991, ГСП-1, г. Москва, ул. Вавилова, 40).

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан

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

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

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

В.В.Рязанов

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

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

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

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

Истоки понятия комитета можно найти в ранних работах по те-

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

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

ории голосования (см., например, работы 3' 4). Строгая же математическая формулировка понятия комитетного решения (комитета болынинства), по-видимому, впервые была дана в работе К. Эйблоу и Д. Кейлорг5 для случая системы линейных неравенств в . Вместо

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

(х1, х2,.....хч)

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

Основополагающими в теории комитетных решений являются работы Вл.Д. Мазурова начала 70-х гг. прошлого века. Им доказана теорема существования комитетного решения несовместной системы линейных неравенств и получена точная верхняя оценка числа элементов минимального комитета системы в однородном случае; введены различные обобщения понятия комитета: ^-комитет, (z, p-ре-шение и т.п., и доказаны первые теоремы существования этих конструкций для отдельных систем ограничений. На основании понятия комитетного решения им введено понятие разделяющего комитета конечных множеств А и В вКп. Разделяющим комитетом большинства для множеств А, В была названа последовательность функций fl, f 2,..., fq), каждый элемент которой f( • ) = f('; с') принадлежит некоторому заранее заданному параметрическому семейству

функций , а последовательность

/ l 2

значений параметров (с , c , ..., с ) является комитетным решением системы неравенств

/(а; с) > 0 (аеЛ) /(Ь; с) < о (Ьев).

Таким образом разделяющий комитет обладает свойством: для каждого а э А неравенство f(a) > 0 выполняется для более чем q/2 его элементов; аналогично, неравенство f(b) < 0 выполнено при любом

3Borda J.C. Memoire sur les elections au scrutin. Historia de l'academie des sciences pour. Paris, 1781.

4Condorcet I. A. Essai sur l'apphcation de I'analyse a la probabilite des decisions rendues a la pluralite des voix. Paris, 1785.

5Ablow СМ., Kaylor D.J. Inconsistent Homogeneous Linear Inequalities || Bull. Amer. Math. Sœ; 1965,vol. 71, no. 5, p. 724.

Ь € В более чем для половины элементов комитета. Тем самым, был предложен новый коллективный алгоритм двуклассового распознавания: в семействе ¥ выбирается не одна, а несколько разделяющих функций и строится q однотипных алгоритмов распознавания, каждый из которых может оказаться некорректным. Алгоритм с номером г 6 сопоставляет объекту 5 с описанием х = 6 Е" число 0^(8) 6 {0,1} (относит к тому или иному классу) по правилу

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

Комитетный же алгоритм относит объект в одному из двух классов на основе правила простого большинства: к первому классу, если большинство чисел ах (8) равно 1, и ко второму — в противном случае. По построению, введенный алгоритм безошибочно классифицирует множество объектов с векторами описаний из множества А и В, т.е. является корректным. Подробно проблема построения оптимальных корректных алгоритмов распознавания на базе множеств некорректных исследуется в работах, посвященных алгебраическому подходу в распознавании, опирающихся на фундаментальные статьи Ю.И.Журавлева и К.В.Рудакова.

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

A.И. Кривоногова изучались вопросы разделения аффинным комитетом не обязательно конечных множеств; Ю.А.Зуев исследовал вероятностные характеристики комитета не обязательно однотипных классификаторов; В.В.Рязанов предложил новые комитетные алгоритмы таксономии; в работах Н.Г.Белецкого и М. Осборна изучались комитетные алгоритмы распознавания с различными логиками подсчета голосов; в работах Г.С.Лбова, Н.Г. Старцевой и В.М.Неделько исследовалась устойчивость распознавания в классе логических решающих правил; А.И.Рыбиным получены новые достаточные условия существования комитетных решений различных систем ограничений; работы А. Швайгхофера и

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

конструкции — байесовского комитетного алгоритма (bayesian committee machine), также являющейся коллективным алгоритмом распознавания (вероятностного типа). Комитетные алгоритмы распознавания были успешно реализованы В.С.Казанцевым в серии программных комплексов под общим названием "Квазар".

Известно, что при исследовании комитетных решений несовместной системы ограничений достаточно ограничиться комитетами, составленными из решений ее максимальных по включению совместных подсистем (м.с.п.). Работы Д.Н. Гайнанова посвящены изучению множества м.с.п. несовместной системы линейных неравенств в терминах графа ее м.с.п, определение будет приведено ниже. В частности, в этих работах удалось связать проблему поиска комитетного решения с задачей поиска цикла нечетной длины в графе м.с.п. несовместных систем. Вл.Д. Мазуровым аппарат м.с.п. несовместных систем линейных неравенств был успешно применен для анализа многомерных сцен. В работах Е. Амалди исследовалась вычислительная сложность задачи поиска наибольшей м.с.п. несовместной системы линейных уравнений и неравенств в терминах гиперграфа ее минимальных несовместных подсистем. Отметим, что введенное в первой главе диссертации понятие гиперграфа м.с.п. построено на принципиально иной основе и обобщает понятие графа м.с.п.

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

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

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

- исследование вычислительной сложности комбинаторной задачи о минимальном по числу элементов комитетном решении: доказательство ее труднорешаемости, разбор основных специальных случаев, вывод условий эффективной

аппроксимируемости, разработка полиномиальных

приближенных алгоритмов и т.д.

- создание и обоснование новых комитетных алгоритмов распознавания.

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

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

Доказан критерий равномерной распределенности системы однородных линейных неравенств; решена задача о минимальном комитете в классе таких систем.

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

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

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

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

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

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

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

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

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

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

- получены оценки порога эффективной аппроксимативно-сти для задачи 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, Екатеринбург).

Публикации. Основные результаты диссертации опубликовано в 29 научных работах, из которых 10 в соавторстве.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, объединяющих 16 параграфов и содержащих 14 рисунков, заключения и списка литературы из 113 наименований. Объем работы составляет 175 страниц.

Автор признателен своему учителю, Владимиру Даниловичу Мазурову, за внимание и интерес к работе, а также Ивану Ивановичу Еремину за плодотворные дискуссии и поддержку.

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

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

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

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

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

(1)

Для произвольного 0 ф Ь С Мт будем называть подсистемой системы (1) с индексным множеством (индексом) Ь и обозначать (1)£, множество ее решений обозначим через D(L) = Dj.

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

Определение 1.1.1. Подсистема (1)z называется максимальной совместной подсистемой (м.с.п.) системы (1), если множество D(L) D(L U {;'}) = 0 Для каждого j € NOT \ L.

Определение 1.1.2. Комитетным решением (комитетом) системы (1) называется конечная последовательность

такая, что

для каждого j €

|{i: 6 Dj)| > (q/2)

Далее приводятся определения более общих комитетных конструкций: ^, р)-решения, обобщенного решения и др., которые здесь, ввиду краткости изложения, мы пропустим. Заканчивает параграф перечисление некоторых известных свойств введенного в работе Д.Н. Гайнанова6 понятия графа максимальных совместных подсистем, являющегося удобным инструментом, в частности, для изучения комитетной разрешимости несовместной системы ограничений.

Определение 1.1.5. Графом максимальных совместных подсистем системы ограничений (1) называется конечный граф G = (V, Е), множество вершин которого совпадает с множеством /1, J2,..., J¡ индексов максимальных совместных подсистем системы и {/, /} э Е тогда и только тогда, когда и I. = 1Чт.

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

Интерес к исследованию свойств графа м.с.п. был вызван, по-видимому, следующими утверждениями.

Теорема 1.2.1. Пусть Q — (х\ х— коллективное решение (обобщенное решение, (т^,р)-комитет и т.д.) системы (1). Существует одноименное решение Q' — (у1, у2,...,у4) системы, составленное из решений ее м.с.п.

Утверждение 1.1.1. Пусть 1,,12,---— цикл в графе

м.с.п. системы (1) и X € Б(1). Последовательность (х1,х2,..., X2'1) — комитетное решение системы (1).

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

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

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

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

Пусть, как и ранее, множество V = {/1,12, ..., /7} СОСТОИТ ИЗ индексов м.с.п. заданной системы (1).

Определение 1.3.1. Гиперграфом м.с.п. системы (1) называется конечный гиперграф О = (V, Е), множество ребер которого определяется соотношением

Теорема 1.3.1. Пусть задан конечный гиперграф Г = (УТ,ЕТ) без кратныхребер, в котором VI' {у1;..., УТ]. Найдутся подходящее число т и множества /),,..., 1)щ С N такие, что гиперграф Г изоморфен гиперграфу Ом.с.п. системы (1) тогда и только тогда, когда ЕТудовлетворяет условиям:

если Т > 1, то ЕТ не содержит петель, (и 6 ЕТ, и С») =>п е ЕТ.

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

Определение 1.3.2. Конечную последовательность вершин 5 — (уп,у22 гиперграфа Г, обладающую свойством: для

каждого подмножества Ь С Р^+х мощности к +1 справедливо включение

: з € Ь) € ЯГ,

назовем (', £)-симплексом в гиперграфе Г = (УГ,ЕГ).

Обозначение (', £)-симплекс выбрано из геометрических соображений. Видно, например, что вершины — элементы (2,1)-симплекса образуют в гипер графе Г "треугольник" (цикл длины 3).

Теорема 1.3.2. Система (1) имеет комитетное решение из q элементов тогда и только тогда, когда в гиперграфе О ее м.с.п. найдется подгиперграф, вершины которого образуют (q — 1, [(' -1)/2])-симплекс.

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

Определение 1.3.3. Последовательность (11, 12, ..., I) индексов м.с.п. системы (1) назовем q-комитетообразующей совокупностью

КОС'), если найдется минимальный комитет системы (1) 0 = (х1, х2,..., х') такой, что а;' 6 Л(^) = ^ для каждого г £

Из доказательства теоремы 1.3.2 следует, что если число элементов минимального комитета системы (1) равно q, то понятия '-КОС и (' — 1, [('- 1)/2])-симплекса совпадают. Далее будем рассматривать

только те комитеты системы (1), которые состоят из решений ее м.с.п.. Будем отождествлять комитеты Q1 = (х1, x2,..,xq) и Q2 = (у1 ,у2, ■ ■ ■ ,уч) системы (1), для которых найдется перестановка тг, что Х*,у*6 D(J). Обобщим это определение на случай комитетов различных систем включений. Пусть К = J,..., J) — q-КОС системы (1) и

где К q, — множество множество ее элементов.

Определение 1.3.4. Гиперграфом q-комитетообразующей совокупности К назовем подгиперграф G(K) порожденный в гиперграфе м.с.п. системы (1) множеством вершин L(K).

Пусть дополнительно задана система включений:

гея; (2)

И пусть К' = ^^ J2,..., J') — произвольная q-KOC системы (2).

Определение 1.3.5. Будем называть q-КОС К и К' изоморфными, если изоморфны соответствующие им гиперграфы G(K) и G(K').

Таким образом, задача перечисления q-КОС эквивалентна задаче перечисления попарно неизоморфных гиперграфов G(K). Поскольку гипер граф произвольной 3-КОС — цикл длины 3, и, следовательно, все 3-КОС попарно изоморфны, то решим поставленную задачу в простейшем нетривиальном случае, когда q = 5. Обозначим через 5 множество всех систем произвольных включений вида (1), а через 5 — произвольный элемент 5, конкретную систему (1). Обозначим через К(8) множество всех 5-КОС, которыми обладает система 5, а через К(5) = 1^65 £(5)

Теорема 1.3.3. Множество К(5) содержит 15 попарно неизоморфных элементов.

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

Определение 1.3.6. Пусть А = (д1, а2, ..., ак) и В = (Ь1,..., Ьк) — конечные последовательности неотрицательных целых чисел. Будем

говорить, А и В связаны отношением А ^ В, если выполнены условия:

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

Определение 1.3.7. Последовательность А назовем комитетно-ми-нимальной, если для всякой последовательности В либо А и В несравнимы, либо В А.

Основным результатом этой части параграфа является

Теорема 1.3.5. Пусть А — комитетно-минималъная последовательность. Существует подходящая система включений (1), один из минимальных комитетов которой обладает последовательностью весов А.

В завершение приведено несколько условий (необходимых или достаточных) комитетной минимальности заданной последовательности.

Параграф 1.4 посвящен выводу достаточных условий существования комитетного решения с ограниченным сверху числом элементов для несовместной системы линейных неравенств в

{а5,х)>Ь, 0'еКт). (3)

Обозначим через г ранг системы (3). Основными результатами параграфа являются следующие теоремы.

Теорема 1.4.2. Пусть каждая подсистема системы (3) ранга k, 0 < k < г разрешима комитетом из не более, чем q элементов.

Тогда система (3) также разрешима комитетом, причем число его элементов ограничено сверху числом

Теорема 1.4.3. Пусть каждая подсистема системы (3) из k + 1 неравенства (0 < k < г) совместна, тогда система разрешима комитетом, число элементов которого ограничено сверху числом

Теорема 1.4.3 с одной стороны является обобщением известного критерия существования комитетных решений системы линейных неравенств, доказанного Вл.Д. Мазуровым, а с другой может рассматриваться как аналог известной теоремы Хелли. Действительно, по теореме Хелли, условие совместности каждой подсистемы из не более чем г+ 1 неравенства системы (3) достаточно для того, чтобы вся система также была совместна (т.е. обладала ко-митетным решением из одного элемента). При условии, что каждая подсистема из k + 1 неравенства системы (3) (при 0 < k < г) совместна, сама система может оказаться, очевидно, несовместной в обычном смысле этого слова, однако она во всяком случае будет иметь комитетные решения с числом элементов, оцененным сверху в теореме 1.4.3. Таким образом, число элементов минимального комитета несовместной системы линейных неравенств может рассматриваться в качестве "меры" ее несовместности. Заметим, что в общем случае произвольной системы ограничений это вообще говоря не так (в работе приведены подтверждающие это примеры).

Теорема 1.4.4. Пусть каждая подсистема системы (3) из k + 1 неравенства(1 <к < г), совместна, и пусть L0С Nт — индексное множество подсистемы, разрешимой комитетом из 2q-1 элемента. Число элементов минимального комитета системы (3) не превосходит

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

крайне простую структуру — простого цикла нечетной длины, не превосходящей числа ее неравенств. Структура гиперграфа м.с.п такой системы более сложна. Гиперграф содержит большое количество минимальных по включению ребер, по мощности больших 2 (и естественно, не порождаемых его двухэлементными ребрами).

Пусть задана система

(^,®)>о (¿емт), (4)

где й},х € К2 и среди векторов а] нет нулевых и противоположно направленных. Пусть {/1, /2, ..., 1р} — множество индексов ее м.с.п. Известно, что число элементов в минимальном комитете системы также равно р. Основным результатом параграфа является следующая теорема.

Теорема 1.5.1. Пусть ф — гомоморфизм гиперграфа О2 м.с.п. системы линейных однородных неравенств на плоскости в гиперграф О — (У,Е) м.с.п. системы включений (1) и существует {1к1,1к2---,1к,} С Уг такое, что {1^,/*2..., 1к,} $ Е2, а {ф[1кг)} • ■ • > 'Ф(1к>)} € Е, тогда число элементов минимального комитета, разрешающего систему (1), меньше р.

В качестве следствия этой теоремы далее в параграфе приводится еще одна верхняя оценка числа элементов минимального комитета несовместной системы линейных неравенств.

Последний параграф главы (пар. 1.6) посвящен изучению свойств специального класса систем линейных однородных неравенств равномерно распределенных систем (по Гейлу). Сопоставим произвольному вектору множества

(ау.х) > 0}

(а;-,х) < 0} (а,, я) =0}.

Зафиксируем произвольное натуральное число к.

Определение 1.6.1. Система линейных неравенств (3) при ш = 2к + п — 1 равномерно распределена, если для каждого 0 ф х € К" выполнено условие

Основные результаты параграфа — следующие.

¿>(х) - и ь 7<(аг) =

= ИеП

Теорема 1.6.2. Система неравенств (3) равномерно распределена по Гейлу тогда и только тогда, когда одновременно выполнены условия: каждые п векторов из а„ а# ...,ат линейно независимы; если Ь — индексм.с.п. системы (3), то \Ь\ = к + п - 1.

Теорема 1.6.3. Минимальный комитет равномерно распределенной по Гейлу системы (3) состоит из + 1.

Кроме этого параграф содержит несколько утверждений, описывающих свойства графа м.с.п равномерно распределенной системы неравенств.

В главе 2 получена новая серия необходимых условий существования комитета из q элементов системы абстрактных включений (1). Для произвольных натуральных чисел к и q, связанных соотношением k < q и системы абстрактных включений, обладающей комитетным решением из q элементов, здесь получена точная нижняя оценка

е _И

дЯ,к = -

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

Теорема 2.2.1. Для произвольных натуральных к ^ справедливы равенства

где 8 = и Ь ■

т-

Полученная здесь оценка является верхней ценой подходящей антагонистической игры. Далее в главе показано, что эта игра при почти всех значениях параметров q и к не разрешима в чистых стратегиях, однако всегда разрешима в смешанных, причем цена игры в этом случае также равна <5?1*. Из теоремы следуют некоторые известные ранее результаты. В частности, известная нижняя оценка мощности наибольшей м.с.п. несовместной системы, разрешимой комитетом из q элементов, может быть получена подстановкой k = ?

Г2г1

Неожиданным следствием теоремы является равенство

<52«-1,2«-З = 0.5 2а _

задающее нижнюю относительную оценку мощности наибольшей подсистемы, обладающей комитетом, число элементов которого на два меньше числа элементов комитета всей системы. Видно, что значение оценки монотонно возрастает с ростом s, однако его предел равен 0.75 (в то время, как на первый взгляд, ожидается, что оценка должна стремиться к единице при й -¥ оо).

Далее показано, что игра Г не имеет решений в чистых стратегиях (за исключением случая д = 2р = к + 1, однако всегда разрешима в смешанных.

Теорема 2.2.2. Игра Г разрешима в смешанных стратегиях. Оптимальными смешанными стратегиями игроков являются, соответственно, меры х и Д, где

Цена игры совпадает с и определяется по формулам (2.2.1)

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

Теорема 2.3.1. Пусть А —произвольное натуральное число.

1. Для п = 2А справедливоравенство

2. Для п~2\ — \ предел 11т?_юо не существует, причем

Здесь, как обычно, использовано обозначение Ь(к;п,р) для вероятности к успехов в схеме из п независимых испытаний Бернулли с вероятностью успеха р.

В главе 3 исследуется вычислительная сложность одной задачи комбинаторной оптимизации, возникающей в теории комитетных решений — задачи о минимальном комитете (Minimal Committee, МС).

Задача "МИНИМАЛЬНЫЙ КОМИТЕТ" (МС):

Заданы множество X и набор его непустых подмножеств Д, D2, ■■■,Dm, Требуется найти комитетное решение системы (1) с наименьшим возможным q (или установить, что система не имеет комитетных решений).

Глава состоит из четырех параграфов. Первый параграф является обзорным, в нем перечислены основные определения теории сложности алгоритмов, введены понятия основных сложностных классов Р и NP, сводимости по Карпу и по Тьюрингу и т.д. Обзор построен с использованием работ М.Гэри и Д.Джонсона7, А.Китаева и др.8 и К.Пападимитриу9. Во втором параграфе формулируются: задача МС и эквивалентные ей задачи целочисленного линейного программирования

в которых матрицы А и В определяются однозначно по множеству индексов м.с.п. системы (1), а векторы е, / — состоят из единиц.

Параграф 3.3 посвящен рассмотрению специального случая задачи МС (в работе эта задача названа MCFS), в котором исходное множество X и его подмножества

являются конечными. Ниже приведены основные результаты параграфа.

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

8Китаев А., Шень А., Вялый М. Классические и квантовые вычисления■ -М.: МЦНМО ЧеРо. 1999.

9Papadimitriou Ch. Computational Complexity■ - Addison-Wesley. 1993.

min {(e,i) \ Bt> f,t€ Z+}

(5)

(6)

Di, D„..,D,

Теорема 3.3.1. Задача MCFS NP-трудна.

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

Теорема 3.3.2. Задачи MCFS, (5) и (6) полиномиально эквивалентны.

Следствие. Задачи (5) и (6) NP-трудны.

Далее в параграфе оценивается порог аппроксимируемости задачи MCFS, значение которого определяет точность аппроксимации оптимума NP-трудной задачи комбинаторной оптимизации (задачи MCFS в данном случае).

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

№= min{/[/](z) : хеХ{1}}

допустимое решение , обладающее свойством

№М < Г|

Аппроксимационным порогом задачи называется нижняя оценка точности аппроксимации, справедливая для произвольного приближенного алгоритма исследуемой задачи. Основными результатами этой части параграфа являются приведенные ниже теоремы, опирающиеся в свою очередь на выдающиеся результаты К. Лунда, М. Яннакакиса10 и У. Файджа11.

Теорема 3.3.5. Если справедлива гипотеза Р ф NP, то не существует приближенного алгоритма для задачи MGFS с точностью аппроксимации jlog2(m — 1).

10Lund С, Yannakakis M. On the hardness of approximating minimization problems // In: Proc. of the 33rd IEEE Symposium on Foundations of Computer Science. 1992. pp. 960-981.

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

Теорема 3.3.6. Если справедливо условие

ИР Ч ГШ£(п°(1о«1окп>),

то для произвольного £ > 0 не существует приближенного алгоритма решения задачи МСЕ8 с точностью аппроксимации

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

В параграфе 3.4 исследуется другой важный специальный случай задачи МС — задача о минимальном комитете несовместной системы линейных алгебраических неравенств

(а„х)>0 0€Пт) (7)

с рациональными векторами левых частей. В диссертации эта задача названа М^Е. Постановка задачи МСЬЕ, в частности, возникает при обучении распознаванию образов в классе аффинных разделяющих комитетов.

Теорема 3.4.2. Задача МСЬЕИР-трудна.

Показано, что задача М^Е остается ИР-трудной даже при условии, что все координаты векторов левых частей неравенств принадлежат множеству {-1,0,1} и число ненулевых координат каждого из этих векторов ограничено сверху числом 3.

Утверждение теоремы верно при условии, что п может принимать сколь угодно большие значения. При дополнительном ограничении на величину п задача М^Е может оказаться полиномиально разрешимой. Известно, например (см., например, работу Вл.Д. Мазурова12), что задача М^Е при п = 2 обладает полиномиальным алгоритмом.

Наряду с задачей МСЕЕ рассматривается задача COMLE, являющаяся переформулировкой первой в виде задачи распознавания свойства.

Задача "КОМИТЕТ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ" (COMLE)

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

Заданы натуральные числа п > 1 и т, векторы

а1,а2,...,ат 6

и нечетное число к. Существует ли комитет системы системы (7) с числом элементов, не превосходящим к?

Из теоремы 3.4.2 и теоремы Мазурова далее получено

Следствие. Задача СОЫЬЕ полиномиально разрешима при к т или к< 2 и ЫР-полна в противном случае.

Завершает параграф описание приближенного алгоритма решения задачи МСЬЕ, вычислительная сложность которого линейно зависит от вычислительной сложности задачи поиска решения совместной подсистемы исходной системы линейных неравенств. Свойства алгоритма описывает следующие теоремы.

Теорема 3.4.4.

1. Предложенный алгоритм корректен и имеет не более итераций.

2. Пусть мощность наибольшей совместной подсистемы системы (7) не превосходит числа к + (п - 1) +1 для некоторого натурального I, тогда точность аппроксимации г алгоритма удовлетворяет соотношению

Теорема 3.4.5. Задача ЫСЬЕ в классе равномерно распределенных систем линейных неравенств полиномиально разрешима.

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

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

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

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

(а,х) > О (6, х) < О

(а 6 А) (Ь€В),

а задаче поиска аффинного комитета — систему

(а, ж) + у > О (6, я) + 2/ < О

(в€-А)

(ЬеВ).

(8)

(9)

Обозначим через г1 и г2 ранги систем (8) и (9), соответственно.

Следствие 4.1.1. Пусть каждая подсистема системы (8) (системы (9)) ранга k, 0 < k < г1 (0 < k < г2) имеет ко-митетпое решение, состоящее из не более, чем q элементов. Тогда существует линейный (аффинный) разделяющий комитет для множеств А и В, число элементов которого ограничено сверху числом

2д

+ 1.

Следствие 4.1.2. Пусть каждая подсистема системы (8) (системы (9)) из k + 1 неравенства, где 0 < k < г1 (0 < k < г2), совместна, тогда существуетразделяющийлинейный (аффинный) комитет для множеств А и В, состоящий из не более, чем

[(т~к)/2\ к

+ 1

элемента.

Следствие 4.1.3. Пусть дополнительно к условию предыдущего следствия найдется подсистема системы (8) (системы (9)), мощности ц, обладающая комитетным решением из 2q — 1 элемента.

Тогда существует разделяющий линейный (аффинный) комитет, разделяющий множества А и В и состоящий из не более чем

элемента.

Из теоремы 2.2.1 получено необходимое условие существования разделяющего комитета.

Следствие 4.1.4. Пусть известно, что для конечных множеств А, В С К" существует разделяющий комитет Q, линейный или аффинный, состоящий из д элементов. Для произвольного натурального числа к, к < д найдутся подмножества

и подпоследовательность Q' (последовательности Q), являющаяся одноименным разделяющим комитетом для А' и В', причем выполнено соотношение

в котором 5 = Г2^-] и £ =

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

Утверждение 4.1.1. Задачи МСЬЕ и МЬБС полиномиально эквивалентны.

Следствие. Задача МЬБС ИР-трудна.

Показано также, что для ее приближенного решения может быть использован приближенный алгоритм решения задачи MCLE (описанный в параграфе 3.4), будучи примененным для поиска минимального комитетного решения подходящей системы линейных неравенств. Характеристики полученного в результате приближенного алгоритма для задачи MLDC описаны в теореме 4.1.3 (ввиду полной эквивалентности этого результата утверждению теоремы 3.4.4, мы его не приводим).

А' С А, В'С В

\А' и В'\ ^ з £ (Л) ((Д) -V-1)) к у! 1) ({-!))

В параграфе 4.2 рассматривается задача обучения распознаванию образов в классе комитетных решающих правил методом минимизации эмпирического риска. Используемые здесь обозначения и методика проведения рассуждений заимствованы из работы В.Н. Вапника и А.Я. Червоненкиса14. Как и ранее рассмотрим задачу доклассового распознавания образов, обозначим через П = {0,1} множество "меток" классов (полагаем, что 1 обозначает первый класс, а 0 — второй). Зафиксируем множество допустимых описаний объектов X, впоследствии множество будет наделено вероятностной мерой. Произвольную функцию : X —> Г2 назовем решающим правилом. Зафиксируем некоторое множество Т\ = {<р{х] а) | а 6 Л}," базовых" правил. Комитетным решающим правилом из д элементов базового класса Т\ называется правило

¡=1

где

0(4)

-К

если г > 0, в противном случае

аналог функции Хэвисайда. Если Л = X* и

Тх ={0((а,х)) | а€Л},

то Тч будем называть классом линейных комитетных решающих правил из д элементов и обозначать через Ып8. Соответственно, при Л = ГхИи

Тх = {в((в,®) + б) |оех'.бек}

класс ¥д обозначим через Л^ и назовем классом аффинных комитетных правил из д элементов. Кроме того, будем использовать следующие обозначения:

Прямым следствием теоремы 1.4.3 является

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

Теорема 4.2.2. Пусть Т\ € {Ып^Айх}, выборка (4.2.1) и натуральное число к таковы, что для произвольной подвыборки

существует правило 1)) € Т\ —решение системы

(10)

тогда оптимальное функционала эмпирического риска в классе Е' при

~[(1-к)/2\-

<7 = 2

+ 1,

равно нулю.

В следующей теореме приводится нижняя оценка емкости класса 1лп<4

Теорема 4.2.4. Пусть X = Е, тогда емкость к(',п) класса 1лп<? оценивается снизу числом '(п - 1).

Заметим, что в случае п = 2 известно точное значение Н(2) = ' + 1.

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

51 = {Аа \а € Л},

нечетное число ' = 2s+ 1 и рассматривается новый класс 5, построенный из всевозможных элементов вида

Основным результатом здесь является следующая Лемма 4.2.1. Пусть заданы: число ' = 2s + 1, события

А, ..., А' С51 и В= где р = (1,2,....д). ,

Если выборки х(1) и у(1) таковы, что для каждого Ь С мощности, большей чем 5 + 1, справедливы равенства:

(12)

|1'2(В)-1/1(В)|<дтах{|1/2(^)-1/1(ЛЛ| : I €

Здесь и у2 обозначают частоты выпадения события на выборках х(1) и у(1), соответственно. Приведенный далее в главе пример подтверждает необходимость условия леммы (во всяком случае для q = 3). В качестве непосредственного следствия леммы, получена

Теорема 4.2.5. Пусть вероятностная мера Р и класс событий ^ таковы, что для каждого подмножества Ь С К} мощности, большей, чем 5 + 1 справедливы равенства

Тогда для каждогое 6 (0,1) верно неравенство

Р{вщ>\1>2Ш -1/1 (В0)\ > де} < Р^ирНЛ*) - ^(А,)! > е).

Заметим, что полученные оценки, также как и упомянутые выше результаты В.Н.Вапника и А.Я. Червоненкиса, вряд ли могут быть использованы на практике ввиду их очевидной завышенности. Вопрос получения более тонких результатов пока остается открытым.

то

Основные результаты

1. Введено новое понятие гиперграфа максимальных совместных подсистем (м.с.п.) несовместной системы абстрактных

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

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

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

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

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

- показано, что задачи МСЬ8 и МСЬЕ ЫР-трудны, трудно-решаемыми также являются и некоторые близкие к ним задачи;

- найдены оценки порога аппроксимации для задачи МСЬ8;

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

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

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

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

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

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

[4] Мазуров Вл.Д, Хачай М.Ю., Некрасов В.П. Реализация диагностики и выбора вариантов в горно-геологических задачах. //Известия ВУЗ-ов. Горный журнал. 2001. №1. С. 10-15.

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

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

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

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

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

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

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

[12] Хачай М.Ю. О достаточной длине обучающей выборки для ко-митетного решающего правила // Искусственный интеллект.

2000, №2, С. 219-223.

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

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

2001. С. 41-44.

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

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

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

[18] Хачай М.Ю. Об эффективном алгоритме построения приближения к минимальному по числу элементов комитетному решающему правилу // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ- 6-2002»■ - Новгород: НовГУ. 2002. С. 593-596.

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

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

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

[22] 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.

[23] 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.

[24] Khachai M.Yu. On the Combinatorial Problem Concerned with the Notion of Minimal Committee // Pattern Recognition and Image Analysis. 2001. V.11 no.1 pp. 45-46.

[25] 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.

[26] 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.

[27] Khachay M.Yu. On Computational Complexity of the Minimal Committee of Finite Sets Problem // In: Proc. of the 2nd International Workshop 'Discrete Optimization Methods in Production andLogistics'. Omsk-Irkutsk. 2004, pp.176-179.

[28] Khachay M.Yu. On Computational Complexity of the Minimal Committee Problem // In: Proc. of the 7th International Conference on Pattern Recognition and Image Analysis: New Information Technologies (PRAI-7-2004). St. Petersburg: IAPR. 2004. vol. 1, pp. 58-61.

[29] Mazurov Vl.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), S67-S101.

Подписано в печать 25.11.04 Формат 60 х 84/16. Объем 2 п.л. Тираж 100 экз. Заказ №208 Размножено с готового оригинал-макета в типографии УрО РАН 620219, г.Екатеринбург, ул. С.Ковалевской, 18

»~f 167

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

Введение

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

1.1 Основные понятия и определения.

1.2 Условия существования комитетного решения абстрактной системы включений

1.3 Гиперграф максимальных совместных подсистем.

1.4 Условия существования комитетного решения системы линейных неравенств.

1.5 Эремальноеово гиперграфа мп. однородной системы линейных неравенств.

1.6 Равномерно распределенные системы неравенств.

2 Необходимые условия существования комитета в игровой постановке

2.1 Постановка задачи.

2.2 Основная теорема.

2.3 Предельные соотношения.

2.4 Замечания.

3 Задача о минимальном комитете

3.1 Элементы теории сложности алгоритмов.

3.2 Постановка задачи о минимальном комитете.

3.3 Вычислительная сложность задачи о минимальном комитете

3.3.1 Труднорешаемость задачи MCFS.

3.3.2 Порог аппроксимируемости для задачи MCFS.

3.4 Задача о минимальном комитете системы линейных неравенств.

3.4.1 Вычислительная сложность задачи MCLE.

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

4 Комитетные алгоритмы распознавания

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

4.2 О минимизации эмпирического риска в классе комитетных решающих правил.

4.2.1 Комитетные решающие правила.

4.2.2 Оценка скорости сходимости частоты к вероятности по классу комитетных событий

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

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

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

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

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

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

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

- создание и обоснование новых комитетных алгоритмов распознавания.

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

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

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

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

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

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

Практическая значимость. Результаты работы по большей части носят теоретический характер и могут быть полезны специалистам по теоретической информатике. Тем не менее, некоторые результаты, например, приближенный алгоритм построения минимального разделяющего комитета, нашли применение на практике. Реализованный автором совместно с А.В. Качалковым и А.И. Рыбиным в виде СОМ-объекта 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].

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение Щ

В заключении перечислим основные результаты диссертационной работы:

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

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

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

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

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

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

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

Список источников диссертации и автореферата по математике, доктора физико-математических наук, Хачай, Михаил Юрьевич, Екатеринбург

1. Белецкий Н.Г. Комитетные конструкции в многоклассовых задачах распознавания образов. Дис. на соискание степени к.ф.-м.н. (01.01.09 - мат.кибернетика). -Свердловск. 1984.

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

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

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

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

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

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

8. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990, 384 с.

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

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

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

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

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

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

15. Журавлев Ю.И. Об алгоритмах распознавания с представительными наборами (о логических алгоритмах). // ЖВМ и МФ. 2002. т.42. т. С. 1425-1435.

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

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

18. Зуев Ю.А. Наихудший случай для принятия решения большинством голосов//ЖВМ и МФ. 1989. т.29. т. С. 1256-1257.

19. Зуев Ю.А., Иванов С.К. Обучение и самообучение в процедурах взвешенного голосования // ЖВМ и МФ. 1995. т.35. №1. С. 104121.

20. Казанцев B.C. Задачи классификации и их программное обеспечение (пакет КВАЗАР). М.: Наука. 1990. 136 с.

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

22. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО ЧеРо. 1999.

23. Кривоногов А.И. О некоторых комитетных конструкциях классификации / в сб. Методы оптимизации и распознавания образов в задачах планирования. Свердловск: УНЦ АН СССР. 1980. С. 9298.

24. Кривоногов А.И. Некоторые вопросы обоснования комитетных алгоритмов /в сб. Классификация и оптимизация в задачах управления. Свердловск: УНЦ АН СССР. 1981. С. 39-51.

25. Лбов Г.С., Неделько В.М. Построение решающей функции на основе вероятностных логических высказываний многих экспертов. //

26. Известия высших учебных заведений. Физика. 1995, №9. С. 119123.

27. Лбов Г.С., Старцева Н.Г. Логические решающие функции и вопросы статистической устойчивости решений. Новосибирск: ИМ СО РАН, 1999. 212 с.

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

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

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

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

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

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

34. Мазуров Вл.Д., Хачай М.Ю., Некрасов В.П. Реализация диагностики и выбора вариантов в горно-геологических задачах. //Известия ВУЗ-ов. Горный журнал. 2001. №1. С. 10-15.

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

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

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

38. Рудаков К.В. О некоторых классах алгоритмов распознавания. -М.: ВЦ РАН СССР, 1980.

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

40. Рудаков К.В., Трофимов С.В. Алгоритм синтеза корректных процедур распознавания для задач с непересекающимися классами.// ЖВМ и МФ. 1988. т.28. №. С.1431-1434.

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

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

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

44. Харари Ф. Теория графов. -М.: Мир, 1973.

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

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

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

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

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

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

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

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

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

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

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

56. Хачай М.Ю. Об эффективном алгоритме построения приближенияк минимальному по числу элементов комитетному решающему правилу // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-6-2002». — Новгород: НовГУ. 2002. С. 593-596.

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

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

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

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

61. Эндрюс Г. Теория разбиений. М.: Наука, 1982. -255 с.

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

63. Amaldi E., Капп V. The complexity and approximability of finding maximum feasible subsystems of linear relations // Theoretical Computer Science. 1995, vol. 147, pp. 181-210.

64. Amaldi E., Pfetsch M.E., Trotter L.E. (Jr.) On the maximum feasible subsystem problem, IISs and HS-hypergraphs // Mathematical programming. 1995. Ser. A. pp. 533-554.

65. Amaldi E., Pfetsch M.E., Trotter L.E. (Jr.) Some Structural and Algorithmic Properties of the Maximum Feasible Subsystem Problem //In Procs. ofIPCO'99, LNCS 1610, pp. 45-59, 1999.

66. Amaldi E., Mattavelli M. The MIN PFS problem and piecewise linear model estimation // Discrete Applied Mathematics. 2002. 118, pp. 115—143.

67. Arora S. Probabilistic checking of proofs and the hardness of approximation problems. Ph.D. thesis. UC Berkeley. 1994.

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

69. Bar-Yehuda R. One for the Price of Two: a Unified Approach for Approximating Covering Problems. // Algorithmica. 2000. no. 27, pp. 131—144.

70. Blum A., Rivest R. L. Training a 3-node neural network is NP-complete. In: D. S. Touretzky (Ed.), Advances in neural information processing systems, Morgan Kaufmann, 1988.

71. Borda J.C. Memoire sur les elections au scrutin. Historia de Vacademie des sciences pour. Paris, 1781.

72. Chernov V.M. The "modular perceptron": A linear classes separability in the non-Archimedean features spaces. //In Proc. of the 10th Scandinavian Conference on Image Analysis (SCIA '97). Lappeenranta, 1997. v.2. pp. 803-808.

73. Condorcet I. A. Essai sur Vapplication de Vanalyse a la probabilite des decisions vendues a la pluralite des voix. Paris, 1785.

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

75. DasGupta В., Hammer B. On Approximate Learning by Multi-layered Feedforward Circuits// In Procs. of ALT-2000, LNAI-1968, pp. 264278, 2000.

76. Dinur I., Regev O. 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. Feige U. A Threshold of Inn for Approximating Set Cover. Journal of the ACM. 1998, 45(4).

78. Freund Y. , Schapire R.E. A decision-theoretic generalization of on-linelearning and application to boosting. //In Procs of 2nd Eur. Conf. on Сотр. Learn. Theory. 1995.

79. Gale D. Neighboring vertices on a convex polyhedron. In: Linear inequalities and related systems, edited by H.W.Kuhn and A.W.Tucker, Princeton, 1956 pp. 255 263.

80. Guruswami V. Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses // Algorithmica. 2004, vol. 38, pp. 451—469.

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

82. Hastad J. Clique is Hard to Approximate within nl~e. Acta Mathemat-ica. 1999, vol. 182, pp. 105-142.

83. Hammer B. Training a Sigmoidal Network is Difficult// In Procs. of ESANN'1998. Bruges. 1998. pp. 255-260.

84. Ibarra O.H., Kim C.E. Fast Approximation Algorithms for the Knapsack and Sum of Subsets Problems // Journal of ACM. 1975, vol. 22, pp. 463-468.

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

86. Johnson D.S., Preparata F.P. The Densest Hemisphere Problem // Theoretical Computer Science. 1978, no. 6. pp. 93-107.

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

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

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

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

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

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

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

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

95. Lovasz L. Coverings and Colorings of Hypergraphs //In Proc. of 4th Southeastern Conference of Combinatorics, Graph Thery and Computing. 1973. Utilitas Mathematica Publishing. Winnipeg, pp. 3-12.

96. Lovasz L. On the ratio of optimal integral and fractional covers 11 Discrete. Mathematics. 1975. vol. 13, pp.383-390.

97. Lund C., Yannakakis M. On the hardness of approximationg minimization problems // In: Proc. of the 33rd IEEE Symposium on Foundations of Computer Science. 1992. pp. 960-981.

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

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

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

101. Mazurov V1,D. The Capabilities of Collective Rules of Decision Making, Diagnostics, and Forecasting and Their Use in Engineering and Economic Problems // Pattern Recognition and Image Analysis. 1996. vol. 16, no. 3, pp. 461-469.

102. Mazurov VI.D., Potanin N.I. The Analysis and Interpretation of Textures by Committee Methods of Pattern Recognition // Pattern Recognition and Image Analysis. 1997. vol. 17, no. 2, pp. 260-265.

103. Mazurov V.D., Plotnikov S.V., Rybin A.I., Tyutin A.N., Hachai M.Yu. Algorithms of the KVAZAR+ Package // Pattern Recognition and Image Analysis. 1998. v.8, no.3. pp. 374-375.

104. 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), S67-S101.

105. Osborne M.L. The Senjority Logic: A Logic for a Committee Machine // IEEE Trans, on Сотр. 1977. v.C-26, no. 12, pp. 1302-1306.

106. Papadimitriou Ch. Computational Complexity. Addison-Wesley. 1993.

107. Raz. R. A parallel repetition theorem // SIAM Journal of Computing. 1998, vol 27, no. 3, pp. 763-803.

108. Ryazanov V.V. On the Construction of Collective Solutions in Taxonomy Problems // Pattern Recognition and Image Analysis. 1998. Vol.8, no. 2. pp. 146-147.

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

110. Schwaighofer A., Tresp V. The Bayessian Committee Support Vector Machine // Lecture Notes in Computer Science. 2001. vol. 2130, pp. 411-417.

111. Sima J. On the Complexity of Training a Single Perceptron with Programmable Synaptic Delays // Lecture Notes in Artificial Intelligence. 2003. vol. 2842, pp. 221-233.

112. Tresp V. A Bayesian Commitee Machine // Neural Computation. 2000. 12, pp. 2719-2741." ' ' .' " " ' • * Д,; ' iff'

113. Williamson D.P. The Primal-Dual Method for Approximation Algorithms // Mathematical Programming. 2002. Vol. 91. No. 3. Series В., pp. 447-478.