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

— 4 ;

• Введение 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 танков были уничтожены огнем американских войск. Причиной столь частого ведения огня по своим машинам стало отсутствие прицелов, имеющих большую кратность увеличения и высокую разрешающую способность, тогда как основное вооружение танков и БМП было способно поражать цели за пределами дальности опознавания.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть произведено разбиение объектов на классы C₁, C₂, ,…, C_m. Требуется выделить в пространстве признаков области D_i, i=1, 2, …,m, эквивалентные классам, т. е. характеризуемые следующей зависимостью: если объект характеризуется набором признаков x={x₁, x₂, …, x_N} и относится к классу C_i, то представляющая его в пространстве признаков точка принадлежит области D_i.

Помимо геометрической, существует и алгебраическая трактовка задачи, которая состоит в следующем. Требуется построить разделяющие функции F_i(x₁, x₂, …,x_N), i=1, 2, …,m, обладающие следующим свойством: если объект, имеющий признаки x^o={x₁⁰, x₂⁰, …, x₃⁰}, относится к классу C_i, то величина F_i(x₁⁰, x₂⁰, …, x_N⁰) должна быть наибольшей. Она должна быть наибольшей и для всех других значений признаков объектов, относящихся к классу C_i.Если через x_{q обозначить вектор признаков объекта, относящегося к классу Cq, то для всех значений вектора xq}

F_{q( xq) > Fp( xp), q, p = 1, 2, …, m, q ? p}

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

F_{q(x) - Fp(x) = 0}

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

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

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

L (щ, C_{p) = max {L (щ, Ci)}, i = 1, 2, …, m}

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

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

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

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

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

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

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

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

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

В большинстве задач распознавания классы являются дискретными. Поэтому целесообразно изложить некоторые особенности распознавания образов применительно к такому случаю. Входная информация отличается определенной степенью сложности и вырабатывается некоторым реальным источником. Выходная информация сравнительно проста — она сводится к указанию класса. Существенным является то обстоятельство, что множество различных входных данных, поступающих от различных источников s_i1, s_i2,…, но несущих информацию об одном и том же образе щ, должны быть отображены в один и тот же класс C_i. Следовательно, распознавание образов представляет собой однозначное отображение. Это означает, что все входные данные, поступающие от s_i1, s_i2,…и подлежащие отображению в один и тот же класс, эквивалентны (хотя и различны) относительно соответствующего образа. На языке теории множеств это означает, что на множестве S_i={s_i1, s_i2,…} должно существовать некоторое отношение эквивалентности «S_i» .Отношением эквивалентности называется всякое отношение, обладающее свойствами рефлексивности, симметричности и транзитивности. Рефлексивность означает, что s_ii принадлежит к тому же классу, что и s_ii. Симметричность указывает, что если s_ii принадлежит к тому же классу, что и s_ij, то s_ij принадлежит к тому же классу, что и s_ii. Транзитивность означает, что если s_ii принадлежит к тому же классу, что и s_ij, а s_ij принадлежит тому же классу, что и s_ik, то s_ii и s_ik также принадлежат к одному и тому же классу.

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

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

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

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

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

1) r₁:S_i>F_i, обеспечивающее получение значений признаков F_i = {f_i1, f_i2,…}

2) r₂:F_i>С_i — процесс классификации, посредством которого входным данным ставятся в соответствие классы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— 4 ;

— 4 ;

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

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

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

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

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

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

. (1.1)

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

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

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

(1.2)

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

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

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

— 4 ;

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

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

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

. (1.3)

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

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

r_{12 - r22 = r21 - r11.}

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

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

(1.4)

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

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

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

е = е_{1P(C1) + е2P(C2), (1.5)}

где е₁ и е₂ — вероятности ошибок первого и второго рода соответственно.

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

. (1.6)

. (1.7)

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

— 4 ;

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

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

(1.8)

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

. (1.9)

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

. (1.10)

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

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

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

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

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

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

r_ij — потери при решении xC_j, если xC_i.

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

(1.11)

для всех k ? j.

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

(1.12)

или

(1.13)

для всех k ? j.

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

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

(1.14)

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

. (1.15)

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

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

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

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

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

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

(1.16)

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

.(1.17)

С ростом k математическое ожидание и дисперсия отношения правдоподобия u_k для классов C₁ и C₂ имеют вид

m_{ik = kmi, (1.18)}

у²_{ik = kу²i, (1.19)}

так как z_i также являются независимыми и одинаково распределёнными случайными величинами. С ростом k m_ik увеличивается, если m_i>0, и уменьшается, если m_i < 0. Увеличение у_ik пропорционально k^½ и происходит медленнее, чем возрастание m_ik. Кроме того, при больших k, в соответствии с центральной предельной теоремой, плотность вероятности отношения правдоподобия u_k стремится к плотности нормального распределения.

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

u_k?a > xC₁,

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

b?u_k > xC₂,

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

(1.20)

. (1.21)

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

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

. (1.22)

Поэтому

(1.23),

. (1.24)

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

(1.25)

(1.26)

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

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

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

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

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

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

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

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

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

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

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

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

— 4 ;

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

(1.27)

где r_j — стоимость наблюдений x_{1, 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 — корреляционные матрицы случайных величин, M_i — математические ожидания соответственно.

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

. (1.29)

Произведение M^T_{ix представляет собой коэффициент корреляции между векторами Mi и x. Легко видеть, что для принятия решения рассматриваемый классификатор сравнивает разность коэффициентов корреляции векторов x и М1 и x и M2 с выбранным порогом. Следовательно, его можно назвать корреляционным классификатором.}

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

(1.30)

или

. (1.31)

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

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

AУA^T=I. (1.32)

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