Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 34
Текст из файла (страница 34)
%ТО НОМЕР Э! СООТВЕТСТ ответствует такому (1 — 1)-разрядному слову а,а, ... а в в е целого (1 О) которое получится после записи з, в вид ц ,в алфавите (, е (4.25) в этом случае ;(1 — 1)-разрядного двоичного числа. Выражение,' . ) „Перепишется в виде ( ) ) д. (« /з ) Д«з яц (зг) ! Рц (з!)~ Рц (й) Рц Рц Ч— пз(„) ( ./ ) — плотность распределения вероятностей 1-го призна'где ац (х; з,) — плот ,,'ка для /-го класса при условии, что 1, 2, ... (( — ! и ;мают такие значения, при которых первые( — 1 разрядов слов а,а, ...
а„ ,,'соответствуют данному значению х;. Т образом, в рассмотренной выше постановке задача узнавааким о аз го итма для решения 'иия на этапе экзамена сводится к построению алгор !проблемы эквивалентности слов. Это может быт д ыть с елано, например, ';с помощью извест тных в математической статистике методов проверки ии к ите ии по-разному ..Гипотез. Разработанные в рамках этой теории крит р ')Рормализуют понятия эффективности принят р ия ешения в зависимо!«)РО а ';ьтн от характера исследуемои задачи и е щ Р им ю ихся в Оаспоряжении нных об априорных вероятностях классо $, $з— '.,'~решений каждого типа и т. д.
(см. З 4.4). Например, согласно принци/(,пу максимума апостериорной вероятности, соотв ' у щ у !1!Рию «и еального наблюдателя» и минимизирующему полную вероят"Ность ошибки опознавания, некоторая реал ц е д , 'Кому классу Ац апостериорная вероятност (/ ) = $! )) ь Р г'/Х!=(и ( /)) а!»)(! — яг)Г '~' /'.Г,Й~Р (Х//) которого максимальна (/» (Х//)=1»т ((Пц (зг)1 ! (г)ц(зг) ) ,,): Оценим полную вероятность Р, ошибки опознавания в этом слуподобия чае.
Очевидно, что при независимости признаков коэфф коэффициент правдо- ~-1 Р~г'втз Рассмотрим величину Л (Х) = 1п Л (Х) = ~з Л; (Х), где Л; (Х) = ч 1п Л; (Х) = аю 1и (р1,/р,а) + (1 — а ) 1п (ац/д;з) — дискретная случайнап величина, которая может принимать только два значения. Плотность распределения этой величины для /'-го класса можно записать в виде ец(Л1)=рц51 Л~ — 1п — ) + ри1, р,,) +оц 5()ч — — ' /, ъ) «. /' где 5 — символ дельта-функции. дисперсия величины Л1 (Х) могут быть тм/ 0 т,(л! лта/ Рис. 4.15. График плотности распределения вероятностей значений Л(л) яля классов 1 и 2 Математическое ожидание и найдены из соотношений нц() )=рц1п — Нл,-чц1п — ', Лц(Л;)=-рцац((п — '"~ Р~ ого кл Распределение вероятностей случайной величины Л (Х) ) для кажд асса можно получить применением центральной предел ремы, если и ост ьной теомых и достаточно велико.
Учитывая независимость использ для опознавания признаков, найдем, что величина Л (Х) уекласса асп р ределена нормально (рис. 4.15) с математическим ожидаа ( ) для/-го наем тт (Л) = ~ тц (Л~) и дисперсией сЮ! (Л) = ~с(ц (Л,). Соотв етственно используемому решающему правилу предъявленная для узнавания реализация Х относится к класс А„классу А, и решение не принимается, если Л (Х) соответственно больше, меньше или равна О. Таким образом, вероятность ошибки распознавания ле- 156 — вероятность появления соответствующего реализации Х вектора х = а„а„..., а„в классе Ат).
Для случая независимых признаков а рц (з1) = — р» и Р (Х//) = — П((рц)"' (дц)ц '1, ч 1 Принцип максимума правдоподобия в рассматриваемом случае при- водит к следующему решающему правилу. А, и Решающее правило: реализация Х относится к клас у А, с „классу и решение не принимается, если коэффициент правдоподобия равен /. Л (Х) = Р (Х/1) /Р (Х/2) соответственно больше, ме алыче, меньше или о Ю о ит в пределах ппп1) у, (Л) дЛ.( да(Л)дЛ1 - Р, - шах1) д, (Л) к 'о „х с(Л ~уа (Л) йЛ!. Для каждой из этих границ нетрудно установить в явном виде связь с выбранными значениями порогов.
Соответствую- :,щая верхней границе функция должна далее минимизироваться для „,,получения минимаксного значения Р,. При этом могут быть использо- ваны обычные методы поиска экстремума функции многих переменных (методы градиента, наискорейшего спуска и т. п.). Если на функцию ;; (х;) не накладывать никаких ограничений, то алгоритм поиска тдоцлжен предусматривать возможность появления локальных миниму- ,мов, не являющихся экстремальными. Эту задачу можно решить, на- :,пример, многократным случайным изменением значений порогов, по- лученных после достижения очередного минимума функции.
Число ",этих изменений (абросковз) должно соответствовать требуемой досто- верности отыскания экстремума, При использовании принципа максимума апостериорной вероят- , 'ности вероятность ошибки распознавания может быть найдена из уса ловия Р, = $, ) у, (Л) с(Л + $а ) уа (Л) дЛ, причем тт (Л) изменяется о иа величину 1п ($,/$а), а выражение для с(1 (Л) остается прежним. Сле- "дует отметить имеющие место практические трудности реализации , предложенного подхода к отысканию оптимальных значений порогов, .поскольку число используемых для узнавания признаков обычно ве- ,лико, а выражение для минимизируемой функции довольно громозд- ко. В этой связи рассмотренный подход можно использовать в слу- чаях, когда число признаков не превышает 5 — 8.
Назначение порогов при многоальтернатианой ситуации. Как уже ',указывалось выше, назначение порогов по признакам позволяет све- 'сти задачу многоклассовой идентификации к ряду последовательнйх ,"дихотомий. Задача может быть решена, например, следующим обра- , зом. Для каждой пары (/, 1) из и классов (/, 1 = 1, 2, " тп' 1, > /) ~в соответствии с той или иной методикой назначается порог Пц, по 1-му признаку. Общее число порогов по данному признаку составит 0,5т(т — 1), поскольку Пц, = Ппр При предъявлении реалйзации Х, подлежащей опознаванию, для 'нее фиксируется х; (1 =- 1, 2, ..., и) и в произвольном порядке осущест- чвляются последовательные дихотомии классов. На каждом этапе ре- 'шающей схемой определяется принадлежность предъявленной реали- 4)ации одному из классов, участвующих в дихотомии.
При этом другой асс нз рассмотрения исключается. Таким образом, общее число этаов опознавания данной реализации составляет пт — 1. Эта процеду- ''4 а может быть использована в случае, если заранее известно, что не- 'а(оторый класс А1, к которому в конечном счете относится реализация .)гт(, не может проиграть не только классам, участвовавшим с ним в ди- Яотомиях, но и классам, исключенным из рассмотрения на предшест- вующих этапах.
В противном случае возможны недоразумения. Пред- :доложим, что и = 3, реализация Х при дихотомии классов А, и Аа 157 Рнс. 4,! б. Процедура прняягвя п»сияя в пороговой системе прн мно гоальтернатнвной ситуации »бэ относится к А„а лри дихотомии А, и А, — к классу А,. Реализация опознается как принадлежащая классу А,. Однако класс А, может пРоигрывать классу А„что фактически не проверяется. Более того, если классы А, и А, не пересекаются ло отдельным признакам, то выможно отнесение к классу Аз реализации Х, появление которой в этом классе невозможно (она может в действительности принадлежать, напримеР, классу А,). Это происходит потому, что пороги ло призна- кам для каждой пары классов в ртппг утопг упапу общем случае различны, несмотря на то что лри каждой дихотомии РП/к/ используются одни и те же признаки. Описанная процедура может быть дополнена следующим образом (рис.
4.16). Р!"/к Э.т а и 1. На этом этале фиксируется вектор х = (х„х„...,х„), соответствующий предъявленной реализации Х. Р/т «/ Э т а и 2. На данном этапе производятся дихотомии каждой пары классов (1, 1) и вычисляются вероятности Рг» (Х//) и Рг» (Х!1) лс»явления Х в каждом из участвующих в дихотомии классов. Э т а п 3. На этом этапе подсчитываются алостериорные веРоятжениям ности классов, соответствующие данной входной ситуа ии т ц и, ио выра- й, П р,»(х/1) р(ьх)= — -'='' ' (! =1, 2,..., т) . ~ ~В» П Рз»(Х/1) »= », »е» Реализация Х относи относится к такому классу Аь алостериорная вероят- ность которого максимальна. Назначение порогов исходя из минимизации Р или гой к й- либо величины и и р многоальтернативной ситуации крайне затрудни, илидруго како- тельно. Иногда для этого можно использовать процедуру, применяе- мую ири построении оптимального статистического кода.
Тогда число порогов ло каждому признаку и количество этапов опознавания могут быть сведены к минимуму и равны соответственно т — 1 и Вл1 (1одат). Найдем, например, такую граничную точку П»„слева и справа от которой площади лод кривой т — '(д»г (х») + д»з(х,)+...+я» (х,)1= ~ ... ( т,„, (далее эти неРавенства считаются справедливыми для любого»). Тогда исходное множество функций (х ) (' = 1 2 т) и, следовательн, о, классов можно разделить на два подмножества, включающих функции я» (е = 1 2, ..., ') »ш, =,, ..., т ) и д»за (е, = т' + 1, 158 + 2 т) соответственно Очевидно что для симметричных мо' льных распределений т;з, ( Пл гл»аз~ П»г и т/2 лри т четном Р т/2~1 лри т нечетном. результате ло 1-му признаку будет назначено т — 1 порогов Пы, „, ..., П,, Аналогично назначаются пороги ло другим приз' аиам.
Эт а п 1. На этом этапе узнавания реализации Х значение х, я нее сопоставляется с Пы (1 = 1, 2, ..., и) и в соответствии с выраниым критерием принимается решение о принадлежности этой лизации к одному из подмножеств Жлассов е, или е„после чего из рас- Р гу Вмотрения исключается т — т или ' классов соответственно. Э та и 2. На этом этапе данная входная ситуация относится и одно.му из подмножеств выбранного~ лод- тц»)11!. т»» : множества классов и т. д. Таким обРазом, общее число эта- Рнс. 4.17. Назначенне порога П лов опознавания составит 1ояз т, есл»» прн дяхогомян классов А» н А» по : эта величина есть целое число, и прязнаку х~ Пора т) + 1, если она имеет дРоб' ную часть. Здесь 1...] — выделение целой части.
При распределе, ниях яц (х»), не являющихся симметричными и модальными, разделе' ние классов на подмножества можно производить ло значениям площа' дей лод кривыми дц (х,) слева и справа отсоответствующих порогов. Из рассмотреннйх выше процедур назначения порогов лрн много- , альтернативной ситуации более предпочтительной на этапе узнавания ;:является вторая процедура, обеспечивающая лри прочих равных усло- Виях меньшее время опознавания и меньшее число данных, подлежа"щих запоминанию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
