1.5. Последовательная решающая модель для классификации образов

В статистических системах классификации, описанных в § 1.4, все признаков «наблюдались» классификатором за один шаг. Это называют решающей процедурой с фиксированным объемом выборки. При этом фактически не учитывалась стоимость измерений признаков. Очевидно, что недостаточное число измерений признаков не позволит получить удовлетворительные результаты классификации. С другой стороны, практически нецелесообразно измерять чрезмерно большое число признаков. Если должна учитываться стоимость выполнения измерений признаков или если признаки входных образов по своей природе возникают последовательно, необходимо применять последовательную решающую процедуру [4, 5] к этому классу задач распознавания образов [6].

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

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

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

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

Применение процедуры последовательных решений к классификации образов предложено автором. В случае двух классов распознавания образов, можно применить последовательный критерий отношения вероятностей Вальда (п. к. о. в.) [4]. (Краткое введение в последовательный анализ дано в приложении А.)

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

где -мерная функция условной плотности вероятности X для класса образов Далее, вычисленная согласно (1.45), сравнивается с двумя останавливающими границами (порогами) Если

и если

Если то должны быть произведены дополнительные измерения и процесс продолжается до

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

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

Выражения (1.46) и (1.47) при знаках равенства представляют собой решающие границы, которые разбивают пространство признаков на три области: область, относящуюся к область, относящуюся к и область неопределенности (или нулевую область), заключенную между двумя границами. Область неопределенности соответствует условиям, когда не может быть принято окончательное решение. Можно показать, что при последовательном процессе классификации решающие границы изменяются с числом замеров признаков Предположим, например, что независимые замеры признаков с одномерной гауссовой функцией плотности со средним значением и дисперсией Для простоты вычислим вместо А». После того как выполнено первое измерение получим

Сравним

Если

(кликните для просмотра скана)

Теперь процедура классификации будет следующей: если

и если

и если

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

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

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

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

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

Останавливающая граница определяется соотношением

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

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

Для Двух классов образов, процедура классификации (1.60) эквивалентна последовательному критерию отношения вероятностей Вальда и поэтому сохраняет его оптимальность. Сохраняется ли оптимальность при не доказано. Однако эта процедура классификации близка к оптимальной в том смысле, что среднее число измерений, необходимых для исключения класса образов из дальнейшего рассмотрения, близка к минимуму, когда рассматриваются две гипотезы (о необходимости исключить данный класс образов и сохранить его). Общая блок-схема системы последовательного распознавания представлена на рис. 1.9. Моделирование с помощью вычислительной машины распознавания букв будет описано в § 2.3

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

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

Рис. 1.9. Система последовательного распознавания образов.

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

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