Методы распознавания образов при идентификации объектов бинарного класса в автоматизированных телекоммуникационных комплексах систем управления

 

Содержание

Введение3

1. Современное состояние и перспективы распознавания образов.9

1.1 Основные понятия.9

1.2 Признаки образов.11

1.3 Методы распознавания образов.12

1.4 Статистические методы распознавания образов.14

1.4.1 Введение в статистические методы.14

1.4.2 Проверка статистических гипотез при распознавании образов. Вероятность ошибки при проверке гипотез.16

1.4.3 Последовательная проверка гипотез.23

1.4.4 Линейные классификаторы.29

1.4.5 Оценивание параметров.38

1.5.6 Оценивание вероятности ошибки.46

1.5 Структурные методы в распознавании образов.59

1.5.1 Введение.59

1.5.2 Введение в формальные языки.61

1.5.3 Типы распознающих устройств в системах синтаксического распознавания образов.63

1.5.4 Модификации грамматик.70

1.5.5 Языки описания образов.73

1.6.6 Синтаксический анализ как распознающая процедура.78

2. Описание системы опознавания.86

2.1 Блок-схема системы опознавания.86

2.2 Описание оптической системы.88

2.3 Описание матрицы фотоэлементов.91

2.4 Описание системы предварительной обработки.92

2.5 Описание вычислительной системы.96

2.6 Алгоритм распознавания.98

2.6.1 Описание подклассов.98

2.6.2 Описание признаков подклассов.99

Заключение.102

Литература.104

Введение

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

В качестве примера можно привести следующий факт. В ходе операции «Буря в пустыне» войска США потеряли 20 БМП «Брэдли» и 9 танков «Абрамс». Из них 17 БМП и 7 танков были уничтожены огнем американских войск. Причиной столь частого ведения огня по своим машинам стало отсутствие прицелов, имеющих большую кратность увеличения и высокую разрешающую способность, тогда как основное вооружение танков и БМП было способно поражать цели за пределами дальности опознавания.

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

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

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

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

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

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

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

Задача 1. Задача состоит в подробном и тщательном изучении объектов, для распознавания которых предназначена проектируемая система. Её цель - уяснить особенности изучаемых объектов и определить, что роднит и отличает их друг от друга.

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

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

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

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

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

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

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

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

Пусть в словаре содержится упорядоченный набор параметров объектов или явлений - признаки x1, x2, …, xN. Величины x1, x2, …, xN можно рассматривать как составляющие вектора x={x1, x2, …, xN}, характеризующего пространство признаков.

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

Пусть произведено разбиение объектов на классы C1, C2, ,…, Cm. Требуется выделить в пространстве признаков области Di, i=1, 2, …,m, эквивалентные классам, т. е. характеризуемые следующей зависимостью: если объект характеризуется набором признаков x={x1, x2, …, xN} и относится к классу Ci, то представляющая его в пространстве признаков точка принадлежит области Di.

Помимо геометрической, существует и алгебраическая трактовка задачи, которая состоит в следующем. Требуется построить разделяющие функции Fi(x1, x2, …,xN), i=1, 2, …,m, обладающие следующим свойством: если объект, имеющий признаки xo={x10, x20, …, x30}, относится к классу Ci, то величина Fi(x10, x20, …, xN0) должна быть наибольшей. Она должна быть наибольшей и для всех других значений признаков объектов, относящихся к классу Ci.Если через xq обозначить вектор признаков объекта, относящегося к классу Cq, то для всех значений вектора xq

Fq( xq) > Fp( xp), q, p = 1, 2, …, m, q ? p

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

Fq(x) - Fp(x) = 0

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

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

Алгоритмы распознавания основываются на сравнении той или другой меры близости (сходства) распознаваемого объекта с каждым классом. При этом, если выбранная мера близости L данного объекта ? с каким - либо классом Cp, p=1, 2, , , m, превышает меру его близости с другими классами, то принимается решение о принадлежности этого объекта классу Cp, т. е. ?Cp, если

L (?, Cp) = max {L (?, Ci)}, i = 1, 2, …, m

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

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

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

1.1 Основные понятия

В распознавании образов можно выделить 2 направления [1]:

) в узком смысле - автоматическое распознавание таких образов, которые могут распознаваться при помощи органов чувств. Это направление будем называть распознаванием на основе данных, воспринимаемых органами чувств (sense-data pattern recognition);

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

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

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

В большинстве задач распознавания классы являются дискретными. Поэтому целесообразно изложить некоторые особенности распознавания образов применительно к такому случаю. Входная информация отличается определенной степенью сложности и вырабатывается некоторым реальным источником. Выходная информация сравнительно проста - она сводится к указанию класса. Существенным является то обстоятельство, что множество различных входных данных, поступающих от различных источников si1, si2,…, но несущих информацию об одном и том же образе ?, должны быть отображены в один и тот же класс Ci. Следовательно, распознавание образов представляет собой однозначное отображение. Это означает, что все входные данные, поступающие от si1, si2,…и подлежащие отображению в один и тот же класс, эквивалентны (хотя и различны) относительно соответствующего образа. На языке теории множеств это означает, что на множестве Si={si1, si2,…} должно существовать некоторое отношение эквивалентности «Si» .Отношением эквивалентности называется всякое отношение, обладающее свойствами рефлексивности, симметричности и транзитивности. Рефлексивность означает, что sii принадлежит к тому же классу, что и sii. Симметричность указывает, что если sii принадлежит к тому же классу, что и sij, то sij принадлежит к тому же классу, что и sii. Транзитивность означает, что если sii принадлежит к тому же классу, что и sij, а sij принадлежит тому же классу, что и sik, то sii и sik также принадлежат к одному и тому же классу.

При распознавании образов можно ввести в систему механизм обучения, который сводится к следующему. Проектировщик системы для каждого из отличающихся друг от друга образов i задаёт примеры si1, si2, …, sin, причем каждому образу ставится в соответствие метка, указывающая класс Ci, к которому он принадлежит. Множество таких примеров называют обучающим множеством. В процессе обучения система должна научиться отображать входную информацию в «правильные» классы. Обучающее множество должно быть репрезентативно относительно всех возможных входных данных. Результат распознавания зависит также от размера обучающего множества.

.2 Признаки образов

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

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

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

) r1:Si?Fi, обеспечивающее получение значений признаков Fi = {fi1, fi2,…}

) r2:Fi?Сi - процесс классификации, посредством которого входным данным ставятся в соответствие классы.

Основная проблема распознавания - изменчивость образов. Входные данные, которые должны быть классифицированы как объекты одного класса, могут отличаться довольно сильно. Причин такой изменчивости множество [1]:

1)изменчивость, связанная с процессом измерения (шумы в датчиках);

2)изменчивость, связанная с каналами связи;

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

1.3 Методы распознавания образов

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

1)Методы статистической теории решений.

Эти методы применяются при распознавании тех образов, признаками которых служат числовые значения, причём эти значения у образов, принадлежащих одному классу, различны. Априорные сведения существенны для выбора признаков; сведения об отклонениях значений признаков объектов одного класса должны собираться с использованием статистического анализа. Обе эти разновидности сведений могут способствовать формированию решающих функций, обеспечивающих классификацию. Подробно эта группа методов рассмотрена в работе [3]

2)Структурные (лингвистические, синтаксические) методы.

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

Более подробно эти методы будут рассмотрены ниже.

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

3)Метод базовых точек.

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

1.4 Статистические методы распознавания образов

1.4.1 Введение в статистические методы

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

Обозначим через x вектор признаков объекта. Каждую из составляющих этого вектора будем считать значением i-го признака, распределённым в соответствии с некоторым законом. Следовательно, вектор x будет случайным вектором. Множество таких векторов образует n-мерное пространство образов, а каждая конкретная точка этого пространства соответствует определенному объекту. Классам образов при этом будут соответствовать области этого пространства.

Задача распознавания образов сводится, таким образом, к определению границ областей, соответствующих различным классам. На рисунке 1 приведен простой случай двух распределений. Если из прошлого опыта эти два распределения вектора x известны, то можно установить между ними границу g(x1, x2), которая делит двумерное пространство на две области. Таким образом, при рассмотрении нового образа в зависимости от знака функции g(x1, x2) можно решить, принадлежит этот образ классу I или классу II.

Функцию g(x1,x2) называют дискриминантной функцией, а техническое устройство, определяющее знак g(x1, x2) - блоком распознавания образов или классификатором. На рисунке 2 изображена блок-схема классификатора в n-мерном пространстве.

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

Таким образом, решение задачи распознавания образов методами статистической теории решений состоит из двух частей: выбора информативных признаков и проектирования классификатора [3]. На практике между этими частями нет чёткой границы. Действительно, классификатор можно представить как устройство для выбора признаков, которое отображает m признаков в один (дискриминантная функция).

1.4.2 Проверка статистических гипотез при распознавании образов. Вероятность ошибки при проверке гипотез

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

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

Практически все критерии проверки гипотез основаны на сравнении величины, называемой отношением правдоподобия, с пороговым значением. Отношение правдоподобия l(x) определяется как отношение условных плотностей вероятности принадлежности вектора признаков x классам C1 и C2, т.е.

.(1.1)

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

1) Байесовское правило принятия решения, минимизирующее функцию риска.

Предположим, что, принимая то или иное решение, мы несём определённые потери (штраф). Величина этих потерь зависит от того, к какому классу принадлежит объект в действительности. Можно ввести матрицу риска R=, где rij - потери в случае принятия решения в пользу принадлежности объекта классу j, тогда как в действительности он принадлежит классу i. Если записать выражение для среднего риска и затем минимизировать его, то можно получить, что значение порога равно

,(1.2)

где rij - элементы матрицы риска. Здесь P(Ci) - априорные вероятности того, что объект принадлежит классу Ci.

2) Минимаксное правило принятия решения.

Байесовский критерий, минимизирующий риск, основан на сравнении отношения правдоподобия с пороговым значением (1.2), которое является функцией априорных вероятностей P(Ci), i=1, 2. Поэтому, если априорные вероятности не изменяются, то байесовское решающее правило всегда обеспечивает минимальный риск. Однако если априорные вероятности изменяются или их значение неизвестно, то зафиксированная величина порога уже не обеспечивает достижимого минимума риска. Минимаксный критерий используется для нахождения такой величины порога, при которой минимизируется максимум возможного риска, даже если априорные вероятности изменяются или неизвестны.

Таким образом, при использовании минимаксного критерия необходимо найти значения P*(Ci), при которых достигается максимум среднего риска, а затем подставить найденные значения в формулу (1.2).

3)Правило принятия решения, основанное непосредственно на вероятностях.

Его можно записать следующим образом:

.(1.3)

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

Сравнивая формулы (1.2) и (1.3), видно, что данное правило является частным случаем байесовского правила принятия решения, когда потери связаны соотношением

r12 - r22 = r21 - r11.

Это так называемый случай симметричной функции штрафа, при которой штрафом является вероятность ошибки, и критерий (1.3) её минимизирует.

Иногда вместо отношения правдоподобия l(x) удобно использовать величину -ln l(x). В этом случае решающее правило (1.3) примет вид

(1.4)

Вероятность ошибки при проверке гипотез.

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

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

? = ?1P(C1) + ?2P(C2),(1.5)

где ?1 и ?2 - вероятности ошибок первого и второго рода соответственно.

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

.(1.6)

.(1.7)

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

Критерий Неймана - Пирсона принятия решения.

Критерий Неймана - Пирсона используется, когда неизвестна матрица потерь R и априорные вероятности P(C1) и P(C2). Решающее правило Неймана - Пирсона представляет собой решающее правило, минимизирующее вероятность ошибки первого рода при условии, что вероятность ошибки второго рода есть фиксированная величина, например ?0. Для определения этого решающего правила необходимо найти минимум выражения

,(1.8)

где ? - множитель Лагранжа, который есть решение уравнения

.(1.9)

Если использовать плотность вероятности отношения правдоподобия, то уравнение для вычисления порога ? имеет вид

.(1.10)

Так как плотность вероятности p(l/C2) ? 0, то вероятность ошибки ?2, определяемая выражением (1.10), является монотонной функцией относительно ?. Иначе говоря, когда порог ? увеличивается, вероятность ошибки ?2 уменьшается. Поэтому после вычисления значений ?2 для нескольких значений порога ? можно найти такое ?, которому соответствует значение ?2, равное ?0. Однако получить точное решение уравнения (1.10) нелегко.

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

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

Проверка многих гипотез.

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

При обобщении функции штрафа на случай многих гипотез имеем

rij - потери при решении xCj, если xCi.

После минимизации величины риска можно получить

(1.11)

для всех k ? j.

Если rii=0 и rij=1, то неравенство (1.11) примет вид

(1.12)

или

(1.13)

для всех k ? j.

Проверка сложных гипотез.

Иногда условная плотность вероятности не задана непосредственно, но известны p(x/?i) и p(?i/Ci), где p(x/?i) - условная плотность вероятности вектора x при фиксированном значении некоторого параметра или вектора параметров ?i, а p(?i/Ci) - условная плотность вероятности вектора ?i при фиксированном классе Ci. В этом случае можно вычислить p(x/Ci) следующим образом:

,(1.14)

где областью интегрирования ? является вся область изменения ?i. После того, как условные плотности вероятности p(x/Ci) получены, можно составить выражение для отношения правдоподобия, как описано выше:

.(1.15)

Это выражение представляет собой критерий проверки сложных гипотез.

1.4.3 Последовательная проверка гипотез

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

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

Последовательный критерий Вальда.

Последовательный критерий проверки гипотез Вальда можно реализовать следующим образом. Пусть x1, x2, … - последовательно наблюдаемые, независимые и одинаково распределённые случайные векторы. Для каждого xj можно вычислить отношение правдоподобия

,(1.16)

являющееся случайной величиной. После k наблюдений отношение правдоподобия будет равно

.(1.17)

С ростом k математическое ожидание и дисперсия отношения правдоподобия uk для классов C1 и C2 имеют вид

mik = kmi,(1.18)

?2ik = k?2i,(1.19)

так как zi также являются независимыми и одинаково распределёнными случайными величинами. С ростом k mik увеличивается, если mi>0, и уменьшается, если mi < 0. Увеличение ?ik пропорционально k1/2 и происходит медленнее, чем возрастание mik. Кроме того, при больших k, в соответствии с центральной предельной теоремой, плотность вероятности отношения правдоподобия uk стремится к плотности нормального распределения.

Если установить решающее правило следующим образом:

uk?a? xC1,

a<uk<b?произвести следующие наблюдения,

b?uk?xC2,

то можно отнести объект x с вероятностью 1 к классу C1 или C2. Кроме того, при этом ошибки классификации зависят от значений a и b, т.е. при увеличении абсолютных значений a и b вероятности ошибки классификации уменьшаются, а количество наблюдений, требуемое для принятия решения, увеличивается. Соотношение между значением порога и ошибками классификации можно выразить следующим образом:

,(1.20)

.(1.21)

Для любых значений вероятностей ошибки ?1 и ?2 теоретически можно определить значения a и b из выражений (1.20) и (1.21).

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

.(1.22)

Поэтому

,(1.23),

.(1.24)

Левая часть выражения (1.23) содержит все векторы x, принадлежащие классу C1, и классифицирует их правильно. Следовательно, она равна 1-?1. С другой стороны, правая часть выражения (1.23) содержит все векторы x, принадлежащие классу C1, но классифицированные как принадлежащие классу C2. Следовательно, правая часть (1.23) равна ?2. Аналогично можно получить, что левая и правая части (1.24) соответственно будут равны ?1 и 1 - ?2. Тогда (1.23) и (1.24) можно переписать следующим образом:

(1.25)

(1.26)

Таким образом, для любых заданных значений вероятности ошибки ?1 и ?2 можно получить пороговые значения A и B из формул (1.25) и (1.26).

В заключение можно сделать некоторые замечания, касающиеся свойств последовательного критерия Вальда [3]:

) Для получения выражений (1.25) и (1.26) не требуется независимости и равенства распределений случайных векторов x1, x2, …,xn.

) Можно доказать, что критерий Вальда сходится с вероятностью 1.

) Критерий Вальда минимизирует среднее количество наблюдений, требуемых для достижения заданных вероятностей ошибки ?1 и ?2.

) Критерий Вальда не зависит от априорных вероятностей P(Ci), хотя ошибки и зависят от P(Ci).

Последовательный байесовский критерий.

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

) Наблюдаемые переменные взаимно коррелированны и имеют разные распределения.

) Значение порога должно изменяться при каждом наблюдении. На рис.5 изображён пример классификации двумерного объекта на классы C1 и C2. Если наблюдается случайный вектор x1, то для отношения правдоподобия можно установить значения порогов равными A1 и B1. Однако если наблюдаются два случайных вектора x1 и x2, то A2 должно быть равно B2, так как нельзя откладывать принятие решения до предъявления следующей переменной. Как правило, предполагают, что по мере увеличения k значения порогов стремятся к одному и тому же значению.

) Вероятность ошибки определяется условными плотностями вероятности p(x/C1) и p(x/C2) при наблюдении всего набора из n переменных.

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

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

,(1.27)

где rj - стоимость наблюдений x1, x2, …, xj; L(Ci, dj(x1, x2, …, xj)) - математическое ожидание потерь для случая, когда (x1, x2, …, xj)Ci и использовано решающее правило dj(x1, x2, …, xj); ?i - область пространства X, для которой последовательность испытаний заканчивается при j-м наблюдении. В случае байесовского критерия необходимо отыскать решающие правила dj(x1, x2, …, xj), j=1, 2, …, n, минимизирующие риск R для заданного множества стоимостей наблюдений.

1.4.4 Линейные классификаторы

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

Наиболее простым и общим видом является линейный или кусочно-линейный классификатор.

Байесовский линейный классификатор.

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

,(1.28)

где ?i - корреляционные матрицы случайных величин, Mi - математические ожидания соответственно.

Если корреляционная матрица равна единичной, то можно считать, что вектор x представляет собой наблюдение, искажённое белым шумом. Компоненты вектора x при этом некоррелированы и имеют единичную дисперсию, а байесовское решающее правило принимает вид

.(1.29)

Произведение MTix представляет собой коэффициент корреляции между векторами Mi и x. Легко видеть, что для принятия решения рассматриваемый классификатор сравнивает разность коэффициентов корреляции векторов x и М1 и x и M2 с выбранным порогом. Следовательно, его можно назвать корреляционным классификатором [3].

Если умножить (1.29) на 2, а затем прибавить и вычесть xTx из левой части, то можно получить решающее правило

,(1.30)

или

.(1.31)

Полученному решающему правилу можно дать следующую интерпретацию: сравниваются расстояния между вектором x и векторами M1 и M2 с порогом.

В общем случае, когда корреляционные матрицы не равны единичной, наблюдаемый шум коррелирован, и его часто называют «окрашенным». В этом случае байесовский классификатор так легко не интерпретируется. Однако по-прежнему целесообразно рассматривать в качестве решающего правила корреляционный классификатор или классификатор, основанный на вычислении расстояния. Для этого можно ввести декоррелирующее преобразование y = Ax, которое переводит коррелированный («окрашенный») шум в белый:

A?AT=I.(1.32)

Заметим, что пока корреляционная матрица ? является положительно определённой, матрица A существует и невырождена. Поэтому декоррелирующее преобразование обратимо, и наблюдения вектора y можно классифицировать также эффективно, как и наблюдения вектора x [3].

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

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

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

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

.(1.33)

Выражение h(x) есть линейная разделяющая функция относительно x. Задача синтеза классификатора заключается в том, чтобы для заданных распределений определить коэффициенты VT=[v1, v2, …, vn] и значение порога v0, оптимальные по различным критериям.

Если случайная величина h(x) распределена по нормальному или близкому к нему закону, то для вычисления вероятности ошибки можно использовать её математическое ожидание и дисперсию для классов C1 и C2, а затем выбрать параметры V и v0 так, чтобы минимизировать ошибку решения. Так как h(x) является суммой, состоящей из n слагаемых xi, приходим к выводу [3]:

1)если векторы x имеют нормальное распределение, то величина h(x) также имеет нормальное распределение;

2)даже если векторы x распределены не по нормальному закону, но при большом n выполнены условия центральной предельной теоремы, то распределение величины h(x) может быть близко к нормальному.

Математические ожидания и дисперсии величины h(x) в классах C1 и C2 равны

Mi = VTmi + v0,(1.34)

?2i = VT?iV.(1.35)

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

.(1.36)

Если требуется минимизировать риск R, то вместо вероятностей P(C1) и P(C2) в формуле (1.36) должны быть использованы величины r12P(C1) и r21P(C2). При такой замене предполагается, что r11 = r22 = 0.

Продифференцировав выражение (1.36) по параметрам V и v0, получим, что

,(1.37)

при этом h=0 и M2-M1 = [(m2/?22)?2-(m1/?21)?1].

Кусочно-линейные разделяющие функции.

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

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

В задачах со многими классами критерии проверки многих гипотез дают наилучшее в байесовском смысле решающее правило, обеспечивающее минимум риска или вероятности ошибки. В соответствии с критерием проверки гипотез плотность вероятности или её логарифм следует сравнивать с плотностями вероятности других классов, как следует из (1.11). На рис. 6,а изображены полученные таким образом границы. Если оценивание плотностей вероятности является слишком сложной задачей или границы, определяемые в соответствии с критерием проверки гипотез, слишком вычурные, то можно заменить эти сложные границы множеством простых линейных границ. Такая замена, конечно, приводит к некоторому ухудшению качества распознавания. Однако использование линейных границ особенно эффективно для задач распознавания многих классов, т.е. в тех случаях, когда сложность границ быстро возрастает с увеличением числа классов, и является желательным некоторое упрощение процедуры синтеза классификатора [3]. На рис. 6,б показана замена байесовских границ кусочно-линейными границами.

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

hij(x) = VTijx + vi0, i, j = 1, 2, …, M, i ? j,(1.38)

где M - число классов. Знаки Vij выбираются так, чтобы распределение класса i находилось в области положительных значений линейной функции hij(x), а распределение класса j - в области отрицательных значений. Из этого требования следует, что

hij(x) = hji(x).(1.39)

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

hi1(x) > 0, hi2(x) > 0, …, hiM(x) > 0 ? xC1(1.40)

(функция hii(x) исключена из рассмотрения). Наличие тёмной области на рисунке 6,б показывает, что M областей, определяемые условиями (390), не обязательно покрывают всё пространство. Если объект попадает в эту область, то кусочно-линейный классификатор не может принять решение о его принадлежности к определённому классу; эту область называют областью отказов. Решающее правило состоит из M-1 линейных разделяющих функций и логического элемента AND с M-1 входами, которые принимают значения sign{hij(x)}. Соответствующая блок-схема изображена на рис. 7. Поскольку каждая из параллельных цепей состоит из двух последовательно соединённых элементов, то такой кусочно-линейный классификатор иногда называют двухслойной машиной.

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

Вероятность ошибки решения для каждого класса ?i можно выразить через (M-1)-мерную функцию распределения вероятности:

(1.41)

(функция hii исключена из рассмотрения.). Тогда общая ошибка решения

.(1.42)

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

Кратко отметим несколько приближённых методов решения задачи [3].

1)Можно подстраивать коэффициенты V и v0 так, чтобы минимизировать вероятность ошибки решения ?, определяемую формулой (1.41).

2)Линейная разделяющая функция между парой классов строится с помощью одного из методов, рассмотренных ранее для случая распознавания двух классов. Вычисляются M(M-1)/2 разделяющих функций. Эти функции без дальнейшей коррекции используются в качестве кусочно-линейной разделяющей функции. Если распределения являются нормальными с равными корреляционными матрицами, то описанная процедура эквивалентна применению байесовского решающего правила. Если распределения существенно отличаются между собой, то дальнейшая коррекция решающего правила может привести к уменьшению ошибки. Однако часто оказывается, что уменьшение ошибки за счёт подстройки параметров V и v0 относительно невелико.

Обобщенные линейные разделяющие функции.

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

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

(1.43)

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

Другим важным случаем является использование квадратичных поверхностей, где r переменных gi(x) задают так, что первыми n переменными являются x2i, i=1, 2, …, n, следующими n(n-1)/2 - все пары xixj, i, j=1, 2, …, n, i?j, а последние n переменных представляют собой xi, i=1, 2, …, n. Относительно этого преобразования можно сказать, что для каждой квадратичной разделяющей функции в пространстве x существует соответствующая линейная разделяющая функция в пространстве функций gj(x).

Переменные gi(x) являются признаками. Выбор эффективной системы признаков представляет собой самостоятельный раздел теории распознавания образов.

1.4.5 Оценивание параметров

Как говорилось выше, если известны плотности вероятности классов, то для классификации объектов можно определить граничную поверхность, разделяющую пространство признаков на области. Следующий вопрос заключается в том, как по имеющейся выборке объектов оценить эти плотности вероятности? Эта задача является очень сложной, если нельзя сделать предположение о структуре многомерной плотности вероятности. Однако если можно задать вид этой функции, то задача сводится к определению конечного числа параметров. Для этого можно использовать известные статистические методы оценки параметров. Оценивание параметров плотностей вероятности известного вида и классификацию объектов на основе этих плотностей называют параметрическим методом классификации [3].

Первая задача, которая здесь возникает, заключается в оценке основных параметров плотностей вероятности, таких, как вектор математического ожидания, корреляционная матрица и т.д., в предположении, что эти параметры не являются случайными величинами. Далее следует рассмотреть случай, когда эти параметры - случайные величины. Такие задачи называют точечным оцениванием [3].

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

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

Пусть ? и - соответственно истинный вектор параметров и его оценка. Значение есть функция от наблюдаемых случайных векторов x1, x2, …, xN, т.е.

,(1.44)

где .

Оценка называется несмещённой оценкой параметра ?, если её математическое ожидание равно истинному значению параметра, т.е.

.(1.45)

Оценка называется состоятельной оценкой параметра ?, если сходится по вероятности к ?, т.е.

.(1.46)

Оценка называется эффективной оценкой параметра ?, если для всех возможных оценок

.(1.47)

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

.(1.48)

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

Оценки моментов.

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

Общий выборочный момент порядка i1+i2+…+in определяется как среднее от моментов порядка i1+i2+…+in отдельных случайных выборочных объектов

,(1.49)

где - k-я компонента j-го объекта.

Математическое ожидание оценки (1.49) вычислить нетрудно, оно равно истинному значению искомого момента распределения, а дисперсия (1.49) равна

,(1.50)

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

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

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

,(1.51)

.(1.52)

Формулы (1.51) и (1.52) - частные случаи формулы (1.49), поэтому оценки математического ожидания и автокорреляционной матрицы являются несмещёнными и состоятельными.

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

.(1.53)

Математическое ожидание оценки равно , отсюда видно, что такая оценка корреляционной матрицы является смещённой. Это смещение можно устранить с помощью следующей модифицированной оценки корреляционной матрицы:

.(1.54)

Нижнюю границу дисперсии любой несмещённой оценки можно определить с помощью следующего неравенства, называемого границей Крамера - Рао:

(1.55)

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

Любая несмещённая оценка, при которой в (1.55) имеет место равенство, является эффективной оценкой.

Оценка максимального правдоподобия.

Более общим методом точечного оценивания является выбор при наблюдаемой величине Z такой оценки, которая максимизирует условную плотность вероятности p(Z/?), или ln p(Z/?). Иначе говоря, выбирается значение параметра ?, при котором Z является наиболее правдоподобным результатом. Ясно, что эта оценка есть функция вектора Z. Логарифмическая функция рассматривается для удобства вычислений и, будучи монотонной, не изменяет точки максимума. Эту оценку называют оценкой максимального правдоподобия. Она представляет собой решение следующих эквивалентных уравнений:

,

или

(1.56)

Эти уравнения называют уравнениями правдоподобия.

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

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

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

Байесовская оценка.

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

,(1.57)

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

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

) Оценка, минимизирующая среднеквадратичную ошибку

В качестве функции штрафа можно использовать величину

.(1.58)

При этом байесовский риск (1.57) превращается в среднеквадратичную ошибку оценки . Минимизируя выражение (1.57) при условии (1.58) и при фиксированном векторе наблюдений Z, получим

.(1.59)

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

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

,(1.60)

где ?=?-M{?/Z}.

) Оценка, максимизирующая апостериорную вероятность.

Пусть функция штрафа имеет следующий вид:

(1.61)

где параметр ? и область ?? выбраны достаточно малыми так, чтобы условную плотность вероятности p(?/Z) можно было считать постоянной в данной области. Пусть ?V - объём области ??. Тогда выражение (1.57) можно переписать в виде

.(1.62)

Подынтегральное выражение в (1.62) является неотрицательным. Поэтому риск R можно минимизировать, если оценку выбрать равной значению параметра ?, которое максимизирует апостериорную плотность вероятности p(?/Z). Другими словами, эта оценка есть решение уравнения

или

.(1.63)

Такую оценку называют оценкой, максимизирующей апостериорную вероятность.

1.5.6 Оценивание вероятности ошибки

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

При оценке вероятности ошибки рассматривают две задачи. Первая из них состоит в оценивании вероятности ошибки по имеющейся выборке в предположении, что задан классификатор [3].

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

Оценка вероятности ошибки для заданного классификатора.

1) Неизвестны априорные вероятности - случайная выборка.

Предположим, что заданы распределения обоих классов и классификатор. Задача заключается в оценивании вероятности ошибки по N объектам, полученным в соответствии с этими распределениями.

Когда неизвестны априорные вероятности P(Ci), i=1, 2, то можно случайно извлечь N объектов и проверить, даёт ли данный классификатор правильные решения для этих объектов. Такие объекты называют случайной выборкой.

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

.(1.64)

Оценка максимального правдоподобия из уравнения (1.56) равна

,(1.65)

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

Математическое ожидание и дисперсия биномиального распределения соответственно равны

,(1.66)

.(1.67)

Таким образом, оценка является несмещённой.

) Известны априорные вероятности - селективная выборка.

Если известны априорные вероятности классов P(Ci), i=1, 2, то можно извлечь N1=P(C1)N и N2=P(C2)N объектов соответственно и проверить их с помощью заданного классификатора. Такой процесс известен как селективная выборка. Пусть ?1 и ?2 - число неправильно классифицированных объектов соответственно из классов C1 и C2. Поскольку ?1 и ?2 взаимно независимы, то совместная плотность вероятности ?1 и ?2 будет равна

,(1.68)

где ?i - истинная вероятность ошибки для класса Ci. В этом случае оценка максимального правдоподобия равна

.(1.69)

Математическое ожидание и дисперсия оценки соответственно

,(1.70)

.(1.71)

Таким образом, оценка (1.69) также несмещённая.

Нетрудно показать, что дисперсия (1.71) меньше, чем дисперсия (1.67). Это естественный результат, поскольку в случае селективной выборки используется априорная информация.

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

Оценка вероятности ошибки, когда классификатор заранее не задан.

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

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

Как правило, вероятность ошибки есть функция двух аргументов:

? (?1, ?2),(1.72)

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

Оптимальная классификация объектов, характеризуемых распределением с параметром ?2, осуществляется байесовским классификатором, который построен для распределения с параметром ?2. Поэтому

? (?2, ?2) ? ? (?1, ?2).(1.73)

Пусть для данной задачи ? - вектор истинных параметров, а - его оценка. Таким образом, оценка является случайным вектором и ?0=? (?, ?). Для любого конкретного значения оценки на основании (1.73) справедливы неравенства

,(1.74)

.(1.75)

Выполнив над обеими частями неравенств (1.74) и (1.75) операцию математического ожидания, получим

,(1.76)

.(1.77)

Если

,(1.78)

то для вероятности ошибки байесовского классификатора имеет место двустороннее ограничение

.(1.79)

Левое неравенство (1.79) основано на предположении (1.78) и не доказано для произвольных истинных плотностей вероятности. Однако это неравенство можно проверить многими экспериментальными способами. Из выражения (1.5) видно, что равенство (1.78) выполняется тогда, когда оценка проверяемой плотности вероятности, основанная на N наблюдениях, является несмещённой и классификатор заранее фиксирован. Следует отметить, что нижняя граница менее важна, чем верхняя.

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

) : одни и те же N объектов используются и для синтеза байесовского классификатора, и для последующей классификации. Этот случай назовём C-методом. Из (1.79) следует, что C-метод даёт, вообще говоря, заниженную оценку вероятности ошибки.

) : для синтеза байесовского классификатора используются N объектов, а классифицируются объекты из истинных распределений. Эту процедуру называют U-методом. U-метод также даёт смещённую оценку вероятности ошибки ?0. Это смещение таково, что его математическое ожидание является верхней границей вероятности ошибки. Объекты из истинного распределения могут быть заменены объектами, которые не были использованы для синтеза классификатора и независимы от объектов, по которым классификатор был синтезирован. Когда число классифицируемых объектов увеличивается, их распределение стремится к истинному распределению.

Для реализации U-метода имеется много возможностей. Рассмотрим две типовые процедуры.

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

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

Метод разбиения выборки.

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

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

,(1.80)

где ?i - истинная вероятность ошибки для i-го класса.

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

,(1.81)

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

Дисперсию оценки вычислить сложно. Однако в случае нормальных распределений с равными корреляционными матрицами интегралы в (1.81) можно привести к одномерным интегралам

,(1.81)

где ?i и ?2i определяются условными математическими ожиданиями:

,(1.82)

,(1.83)

.(1.84)

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

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

,(1.85)

где Ni - число объектов x(i)j класса i, используемых для синтеза классификатора.

Выражение для математического ожидания оценки достаточно громоздкое, здесь приводится простейший случай, когда P(C1)=P(C2) и N1=N2:

,(1.86)

,(1.87)

где d - расстояние между двумя векторами математических ожиданий, определяемое по формуле

.(1.88)

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

(1.89)

при ??>0 (b?0 и c>0).

Математическое ожидание и дисперсия плотности вероятности (1.89) соответственно равны

,(1.90)

.(1.91)

Исключив c, получим верхнюю границу дисперсии , т.е.

(1.91)

при b ? 0.

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

.(1.92)

Величину sэксп следует сравнивать с величиной sтеор, которая характеризует влияние числа объектов в экзаменационной выборке на оценку вероятности ошибки. Значение sтеор получается подстановкой в формулу (1.80) значений P(C1) = P(C2) =0.5 и ?1 = ?2 = ?0:

.(1.93)

Исключение задания класса для объектов экзаменационной выборки.

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

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

Введём критическую область для задач классификации M классов:

,(1.94)

где P(x) - плотность вероятности смеси, t - критический уровень, 0 ? t ? 1. Условие (1.94) устанавливает, что если для данного объекта x значения P(C1)p(x/C1), вычисленные для каждого класса Mi, не превышают величины (1-t)p(x), то объект х не классифицируют вообще; в противном случае объект x классифицируют и относят его к i-му классу. Таким образом, вся область значений x делится на критическую область ?r(t) и допустимую область ?a(t), причём размеры обеих областей являются функциями критического уровня t.

При таком решающем правиле вероятность ошибки ?(t), коэффициент отклонения r(t) и коэффициент правильного распознавания c(t) будут равны

,(1.95)

,(1.96)

?(t) = 1 - c(t) - r(t).(1.97)

Предположим, что область отклонения увеличивается на ?r(t) за счёт замены значения t на t-?t. Тогда те x, которые раньше классифицировались правильно, теперь отклоняются:

(1.98)

при x??r(t). Интегрируя (1.98) в пределах области ??r(t), получим

(1 - t)?r(t) ? -?c(t) < (1 - t+?t)?r(t),(1.99)

где ?r(t) и ?c(t) - приращения r(t) и c(t), вызванные изменениями t. Из формулы (1.97) следует, что неравенство (1.99) можно переписать следующим образом:

t?r(t) ? ??(t) < -?(t - ?t)?r(t).(1.100)

Полагая ?t?0, получаем интеграл Стилтьеса

.(1.101)

Уравнение (1.101) показывает, что вероятность ошибки ?(t) может быть вычислена после того, как установлена зависимость между значениями t и r(t). Из решающего правила (1.94) следует, что при t = 1-1/M область отклонения отсутствует, так что байесовская ошибка ?0= ?(1-1/M). Кроме того, из формулы (1.101) можно установить взаимосвязь между вероятностью ошибки и коэффициентом отклонения, так как изменение вероятности ошибки можно вычислить как функцию от изменения коэффициента отклонения.

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

1.Для определения ??r(kt0) при t = kt0, k = 0, 1, …, m = (1-1/M)t0, где t0 - дискретный шаг переменной t, будем использовать относительно дорогостоящие классифицируемые объекты.

2.Подсчитаем число неклассифицированных объектов экзаменационной выборки, которые попали в область ??r(kt0), разделим это число на общее число объектов и обозначим полученное соотношение через ?r(kt0).

.Тогда из выражения (1.94) следует, что оценка вероятности ошибки

.(1.102)

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

1.5. Структурные методы в распознавании образов

1.5.1 Введение

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

Структурный подход к распознаванию образов даёт возможность описывать большое число сложных объектов путём использования небольшого множества непроизводных элементов и грамматических правил (правил подстановки). Грамматическое правило может быть применено любое число раз, так что оказывается возможным очень компактно выразить основные структурные характеристики бесконечного множества предложений. Различные отношения, определённые между подобразами, обычно могут быть выражены логическими и (или) математическими операциями [4].

Система синтаксического распознавания образов.

Систему синтаксического распознавания образов можно считать состоящей из трёх основных частей: блока предварительной обработки, блока описания (представления) объекта и блока синтаксического анализа. Обычно предполагается, что объекты на выходе блока предобработки представлены в достаточно хорошем качестве. Затем каждый подвергнутый предобработке объект представляют в виде структуры языкового типа. Этот процесс представления объекта состоит, во-первых, из сегментации, и, во-вторых, из выделения непроизводных элементов (признаков). Иными словами, каждый объект после предобработки делится на части и непроизводные элементы на основе заранее заданных синтаксических операций (или операций композиции) и получает своё представление через множество непроизводных элементов и определённые синтаксические операции. Решение о том, является ли представление объекта синтаксически правильным (т.е. принадлежит ли он к классу объектов, описываемых данным синтаксисом или данной грамматикой), принимается блоком синтаксического анализа. По ходу синтаксического анализа этот блок может давать полное синтаксическое описание объекта в терминах грамматических единиц или дерева синтаксического анализа (если представление объекта синтаксически правильное). В противном случае объект либо исключают из рассмотрения, либо анализируют на основе других заданных грамматик, которые, может быть, описывают другие возможные классы рассматриваемых образов [4].

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

Блок-схема системы синтаксического распознавания образов изображена на рис.8.

1.5.2 Введение в формальные языки

Языки и порождающие грамматики.

Порождающая грамматика есть четвёрка G=(VN, VT, P, S), где VN и VT - основной и вспомогательный словари (или множества переменных) соответственно, P - конечное множество правил вывода или правил подстановки, символ - начальный символ. Объединение VT и VN составляет полный словарь V грамматики G, VT?VN=Ø. Правила подстановки из P обозначаются как ???, где ? и ? - цепочки символов из V,причём ? содержит хотя бы один символ из VN.

Часто используются следующие обозначения [4]:

1.?* - множество всех конечных цепочек символов из конечного множества ?, включая ? - цепочку нулевой длины, ?+= ?*-?.

2.xn - цепочка, состоящая из n раз написанной цепочки x.

3.|x| - длина цепочки, т.е. число символов в цепочке.

4. - цепочка ? непосредственно порождает цепочку ?, если ?=?1??2, ?=?1??2 и ??? - элемент P.

. - цепочка ? порождает цепочку ?, если существует такая последовательность цепочек ?1, ?2, …, ?N, что ?= ?1, ?= ?N и ?i ?i+1.

Язык, порождаемый грамматикой G, есть

L(G) = {x / xV*T, x - такая цепочка, что }.(2.1)

Если G - порождающая грамматика, то L(G) называется формальным языком.

Типы порождающих грамматик (по Хомскому).

) Грамматики типа 1 (грамматики непосредственно составляющих).

Правила подстановки грамматик типа 1 имеют следующий вид:

?1A?2??1??2,(2.2)

где AVN, ?1, ?2, ?V* и ???.

Это означает, что цепочку A можно заменить на ? в контексте ?1, ?2.

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

) Грамматики типа 2(бесконтекстные грамматики).

Правила подстановки таких грамматик имеют вид:

A??,(2.3)

где AVN и ?V+. Следует заметить, что такие правила подстановки позволяют заменять вспомогательный символ A на цепочку ? независимо от контекста, в котором встречается A.

Языки, порождаемые грамматиками типа 2, называются языками типа 2 или бесконтекстными языками.

) Грамматики типа 3 (автоматные или регулярные).

Правила подстановки грамматик типа 3 имеют вид

A?aB или A?b,(2.4)

где A, BVN и a, bVT. Заметим, что A, B, a, b - одиночные символы V.

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

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

1.5.3 Типы распознающих устройств в системах синтаксического распознавания образов

Автоматные языки и конечные автоматы.

Конечный (детерминированный) автомат - пятёрка A=(?, Q, ?, q0, F), где ? - конечное множество входных символов (алфавит), Q - конечное множество состояний, ? - функция, определяющая следующее состояние, т.е. отображение Q×? в Q, q0Q - начальное состояние и FQ - множество заключительных состояний. Функция ?(q, a) интерпретируется следующим образом: автомат A в состоянии q читает входной символ a, переходит в состояние q и сдвигает устройство считывания на один символ вперёд. Отображение ? можно распространить с одного входного символа на цепочку, если определить

? (q, ?) = q, ? (q, xa) = ? (? (q, x),a), x?*,a?.(2.5)

Таким образом, ? (q, ?) = q понимается так: находясь в состоянии q, автомат A просматривает цепочку x на входной ленте и переходит в состояние q, а считывающее устройство смещается вперёд с той части входного потока, которая содержит x. Говорят, что цепочка, или предложение x, допускается автоматом A, если

? (q, ?) = p для некоторого pF.(2.6)

Множество цепочек, допускаемых A, определяется как

T (A) = {x| ? (q0, x) F}.(2.7)

Недетерминированный конечный автомат есть пятёрка A = (?, Q, ?, q0, F), где ? - конечное множество входных символов (алфавит), Q - конечное множество состояний, ? - отображение Q×? во множество подмножеств множества Q, q0 - начальное состояние и F - множество заключительных состояний.

Единственная разница между детерминированным и недетерминированным вариантами автомата состоит в том, что ?(q, a) обозначает множество состояний (возможно, пустое), а не обязательно единственное состояние. Отображение ? (q, a) = (q1, q2, …, ql) интерпретируется следующим образом: автомат в состоянии q, читая на входе символ a, выбирает в качестве следующего любое из состояний q1, q2, …, ql, и сдвигает считывающее устройство на один символ вперёд. Как и в случае детерминированного автомата, отображение ? можно распространить с одного входного символа на цепочку, определив

? (q, ?) = q, ? (q, xa) = ?(qi, a), x?*, a?.(2.8)

Далее можно определить

? ( {q1, q2, …, ql},x) = ?(qi, x).(2.9)

Цепочка x допускается недетерминированным автоматом A, если найдётся такое состояние p, что

p? (q0, x) и pF.(2.10)

Множество цепочек, допускаемых автоматом A, определяется как

T (A) = {x| p? (q0, x и pF)}.(2.11)

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

Бесконтекстные языки и магазинные автоматы.

Магазинный автомат определяется как семёрка M = (?,Q,?,?,q0, Z0, F), где ? - конечное множество входных символов, Q - конечное множество состояний, ? - конечное множество магазинных символов, q0Q - начальное состояние, Z0? - начальный символ, первым появляющийся в магазинной памяти, FQ - множество заключительных состояний, ? - отображение Q×(?U{?})×? во множество конечных подмножеств Q×?*.

Устройство магазинного автомата близко к устройству конечного автомата, но он снабжён дополнительной магазинной памятью. Магазинная память организована по стековому принципу, т.е. символы можно вводить или считывать только на вершину и с вершины магазинной памяти [4].

Отображение

?(q, aZ) = {(q1, ?1), ,…, (qm, ?m)}, q1, …, qmQ, a?, Z?, ?1, …, ?m?*

интерпретируется следующим образом: магазинный автомат, находясь в состоянии q, считывает входной символ a и верхний символ магазина Z, переходит в состояние qi, заменяя в магазине памяти символ Z на символ ?i, 1?i?m, и продвигает устройство считывания на один символ. Запись

?(q, ?, Z) = {(q1, ?1), (q2, ?2),…, (qm, ?m)}(2.12)

означает, что магазинный автомат в состоянии qi при верхнем символе в магазине Z независимо от считываемого входного символа перейдёт в состояние qi и заменит Z на ?i, 1 ? i ? m. В этом случае считывающее устройство не работает. Такая операция используется для изменения содержания магазина и обычно называется ?-движением.

Для описания ситуации магазинного автомата используется упорядоченная пара (q, ?), qQ0 и ??*. Если (q,?)?(q, a, Z), q, qQ, для a(?U{?}), ?, ?? и Z?, то выражение

a (q, Z?)(q, ??)(2.13)

означает, что по правилам перехода данного автомата M входной символ a может вызвать переход M из ситуации (q, Z?) в ситуацию (q, ??). Если для символов a1, a2, …, an, ai(?U{?}), 1 ? i ? n, состояний q1, q2, …, qn+1 и цепочек ?1, ?2, …, ?n+1, ?i?*, 1 ? j ? n+1, справедливо, что

a :(qi, ?i)(qi+1, ?i+1), 1 ? i ? n,(2.14)

то пишется

a1a2…an: (q1, ?1)) (qi+1, ?i+1).(2.15)

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

T (M) = {x| x: (q0, Z0) (q, ?) для некоторых ?? и qF}.(2.16)

С другой стороны, язык N(M), допускаемый M при пустом магазине, определяется как

N (M) = {x| x: (q0, Z0) (q, ?) для некоторого qQ}.(2.17)

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

Языки, допускаемые магазинными автоматами при пустом магазине, являются бесконтекстными [4].

Машины Тьюринга.

Машина Тьюринга - шестёрка T = (?, Q, ?, ?, q0, F), где Q - конечное множество состояний, ? - конечное множество символов на входе, один из которых - пустой символ B. В начале работы n крайних левых полей на входе машины содержат символы входной цепочки (n - конечное число). Оставшееся бесконечное число полей заполнено специальным символом B - символом «пустое место», который не является входным.

Подмножество ??, не содержащее B, составляет множество входных символов, ? - отображение Q×? в Q×(?-{B})×{L,R} (оно может быть не определено для некоторых аргументов), q0Q - начальное состояние, FQ - множество заключительных состояний.

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

Ситуация машины Тьюринга задаётся тройкой (q, ?, i), где qQ, ?(?-{B})* - непустая часть ленты, i - расстояние читающей-пишущей головки от левого конца ?. Пусть (q, A1A2…An, i), 1 ? i ? n+1 - ситуация машины Тьюринга. Если ?(q, Ai) = (p, x, R), 1 ? i ? n, то движение T, под которым понимается элементарное действие машины, может быть записано как

(q, A1A2…An, i) (p, A1A2...Ai-1XAi+1…An, i+1).(2.18)

Это означает, что машина Тьюринга записывает в i-ю клетку символ X и сдвигает головку на одно поле вправо. Если же ? (q, Ai) = (p, X, L), 2?i?n, то

(q, A1A2…An, i) (p, A1A2...Ai-1XAi+1…An, i-1).(2.19)

В этом случае машина Тьюринга записывает символ X в i-ю клетку и сдвигает головку на одно поле влево, но не левее левого конца ленты. Если i=n+1, то машина считывает пустой символ B. Если ? (q, B) = (p, X, R), то

(q, A1A2…An, n+1) (p, A1A2,…An, X, n+2).(2.20)

Если же, наоборот, ? (q, B) = (p, X, L), то

(q, A1A2…An, n+1) (p, A1A2, …An, X, n).(2.21)

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

Язык, допускаемый машиной Тьюринга, определяется как множество

{x| x?* и (q0, x, 1) (q, ?, i) для некоторых qF, ??* и i}(2.22)

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

Недетерминированная машина Тьюринга - это такая машина, у которой ? - отображение Q×? во множество подмножеств множества Q×(?-{B})×{L, R}. Можно показать, что если язык L допускается недетерминированной машиной Тьюринга T1, то L допускается и некоторой недетерминированной машиной Тьюринга T2.

Линейно ограниченный автомат.

Линейно ограниченным автоматом M называется шестёрка M = (?, Q, ?, ?, q0, F), где Q - конечное множество состояний, ? - конечное множество входных символов, ?? - множество входных символов, ? - отображение Q×? во множество подмножеств Q×?×{L, R}, q0Q - начальное состояние, FQ - множество заключительных состояний. Множество ? содержит два специальных символа, обозначаемых обычно Ø и $, которые отмечают соответственно левый и правый концы цепочки. Их функция - не дать считывающему устройству уйти с той части цепочки, на которой задан вход.

Из определения следует, что линейный ограниченный автомат есть, в сущности, недетерминированная машина Тьюринга, которая никогда не сдвигается с той части входной ленты, на которой задан вход [4]. Ситуация линейно ограниченного автомата и связь между двумя ситуациями определяются так же, как и для машины Тьюринга. Язык, допускаемый линейным ограниченным автоматом, есть множество

{x|x(?-{Ø, $})* и (q0Øx$, 1)(q, ?, i)

для некоторых qF, ??* и i}.(2.23)

Если для любого qQ и A? отображение ?(q, A) содержит не более одного элемента, то линейно ограниченный автомат называют детерминированным.

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

1.5.4 Модификации грамматик

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

Программные грамматики.

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

Программной грамматикой Gp называется пятёрка (VN, VT, J, P, S), где VN, VT и P - конечные множества вспомогательных символов, основных символов и правил вывода соответственно, S - начальный символ, SVN, J - множество меток правил подстановки.

Правило вывода из P имеет вид

(r)???S(U)F(W).(2.24)

Правило подстановки ??? называется ядром. Здесь ?V*VNV и ?V*; r - метка (обычно номер правила); U - список переходов при успехе, W - список переходов при неудаче, U, WJ.

Программная грамматика действует следующим образом. Сначала применяется правило с меткой (1). Если делается попытка применить правило (r), чтобы заменить подцепочку ?, и выведенная перед этим цепочка содержит ?, то применяется правило (r) ???, и следующее правило выбирается из правил, метки которых содержатся в списке переходов при успехе U. Если выведенная цепочка не содержит ?, то правило (r) не используется, а следующее правило выбирается из тех, метки которых содержатся в списке переходов при неудаче W. В случае, когда ядра всех выводов имеют бесконтекстную форму (т.е. A??), грамматика называется бесконтекстной программной. Аналогично, когда ядра правил имеют регулярный вид или вид правил непосредственно составляющих, грамматика называется регулярной программной или программной грамматикой непосредственно составляющих. Показано, что язык, порождённый бесконтекстной программной грамматикой, может быть языком непосредственно составляющих. Более того, показано, что класс языков, порождённых бесконтекстными программными грамматиками, включает все бесконтекстные языки.

Индексные грамматики.

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

Индексной грамматикой называется пятёрка Gi = (VN, VT, F, P, S), где VN, VT, F и P - конечные множества вспомогательных символов, основных символов, индексов и правил подстановки соответственно, SVN - начальный символ. Каждый символ из F - это конечное множество специальных (индексных) правил подстановки вида A??, где A VN и ?V*. Правила подстановки из P имеют вид A?X1?1X2?2… Xm?m, где X1, X2, …, XmVNUVT, а ?1, ?2, …, ?m лежат в F*. Если XiVT, то ?i = ?.

Определим отношение на цепочках множества (VNF*UVT)* следующим образом:

. Если ?A?? - цепочка, в которой ? и ?(VNF*UVT)*, AVN, ?F*, а A?X1?1X2?2… Xm?m - правило подстановки из P, в котором XiV, а ?iF*, для всех i, то считаем, что

?A???X1?1X2?2…Xm?m?.(2.25)

Здесь ?i = ?, если XiVT, и ?i = ?i?, если XiVN .

. Если ?Af?? - цепочка, в которой ? и ?(VNF*UVT)*, AVN, fF и ?F*, а A?X1?1X2?2… Xm?m - индексное правило из f, то

?Af???X1?1X2?2…Xm?m?,(2.26)

где ?i = ?, если XiVT, и ?i = ?, если XiVN.

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

1.5.5 Языки описания образов

Выбор непроизводных элементов.

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

1.Непроизводные элементы должны служить основными элементами образов и обеспечивать адекватное и сжатое описание исходных данных в терминах заданных структурных отношений.

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

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

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

Выделение непроизводных элементов на границах и остовах.

Множество непроизводных элементов, которые обычно используют для описания границ и остовов, получают по схеме цепного кодирования. На двумерное изображение накладывают прямоугольную сетку, и узлы сетки, которые наиболее близки к точкам изображения, соединяют отрезками прямых. Каждому такому отрезку в соответствии с его наклоном присваивают восьмеричное число. Таким образом, изображение представляется цепью (последовательностью) или цепями восьмеричных чисел. Эта дескриптивная схема обладает рядом полезных свойств. Например, поворот изображения на угол, кратный 45º, сводится к прибавлению восьмеричного числа (сложение по модулю 8) к каждому числу цепочки. Конечно, при этом изображение может исказиться. Только поворот на угол, кратный 90º, никогда не приводит к искажению изображения. Легко выполняются и некоторые другие простые манипуляции с изображением, такие, как растяжение, изменение длины кривой, определение самопересечений. Изменяя шаг сетки, накладываемой на изображение, можно получить любое желаемое разрешение [4]. Этот метод не ограничен изображениями с односвязными замкнутыми изображениями. Его можно применять для описания произвольных двумерных фигур, составленных из прямых и кривых линий и отрезков. На рис.10 показано множество непроизводных элементов и кодовая цепочка 66767011221222, которая описывает кривую.

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

Второй способ выделения непроизводных элементов - кодирование геометрических образов, которые строятся из областей. Основными непроизводными элементами служат полупространства образов (поля наблюдения). Можно показать, что любая фигура аппроксимируется произвольным многоугольником, который, в свою очередь, можно представить как объединение конечного числа выпуклых многоугольников. Каждый выпуклый многоугольник можно представить в виде пересечения конечного числа полуплоскостей. Если подходящим образом задать последовательность выпуклых многоугольников, составляющих произвольный многоугольник, то можно однозначно определить минимальное множество в некотором смысле множеств, объединение которых даст исходную фигуру. По аналогии с лингвистикой фигура - это «предложение», составляющие её выпуклые многоугольники - «слова», а полуплоскости - «буквы» [4].

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

Использование семантической информации.

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

Начальное описание T(x) образа x можно определить выражением

T(x) = (Ts(x), Tv(x)),(2.27)

где Ts(x) - задание непроизводных элементов образа x и их взаимных отношений, а Tv(x) - значение признаков для каждого элемента. Структурная информация об образе x задаётся синтаксическим или иерархическим описанием

H(x) = (Hs(x), Hv(x)),(2.28)

где Hs(x) - синтаксическая компонента, состоящая из множества необходимых для порождения Ts(x) правил подстановки, а Hv(x) - выполнимость интерпретационного правила, соответствующего каждому правилу подстановки грамматики G, которое используется при грамматическом разборе выражения Ts(?). Таким образом, полное описание образа x определено выражением

(T(x), H(x)) = ((Ts(x), Tv(x)), (Hs(x), Hv(x))).(2.29)

Класс образов может быть описан ассоциативной семантической информацией и грамматикой G, такой, что для любого образа x из этого класса Ts (x)L (G). «Смысл» образа выражен как начальным, так и синтаксическим описанием.

Все признаки разделяются на две группы: унаследованные и синтезированные [4]. Унаследованные признаки касаются тех аспектов смысла, которые определяются контекстом фразы, а синтезированные связаны с самой фразой.

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

Семантические правила добавляются к бесконтекстной грамматике следующим образом. Каждому символу X(VN U VT) приписано конечное множество A (X) признаков. Оно разделено на два непересекающихся множества синтезированных A0(X) и унаследованных A1(X) признаков. Требуется, чтобы A1(S)=Ø и A0(X) = Ø при XVT. Каждый признак ?A(X) имеет множество возможных значений D?, из которого при появлении символа X в дереве синтаксического анализа может быть выбрано одно значение. Пусть множество P состоит из m правил подстановки, и пусть k-е правило имеет вид

Xk0 ? Xk1, Xk2, …, Xknk,(2.30)

где Xk0VN, n ? 0, и Xkj(VN U VT), 1 ? j ? nk. Семантическими правилами называются функции fkj?, определённые для всех 1 ? k ? m, 0 ? j ?nk, причём ?A0 (Xkj) при j = 0 и ?A1 (Xkj) при j > 0. Каждая такая функция - это отображение прямого произведения D?1×D?2×…×D?t во множество D? для некоторого t = t (k, j, ?) ? 0, где каждое ?i = ?i (k, j, ?), 1 ? i ? t, - это признак некоторого символа Xkli для 0 ? li ? nk. Иными словами, каждое семантическое правило переводит определённые признаки символов Xk0, …, Xknk в величину некоторого признака Xkj.

Приписывание семантики цепочкам бесконтекстного языка при помощи семантических правил осуществляется следующим образом. Для любой основной цепочки x нужно обычным образом построить дерево её вывода из начального символа S. Корнем этого дерева является символ S, а вершина, соответствующая применению k-го правила подстановки, является либо основным, либо вспомогательным символом xk0. Пусть X - символ какой-либо вершины этого дерева, а ?A (X) - признак этого символа. Если ?A0 (X), то X = Xk0 для некоторого k, а если ?A1 (X), то X = Xkj для некоторых j и k, 1?j?nk. По определению, признак ? имеет величину v для данной вершины, если в соответствующем семантическом правиле

fkj?: D?1×D?2×…×D?t ? D?(2.31)

все признаки имеют величины v1, …, vt для соответствующих вершин, помеченных символами Xkl1, …,Xklt, и v = fkj? (v1, …, vt). Этот процесс оценки признаков нужно проводить по всему дереву до тех пор, пока он не закончится естественным образом [4]. Полученные на этой стадии оценки признаков и являются «смыслом», соответствующим данному выводу.

1.6.6 Синтаксический анализ как распознающая процедура

После того, как построена грамматика, порождающая язык для описания рассматриваемого образа, необходимо построить устройство, распознающее объекты представленные цепочками, порождёнными этой грамматикой. Прямой подход к решению этой задачи состоит в создании отдельной грамматики для каждого класса объектов. Распознающее устройство для данной грамматики будет выделять только те объекты, которые принадлежат соответствующему этой грамматике классу. Например, для m классов объектов C1, C2, …, Cm можно построить m соответствующих грамматик G1, G2, …, Gm, таких, что цепочки, порождённые грамматикой Gi, будут представлять объекты из класса Ci. [4] Тогда для произвольного объекта, описываемого цепочкой x, проблема распознавания сводится к вопросу: верно ли, что

xL (Gi) для i = 1, …, m?(2.32)

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

Будем считать, что если объекты представляются единственным образом, то среди ответов на вопросы «верно ли, что xL (Gi) для i = 1, …, m?» может быть один только один положительный ответ, а все остальные - отрицательными. При ответе «xL (Gj)» считается, что x принадлежит классу Cj. Если же все ответы отрицательны, то считается, что x не принадлежит ни одному из классов.

Простой способ распознавания состоит в сопоставлении входной цепочки с прототипом или эталоном каждого класса. Эталонная цепочка задаётся в терминах непроизводных элементов. Сопоставление непроизводных элементов может осуществляться параллельно или последовательно. Цепочка x относится к тому классу, из которого взята эталонная цепочка, наилучшим образом согласующаяся с x. В этом случае требуется либо точное совпадение x с эталоном, либо выполнение подходящего критерия согласования. Конечно, не менее важен и выбор эталонных цепочек [4]. Этот подход, хотя и выглядит менее гибким, может быть реализован быстродействующей программой. Однако в действительности иерархическая структурная информация используется недостаточно, и этот подход полезен только тогда, можно определить соответствующие эталонные цепочки и имеющий смысл критерий согласования.

Если грамматика Gi регулярна, то можно построить детерминированный конечный автомат для распознавания цепочек, порождённых Gi. Если Gi - бесконтекстная или программная грамматика, то обычно требуется недетерминированный автомат. В процессе распознавания используется, вообще говоря, некоторая недетерминированная процедура. Задача синтаксического анализа может быть поставлена следующим образом: для заданного предложения x и грамматики G построить треугольник

S

x

и попытаться заполнить его внутреннюю часть деревом вывода x, правильным для грамматики G [4]. Если попытка успешна, то xL (G), в противном случае xL (G). В принципе не важно, как мы пытаемся заполнить треугольник. Это можно делать, начиная с корня дерева (грамматический разбор сверху вниз) или снизу к вершине (разбор снизу вверх). Оба способа называются разборами слева направо, так как там, где это возможно, символы в предложении обрабатываются слева направо. Какой бы способ не использовался, отдельные шаги состоят из попыток найти правило подстановки, подходящее для рассматриваемого участка предложения. Тот факт, что приходится делать пробные попытки, которые впоследствии оказываются ошибочными, делает синтаксический анализ, вообще говоря, неэффективной процедурой. Правило подстановки выбирается только в том случае, если оно удовлетворяет некоторым априорным тестам. Например, выбираются только такие правила подстановки, которые подходят только для данного участка цепочки. Априорные тесты могут быть и более сложными. Правило подстановки может отбрасываться из-за того, что его применение приводит к большему количеству основных символов, чем содержится в исходной цепочке, либо к появлению основного символа, которого в цепочке нет. Быстрота синтаксического анализа зависит от того, насколько удаётся избежать ошибочных проб, которые и приводят к лишним затратам времени. Если порядок выбора шагов и априорные тесты таковы, что на каждом шаге применимо только одно правило подстановки, метод синтаксического анализа не может быть существенно улучшен (при условии, что проверка априорных тестов не слишком длинна). Однако если на каждом шаге есть несколько возможностей, то общее число возможных грамматических разборов растёт экспоненциально. Поэтому выбор априорных тестов и порядок действий становятся чрезвычайно важными [4].

Грамматический разбор сверху вниз.

Синтаксический анализ сверху вниз начинается с символа S, обозначающего всё предложение, и состоит из последовательных пробных подстановок правил, которые порождают подходящие для этого предложения вспомогательные символы. Чистый синтаксический анализ сверху вниз - полностью целенаправленный процесс. Главной целью является вывод из S данного предложения x. Делается предположение, что анализируемая цепочка действительно есть предложение в языке данной грамматики G. Поэтому первый шаг - выяснить, можно ли свести цепочку к правой части некоторого правила подстановки

S?X1X2…XN.(2.33)

Это выясняется следующим образом. Применение данного правила подстановки в случае, когда X1 - основной символ, возможно, если цепочка начинается с этого символа. Если же X1 - вспомогательный символ, ставится подзадача: определить, можно ли какое-либо начало цепочки свести к X1. Если это оказывается возможным, таким же образом проверяется X2, затем X3 и т.д. Если для некоторого Xi не удаётся найти подходящего места в выводе цепочки, то надо попробовать применить другое правило подстановки.

Точно также решаются подзадачи для всех AVN, проверяется применимость правила подстановки A?X1X2…Xl и ставится и решается новая подзадача. Если подзадачу решить не удаётся, то на предыдущем уровне надо попытаться применить другое правило.

При анализе слева направо и сверху вниз иногда вызывает затруднение повторение слева вспомогательного символа: правила подстановки вида A1?A1? могут приводить к бесконечным петлям при анализе. Это происходит, когда сведение части цепочки к символу A1 ставится как подзадача, и первым шагом в её решении оказывается решение той же задачи, т.е. сведение части цепочки к A1. Проблема повторения слева иногда решается путём какого-либо преобразования грамматики или изменения порядка разбора. Большую роль здесь также может сыграть порядок, в котором проверяются различные правые части правил подстановки при одной и той же левой части. Если только одна правая часть содержит повторение слева, то она должна проверяться в последнюю очередь. Однако такая последовательность действий может вступать в противоречие с другими условиями на порядок проверки, например, с требованием, что кратчайшая правая часть проверяется последней.

Грамматический разбор снизу вверх.

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

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

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

LR (k)-грамматики.

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

Один из таких классов называется классом LR (k)-грамматик. Запись LR(k) означает, что при грамматическом разборе слева направо и снизу вверх достаточен просмотр цепочки вперёд на k символов. Неформально будем относить бесконтекстную грамматику G = (VN, VT, P, S) к LR (k)-грамматикам, если для любой выводимой цепочки s верно следующее: s единственным способом записывается в виде ???, так что существует единственный правый вывод S*?A????, причём A заменено на ? на последнем шаге вывода, и если, кроме того, A и ? определяются однозначно при просмотре цепочки s слева направо не более, чем на k символов после ?. Если часть этих k символов расположена правее конца цепочки, то будем считать, что цепочка s выводима из S$k, где $VN.

Формально грамматика G относится к классу LR (k)-грамматик, если для каждой цепочки ??x1x2 (где ?, ?V*, и x1, x2VT* и |x1| = k), такой, что S$k??x1x2, выполняется следующее условие.

Если на предпоследнем шаге вывода получена цепочка ?Ax1x2 так, что

,(2.34)

и есть некоторая другая цепочка ??x1x3, такая, что

,(2.35)

то ? = ?, A = B и x = x1x3. Другими словами, в правом выводе двух цепочек, у которых совпадают k символов правее места последней подстановки, в цепочках, полученных на предпоследнем шаге этого вывода, должны также совпадать k символов правее места последней подстановки.

Важные свойства LR (k)-грамматик.

1)Каждая LR (k)-грамматика однозначна.

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

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

)Если язык L1 допускается некоторым детерминированным магазинным автоматом, то существует такая LR (0)-грамматика G, что L (G) = L1$.

2. Описание системы опознавания

2.1 Блок-схема системы опознавания

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

- оптическая система;

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

- система предобработки;

- вычислительная система (ЭВМ).

На вход системы распознавания поступает оптический сигнал A(x, y), который фокусируется оптической системой на матрицу фотоэлементов. Оптическая система характеризуется импульсной характеристикой H(x, y). Физический смысл импульсной характеристики состоит в следующем: импульсная характеристика является откликом системы на точечный источник ?(x, y). Для системы распознавания функция H(x, y) - одна из важнейших характеристик, так как от неё зависят такие величины, как расстояние, на котором система может распознавать объекты с заданной достоверностью. Тогда на выходе оптической системы входной сигнал преобразуется в сигнал следующего вида:

.(3.1)

Матрица фотоэлементов преобразует сигнал оптический сигнал B(x, y) в электрический. Следует учесть, что физически реализуемы только матрицы с конечным числом фотоэлементов. Таким образом, на выходе матрицы фотоэлементов будет множество электрических сигналов Bij, i=1, …, m, j=1, …,n. От количества элементов матрицы зависит такая важная характеристика системы, как разрешающая способность по горизонтали и вертикали, а также качество изображения, выводимого на дисплей вычислительной системы.

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

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

Режимы работы системы распознавания образов:

1.фоновый режим.

В этом режиме объект в поле зрения системы отсутствует, режим является «спящим».

2.выделение объекта из фона (обнаружение объекта).

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

3.распознавание объекта.

2.2 Описание оптической системы

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

Характеристики оптической системы определяются её импульсной характеристикой H(x, y). Рассмотрим, какой вид имеют импульсные характеристики различных элементов оптической системы.

Основные элементы оптических систем - линзы и управляемые транспаранты. Работа этих оптических систем основана на известном свойстве оптической линзы выполнять пространственное преобразование Фурье от входного сигнала A(x, y), т.е. импульсная характеристика линзы имеет вид

Hл(x, y) = exp {i (x+y)}(3.2)

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

В рассматриваемой оптической системе может быть осуществлено большое число различных функциональных преобразований входных сигналов и изображений [5]. Для этой цели в оптическую систему вводятся два управляемых транспаранта. Один из них размещается во входной плоскости системы, и в этом случае обрабатываемое изображение будет произведением исходного изображения на амплитудно-фазовую функцию пропускания управляемого транспаранта T1(x, y). Другой транспарант размещается в спектральной плоскости, и здесь также формируется произведение поступающего спектра и функции пропускания транспаранта T2(x, y). Выбирая две функции, реализуемые на обоих транспарантах, можно осуществить требуемое преобразование изображения. При этом может быть реализовано большое число режимов работы такой оптической системы, при которых отдельные транспаранты могут функционировать как вместе, так и по отдельности. Например, при наличии только второго транспаранта система может выполнять функции пространственного фильтра, отсеивающего ненужные пространственные частоты или шум.

В общем случае оптический поиск можно представить как процесс получения информации о распределённом в пространстве поле излучений. Особенностью источников такой информации является их двумерность. Процессы получения и обработки двумерной информации могут осуществляться либо путём параллельного просмотра всех элементов поля без сканирования (параллельный просмотр), либо путём сканирования простым пятном (последовательный просмотр), либо путём сканирования составным пятном (последовательно-параллельный просмотр). Способы обзора пространства простым сканирующим пятном представлены на рис. 11. Буквами обозначены следующие способы обзора: а - параллельный; б - последовательный; в - последовательно-параллельный; г - параллельно-последовательный; д - последовательно-последовательный [5].

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

Также известны некоторые упрощённые варианты обзорных схем параллельного восприятия визуальной информации. Такой вид обзора пространства имеет ряд достоинств. Он позволяет существенно уменьшить время, необходимое для обзора, повышает информативные характеристики систем и т.д. Однако ясно, что наличие многих каналов приводит к значительному усложнению таких систем. Способы обзора пространства составным сканирующим пятном (сложной апертурой) представлены на рис. 12. Буквами обозначены следующие способы обзора пространства: а - последовательный; б - последовательно-параллельный; в - последовательно-последовательный [5].

2.3 Описание матрицы фотоэлементов

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

2.4 Описание системы предварительной обработки

Кодирование и аппроксимация.

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

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

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

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

Фильтрация, восстановление и улучшение.

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

?( T(f))=T(?(f))(3.3)

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

Часто необходимо определить, насколько сильно два объекта согласуются друг с другом (насколько они похожи) или обнаружить сходство одного объекта с частью другого. Подсчёт взаимной корреляции между двумя функциями f и g служит одним из простых методов установления идентичности двух объектов с точностью до переноса и умножения на константу. Этот метод может быть очень полезным в тех задачах распознавания образов или их непроизводных элементов, для которых легко задать прототипы или эталоны этих образов.

При этом задача распознавания сводится к подсчёту взаимной корреляции исходного объекта с каждым из эталонов. Аналогично задачу нахождения объекта f в объекте g можно решить вычислением отношения двух коэффициентов взаимной корреляции. Пусть в объекте g содержится зашумленный объект f , и нужно найти этот объект посредством подсчёта взаимной корреляции эталона f* с объектом g .Можно показать, что если шум аддитивен и независим от f, то лучшим эталоном f* для обнаружения f является сам объект f. Это есть в точности согласованный фильтр.

Другой способ сравнения объекта с эталоном состоит в подсчёте не свёртки, а произведения преобразований Фурье объектов и последующем вычислении обратного преобразования Фурье полученного произведения. В этом случае операция сравнения определена в области частот или пространственных частот. Одно из важных применений такой фильтрации лежит в задаче восстановления объекта. Допустим, что имеющийся объект искажён в результате процесса передачи или аппроксимации. Если искажённый объект можно представить в виде свёртки f*g, где f -исходный объект, а g - некоторая функция, то для восстановления необходимо вычислить обратное преобразование Фурье функции , где FG - преобразование Фурье свёртки f*g.

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

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

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

Сегментация изображения.

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

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

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

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

2.5 Описание вычислительной системы

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

При описании вычислительной системы представляет интерес подробное рассмотрение режимов её работы.

Фоновый режим.

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

Режим обнаружения объекта.

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

1.различия в яркости фона и объекта.

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

2.движение объекта.

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

3.распознавание объекта.

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

.6 Алгоритм распознавания

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

2.6.1. Описание подклассов

Проще всего структуру подклассов привести в иерархическом виде.

Объект

НаземнаяВоздушная

техникатехника

ГусеничнаяКолёснаяВертолётСамолёт

техникатехника

ТанкДругаяГрузоваяДжип

БМПтехникамашинаПрочее

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

Различение приведённых классов проводится по различным признакам: контурным, структурным и по базовым точкам.

2.6.2 Описание признаков подклассов

Различение наземной и воздушной техники.

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

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

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

Различение других подклассов.

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

Типы воздушной техники в системе распознавания образов.

Примерные контуры самолётов и вертолётов приведены на рис. 13. и 14.

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

Типы наземной техники в системе распознавания образов.

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

Заключение

В данной дипломной работе проведено следующее:

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

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

) Проведён анализ литературы, посвященной состоянию области распознавания образов на сегодняшний день.

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

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

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

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

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

Литература

1.Распознавание образов. Состояние и перспективы. Пер. с англ. под редакцией Гуревича И.Г. М.: Радио и связь, 1985.

2.Горелик А. Л., Скрипкин В. А. Методы распознавания. Учебное пособие для ВУЗов. М.: Высшая школа, 1984.

.Фукунага К. Введение в статистическую теорию распознавания образов. М.: Наука, 1979.

.Фу К. Структурные методы в распознавании образов. М.: Мир, 1977.

.Катыс Г.П. Восприятие и анализ оптической информации автоматической системой. М.: Машиностроение, 1986.

Содержание Введение3 1. Современное состояние и перспективы распознавания образов.9 1.1 Основные понятия.9 1.2 Признаки образов.11 1.3 Методы

Больше работ по теме: