Введение к работе
Дискретное моделирование - собирательное имя исследования теоретических подходов и создания аппаратно - программных технологий построения компьютерных моделей для анализа реальных предметных областей и их задач. Технологичность дискретного моделирования заключается в разработке необходимого объема и состава теоретических и алгоритмических средств, использование которых автоматизируемо в рамках соответствующих программируемых интеллектуальных сред, которые и пораждают те пли иные конкретные приложения на основе информации предметной области. В данной работе рассматриваются две основные группы теоретических проблем - это задачи связанные с минимизацией бупевих функций в классе дизъюнктивных нормальных форм и классы задач метрической оптимизации систем подмножеств вершин n-мерного единичного куба и систем подмножеств конечных множеств, которые совместно служат достаточной основой для моделирования широкого круга приложений - таких, как алгоритмическое обеспечение универсальных и специализированных базы данных, проблемы распознавания образов, анализ временных свойств прохождения сигнала в комбинационных схемах в асинхронном режиме и др. Рассмотрение данной группы прикладных задач показывает универсальность выбранных теоретических структур, однако основной наш интерес связан с задачей распознавания и классификации в ее традиционной постановке х, и эти вопросы рассмотрены в работе наиболее подробно.
1Ю. И. Журавлев. Об алгебраическом подходе к решению задач распознавания или классификации. Проблемы кибернетики, 33:5-68, 1978.
Термин распознавание образов представляет сегодня область исследования, в котором изучаются вопросы проектирования, разработки и функционирования систем обнаружения образов и закономерностей в данных эксперимента. Это включает в себя традиционные направления связанные с вероятностными методами распознавания и анализа данных (дискриминантный анализ, проверка гипотез), лингвистическими (структурными) методами распознавания (грамматические выводы и анализ сцен) и прикладными направлениями такимы как анализ изображений, распознавание символов, распознавание речи, диагностика человека и машины и др. Задача распознавания одна из типичных методик эвристического подхода к анализу данных. Она часто рассматривается в пространстве признаков большой размерности при условии, что число объектов в обучающей выборке сравнительно невелико (не образует статистику). В других случаях яисло доступных признаков также невелико. Данное обстоятельство послужило причиной возникновения методов анализа информации, которые сейчас принято называть дискретными. Основным объектом исследования является априорная информация о дополнительных свойствах классификации, совокупность всех подмножеств формального множества признаков и элементов обучения и множество всех алгоритмов, из которого необходимо выбрать адекватную к рассматриваемой задаче. Особый вклад в теорию и практику разработки дискретных методов распознавания образов внесла советская школа дискретной математики во главе с академиком Юрием Ивановичем Журавлевым. В рамках этой школы и была выполнена данная работа.
Одна из ранних работ применения формальных методов для реше-
ния задач классификации и распознавания - это 2, в котором предлагалось применение известных структур тестов и тестеров из области дискретного моделирования к синтезу алгоритмов классификации бинарных образов без учителя. Бурное развитие синтеза алгоритмических структур логического уровня призванных решить задачи распознавания образов сопутствовалось решением новых прикладных задач и соответствующими публикациями. Характерны следующие основные этапы развития теории дискретных методов классификации п распознавания.
Эмпирический или неформализованный период, состоявшийся в решении прикладных задач различных предметных областей путем построения отдельных эвристических алгоритмов. Для анализа экспериментальных многомерных данных различной природы зачастую применялись схожие подходы, не систематизируя это и тогда обоснованием принятых подходов служили только практические результаты успешных обработок. В результате развития данного этапа были разработаны большое количество отдельных эвристик, было решено большое количество прикладных задач и была создана основа для систематического синтеза и анализа семейств алгоритмов классификации образов.
Характерным результирующим объектом построения следующего этапа развития методов классификации служит алгоритмическая модель вычисления оценок 3. Это многопараметрическая модель алгоритмов, в котором выделены этапы вычисления оценок и последую-
2А. Н. Дмитриев, Ю. И. Журавлев, Ф. П. Кренделев. О математических принципах классификации предметов и явлений. Сб. Дискретный анализ, 7:3-15, 1966.
3Ю. И. Журавлев, В. В. Никифоров. Алгоритмы распознавания, основанные на вычислении оценок. Кибернетика, 3:1-11, 1971.
щего принятия решения. Вычисление оценок производится на основе широкого класса метрик, для которых решены вопросы вычислительного характера. Алгоритмы этого класса обобщают широкий класс известных эвристических алгоритмов и являясь параметрическими позволяют сформулировать и решить оптимизационные задачи выбора наилучших значений параметров по множествам обучения и контро^ ля и по выбранной целевой функции. Таким образом создается основа формализованного подхода к решению задач классификации, в основе которого лежит поиск локального оптимума по сформулированному критерию.
Следующий этап заключается в построении алгебраических структур над множествами эвристических процедур распознавания в рамках которого возможна формулировка и решение проблемы с сопоставлением задач и методов их решения.
Актуальность темы
В классе дискретных модельных построений особое место занимает нашедшее широкое применение аппарат и технологии метрической теории булевых функций. Одной из главных задач этой теории является минимизация булевых функций в классе дизъюнктивных нормальных форм, однако в области применений результатов метрической теории булевих функций преобладающим является применение основных структур и построений этой теории для моделиривания и интерпретации различных задач, и не минимизация отдельно взятых булевых функций. Многомерное бинарное пространство с расстоянием Хэмминга является базовой модельной областью для дискретных по-
строений. Такие объекты как сокращенная дизъюнктивная нормальная форма, множество всех тупиковых дизъюнктивных нормальных форм и их аналоги являются универсальными интерпретаторами различных предметных сред. Поэтому метрическая теория булевых функций легла в основу многих приложений таких, как конструиривание электронных схем и вычислительных архитектур, теория распознавания образов, систем сбора, хранения и анализа экспериментальных данных в средах естественнонаучных исследований и др. В связи со сказанным в работе исследована возможность и методы автоматизации решения широкого круга прикладных задач информатики на основе анализа дополнительных данных эксперимента с использованием алгоитмиче-ских решений специальных классов доскретных оптимизационных задач, в том числе задач метрической теории булевых функций. Введены и исследованы методы распознавания с логическими отделителями, которые базируются на расширенном анализе структуры и сложност-ных характеристик сокращенной дизъюнктивной нормальной формы булевых функций а также на исследовании метрических свойств подмножеств п-мерного единичного куба и систем подмножеств конечного множества.
Развитие задач метрической теории булевых функций - одного из двух указанных нами составляющих выбранного технологического подхода было связано с основопологающими работами К. Шеннона и с растущими н}гждами направления создания электронных вычислительных машин стремительно развивающегося с середины XX века. Существенный вклад в эту теорию внесла российская школа ученых, Ю. И. Журавлев, О. Б. Лупанов, С. В. Яблонский, В. В. Глаголев, Ю. Л. Васильев, А. А. Сапоженко и др.
Основная задача минимизации булевых функций оказалась весьма сложным объектом как для всеобъемлещих теоретических исследований, так и для получения простых алгоритмических решений. Были созданы алгоритмы градиентной и приближенной минимизации и вместе с тем предложены модели минимизации, отличающиеся от классической - в классе дизъюнктивных нормальных форм 4. Параллельно с этим были даны приложения развитой теории как в проектировании и тестировании схем из функциональных элементов (вычислительных сред), так и в областях, далеких от алгебры логики таких как синтез алгоритмов распознавания и классификации 5. Опыт данной работы, как уже было отмечено, связан с тремя группамы приложений теории метрических свойств булевых функций - это задачи автоматизированного синтеза реляционных структур моделей данных, задачи анализа поведения комбинационных схем в асинхронном режиме и задачи построения алгоритмов распознавания и классификации, основанном на идее логического отделения классов. Основным объектом модельных построений всех указанных задач и служит сокращенная дизъюнктивная нормальная форма, которая и является объектом специального исследования далее в изложении.
Подитожывая сказанное получаем, что на пути построения универсальных сред дискретного моделирования сегодня актуально выделение и исследование групп дискретных оптимизационных задач с укза-нием классов соответствующих им прикладных задач, для которых основой адекватного моделирования служат именно эти выделенные
4В. М. Караханян. Минимизация булевых функций в классе шаровых покрытий. Tanulmdnyok, 135:39-50, SzTAKI, МТА, Budapest, 1982.
5Л. В. Баскакова, Ю. И. Журавлев. Модель распознающих алгоритмов с представительными
наборами и системами опорных множеств. ЖВМ и МФ, г.21, 5:1264-1275, 1981
теоретические постановки. Следующим за этим шагом является создание прикладных программных сред - генераторов, основанных на полученных алгоритмических построениях. Применительно к теории распознавания образов этот подход реализуется в рамках исследования методов автоматизации решения задач распознавания в зависимости от предоставленной дополнительной информации задачи. Исследуется зависимость предположений (гипотез) распознавания, степень соответствия задач этим гипотезам и выбор алгоритма решения для рассматриваемой задачи.
Обшая методика исследования
Основным инструментом исследования работы является логико - комбинаторный аппарат дискретного анализа а также методы вычислительного моделирования в решении различных прикладных задач распознавания образов и приложений, таких как распознавание в геологии, сейсмологии, распознавание звуковой, текстовой, графической и др. информации.
Цель работы
Основной целью данной работы является опробация подхода построения сред дискретного моделирования для широких классов задач предметных областей на основе исследования соответствующих им специальных классов дискретных оптимизационных проблем и синтеза прикладных программных систем - генераторов для решения выделенных задач на основе накопленного опыта:
исследование алгоритмов синтеза и оценка сложности сокращенной дизъюнктивной формы булевых функций (случаи полного и частичного определения функций),
исследование распределения подмножеств дискретных структур с заданной компактностью, асимптотического поведения компактности и исследование структуры множества всех решений дискретной изопериметрической задачи,
исследование моделей логического уровня для задач распознавания и классификации и их приложение в геологии, сейсмологии а также в решении задачи оптического распознавания букв и других графических образов.
Научная новизна
В плане научной новизны можно выделить следующие результаты:
В задаче оценки сложности сокращенной дизъюнктивной нормальной формы слабо определенных булевых функций доказана эквивалентность к обобщенным числам Стерлинга второго рода и получена асимптотическая оценка для этих чисел,
исследовано асимптотическое поведение свойства компактности на подмножествах n-мерного единичного куба и основные свойства структуры множества всех решений дискретной изопериметрической задачи,
исследованы задачи моделирования логического уровня в задачах распознавания образов, построены иерархические системы гипо-
тез распознавания и соответствующие им программные технологии, (аналогичные структуры могут быть исследованы и в проектировании реляционных моделях данных, и др.).
Практическая ценность
Разработанные в работе методы представляют собой новый эффективный инструмент проектирования комплексного исследования задач класса распознавания образов и выбора алгоритмов для их решения. Полученные математические резултаты представляют решение известных задач дискретного анализа и служат основой автоматизации научных исследований в широком спектре задач дискретного моделирования. Представляют определенный интерес практические приложения, полученные на основе указанных теоретических и методических разработок, такие как:
разработка и программная реализация системы КАРС — кластерный анализ, распознавание и стастистика (платформа ЕС ЭВМ, алгоритмический язык Фортран), с внутренним языком управления, базой данных, со стандартно принятым набором алгоритмов кластерного анализа и распознавания, и классом алгоритмов логических отделителей,
создание технологии и программной системы для оптического распознавания символов, использующее бинарное отображение (bit map) символов и развитых алгоритмических систем распознавания и классификации графических примитивов (программная реализация для IBM PC, С 6.00),
создание технологической среды работы с базами данных и решение задачи информационного обеспечения управления производи ством с включением подсистем управления окон, генерации меню, отчетных печатных табличных и графических форм, оперативних просмотров, структур создания моделей данных и справочников и организация поиска по справочникам. Данная технологическая среда разработана как нулевая оболочка, которая заполняясь содержанием различных проблемных задач превращается в соответствующее сетевое рабочее место и реально приближена к приложениям типа обеспечения ведения производственной кон-структорско - технологической документации, разработки производственного плана, учета материалов и финансов и др. (IBM PC, Novell NetWare 3.12, CLIPPER 5.1). В работе, в частности в подсистеме работы с системными справочниками широко используются алгоритмы поиска и распознавания, основанные на основных результатах данной работы,
созданы программные системы решения сейсмологических задач:
— сбор, хранение и обработка базы данных землетрясений по
их основным параметрам (время, место (гипоцентр), мощ
ность, инструмент регистрации), связь данных с географи
ческой картой, оценка сейсмического риска и выработка сей
смического прогнозного критерия на основе ретроспективно
го анализа данных и алгоритмов распознавания образов (IBM
PC, PASCAL 5.5),
— дискретизация сейсмического сигнала с магнитных носителей
с помощью аналого - цифровых и цифро - аналоговых пре-
образователен, с автоматизацией обработки временного канала и привязки полезного сигнала по времени на основе методов распознавания образов (IBM PC, PASCAL 5.5),
дискретизация сейсмического сигнала с графического образа (scanner, PCX, GIF) (IBM PC, С 6.00),
создана геоинформационная система города для анализа последствий разрушительного землетрясения.
Основные результаты работы доложены в ВЦ Российской Академии Наук, в ИПИА НАН Армении, на конференции "Математические методы распознавания образов", Пущино, 1995г., на международной конференции "Intelligent and Cognitive Systems", Institute for studies in Theoretical Physics and Mathematics, Tehran, September, 1996 (пленарный доклад), на семинаре в Institute of Computer and Communication Systems, National Technical University of Athens, May, 1997.
