Файл: Горелик, А. Л. Некоторые вопросы построения систем распознавания.pdf

(4.4), иначе обеспечивает минимизацию математическо­ го ожидания расходов, связанных с реализацией процес­ са распознавания.

4.3.ОБЩЕЕ ПРЕДСТАВЛЕНИЕ АЛГОРИТМА ПРОЦЕССА РАСПОЗНАВАНИЯ

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

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

строится с учетом системы ограничений Г.

Наличие в алгоритме zo означает, что окончательное

решение о том, что объект принадлежит к одному из классов Оі, принимается без проведения экспериментов. В этом случае все операции, обозначаемые в алгоритме аі, ..., ßft и Zi, ..., zu, отсутствуют. Если в алгоритме го

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

79

чает, что на основе изучения признаков распознаваемого

правилу R, принимается окончательное решение, что

распознаваемый объект относится к определенному клас­ су, и дальнейшие эксперименты не проводятся.

Порядок планирования экспериментов в соответствии с алгоритмом (4.5) схематически изображен на рис. 4.1.

Р и с . 4.1.

80

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

Положим, возможные исходы эксперимента а1— Х'а

и X" . Эти исходы анализируются в блоке анализа ре­ зультатов экспериментов. При этом, если исход X " 0f

то, к примеру, принимается окончательное решение гДХ" ), а если — X' , то принимается решение провести новый эксперимент а2(Х' ). Пусть его возможные исходы X' X" и X '" . Анализ этих исходов может привести, на­

с обратной связью. Действительно, всякий раз результа­ ты эксперимента используются для корректировки пла­ на проведения последующих экспериментов.

4.4.АЛГОРИТМ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОГО ПЛАНА R

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

Для отыскания этого правила введем в рассмотрение

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

öik с исходами X , Ха и принято окончательной

решение z. Как правило, имеет место такая ситуация,

когда расходы на проведение экспериментов с помощью технических средств Т суммируются и не зависят от

объектов со и конкретных исходов экспериментов Ха .

В этом случае

Здесь Qi — убыток от принятия окончательного решения,

связанного с отнесением распознаваемого объекта со к классу £2;.

Для каждого объекта со и выбранногоДюследовательного правила R величина среднего убытка ÜW{R) равна

математическому ожиданию от величины Сш:

Ош(^) = М[Сш(Хаі...... X ; z(Xa , ..., X )], (4.7)

где математическое ожидание подсчитывается в соот­

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

быть определена иначе на основании следующего вы­ ражения:

82

следующим образом:

(4.9)

В выражении (4.8) п — число всевозможных цепочек

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

ка Um (R) следует усреднить с помощью априорной ве­

роятности появления объектов соответствующих классов Р(Пі) и каждый алгоритм характеризовать величиной

(4.4)

т

£МЯ) = Е ÜJR)P(Qt),

;=1

где Up(R) — функция убытка (функция риска).

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

ятный противник», чистыми стратегиями которого явля­ ются все объекты со из Qt-, в качестве второй стороны — система распознавания, чистыми стратегиями которой является совокупность последовательных правил R из Rr . Это, в свою очередь, позволяет рассматривать во­

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

Оптимальным байесовым последовательным прави­ лом назовем такой алгоритм R, который минимизирует

Up(R). Это означает, что UV(R) ^ U P(R) для всех воз­ можных алгоритмов R e Rr. При реализации системы

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

Введем в рассмотрение следующие три определения.

Определение 1. Риском прекращения эксперимен­

вероятностей объектов, которое вычисляется с помощью формулы Байеса по априорной вероятности появления объектов данного класса Р(£2і) и априорным вероятно­

стям вида

Частным случаем риска прекращения экспериментов

после цепочки исходов (Ха ,..., Ха ) является риск при­

нятия окончательного решения без проведения экспери­ ментов р°, который равен

Р° = min £ Сш(г) Р (Оі). Z^ z 9.г

Определение 2. Риском продолжения эксперимен­

тов после цепочки исходов Х„,..., X назовем величину

а,

Здесь inf берется по всевозможным последовательным правилам R (X a,..., Ха ), которые в соответствии с си-

84