Дуда Р., Харт П. - Распознование образов и анализ сцен, страница 8

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

Для формулировки задачи в общем виде обозначим п состояний природы вектором е=-(в(1), ..., в(п))', где е(1) относится к одному из с значений е„..., в,. Пусть Р(е) есть априорная вероятность и состояний природы. Пусть Х=(х„..., х„) есть матрица, определяющая п наблюдаемых векторов признаков, где х, есть вектор признаков, получаемый при состоянии природы со (1).

И наконец, пусть р(Х~в) — функция плотности условного распределения величины Х при условии, что множество состояний природы есть е. В этом случае апостериорная вероятность состояния е определяется выражением Р(е)Х)= Р р (х) (58) р(Х) =я~~ р(Х !св) Р (е), (59) Для составной задачи принятия решений в общем случае можно определить матрицу потерь и отыскивать решающее правило, минимизирующее составной риск. Данная теория строится пв аналогии с ранее рассмотренной простой задачей принятия решения, приводя в итоге к тому, что оптимальная процедура состоит в минимизации составного условного риска.

В частном случае, если при правильном решении потери отсутствуют и если все ошибки имеют одинаковую цену, то процедура сводится к вычислению Р(е~Х) для всех е и выбору такого е, апостериорная вероятность которого наибольшая. Так как при этом требуется проделать все необходимые вычисления для определения Р(е~Х), задача на практике часто оказывается чересчур громоздкой. Если каждая из компонент е(1) может принимать одно из с значений, то необходимо рассмотреть с" воз- Гя. 2. Байееоесяая шеория решений можных значений ео.

Задача несколько упрощается в случае, когда распределение вектора признаков хе зависит от соответствующего состояния природы ео (1) и не зависит от других векторов признаков и состояний природы. Общая плотность р(Х ~со) определяется при этом просто произведением плотностей компонент р(х;!ео(()): р (Х ( е) = ~ф р (х; ! ео (()). (60) Таким образом, вычисление р(Х ~со) при этом упрощается, однахо все еще сохраняются трудности определения априорной вероятности Р (ео). Эта вероятность, отражающая взаимосвязь состояний природы, лежит в основе составной байесовской задачи принятия решения. Поэтому задачу вычисления Р (со) нельзя упрощать, вводя предположение о независимости состояний природы.

Кроме того, на практике обычно стараются каким-нибудь способом йзбавиться от вычисления Р(ео~Х) для всех с' возможных значений ео. Оставим эти задачи предметом для дополнительных раздумий, а читателей, интересующихся дальнейшими подробностями, отошлем к соответствующей литературе. эдй. ПРИМЕЧАНИЯ. Таким образом, мы закончили изложение байесовской теории решений, остановившись особо на случае многомерного нормального распределения. Соображения, положенные в ее основу, весьма просты. Для того чтобы сделать общий риск минимальным, необходимо выбирать такое действие, при котором будет минимален условный риск, соответствующий выражению с Я (се; ! х) = ~с Х (я~ ~ ее~) Р (ео ~ х).

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

В некоторых случаях можно предположить некоторый вид функций плотности, однако значения характеризующих их параметров остаются неизвестными. Типичен, например, случай, когда либо известно, либо можно предположить, что плотности распределений имеют вид плотностей многомерных нормаль- 232. Библиографические и исторические сееденил 47 ных распределений, но векторы средних значений и ковариационные матрицы неизвестны. Чаще же об условных плотностях известно еще меньше, и нужно обращаться к процедурам, в которых конкретные предложения относительно плотностей меньше влияют на результаты.

Большинство последующих разделов части 1 данной книги как раз и будут посвящены различным процедурам, разработанным для решения этой проблемы. 2ЛЗ. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ СВЕДЕНИЯ Теория принятия решений связывается с именами многих известных математиков-статистиков, так что этому вопросу посвящено большое число научных работ. Среди общепринятых учебников по теории принятия решений имеются работы Вальда (1950), Блекуэлла и Гнршика (1954) и более элементарная книга Чернова и Мозеса (1959), Интерес представляет также работа Фергюсона (1967), в которой рассматривается ряд вопросов статистики с точки зрения принятия решений. Теория принятия решений тесно связана с теорией игр, развитой в классическом труде Неймана и Моргенштерна (1944) и в работе Льюса и Райфы (1957).

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

Ни одно из указанных обстоятельств не представляет серьезных трудностей при решении типичной задачи распознавания образов, поэтому классический байесовский подход в данном случае наиболее прост и целесообразен. Чоу (1957) одним из первых применил байесовскую теорию принятия решений к задаче распознавания образов. В свой анализ он ввел отказ от принятия решения, а в дальнейшем установил основное соотношение между величинами ошибки и коэффициентом отказов (Чоу, 1970). Точный расчет вероятности ошибки весьма сложен, в связи с чем большинство опубликованных результатов связано с определением границ для уровня ошибки (Альбрехт и Вернер, 1964; Ча и Чуи, 1967; Лейниотис и Парк, 1971).

Разделяющие функции к задаче классификаций были применены Фишером (1936); его подход будет рассмотрен в гл. 4. Мы используем это понятие, следуя Нильсону (1965). Андерсон (1958) детально ис- Ге. е. Байесоесиаи «нория реиииий следовал случай многомерного нормального распределения и получил квадратичные разделяющие функции несколько иного вида. Мэрилл и Грин (1960) показали, как можно применить это решение при распознавании образов.

Купер (1964) исследовал другие непрерывные распределения, для которых применение линейных и квадратичных разделяющих функций является оптимальным. Согласно Нильсону (1965), линейные разделяющие функции для случая двоичных независимых переменных (и многомерных, распределенных по закону Бернулли) получены Дж. В. Джонсом, хотя впервые публикации по этому вопросу появились у Минского (1961) и в дальнейшем с различными обоснованиями опубликованы Уиндером (!963) и Чоу (1965). Казмнрчаком и Штейнбухом (1963) получены оптимальные квадратичные разделяющие функции для случая тернарных независимых переменных; случай этот легко обобщить для вывода полиномиальных разделяющих функций и-й степени,,определяющих условия оптимальности для случая (и+1)- арных независимых переменных.

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

Кроме полученного Андерсоном и Бахадуром (1962) решения общего многомерного нормального случая для двух классов, других общих решений получено не было. Вместе с тем, как будет показано в гл. 5, решения многих задач можно найти, применяя другие критерии, помимо критерия минимума риска. Общая байесовская теория составных решений связана с более разнообразными задачами, нежели ранее описанная простая байесовская теория. Объяснение основных положений теории составных решений дано Абендом (1966); им же приведен ряд важных ссылок на соответствующие работы по статистике.

Оптимальные процедуры распознавания для случая марковской зависимости состояний природы предложены Равивом (1967) и Абендом (1968), причем Равив сообщает о результатах применения этих процедур при распознавании стандартного английского текста. В работе Абсида, Харли и Кеиала (1965) показано, как можно распространить марковский подход с одномерной ситуации на двумерные.