Дуда Р., Харт П. - Распознование образов и анализ сцен, страница 10
Описание файла
DJVU-файл из архива "Дуда Р., Харт П. - Распознование образов и анализ сцен", который расположен в категории "". Всё это находится в предмете "распознавание изображений" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "распознавание изображений" в общих файлах.
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 10 - страница
что рандомизацня в данном случае никакой выгоды не дает. 9. Рассмотрим многомерную нормальную плотность, для которой а,~=О, а ил=аз. Покажите, что Г 1 р(х)= а 2~и[! о; Д У2наг Опишите контуры постоянной плотности; запишите выражение для махаланобнсова расстояния от х до )з. Задачи 10. Пусть р(х(юг) й/(рг, оз) для одномерной задачи и двух классов при Р(ыг)=Р(ыь)=1/2. Покажите. что минимальная вероятность ошибки определяется выражением 1/2л ) а где а=!Рз — рх!/2а. Рассмотрите неравенство ( -гг/з!ы 1 (/! в Покажите, что Р, стремится к нулю при стремлении !рз — рг)/а к бесконечности.
11. Пусть р(х!ыг)-Ф ()ьп аз/) для дмерной задачи и двух классов прн Р(ыг) = = — Р(ы,)=1/2. Покажите, что минимальная вероятность ошибки определяется выражением Ф Р = — ( с (т/в!з би, )г 2л,) а где а=!!Рз — )ьг)!/2а. Пусть Р,=О и Рз=(р, ..., р)г. Используя неравенство из задачи 10, покажите, что Р, стремится к нулю при стремлении Ы к бесконечности. Выразите смысл этого результата словами. 12.
Пусть р(х)ы;) /т'(Рп Х) для д-мерной задачи н двух классов с произвольными априорными вероятнсстямн; рассмотрим махаланобисово расстояние гг =(х — )з;)' Х (х — Рг). а) Покажите, что градиент величины гг~ определяется выражением тгг = 22 (к — Рг). б) Покажите, что уг1 указывает одно н то же направление вдоль любой прямой, проходящей через Рр в) Покажите, что уг, и угз указывают противоположные направления вдоль пРЯмой. соединЯющей )ь, и Рз.
г) Покажите, что оптимальная разделяющая гиперплоскость касательна к гиперэллипсоидам постоянной плотности распределения в точке пересечения разделяющей гиперплоскссти с прямой, проходящей через рг и рз. 13. В предположении, что ьы>Хгг и ь,з)дзз, покажите, что в общем случае разделяющая функция, дающая минимум риска для независимого бинарного случая, описанного в равд. 2.!О, определяется выражением й(х)=мех+же, где ьт неизменг(а, а ыз есть а шо —— ',)", ! К вЂ” +!Ой — +!М 1 — рг Р (ыг) "зт — "и 1 — Ог Р (ыз) Х,з — )ез ' г=! 14. Пусть компоненты веитора х=(х,, ..., ха)г бинарны (! или 0). Пусть также Р(ы/) есть априорная вероятность состояния природы а/(!'=1, ..., с), н пусть рП=Рг(х1=! (ы/), !=1, ..., Н, /=1, ..., с, с компонентами хп статистически независимыми для всех х в ы/.
Гя. 2. Брйессвпиш шео ия решений Пока)ките, что минимальная вероятность ошибки получается при использо- вании следующего раша)ощего правила: принять решение юз, если ла(х)~Б/(х) для всех /, где р и Рг/ а/(х) =~~~~ хг )ой — -( ~~~«' (ой (1 )+1 Р( «и! 1 — рг/ 1$. Пусть компоненты вектора х= (х„..., х,г)Г тернариы (1, О нлн — 1) с ве- роятностями р//= Рг (х; = 1 ( ш/), ч// = Рг (х; = О ) ы/), гВ = Рг (хг — 1 ( ш/), причем компоненты х/ статистически независимы для всех х в ы/. Повар«иге, что можно получить решаощее рравшю с минимальной вероят- ностью ошибки, используя разделяющие функции й/(х), представляющие собой квадратичные функции компонент хр Попробуйте обобюнть результаты решения задач 14 н 16. 16.
Пусть х распределен так же, как в задаче 14, с=2, а И нечетно, пусть также рп=р > 1/2, 1=1, ры=1 — р, 1=1,, „<1, и Р (юг) = Р (а,) = 1/2, а) Покажите, что решающее правило по минимуму уровня ошибки прн этом имеет вид л принять решение в„если Ч»«1 хг > Л/2 Г=г б) Покажите, что минимальная вероятность ошибки определяется выражением щ- юл Р (г(, р)= Ь (й) р" (1 — р)л а о в) Чему равен предел Р,ОК, р) при р-+1/2? г) Покажите, что Р, Я, р) стремится к нулю при И-+со. (Вто трудно выпол.
нить без привлечения закона больших чисел. Вместе с тем важно почувствовать, почему это соотношение верно, н для тех, кто этим интересуется, но не располагает временем для самостоятельного вывода, мы рекомендуем кингу В. Феллера «Введение в теорию вероятностей и ее приложения» (М., «Мир», 1967, т. 1). Глава 3 ОЦЕНКА ПАРАМЕТРОВ И ОБУЧЕНИЕ С УЧИТЕЛЕМ 3.1. ОЦЕНКА ПАРАМЕТРОВ И ОБУЧЕНИЕ С УЧИТЕЛЕМ В гл. 2 рассматривались вопросы разработки оптимального классификатора в случае, когда известны априорные вероятности Р(оц) и плотности р(к~го~), условные по классу. К сожалению, на практике при распознавании образов полная вероятностная структура задачи в указанном смысле известна далеко не нсегда.
В типичном случае имеется лишь неопределенное общее представление об исследуемой ситуации и некоторый набор конетрунтливных выборок — конкретных представителей образов, цодлежащнх классификации '), Задача, следовательно, заключается в том, чтобы найти способ построения классификатора, используя эту информацию. Один из подходов к задаче заключается в ориентировочной оценке неизвестных вероятностей и плотностей по выборкам и последующем использовании полученных оценок, как если бы они были истинными значениями. Оценка априорных вероятностей в типичных задачах классификации образов не представляет большой трудности. Иначе обстоит дело с вопросом оценки условных по классу плотностей.
Имеющееся количество выборок всегда представляется слишком малым для их оценки, и если размерность вектора признаков х велика, то задача сильно усложняется. Трудность значительно уменьшится, если возможна параметрязация условных плотностей, исходя из общего представления о задаче, Допустим, например, что есть некоторые основания предположить, что р(х!тот) соответствует нормальному распределеншо со средним значением мг и ковариационной матрицей Хя хотя точные значения указанных величин неизвестны. Это упрощает задачу, сводя ее вместо определения функции р(х~сот) к оценке ларалгетров Иу и Ер Задача оценки параметров, относящаяся к классическим задачам математической статистики, может быть решена различными способами.
Мы рассмотрим два общепринятых способа — оценку ло максимуму правдоподобия и байесовскую оценку. Несмотря на х) В литературе но математической статистике выборка объема и соответствует набору п таких представителей. Считая каждый из представителей выборкой, мы следуем практике, принятой в технической литературе. Статистикам слепо.
зало бы каждую нз рассматриваеыых здесь выборок считать выборкой единичного объема. бб Гл. 3. Оценил паразмтров и обучение с рчипмлем то что результаты часто оказываются весьма близкими, подход к решению при применении этих способов принципиально различен. Прн использовании методов максимального правдоподобия значения параметров предполагаются фиксированными, но неизвестными.
Наилучшая оценка определяется как величина, при которой вероятность реально наблюдаемых выборок максимальна. При байесовских методах параметры рассматриваются как случайные переменные с некоторым априорно заданным распределением. Исходя из результатов наблюдений выборок, это распределение преобразуют в апостериорную плотность, используемую для уточнения имеющегося представления об истинных значениях параметров. Как мы увидим, в байесовском случае характерным следствием привлечения добавочных выборок является заострение формы функции апостериорной плотности, подъем ее вблизи истинных значений параметров.
Это явление принято называть байесовасилг обучением. Следует различать обучение с учителем и обучение без учшпеля. Предполагается, что в обоих случаях выборки х получаются посредством выбора состояния природы озг с вероятностью Р (а,), а затем независимого выбора х в соответствии с вероятностным законом )г(х)го)). Различие состоит в том, что при обучении с учителем известно состояние природы (индекс класса) для каждого значения, тогда как при обучении без учителя оно неизвестно.
Как и следовало ожидать, задача обучения без учителя значительно сложнее. В данной главе будет рассмотрен только случай обучения с учителем, рассмотрение же случая обучения без учителя отложим до гл. б. 3.2. ОЦЕНКА ПО МАКСИМУМУ ПРАВДОПОДОБИЯ 3,2ьК ОБЩАЯ ИДЕЯ МЕТОДА Предположим, что мы разбили множество выборок на классы, так что получено с классов выборок Ю„..., Х„причем выборки в каждом классе Я') получены независимо в соответствии с вероятностным законом р(х)гог).
Предполагается, что плотность р(х)го)) задана в известной параметрической форме и, следовательно, однозначно определяется вектором параметров 8). Мы могли, например, получить распределение )г(х)го)) Ж()зп Х>), в котором компоненты 8) составлены нз компонент )з) и Х). Чтобы явно выразить зависимость р(х)гог) от йп запишем р(х(ы)) в виде ") р(х)ыя 8)).
Задача состоит в использовании информации, получаемой из выборок, для удовлетворительной оценки векторов параметров 8„ ..., 8,. г) Некоторые авторы предпочитают запись вида р(к~юг, В.), так ках, строго говоря, обозначение р(х)мл ВГ) подразумевает, что Ву есть случайная переменная. Мы пренебрежем зтим различием в обозначениях и будем считать Ву обычным параметром при анализе по максимуму правдоподобия я случайной переменной прн байесовском анализе. З.З. Оценка по максимуму яраадояаообия 57 Для облегчения задачи предположим, что выборки, принадлежащие Я ь не содержат информации о Оь если (Ф/, т. е.
предполагается функциональная независимость параметров, принадлежащих разным классам '). Это дает возможность иметь дело с каждым классом в отдельности и упростить обозначения, исключив индексы принадлежности классу. В результате получается с отдельных задач, формулируемых следующим образом: яа основании множества Х независимо полученных выборок в соответствии с вероятностным законом р (х !0) оценить неизвестный параметрический вектор О.