Алгоритм управления процессом распознавания

 

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

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

 

(9.5)

 

где свидетельствуют о том, что алгоритм строится с учетом системы ограничений Г.

Наличие в алгоритме члена z⁰_i означает, что окончательное решение о том, что объект принадлежит классу Ω_i, принимается без проведения экспериментов. В этом случае все операции (a₁,..., а_k; z¹_i, ..., z^k_i) отсутствуют. Если в алгоритме z⁰_i отсутствует, то назначается проведение экспериментов а₁первой стадии. Если на основе признаков объекта, определенных по информации экспериментов первой стадии, принимается окончательное решение о его принадлежности какому-либо классу z¹_i (х_a1), то все операции, обозначаемые в алгоритме а₂, ..., а_k; z⁰_i, z²_i, ..., ..., z^k_i, отсутствуют.

Наличие в алгоритме члена a_k(x_a1, ..., х_аk-1) означает, что на основе изучения признаков распознаваемого объекта, полученных в результате исходов экспериментов х_а1, ..., х_ak-1, принято решение о проведении экспериментов а_kÎА^Г_k стадии л.

Наличие в алгоритме члена z^л_i (х_а1, ..., х_л) означает, что после получения исходов х_в1, ..., х„_к экспериментов а_и ..., а_к, проведенных согласно правилу R, принимается окончательное решение о принадлежности распознаваемого объекта к классу Ω_i и дальнейшие эксперименты не проводятся. Порядок планирования экспериментов проводится в соответствии с алгоритмом (9.5), изображенным на рис. 9.1.

Алгоритм работает следующим образом. Пусть на вход системы распознавания поступил объект w. Установлено, что принимать окончательное решение без проведения экспериментов z⁰_i нецелесообразно и для определения его признака решено провести эксперимент а₁ (из каких соображений принимаются подобные решения, будет показано ниже). Положим, что возможные исходы эксперимента будут x_a1¢ и х_a1¢¢. Эти исходы анализируются в блоке анализа результатов экспериментов БАРЭ. При этом если исход эксперимента а₁ будет х_a1¢¢, то, например, принимается окончательное решение z¹_i(x_a1¢), а если исход эксперимента будет x_a1¢¢, то принимается решение провести новый эксперимент а₂ (x_a1¢). Пусть его возможные исходы будут x_a1¢, x_a2¢¢ и x_a3¢¢¢. Тогда их анализ может привести, например, к таким решениям: если исходы эксперимента a₂(x_a1¢) будут x_a1¢ или x_a3¢¢¢, то следует принять окончательные решения z²_q(x_a1¢, x_a2¢) или z²_q(x_a1¢, x_a2¢¢¢), i, q, g=l, ..., т, а если исход x_a2¢¢, то необходимо провести эксперимент а₃ (x_a1¢, x_a2¢¢). Исходы x_a3¢ и x_a3¢¢ этого эксперимента вновь анализируются, и разрабатывается план дальнейшего развития экспериментов.

 

 

Рис. 9.1

 

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

Построение алгоритма. Уравнение (9.5) определяет множество всех возможных последовательных правил поиска решений. В этом множестве должно быть определено правило, оптимальное с точки зрения минимизации затрат на проведение процесса распознавания. Для отыскания этого правила введем в рассмотрение карту штрафов С_w[х_a1, ..., х_аk; z^k_i {x_a1, ..., х_k)], согласованную с системой последовательных ограничений Г. Величина C_w[x_a1, ..., ..., х_аk; z^k_i (x_a1, ..., х_аk)] означает штраф, уплачиваемый в случае, когда подвергается распознаванию объект w. Для определения признаков объекта w проведены эксперименты а₁, ..., а_k с исходами x_a1, ..., х_аk и принято окончательное решение z^k_i(x_a1,..., х_аk). Как правило, имеет место такая ситуация, когда расходы на проведение экспериментов с помощью технических средств Т_b суммируются и не зависят от объектов со и конкретных исходов х_а1, ..., х_аk экспериментов. В этом случае

 

(9.6)

 

где C_w[z^k_i (x_a1,..., х_аk)] — ущерб от принятия окончательного решения о том, что w=Ω_i, после проведения к стадий экспериментов.

Для каждого объекта w и выбранного последовательного правила R значение среднего убытка `U_w(R) равно математическому ожиданию от величины С_w:

 

(9.7)

 

где математическое ожидание подсчитывается в соответствии с распределением Р_Ω.(х_аk+1½x_a1, ..., х_аk), которое определяет вероятность исхода х_аk+1 эксперимента а_k+1 при условии, что проведенные эксперименты а₁ ..., а_k дали исходы x_a1, ..., х_аk по всем возможным цепочкам развития эксперимента — до принятия окончательного решения в алгоритме R. Средний убыток, вычисляемый по всем возможным цепочкам исхода алгоритма R, оканчивающимся принятием окончательного решения z^k_i, может быть определен иначе так:

 

(9.8)

 

где n — число всех возможных цепочек развития экспериментов, P_Ωi(x_a1, ..., х_аk) — вероятность реализации цепочки экспериментов, закончившихся исходами x_a1, ..., х_аk; она может быть выражена следующим образом:

 

(9.9)

 

Так как алгоритм (9.5) должен носить массовый характер и заранее не известно, какого класса объект будет подвергаться распознаванию в каждой из конкретных ситуаций, то значение убытка `U_w(R) следует усреднить с помощью априорной вероятности появления объектов соответствующих классов P(Ω_i) и каждый алгоритм характеризовать функцией убытка, функцией риска

 

(9.10)

 

Теперь появилась возможность, подобно тому, как это осуществляется в теории последовательных статистических решений, методологические вопросы выбора приемлемого правила поиска последовательных решений рассматривать как игру двух сторон с функцией убытка U_P(R). В качестве одной стороны выступает «вероятный противник», чистые стратегии которого — все объекты w из Ω_i в качестве второй стороны — система распознавания, чистые стратегии которой — совокупность последовательных правил R из R^Г . Это, в свою очередь, позволяет рассматривать вопросы существования чистых минимаксных стратегий, смешанных минимаксных стратегий и байесовых стратегий. Класс байесовых стратегий оказывается в некотором смысле полным, т. е. для любой небайесовой стратегии найдется лучшая (или, во всяком случае, не худшая) байесова стратегия. Исходя из этого, в дальнейшем будем придерживаться именно байесова подхода к решению задачи.

Оптимальным байесовым последовательным правилом назовем такой алгоритм Ř, который минимизирует значение убытка U_P(R). Это означает, что U_P(Ř)£U_P(R) для всех возможных алгоритмов RÎR^Г. При реализации системы распознавания целесообразно использовать оптимальные байесовы алгоритмы. Принципиальная возможность построения таких алгоритмов, рассчитанных заранее до начала функционирования системы распознавания, определяется рекуррентными уравнениями для функций риска. Введем в рассмотрение следующие определения.

Риском прекращения экспериментов после цепочки исходов x_a1, ..., х_аk назовем величину

 

(9.11)

 

где P(Ω_i½x_a1, ..., x_ak) — апостериорная вероятность, вычисляемая с помощью формулы Байеса по априорной вероятности появления объектов данного класса Р(Ω_i)и априорным вероятностям вида P_Ωi [x_ak+l½x_a1, ..., х_аk].

Частный случай риска прекращения экспериментов после цепочки исходов x_a1, ..., х_ak — риск r₀⁰ принятия окончательного решения без проведения экспериментов, который равен

 

(9.12)

 

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

Риском продолжения экспериментов после цепочки исходов x_a1, ..., x_ak назовем величину

 

(9.13)

 

где inf берется по всем возможным последовательным правилам R(x_a1, ..., x_ak), которые в соответствии с системой последовательных ограничений Г можно построить с помощью экспериментов, принадлежащих соответственно A^Г_k+1 A^Г_k+2,...стадиям. Риск продолжения экспериментов после проведения экспериментов а_и ..., а_к с цепочкой исходов х_a1, ..., х_аk определяется расходами на дальнейшее проведение экспериментов (k+1)-й стадии, спланированных на основе оптимального последовательного правила Ř. В соответствии с (9.7) расходы определяются как затратами на проведение собственно экспериментов (k+ 1)-й стадии, так и наименьшими потерями, которые несет система распознавания от принятия окончательного решения о принадлежности распознаваемого объекта к соответствующему классу на основе полученной информации x_a1,..., x_ak, х_аk+1.

Риском после цепочки исходов х_a1, ..., х_аk называется

 

(9.14)

 

Приведенные определения позволяют записать следующее рекуррентное уравнение:

 

(9.15)

где вероятность исхода x_ak+1 эксперимента а_k+1.

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

 

(9.16)

 

Рекуррентное уравнение (9.15) с учетом (9.16) позволяет на основе использования рекурсии от N к N— 1, N—2 и т. д. и данных о значениях r⁰_k после каждой стадии проведения экспериментов от первой до N-й восстановить значения функций риска при всех значениях k=1, ..., N.

Порядок расчета таков. После установления количества стадий экспериментов определяются значения r⁰₀, r⁰₁(х_a1),..., r⁰_N (x_a1, ..., х_aN). По величине r_N(x_a1,..., х_aN) = r⁰_N(х_a1,..., x_aN) в соответствии с (9.15) находится величина Из сопоставления величинив соответствии с (9.14) определяется величина Это в свою очередь на основе (9.15) позволяет найти величину ..., N-кратное повторение описанной процедуры расчетов дает возможность определить величины и т. д. вплоть до риска проведения экспериментов первой стадии.

Нахождение значений функций риска продолжения и прекращения экспериментов после каждой из стадии позволяет осуществлять оптимальное последовательное планирование проведения экспериментов: эксперименты последовательно проводятся до тех пор, пока Как только (после цепочки исходов x_a1, ..., ..., х_аk) значение риска продолжения эксперимента становится больше или равно значению риска прекращения экспериментов, эксперименты следует прекратить и принять решение z^k_i (x_a1, ..., х_аk), при котором

 

(9.17)

 

Порядок управления экспериментами (до тех пор, пока их выгодно продолжать) определяется с помощью функции риска продолжения экспериментов: в качестве а_k+1 (х_a1, ..., ..., х_аk) в байесовом правиле следует выбирать такой эксперимент a_k+1ÎA^Г_k+1(x_a1, ..., х_аk), на котором достигается inf в правой части рекуррентного уравнения для риска (9.15).

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

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

 

 

2. Из физических соображений определяется предельное количество N стадий экспериментирования.

3. На основе (9.15) рассчитываются значения рисков продолжения экспериментов для всех стадий от N— 1 до первой.

4. Из сравнения величин r⁰_k и для всех возможных исходов экспериментов определяется оптимальное количество стадий экспериментирования*.

*В первом издании настоящей книги (1977) на конкретном примере проиллюстрировано применение рассмотренной методологии оптимального планирования процесса накопления апостериорной информации.