- 2 -
ОГЛАВЛЕНИЕ
стр.
ВВЕДЕНИЕ...................................................... 3
Глава I. МОДЕЛЬ РАСПОЗНАЮЩИХ АЛГОРИТМОВ, ОСНОВАННЫХ
НА ВЫДЕЛЕНИИ ПРЕДСТАВИТЕЛЬНЫХ НАБОРОВ...............II
§ 1.1. Исходные определения ............................... 12
§ 1.2. Представительные наборы. Определения
и некоторые свойства .............................. 16
§ 1.3. Синтез множества представительных наборов ... 26
§ 1.4. Модель распознающих операторов. Описание
и исследование полноты ............................ 31
ГлаЕа 2. ЧИСЛЕННЫЕ МЕТОЛУ РЕАЛИЗАЦИИ АЛГОРИТМОВ РАСПОЗНАВАНИЯ ПО ПРЕДСТАВИТЕЛЬНЫМ НАБОРАМ.........................43
§ 2.1. Решение систем булевых уравнений
специального вида...................................43
§ 2.2. Выбор порядка умножений левых частей
уравнений специального гида ........................ 55
Глава 3. ВЫЧИСЛИТЕЛЬНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ РАСПОЗНАВАНИЯ ПО ПРЕДСТАВИТЕЛЬНЫМ НАБОРАМ............................63
§ 3.1. Общее описание комплекса программ АЛКОРА ... 63
§ 3.2. Описание отдельных блоков программного
комплекса...........................................65
§ 3.3. Практическое применение программного
комплекса АЛКОРА ................................... 78
Ж ТЕРАТУРА....................................................86
ПРИЛОЖЕНИЯ....................................................91
- 3 -
ВВЕДЕНИЕ
Одной из актуальных задач математической кибернетики является задача распознавания образов. Е настоящее время существуют разные подходы к решению этой задачи. Выбор подхода зависит от типа обучающей информации, точности получения значений признаков, требуемой точности распознавания. Если известно, что описание объектов обучения и распознаваемых объектов получены с гарантированной малой ошибкой и по условиям задачи необходима еысокэя точность распознавания, то, как правило, для решения применяются методы двух типов.
Методы первого типа /3,12,16,21,28/ состоят в том, что априори выбирается параметрическая модель алгоритмов распознавания с пороговыми решающими правилами. В этом случае условия правильного распознавания заданных контрольных объектов с использованием обучающих объектов описываются е Еиде систем неравенств. Задача оптимальной адаптации или ЕЫбора оптимального по точности алгоритма состоит, в этом случае, в подборе значений параметров, выделении в модели фиксированного алгоритма таких, что при этом выполняется максимальное число неравенств указанной Еыше системы.
Даже для простых моделей выбор оптимального по точности алгоритма приводит к решению трудных экстремальных задач. Так, в модели, где параметрами являются только веса признаков, построение оптимального набора весоЕ сводится к задаче выбора максимальной совместной подсистемы системы линейных неравенств.
- 4 -
А эта задача - одна из эталонно трудних задач вычислительной математики.
Как правило, даже е простых случаях получить точное решение подобных вышеописанных экстремальных задач в приемлемое время не удается. Поэтому на практике используются приближенные методы, что приводит к уменьшению точности распознавания.
Чем более сложной является модель распознающих алгоритмов, тем труднее выбрать в ней оптимальный алгоритм, поэтому потенциальные возможности "богатых" моделей, как правило, не удается использовать. В приложениях хорошо известен парадокс, состоящий в том, что приближенно оптимальные алгоритмы в "богатых" моделях дают худший эффект, чем оптимальные алгоритмы в малопараметрических моделях или хорошо проверенные эвристики /30/.
Описанные Еыше обстоятельства делают актуальным исследования хорошо зарекомендовавших себя на практике эвристических алгоритмов и разработку эффективных вычислительных мєтодое для реализации таких алгоритмов на ЭВМ. Еывод об актуальности подобных исследований подкрепляется также тем, что Еторой класс современных методов, основанных на алгебраической /22-25,40,41/ или логической /27,31/ коррекции распознающих алгоритмов требует использования очень больших массивов памяти и поэтому далеко не всегда применяются на практике.
Среди различных типое задач распознавания особое место занимает тип задач, в которых все признаки, составляющие описание объекта, являются бинарными, то есть принимают значения О или I. Задачи с таким типом информации достаточно часто встречаются на практике, но основное обстоятельство, определяющее
- 5 -
их актуальность, саязано с тем, что задачи, происходящие из описательных наук, таких как геология, медицина и т.д., как правило, дают данные с Еесьма невысокой гарантированной точностью. Поэтому замена в этих задачах, например, числовых признаков бинарными обычно не приводит к сколько-нибудь существенной потере точности.
Из сказанного Еыше следует особая важность изучения эвристических алгоритмов распознавания, работающих с бинарной информацией. Среди многочисленных эвристик этого типа наибольшее распространение получили разнообразные схемы, связанные с построением доопределений частичных булеЕЫХ функций. Общая схема метода: формируется частичная функция /■" , принимающая значения I на эталонных объектах первого класса и 0 - на эталонных объектах второго класса. Выбирается некоторый способ доопределения Г на Еесь куб Е*1 } И - число признаков, участвующих в описании объектов или на часть Е*1. После построения доопределения решающее правило для распознавания состоит в проверке: чему равно доопределенное значение А на описании нового объекта.
Различные алгоритмы, основанные на применении указанного принципа, описывались в разных терминах и получали разные названия: "Тест", "Кора", "Метод перебора конъюнкций" и т.д. /1-3,9,11-13,25,29,30,33,34/. На самом деле все эти алгоритмы могут быть описаны единым способом. Все они е той или иной форме сеязэны с построением и анализом полных или частичных совокупностей так называемых "представительных наборов" или, е другой терминологии, допустимых конъюнкций для всюду определенных булевых функций.
- 6 -
Все методы, связанные с доопределением частичных булевых функций, характеризуются тем, что их применение к реальным задачам приводит к сложным вычислительным процедурам, что существенно ограничивает объем реальных решаемых задач. Поэтому весьма актуальной является построение эффективных численных методов для алгоритмов, основанных на доопределении частичных функций. В литературе детально исследован лишь один из алгоритмов доопределения - тестовый алгоритм. Другие схемы доопределения, происходящие, например, от алгоритмов типа "Кора", не изучались, и вычислительные схемы для их применения представляли собой модификацию методов направленного перебора. В то же время для многих задач схемы доопределения, не сводящиеся к тестовой, представляются более естественными.
Целью настоящей работы является разработка и исследование численной и программной реализации алгоритмов, основанных на принципе доопределения булевых функций на базе использования только простых, допустимых импликант этой функции или, в геометрической интерпретации, ее максимальных интервалов.
Построение соответствующих простых импликант или минимальных представительных наборов легко пригодятся к решению систем нелинейных булевых уравнений специального вида. Стандартный метод решения таких систем состоит в последовательном умножении левых частей уравнений и приведении результатов умножения к дизъюнктивной нормальной форме. Реальное выполнение такого метода, как правило, приводит к необходимости использования массивов памяти, существенно превосходящих возможности современных ЭВМ.
- 7 -
Осноиная цель диссертации состоит в том, чтобы разработать более эффективные методы решения таких специальных систем, основанных на некотором особом подборе сомножителей. В процессе синтеза такой группировки решается вспомогательная экстремальная задача типа задачи о максимальном паросочетании на графах, а также задач, связанных с явным вычислением сложности формул, полученных в результате умножения двух, трех и четырех левых частей булевых уравнений. В диссертации проведено исследование полноты модели распознающих алгоритмов, основанных на выборе множества тупиковых представительных наборов. Оказалось, что полнота имеет место для так называемых регулярных задач, а условие регулярности задач определяется соотношением,пропорционально связывающим характеристики, легко вычислимые в процессе синтеза алгоритма.
На базе проведенных исследований в диссертации разработан алгоритм, позволяющий в приемлемое время решать задачи распознавания с бинарной информацией, основанный на выделении максимальных интервалов частичных булегых функций или соответствующих им минимальных (тупиковых) представителышх наборов. Алгоритм реализован на ЭВМ БЭСМ-6 на языке Ф0РТРАН-1У. С помощью алгоритма решены прикладные задачи.
Диссертация выполнялась в лаборатории проблем распознавания Вычислительного центра АН СССР.
Диссертация состоит из введения, трех глэе, списка литературы и приложений. Список литературы содержит 46 наименований, в том числе 2 работы автора, в которых изложены основные результаты работы.
- 8 -
Б главе I даются необходимые определения, постановка задачи распознавания со стандартной обучающей информацией. Приводятся понятия распознающего алгоритма и оператора. В § 1.2 вводятся понятия и рассматриваются простейшие свойства представительного и тупикового представительного наборов, которые являются основными понятиями диссертации.
В главе I описывается модель алгоритмов распознавания, основанная на выборе множества тупиковых представительных наборов. Модель содержит все алгоритмы типа "Кора" как базовые, но при этом снимаются ограничения на возможные длины наборов и вводятся параметры, характеризующие веса признаков, веса (меры типичности) объектов из таблицы обучения и пороговые параметры, по которым определяется, следует ли учитывать данный представительный набор при распознавании данного объекта.
Показано, что представительные наборы можно получить как элементарную конъюнкцию специальных, не есюду определенных булевых функций. В задачах распознавания эти функции, как правило, яеляются слабоопределенными, и поэтому задачи синтеза их сокращенной дизъюнктивной нормальной формы не являются столь сложными, как в общем случае. Для синтеза сокращенной д.н.ф. предлагается использовать метод Нельсона /45,46/ с некоторыми модификациями, учитывающими не полную определенность функций.
В этой же главе изучаются связи между тестовыми алгоритмами и алгоритмами на базе выбора множества представительных наборов. Показано, что во многих случаях, когда тестовые алгоритмы не применимы, алгоритмы с представительными наборами дают решение задачи распознавания. Последнее свойство усиливается
- 9 -
доказательством теоремы о полноте, показывающей, что для широкого класса множества регулярных задач в рамках расширений модели с представительными наборами может быть построен алгоритм, дающий правильное решение задачи. Значения параметров такого алгоритма выписываются в процессе доказательства теоремы о полноте.
В главе 2 описывается численный метод синтеза представительных наборов. Метод основан на специальном алгоритме решения системы нельсоновских уравнений. Показывается, что сложность д.н.ф., получающейся в результате умножений левых частей двух, трех и четырех уравнений и приведения элементарных упрощений, может быть представлена яеными,легко вычислимыми формулами. Такие формулы выведены в диссертации.. Их наличие позволяет поставить и решить задачу разбиения системы нельсоновских уравнений на блоки таким образом, чтобы суммарная или максимальная длина полученных блокоЕ была минимальной. Решение этой последней задачи сеодится к построению максимального паросочетания в полном неориентированном графе, для чего использовался алгоритм Эдмондсона-Джонсона. Метод, описанный е главе 2, позволяет находить представительные наборы для таблиц обучения, в которых каждый класс представлен не более чем 20 эталонами. Метод позволяет экономить величину памяти, необходимой для записи промежуточных результатов алгоритма.
Е главе 3 дается описание комплекса программ АЛКОРА, который позволяет решать задачи распознавания предложенным алгоритмом. Комплекс реализован на языке Ф0РТРАН-1У для ЭВМ БЭСМ-6 и предназначен для эксплуатации в мониторной системе "Дубна".
Комплекс имеет блочную структуру. Отметим, что структура программного комплекса позволяет использовать отдельно взятые
- Київ+380960830922