Количество серий третьего этапа формирования и определяет частость которая при N (( стремится к искомой величине Pч . Б.Еще один пример, но из области непосредственного применения метода Монте-Карло к вычислению интегралов. Пусть необходимо вычислить При этом будем считать, что 0 функция лежит в единичном квадрате. Такое ограничение не влияет на общность задачи, так как любой интеграл заменой переменных и изменением масштаба может быть приведен к рассматриваемому. Y 1 y = g(x) x 1 Рис.5.3.1. Будем рассматривать две области на плоскости (x,y) ( - область, заданная неравенствами 0 0 w - область, ограниченная кривой y = g(x) и ординатами x=0 и x = 1. Площадь области ( равна единице S1=1, а площадь области w(2 = I. Зададим в области ( равномерное распределение случайных точек. Это означает, что вероятность попадания точки с координатами xi , yi в область ( равна 1, а в некоторую часть этой области - пропорциональна площади этой области независимо от ее расположения внутри (. Плотность заданного распределения вероятностей f(x,y) = 1 Поэтому вероятность попадания точки в область w равна Таким образом, I = S2. Если теперь мы располагаем возможностью имитировать случайные точки с координатами xi, yi в соответствии с заданной плотностью, то после N испытаний, подсчитав число тех из них (m), которые попали в область w , получим частость Вспоминаем, что частота при N (( стремится к истинному значению, а в качестве приближенного значения интеграла следует использовать указанную частоту. Подводя итог рассмотренному примеру с точки зрения введенного определения метода Монте-Карло, отметим, что -решаемая задача относится к области вычислительной математики; -для решения задачи формировалась случайная последовательность чисел как выборка значений из последовательности с равномерной плотностью распределения вероятностей, попадающих в область w; -искомая величина определялась как отнесение числа попаданий в область w к общему числу экспериментов. Рассмотренных примеров уже вполне достаточно для того, чтобы пояснить данное в начале определение метода статистических испытаний. В то же время следует иметь в виду , что существует большое многообразие задач, для которых метод Монте-Карло является плодотворным, позволяя достигать инженерного результата там, где аналитические методы либо сложны, либо не дают ответа. В этом аспекте необходимо отметить такие области применения, как -многомерные интегралы; -теория обнаружения сигналов; -обращение матриц и решение систем линейных алгебраических уравнений; -некоторые краевые задачи; -нахождение собственных значений и собственных функций и др. 5.3.2.Принципы получения случайных величин на ЭВМ Датой рождения метода Монте-Карло принято считать 1949 г , когда в американском журнале ассоциации статистиков появилась статья Метрополиса и Улама “ Метод Монте-Карло”. Создателями метода считают Дж.Неймана и С.Улама. В Советском Союзе первые статьи о методе относятся к 1955-1956 годам. Теоретические основы метода Монте-Карло известны уже давно. Более того, некоторые задачи статистики решались с использованием случайных выборок, то есть, фактически этим методом. Но так как моделировать случайные величины вручную - очень трудоемкая работа, широкое применение метода началось с появления вычислительных машин. Само название “Монте-Карло” происходит от названия города в княжестве Монако, знаменитого своими игорными домами. Все дело здесь в том, что одним из простейших механических устройств для получения случайных величин является рулетка. Простейшая схема ее - вращающийся диск с цифрами, резко останавливающийся для определения цифры, на которую указывает неподвижная стрелка. Пуская и останавливая рулетку и объединяя получаемые в каждом пуске цифры в группы заданного размера (например, пять), можно составить таблицу случайных цифр (в случае примера группирования - пятизначную). Таблица эта носит название таблицы случайных чисел, хотя правильнее было бы назвать ее таблицей случайных цифр. Самая большая такая таблица (RAND Corporation, 1955 г) содержит 1 000 000 цифр. Составление таблиц случайных чисел - не такая простая задача. Если мы хотим иметь хорошую таблицу, то придется при разработке ее тщательно проверять, так как любое физическое устройство вырабатывает случайные числа отличающимися по распределению от равномерного. Ну, а используются такие таблицы либо для ручного счета, что сегодня - редкость, либо при машинном применении приходится поступаться тем, что при вводе соответствующий файл потребует большой памяти в ущерб решаемым при этом задачам. Для устранения этого недостатка казалось бы легче подключить рулетку к ЭВМ. Однако ясно, что быстродействие такого комплекса генерации случайных чисел будет исключительно низким. Поэтому в качестве генераторов случайных величин чаще используются шумы в электронных лампах. Например, здесь может быть предложен следующий алгоритм. Если за некоторый фиксированный промежуток времени (t уровень шума превысил заданный порог четное число раз, то в разряд некоторого числа записывается единица, если нечетное - ноль. Так как количество такого рода генераторов выбирают равным количеству разрядов упомянутого числа в ЭВМ, то во все эти разряды будут записаны нули и единицы. Каждый такт такой логической проверки всех генераторов дает одно полноразрядное число, равномерно распределенное в интервале [0,1]. Недостатки этого метода генерации: 1)Возможны неисправности электронных генераторов шума, приводящие к пропаданию равновероятности нулей и единиц, что требует постоянных проверок и ремонта. 2)Невозможно повторение случайной последовательности чисел, полученной в одном эксперименте, для проверки работы программы ЭВМ. Поэтому такого рода датчики применяются в специализированных ЭВМ для решения задач методом Монте-Карло. Для универсальных ЭВМ такие датчики - слишком дорогостоящее оборудование, так как в таких ЭВМ прибегают к расчетам с использованием случайных чисел достаточно редко. Но чтобы не исключить полностью такую возможность здесь лучше использовать так называемые псевдослучайные числа. Генерация псевдослучайных чисел осуществляет сама машина в соответствии со специальными стандартными функциями, предусматриваемыми в ее математическом обеспечении. Можно вообще не интересоваться, как эти числа получаются. Указанные стандартные функции неоднократно проверяются разработчиками и качество их гарантируется. Однако сама постановка вопроса “получение псевдослучайных чисел” на ЭВМ вызывает недоумение. Ведь все, что делает машина, должно быть заранее запрограммировано. Поэтому хотелось бы понимать, откуда появляется случайность. Кроме того, без понимания особенностей псевдослучайных последовательностей, хотя бы поверхностного, трудно говорить иногда о их разумном использовании. Что же такое псевдослучайные числа? Числа, получаемые по какой-либо формуле и имитирующие значения случайной величины, называются псевдослучайными. Под словом “имитирующие” подразумевается, что эти числа удовлетворяют ряду требований так, как если бы они были значениями случайной величины. Первый алгоритм для получения псевдослучайных чисел был предложен Дж.фон Нейманом в 1951 г. Он получил название метода середины квадратов. . Существо его заключается в следующем. Пусть задано произвольное 4-значное целое число n1= 9876. Возведем его в квадрат и получим 8-значное число n12 = 97535376. Выберем 4 средние цифры из этого числа и обозначим n2= 5353. Затем снова возведем его в квадрат n22 = 28654609 и выберем 4 средние цифры. В результате получим n3 = 6546. Продолжая указанные рекуррентные действия будем иметь n4 = 8501; n5 = 2670; n6 = 1289 и т.д. В качестве псевдослучайных значений предлагалось использовать (к = 10 -4 *n к , то есть: 0.9876; 0.5353; 0.6546; 0.8501; 0.2670; 0.1289 и т.д. Таков самый простой алгоритм, обладающий отдельными недостатками, на которых не будем задерживать внимание. Главное то, что они заставили в последующем обратиться к более сложным алгоритмам. Но схема получения псевдослучайных чисел осталась фактически неизменной: очередное значение получается из предыдущего или предыдущих. Рассмотрение теории вопроса и других алгоритмов не входит в планы нашего курса, но нам необходимо знать один важный вывод из соответствующих разделов, имеющий практическое значение: рекуррентно получаемые псевдослучайные последовательности обладают периодом, величина которого зависит главным образом от разрядности представления чисел в машине. С точки зрения теории вероятностей - это плохо. Однако там, где длины генерируемых последовательностей удовлетворяют потребителя, появляется такое достоинство как возможность отработки программного обеспечения сложных систем при одних и тех же последовательностях. Ну, а рекуррентность получения псевдослучайных последовательностей и определенный период позволяют повторять генерацию последовательности любое число раз, что невозможно для физических датчиков случайных чисел и что так важно для отладки специфических программ. В целом достоинства методов получения псевдослучайных чисел заключаются в следующем: 1) на получение каждого числа затрачивается всего несколько простых операций, в результате чего скорость генерирования случайных чисел имеет тот же порядок, что и скорость работы ЭВМ. 2) программы получения псевдослучайных чисел чрезвычайно компактны в силу простоты рекуррентных соотношений. 3) любое псевдослучайное число может быть легко воспроизведено. 4) последовательность псевдослучайных чисел достаточно один раз аттестовать, а затем постоянно использовать в сходных задачах без опасения изменения характеристик. Л Е К Ц И Я 5.4 Метод статистических испытаний (продолжение) 5.4.1. Моделирование независимых случайных событий Возможность генерации псевдослучайных чисел, равномерно распределенных на интервале [0,1], открывает широкие возможности для статистического моделирования вообще во всех его приложениях. Наиболее важным в задачах статистических испытаний представляется моделирование независимых случайных событий. Здесь существо задачи состоит в том, что необходимо воспроизвести случайное событие А, наступающее с вероятностью p. Если для этого воспользоваться квазиравномерной последовательностью, то интересующая вероятность в общем виде может рассматриваться как результат интегрирования соответствующей плотности распределения вероятностей где z - некоторый пока неопределенный предел; fрр(x)- плотность вероятностей равномерно распределенных чисел. Но для равномерного распределения на интервале [a,b] имеем Для чисел равномерных на интервале [0,1] будем иметь f рр(x)= 1 и соответственно Отсюда очевидно z = p. Тогда понятно, что реализация события А с вероятностью p осуществляется тогда, когда равномерно распределенные числа на интервале [0,1] попадают в его часть [0,p]. Следовательно, процедура моделирования появления случайного события А должна состоять в генерации случайных чисел R 4i 0 и сравнении их с величиной p : Ri Выполнение неравенства соответствует наступлению события А. Рассмотренные соображения распространяются на моделирование полной группы событий . A1,A2,…,Am , наступающих с вероятностями p1,p2 ,…,pm, для которых естественно определено: p1 + p2 +…+ pm = 1. Здесь, используя ту же квазиравномерную последовательность, можем записать условия наступления любого события As из представленной группы: Тогда действительно: что и требовалось доказать. Процедура моделирования появления событий As (s=1,m) состоит в рассмотренном случае в генерации последовательности Ri и проверки попадания ее в интервалы Исходом испытания при этом будет появление того события As, номеру которого соответствует выполненное неравенство, а значит интервал. 5.4.2. Способы получения случайных чисел с заданным законом распределением Основным соотношением, связывающим случайные числа Si, имеющие заданный закон распределения f(x), и числа Ri, равномерно распределенные на интервале [0,1], является: Доказательство справедливости этого соотношения следует из того факта, что где F(() - интегральная функция распределения вероятностей, являющаяся однозначной функцией своего аргумента. При этом F( () изменяется от 0 до 1 при изменении ( от - ( до + (. Таким образом, для аргумента, лежащего в интервале - ( < ( < + (, функция 0 < F(() < 1, что соответствует числам последовательности, равномерно распределенным на интервале [0,1]. Возвращаясь к исходному выражению заметим, что для получения числа, принадлежащего совокупности {Si}, имеющей плотность распределения f(x), необходимо приведенное уравнение разрешить относительно Si . Пусть, например, требуется получить случайные числа с экспоненциальным законом распределения В силу приведенного соотношения преобразования имеем Интегрируя, получим Отсюда Понятно, что генерация равномерной последовательности значений в интервале [0,1] и подстановка их в полученное выражение обеспечивает генерацию случайной последовательности с экспоненциальным законом распределения вероятностей. При попытке преобразования равномерного распределения в заданное может оказаться, что разрешить уравнение относительно Si, как это проделано в примере, весьма трудно. Это случается, например, когда интеграл от f(x) не выражается через элементарные функции или когда плотность f(x) задана только графически. В такой ситуации для преобразования используется метод Неймана. Условия для его реализации: случайная величина x может быть определена на интервале [a,b]; плотность распределения вероятностей f(x) на интервале [a,b] ограничена f(x) Разыгрывание (генерация) значений x, распределенных с плотностью вероятностей f(x), осуществляется следующим образом: 1)Генерируем два случайных значения R1 и R2 величины равномерно распределенной на интервале [0,1] и получаем случайную точку на графике f(x) с координатами x’ = a + R1*(b - a) y’ = R2* Mo y Mo y’ Г a x’ b x Рис.5.4.1. 2)Если полученная точка лежит под кривой y = f(x), то полагаем, что первое значение случайной величины, соответствующей плотности распределения вероятностей f(x) равно x1 = a + R1*(b - a) = x’ Если же полученная точка лежит над кривой y =f(x), то пара случайных чисел R1 и R2 отбрасывается, выбирается новая R3 и R4 и операции пп.1,2 повторяются. Случайные числа xi, полученные таким образом, имеют плотность распределения вероятностей f(x). Получение случайных величин, плотность вероятностей которых - нормальный закон, имеет свои особенности. Основное уравнение преобразования в этом случае имеет следующий вид: В явном виде оно неразрешимо. Поэтому приходится использовать другой путь. Так согласно центральной предельной теореме теории вероятностей известно, что нормальный закон распределения возникает во всех ситуациях, когда случайная величина может быть представлена в виде суммы достаточно большого числа независимых (или слабо зависимых) элементарных слагаемых, каждое из которых в отдельности мало влияет на сумму. Это дает возможность приближенно моделировать нормальную плотность распределения вероятностей суммированием чисел, равномерно распределенных на интервале [0,1]: ( = (1 + (2 + .....+ (( Но для равномерной плотности распределения Значит Тогда, если i-ое значение нормальной случайной величины ( соответствует i-му эксперименту суммирования n равномерно распределенных чисел, то (i = (i1 + (i2 + .....+ (i( Значит, получение нормально распределенной последовательности {Si} с математическим ожиданием mз и СКО - (з осуществимо путем нормирования и перемасштабирования последовательности {(i}, то есть, приведения ее к заданным числовым характеристикам: Л Е К Ц И Я 5.5 Модель системы распознавания образов Теперь после изложения общих представлений о моделировании вообще можно перейти к построению моделей конкретных систем - систем распознавания образов. Поэтому начнем с того, что определим в первом приближении цель моделирования систем распознавания. Цель компьютерного моделирования систем распознавания - их исследовательские испытания для оценки эффективности распознавания в приемлемые сроки и во всем факторном пространстве представления объектов (явлений, процессов) и возможностей измерителей их характеристик. Можно было бы предположить, что такое определение касается только сложных СР, в состав которых входят многочисленные и разнородные средства измерений или на информационной основе которых строятся сами системы распознавания. Для таких систем не вызывает сомнения необходимость применения опытно-теоретического метода испытаний. Поэтому для них и должна идти речь о сроках и факторном пространстве применения СР. То есть, к компьютерному моделированию прибегают чаще всего постольку, поскольку не могут в приемлемое время провести натурные испытания СР во всем факторном пространстве поведения объектов (явлений, процессов) и измерителей их характеристик. И далее, казалось бы, что системы распознавания, для которых натурные испытания достаточно дешевы, а способы моделирования входных воздействий достаточно сложны и неясны, не следует вообще и моделировать. Кажется, что все можно получить в эксперименте. Если задаться целью, то можно найти настолько простые системы. Однако в большинстве случаев кажущаяся простота и дешевизна натурных экспериментов (испытаний) при неопределенности методов построения моделей входных воздействий скрывает от испытателя характеристики факторного пространства состояния и поведения объектов распознавания. При этом не удается определить фактическую эффективность, а оцененное значение ее только успокаивает (“ведь оценка получена!”), так как, к сожалению, характеризует только какую-то неопределенную часть факторного пространства, о которой могут быть лишь качественные суждения, а чаще всего и ошибочные. Поэтому независимо ни от чего попытка разработки изоморфной модели уже ведет к получению дополнительной информации для создания более эффективных систем или для четкого определения области применения созданной системы распознавания. Отказ от этого подхода приводит к тому, что легко реализуемые экспериментальные применения системы часто не позволяют объяснить причины неожиданно появляющихся отрицательных результатов. И только более полный анализ поведения объектов (явлений, процессов) распознавания, измерителей их характеристик и сопутствующих искажений (что входит в задачи создания соответствующих моделей) выводит из тупиковой ситуации, если, конечно, она расценена как тупиковая. Решение задач построения компьютерных моделей систем распознавания образов основывается на -понимании принципов классификации и структуры систем распознавания; -способов описания классов на языке словаря признаков; -подходов к формализации показателей эффективности распознавания. Начиная с декомпозиции, как одного из важнейших принципов построения моделей, можно заметить, что блочный состав моделей систем распознавания грубо уже определяют их схемы, рассмотренные при изучении принципов классификации. Поэтому модель СР первого приближения должна включать следующие основные элементы: -распознаваемый объект (явление, процесс); -технические средства (средства измерений); -многоуровневая (в общем случае) система обработки измерений; -алгоритм классификации. Ну, а так как моделирование систем распознавания, как это было сформулировано выше, преследует целью проведение испытаний и получение оценки выполнения ими задач - эффективности -, то последним венчающим модель элементом в перечисленный состав должен быть включен блок оценки этого показателя (эффективности). Рассмотрим более подробно все перечисленные элементы модели, стремясь к их детализации и определению принципов компьютерной реализации во взаимодействии друг с другом. 5.5.1. Моделирование распознаваемого объекта Сложность модели распознаваемого объекта (явления, процесса) определяется полностью степенью физико-химической сложности его самого, условий его наблюдения и степенью доступности необходимых измерений. Исходя из определения назначения системы распознавания ,- получение информации, необходимой для принятия решения о принадлежности неизвестного объекта (явления, процесса) к тому или иному классу ,- ничего другого не остается, как получить по возможности всю информацию, имеющую отношение к его распознаванию. Незнание или плохое знание описания объекта во всем диапазоне интересующих сторон, свойств, характеристик, факторов поведения не дает оснований надеяться на эффективность получаемых решений. Заметим, что соответствующая задача (получение всей информации) не противоречит самой первой задаче, с которой начинается создание СР, - определение полного перечня признаков распознавания. Говоря слова “модель объекта” (а равно “модель явления”, “модель процесса”) условимся, что при этом будем иметь в виду “модель объектов распознавания”, которые могут относиться к различным классам. Но так как в системе в каждом акте ее применения всегда имеют дело с одним неизвестным объектом, подлежащим распознаванию, а также имея в виду, что принципы моделирования всех объектов данной СР одинаковы (различны лишь характеристики), чаще всего используется термин “модель объекта распознавания”. Исходя из этого определим модель объекта как цифровой имитатор совокупности его свойств, характеристик и состояний. Заметим, что, на первый взгляд, число моделируемых (имитируемых) свойств, характеристик и состояний объекта равно размерности словаря признаков распознавания. Так действительно, если в СР используется один простой признак распознавания, то и моделью соответствующего объекта должно имитироваться поведение этой одной характеристики, одного свойства, одного состояния объекта. Точно также, если СР использует несколько простых признаков, то имитатор объекта должен обеспечивать получение такого же количества характеристик (свойств, состояний) каждого моделируемого объекта. Однако если признак распознавания один, но комбинированный, то цифровой имитатор соответствующего объекта должен выдавать системе столько и таких его характеристик (свойств, состояний), сколько и каких используется для расчета этого комбинированного признака во многоуровневой системе. То есть, размерность вектора имитируемых свойств может быть больше или равна размерности вектора признаков распознавания. Примеры. 1)Пусть в СР в качестве признака распознавания используется один - масса объекта. Значит моделью каждого из объектов, подлежащих распознаванию, будет в простейшем случае запись в банке данных каждого из них всего одного соответствующего числа в принятой размерности (тонна, килограмм, грамм и т.п.). 2)Пусть в качестве признаков распознавания в СР используются геометрические размеры объекта. Тогда модель каждого объекта, подлежащего распознаванию, будет представлять в простейшем случае три числа в соответствующем банке данных - длина, ширина, высота (м, дм, см, мм). 3)Пусть в СР метеоосадков в качестве признака дождей (а дожди бывают разными хотя бы по интенсивности) используется количество воды, попадающей на определенную поверхность земли. Тогда моделью любого класса дождей может быть всего одно число - количество мм осадков в час (месяц, год). 4)Пусть в СР распознаются звуки по высоте их тона. Тогда моделью каждого звука будет число, характеризующее частоту основного тона его и имеющее размерность - Гц. 5)Пусть в СР распознаются звуки по ряду признаков: -высота основного тона; -наличие низкочастотной модуляции основного тона; -изменение интенсивности. Тогда модель такого в данном случае сложного явления должна содержать по каждому классу, подлежащему распознаванию, по крайней мере, такие параметры как частота основного тона; -частота модуляции; -изменение амплитуды основного тона во времени (вид модуляции). Чем сложнее свойства объекта, отражаемые в составе вектора признаков распознавания, тем сложнее модель этого объекта. Так, если для распознавания требуется знание геометрических характеристик объекта более полно, чем для определения длины, ширины и высоты, то такой объект должен уже представляться чертежами его в трех проекциях. Соответствующая модель - внешние контуры указанных проекций, представляемые -либо в виде набора дискретных точек координат; -либо в виде набора параметров сплайнов, аппроксимирующих указанные контуры; -либо в виде радиально-круговых разверток указанных контуров, то есть , величин радиус-векторов, имеющих начало в некотором центре чертежа проекции и конец на границе контура. Так или иначе мы имеем и здесь и в рассмотренных простейших случаях наборы числовых характеристик распознаваемых объектов, которые для каждого из объектов и представляются как его модель. Утверждая, что чем больше размерность вектора признаков, тем сложнее модель объекта, мы как бы все и усложняем сами вполне сознательно. Действительно формирование словаря признаков, а значит размерности соответствующего вектора, - эвристическая операция. Причем эта задача обычно нацелена на то, чтобы как можно всестороннее охарактеризовать выбранным словарем объект распознавания. Ведь от количества и качества признаков распознавания зависит эффективность классификации. Поэтому получающееся отсюда усложнение модели следует считать естественным состоянием при стремлении к созданию высокоэффективной системы. Для четкости последующего изложения вопросов построения моделей СР назовем банк данных с числовыми характеристиками распознаваемых объектов, соответствующими признакам распознавания, модулем статических характеристик объектов в составе модели объекта. Этим модель не исчерпывается. Следующий важный шаг анализа состава модели объекта (явления, процесса) основывается на представлении о том, как объекты распознавания появляются на входе системы распознавания. Достаточно трудно представить себе системы, на вход которых объекты попадают в строгой очередности. Обычно имеем дело с некоторым вероятностным распределением, то есть, каждый объект или группа достаточно близких объектов, образующих класс, предъявляются СР с конкретной априорной вероятностью. Изоморфно этому одним из составляющих модель СР модулей должен быть элемент, осуществляющий вероятностный выбор предъявляемого объекта в каждом запуске программы модели распознавания. Таким образом каждый модельный эксперимент по распознаванию при наличии такого модуля должен начинаться со статистической задачи выбора объекта определенного класса, подлежащего в этом эксперименте распознаванию. Логико-математические принципы построения модуля выбора объекта - это принципы генерации случайных событий методом статистических испытаний (Монте-Карло). При этом, если каждый класс, для которого определена априорная вероятность, представляется одним объектом, то имеем дело с одним датчиком случайных событий (появлений объектов на входе СР). Если же каждый класс содержит несколько однотипных объектов, то соответственно модуль должен иметь и второй датчик случайных событий, заключающихся в появлении на входе системы одного конкретного объекта из набора их (полной группы событий), входящих в имитируемый класс. В итоге для наиболее общего случая функциональная схема рассмотренной части модели объекта имеет следующее строение (Рис.5.5.1). Рассмотренная часть модели распознаваемого объекта является достаточной, если мы имеем дело с объектами, явлениями или процессами в статике или если располагаем наблюдениями их для измерения характеристик в фиксированные моменты времени. Однако чаще всего реальные СР имеют дело с объектами, характеризующимися некоторой кинематикой. Например, нами рассматривалась такие характеристики звука как высота и громкость, соответствующие признаки которых - частота и амплитуда. В представленном на схеме модуле статических характеристик указанные параметры были бы записаны в виде двух чисел по каждому классу. Но звук одного тона - это периодический во времени процесс, кинематическая характеристика которого , где A - амплитуда; f - частота. Здесь получить интересующие признаки (частоту и амплитуду) по одному мгновенному значению не представляется возможным. Они могут быть определены только путем наблюдений и обработки процесса X(t). А если это так, то в соответствующую модель необходимо ввести модуль, который обеспечивает получение X(t), а значит -счет времени от некоторого момента начала наблюдений или обработки t0; -расчет кинематики X(t) по приведенной выше зависимости, в Модуль выбора класса в соответствии с ап- риорными вероятнос- тями появления P(Wi) № класса Модуль выбора объек- та заданного класса из соответствующего набора № класса ( i ) № объекта М о д у л ь с т а т и ч е с к и х х а р - к о б ъ е к о в Статические Статические Статические характеристики характеристики ... характеристики объектов 1-го объектов 2-го объектов m-го класса класса класса Статические характеристики объекта i-го класса Рис.5.5.1 Функциональная схема чсти модели объекта которую и входят статические характеристики - амплитуда и частота. Здесь счетчик времени - независимая от физического содержания задачи функция , где (t - принятая в модели дискретность представления исходных сигналов; k - число тактов моделирования кинематики. Сам же расчет кинематики определяется объектом и его свойствами. Рассмотрим еще один пример. Пусть объект распознавания описан плоским изображением, контур которого в модуле статических характеристик представлен в виде таблицы расстояний от центра тяжести этого изображения с помощью радиально-круговой развертки: или при выбранной дискретности развертки (( развертки Если реально объект распознавания является вращающимся вокруг центра масс с угловой скоростью (v , а система распознавания должна получать соответствующие признаки путем обработки измеренных радиальных размеров объекта, то модель объекта должна содержать модуль кинематики. При этом определение исходного радиального размера объекта во времени должно осуществляться путем, по крайней мере, линейного интерполирования значений таблицы статических характеристик. С учетом дискретной во времени имитации радиального размера будем иметь: Если вместо статического описания радиально-круговой разверткой тот же плоский объект описан координатами точек контура в прямоугольной системе x,y. Тогда кинематика его при вращении относительно центра масс: где Xio ,Yio - координаты i-ой точки статического описания объекта; Xi(t),Yi(t)- координаты i-ой точки в процессе вращения объекта. Применив указанное преобразование ко всем точкам описания объекта, получим его положение в каждый интересующий момент времени в виде соответствующих положений всех описывающих точек. Точно также, как и в предыдущем случае, при дискретном счете времени от некоторого момента t0 будем иметь: Если же при вращении центр нашей фигуры будет совершать некоторое поступательное движение, то для координат точек ее контура будут: Осуществляя указанные расчеты по статической таблице координат точек контура, будем получать в последовательные моменты времени с дискретностью (t полное представление о движении рассматриваемого объекта. Это и является практическим решением задачи его моделирования при геометрическом описании. Рассмотрение приведенных примеров показывает, что более сложные физические описания статики распознаваемых объектов (явлений, процессов) приведут к более сложным выражениям для определения их кинематики. На этом рассмотрение основ построения модели распознаваемого объекта может быть закончено. Типичная функциональная схема его может быть представлена теперь следующим образом (Рис.5.5.2.). В заключение отметим, что счетчик времени, введенный необходимостью моделирования кинематики объекта, задает темп работы Модуль выбора класса в соответствии с апри- орными вероятностями появления P(Wi) № класса Модуль выбора объекта заданного класса из соответствующего набора № класса (i) № объекта М о д у л ь с т а т и ч е с к и х х - к о б ъ е к о в Статические характеристики объекта i-го класса М о д у л ь к и н е м а т и ч е с к и х х а р - к Субмодуль Субмодуль Субмодуль счетчика вре- счетчика вре- счетчика време- мени функцио- мени функцио- ни функцио- нирования №1 нирования №2 нирования №m Субмодуль рас- Субмодуль рас- Cубмодуль рас- чета кинемати- чета кинемати- чета кинемати- ческих харак- ческих харак- ческих харак- теристик объ- теристик объ- теристик объ- екта 1-го кл. екта 2-го кл. екта (-го кл. Кинематические характеристики объекта Рис. 5.5.2. Функциональная схема модели объекта всей модели системы распознавания. Через время (t на выходе модели объекта появляются новые данные о нем. При этом отсчет времени начинается с момента запуска модели. Сам же счет при синхронизации от ЭВМ обеспечивает работу модели, как говорят, “в реальном времени”. Если же такая синхронизация отсутствует, то очередной такт моделирования объекта начинается после выполнения всех программ модели до конца. В этом случае масштаб времени может быть замедленным относительно реального или ускоренным. Все зависит от объема вычислительных операций всей модели СР. Л Е К Ц И Я 5.6. Модель системы распознавания образов (продолжение) 5.6.1. Моделирование средств определения характеристик объектов распознавания Модель измерителей, обеспечивающих определение характеристик для решения задачи распознавания, является логическим продолжением модели объекта , а значит очередным элементом, в составе общей модели системы. Как следует из предыдущих разделов курса сами измерители являются наиболее сложной и, как следствие, дорогостоящей частью системы. Отсюда вполне понятно, что эта сложность отражается и на рассматриваемой модели. Чаще всего причина сложности модели заключается в том, что в составе систем распознавания используются дистанционные измерители, реализующие достаточно сложные по техническому осуществлению физические принципы с вытекающими отсюда последствиями их математического описания. Кроме того, работа измерителей сопровождается ошибками измерений и отказами, что в свою очередь обусловливает усложнение физико-математического описания и алгоритм. Для того, чтобы выделить принципы построения моделей средств определения характеристик объектов распознавания, прежде всего обратимся к примерам. Начнем с такого простого случай как распознавание звуков по их высоте. Тогда на выходе модели объекта, а значит на входе модели измерителей, мы имеем дело с дискретным процессом Естественно потребовать от измерителя определение частоты как параметра распознавания. Тогда задачами такого измерителя, состоящего очевидно из микрофона и усилителя должны быть: -прием и усиление этого звукового сигнала; -определение периода принятого гармонического сигнала и по нему частоты. Последняя задача может выглядеть как рекуррентное сопоставление каждого принятого дискретного значения с предыдущим и обнаружение номера дискрета, когда достигается максимум сигнала. На некотором временном интервале в результате такой обработки будет получено s таких значений: kmax1 , kmax2 , ....., kmaxs. Тогда интересующая частота тона определится как Но оказывается, что при моделировании этим нельзя ограничиться, так как реальный сигнал искажается шумами измерительного тракта и ошибками измерителя амплитуды . При этом где ((k(() - нормальный случайный процесс с нулевым математическим ожиданием и дисперсией Dx. При этом дисперсия является паспортной характеристикой применяемого измерителя частоты тона звукового сигнала. Случайная аддитивная составляющая сигнала, входящая в это выражение и обусловливает ошибки определения номеров тактов достижения максимумов сигналом, а значит и ошибку определения частоты. Определить величину, вернее параметры, этой ошибки можно, проведя теоретический вывод зависимости пользуясь рассмотренной связью между частотой и максимумами сигнала. Этого же можно достичь и численно, пользуясь методом статистических испытаний (Монте-Карло). Для реализации его придется очевидно генерацию нормальной случайной последовательности ((k(() с Mx = 0 и дисперсией Dx. Добавляя соответствующее значение последовательности к периодической части сигнала и определяя по приведенному алгоритму значения fi, после набора достаточного статистического материала (q реализаций) получим Точно так может быть определена и плотность распределения вероятностей интересующих нас ошибок измерений. Заметим, что с точки зрения построения всей модели измерителя получение параметров ошибок измерения частоты (Mf, (f 2 ) или плотности распределения вероятностей в рамках модели самого измерителя не является необходимым. Рассмотренную операцию можно провести отдельно. Выполняется это, как мы упомянули и показали, либо аналитически, либо с использованием метода Монте-Карло. Причем компьютерные реализации и того и другого подходов представляют собой частные модели ошибок. А результаты их работы дают возможность включить в модель измерителя частоты упрощенный субблок ошибок. Последний будет представлять собой всего лишь датчик случайных чисел , построенный на основе реализации плотности распределения вероятностей ошибок определения частоты или нормальной аппроксимации плотности с числовыми характеристиками, определенными на упомянутых частных моделях . В качестве второго примера, помогающего нам выяснить принципы построения модели распознавания, рассмотрим измеритель радиального размера такого объекта как вращающийся вокруг своего центра тяжести прямоугольник. Для простоты и наглядности будем считать, что точка, из которой ведутся наблюдения этого прямоугольника и измеряется его текущий радиальный размер лежит в начале координат (0,0). При этом радиальным размером объекта считается величина где Ri max(k(t), Ri min(k(t) - расстояния до наиболее удаленной и ближайшей к точке стояния измерителя точек контура прямоугольника (пересечения с радиус-вектором наблюдения). Из простых алгебраических соображений, решая уравнения по определению точек пересечения прямых, отрезки которых образуют стороны прямоугольника, с прямой радиус-вектора из начала координат, для каждого положения прямоугольника будем иметь соответствующие значения. А как изменяются во времени координаты точек контура прямоугольника в модели объекта, а значит и уравнения отрезков сторон его, мы уже рассмотрели. Понятно, что изложенные принципы позволяют записать строго все математические выражения, составляющие существо такого измерителя и легко программно реализовать при построении модели. По аналогии с предыдущим примером можно считать, что паспортной характеристикой измерителя радиального размера должна быть либо плотность распределения вероятностей ошибок определения ri или числовые характеристики нормального закона, имеющего место как правило при измерениях. И так же, как и в предыдущем примере, модель измерителя радиального размера должна включать модуль датчика случайных чисел, генерирующего аддитивную добавку к ri - (ri в соответствии с указанными данными. То есть, измеренное в каждом такте работы программы модели значение радиального размера должно иметь случайную добавку Следует еще раз подчеркнуть, что плотность распределения этой добавки, как случайной величины, должна соответствовать заданной в паспорте для данного измерителя или полученной для него экспериментально в процессе его испытаний. Таким образом, уже два рассмотренных примера однозначно демонстрируют, что составными частями модели измерителей характеристик объектов распознавания должны быть: -модули каждого из средств, отличающихся по физическим принципам, алгоритмы измерений которых имеют свое специфическое математическое описание; -модули датчиков случайных чисел, реализующие случайные добавки к измерениям каждого средства в соответствии с заданными плотностями распределения вероятностей ошибок. В то же время эти примеры, позволившие сформировать первые представления о модели средств измерений, не достаточно подчеркнули факт того, что измерители чаще всего определяют интересующие характеристики объекта на некотором временном интервале наблюдения, то есть по совокупности сигналов, а не в точке. Уже в первом примере измерителя частот гармонических сигналов нельзя было обойтись без накопления информации: частота определялась по результатам наблюдения нескольких периодов сигнала X(t). Точно также во втором примере (вращающийся прямоугольник) скорее всего для решения распознавательных задач мгновенными замерами радиальных размеров ограничиться нельзя. Требования классификации могут заставить нас здесь либо опять-таки измерять период вращения, либо пользоваться в этих целях такими характеристиками как математическое ожидание и среднеквадратический разброс радиального размера объекта: Таким образом, рассмотренные примеры реализации измерителей параметров объекта, а значит и признаков их распознавания, заставляют считать обязательным наличие в составе модели измерителя модуля накопления информации об объекте на некотором интервале времени. Длительность его будет естественно определяться необходимой точностью получаемых оценок, а также зависит от -типа измерителя, его возможностей обнаружения и устойчивого измерения соответствующего параметра; -допустимого временного баланса на решение задачи распознавания. Так радиолокатор начнет измерения радиолокационных характеристик воздушного или космического объекта только после того, как этот объект приблизиться настолько, что соответствующий отраженный сигнал превысит уровень собственных шумов приемного устройства этого радиолокатора. Датчик температуры начнет ее измерения после достижения ею порога чувствительности его. Рассмотрев указанные примеры, мы все-таки не охватили другие важные стороны измерителей, на которые должно быть обращено внимание при построении модели. К ним относиться надежность. Если измеритель вышел из строя или его отказ привел к снижению точности определения параметра распознавания, то ясно, что это приведет к падению эффективности классификации объектов. Следовательно, при моделировании такие ситуации должны быть предусмотрены, а выполнить это достаточно просто, если мы располагаем, например, вероятностью безотказной работы соответствующего средства как паспортной характеристикой. В соответствии с рассмотренным нами методом моделирования случайных событий (метод Монте-Карло) достаточно организовать датчик таких случайных событий как отказ и при выполнении условий выхода из строя запрещать модели измерителя выдавать на выход данные по распознаваемому объекту. Если же отказ приводит только к снижению точности, то в задачи такого модуля должно входить соответствующее изменение характеристик измеренных параметров по сравнению с паспортными. Проведенное рассмотрение типового состава модели измерителя дает основания считать, что реальные объекты, явления, процессы, подлежащие распознаванию, а соответственно и измерители их характеристик, могут обладать широким спектром особенностей. Именно они отражаются на принципах построения модели измерителя. Поэтому реально рассматриваемые модели могут быть и значительно проще и существенно сложнее. Однако изложенные принципы дают основы методологии, базирующейся на тщательном анализе объектов, явлений, процессов и задач измерения их характеристик, а поэтому позволяют надеяться на учет указанной простоты или сложности при реализации и обеспечении изоморфного представления моделей измерителей. 5.6.2. Моделирование каналов связи Немаловажную роль в определении характеристик распознаваемых объектов играют каналы связи. И говоря о том, что главная цель СР - получение информации для решения задач распознавания, указанные каналы можно считать конструктивно присущими таким системам. В качестве каналов связи могут рассматриваться: -каналы передачи и приема энергии измерителями, осуществляющими дистанционное измерение характеристик объектов; -каналы передачи информации измерителя на устройства, осуществляющие ее обработку и использование. Так, если речь идет об измерителях радиолокационного типа, то здесь каналом названного первого типа является земная атмосфера. Она обладает частотно-избирательными свойствами, пропуская почти без потерь одни волны и задерживая другие. Ослабление и поглощение при этом носит экспоненциальный характер и зависит от протяженности трассы распространения сигналов от радиолокатора до наблюдаемого объекта. Поэтому при достаточно коротких трассах этим ослаблением можно пренебречь. В противном случае любые ослабления сигналов ведут как к снижению дальности наблюдения интересующего объекта, так и к ухудшению точности сопутствующих измерений. Ионосфера Земли является анизотропной средой, обладающей различными значениями показателя преломления для различных длин волн. В итоге - изменение поляризации, а значит ослабление принимаемого сигнала. Слоистость атмосферы - причина систематических ошибок измерения угловых координат, дальности и скорости объекта. Местные неоднородности атмосферы, обусловленные вихревыми процессами в воздухе, - причина случайных ошибок измерений. Для ультразвукового локатора, используемого в медицинской аппаратуре УЗИ, слоистость и местные неоднородности тканей человека, частотная зависимость их коэффициента пропускания приводят: -к затуханию сигнала; -к поглощению сигнала; -к рассеянию сигналов; -к интерференции ультразвуковых колебаний. Если первые три вызывают неоднородное ослабление отраженного сигнала, несущего информацию о состоянии внутреннего органа человека, то последнее приводят к появлению спекл - шума, затрудняющего наблюдения распознаваемых объектов и являющегося результатом дифракции отраженных от различных неоднородностей сигналов. Характерно то, что в большинстве случаев исследованию рассматриваемых каналов связи посвящены многочисленные теоретические и экспериментальные работы. При этом достаточно часто указанные воздействия на распространение сигналов измерителей хорошо описываются математически. Для них существуют или теоретические зависимости или в худшем случае эмпирические соотношения, хорошо себя зарекомендовавшие. В каждом конкретном случае канала связи и измерителя эти зависимости и соотношения наполняются своим специфическим содержанием. Главный вывод из этого рассмотрения - возможность учета искажений информационных сигналов в разрабатываемой модели системы распознавания. Второй из упомянутых типов каналов передачи информации измерителей - это в большинстве случаев каналы ее ввода в ЭВМ. Здесь главным является, если не учитывать дальность передачи и соответствующее ослабление сигналов, преобразование измеренного значения , представленного в виде тока или напряжения в цифровую форму. Такое преобразование может осуществляться как стандартными средствами ЭВМ, так и в самом измерителе параметров объектов распознавания. Речь же о важности выяснения существа указанного преобразования идет потому, что дискретизация всегда вносит ошибки в передаваемый параметр и должна учитываться при моделировании. Здесь математическое описание достаточно строго и исходит их того, что плотность распределения вероятностей ошибок дискретизации - равномерная с нулевым математическим ожиданием и дисперсией где ( - цена младшего разряда преобразования. Таким образом, рассмотрение показало, что каналы связи, осуществляющие передачу информации зависят главным образом от типа измерителя. Поэтому их включение в модель измерителя в качестве специальных модулей не должно вызывать сомнений. В итоге типовая функциональная схема модели измерителя может быть представлена следующим образом (Рис.5.6.1). Динамические характеристики объекта Модель 1-го измери- Модель 2-го измери- теля теля Модуль имитации Модуль имитации отказов измери- отказов измери- .... теля теля Модуль имитации Модуль имитации начала и продол- начала и продол- жительности из- жительности из- .... мерений мерений Модуль оценки Модуль оценки .... параметров параметров Модуль имитации Модуль имитации аппаратурных аппаратурных .... ошибок ошибок Модуль имитации Модуль имитации ошибок канала ошибок канала .... связи связи Модуль имитации Модуль имитации преобразования преобразования .... параметра в циф- параметра в циф- ровой код ровой код Рис.5.6.1. Модель средств измерения характеристик Л Е К Ц И Я 5.7. Моделирование алгоритма распознавания 5.7.1. Модель алгоритма распознавания объектов (явлений, процессов) О модели алгоритма распознавания следует вести речь в следующих случаях: 1)При программной реализации соответствующего алгоритма не на рабочей ЭВМ, а на ЭВМ, предназначенной только для предварительной его отработки. 2)При отличиях языка программирования модели от языка программирования рабочего алгоритма. 3)При отработке в процессе моделирования принципов построения алгоритма и, в частности, алфавита классов и словаря признаков, а также решающего правила. 4)При различных сочетаниях ситуаций, представленных в пп. 1-3 настоящего перечня. Если алгоритм системы распознавания реализуется на “своей” ЭВМ в эксплуатационном представлении, то он уже в силу полной изоморфности и аналогичности не представляет собой модель, а является реальной составной частью системы или ее модели (если идет речь о модели системы). В этом случае функциональная схема алгоритма ничем не отличается от схем, приведенных при изучении вопросов их классификации. Реализация алгоритма распознавания на “своей” ЭВМ совместно с моделью объекта распознавания и средств измерения характеристик представляет собой комбинированную модель СР (реальный программно реализованный алгоритм СР и модели входных воздействий), предназначаемую для оценок: -правильности функционирования алгоритма СР; -эффективности системы распознавания, имеющей выбранную структуру и реализацию. Первая из рассмотренных ситуаций применения моделирования систем распознавания может иметь достаточно широкий спектр задач в процессе создания алгоритма и его отработки, если отсутствуют экономически допустимая возможность его реализации на рабочей ЭВМ или ЭВМ подобного типа. Точно также существуют условия для возникновения второй ситуации. Например, желание приспособить готовую программно реализованную СР для другой системы на ЭВМ, где в соответствии с имеющимися требованиями программирование ведется на другом языке или на автокоде, заставляет рассматривать существующую реализацию как модель. Третья ситуация применения моделей систем распознавания представляется наиболее соответствующей конструирования систем распознавания. В том случае, когда целью моделирования алгоритма является выбор признаков распознавания и алфавита классов, состав модели оказывается наиболее полным по сравнению с другими и поэтому представляющим наибольший интерес. Главное что отличает такую модель - это наличие модуля описания классов на языке признаков. Забегая вперед, можно заметить, что подобный модуль может быть и принадлежностью рабочего алгоритма СР. Наиболее это очевидно для обучающихся систем распознавания. Алгоритм функционирования модуля описания классов на языке признаков в максимальной степени интересен для вероятностных систем распознавания. Другие системы имеют более простую и очевидную реализацию. На начальной стадии модельной отработки вероятностной СР имеем дело с m классами и N признаками распознавания .В дальнейшем их число может быть изменено. Для этого и проводится моделирование. Тогда, как известно, описание каждого из классов представляется так: _ Класс 1 : f(X/W1) и P(W1) _ Класс 2 : f(X/W2) и P(W2) _ Класс 3 : f(X/W3) и P(W3) .............................. _ Класс m : f(X/Wm) и P(Wm) При независимости всех N признаков обычно имеем: _ _ _ _ f(X/W1) = f(X1/W1)*f(X2/W1)*....*f(XN/W1) _ _ _ _ f(X/W2) = f(X1/W2)*f(X2/W2)*....*f(XN/W2) ....................................... _ _ _ _ f(X/Wm) = f(X1/Wm)*f(X2/Wm)*....*f(XN/Wm) Как видим, исходными данными для описания классов N признаками являются в этом случае частные описания каждого из классов по каждому признаку f(Xj/Wi), где j = 1,N Отсюда понятно, что если j-ый признак распознавания имитируется в модели объекта ( а у нас такая имитации будет предусмотрена), то при достаточном количестве запусков модели (числе испытаний) получим в каждом заранее известном классе ряд измерений {Xjk} k = 1, Nисп Отсюда статистической обработкой может быть получена сначала гистограмма плотности распределения вероятностей f(Xj/Wi) Затем аппроксимация этой плотности теоретическим непрерывным распределением (например нормальным) дает требуемое частное описание i-го класса по данному j-му признаку. Точно также получаются частные описания всех классов по каждому из признаков. Они и обеспечивают при указанной независимости признаков начальное описание всех классов. Таким образом, отсюда понятно, что в составе модуля описания классов модели СР должен находиться субмодуль восстановления плотностей распределения вероятностей признаков в каждом из назначенных классов, реализующий рассмотренный алгоритм. Обратим теперь внимание на то, что число классов и число признаков в соответствии с имеющимися представлениями о создании СР в исходном состоянии должно быть максимально возможным. Число классов - так как всегда есть стремление к максимальной детализации решений. Число признаков - так как их максимуму соответствует максимум вероятности правильной классификации. В соответствии с этим модель СР может быть использована для оценки результативности увеличения числа признаков, введения новых. Здесь без дополнения ее путем доработок не обойтись. Ну, а все последующие шаги оптимизации СР, обеспечивающей максимум вероятности правильной классификации, связываются, во-первых, с выбором такого числа признаков, которое удовлетворяло бы имеющимся ограничениям на создание средств измерений и обработки информации. Таким образом, здесь уже имеем дело с противоположной тенденцией - ограничением числа признаков (исключением менее эффективных), но при стремлении сохранить достигнутую эффективность на полном их наборе. Следовательно, во-вторых, в задачи оптимизации должны входить действия по компенсация потерь от уменьшения числа признаков, которые сопровождаются, как мы уже доказали, только уменьшением числа классов в исходном алфавите. В результате сокращения числа признаков сокращенное описание будет иметь вид: где k - число исключенных признаков распознавания из i-го класса i = 1,(m-l) l - число исключенных классов. Причем здесь предполагается, что после отбора в состав вектора признаков тех, которые удовлетворяют предъявленным ограничениям, производится повторное описание классов . Когда же есть необходимость уменьшить число классов, то исключаемые из алфавита классы вынужденно объединяются с теми оставшимися в его составе, для которых такое объединение не принесет увеличения числа ошибочных решений в системе. Тогда при объединении, например, двух классов (p-го и q-го) и тот и другой исчезают из алфавита и появляется один новый (m+1)-ый с описанием: Естественно, что тогда (после исключения) последней алгоритмической функцией в модуле описания классов должна быть функция их перенумерации в новом составе. Таким образом, последовательность алгоритмических действий модуля описания классов включает: 1)Расчет одномерных плотностей распределения вероятностей каждого из признаков по классам по репрезентативной выборке реализаций измеренных значений (при моделировании объектов и измерителей). 2)Исключение из описаний одномерных плотностей распределения при сокращении размерности вектора признаков. 3)Перекомпоновка плотностей описания классов и априорных вероятностей при сокращении числа классов. 4)Перенумерации классов после объединения отдельных. Учитывая тот факт, что при имеющихся ограничениях на создание средств измерений и (или) средств обработки приходится варьировать наборами признаков, рассмотренный модуль описания классов должен повторять функции 2-го пункта при каждом новом наборе. Наличие рассмотренного модуля в составе модели СР предъявляет определенные требования к его окружению. Во-первых, для каждого нового описания классов необходимо в качестве входной информации модуля иметь используемый в данной серии испытаний вектор отбора признаков. При решении задачи объединения классов в качестве входной информации модуля необходимо иметь решение в виде номеров классов, назначенных к объединению. В соответствии с этим модуль обеспечивает: -повторное описание классов при каждом новом векторе отбора; -описание объединенных классов после испытаний системы распознавания для одного состава алфавита (перекомпоновка векторов-признаков при их независимости). Если первая из приведенных задач решается автоматически исключением признаков, то вторая не может быть решена без оценки эффективности СР в данной серии испытаний. То есть, решается после проведения испытаний с данным вариантом алфавита во всем диапазоне допустимых векторов отбора признаков распознавания. 5.7.2. Модуль оценки эффективности системы распознавания Оценка эффективности СР, как это следует из самого понятия “эффективность”, представляется необходимым элементом модели СР в целом, позволяющим ответить на вопрос, каково качество или созданной системы или системы после ее очередных доработок (изменений алфавита классов и словаря признаков распознавания), осуществляемых в процессе оптимизации. В том случае, когда решение системы зависит от многих факторов, имеющих случайный характер, показателями, характеризующими оптимальность, являются вероятности правильных и ошибочных решений. Отсюда целесообразным для конструкции модели оценки эффективности должен быть субмодуль оценки вероятностей решений системы. К основным данным для формализации такого субмодуля относятся исходы модельных испытаний. Они представляют собой решения о принадлежности при известной принадлежности классифицируемого объекта в каждом испытании. Поэтому работа алгоритма субмодуля в рассматриваемой части заключается в фиксации решений и истиной принадлежности объекта в некоторой матрице решений: где nij/Vk - число отнесений объекта j-го класса (известного при организации моделирования) к классу i. Число таких матриц после испытаний СР для каждого вектора отбора Vk равно числу таких векторов, удовлетворяющих ограничениям средств на создание или использование систем измерений признаков распознавания. Если же имеем дело с оценкой конкретной структуры системы распознавания, то естественно будем иметь всего одну матрицу для заданного конкретного набора признаков распознавания. В любом случае эти матрицы легко преобразуются в матрицы вероятностей соответствующих решений (точнее, частот, сходящихся к вероятности с заданной точностью при специально выбранном количестве модельных испытаний).Тогда для алфавита классов Ar имеем: Эта простота конечной оценки показателей функционирования системы как раз и является характерной особенностью метода статистических испытаний (метода Монте-Карло). Отсюда может быть получена вероятность правильных системных решений в целом (то есть, отнесений ко всем классам алфавита): На этом при оценке эффективности СР с конкретной детерминированной структурой моделирование завершается и рассмотренным субмодулем ограничивается структура модуля оценки эффективности. Если же существует необходимость оптимизации, то возникает необходимость дополнения модели оценки эффективности субмодулем выбора оптимального набора признаков распознавания. . Его алгоритм очевиден: _ То есть, g-ый вектор отбора (Vg) обеспечивает максимальную вероятность правильных системных решений в алфавите Ar. Теперь матрица вероятностей соответсвует любым системным решениям для найденного оптимального набора признаков распознавания. В результате появляется возможность определить в данном алфавите класс (, объекты которого классифицируются в максимальной степени ошибочно. Соответствующую вероятность находим как максимальную вероятность ошибки: откуда номер упомянутого класса: Если теперь задаться порогом вероятности P( ()зад, то появляется возможность при P( (/(r) > P( ()зад принять решение о необходимости исключения из алфавита Ar класса с номером ( , эффективность отнесения к которому ниже требуемой (заданной). Отсюда все операции, связанные с определение такого класса (номера его через вероятность ошибочного отнесения), могут быть объединены в отдельном субмодулем- поиска класса, снижающего эффективность распознавания. Наконец, та же матрица позволяет выделить такой класс, отнесение к которому объектов найденного низкоэффективного класса наиболее целесообразно для повышения эффективности системных решений. Номер такого класса соответствует максимальной вероятности отнесения к нему указанного низкоэффективного класса. То есть: Эти операции можно поручить отдельному субмодулю, выходом которого должны быть номера классов ( и ( , которые следует объединить в алфавите Ar, чтобы повысить эффективность СР в целом. Он может быть назван субмодулем определения номеров объединяемых классов. В рассматриваемом составе (Рис.5.7.1.) модуль оценки эффективности удовлетворяет потребностям как оценки качества СР, так и потребностям управления оптимизацией СР в условиях ограничений средств на создание измерителей. Сами функции управления моделью СР необходимо объединить в отдельном модуле. № распознанного класса Субмодуль оценки № имитируемого результата распо- класса знавания (от модели объекта) Ar i,j Субмодуль расчета _ от модуля матрицы решений Vk управления (от модуля управления) || nij/V k || Субмодуль расчета и хранения матриц на модуль вероятностей ре- управления шений || Pij (Ar /Vk ) || Субмодуль опреде- ления оптимально- на модуль го набора призна- управления ков в алфавите Ar (Ar Субмодуль поиска неэффективно рас- на модуль познаваемого управления класса и модуль P( (/Ar) и (/Ar описания классов Субмодуль решения Субмодуль опреде- об исключении (-го ления расширяемо- класса го класса (( ) Рис.5.7.1. Модуль оценки эффективности 5.7.3. Модуль управления моделью системы распознавания Из рассмотрения общих принципов моделирования сложных систем, а также состава и особенностей построения модели СР следует, что в общих чертах динамика моделирования системы распознавания представляет собой -многократно повторяющийся ( с каждым пуском программы модели) процесс выбора распознаваемого объекта; -многократно повторяющийся процесс имитации работы измерителей параметров по каждому моделируемому объекту и штатной обработки полученной информации с целью получения признаков распознавания; -многократно повторяющийся ( для каждого выбранного объекта распознавания) процесс штатного принятия решения о принадлежности предъявленного объекта; -статистическую обработку принятых решений в каждом из пусков программы модели как источник определения показателя качества СР в целом. Первая из приведенных функций, задающая весь процесс функционирования программы модели в каждом пуске, реализуется в виде: -первоначального пуска программы модели испытателем с исходными требованиями, введенными им предварительно; -автоматического повторения заданного числа циклов пуска программы для реализации повторений процесса распознавания в соответствии с методологией статистических испытаний; -своевременной выдачи необходимых исходных данных для ввода в отдельные субмодули модели для организации их работы по заранее введенным и хранимым данным или по результатам выполненной работы другими субмодулями. Все остальные функции, характеризующие динамику модели СР в целом, должны выполняться автоматически в рассмотренной последовательности. То есть, первая функция объединяет фактически все задачи управления моделью. Выполнение ее логично возложить на отдельный модуль - модуль управления. . Общее рассмотрение реализации модуля управления позволяет обратить внимание на задачу связи испытателя с моделью системы. При этом рассматривая алгоритмическое содержание уже описанных модулей, входящих в состав модели, можно заключить, что модуль управления должен иметь интерфейс, позволяющий вводить для организации моделирования такие исходные данные, как -количество статистичесих испытаний (пусков) на модели системы; -исходный априорный алфавит классов; -априорные вероятности предполагаемых классов; -допустимое значение вероятности ошибочной классификации. Кроме того, тот же интерфейс должен обеспечить представление испытателю по его требованию индикации: -реализаций измеренных характеристик (признаков) моделируемых объектов; -поэтапных значений (для каждого алфавита классов и набора признаков распознавания) показателя эффективности системы; -состава алфавита классов и параметров их описания; -текущего состояния отбора признаков в рабочий словарь. Теперь можно детализовать отдельные детали управления. Так модуль управления должен обеспечивать -автоматическое повторение решений полного объема задач испытаний на модели со сменой вектора отбора признаков распознавания (если заданы ограничения на средства создания и использования средств измерений); -автоматический переход к анализу эффективности всех вариантов рабочего словаря после завершения испытаний со всеми возможными векторами отбора; -автоматический переход к выполнению корректировки алфавита классов после выполненного анализа ошибок классификациии; -автоматическое повторение циклов полного объема испытаний после корректировки алфавита классов. А отсюда логически вытекает, что задание (генерация) векторов отбора, удовлетворяющих заданным ограничениям, вполне соответствует функциям управления. То есть, эта задача должна решаться модулем управления, который обязан иметь соответствующие исходные данные по ограничениям выделенных средств и затратам на создание или применение отдельных измерителей. Перечисленные функции должны быть алгоритмически дополнены функцией обучения системы на информации об объектах, имитируемой соответствующим модулем модели. Работа в указанном режиме может осуществляться как при первом пуске модели для первоначального описания классов, так и при любой смене алфавита классов и словаря признаков. Обобщенная структурная схема модуля управления приведена на рис 5.7.2, а общая структурная схема модели СР без детализации рассмотренных модулей и субмодулей - на рис.5.7.3. От модуля обработки Субмодуль вывода Субмодуль ввода P(Wi) характеристик исходных данных Ar измерений объекта распозна- и управления ото- P(()з вания бражением От модуля Субмодуль отобра- Субмодуль генера- _ жения процесса ции допустимых Vk оценки эф- моделирования векторов отбора фективно- сти и др. Субмодуль управ- ления описанием На классов модуль описания классов Субмодуль управ- ления циклом ис- пытаний системы На модуль имитации объектов Субмодуль управ- ления оценкой эф- фективности На модуль оценки эффективности Рис. 5.7.2. Обобщенная структурная схема модуля управления моделью информация, управление P(()з Модуль управления моделью Ar Ar Vk Модуль имитации объектов распоз- навания Модуль измерите- лей характеристик объектов Модуль отбора признаков распоз- навания Ar Модуль описания Модуль принятия классов решений о при- надлежности ( ( Модуль оценки эффективности Рис.5.7.3. Общая структурная схема модели СР Л Е К Ц И Я 5.8 Опытно-теоретический метод в задачах создания систем распознавания 5.8.1. Использование принципов опытно- теоретического метода при моделировании СР Назначение опытно-теоретического метода - испытания сложных систем во всем факторном пространстве их функционирования. Системы распознавания образов являются обычно составной частью сложных технических систем. Поэтому испытания самих сложных систем обеспечивают, как правило, и испытания СР. Главное, что объединяет информационно системы распознавания и сложные системы, в состав которых они входят, это - объекты распознавания и средства измерений характеристик этих объектов. Причина такого пересечения систем очевидна и состоит в том, что сложные системы обеспечивают принятие решений по определенным объектам (процессам, явлениям), а распознавание этих же объектов (явлений, процессов) всегда направлено на получение дополнительной информации для принятия указанных решений. Отсюда казалось, что занимаясь системами распознавания, можно было бы не интересоваться опытно-теоретическим методом, отдать его на откуп специалистам-испытателям сложных систем. При этом, если не учитывать неотъемлемое использование в составе СР средств измерений ( а они нужны сложной системе и без задач распознавания), то сама СР не выглядит как сложная. Однако часто СР разрабатываются либо после создания систем принятия решений, являющихся сложными, либо самостоятельно в расчете на перспективное использование в какой-либо предметной области. То есть, в этих случаях разработчики СР встречаются с тем, что или не располагают изоморфными моделями объектов распознавания и средств измерений (они не были нужны разработчикам сложных систем) или просто лишены этих данных, так как предметная область применения СР еще не определилась. Поэтому и в первом и во втором (после определения предметной области) случаях становится важным для всесторонних оценок характеристик этих систем взгляд с позиций опытно-теоретического метода на упомянутое пересечение систем - объекты распознавания и средства измерения их параметров. Это обращение к опытно- теоретическому методу заставляет разработчиков СР самостоятельно идти по пути создания изоморфных моделей объектов и измерителей. В результате объединение модели СР с упомянутыми моделями уже представляется как сложная система со всеми вытекающими последствиями по ее испытаниям. Дополнительно к изложенному можно заметить, что в соответствии с приведенными в нашем курсе определением главной задачей СР является получение информации об объекте распознавания. А это как раз и оправдывает объединение программно реализованного алгоритма распознавания с моделями объекта и измерителей при испытаниях системы распознавания. Само моделирование объектов (явлений, процессов) распознавания почти всегда представляет собой достаточно объемную и сложную задачу. Примером может служить хотя бы разработка модели системы распознавания речевых сообщений. Объект распознавания здесь - это в конечном итоге состояния речевого аппарата человека при производстве колебаний звукового диапазона. Сложность этого аппарата, его динамики не позволяет надеяться на легкое создание безупречной модели. При этом опытно-теоретический метод испытаний остается единственным в достижении высокой достоверности результатов отработки соответствующей СР на модели. А без всесторонних испытаний во всем факторном пространстве применения подобных систем, особенно для принятия решений высокой ответственности, не представляется возможным обойтись. Поэтому здесь создание изоморфных реальному речевому аппарату синтезаторов речи - это одновременно и путь создания эффективных СР. Можно найти достаточное число примеров из других областей науки и техники, которые подтвердят, что устраняться от использования принципов опытно-теоретического метода при создании СР не только нецелесообразно, но и ошибочно. Отсюда арсеналом средств разработчика СР при создании моделей объектов и измерителей должны быть следующие принципы опытно-теоретического метода: 1).Построение общей топологии модели СР, включая источники информации, и проведении ее декомпозиции. 2).Распределение задач между моделями и определение состава частных моделей. 3).Выбор и обоснование способов приближения моделей к реальным моделируемым объектам и измерителям их характеристик. 4).Выбор условий проведения и планирование натурных испытаний информационных средств СР. 5).Обоснование объема экспериментов и проведение натурных испытаний информационных средств СР для оценки степени близости моделей и реальных объектов и измерителей. 6).Проведение параметрической и структурной доработок модели информационных средств СР на основе сравнения в одинаковых условиях результатов реальных испытаний и моделирования. 7).Проверка статистической совместимости моделей и соответствующих информационных средств в выбранных точках факторного пространства состояний объектов распознавания и измерителей их характеристик. 8).Проведение испытаний СР на моделях, определение характеристик качества программно реализованных алгоритмов, функционального взаимодействия элементов системы и ее эффективности во всей области факторного пространства. В целом опытно-теоретический метод подход к испытаниям сложных систем и его принципы основываются на целом ряде теоретических положений, решений и выводов, которые могут быть рассмотрены только в отдельном курсе. Наша задача - показать логическую приемлемость этого подхода к моделированию СР и адресовать будущего разработчика к таким материалам, излагающим соответствующие методы, как 1. Н.П.Бусленко. Теория больших систем. М.,”Наука”, 1969. 2. А.С.Шаракшанэ, И.Г.Железнов и др. Сложные системы. М.,”Высшая школа”, 1977. 3. Г.И.Бутко,Ю.П.Порывкин и др. Оценка характеристик систем управления летательными аппаратами. М.,”Машиностроение”, 1984. 5.8.2. Моделирование в задачах создания и оптимизации систем распознавания После того, как рассмотрены основные принципы построения моделей сложных систем и их испытаний с использованием моделирования, не сложно понять, на каком этапе создания СР может и должна появляться соответствующая модель. Если обратиться к задачам создания СР, то первая из них - выбор признаков распознавания заданных объектов (явлений, процессов). То есть, в самом начале разработки СР в распоряжении разработчика находится конкретная, вполне определенная предметная область с ее объектами (явлениями, процессами). Не вызывает сомнений то, что на рассматриваемом этапе уже возможно создание модели объектов (явлений, процессов), подлежащих распознаванию. В то же время соответствующая разработка оказывается в целом ряде случаев достаточно объемной, так как в самом начале работ в априорный словарь признаков включаются все возможные параметры, характеризующие объект (явление, процесс). А в результате последующего моделирования отдельные характеристики могут оказаться невостребованными в связи с тем, что не найдется соответствующего измерителя их или его создание окажется экономически невозможным. Поэтому хотя то всестороннее изучение свойств объекта, которое будет в указанном случае проведено, и полезно для представлений возможного развития СР, разработка модели более целесообразной оказывается после анализа и выбора допустимого набора измерительных средств. Так или иначе построение в выбранном признаковом пространстве модели, изоморфной реальному объекту, представляется достаточно мощным процессом для поиска наиболее эффективных признаков распознавания. Указанный процесс обязывает к глубокому анализу существа распознаваемого объекта. В результате создания модели объекта появляется возможность очередного шага в построении модели СР в целом - возможность создания и подключения модели средств измерений. Далее после решения задачи выбора априорного алфавита классов (а это уже следующая задача создания СР) созданный комплекс из двух моделей (объекта и измерителей) позволяет методом статистических испытаний получить описание этих классов. То есть, статистически разыгрывая начальные условия состояния и движения объекта и измерителей его характеристик, получаем статистические данные (плотности распределения вероятностей) по каждому из признаков при их независимости в назначенных классах или совместные описания в более сложных случаях. Если создается обучающаяся система, то после выбора начальных приближений разделяющих функций классов (а это уже очередной этап создания СР) использование созданных моделей ( объекта и измерителей) обеспечит тем же методом статистических испытаний уточнение параметров указанных разделяющих функций. При этом появляется возможность проверки приемлемости для создаваемой системы различных решающих функций. Для случая “полной” априорной информации (система без обучения) задача выбора правила классификации также легко решается методом статистических испытаний. Здесь реализуется возможность проверки различных статистических критериев. Как для обучающейся системы, так и для системы без обучения этап исследования решающих правил уже предполагает, что в состав модели входит модуль оценки эффективности. Без него предусматриваемое сравнение в приведенных случаях невозможно. Таким образом, на всех этапах (при решении всех задач) создания СР любых типов моделирование оказывается инструментом, избавляющим разработчика от сбора большого объема экспериментальных данных. При этом, конечно, всегда предполагается, что применяемые модели прошли калибровку в рамках опытно-теоретического метода и являются изоморфными реальным аналогам. В итоге рассмотрения роли и места моделирования в задачах создания систем распознавания образов остается вспомнить, что одно из важнейших направлений разработки - оптимизация эвристических выборов априорного словаря признаков и априорного алфавита классов. Однако в том, что моделирование может обеспечить выбор наиболее эффективных рабочего словаря и рабочего алфавита, уже пришлось убедиться при разработке структурной схемы полной модели СР. В заключение необходимо обратить внимание на то, что общая структурная схема модели системы распознавания, рассматриваемая для вероятностного описания классов, остается справедливой для детерминированных и логических систем. Конечно внутренняя структура отдельных модулей должна быть подвергнута корректировке. Так в детерминированном случае ошибки измерений становятся несущественными и соответствующий субмодуль можно было бы исключить из модуля измерителя характеристик объекта распознавания. Точно также упрощается модуль описания классов за счет использования набора детерминированных эталонов. Упрощается и модуль классификации. Но в целом вся структура модели остается приспособленной для испытаний детерминированных систем. Аналогично свои особенности имеет реализация модели логической СР: -результаты обработки информации измерителей после бинарного квантования должны преобразовываться в логические признаки; -случайность результатов измерений за счет сопутствующих ошибок трансформируется в реально имеющую место случайность получения того или иного логического признака; -описание классов выглядит в виде системы булевых функций классов с импликантами в виде произведений логических признаков; -модуль классификации должен приобрести возможность решения булевых уравнений. В то же время модуль оценки эффективности в основной своей части должен мало отличаться от модуля вероятностной системы, так как и в этом случае оценки основываются на методе Монте-Карло. Таким образом, разработанная общая структурная схема модели СР должна играть роль типовой, содержание модулей которой корректируется в зависимости от назначения системы и характеристик признаков распознавания. Л А Б О Р А Т О Р Н Ы Е Р А Б О Т Ы П О К У Р С У "Основы построения систем распознавания образов" Лабораторная работа №1 по курсу “Основы построения систем распознавания образов” Исследование геометрических мер близости распознаваемых объектов и классов I. Цель работы Целью лабораторной работы является практическое освоение методов компьютерной реализации геометрических мер близости, применяемых для принятия решений в детерминированных системах распознавания. II. Задачи лабораторной работы 1. Разработка алгоритма принятия решения в детерминированной системе распознавания на основе использования известных геометрических мер близости. 2. Программная реализация разработанного алгоритма. 3. Ввод заданных описаний 3-х классов на языке 11-и предложенных признаков распознавания (таблицы 1-3 - варианты заданий). 4. Отладка программы. 5. Выполнение контрольных распознаваний неизвестных объектов по векторам их признаков (таблица 4). 6. Сравнение принятых решений об отнесении неизвестных объектов к заданным классам по различным мерам близости. III. Требования к выполнению задач. 1. Число классов распознавания - 5-10. 2. Размерность вектора признаков - до 20. 3. Число эталонов описания классов - 5-10. 4. Язык программирования - Паскаль, Си. 5. Программно должно быть предусмотрено использование для принятия решения всех введенных эталонов описания классов и их усредненных описаний. 6.Лабораторная работа должна быть оформлена в соответствии с установленным порядком. IV. Методические указания 1. В качестве геометрических мер близости при детерминированном описании распознаваемых объектов и классов использовать а) Эвклидово расстояние между объектами, описанными на языке признаков б) Угловое расстояние между векторами признаков распознаваемого объекта и эталона в) Сумму модулей разности координат (признаков) объекта и эталона . 2. Решение о принадлежности объекта, представленного вектором Xw, к одному из классов принимается согласно правилам принятия решений в детерминированных системах. Примечание: Описание классов k эталонами может быть преобразовано к описанию одним эталоном. Это осуществляется осреднением эталонов по признакам. V. Исходные данные для тестирования программы и проведения исследований. 1й класс ТАБЛИЦА 1 ЭТАЛОНЫ № признака 1 2 3 4 5 1 0.95 0.80 0.90 0.70 1.00 2 0.54 0.68 0.47 0.75 0.80 3 0.80 0.40 0.90 0.30 0.50 4 0.65 0.90 0.80 0.60 0.70 5 0.81 0.51 0.91 0.71 1.00 6 0.42 0.56 0.14 0.70 1.00 7 1.00 0.56 0.78 0.67 0.34 8 0.60 0.81 1.00 0.74 0.88 9 0.64 0.51 0.77 0.25 1.00 10 0.50 0.63 1.00 0.24 0.76 11 0.51 1.00 0.25 0.77 0.64 2й класс ТАБЛИЦА 2 ЭТАЛОНЫ № признака 1 2 3 4 5 1 0.21 0.25 0.17 0.23 0.30 2 0.24 0.28 0.20 0.26 0.30 3 0.80 0.70 0.74 0.76 0.78 4 0.40 0.30 0.10 0.20 0.25 5 0.42 0.39 0.50 0.36 0.30 6 0.16 0.15 0.16 0.17 0.16 7 0.35 0.29 0.33 0.31 0.25 8 0.26 0.38 0.50 0.34 0.42 9 0.19 0.17 0.21 0.13 0.25 10 0.40 0.48 0.70 0.24 0.56 11 0.02 0.04 0.01 0.03 0.03 3й класс ТАБЛИЦА 3 ЭТАЛОНЫ № признака 1 2 3 4 5 1 0.21 0.25 0.17 0.23 0.30 2 0.60 0.80 0.40 0.70 1.00 3 1.00 0.80 0.84 0.86 0.88 4 1.00 0.90 0.70 0.80 0.85 5 0.15 0.12 0.21 0.09 0.03 6 0.08 0.06 0.10 0.14 0.09 7 0.25 0.20 0.22 0.21 0.18 8 0.25 0.34 0.44 0.31 0.37 9 0.19 0.17 0.21 0.13 0.25 10 0.49 0.57 0.83 0.33 0.65 11 0.04 0.06 0.03 0.05 0.05 4й класс ТАБЛИЦА 4 ЭТАЛОНЫ № признака 1 2 3 4 5 6 1 0.85 0.75 0.19 0.27 0.19 0.27 2 0.40 0.61 0.22 0.30 0.50 0.90 3 0.60 0.70 0.72 0.80 0.82 1.00 4 0.85 0.75 0.15 0.35 0.75 0.95 5 0.61 0.41 0.33 0.45 0.06 0.18 6 0.28 0.84 0.15 0.17 0.07 0.11 7 0.45 0.89 0.27 0.35 0.19 0.23 8 0.67 0.95 0.30 0.46 0.28 0.40 9 0.38 0.90 0.15 0.23 0.15 0.23 10 0.37 0.89 0.32 0.64 0.41 0.73 11 0.38 0.90 0.02 0.04 0.04 0.06 Л И Т Е Р А Т У Р А (1( Конспект лекций по курсу "Основы построения систем распознавания образов". Лабораторная работа №2 по курсу “Основы построения систем распознавания образов” Исследование вероятностной меры близости распознаваемых объектов и классов I. Цель работы Целью лабораторной работы является практическое освоение методов компьютерной реализации вероятностной меры близости, применяемой для принятия решений в вероятностных системах распознавания. II. Задачи лабораторной работы 1. Разработка алгоритма принятия решения в вероятностной системе распознавания на основе использования известной вероятностной меры близости - среднего риска. 2. Программная реализация разработанного алгоритма. 3. Ввод заданных описаний классов на языке предложенных признаков распознавания. 4. Отладка программы. 5. Выполнение контрольных распознаваний неизвестных объектов по векторам признаков, заданных преподавателем. 6. Проведение исследований влияния на решение о принадлежности - априорных вероятностей классов; - плат, назначаемых за ошибочные решения. III. Требования к выполнению задач. 1. Число классов распознаваемых объектов - 3. 2. Количество признаков распознавания - 1. 3. Язык программирования - Паскаль, Си. 4. Лабораторная работа должна быть оформлена в соответствии с установленным порядком. 5. Исследования выполнить в два этапа: Этап 1 - оценка влияния априорных вероятностей классов на принимаемые решения о принадлежности; Этап 2 - оценка влияния плат за ошибочные решения о принадлежности на эти решения. (V. Исходные данные для исследований 1. Условные априорные плотности распределения вероятностей, используемые для описания классов - нормальные с математическими ожиданиями mi и среднеквадратическими разбросами - (i (Таблица 1). 2. Измеренные значения признаков по распознаваемым объектам (Таблица 1) 3. Априорные вероятности классов и матрица плат за ошибки для первого исследования: P(W1) P(W2) P(W3) 1-й набор 0.1 0.8 0.1 2-й набор 0.2 0.6 0.2 3-й набор 0.3 0.4 0.3 4-й набор 0.4 0.2 0.4 5-й набор 0.4 0.1 0.5 4. Априорные вероятности классов и матрицы плат за ошибки для второго исследования: P(W1)= 0.33, P(W2)= 0.33, P(W3)= 0.33. 5. Варианты заданий Таблица 1 Класс 1 Класс 2 Класс 3 Класс 1 Класс 2 Класс 3 1 17 19 23 3 1.5 4 20 2 27 29 33 2.9 1.6 3.8 30 3 37 39 43 3.2 1.4 4.1 40 4 32 34 38 3 1.5 4 35 5 28 39 34 2.9 1.6 3.8 31 6 47 49 53 3.2 1.4 4.1 50 7 42 44 48 3 1.5 4 45 8 39 41 45 2.9 1.6 3.8 42 9 36 38 42 3.2 1.4 4.1 39 10 46 48 52 3 1.5 4 49 11 22 24 28 2.9 1.6 3.8 25 12 51 53 57 3.2 1.4 4.1 54 13 24 26 30 3 1.5 4 27 14 15 17 21 2.9 1.6 3.8 18 15 25 27 31 3.2 1.4 4.1 28 Л И Т Е Р А Т У Р А (1 ( Конспект лекций по курсу "Основы построения систем распознавания образов". Лабораторная работа № 3-1 по курсу "Основы построения систем распознавания образов" Оценка эффективности вероятностной системы распознавания I. Цель работы Целью лабораторной работы является практическое освоение методов компьютерной реализации алгоритмов оценки эффективности СР. Лабораторная работа выполняется в процессе решения конкретной задачи. II.Задачи лабораторной работы 2.1. Разработать алгоритм решения задачи следующего содержания: в процессе демонтажа приводов некоторых устройств, проводимого в целях их ремонтно-восстановительных работ, автоматически классифицируются и комплектуются муфты вращающихся сочленений по их внутреннему диаметру. Принятый технологический процесс демонтажа обусловливает случайный характер демонтажа муфты каждого типоразмера и передачу ее на классификацию и комплектование. Среднеквадратическая ошибка измерений внутреннего диаметра муфты специальной электромеханической системой составляет 3 мм. Всего в демонтируемых изделиях используется 5 типоразмеров муфт, внутренние диаметры которых и количество приведены в таблице Кол-во муфт Диаметры муфт по вариантам 1 2 3 4 5 6 7 8 9 10 11 12 13 100 3 7 18 35 4 17 8 11 5 20 6 10 19 100 6 10 21 38 7 20 11 14 8 23 9 13 22 100 9 13 24 41 10 23 14 17 11 26 12 16 25 100 12 16 27 44 13 26 17 20 14 29 15 19 28 100 15 19 30 47 16 29 20 23 17 32 18 22 31 2.2.В результате разработки: 2.2.1. Описать классы системы распознавания, учитывая что ошибки измерений в технических устройствах приводят, как правило, к нормальному закону распределения вероятностей оцениваемого параметра. 2.2.2. Рассчитать вероятности ошибок ложной классификации муфт предлагаемой системой . 2.2.3. Определить априорный риск распознавания в системе при равных платах за ошибки.(Границы между i-ым и i+1-ым классами устанавливаются по равенству плотностей распределения вероятностей соседних классов, то есть: mi + mi+1 аi,i+1 = (((( 2 где mi и mi+1 - математические ожидания описаний соседних классов.) 2.3. Выполнить программную реализацию разработанного алгоритма. 2.4. Отладить программу. 2.5. Выполнить расчеты. 2.6. Провести анализ и оформление результатов. (((. Методические указания к выполнению задания. 3.1. Программа расчета и анализа эффективности может быть выполнена на любом языке высокого уровня. 3.2. Зависимости вероятностей ошибок классификации и среднего риска от СКО измерений оформить графически. 3.3. Для использования при решении интеграла Лапласа необходимо разработать программную функцию на основе его разложения в ряд. 3.4.При интегрировании нормальной плотности распределения вероятностей использовать следующее значение интеграла Лапласа Л И Т Е Р А Т У Р А ((( Конспект лекций по курсу "Основы построения систем распознавания образов". Лабораторная работа № 3-2 по курсу "Основы построения систем распознавания образов" Исследование влияния ошибок распознавания на эффективность вероятностной системы I. Цель работы Целью лабораторной работы является практическое освоение методов компьютерной реализации алгоритмов оценки эффективности СР. Настоящая лабораторная работа основывается на выполненной лабораторной работе N 3-1 и является ее продолжением. II. Задачи лабораторной работы 2.1. В качестве алгоритма для выполнения настоящей работы использовать алгоритм, разработанный в лабораторной работе № 3-1. 2.2. Исходные данные для расчетов оставить теми же, что были выбраны по предложенному варианту в лабораторной работе № 3-1. 2.3. Требуется: 2.3.1. Среди ошибок классификации муфт (см. лабораторную работу № 3-1) найти такую, которая имеет максимальную вероятность 2.3.2. Используя созданную в лабораторной работе № 3-1 программу, рассчитать зависимость максимальной по вероятности ошибки классификации P(Wk/Wd) от величины СКО ошибки измерений диаметра при дискретном повышении точности измерителя диаметра ( = 3 мм, 2.5 мм, 2 мм, 1.5 мм, 1 мм и 0.5 мм: P(Wk /Wd)= F1( ( ). 2.3.3. Для тех же значений ошибки измерений (п.2) рассчитать зависимость среднего риска распознавания: _ R = F2( (). 2.3.4. По результатам определения в п 2. зависимости P(Wk /Wd )=F1( () предъявить требование к точности системы измерений внутреннего диаметра муфт (СКО) для выполнения требования технического задания на систему распознавания - не более двух ошибочных классификаций на 500 муфт . 2.4. Выполнить расчеты. 2.5. Провести анализ и оформить результаты. (((. Методические указания к выполнению задания. 3.1. Зависимости вероятностей ошибок классификации и среднего риска от СКО измерений оформить графически. 3.2. При выполнении п. 2.3.4 воспользоваться линейной интерполяцией . Л И Т Е Р А Т У Р А (1( Конспект лекций по курсу "Основы построения систем распознавания образов". Лабораторная работа № 3-3 по курсу "Основы построения систем распознавания образов" Оценка влияния числа классов на эффективность вероятностной системы распознавания I. Цель работы Целью лабораторной работы является практическое освоение методов оценки эффективности СР. Настоящая лабораторная работа выполняется как продолжение лабораторных работ №№ 3-1, 3-2. II.Задачи лабораторной работы 2.1. На основе разработанной программы и результатов расчетов по лабораторным работам №№ 3-1, 3-2 повторить выполнение их требований, предварительно исключив из состава классифицируемых муфт 100 штук следующих диаметров по вариантам: Диаметры исключаемых муфт в мм по вариантам Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 Диаметр 9 13 24 41 10 23 14 17 11 26 12 16 25 2.2. Сравнить зависимость априорного риска от точностей измерения признака распознавания с зависимостью, полученной в первом исследовании (лабораторная работа № 3-2). 2.3. Сравнить зависимость максимальной ошибки распознавания классов от точностей измерения признака распознавания с зависимостью, полученной в первом исследовании, и пояснить результат. Л И Т Е Р А Т У Р А (1( Конспект по курсу "Основы построения систем распознавания образов". В О П Р О С Ы ПРАКТИЧЕСКИХ ЗАНЯТИЙ ПО КУРСУ "Основы построения систем распознавания образов" З А Н Я Т И Е № 1 Особенности задач построения систем распознавания образов 1.Основные определения теории (объект, образ, распознавание, система распознавания). 2.Инвариантность задач построения СР относительно применений и узкая специфичность технических СР. 3.Содержание и особенности I этапа создания СР. Определение полного перечня признаков распознавания. 4.Содержание и особенности II этапа создания СР. Разработка априорного алфавита классов. 5.Содержание и особенности III и IV этапов создания СР. Разработка априорного словаря признаков и описание классов. 6.Содержание и особенности ( этапа создания СР. Разбиение априорного пространства признаков на области, соответствующие алфавиту классов. Выбор алгоритма классификации. 7.Содержание и особенности VI этапа создания СР. Определение рабочего алфавита классов и рабочего словаря признаков. З А Н Я Т И Е № 2 Классификация систем распознавания образов 1.Классификация систем распознавания (простые и сложные). 2.Классификация систем распознавания (системы без обучения, обучающиеся и самообучающиеся). 3.Классификация систем распознавания (общие представления о логических и структурных системах). 4.Классификация систем распознавания (детерминированные и вероятностные системы). З А Н Я Т И Е № 3 Основные особенности детерминированных систем распознавания образов 1.Описание классов на языке детерминированных признаков. 2.Меры близости, используемые для оценки принадлежности образов в детерминированных системах распознавания. 3.Решающее правило для классификации объектов, описанных на языке детерминированных признаков. З А Н Я Т И Е № 4 Основные особенности вероятностных систем распознавания образов 1.Описание классов на языке вероятностных признаков распознавания. 2.Порядок назначения плат за ошибочные решения. 3.Меры близости, используемые для оценки принадлежности образов в вероятностных системах. 4.Определение апостериорных вероятностей классов. 5.Решающее правило для классификации объектов, описанных на языке вероятностных признаков распознавания. Апостериорный риск. З А Н Я Т И Е № 5 Особенности эвристических выборов признаков и классов 1.Априорная оценка эффективности вероятностной системы распознавания. Априорный риск. 2.Определение вероятности ошибки при оценке среднего априорного риска. Особенности определения ошибок при описании классов нормальной плотностью распределения вероятностей. 3.Доказательство влияния числа признаков на эффективность распознавания. 4.Доказательство влияния числа классов на эффективность распознавания. З А Н Я Т И Е № 6 Основы математического моделирования сложных технических систем 1.Основные определения теории моделирования систем (модель, моделирование, описание системы, изоморфность модели и системы). 2.Характерные особенности сложных систем. Принципы построения моделей сложной системы (декомпозиции, допустимых упрощений). 3.Назначение и сущность опытно-теоретического метода испытаний сложных систем. 4.Назначение частных и системных моделей в испытаниях сложных систем. З А Н Я Т И Е № 7 Метод статистических испытаний (Монте-Карло) 1.Сущность метода статистических испытаний и его достоинства. 2.Понятие псевдослучайного числа. Особенности квазислучайных величин, получаемых на ЭВМ. 3.Принципы статистического моделирования независимых случайных событий. 4.Способы получения на ЭВМ случайных чисел с заданным законом распределения. З А Н Я Т И Е № 8 Математическое моделирование систем распознавания образов 1.Цель компьютерного моделирования СР. 2.Особенности моделирования распознаваемого объекта. 3.Моделирование средств определения характеристик распознаваемых объектов. 4.Моделирование каналов связи и передачи информации. 5.Оценка эффективности распознавания при моделировании СР. 6.Задачи управления при моделировании. 7.Особенности применения опытно-теоретического метода испытаний сложных систем к моделированию СР. 8.Использование моделирования СР на этапах их создания и оптимизации. Л И Т Е Р А Т У Р А (1( Конспект лекций по курсу "Основы построения систем распознавания образов". (2( Горелик А.Л. Методы распознавания. М., "Высшая школа", 1986 г. (3( Аркадьев А.Г., Браверман Э.М. "Обучение машины распознаванию образов" М., "Наука", 1964 г. (4( Левин Б.Р."Теоретические основы статистической радиотехники" М. , "Сов.радио", 1968 г. (5( Вентцель Е.С . "Теория вероятностей" М."Физматгиз", 1969 г. (6( Мартин Ф. "Моделирование на вычислительных машинах" М., "Сов.радио", 1972 г. (7( Полляк Ю.С. "Вероятностное моделирование" М., "Сов.радио", 1971 г. (8( Бусленко Н.П., Голенко Д.И., Соболь И.М. и др "Метод статистических испытаний. (Метод Монте- Карло)" М., ГИФМЛ, 1962 г. (9( Васильев В.И. "Распознающие системы. Справочник" Киев, Наукова думка, 1983 г. (10( Барабаш Ю.Л., Зиновьев Б.В. и др. "Вопросы статистической теории распознавания" М., Сов. радио, 1967 г. (11("Физика визуализации изображений в медицине" т.2., М., Мир, 1991 г.
