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

  • Хачай, Михаил Юрьевич
  • доктор физико-математических наукдоктор физико-математических наук
  • 2004, Екатеринбург
  • Специальность ВАК РФ01.01.09
  • Количество страниц 174
Хачай, Михаил Юрьевич. Комитетные решения несовместных систем ограничений и методы обучения распознаванию: дис. доктор физико-математических наук: 01.01.09 - Дискретная математика и математическая кибернетика. Екатеринбург. 2004. 174 с.

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

Введение

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 Оценка скорости сходимости частоты к вероятности по классу комитетных событий

Рекомендованный список диссертаций по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

Введение диссертации (часть автореферата) на тему «Комитетные решения несовместных систем ограничений и методы обучения распознаванию»

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

Актуальность темы. Известно (см., например, [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] получены новые достаточные условия существования комитетных решений различных систем ограничений.

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

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

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

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

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

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

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

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

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

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

Похожие диссертационные работы по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Хачай, Михаил Юрьевич

Заключение Щ

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

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

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

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

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

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

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

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

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

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

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

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

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.

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