МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ

ДОНЕЦКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

О С Н О В Ы П О С Т Р О Е Н И Я

С И С Т Е М Р А С П О З Н А В А Н И Я

О Б Р А З О В

Ч а с т ь 1

(К у р с л е к ц и й)

Утверждено : заседении кафедры на распознавания образов

Протокол № 3 от 23.11.97

1 9 9 7

Настоящее учебное пособие представляет собой первую часть курса лекций по "Основам построения систем распознавания образов", читаемых студентам специальности "Программное обеспечение вычислительной техники и автоматизированных систем управления" в VI - VII семестрах обучения в
Донецком Государственном институте искусственного интеллекта.

Причинами подготовки и выпуска специального курса лекций явились:

1.Отсутствие отработанного и доступного учебника инженерной направленности по созданию систем распознавания.

2.Дефицит книг соответствующей тематики для организации самостоятельной работы студентов.

3.Необходимость обобщения отдельных взглядов автора, достаточно продолжительное время специализировавшегося в области создания систем распознавания.

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

Составитель доц. Л.А. Белозерский

Ответственный за выпуск В.В. Гончаров

С О Д Е Р Ж А Н И Е

Т е м а 1 Распознавание образов в жизни человека (Введение)...……

Л Е К Ц И Я 1.1 Распознавание в биологических и технических системах.

1.1.1. Всеобъемлющий характер действия механизмов распознавания

.......................................................................

.......................

1.1.2. Краткая история вопроса появления технических систем автоматического распознавания и методов их создания...............................................................

.............................………

Л Е К Ц И Я 1.2 Терминология и отличительные особенности систем распознавания

...................................................................……….

1.2.1. Основные определения...........................................……………….

1.2.2. Системы распознавания................................................…………..

Т е м а 2 Задачи, решаемые в процессе создания систем распознавания

Л Е К Ц И Я 2.1. Проблематика задач создания систем распознавания на описательном уровне ...............……………………

Л Е К Ц И Я 2.2. Формулировка задач создания систем распознавания и методы их решения .........................…………………

Л Е К Ц И Я 2.3. Формулировка задач создания систем распознавания и методы их решения (продолжение) ……………….

Т е м а 3 Классификация систем распознавания

Л Е К Ц И Я 3.1 Принципы классификации и типы систем распознавания………………………………………………………….

Л Е К Ц И Я 3.2 Принципы классификации и типы систем распознавания

(продолжение) ….....................……………………….

Т е м а 4 Оптимизация эвристических выборов при создании систем распознавания образов

Л Е К Ц И Я 4.1 Оптимизация алфавита классов и словаря признаков

4.1.1. Уточнение назначения и цели создания СР .......……………….

4.1.2. Взаимосвязь размерности алфавита классов и эффективности СР

………………………………………………………………………

Л Е К Ц И Я 4.2 Оптимизация алфавита классов и словаря признаков (продолжение)

….……………..............................................

4.2.1.Взаимосвязь размерности вектора признаков и эффективности

СР…………………………………………………………………………

4.2.2.Формализация задачи оптимального взаимосвязанного выбора

алфавита классов и словаря признаков ………….…………………….

1. Формализация исходных данных .. . . ....... .....……… .

4.2.2.2.Выигрыш распознавания и оптимизация алфавита классов и словаря признаков в условиях ограничений ……..

Т е м а 5 Моделирование систем распознавания образов - методология их создания и оптимизации

Л Е К Ц И Я 5.1 Введение в моделирование
.....................................

5.1.1. История вопроса
......................................................……………..

5.1.2 Основные определения
............................................……………

Л Е К Ц И Я 5.2 Моделирование сложных систем и применение моделей

5.2.1. Принципы построения модели сложной системы ...………….

5.2.2. Моделирование сложных систем и опытно-теоретический метод их испытаний ........................……………………………………

Л Е К Ц И Я 5.3 Метод статистических испытаний (метод Монте-

Карло)………………………………………………………………….

5.3.1.Основное определение
.............................................…………….

5.3.2.Принципы получения случайных величин на ЭВМ …………

Л Е К Ц И Я 5.4 Метод статистических испытаний (продолжение)

5.4.1.Моделирование независимых случайных событий ……………

5.4.2.Способы получения случайных чисел с заданным законом распределения

..........................................................……………………

Л Е К Ц И Я 5.5 Модель системы распознавания образов

................

5.5.1.Моделирование распознаваемого объекта ........…………………

Л Е К Ц И Я 5.6. Модель системы распознавания образов

(продолжение)……………………………………………………………

5.6.1.Моделирование средств определения характеристик объектов распознавания.........................................................…

…………………....

5.6.2.Моделирование каналов связи
...............................………………

Л Е К Ц И Я 5.7. Моделирование алгоритма распознавания .............

5.7.1.Модель алгоритма распознавания объектов (явлений, процессов)

.......................................................................

.............................

5.7.2.Модуль оценки эффективности системы распознавания ……..

5.7.3.Модуль управления моделью системы распознавания …………

Л Е К Ц И Я 5.8 Опытно-теоретический метод в задачах создания систем распознавания

.............................................……………………

5.8.1.Использование принципов опытно-теоретического метода при моделировании СР .........................................……………………………

5.8.2. Моделирование в задачах создания и оптимизации систем распознавания..........................................................

........…………………

ЛАБОРАТОРНЫЕ
РАБОТЫ..................................................................

ВОПРОСЫ ПРАКТИЧЕСКИХ ЗАНЯТИЙ ...................................…...

ЛИТЕРАТУРА................................................…............
.............................

Т е м а 1

Распознавание в биологических и технических

системах

Л Е К Ц И Я 1.1

Распознавание образов в жизни человека

( Введение)

1.1.1. Всеобъемлющий характер действия механизмов распознавания.

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

Можно даже не утруждая себя примерами (мы рассмотрим их ниже) заметить, что похожие действия наблюдаются в биологии, в живой природе, а иногда даже в неживой. Кроме того, распознавание постоянно встречается в технике. А если это так, то, очевидно, следует считать механизм распознавания всеобъемлющим.

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

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

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

1.Вы легко узнаете издалека своего знакомого (но задайтесь вопросом: как?) Обратите внимание на слабую зависимость результатов распознавания от дальности, если конечно мы еще видим отдельные элементы и движения.

2.Предположим Вам нужен для изучения или повторения такой раздел математики, как интегральное исчисление. Ваши действия :

а) распознаете по корешкам обложек справочник на книжной полке;

(на фоне других книг - прочитывая, распознавая названия при последовательном просмотре или по внешнему виду, хранимому Вами в памяти по предшествующему пользованию этим справочником)

б) листаете и распознаете страницу справочника с оглавлением; (по опыту знаете, что оглавление располагается в начале или в конце книги)

в) распознаете тексты заголовков оглавления; (читаете);

г) распознаете среди всех заголовков необходимый Вам (сравниваете прочитанный со смысловым содержанием интересующего Вас раздела)

д) распознаете соответствующую этому заголовку страницу; (зная, что в оглавлении против найденного раздела печатается интересующий номер страницы)

е) листаете справочник и распознаете по нумерации страниц необходимый номер;

(сравниваете запомненный номер с номерами открываемых страниц) и т.д., и т.п.

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

В рассмотренном примере мы уже должны были заметить, что помимо
“чистого” распознавания в нем присутствуют наши действия, но при этом любому действию предшествует распознавание. А любое выполненное действие влечет за собой новый этап распознавательной деятельности.

3.Вот может быть более очевидный пример из военного дела.
Обратите в нем внимание на сочетание распознавания и действий, являющихся управлением.

Представьте себя в роли летчика в кабине самолета-истребителя. Вы взлетаете, набираете высоту, готовитесь и начинаете выполнять боевую задачу. Прежде всего:

-обнаруживаете (то есть, распознаете) в зоне обзора цель-самолет противника;

-идете на сближение;

-на основе имеющихся знаний о своем самолете как оружии - распознаете момент, когда произвести пуск ракеты по обнаруженной цели;

-производите пуск;

или:

-распознаете, что противник опередил Вас и произвел по вашему самолету пуск ракеты;

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

-производите маневр.

-распознаете, что маневр удался (если не удался и есть возможность- повторяете) - и сами атакуете противника;

Затем:

-распознаете, что горючее на исходе или - задача выполнена - уходите на посадку;

-распознаете посадочную полосу - осуществляете посадку.

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

4. Рассмотрим пример из области экономики. Руководитель экономического региона по экономическим показателям хозяйственной деятельности обнаруживает (распознает) ухудшение продовольственного обеспечения области, города и т.п.

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

5. Еще один военный пример из области обороны, где человек не выполняет ни распознающей функции, ни функции управления. СПРН (система предупреждения о ракетном нападении), находясь в режиме круглосуточного боевого дежурства автоматически обнаруживает в некоторый момент времени
(то есть, распознает) КО (космический объект) и завязывает его траекторию.
На этой основе автоматически определяется не является ли этот КО баллистической ракетой (распознается по попаданию пролонгированной во время полета КО точки его падения на обороняемую территорию, на территорию страны). Если указанное условие выполнилось СПРН дает сигнал тревоги на средства противодействия , например систему противоракетной обороны (ПРО).
Система ПРО, в свою очередь, обязана автоматически по данным СПРН обнаружить (распознать ) интересующую цель, распознать, например, что это сложная баллистическая цель СБЦ (боевая часть БЧ +ложные цели ЛЦ), распознать БЧ среди ЛЦ, произвести пуск противоракеты и т.д., и т.п.

6.Теперь примеры из области биологии.

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

Росянка распознает насекомое, севшее на ее лепестки и резко закрывается как ловушка для последующего переваривания пищи.

Подсолнечник распознает, где расположено солнце, и поворачивает свое соцветие в его сторону.

Комар распознает человека и пьет его кровь.

Лягушка распознает и ловит комара.

Удав распознает и ловит лягушку. и т.д.

И здесь также мы задаемся уже знакомым нам вопросом: как?

7. Совсем уже утрированный случай из техники: дверной замок распознает свой ключ и разрешает открыть помещение.

В последнем примере человек, как создатель, знает все.

Таким образом, приведенные примеры показывают, что распознавание в природе, обществе, в жизни человека, в технике - всеобъемлюще. Но при этом мы отмечаем, что ответов на поставленные вопросы, когда речь касается распознающей деятельности человека в большинстве случаев мы не найдем.
До настоящего времени полные представления о способностях живых организмов в распознавании многих явлений и объектов отсутствуют. В то же время, создавая технические системы, способные заменить его, человек высказывает гипотезы, продвигающие его к знанию распознающей деятельности в природе, что позволяет ему успешно решать стоящие задачи. Рассматриваемый курс “Основы построения систем распознавания образов” и должен научить пониманию того, что лежит в основе современных гипотез распознавательной деятельности и как на этой основе упомянутые задачи решаются.

1.1.2. Краткая история вопроса появления технических систем автоматического распознавания и методов их создания

Длительное время вопросы распознавания рассматривались человеком лишь с позиций методов биологии и психологии. При этом целью изучения являлись в основном качественные характеристики, не позволяющие вскрыть и точно описать соответствующий механизм. Если и получались числовые характеристики, то они, как правило, были связаны с изучением рецепторов, таких как органы зрения, слуха, осязания. Что же касалось характеристик принятия решений, то до их математической оценки дело не доходило. И только кибернетика позволила ввести в изучение психологического процесса распознавания образов, лежащего в основе принятия любых решений, количественные методы, что открыло принципиально новые возможности в исследовании и проектировании автоматических систем распознавания. Только кибернетика позволила ввести в область распознавания, как явления природы, математические представления. В этом можно увидеть в частности реализацию взглядов Галилея, который утверждал:

“Книга природы написана на языке математики. И тот, кто хочет прочесть ее, должен изучать этот язык”.

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

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

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

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

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

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

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

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

Итак, основные цели замены человека в задачах распознавания сводятся к следующим:

1) Освобождение человека от однообразных рутинных операций для решения других более важных задач.

2) Повышение качества выполняемых работ.

3) Повышение скорости решения задач.

В течение достаточно продолжительного времени проблема распознавания привлекает внимание специалистов в области прикладной математики, а затем и информатики. Так можно, в частности, отметить работы Р.Фишера, выполненные в 20-х годах и приведшие к формированию дискриминантного анализа, как одного из разделов теории и практики распознавания. В 40-х годах А.Н.Колмогоровым и А.Я.Хинчиным поставлена задача о разделении смеси двух распределений.

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

Новая научная дисциплина получила название “Распознавание образов”.

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

В последующем математический аппарат теории распознавания расширился за счет применения:

-разделов прикладной математики;

-теории информации;

-методов алгебры логики;

-математического программирования и системотехники.

(Системотехника - научное направление, охватывающее проектирование, создание, испытания и эксплуатацию сложных систем).

К середине 70-х годов определился облик распознавания как самостоятельного научного направления, появилась возможность создания нормальной математической теории распознавания. В этом нам придется убедиться, а также приобрести необходимые навыки, прослушав курс “Основы построения систем распознавания образов”.

Первая отечественная работа в области распознавания образов - работа основоположника современной теории информации Харкевича Александра
Александровича - “Опознавание образов” .”Радиотехника” т.14,15. 1959 г.

Наши отечественные ученые, внесшие существенный вклад в эту дисциплину:

В.М.Глушков, В.С.Михалевич, В.С.Пугачев, НП.Бусленко, Ю.И.Журавлев,
Я.З.Цыпкин, А.Г.Ивахненко, М.А.Айзерман, Э.М.Браверман, М.М.Бонгард,
В.Н.Вапник, Г.П.Тартаковский, В.Г.Репин, Л.А.Растригин, А.Л.Горелик и др.

Зарубежные ученые:

1-й Ф.Розенблатт - 1957г , Персепторон - простейшая модель мозга, решающая задачи распознавания.

Р.Гонсалес, У.Гренандер, Р.Дуда, Г.Себестиан, Дж.Ту, К.Фу,
П.Харт.

Л Е К Ц И Я 1.2

Терминология и отличительные особенности систем распознавания

1.2.1. Основные определения

В силу чисто исторических причин класс задач распознавания связан с понятием “образа”. В свое время не обратили внимания, что в заимствованном из англоязычных работ термине “pattern recognition” термин “pattern”, кроме значения “образ”, имеет еще значение “модель”, стиль”, “режим”,
“закономерность”, “образ действия”. В современном распознавании и особенно искусственном интеллекте его употребляют в самом широком смысле, имея в виду, что “образ” - это некоторое структурированное приближенное
(обратите внимание - “приближенное”!) описание (эскиз) изучаемого объекта, явления или процесса.

То есть, частичная определенность описания является принципиальным свойством образа.

Основное назначение описаний (образов) - это их использование в процессе установления соответствия объектов, то есть при доказательстве их идентичности, аналогичности, подобия, сходства и т.п., которое осуществляется путем сравнения (сопоставления). Два образа считаются подобными, если удается установить их соответствие. Можно, в частности, считать, что имеет место соответствие, если достигнута их идентичность.

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

Теперь отметим следующий важный момент, что в различных задачах образу придается различный смысл. Это определяется часто тем, какие характеристики объекта входят в описание образа, какой аппарат используется для представления этих характеристик. Именно отсюда и можно понять, почему образ является приближенным описанием объекта. Чем большее число свойств и качеств объекта отражено на принятом языке в образе рассматриваемого объекта, тем полнее это описание, тем полнее этот образ характеризует описываемый объект. Однако в любом случае мы имеем дело с описанием, а не с самим объектом, который всегда богаче описания. Итак, любой образ представляется некоторым набором признаков. Поэтому вполне допустимо наряду с выражением “распознавание образов” применять выражение
“отождествление некоторых наборов описаний объектов”.

* * *

Достаточно наглядно и теоретически и практически понимается различие между объектом и образом, если рассмотреть различия между картиной
(художественное полотно), являющейся плоским объектом, и таким ее изображением как фотографическое или компьютерное, введенное телекамерой или сканером.

Простота примера состоит в том, что как картина, так и ее изображение на пленке или в телевизионном кадре записи - двумерны. Вводя соответствующие системы координат, представим их так

f(a,b) - объект;

g(x,y) - изображение объекта.

Общепринято объект обозначать буквой f, а изображение -g.

Заметим сразу, что изображение может выступать как образ картины в том числе в автоматической системе распознавания, будучи введенным в компьютер для прямого сопоставления с другими изображениями. Но при этом обратим внимание и на то, что изображение здесь - это уже не сам объект.

Можно понять, что идеальная изображающая система - это такая система, для которой в любой точке пространства выполняется равенство f = g. На практике почти не существует таких систем. Функциональные связи между f и g всегда подлежат экспериментальному определению.

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

В данном примере распределения f и g имеют одну и ту же размерность, поскольку они являются пространственным распределением интенсивности света или его цвета в плоскости.

Фотография формируется квантами света, отраженного от картины, прошедшего через линзовую систему фотоаппарата и попавшего на фотопленку.
Такое формирование изображения приводит к потери качества за счет искажений и несовершенства приемного устройства, и следовательно, в этом случае f и g не равны друг другу. И только если известен закон потери качества, то можно провести компенсацию искажений путем соответствующей обработки изображения.

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

То есть, изображение g есть некоторое представление (описание) объекта f, которое, хотя и располагается в том же месте, но может иметь отличия не только качественные, но и такие количественные как размеры. В данном случае приходится констатировать, что процессы в гамма-камере, с помощью которой производится регистрация исходных данных, на сегодняшний день не имеют математического описания, позволяющего связать объект с его изображением. Это еще раз заставляет подчеркнуть, что врач не видит изменений интенсивности поглощения гамма-излучения в теле пациента, а только - распределение интенсивностей на изображении, полученном с помощью системы регистрации. А отсутствие математического описания связей изображения и процесса не позволяет строго трактовать результаты медицинского наблюдения. Остается надеяться только на опыт врача.

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

Таким образом, в общем случае не существует идеального (1:1) соответствия между информацией, содержащейся в какой-либо точке с координатами (a, b), и информацией, соответствующей точке (x, y). В принципе информацию от каждой точки объекта можно “рассеять” по всем точкам изображения. Однако в любом полезном методе визуализации главный вклад в каждую точку (a, b) будет давать отдельная конкретная точка
(x, y). Другие, соседние точки будут вносить меньшее количество информации, причем уменьшение указанного вклада происходит достаточно резко по мере удаления от основной точки с координатами (x, y). Эти выводы известны как принцип близости, а распределение по изображению некоторой точки из пространства объекта может зависеть как от значения поля в точке объекта, так и от поля в точках, расположенных около этой точки и удаленных на бесконечное расстояние от нее.

Какая же существует физическая связь между пространством объекта и пространством изображения?

В плоскость изображения попадает информация исходя из наличия информации в плоскости объекта, а также в зависимости от того, какой кодирующий носитель информации используется в данном методе визуализации
(фотография формируется за счет переноса фотонов, яркостная картина УЗИ
- за счет рассеяния продольных ультразвуковых волн, степень поглощения радиационных препаратов - путем счета испущенных (-квантов, рентгенограмма - за счет линейного затухания рентгеновских квантов и т.п.).

Введем функцию h(x,y,a,b), которая описывает пространственные связи для точечного процесса, то есть процесса, который отличен от нуля лишь в точке с координатами (a' ,b' ). Тогда зарегистрированное изображение будет иметь вид:

[pic]

Здесь зависимость распределения изображения от амплитуды сигнала точечного источника учтена введением в функцию h пятого аргумента.

Рассмотрим теперь сигнал от второго точечного объекта, расположенного там же, где и первый:

[pic]

Согласно принципу суперпозиции излученные энергии сигналов суммируются:

[pic]

Это - нелинейная суперпозиция в силу нелинейности слагаемых в правой части равенства. В итоге, как видим, суммированию измеряемых распределений в плоскости изображения не соответствует сложение функций в плоскости объекта.

Если же система линейна, то

[pic]

а суперпозиция будет иметь следующий вид

[pic]

То есть, в случае линейности системы сложение функций в плоскости объекта приводит к суммированию распределений в плоскости изображения с точностью до единственной функции преобразования h.

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

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

[pic]

а для линейной

[pic]

Функция h, используемая для связи распределений f и g, называется функцией отклика точечного источника (ФОТИ). Зависимость ее от всех четырех пространственных координат определяет ФОТИ как пространственно- зависимую. Если же точечный процесс одинаков для всех точек плоскости объекта, то h - пространственно-инвариантна. При этом h зависит лишь от разности координат (x-a,y-b). Для пространственно-инвариантной системы

[pic]

при этом для линейной пространственно-инвариантной системы

[pic]

Последнее выражение известно как интеграл свертки, согласно которому распределение по изображению представляет собой свертку распределения по объекту с ФОТИ. Именно функция h описывает процесс переноса информации от объекта в пространство изображения и характеризует все геометрические искажения, присущие процессу визуализации.

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

[pic]

а для пространственно-инвариантной

[pic]

Это свойство системы называется разделимостью.

В итоге для линейной, пространственно-инвариантной разделимой системы получаем

[pic]

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

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

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

[pic]

где n(x,y) - распределение шума в изображении.

* * *

Теперь сконцентрируем внимание на следующем важном термине распознавания образов - “класс”. Здесь, прежде всего, обратим внимание на то, что как человек, так и автомат принимают решение на основе отождествления совокупности конкретных значений характеристик объектов или явлений не просто друг с другом, а обычно с некоторым классом, в который объединяются объекты или явления, имеющие общие свойства (например: характеристики выхода из строя агрегатов и систем той же АЭС - класс опасных отказов или класс отказов, требующих определенного технического вмешательства, но неопасных).

Таким образом, классы - это объединения объектов (явлений), отличающиеся общими свойствами, интересующими человека.

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

Таким образом, в самых общих чертах распознавание можно определить как соотнесение объектов или явлений на основе анализа их характеристик, представляющих образы этих объектов, с одним из нескольких, заранее определенных классов.

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

1.2.2. Системы распознавания

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

Здесь необходимо подчеркнуть, что именно центральную задачу распознавания образов представляет построение на основе систематических теоретических и экспериментальных исследований эффективных вычислительных средств (объединяемых в понятии “системы распознавания”) для отнесения описаний с объектов, явлений, процессов к соответствующим классам.

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

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

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

Рассмотрим некоторые применения.

1) Системы технической диагностики.

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

Исторически сложившаяся тенденция усложнения, а значит удорожания машин постоянно увеличивает затраты на эксплуатацию. Выход - переход к системам технической диагностики (распознавания состояния машин), например, безразборный поиск неисправностей. В результате вместо планово- предупредительного ремонта - ремонт по фактической необходимости.
Например, в инструкции по эксплуатации автомобиля предусмотрены плановые технические обслуживания через 500 км, 1000 км, 2000 км и т.д. Если же его оснастить системами распознавания состояний, то от плановых ТО можно было бы отказаться заменив их обслуживанием отдельных узлов и систем по необходимости.

2) Медицинская диагностика.

Автоматизированные системы диагностики в медицине - путь увеличения

- широты и глубины охвата симптомов;

( рассчитывать только на память врача во всех ситуациях очень трудно.
Лучше функцию памяти отдать компьютеру)

-оперативности;

(компьютер обеспечит почти мгновенный результат)

-достоверности.

(диагноз компьютера не зависит от внешних факторов, как это случается с человеком)

3) Сельское хозяйство.

Области применения здесь:

-распознавание размеров урожая по данным космических наблюдений;

-уменьшение ручного труда при сортировке плодов по форме, цвету и размерам и т.п.

4) Военное дело.

Сложные системы вооружения:

-автоматический функциональный контроль технического состояния систем и ввод резервирующих;

-роботы, обслуживающие фазированные антенные решетки радаров.

На основе рассмотренного можно уже ответить на вопрос, что же представляет собой СР.

В первом приближении:

“СР - это автоматическое вычислительное устройство, предназначенное для распознавания образов (каких? можно уже не повторяться).

Заметим, что это очень поверхностное определение. Сегодня физически
СР это и вычислительная машина как один составляющий элемент СР;

-это и такие часто более дорогостоящие технические средства, как средства обнаружения распознаваемых объектов (например, патологических изменений того или иного органа человека);

-это и средства измерений параметров обнаруженных объектов (без них не получить признаков распознавания);

-это и математическое обеспечение, в составе которого: методы и алгоритмы обработки измерительной информации; методы и алгоритмы определения признаков распознавания; методы и алгоритмы непосредственно распознавания объектов, явлений , процессов ( построения решающих правил отнесения объектов к тому или иному классу); методы и алгоритмы в некотором смысле оптимального управления процессом распознавания; методы и алгоритмы оценки эффективности СР как на стадии проектирования, так и в процессе ее функционирования;

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

Рассмотрим подробнее отдельные элементы.

а) Средства обнаружения распознаваемых объектов.

К ним в разных областях применения относятся:

в медицине:

-рентгеновские аппараты;

-аппараты УЗИ;

-ЯМР-томографы;

-энцефалографы;

-рентгеновские томографы;

-кардиографы и т.д.

в военном деле:

-радиолокаторы;

-оптические (лазерные) локаторы;

-лазерные дальномеры;

-приемники гамма-излучения;

-сонары - ультразвуковые локаторы.

Средства обнаружения представляют дорогостоящую часть СР. Но этим дорогостоящая часть СР не ограничивается.

б) Средства сопряжения.

Для сопряжения средств обнаружения с ЭВМ необходимы специальные электронные устройства аппаратного интерфейса. Эти составные части СР также достаточно дорогостоящи.

в)Средства измерений параметров распознаваемых объектов,явлений, процессов.

Средства измерений часто входят в состав обнаружителей (РЛС - измерение дальностей, углов, Рс/Рш).

г) Методы и алгоритмы обработки измерительной информации

Часто для получения признаков распознавания или параметров , которые их обусловливают необходима специальная математическая обработка (пример, для РЛС - определение дальностей целей по временной задержке сигналов, угловых координат по разности фаз, коэффициентов лобового сопротивления целей по координатам и их производным и т.п.).

Сам процесс назначения признаков - творческий процесс, говорят - эвристический, зависящий от человека.

д) Методы и алгоритмы принятия решения о принадлежности объектов распознавания.

е) Методы и алгоритмы оптимального управления распознаванием.

ж) Методы и алгоритмы оценки эффективности распознавания.

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

з) Э В М

Наконец, ЭВМ. Это обязательный элемент современной СР. Вся обработка измерений с целью выделения признаков распознавания, вся математика классификации, управления и оценки эффективности выполняется ЭВМ. Само развитие теории и методов распознавания обязано появлению ЭВМ.

и) Коллектив подготовленных специалистов.

Такая составляющая на первый взгляд не имеет отношения к системе.
Однако без коллектива подготовленных специалистов трудно обойтись в больших системах, решения которых чрезвычайно ответственны. В таких системах оценка эффективности - это показатель, которым пользуются с момента создания СР и до конца ее существования. При этом пользуются этим показателем специалисты, а не система. А сама необходимость такого использования связана с тем, что в процессе работ появляется возможность повысить эффективность СР за счет получения новых данных и уточнения параметров системы в результате анализа специалистами конкретного случая распознавания с последующим уточнением этими специалистами имеющихся параметров. То есть, система в течение своей жизни (говорят - “жизненного цикла”) изменяется (динамизм системы).

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

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

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

Далее на пути оперирования с информацией у технических СР стоит устройство сопряжения с ЭВМ. Естественными аналогами его являются биологические средства связи человеческих рецепторов с мозгом, выполняющим роль ЭВМ.

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

-какие функции выполняют рецепторы в части первичной обработки результатов обнаружения объектов, явлений;

-каковы характеристики линий передачи данных от рецепторов к мозгу как ЦВС;

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

-какие алгоритмы использует мозг для решения задачи классификации, оптимального управления процессом распознавания;

-как человеку удается избавиться от специфичности, свойственной техническим СР и т.д.

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

Достижение соответствующих целей - задачи XXI века.

Тема 2

Задачи, решаемые в процессе создания систем распознавания.

Л Е К Ц И Я 2.1.

Проблематика задач создания систем распознавания на описательном уровне

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

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

Итак, мы уже знаем, что распознавание образов в технике - необходимый элемент процесса механизации и автоматизации машин, устройств и систем для

-замены человека там, где используется тяжелый физический труд;

-реализации быстрых реакций в управлении там, где нет времени на раздумье;

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

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

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

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

Постараемся осмыслить эту инвариантность построения СР , рассмотрев простые реализации систем.

А. Распознавание стороной А самолетов стороны В (этот пример мы будем часто использовать в последующем, постепенно его усложняя).

Здесь фактически требуется создать автоматическую систему, обеспечивающую стороне А решение указанной задачи.

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

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

Как эта информация может быть получена:

-из открытой печати (часто многие характеристики самолетов не скрываются);

-из разведданных;

-из экспериментальных наблюдений самолетов стороны В и измерений их характеристик (например, с помощью РЛС);

-из экспериментальной обработки данных, полученных по макетам и моделям соответствующих самолетов стороны В

(наземные стенды или электродинамические расчеты); и т.д.

Какие это характеристики? Это - численность экипажей, высоты полета, крейсерские скорости, дальности полета, число двигателей и т.д.

Рассматриваемое изучение позволит обнаружить в том числе и способы, которые применяет или предполагает применять сторона В для преодоления противовоздушной обороны (ПВО) стороны А и которые будут ухудшать возможности распознавания. Например, США по программе Стелс разработали бомбардировщик-невидимку для радиолокационных средств - В1).

Таким образом мы должны получить все мыслимые и существующие характеристики самолетов (признаки).

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

Это фактически соответствует разделению самолетов стороны В на классы, для каждого из которых стороне А известно, что нужно предпринять.

В результате может оказаться, что классов 3 (А1- бомбардировщики, А2
- штурмовики ,А3 - истребители), а средств противодействия - 2 (S1 - ЗУР,
S2 - истребители с их вооружением).

При этом наиболее эффективно их распределить следующим образом:

А1 - S1

А2 - S2

А3 - S1 то есть, классы А1 и А3 с точки зрения противодействия желательно объединить в один класс.

Если же средств противодействия - 3 (S1- ЗУР для больших высот, S2 -
ЗУР маловысотные, S3 - истребители с их вооружением), то классы можно не объединять, а использовать стратегию

А1 - S1

А2 - S2

А3 - S3

Третий шаг по созданию системы распознавания самолетов стороны В - выбор измерителей.

Для обозначенных классов авиации из анализа имеющихся у стороны А средств наблюдения за самолетами (РЛС, ОЛС и т.п.) и полного перечня признаков соответствующих самолетов, полученных на первом нашем этапе разработки (например, крейсерские скорости, высоты полета, длины фюзеляжей, размахи крыльев, число двигателей и т.п.) выделить такие, которые могут быть определены по данным имеющихся средств измерений.

Здесь возможны и разочарования: может не оказаться таких средств измерений. Тогда принимается решение о их создании.

Итак, по каждому самолету мы имеем № характеристик - признаков. Но это еще ничего не дает нам для решения задачи. Мы не знаем, как разделить самолеты, пользуясь этими признаками по классам.

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

При этом в описании каждого класса должны содержаться сведения:

- о наличии или отсутствии признаков качественного характера (тип двигателя, наличие постановщика помех, тип помех и т.п.);

- о диапазонах или законах распределения признаков, имеющих количественное выражение.

Следует заметить, что все выбранные признаки должны получить соответствующее содержание (свое) для каждого класса.

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

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

Здесь априорные данные - доопытное признаковое описание классов;

апостериорные данные - послеопытный набор признаков классифицируемого самолета.

Рассмотрим вторую возможную реализацию СР.

Б. Распознавание заболеваний сердца. Требуется построить такого рода автоматическую систему.

1-й шаг создания такой системы - изучение всей информации о заболеваниях сердца.

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

В результате мы должны иметь здесь все возможные характеристики заболеваний (признаки):

-зубцы кардиограмм;

-поведение пульса;

-поведение артериального давления и т.п.

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

В результате может оказаться, что:

-число средств лечения (S1, S2...) больше числа классов заболеваний (А1, А2,....); тогда их просто комплексируют или принимают решение о дополнительном распознавании противопоказаний;

-некоторые классы требуют одинаковых средств лечения (например, хирургическое вмешательство); тогда классы объединяют.

3-й шаг - из анализа имеющегося арсенала средств медицинской диагностики (кардиограф, фонокардиограф, УЗИ, рентген, анализ крови и т.д., и т.п.) и признаков классов заболеваний выделяют те признаки, которые реально определить имеющимися средствами ( Здесь возможны и решения о создании новых специальных средств диагностики).

Заметим, что те же действия предпринимались и для измерения признаков самолетов стороны В.

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

При этом для каждого класса должны быть выделены сведения:

-о наличии или отсутствии признаков качественного характера;

-о диапазонах или законах распределения признаков, имеющих количественное выражение.

Здесь также следует заметить, что все выбранные признаки должны получить соответствующее содержание (свое) для каждого класса.

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

Эти два примера показали, что подходы к построению систем распознавания практически ничем не отличаются, несмотря на специфику самих создаваемых систем.

В результате мы получили общие представления о последовательности решения и составляющих задачи создания системы распознавания. В результате отмечаем, что несмотря на различие предметных областей подходы к построению
СР - одинаковы. Система распознаваний заболеваний сердца строилась также, как и система распознавания самолетов, но заменить ее она не позволяет.
Точно также СР самолетов не может применяться для решения задач распознавания заболеваний сердца.

Системы распознавания объектов (явлений), создаваемые человеком всегда узко специализированы в отличии от его собственных природных возможностей.

Что же касается общего подхода к построению любой системы, то теперь, если у нас имеется некоторая совокупность объектов или явлений, которые необходимо распознавать (классифицировать), на основе обобщения действий при создании СР в 2-х рассмотренных примерах мы знаем, что последовательность решения соответствующих задач следующая:

-в соответствии с выбранным принципом совокупность объектов или явлений подразделяется на ряд классов (говорят: назначается алфавит классов);

-разрабатывается совокупность признаков (говорят: словарь);

-на языке словаря признаков описывается каждый класс;

-выбираются и (или) создаются средства определения признаков;

-на вычислительных средствах реализуется алгоритм сопоставления апостериорных и априорных данных и принимается решение о результатах распознавания.

В то же время, несмотря на выполненное определение последовательности действий, проведенное рассмотрение не позволяет ответить на следующие вопросы:

-как лучше производить разбиение объектов (самолеты, заболевания и пр.) по классам;

-как накапливать и обрабатывать априорную информацию;

-из каких соображений выбирать признаки;

-как описывать классы на языке признаков;

-на основе каких методов сравнивать априорную и апостериорную информацию;

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

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

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

Итак, главные выводы:

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

2. Каждая система распознавания индивидуальна и предназначается только для одного вполне конкретного вида объектов или явлений.

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

3. СР должна создаваться методом последовательных приближений внутренней структуры на ее математической модели по мере накопления необходимой информации.

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

Л Е К Ц И Я 2.2

Формулировка задач создания систем распознавания и методы их решения

ЗАДАЧА № 1

Определение полного перечня признаков (параметров), характеризующих объекты или явления, для которых данная система разрабатывается.

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

Можем себе представить такую неполноту в уже рассмотренной нами задаче распознавания самолетов как использование одного признака - потолок высоты полета самолетов. В результате - бомбардировщики не удастся отличать от истребителей ( при создании бомбардировщиков стремятся к обеспечению максимально возможной высоты полета, а при создании истребителей добиваются, чтобы они могли уничтожать бомбардировщики).

Реально даже целая группа признаков может оказаться неэффективной.

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

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

-детерминированные;

-вероятностные;

-логические;

-структурные.

А. Детерминированные признаки - это такие характеристики объектов или явлений, которые имеют конкретные и постоянные числовые значения.

Примерами детерминированных признаков могут быть, например, ТТХ бомбардировщиков и истребителей США (таблицы № 1, 2).

Числовые значения признаков по каждому из самолетов можно интерпретировать как координаты точек, представляющих каждый самолет в 11- мерном пространстве признаков.

Необходимо иметь в виду, что в задачах распознавания с детерминированными признаками ошибки измерения этих признаков не играют никакой роли, если, например, точность измерений такого признака, как размах крыльев самолета значительно выше (например, 1 мм), чем различие этого признака у разных классов самолетов (например, 10 м).

Представить такую систему, где используются детерминированные признаки не так трудно:

-распознавание принадлежности самолета, данные которого получены разведкой или из открытой печати и не привязаны к классам (бомбардировщик-
А1, истребитель-А2 и т.п.);

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

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

Б. Вероятностные признаки - это характеристики объекта (явления), носящие случайный характер.

С такими признаками в основном и имеют дело в природе и технике.

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

Таблица № 1

|Характерист| Т и п ы |
|ики |с а м о л е т о в |
| |В-1А |В-52 |В-57А |FB-111 |
|Экипаж |4 |6 |2 |2 |
|(чел.) | | | | |
|Vmax (кмч)|2330 |1020 |935 |2330 |
| | | | | |
|при H=15 км| | | | |
|Vmin (кмч)|1200 |500 |500 |1350 |
| | | | | |
|при H=0.3 | | | | |
|км | | | | |
|Потолок (м)|15240 |15000 |13750 |20000 |
|Бомб.нагруз|22 |34 |14 |16 |
|ка (т) | | | | |
|Макс.взлетн|180 |221 |25 |45 |
|ая масса | | | | |
|(т) | | | | |
|Размах |42 |56 |19 |21 |
|крыльев (м)| | | | |
|Длина |44 |48 |20 |22 |
|самолета | | | | |
|(м) | | | | |
|Кол-во |4 |8 |2 |2 |
|двигателей | | | | |
|Тяга |13.6 |7.7 |3.3 |9.2 |
|двигателей | | | | |
|(т) | | | | |
|Дальность |11000 |20000 |4380 |6600 |
|полета (км | | | | |

Таблица № 2

|Характериcтики|Т и п ы с а м о л е т о в |
| |F - 4 |F - 105|F - |F - |Хантер |
| |E |E |15 |100 D | |
| |Фантом|Тандер-|Игл |Супер-| |
| | |чиф | |сейбр | |
|Экипаж |2 |2 |1 |1 |1 |
|(чел.) | | | | | |
|Vmax |2330 |2230 |2655 |1400 |1000 |
|(кмч) | | | | | |
|при H =15 км| | | | | |
|Vmin (кмч) |1470 |1400 |1470 |1220 |1150 |
|при H =0.3 | | | | | |
|(км) | | | | | |
|Потолок (м) |19000 |15000 |21000|15000 |17000 |
|Бомб.нагр. (т)|7.2 |6.4 |- |3.4 |0.9 |
|Макс.взлетн. |26 |24 |25 |18 |11 |
|масса (т) | | | | | |
|Размах крыльев|12 |11 |14 |11 |10 |
|(м) | | | | | |
|Длина самолета|18 |21 |19 |12 |13 |
|(м) | | | | | |
|Кол-во |2 |1 |2 |1 |1 |
|двигателей | | | | | |
|Тяга |5.4 |12 |10.9 |5.3 |4.5 |
|двигателей (т)| | | | | |
|Дальность |885 |760 |1100 |860 |560 |
|полета (км) | | | | | |

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

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

Вспомним из теории вероятностей, чем характеризуется случайная величина - законом распределения вероятностей. То есть, точно так же законом распределения должен характеризоваться каждый вероятностный признак.

Вспомним и то, что в качестве законов распределения вероятностей в теории вероятностей выступают интегральная функция F(x) - интегральный закон или плотность распределения вероятностей (ПРВ) - дифференциальный закон f(x). При этом связь между ними:

[pic]

Вспомним, что самый распространенный в природе закон распределения - нормальный или Гауссов - имеет ПРВ

[pic]

Если предположить, что какой-либо вероятностный признак (например, размах крыльев, измеренный каким-либо средством измерений с ошибками) распределен по нормальному закону, то для 3-х условных классов, отличающихся размахами крыльев, распределения этого параметра будут выглядеть, как показано на рис.2.1.

Из рис. 2.1 видно, что если для неизвестного самолета мы с помощью упомянутого средства измерений определили размах крыльев Lкр с естественной случайной ошибкой , то с определенной вероятностью это измерение может быть отнесено к каждому из классов. Однако, легко заметить, что если это значение лежит ближе к одному из центров рассеяния
(например, Mx1), то вероятность отнесения его к соответствующему распределению, а значит и классу, максимальная.

f(Lкр)

Mx1 Mx2

Mx3 Lкр

Рис.2.1

Примеры вероятностных признаков распознавания:

-среднее значение мощности сигнала радиолокатора, отраженного от самолета (причина - изрезанность круговой диаграммы рассеяния сигнала радиолокатора самолетом и электронные и атмосферные шумы в том же радиолокационном диапазоне);

-размер листа растения (причины - отличия в питании, освещенности, влаги и т.п.);

-размер патологического изменения какого-либо органа человека
(причины - различные стадии заболевания при его обнаружении, различные ракурсы и сечения наблюдений образования и т.п.) и т.д.

В. Логические признаки распознавания - это характеристики объекта или явления, представленные в виде элементарных высказываний об истинности (“да”, "нет” или “истина”, “ложь”).

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

Примеры логических признаков:

-наличие ТРД на самолете ;

-боль в горле пациента ;

-кашель ;

-насморк ;

-растворимость реактива и т.д.

Здесь по каждому признаку можно сказать только то, что он есть, либо его нет.

К логическим можно отнести также такие признаки, у которых не важна величина, а лишь факт попадания или непопадания ее в заданный интервал.
(например, крейсерская скорость самолета больше или меньше 2000 км/ч).

Г. Структурные признаки - непроизводные (то есть, элементарные, не производимые из других элементарных признаков) элементы (символы), примитивы изображения объекта распознавания.

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

Примеры структурных признаков:

а)для изображения прямоугольника:

- горизонтальный отрезок прямой;

- вертикальный отрезок прямой.

б) для любого изображения на экране дисплея:

-пиксел.

Забегая далеко вперед в изложении материала, следует отметить, что традиционно для описания изображений использовались разложения его в ряды по ортогональным функциям (ряды Фурье, полиномы Эрмита, Лежандра,
Чебышева, разложения Карунена-Лоэва и др.).

Структурное описание в отличии от разложений:

-понятнее (физичнее) для человека, решающего задачу распознавания объекта;

-приемлемо и для компьютерной реализации при распознавании;

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

Оказывается, что оперируя ограниченным числом атомарных
(непроизводных) элементов (примитивов), можно получить описание разнообразных объектов. То есть, для отличающихся объектов можно иметь набор одинаковых непроизводных элементов. Но для того, чтобы описание можно было бы выполнить, наряду с определением непроизводных элементов должны вводиться правила комбинирования, определяющие способы построения объекта из упомянутых непроизводных элементов. В результате два одинаковых непроизводных элемента различных объектов могут быть соединены друг с другом по разным правилам. Это и будет их отличать.

В целом для описания какого-либо объекта непроизводные элементы объединяются в цепочки (предложения) по своему, характерному только для этого объекта, набору правил.

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

( Пример - код Фримена).

* * *

Таким образом, мы рассмотрели очень подробно 1-ую задачу создания систем распознавания - определение полного перечня признаков (параметров), характеризующих объекты или явления, для которых данная система разрабатывается. Главные выводы:

1) Выбор, назначение признаков распознавания - эвристическая операция, зависящая от творчества, изобретательности разработчика.

2) Состав признаков , выбираемых на этом этапе, должен быть как можно более разносторонним и полным, независимым от того, можно или нельзя эти признаки получить.

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

Л Е К Ц И Я 2.3

Формулировка задач создания систем распознавания и методы их решения

( продолжение)

ЗАДАЧА № 2

Первоначальная классификация объектов (явлений), подлежащих распознаванию, составление априорного алфавита классов.

Нам уже знакома на описательном уровне эта задача: необходимо выбрать
(назначить) классы объектов (явлений) распознавания. Решение ее осуществляется наиболее часто эвристически, как и выбор признаков распознавания, а логика ее решения следующая:

1-е - определяется, какие решения могут приниматься по результатам распознавания либо человеком, либо автоматической системой управления объектом (цель распознавания).

2-е - на основе определенной выше цели формулируются требования к системе распознавания, позволяющие выбрать принцип классификации.

3-е - составляется априорный алфавит классов объектов (явлений).

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

Тогда, очевидно, что требованием к системе (см.2-й пункт последовательности) - надежное (с высокой вероятностью) диагностирование каждого заболевания печени.

Следовательно, в априорный алфавит классов (см.3-й пункт рассмотренной последовательности) необходимо включить все возможные заболевания печени, а их - 11. То есть, классов распознаваемых заболеваний печени, диагностируемых некоторой гипотетической системой распознавания должно быть
11. Для более четкого понимания назовем эти классы:

1.Острый гепатит.

2.Хронический гепатит.

3.Жировая инфильтрация.

4.Цирроз.

5.Киста простая.

6.Киста паразитарная.

7.Абсцесс.

8.Опухоль.

9.Метастазы.

10.Гематома.

11.Конкременты.

Заметим, что, кроме ситуации, предложенной рассмотренной задачи, возможны и другие, когда количество классов, по которым надежно распознаются некоторые объекты (явления), заранее неизвестно и должно определяться самой системой распознавания. Эта задача называется задачей кластеризации, в которой можно отказаться уже от эвристического подхода.
Однако решение здесь достигается при выборе некоторых общих правил кластеризации, которые задает разработчик системы.

ЗАДАЧА № 3

Разработка априорного словаря признаков распознавания.

Решая задачу №1, мы должны были найти все возможные признаки распознавания заданных объектов или явлений. Точно также при решении задачи
№2 определился состав классов.

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

Таким образом, главное содержание рассматриваемой задачи построения СР
- создание словаря, обеспечиваемого реально возможными измерениями.

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

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

ЗАДАЧА № 4

Описание классов априорного алфавита на языке априорного словаря признаков.

Априорное описание классов - наиболее трудоемкая из задач в процессе создания системы распознавания, требующая глубокого изучения свойств объектов распознавания, а также и наиболее творческая задача.

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

Значения этих параметров описаний можно получить из совокупности следующих работ и действий:

-специально поставленные экспериментальные работы или -- экспериментальные наблюдения;

-результаты обработки экспериментальных данных;

-математические расчеты;

-результаты математического моделирования;

-извлечения из литературных источников.

Что же такое описание класса на языке признаков? Рассмотрим это отдельно для детерминированных, вероятностных, логических и структурных признаков.

Если признаки распознаваемых объектов - детерминированные, то описанием класса может быть точка в №-мерном пространстве детерминированных признаков из априорного словаря, сумма расстояний которой от точек, представляющих объекты данного класса, минимальна.

Легко себе представить такой эталон, вернувшись к рассмотренным нами таблицам ТТХ самолетов. Здесь мы имеем дело с 11-мерным пространством признаков. Каждая координата - это одна какая-нибудь характеристика, например “экипаж”. Если рассматривать только одну координату “экипаж”, то точкой эталона для истребителей будет - 1, для бомбардировщиков - 4. Это точки, суммы расстояний которых от всех истребителей и всех бомбардировщиков, представляющих эти два класса, минимальны.

Точно также это можно сделать по всем 11 координатам (т.е.
“потолок”, “размах крыльев”, ”бомбовая нагрузка “ и т.д.), в результате чего будем уже иметь дело с точками эталонов в 11-мерном пространстве.

Если признаки распознавания - логические, то для описания каждого класса необходимо прежде всего иметь полный набор элементарных логических высказываний A,B,C, входящих в состав априорного словаря. Но это только признаки. Для описания классов этого недостаточно. Еще необходимо установить соответствие между набором значений приведенных признаков A,B,C и классами W1, W2,...Wm.

Так для простоты понимания и без притязаний на медицинскую достоверность возьмем такой пример: необходимо распознавать два заболевания - обычная простуда и ангина (W1,W2), а в качестве логических признаков выберем

А - повышенная температура (А=0 - нет, А=1 - да);

В - насморк (В=0 - нет, В=1 - да);

С - нарывы в горле (С=0 - нет, С=1 - да).

Тогда так называемое булево соотношение между классом W1 (обычное простудное заболевание) и значениями признаками (а эти значения - бинарные) выглядит так

[pic]

Здесь умножение, как вы знаете, соответствует логическому “И”, а сложение - “ИЛИ”.

Точно также для второго класса заболеваний получим следующее описание

[pic]

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

Если распределение объектов распознавания, представляемых числовыми значениями их признаков по областям соответствующего пространства вероятностное, то для описания классов необходимо определить характеристики этих распределений. А из теории вероятности известно, что это

-функции ПРВ fi (x1,x2,....,xn), где x1.....xn - вероятностные признаки, I - номер класса;

-P(Wi) - априорная вероятность того, что объект, случайно выбранный из общей совокупности, окажется принадлежащим к классу Wi.

Как получить ПРВ классов системы распознавания? В распоряжении разработчика СР - три способа:

-экспериментальное определение по статистическим данным;

-теоретический вывод;

-моделирование.

То же касается априорной вероятности класса P(Wi).

Если признаки распознавания - структурные, то описанием каж-дого класса должен быть набор предложений (цепочек из непроизводных элементов с правилами соединения). Каждое из предложений класса - характеристика структурных особенностей объектов этого класса. Пример - код Фримена.

ЗАДАЧА № 5

Выбор алгоритма классификации, обеспечивающего отнесение распознаваемого объекта или явления к соответствующему классу.

Непосредственное решение задачи распознавания на основе использования словаря признаков и алфавита классов объектов или явлений фактически заключается в разбиении пространства значений признаков распознавания на области D1,D2,...,Dn, соответствующие классам
W1,W2,...,Wn (вспоминаем определение “образа”).

Указанное разбиение должно быть выполнено таким образом, чтобы обеспечивались минимальные значения ошибок отнесения классифицируемых объектов или явлений к “чужим” классам.

Результатом такой операции является отнесение объекта, имеющего набор признаков X1,X2,....,Xn (точка в n-мерном пространстве), к классу Wi, если указанная точка лежит в соответствующей классу области признаков - Di.

Разбиение пространства признаков можно представлять как построение разделяющих функций fi(x1,x2,....,xn) между множествами (областями) признаков Di, принадлежащим разным классам.

Упомянутые функции должны обладать следующим свойством:

-если объект, имеющий вектор признаков [pic] фактически относится к классу [pic], то значение разделяющей функции

[pic] должно быть большим, чем значение ее для класса [pic]- [pic] (здесь индекс q - означает номер класса, к которому принадлежит вектор признаков).

Отсюда легко определить выражение решающей границы между областями
Di, соответствующим классам Wi:

[pic]

Для двух распознаваемых классов разбиение двумерного пространства выглядит так (рис 2.2). Физически распознавание основывается на сравнении значений той или иной меры близости распознаваемого объекта с каждым классом. При этом если значение выбранной меры близости (сходства) L данного объекта w с каким-либо классом Wg достигает экстремума относительно значений ее по другим классам, то есть

[pic]

то принимается решение о принадлежности этого объекта классу Wg, то есть w[pic]Wg.

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

X1 o o o o xx x o o o x o o F2(X1,X2) > F1(X1,X2) x x x o o o o x o o o o o x x x x x o o o o o

F1(X1,X2)>F2(X1,X2) x o

x x x x x x x o o x x x x x x x x x x x

X2

Рис.2.2

В алгоритмах распознавания, использующих детерминированные признаки в качестве меры близости, используется среднеквадратическое расстояние между данным объектом w и совокупностью объектов (w1,w2,....,wn), представляющих (описывающих) каждый класс. Так для сравнения с классом Wg это выглядит так

[pic]

где kg - количество объектов, представляющих Wg-й класс.

При этом в качестве методов измерений расстояния между объектами d(w,wg) могут использоваться любые методы (творческий процесс здесь не ограничивается).

Так, если сравнивать непосредственно координаты (признаки), то

[pic]

где N - размерность признакового пространства.

Если сравнивать угловые отклонения, то рассматривая вектора, составляющими которых являются признаки распознаваемого объекта w и класса wg, будем иметь:

[pic]

где ||Xw|| и ||Xwg|| - нормы соответствующих векторов.

В алгоритме распознавания, использующем детерминированные признаки можно учитывать и их веса Vj (устанавливать степень доверия или важности). Тогда рассмотренное среднеквадратическое расстояние принимает следующий вид:

[pic]

В алгоритмах распознавания, использующих вероятностные признаки, в качестве меры близости используется риск, связанный с решением о принадлежности объекта к классу Wi, где i - номер класса. (i=1,2,..,m.).

Описания классов, как мы недавно рассмотрели

[pic]

В рассматриваемом случае к исходным данным для расчета меры близости относится платежная матрица вида:

[pic]

Здесь на главной диагонали - потери при правильных решениях. Обычно принимают Сii=0 или Cii R2

Вывод:

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

Следствие:

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

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

Л е к ц и я 4.2

Оптимизация алфавита классов и словаря признаков

(продолжение)

4.2.1. Взаимосвязь размерности вектора признаков и эффективности СР

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

Итак, докажем, что с увеличением числа признаков вероятность правильного распознавания неизвестных объектов также увеличивается.

Рассмотрим такое доказательство, допуская, что

- для каждого k-го признака распознавания существует некоторая вероятность такого события Ak, когда решение о принадлежности объектов к Wi классу принимается однозначно.

-признаки распознавания независимы между собой.

Независимость признаков означает и независимость событий Ak
(событий принятия однозначных решений о принадлежности).

Обратимся к теории вероятностей. Вероятность наступления двух совместных или несовместных событий A1 и A2

P (A1 + A2 ) = P (A1 ) + P (A2 ) - P (A1 A2 )

Отсюда для трех событий получим

P (A1 + A2 + A3 ) = P [A1+ (A2 + A3 )] = P (A1 ) + P (A2 + A3 ) - P [A1 (A2

+ A3 )] = P (A1 ) + P (A2 ) + P (A3 ) - P (A2A3 ) - P (A1A2 + A1A3 ) =

=P (A1 ) + P (A2 ) + P (A3 ) - P (A2 A3 ) -[ P(A1A2 ) + P (A1A3 ) - P

(A1A2A3 )]

или

[pic]

Точно также для четырех событий

[pic]

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

[pic]

=[pic]

(Наиболее просто эту разность получить, не доводя уменьшаемое до конечного вида

[pic]

[pic]

Теперь по индукции можно записать:

[pic]

Из приведенного выражения следует, что если не достигнута предельная вероятность правильного распознавания, то есть:

[pic]

то при любом ( имеем

[pic]

Это является доказательством возрастания вероятности при увеличении числа признаков.

Таким образом, последовательность

[pic]

при [pic] является монотонно возрастающей, а значит и сходящейся, так как предел возрастания - “1”.

Для сходящейся последовательности

[pic] а значит

[pic] что и требовалось доказать.

Следствие:

Снижение эффективности распознавания за счет увеличения числа классов может быть скомпенсировано увеличением размерности вектора признаков.

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

4.2.2. Формализация задачи оптимального взаимосвязанного выбора алфавита классов и словаря признаков

Решая задачу повышения эффективности СР за счет увеличения размерности вектора признаков, мы не обращали внимания на то, что указанное увеличение - это часто возрастание числа технических средств измерений, каждое из которых обеспечивает определение одного или группы признаков. Значит при этом растут расходы на построение СР. А ресурсы часто ограничены.

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

4.2.2.1. Формализация исходных данных

Пусть задано множество объектов или явлений

W ={w1 , w2 ,....,wl };

(например, W=самолеты, а w1 -пассажирский самолет Ту-154 , w2 - военно-транспортный самолет АН-12, w3 - истребитель МИГ-29 и т.д.).

Введем множество из r возможных вариантов разбиения этих объектов W на классы (варианты алфавита классов)

A ={A1, A2, ..., Ar}

(например, A1 - 2 класса - пассажирские, военные (m1 =2); A2 -5 классов - истребители, бомбардировщики, штурмовики, пассажирские, военно- транспортные (m2 =5) )

Таким образом, с учетом возможного отказа от решений в каждом варианте множество объектов W подразделяется на свое число классов: в варианте A1 - на (m1 +1) классов; в варианте A2 - на (m2 +1) классов;

...........................................................

в варианте Ar - на (mr +1) классов.

Иными словами здесь мы располагаем r алфавитами классов.

В соответствии с вариантом алфавита классов (As) исходные объекты
(явления) разбиваются на ms "решающих" классов

W = {W(1/As ), W(2/As ), W(3/As ),....... , W(ms /As )},

где естественно "1", "2",..... - номера классов; As - вариант алфавита классов, где s=1,2,....,r.

Например:

W(1/As ) = {W1 ,W2 ,..Wk }; W(2/As ) = { Wk+1 ,Wk+2 ,..,Wl }

и т.д.

Таким образом, мы располагаем подмножествами классифицированных объектов.

Если при этом располагаем априорным словарем признаков

_

X = { x1 , x2 , ..., xn }, и притом размеры указанных подмножеств классифицированных объектов таковы, что соответствующие выборки признаков представительны (в каждом классе достаточное в статистическом смысле число объектов),то тогда тем или иным способом может быть проведено описание каждого из классов на языке этого словаря.

В детерминированном случае это достаточно просто. Каждый класс имеет свои эталоны со своими характеристиками как наборами параметров, представляющих собой признаки распознавания:

Xik [W(j/As )],

__ где i = 1,n - число признаков распознавания;

__ j = 1,m - число классов;

___ k = 1,Nэj - число эталонов в j-том классе.

При статистическом подходе (вероятностные признаки и вероятностная
СР) описание это:

- априорные вероятности классов P[W(i/As )];

_

- функции условных ПРВ f{X/[W(i/As )]};

Если же объем выборок объектов по подмножествам недостаточен для непосредственного описания классов, то эти описания, как мы знаем, могут быть получены с помощью процедуры обучения.

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

Если бы не было ограничений на величину ресурсов, ассигнуемых на построение СР, а именно на создание измерительных средств, предназначенных для определения признаков, то можно было бы считать, что как алфавит классов, так и словарь признаков определены и можно приступать к построению системы.

Реально при создании сложных систем не бывает без указанных ограничений. При этом, когда речь идет об ограничениях, это не обязательно финансовые ограничения. Достаточно часто в качестве таковых могут выступать ограничения на быстродействие, память и т.п.

4.2.2.2.Выигрыш распознавания и оптимизация алфавита классов и словаря признаков в условиях ограничений

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

_

V ={v1 ,v2 ,...,vn }, компоненты которого vj равны 1, если данный признак априорного словаря используется в рабочем и 0 в противном случае. Этот вектор носит название вектора отбора.

Располагая стоимостями измерения каждого j-го признака Сj , имеем общие затраты на реализацию априорного словаря признаков

Сапр =[pic]

Для рабочего словаря будем иметь

Сраб =[pic]

При наличии конкретной величины ассигнованных ресурсов (C0 ) на создание СР ограничения, о которых идет речь, формализуются в виде следующего неравенства

С0 >=[pic]

Если в конечном итоге интересоваться вектором отбора, то возникает следующая экстремальная задача:

в пределах выделенных ассигнований на создание СР (C0) еобходимо найти такое пространство признаков, при котором обеспечивается максимальное значение некоторого критерия эффективности СР.

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

Обращая внимание на тот факт, что без критерия эффективности такая задача не решается, введем его.

В соответствующей литературе приводится несколько требований, которыми следует руководствоваться при выборе показателя эффективности:

1) показатель эффективности должен характеризовать систему как единое целое.

2) показатель эффективности должен обеспечивать возможность получения количественной оценки с требуемой достоверностью.

3) область изменения показателя эффективности должна иметь четко очерченные границы.

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

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

Составляющими такого выигрыша от применения СР являются частные выигрыши от отнесения неизвестного объекта к тому или иному классу.

Обозначим такую составляющую в i-ом классе s-ого варианта алфавита классов так:

Gs [W(i/As )].

Что же такое "выигрыш"? Что можно выиграть в управляющем решении?

Рассмотрим в общем виде два примера:

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

2) В военном деле мы можем иметь дело с отнесением к классу опасных не только боевых частей (БЧ) ракет, но и ложных целей (ЛЦ), их имитирующих. При этом вынуждены будем обстрелять (а это и есть решение по результатам распознавания) и БЧ и каждую ЛЦ. В этом случае мы имеем проигрыш, измеряемый ценой ПР и затратами на их пуски. Если же мы все- таки часть ЛЦ распознаем и отнесем к соответствующему классу, то сэкономим часть противоракет ПР. Если же все ЛЦ отделим от БЧ баллистических ракет
(БР), то выигрыш будет максимальным.

Таким образом, в каждом конкретном случае выигрыш специфичен. Но чем он больше, тем лучше.

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

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

[pic] где -[pic]- апостериорная вероятность правильного отнесения объекта к Wi
-му классу (то есть, после измерения вектора признаков и их отбора).

Теперь сформулированная нами задача может быть формализована следующим образом:

[pic] при C0 >=[pic]

Здесь A0 ,v0 - искомое решение, обеспечивающее выбор варианта разбиения на классы (алфавит классов) и определения рабочего словаря признаков.

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

Т е м а 5

Моделирование систем распознавания образов - методология их создания и оптимизации

Л Е К Ц И Я 5.1

Введение в моделирование

5.1.1. История вопроса

История моделирования начинается фактически с истории математики, а также с появления графического и пластического искусств, известных нам по памятникам ранних цивилизаций. Так элементы математического моделирования существовали уже в период зарождения математики. Одним из первых примеров четко сформулированной математической модели является теорема Пифагора (VI век до нашей эры).

Рассмотрим компьютерную реализацию теоремы Пифагора в ее наиболее простой интерпретации

[pic]

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

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

Теорема Пифагора возглавляет длинный список классических примеров математических моделей, среди которых

-законы движения Ньютона (XVII в);

-полиномы Эйлера (XVIII в);

-волновые уравнения Максвелла (XIX в);

-теория относительности Эйнштейна (XX в).

Характеризуя существо математического моделирования, следует определить математическую модель как абстрактное математическое представление отображаемого объекта, явления, процесса .

Графические и пластические искусства в отличие от математики возглавили ряд методов, получивших название аналогового моделирования.

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

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

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

Значимость происшедшего скачка достаточно убедительно характеризует такой пример первых проб компьютерной реализации моделей. В начале 50-х годов в университете Дж. Гопкинса в США был построен имитатор воздушного боя, состоявший из механических элементов. Каждый вариант боя проигрывался на нем вручную несколькими участниками и длился 3 часа.

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

Несколько позже рассмотренная аналоговая модель была формализована в математическую и запрограммирована на ЭВМ ЮНИВАК 1103А. В итоге время реализации одного варианта моделирования уменьшилось почти в 10000 раз.
Эффект, достигнутый при переходе к ЭВМ, был феноменальным.

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

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

-в военных играх;

-в исследованиях боевых операций;

-в испытаниях и исследованиях сложных систем вооружения.

В то же время постепенно моделирование находило все большее применение во всех невоенных областях человеческой деятельности:

-в физических и технических науках;

-в коммерческой деятельности;

-в медицине;

-в юриспруденции;

-в библиотечном деле;

-в социальных науках.

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

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

Усложнение аппаратуры влечет за собой усложнение ее проектирования и производства. Нужно отметить, что организация деятельности многочисленных участников процесса разработки, упорядочение использования технологического и испытательного оборудования и т.д. превратились в ХХ веке в тяжелые системотехнические проблемы.

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

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

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

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

Уникальность и дороговизна сложных систем практически исключает традиционные эмпирические методы их проектирования путем “доводки” аппаратуры на серии опытных образцов. В ряде случаев сложную систему вообще не успевают испытать в течение всего периода эксплуатации. При этом проверка в аварийных ситуациях, как правило, оказывается вообще невозможна (АЭС в аварийных ситуациях).

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

Во-вторых, частные данные (то есть, для отдельных состояний), получаемые в процессе длинных математических выкладок и вычислений, не имеют, к тому же, наглядной физической интерпретации. Это затрудняет:

-выявление первопричин окончательного поведения системы -может потребоваться проведение повторных аналитических выводов и расчетов; только полный объем вычислений по системе в целом характеризует ее исследуемый вариант);

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

Таким образом, при исследовании сложных систем как часто невозможен натурный эксперимент, так и крайне ограничены возможности аналитических и численных расчетов.

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

Сочетание неполного натурного эксперимента с экспериментом на указанной модели получило название опытно-теоретического метода испытаний сложных систем.

В основе этого метода - создание на ЭВМ модели системы, позволяющей не только получить выходные показатели, но и исследовать взаимные связи процессов, элементов и поведение сложной системы в различных условиях эксплуатации при изменяемых значениях параметров и переменных.

5.1.2. Основные определения

Термин “моделирование” имеет в литературе много различных толкований.
Наиболее приемлемым на взгляд многих авторов является такое определение:

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

И как дополнение можно использовать следующее определение:

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

Отправной точкой при построении модели технической системы следует считать описание.

Описание - совокупность сведений об исследуемой системе и условиях, при которых необходимо провести исследования.

Описание представляется в виде:

-схем;

-текстов;

-формул;

-таблиц экспериментальных данных;

-характеристик внешних воздействий и окружающей систему внешней среды.

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

В качестве примера можно без достаточной детализации рассмотреть описание модели системы распознавания речи.

Здесь, во-первых, исходя из того, что описание - это сведения о системе и условиях ее применения, нужно более точно определить систему распознавания речи, Например:

“Система распознавания речевых команд управления подъемом стекол автомобиля в процессе его эксплуатации”.

Для такой системы описание модели должно включать:

-схему речевого аппарата человека и теоретические положения речеобразования;

-описание условий речевого управления (шумы двигателя, шумы окружающей среды и т.д.);

-характеристики микрофона, как датчика сигналов, воспринимающего команду (зависимость выходных сигналов от звукового давления во всем диапазоне частот, например, в виде таблиц);

-характеристики сигналов управления (мощность, направленность, удаленность от микрофона);

-характеристики канала приема электрических сигналов на входе преобразователя “аналог-цифра” компьютера (чувствительность, дискретность, точность и т.п.);

-математические зависимости, применяемые для обработки принятого сигнала с целью получения признаков распознавания и классификации;

-способ преобразования результатов распознавания в команды управления;

-характеристики канала передачи команд управления;

-требования к величинам сигналов управления двигателями подъема стекол. и т.д. и т.п. )

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

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

Другими словами (основываясь на рассмотрении описания системы как функции внешних воздействий) , при моделировании производится аппроксимация функции-описания более простой и удобной для машинного представления функцией-моделью .

Аналогия между построением модели и аппроксимацией позволяет использовать для наглядности представлений аппроксимацию функции w(x) на некотором отрезке [a,b] линейной комбинацией

[pic]

Здесь [pic] - модель функции-описания w(x) характеризуется n параметрами (числовыми коэффициентами (i );

( i (x) - некоторые возможные простые функции, заданные на том же отрезке [a,b].

Теперь, исходя из характеристики модели (см. выше положение о том, что модель воспроизводит систему с упрощениями), варьируя параметрами
(i , необходимо получить наилучшее или удовлетворяющее исследователя (в некотором смысле) приближение функции-модели к функции-описанию.

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

[pic] где Qw - скалярный показатель, который намереваются получить при исследовании системы (например, производительность, надежность, пропускная способность); Q( - скалярный показатель, соответствующий Qw, но полученный при анализе модели (.

При этом описание w(x) и модель ((x) отождествлены с векторами w и ( некоторого многомерного пространства.

Если при этом описание полностью характеризует систему и ее состояния и существует некоторое взаимно-однозначное преобразование [pic]

[pic]

и

[pic]

то модель и система (в крайнем случае ее описание) изоморфны.

При выполнении только второго соотношения, то есть при отсутствии обратного преобразования, имеем дело с гомоморфностью.

Л Е К Ц И Я 5.2

Моделирование сложных систем и применение моделей

5.2.1. Принципы построения модели сложной системы

а) Принцип декомпозиции

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

С этих позиций, к особенностям сложной системы следует отнести такие:

1)Сложную систему можно расчленить на конечное число подсистем, а каждую подсистему, в свою очередь, - на конечное число более простых субподсистем до тех пор, пока не получим элементы системы ( под элементами системы следует понимать объекты, которые в условиях данной задачи не подлежат расчленению на части) .

2)Элементы сложной системы функционируют во взаимодействии друг с другом.

3)Свойства сложной системы определяются не только свойствами отдельных элементов, но и характером взаимодействия между ними.

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

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

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

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

[pic]

или после упрощения и преобразований

[pic],

где [pic], [pic]

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

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

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

Примерами декомпозиции при создании модели системы распознавания заболеваний внутренних органов человека могут быть варианты разбиения ее на элементы и блоки компьютерной системы, построенной на основе ультразвуковой медицинской диагностики. Структурная схема одного такого варианта при достаточно поверхностной декомпозиции представлена на рис.
5.2.1.

Модель отражающих Модель ультразву- свойств внутренне- кового локатора, го органа человека в являющегося ос- ультразвуковом новным элементом диапазоне волн аппарата УЗИ

Модель алгоритма

обработки изображе- ний внутреннего ор- гана

Модель алгоритма анализа и принятия решения

Рис 5.2.1. Структурная схема варианта декомпозиции системы распознавания

Более детальная декомпозиция позволяет представленные блоки расчленить на субблоки и элементы. Так , например, могут быть детализированы первые два из блоков рассмотренной схемы (Рис.5.2.2).

Точно также могут быть подвергнуты декомпозиции и другие модули структурной схемы, приведенной на рис.5.2.1. В результате появляется возможность для узких специалистов на основе физико-математического описания разработать алгоритмы их и затем комплексировать в общий алгоритм модели системы.

а) Принцип допустимых упрощений

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

Модуль описания Модуль описания геометрической возможных поло- формы внутрен- жений потологи- него органа ческих образо- ваний в органе

Модуль описания Модуль описания положений функцио- геометрических нальных элементов характеристик внутреннего органа потологических

образований

Модуль выбора условий наблюде- ния внутреннего органа
(сечение)

Модуль описания звукодинамичес- ких свойств се- чения органа

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

Модуль формирования ультазвуково- го изображения сечения органа

на модель алгоритма обработки изображений

Рис.5.2.2. Структурная схема декомпозиции модели отражающих свойств и ультразвукового локатора

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

Такие возможные недостатки исходного алгоритма модели вытекают из различия целей моделирования отдельных элементов и сложной системы в целом.

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

-непомерно возрастает время счета одной реализации функционирования системы в целом;

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

И это при том, что всегда существуют более простые реализации элементов по сравнению с предложенными “сходу”. К тому же с точки зрения влияния на конечную точность моделирования системы вклады отдельных элементов могут оказаться несущественными, а значит сами описания алгоритмов их функционирования могут допускать упрощения.

Поэтому модель системы в целом должна строиться на основе компромисса между ожидаемой точностью оценок конечного показателя и сложностью самой модели.

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

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

-более углубленное аналитическое изучение и представление работы физического аналога;

-экспериментальные исследования физического аналога.

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

При заменах блоков упрощенным эквивалентом отказываются от точного описания

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

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

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

-неравномерной эмиссией электронов (так называемый “дробовой шум) в электровакуумных приборах;

-неравномерностью процессов генерации и рекомбинации носителей тока в полупроводниковых приборах.

При построении модели указанного измерителя возможны:

1)Строгое физико-математическое описание указанных неравномерностей движения носителей тока и их влияния на измеряемую величину ("модель с точностью до носителя").

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

3)Экспериментальные статистические исследования ошибок измерителя, получение закона распределения вероятностей ошибок и замена точного блока на блок генерации случайных ошибок с заданным законом распределения, добавляемых к “чистым” измерениям.

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

Отсюда следует, что при соответствующих заменах блоков каждый эксперимент на системной модели должен носить случайный характер.

5.2.2. Моделирование сложных систем и опытно-теоретический метод их испытаний

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

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

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

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

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

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

2)Проведение параметрической доработки модели на основе сравнения результатов натурных экспериментов и моделирования, если структура модели удовлетворительна.

3)Проведение структурной перестройки модели, дополнительный учет отдельных факторов, дополнение связей при наличии остаточной разности между выходными характеристиками после попытки параметрической доработки.

4)Проверка статистической совместимости модели и системы в ряде целенаправленно выбранных точек факторного пространства.

5)На основе выполненной калибровки модели (пункты 1-4) распространение результатов испытаний системы с помощью моделирования на всю область факторного пространства.

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

Упомянутый при этом отказ от создания системы в целом, замена ее испытаний на испытания отдельных узлов, модулей, составляющих и т.п. отражается на построении модели системы. Дело в том, что некоторые результаты испытаний могут позволить, например, отдельные составляющие системы не моделировать, описывая соответствующие физические процессы, не искать для них точных математических описаний для реализации, а воспользоваться полученными экспериментальными данными. Так, можно не моделировать уходы параметров отдельных электронных и электромеханических устройств, приводящие к их отказам, если в результате испытаний получены характеристики надежности этих устройств (вероятность безотказной работы в течение рабочего цикла, наработка на отказ, время безотказной работы). То есть, натурные испытания могут явиться основанием для упрощения модели при сохранении ее изоморфности системе.

Рассмотренный путь упрощения - не единственный. Во-первых, уже упомянутый нами компромиссный характер создания модели системы (между точностью и возможностью реализации) дает в отдельных случаях такие основания. Тогда, как уже упоминалось можно отказаться от некоторых деталей моделирования. Во-вторых, задачи, ставящиеся перед моделью могут быть различными: оценка функционирования системы, оценка взаимодействия системы с другими сложными системами, оценка характеристик системы во всем диапазоне условий функционирования и т.д. Это приводит к тому, что при испытаниях сложных систем имеют дело не с одной единственной моделью. Так по своему назначению модели делятся на частные и системные.

Частные модели - это модели отдельных частей системы (подсистем, узлов, агрегатов), позволяющие при высокой точности моделирования этих частей получить исходные данные для использования в системной модели. В результате системная модель не будет перегружена соответствующими частными задачами, то есть, упростится и сможет стать реализуемой в приемлемое время (например, в реальное время), с приемлемым быстродействием и в допустимом объеме.

Системные модели включают в свой состав элементы, отражающие в той или иной степени работу всех частей системы или напрямую используют отдельные части системы. Они позволяют получить показатели качества всей системы в целом. А так как таких показателей может быть несколько, то и системных моделей может быть несколько. При таком разделении функций исчезает сложность разрабатываемых моделей. Этим, в частности, объясняется деление системных моделей на функциональные и комплексные. И если функциональные модели предназначаются для испытаний функционирования сложной системы в различных ситуациях, то комплексные обеспечивают:

-отработку и отладку программного обеспечения сложной системы;

-оценку характеристик отдельных средств и получение исходных данных для полной оценки системы.

Л Е К Ц И Я 5.3

Метод статистических испытаний

(метод Монте-Карло)

5.3.1. Основное определение

Из рассмотрения принципов построения моделей сложных систем следует, что при упрощениях модели и замене блоков, описывающих, как правило, воздействия на систему и ее части, эксперимент на системной модели сложной системы достаточно часто приобретает случайный характер. Случаен в силу этого и выходной эффект системы от запуска модели к запуску. Для проведения моделирования в таких условиях наиболее приемлемым является метод моделирования, основанный на статистических испытаниях, так называемый метод Монте-Карло.

Приемлемость указанного метода обусловливается тем, что

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

2)просто и точно определяется необходимый объем моделирования из условия достижения заданной точности оценок выходных показателей.

3)методика организации экспериментов на модели достаточно проста и хорошо программно реализуема.

В этом легко убедиться на простых примерах. А пока рассмотрим определение.

Метод статистических испытаний (метод Монте-Карло) состоит в решении различных задач вычислительной математики путем построения для каждой задачи случайного процесса с параметрами, равными искомым величинам этой задачи. .

Рассмотрим простейшие примеры.

А. Пусть необходимо определить вероятность Pч того, что суммарное число попаданий при стрельбе в “десятку” мишени при 10 выстрелах - четно.

Известно, что если вероятность попадания в “десятку” при одном выстреле равна p , то искомая вероятность согласно биномиальному закону распределения вероятностей вычисляется так:

[pic]

Здесь [pic] - число сочетаний из 10 по 2k.

Если предварительно подсчитать все числа сочетаний при k=0…5 или использовать готовую таблицу сочетаний, то вычисления Pч по указанной формуле потребуют 26 операций.

Вместо такого расчета можно было бы экспериментально выполнить N серий стрельб по 10 выстрелов и определить из их числа количество серий nч
, в которых число попаданий в “десятку” - четное. Тогда при достаточно большом N имеем

[pic]

Однако при таком подходе для получения достоверными в оценке Pч двух знаков после запятой потребуется около 10 000 серий по 10 выстрелов.

Оказывается, что ЭВМ позволяет выполнить решение указанной задачи третьим способом.

Как известно многие языки программирования имеют в составе стандартных функций датчик случайных чисел, позволяющий формировать случайную последовательность равномерно распределенных чисел на интервале
[0,1].

Поэтому вместо выстрела по мишени достаточно выбрать из датчика указанное число со значением x и проверить выполнение неравенства x