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

• Автор: Хачай, Михаил Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2004
• Место защиты: Екатеринбург
• Количество страниц: 175 с. : ил.

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 Труднорешаемость задачи МСРЭ
3.3.2 Порог аппроксимируемости для задачи МСРБ
3.4 Задача о минимальном комитете системы линейных
неравенств
3.4.1 Вычислительная сложность задачи МСЬЕ
3.4.2 Приближенный алгоритм
4 Комитетные алгоритмы распознавания
4.1 Разделяющие комитетные конструкции

4.2 О минимизации эмпирического риска в классе комитетных решающих
правил
4.2.1 Комитетные решающие правила
4.2.2 Оценка скорости сходимости частоты к вероятности
по классу комитетных событий
Заключение
Литература
Диссертационная работа посвящена исследованию ряда вопросов существования и оптимальности специального класса обобщенных решений несовместных систем ограничений, называемых комитетными. Кроме того в ней подробно изучаются методы и вычислительная сложность построения таких решений, а также приложения теории комитетных решений в распознавании образов.
Актуальность темы. Известно (см., например, [9, 14, 31, 99, 100]), что несовместная система ограничений (уравнений или неравенств)
типичный объект, с которым приходится иметь дело при решении задач принятия решений, оптимизации, распознавания образов, интерпретации результатов измерений, экономической и медицинской диагностики. Во всех перечисленных случаях исследователи сталкиваются с необходимостью обобщения классического понятия решения. Широко известен подход, восходящий к работам П.Л.Чебышева, связанный с ослаблением исходных ограничений и рассмотрением решений полученной таким образом скорректированной задачи ([9, 10, 11]). К сожалению, у него имеются ограничения, одно из которых обусловлено тем, что получаемое в результате решение скорректированной задачи может не удовлетворять ни одному из условий исходной. Введение же дополнительных условий, предъявляемых к искомому решению, нередко приводит к комбинаторным постановкам, обладающим высокой вычислительной сложностью.
Наряду с традиционным подходом в течение последних 40 лет активно развивается другой, дискретный подход к коррекции несовместных систем, базирующийся на замене единичного решения коллективом "псевдорешений", каждое из которых удовлетворяет достаточно большой доле условий исследуемой задачи. Теория комитетных решений является од1.3. Гиперграф максимальных совместных подсистем

Заметим, что если последовательности А и В таковы, что А ^ В, то для произвольной системы существование комитета с "весами" А равнозначно существованию комитета с "весами" В и при этом число элементов последнего разве что меньше.
Для дальнейших рассуждений удобно предполагать, что элементы последовательности упорядочены, например, по убыванию.
Утверждение 1.3.2. Пусть заданы последовательности А = (01,02 ак) и В = (Ь, Ь2,-.., Ьк). Известно, что ^=1 °> = Хл=1 Ьг — Р,
сч > а2> ■ ■ ■ > ак
и что последовательности А и В удовлетворяют соотношению (1.3.12). Существует последовательность С = {с, с2 ск), Хл=1с» = Р1 удовлетворяющая совместно с А условию (1.3.12) такая, что
С > С2 > .. • > Ск.
Доказательство. Без ограничения общности, достаточно убедиться в том, что если В такова, что 61 < Ъ2 то последовательность
В'= (Ъ[,Ъ'2 Ъ'к),
в которой Ь[ = 62, Ь'2 = Ъ и Ъ[ = для всех остальных г £ М*,, также удовлетворяет условию (1.3.12). Зафиксируем 1С1|. так, чтобы неравенство Еде./&г > 2 было верно. Если {1,2} П Д = 0 или {1.2} С С,
ТО = Еге,/^ > 2> откУДа Еге./0* > |> ПО УСЛОВИЮ.
Пусть 1 6 ./, а 2 ^ 7, тогда
£« = Е *>!■
i(iJ 7{1}и{2}
Предположив, ЧТО Еге/аг — §> ПОЛуЧИМ
Е «<5|.
Щ{1}и{2}
так как, по условию, а2 < 01, что противоречит условию (1.3.12). Значит, предположение не верно и Еге.7 °» > §'
Наконец, если 1^/, а2е7и Еле/ К > 2> т0 и Е;е,7 &г > поскольку, ПО условию, Ъ2 > Ь = Ъ'2 откуда Еге./ аг > §• Е]