Основные задачи построения систем распознавания

 

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

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

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

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

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

Детерминированные признаки — признаки, принимающие конкретные числовые значения (например, размах крыла l_кр = 25 м, длина фюзеляжа l_ф = 50 м, масса самолета G=70 тит. д.), которые могут рассматриваться в качестве координат точки в признаковом пространстве, соответствующей данному объекту. При рассмотрении признаков в качестве детерминированных ошибками измерений пренебрегают.

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

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

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

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

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

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

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

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

Если признаки распознаваемых объектов логические и имеют количественные выражения, то для описания классов объектов на языке признаков необходимо (в предположении достаточности исходной информации) определить диапазоны значений признаков ∆xⁱ_j, j=l, ..., N, соответствующие классам Ω_h, i= = 1, ..., m. При этом каждый из отрезков может рассматриваться как элементарное логическое высказывание А, В, С, ... . Если признаки распознаваемых объектов есть суждения качественного характера, то каждый из них также рассматривается как элементарное логическое высказывание А′, В′, С′, ... . Для описания классов на языке этих признаков необходимо выяснить, какими из них характеризуется каждый класс, после этого установить ; зависимости в форме булевых соотношений между признаками А, В, С, ...; А′, В′, С′, ... и классами Ω₁ ..., Ω_m.

Если распределение объектов по областям D_i N-мерного пространства признаков для всех значений i= 1, ..., m вероятностное, то для описания классов необходимо определить характеристики этих распределений: функции плотности вероятности f_i(x₁, ..., x_N) значений параметров х₁ ..., x_N при условии, что объекты принадлежат классу Ω_i априорные вероятности Р(Ω_i) того, что объект, случайным образом выбранный из общей совокупности, окажется принадлежащим классу Ω₁.

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

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

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

Пусть в априорном словаре признаков содержится упорядоченный набор параметров объектов или явлений —- признаки x₁, ..., x_N, которые можно рассматривать как составляющие вектора х_а={х₁ ..., x_N}, описывающего априорное пространство признаков систем распознавания (априорное признаковое пространство) размерности N; конкретные точки этого пространства представляют собой распознаваемые объекты.

Положим, произведено разбиение объектов на классы Ω₁ ..., ..., Ω_m. Требуется выделить в пространстве признаков области D_i, i = l, ..., m, эквивалентные классам, т. е. характеризуемые следующей необходимой зависимостью: если объект, имеющий признаки х⁰₁, ..., x⁰_N, относится к классу Ω_i, то представляющая его в признаковом пространстве точка принадлежит области D_i.

Помимо геометрической существует и алгебраическая трактовка задачи: требуется построить разделяющие функции F_i (x₁ ..., x_N), i= 1,..., m, обладающие следующим свойством: если объект, имеющий признаки х⁰₁, ..., x⁰_N, относится к классу Ω_i то величина F_i(х⁰₁, ..., x⁰_N) должна быть наибольшей. Такой же она должна быть и для всех других значений признаков объектов, относящихся к классу Ω_i,. Если х_q обозначает вектор признаков объекта, принадлежащего к Ω_q-му классу, то для всех значений вектора х_q F_q(x_q)>F_g(x_q), q, g= 1, ..., m, q≠g.

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

 

(1.1)

 

На рис. 1.1 показано разбиение двумерного пространства признаков на области D₁ и D₂, соответствующие классам Ω₁ и Ω₂ (здесь 1 — решающая граница).

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

Алгоритмы распознавания основываются на сравнении той или другой меры близости или меры сходства распознаваемого объекта с каждым классом. При этом если выбранная мера близости L данного объекта w с каким-либо классом Ω_g, g = 1, ..., m, превышает меру его близости с другими классами, то принимается решение о принадлежности этого объекта классу Ω_g, т. е.

 

 

Рис. 1.1

 

В алгоритмах распознавания, базирующихся на использовании детерминированных признаков, в качестве меры близости используется среднеквадратичное расстояние между данным объектом со и совокупностью объектов {w_gl,..., w_gkg}, представляющих собой класс Ω_g:

 

(1.2)

 

причем метод измерения расстояния между объектами d(w, w_gs) свободен для выбора.

В случае, если необходимо учитывать веса W_j признаков x_j, j=l, ..., N, объекта w и признаков x_gsj объектов w_gs класса Ω_g, может быть применена метрика следующего вида:

 

(1.3)

 

В алгоритмах распознавания, базирующихся на использовании вероятностных признаков, в качестве меры близости используется риск, связанный с решением о принадлежности распознаваемого объекта к классу Ω_i, i=1, ..., m. Пусть даны описания классов {f_i(x), Р(Ω_i)}, х={х₁ ..., x_N} и риски правильных и ошибочных решений, представляющие собой элементы платежной матрицы вида

 

(1.4)

 

По главной диагонали матрицы расположены потери при правильных решениях, а по обеим сторонам от нее — потери при ошибочных решениях. Если с_ii<0, i=l, ..., m, то такие отрицательные потери можно рассматривать как выигрыш при правильных решениях.

Пусть в результате экспериментов установлено, что значения признаков у распознаваемого объекта w составляют x₁=х⁰₁, x₂=х⁰₂, ..., x_N=x⁰_N. Обозначим это событие a_N. Тогда значение риска, связанного с решением вида w Є Ω_g при условии, что имеет место событие a_N, будет

 

(1.5)

 

где условная апостериорная вероятность того, что w Є Ω_i в соответствии с теоремой гипотез или формулой Байеса

 

 

В общем случае решение вида w Є Ω_g принимается в случае, если

 

(1.7)

 

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

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

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

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

Первое соображение связано с наличием или возможностью создания конкретных технических средств наблюдений, обеспечивающих на основе проведения экспериментов определение признаков распознаваемых объектов, а также с целесообразностью использования тех или других технических средств, а значит, и признаков, определяемых с помощью этих средств. Это соображение диктуется ограничениями на ресурсы (финансовые, материальные, временные, весовые, габаритные, энергетические и т. п.), на возможность или допустимость создания или использования соответствующих технических средств (см. гл. 5). По поводу последнего приведем следующий пример. В системах медицинской диагностики заболеваний сердца наряду с использованием симптомов (признаков), определяемых с помощью электрокардиографов и рентгеновской аппаратуры, возможно использование признаков, получаемых с помощью ангиограмм — специальных снимков в рентгеновских лучах, сделанных при инъекции в сердце или коронарные артерии рентгеноконтраст-ного вещества. Этот метод диагностирования дает более точную информацию, чем электрокардиография или рентгенография. Однако, во-первых, он дорог (так, в США стоимость проведения ангиографии составляет 2 тыс. дол., что в несколько раз дороже проведения и рентгенографии и электрокардиографии), и, во-вторых, проведение ангиографии сопряжено подчас со смертельным риском.

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

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

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