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

Эффективная с точки зрения удобства вычислений методика описана Райзманом 2.18. Библиоарифичаские и исшорические саедеяил 49 и Эрихом (1971), указавшими на ряд работ по учету контекста в распознавании. Заметим в заключение, что в части ! данной книги везде молчаливо подразумевается, что до того, как принимается решение, производится измерение всех г[ компонент вектора признаков. Возможен и другой способ, с использованием дерева решений, при котором оценка признаков производится последовательно вплоть до момента, когда решение становится возможным. Статистический анализ такого подхода требует учета цены измерения признаков и цен получаемых ошибок и составляет предмет теории последовательного анализа (Вальд, 1947; Фу, 1968).

Слейгл и Ли (1971) показали, как к задачам такого вида применять методы, разработанные для исследования деревьев в теории игр. СПИСОК ЛИТЕРАТУРЫ Абсид (АЬепд К.) Сошроипд дес1яоп ргоседигез 1ог рацегп гесодп(1юп, Рпк. !УЕС, 22, 777 — 780 (1966). Абенд (АЬепд К.) Сошроипд бес!зюп ргоседигез 1ог ипйповгп дЫг(Ьи1(опз апб (ог дерепдеп1 з(а1ев о1 па1иге, 1п Рацегп Песохп!!!оп, рр, 207 — 249, Ь. Капа!, еб. (ТЬошрзоп Воо1г Со„%азыпа!оп, О. С., 1968). Абенд, Харлн н Кенал (АЬепб К., Наг1еу Т. 3., Кала! Ь.

ЬЬ) С!аззи!сапоп о1 Ь[пагу гапбош рамегпз, IЕЕЕ Тгалв. (л[о. Тйеогу, 1Т-11, 538 — 544 (Ос1оЬег 1965). Альбрехт н Вернер (А1Ьгесш П„%егпег %.) Еггог апа!узм о( а Ма1Ы!са! <(ес(в!оп ше(Ьоб, 1ЕЕЕ Тгалв. (л[о. Тйеагу,!Т-10, 34 — 38 ()апиагу 1964). Андерсон (Апдегзоп Т. %.) Ап 1п(гобисиоп (о Миц!чаг!а1е Яа1Ы!са! Апа!уз!з (уоЬп %Пеу, Нечг Тогй, 1958). Андерсон н Бахадур (Апдегзоп Т. %., Ваьадиг )1.

и.) С!аеипса1!оп !п(о (чго пшшчаиа(е поппа! дЫИЬипопз вчНЬ би(егеп! сочамапсе ша1г[сез, Алл. Мани 51ат., ЗЗ, 422-431 (зине 1962). Блекуэлл н Гнршнк (В1асйвчеп О., О!гзсысй М. А.) ТЬеогу о1 Оашев апб Яа11з1!са! Оес1ыопв (уоьп %Пеу, Нечг Уогй, 1954). [Русский перевод: Теория нгр н статистических решейкй, М., ИЛ, 1958.1 Вальд (%а14 А.) Соп(НЬипопз 1о 1Ье 1Ьеогу о1 в(а!!в(!са! езишапоп апд 1ез1!пб о[ Ьуро(йевез, Алл. Ма(Л. Бгат., 10, 299 — 326 (!939).

Вельд (%а!д А.) бейиеп1!а! Апа!уяв (доьп %неу, Ненг Уогй, 1947). Вальд (%а!д А.) Яа1Ы[са1 ОесЫоп Рипс(!опв (3оьп %неу, [4егч Уогк, 1950). Казннрчах н Штейнбух (Кагш!егсхай Н., Яе!пЬисЬ К.) Абер!!че зув1ешз !и рацегп гесойп11!ой, !ЕЕЕ Тгалз. ол Е!ес. Совр., ЕС-12, 822 — 835 (ОесетЬег 1963). Купер (Соорег Р. %.) Нурегр!апев, ЬурегзрЬегез, апб Ьурегйиаймсз ав беси(оп Ьоипбапев, !п Сошри1ег апб 1п1оппа(юп зс!епсез, рр. 1!1 — 138, 1. Т. Тои апб и. Н.

%псох, едз. (5раг(ап, %авЬ!иб(оп, О, С., 1964!. Гл. 2. Байвсовагая лмория решений Лейинотис и Парк (Ьа!п!ойь О. О., Раг1| 5. К.) РгобаЫРИу о! еггог Ьоццбь, !ЕЕЕ Тгалт Ерв. Мал Суб., 5МС-1, 175 — !78 (Аргй 1971). Льюс н Райфа (Сисе (!. О., [!ай!а Н.) Оапаз апд Оес!ьюпь (ЛоЬп %Иву, Неьч Уог1|, !957). [Русский перевод: Игры и решения, М., ИЛ, 1961.[ Минский (М!паду М.) Яерв (оыагд аг(|йс!а! ш1ей!депсе, Рте, ЛВЕ, 49, 8 — 30 (Лапцагу 1961). Мерилл н Грин (Маг!И Т., Огсеп О.

М.) Яайз!!са! гесодпгйоп !цпсйопь апд 1Ье дейдп о! райегп гесодц!ьегь, ?Л!Е Тгалв. Е?вс. Сотр., ЕС-9, 472 — 477 (ОесегпЬег 1960). Нейман и Пирсон (Неутап Л., Реагвоп Е. 5.) Оп !Ье цзе апд !п(егрге!а1|оп о( сег!а|п 1ез! сгйепа !ог рцгромз о[ з1а(нй!са! 1п!егепсе, В!оте|пга, 20А, 175 — 240 (!928). Нейман н Пирсон (Хеутап Л., Реагвоп Е. 5.) Оп 1Ье ргоЫет о! 1Ье гпо|1 ейй с|ел! 1евй о! йаИзйса! Ьуро!Ьеьы, РМЙ. Тгалв. Л?оуа! Еос.

Еолг(ол, 231, 289 — 337 (1933). фои Нейман и Моргенштерн (чоп Хецтапп Л., Могдепз(егп 0.) ТЬеогу о! Оатез апд Есопот!с Вейаиог (Рппсе1оп (Лп!чегвйу Ргеы, Рппсе!оп Х. Л., Гйг|1 Ебй!оп, !944). [Русский перевод: Теория игр й зкономическое поведение, М., |Науками, !970.[ Нильсон (Нйыоп Х. Л.) Ьеагпшд МасЫпев (МсОгаьч-НИ1, Хе» Уог1|, 1965). [Русский перевод: Обучающиеся машины, М., |Мир|, 1967.[ Ранив (йач!ч Л|) Оес[йоп таЫпд !п Магйоч сЬа[ па аррйеб !о 1Ье ргоЫет о! райегп гесодпйюп, !ЕЕЕ Тгалв. Лл?о. Т?ногу, 1Т-13, 536 — 55! (Ос1оЬег 1967).

Райзман и Эрих (И!ытап Е. М., ЕЬпсЬ [[. %.) Соп(ех1ца[»югд гесодпйюп цз!пд Ыпагу б!дгапм, ?ЕЕЕ Тгалв. Сотр., С-20, 397 — 403 (Арп[ 1971). Слейгл и Лн (51ад!е Л. И., Ьее И, С. Т.) АррИса1юпв о! дате (гее ыагсЬ|пд 1есбп!9цеь 1о ьейцепйа! райегп гесодт1юп, Сот. АСМ, !4, !03 — 110 (РеЬгцагу !971). Уиндер (!У!паев [[. 0.) ТЬгеьбо!б !од!с |п агйй!с!а! !п1е1Идепсе, Агйй!с!а! 1п1е1Идепсе, ?ЕЕЕ арве(а[ Риейсадол, 8-142, Р37 — 128 (Лапцагу !963).

Фергюсои (Регби|оп Т. 5.) Майпеп|айса! Яайзйсы А Оесйюп ТЬеогейс АрргоасЬ (Асабет!с Ргеы, Хе»г Уог1|, 1967). Фишер (Р!зЬег И. А.) ТЬе цзе о1 тцИ!р!е теаыгетепй !п 1вхопоппс ргоЫетз, Алл. Еиде|исв, 7, РагС П, 1?9 — 188 (1936); айо!п Соп1пЬцйопз 1о Ма1Ьета1!са! Яа(йй!сь (Лобй %йеу, Хе»г Уогй, 1950). Фу (Рц К. 5.) бег[цепйа! МеИюдз !и Райегп Иесодп|йоп апд МасЫпе 1.еагп1пд (Асабет!с Ргеы, Не»г Уог1|, !968). Ча я Чуи (СЬц Л.

Т., СЬцеЬ Л. С.) Епог ргоЬаЬ|1йу |и бесйюп !цпсйопь 1ог сЬагас1ег гесодпйюп, Л. АСМ, 14, 273 — 280 (Аргй 1967). Чернов и Мозес (СЬегпой Н., Мове| Ь. Е,) Е1е|пеп1агу Оес!топ ТЬеогу (Лоби йгйеу, Ь[егч Уогй, 1959). Чоу (СЬтч С. К.) Ап орйттп сЬагас(ег гесодпй!оп ьуйет цыпд бес!ь!оп !цпс1юпь, ИЕ Тгалв. ол Е!ес. Сотр., ЕС-6, 247 — 254 (ОесетЬег 1957). 51 Задачи Чоу (Сйочг С. К.) 51а1!з!!са! !пберепбепсе апб 1пгшпо!б 1ппс!!опэ, /ЕЕЕ Тгалэ. ол Сош., ЕС-14, 66 — 68 (РеЬгнагу 1965). Чоу (С)ючг С К ) Оп ор(ппшп гесойш!1оп еггог апб ге!ес! 1габео!1, /ЕЕЕ Тгапэ. /и/о. ТЬеогу, 1Т-10, 4! — 46 ()аппагу !970). Задача 1. Пусть условные плотности для одномерной задачи и двух классов заданы распределеынем Коши: р(х)ап)= э ! 1 2.

1 ! ' "' '+(" ")'' Считая, что Р(ыгг=р(юэ), покажите, что Р(ыг!х)=Р(ыэ)х) при х= (1/2) (а,+а ). Набросайте график Р(в,!х) для случая аз=3, аз=5, Ь=1. Как ведет себя Р(ыг!х) при хч — со?+со! 2. Используя условные плотности из задачи 1 и полагая априорные вероятнасти равными, покажите, что минимальная вероятность ошибки определяется выражением 1 1 !а,— ат Р (ошибка) = — — — с12 ~ 2 и ~ 2Ь Рассмотрите это выражение как функцию величины ! (аэ — а,)/Ь!. 3. Рассмотрите следующее решающее правило для одномерной задачи и двух классов: принимать решение ыэ в случае, если х)0; в противном случае прннимать решение юз.

Покажите, что прн использований этого правила вероятность ошибки определяется выражением Р(ошибка)=Р(ю,) ~ р(х) ю,) Лх+Р(ыэ) ~ р(х! ыэ) Лх. Покажите посредством дифференцирования, что дли получения наименьшего значения Р (ошибка) необходымо, чтобы величина 0 удовлетворяла выражению р(0) ы,) Р (ыд=р(0! ыэ) Р(юэ). Проверьте, однозначно ли определиется этим выражением величина 0.

Приведите пример, когда веЛичина О, удовлетворяющая данному уравнению, на самом деле соответствует максимальной вероятности ошибки. 4. Пусть оз~„,(х) есть состояние природы, для которого Р(ымз„~х)>Р(ы/!х) для любого !, !=1, „с, Покажите, что Р(ыщ,з)х)~!/с. Покажите также, что в случае йринятия решения по правилу минимального уровня ошибкы средняя вероятность ошибки определяется выражением Р(ошибка)=1 — ~ Р(ышэ„(х) р(х) Ых. На основанян полученных результатов покажите, что Р (ошибка)~(с — 1)/с.

Опишите случай, при кагором Р(ошибка)=(с — 1)/с: Гл. 2. Байссоеская теория решений б. Для неотрицательных чисел а и Ь покажите, что ш[п(а, Ь)~Р' аЬ, На основании этого покажите, что для байесовского классификатора на два класса уровень ошнбни должен удовлетворять требованию 1 Р ь..б..)н ГЗ ь !Р!н!~ 2 г де р — так называемый ксм[ирициснт Бкаттачария, равный р = ~ [р (х [ в,) р (х [ вз) [г~з йх. 8, Во многих задачах классифяхацнн образов допускается выбор: нли отнести данный образ к одному из с классов, илн отказаться принять решение.

Такой отказ вполне допустим, если он не обходится слишком дорого. Пусть О, ! = 1; г, 1 = 1, ..., с, )Г(а! [ВГ) =- дг, !=С+1, к в остальных случаях, где Хг — потери, возникающие из-за выбора (с+1)-го действия, состоявшего в отказе от принятия решения, а Д вЂ” потери из-за ошибки, связанной с подменой класса. Покажите, что минимальйый риск достигается, если принять решение в! в случае Р(в![х)~Р(ву[х) дли всех 1 и в случае Р(вг[х)=.1 — Х,lйв с отбрасыва- нием прочих решений. Что произойдет в случае Хе=О? Что произойдет в случае Хг>Х,? 7. Пользуясь результатами, полученными при решении задачи 6, покажите, что следующие разделяющие функции оптимальны: р(х [в;) Р (в!), 1=-1,,, с, с г ~ р (х [ вг) Р (вг), 1= с+ 1.

з 1, Изобразите эти разделяющие функции н области решений для одномерного случая и двух классов при р(к[в!)-Д!(1. 1) р(к[вг)-??( — 1 1) Р(в!)=Р(вз)=-1/2 и ХгА,=!/4. Опишите качественно, что произойдет прн возрастании )г,/Лз от О до 1. 8. Предположим, что детерминированную решающую функцию а (х) мы заменим ранйоминизированным нрааи.юм, т. е. вероятностью Р(аг[х) принятия действия аг прн наблюдаемом значении х, Покажите, что риск в этом случае определяется выражением г-[[2 я! ~ )~!и !]~! !н. [ г=! Покажите, кроме того, что )? можно минимизировать, выбирая Р(аг!х)=.1 дчя действия ап связанного с наименьшим условным риском )?(вц[х), т. е.