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

• Автор: Платоненко, Ирина Михайловна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 120 c. : ил

ЕВЕДЕШЕ

Глава I. МОДЕЛЬ РАСПОЗНАЮЩИХ АЛГОРИТМОВ, ОСНОВАННЫХ

НА ВЫДЕЛЕНИИ ПРЕДСТАВИТЕЛЬНЫХ НАБОРОВ

§1.1. Исходные определения

§ 1.2. Представительные наборы. Определения

и некоторые свойства

§ 1.3. Синтез множества представительных наборов

§ 1.4. Модель распознающих операторов. Описание

и исследование полноты

Глава 2. ЧИСЛЕННЫЕ МЕТОЛЫ РЕАЛИЗАЦИИ АЛГОРИТМОВ РАСПОЗНАВАНИЯ ПО ПРЕДСТАВИТЕЛЬНЫМ НАБОРАМ

§ 2.1. Решение систем булевых уравнений

специального Еида
§ 2.2. Выбор порядка умножений левых частей
уравнений специального вида
Глава 3. ВЫЧИСЛИТЕЛЬНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ РАСПОЗНАВАНИЯ ПО ПРЕДСТАВИТЕЛЬНЫМ НАБОРАМ
§ 3.1. Общее описание комплекса программ АЛКОРА
§ 3.2. Описание отдельных блоков программного
комплекса
§ 3.3. Практическое применение программного
комплекса АЛКОРА
ЛИТЕРАТУРА
ПРИЛОЖЕНИЯ

Одной из актуальных задач математической кибернетики является задача распознавания образов. В настоящее время существуют разные подходы к решению этой задачи. Выбор подхода зависит от типа обучающей информации, точности получения значений признаков, требуемой точности распознавания. Если известно, что описание объектов обучения и распознаваемых объектов получены с гарантированной малой ошибкой и по условиям задачи необходима Еысокая точность распознавания, то, как правило, для решения применяются методы двух типов.
Методы первого типа /3,12,16,21,28/ состоят в том, что априори выбирается параметрическая модель алгоритмов распознавания с пороговыми решающими правилами. В этом случае условия правильного распознавания заданных контрольных объектов с использованием обучающих объектов описываются в виде систем неравенств. Задача оптимальной адаптации или выбора оптимального по точности алгоритма состоит, в этом случае, в подборе значений параметров, выделении в модели фиксированного алгоритма таких, что при этом выполняется максимальное число неравенств указанной выше системы.
Даже для простых моделей выбор оптимального по точности алгоритма приводит к решению трудных экстремальных задач. Так, в модели, где параметрами яеляются только Ееса признаков, построение оптимального набора весов сеодится к задаче выбора максимальной совместной подсистемы системы линейных неравенств.

А эта задача - одна из эталонно трудных задач вычислительной математики.
Как правило, даже в простых случаях получить точное решение подобных вышеописанных экстремальных задач в приемлемое время не удается. Поэтому на практике используются приближенные методы, что приводит к уменьшению точности распознавания. Чем более сложной является модель распознающих алгоритмов, тем труднее выбрать в ней оптимальный алгоритм, поэтому потенциальные возможности "богатых” моделей, как правило, не удается использовать. В приложениях хорошо известен парадокс, состоящий в том, что приближенно оптимальные алгоритмы в "богатых" моделях дают худший эффект, чем оптимальные алгоритмы в малопараметрических моделях или хорошо проверенные эвристики /30/.
Описанные выше обстоятельства делают актуальным исследования хорошо зарекомендовавших себя на практике эвристических алгоритмов и разработку эффективных вычислительных методов для реализации таких алгоритмов на ЭВМ. Вывод об актуальности подобных исследований подкрепляется также тем, что второй класс современных методов, основанных на алгебраической /22-25,40,41/ или логической /27,31/ коррекции распознающих алгоритмов требует использования очень больших массивов памяти и поэтому далеко не Есегда применяются на практике.
Среди различных тнпое задач распознавания особое место занимает тип задач, в которых все признаки, составляющие описание объекта, являются бинарными, то есть принимают значения О или I. Задачи с таким типом информации достаточно часто встре^ чаются на практике, но основное обстоятельство, определяющее

б) М - 3$ + 4, <7* 1,2,
в) /7 ~ 2>$ ?2 ^ У - 1у 2, •••
£»«,= Полученные результаты дают верхнюю границу сложности для результата свертывания системы из трех уравнений.
Чтобы найти минимум функционала , нужно чтобы в (2.12) первый член был отрицательным, это выполняется в том и только в том случае, когда одно из #у/ равно 0. Доложим для определенности, что */2. равно нулю.
Имеем задачу определения минимума функционала
— <^23 ^^-^3 ~ ~'1J (2.14)
при у СЛОЕИИ
'<2/3 7" а2з = 7? (2.15)

О г? &Лз> -5 /7 (2Л6)
Преобразуем функционал (2.14), раскрывая скобки и учитывая равенство (2.15):
^=/72-/7-^/з^3 Отсюда вытекает, что
а) если 77 = 2ф , то минимум достигается при &-/3 ~#2ъ= %
б) если 77 ~2^^1 % то минимум достигается, если
/тг/3=^ (а,,,
либо либо ] 2^42
I 22 з “ Ф С (2г з -
Подставляя в формулу (2.14), имеем