Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 28
Текст из файла (страница 28)
теор предыдущему выводу относительно того, что величина га.,„уменьшается очень быстро при увеличении числа объектов обучающей выборки. Так как величина г.к„оценивалась по выборке из 400 объектов каждого класса, то основной вклад в г„,„для выборок среднего и большого объема в действительности вносят результаты экзамена, а не обучения.
Хайлиман показал, что если задача состоит в синтезе классификатора, обеспечивающего минимум дисперсии несмещенной оценки ео,'то для ее решения требуется обучающая выборка относительно небольшого объема по сравнению с экзаменационной (Хайлиман, 19621. Его метод годится для любых плотностеп вероятности, но при весьма жестких ограничениях на вид оценки вероятности ошибки. Г„(~) (5.157) шах Р ((о,) р (Х/(о;)((1 — ~) р (Х) -+ Х я Г (~)' 1=1,2,..., ЛХ, где р(Х) — плотность вероятности смеси, а ~ — критическии уровень, 0 ( ~ ( 1.
Условие (5.157) устанавливает, что если для данного объекта Х значения Р((о;) р(Х/(о(), вычисленные для каждого класса Л1(, не превышают величины (1 — ~) р(Х), то объект Х не классифицируют вообще; в противном случае объект Х классифицируют и относят его к 1-му классу. Таким образом, вся область значений Х делится на критическую область Г,(~) и допустимую область Г (~), причем размеры обеих областей явля1отся функциями критического уровня 1. Прп таком решающем правиле вероятность ошибки е (~), коэффициент отклонения г(1) и коэ4фициент правильного распозн(;- вания с(1) будут равны с (С( = ( таа Р (и;) р (Х(и,( с(Х, (5. 153) г„'(о с(С(= ( р(Х)с(Х (5 159) Г'Г(О е(1) = 1 — с(1) — г(~).
(5.160) Предположим, что область отклонения увеличивается на ЛГ,(~) за счет изменения значения ~ на ~ — Л~. Тогда те Х, которые раньше распознавались правильно, теперь отклоняются: (1 — ' ~)р(Х) < шах Р(о),) р(Х/о)() < ( (1 — 1+К|) р(Х) при Х~ЛГ,(~). (5.161) Исключение задания класса для объектов экзаменационной выборки. Для того чтобы оценить вероятность ошибки как при обучении, так и на экзамене, требуются выборки объектов, в которых известно, какой объект к какому конкретному классу принадлежит. Однако в некоторых случаях получение такой информации связапо с большими затратами. Рассмотрим метод оценки вероятности Ошибки, не требующий информации о принадлежности объектов экзаменационной выборки к конкретному классу (Чоу, 1970].
Применение этого метода наиболее эффективно в случае, когда при оптимальном разбиении выборки на обучающую и экзаменационную, число рбъектов и экзаменационной выборке больше, чем в обучающей. Введем критическую область для задач классификации И классов: ГЛ. 5. ОЦЕНИВАНИЕ ПАРАМЕТРОВ $ 5.»!. ОЦЕНИВАНИЕ ВЕРОЯТНОСТИ ОШИБКИ Интегрируя (5.161) в пределах области ЛГ, (~), получим (1 — ~)Лг(~) < — Лс(~) ( (1 — ~+ М)Лг(~), (5.162) где Лг(») и Лс(»,) — приращения г(»,) и с(»), вызванные изменением ~.
Из формулы (5.160) следует, что неравенство (5.162) можно переписать следующим образом: — Иг(~) ( Ле (») < — (» — Л~) Лг(~) . (5.163) Суммируя по всем дискретным значениям ~ от 0 до ~, получим — ХИг(~) < е (~) < — Х(~ — Л~) ЬгЯ. (5.164) Полагая М-)-0, получаем интеграл Стилтьеса о к»») = — ~ »нг»»)= ) гФ»»). (5.165) »=о Уравнение (5.165) показывает, что вероятность ошибки е(~) может быть вычислена после того, как известна зависимость между значениями ~ и г(~).
Из решающего правила (5.157) следует, что при ~ = 1 — 1/М область отклонения отсутствует, так что байесовская ошибка ее —— = е(1 — 1/М). Кроме того, из формулы (5.165) можно устар) повить взаимосвязь между вероятностью ошибки и коэффи»»иентом отклонения, так как изменение вероятности ошибки можно вычислить как функцию от изменения коэффициента отклонения. Воспользуемся выражением (5.165) для исключения зада- Р!»с.
5.4. приращен!!е областей от- нпя класса объектов экзамена- !»яовеввя. ционной выборки. Для этого а) Аг <~")' б) Аг ц~ »)»о)' поступим следующим образом. ,) АГ, »! » — 2) »,). 1. Для определения ЛГ,(Ио) при ~ = Ио, й=О, 1, ..., т= = (1 — 1/М)~о, где ~о — дискретный шаг переменной ~, будем использовать относительно дорогостоящие классифицируемые объекты.
Это показано на рис. 5.4. 2. Подсчитаем число неклассифицированных объектов экзаменационной выборки, которые попали в область ЛГ„(~с~о) разделим это число на общее число объектов и обозначим полученное отношение через Лг(Ио). 3. Тогда из выражения (5.165) следует, что оценка вероятности ошибки о е (т Ео) = ~~ (Усто) Лг (И ). (5.166) 5.4.4. Метод исключения одного объекта в случае нормальных распределений. В этом разделе мы рассмотрим простую реализацию метода исключения одного объекта в случае нормальных распределений, когда удается устранить вычисление 1)»' байесовских классификаторов ~Фукунага, 1971 в1.
Для нормальных распределений байесовский классификатор определяют выражением 1г(Х, 0) = —, (Х вЂ” ЛХ,) Х» (Х вЂ” и,) — —, (Х вЂ” ЛХ,) Х2 х ~ (Х вЂ” ЛХ,)+ 1п(~~,и~ ~) — 1п(Р(~,)~'(»о2)) О Х = (5.167) где»:» — вектор параметров ЛХ1, ЛХ2, Х1, Х2, Р(о)!)' и р(„,) Пуст~ 6. = (М;, Х», Р(о)»), 1 =* 1, 2) — вектор оценок параметров вычисленных по имеющимся У объ) ектам, и пусть»')))»' » = 1ЛХ!)„Х;А» Р),(о)»), 1 = 1, 2) — вектов оценок параметров, вычисленных по»Х — 1 объектам, оставшимся после исключения объекта Х)). Предположим, что исходная выборка пз Л»' независимых объектов содержит У1 объектов класса о)! и 1))2 объектов класса о)2.
Тогда справедливы соотношения: ЛХ, 1 Х. » 1=! (5.168) »)!» лх»„= ~, х, — х„= и; — (х, — и!), (5 160) .»=-1 В описанной процедуре использовалось то, что коэффициент отклонения является функцией от плотности вероятности смеси, а не от плотностей вероятности отдельных классов. Поэтому после того, как по классифицированным объектам найдены расширенные области отклонения, в дальнейшем для оценивания Лг(~) и вероятности ошибки е(~) нет необходимости использовать классифицированные объекты. Гл. 5. Оценивлние плРлметРОВ % 5,4, Оцее1иВлнпе веРоятности Ошиеки ~ (х, м,.)(х, — м,)', (5.170) Ю1 ;~ (х,— м;„)(х,— м,,)*~ — (х.
— м;,) ~ ,)=1 Л' — 2 1 '+ Ю вЂ” 2 ~ (Х, — Л~1л)' х (х„— лх;)(х„— м;)'), (5.171) (5.172) где Е [Х1, А (Х,)1 = ( л 2 ЗМ. + 1) 22,. (Х,) ~Р, — 1) + М,."14 (Х„) 2 (Л/. — 1)2 — У.сК~ (Х ) ю +1п у 1 + 2 1пу 2) 02 (,1 1)2-"г ( )) 3' Х + —,1п 1 (5.176) (5.177) Ж(Х,) = (Х, — ЛХ;)'2, '(Х, — М;).
У Р (а;) = —. У,— 3 - Уу Р (а) и Р~(а) (5.173) при Хл~а, и Х~фа;. Согласно (5.167) для того, чтобы применить метод исключения одного объекта, нужно вычислить Ь(Х, Е ' ) — (Х вЂ” ЛХ ) Х (Х вЂ” ЛХ ) (Х И) Х (Х И.) ~- 1п[~Х И~ ~) — 1п ~Р„(а,)/Р,(а2)~ при Х5 ~ а,. (5. 174) Подобное выражение может быть получено и для Х~~ о)2. В приложении 5.1 с помощью формул (5.168) — (5.173) получено соотношение (5.175), где Ь(Х„О~) является оценкоп отношения правдоподобия, полученной С-методом: + Д [Х1, 31 (Хь)1 при Х ~ о)„, Ь (Х51 6Л, 1) Ь (Х„, ОЛ й ~Х2 д2 (Х5)1 при Х ~..- о), (5. 175) По выражениям (5.175) — (5.177) можно сделать следующие замечания: 1.
Когда для определения вероятности ошибки используется 2 С-метод, то Ь(Хх 0~) и 4 (Хх), 1 = 1, 2, должны быть вычислены прп Ь = 1, 2, ..., Х Вычисление скалярной функции (5.176) для вычислительной машины является незначительной дополнительной нагрузкой по сравнению с вычислением Ь(Х, Ом) для каждого Ь. Таким образом, суммарное время вычислений С-метода и метода исключения одного объекта становится почти эквивалентным времени вычислений только по С-методу. Напомним, что в С-методе требовалось синтезировать только один классификатор.
2. Как показано в приложении 5.1, величина д( ), определенная по формуле (5.176), всегда положительна независимо от того, каковы значения )х~, д;(Хх) и и. Поэтому из (5.175) следует, что 2 Ь (Х, 0~~~~ 1) ) Ь (Х5, Ол~) при Х5 ~ а, (5.178) ЬЖ, Ол — )) ( Ь(Хь 6 ) прп Х„~ о)2. (5.179) Анализируя решающее правило (5.167), можно сделать вывод, что а) если объект Х~ неправильно классифпцирован С-методом, то он так)ке будет неправильно классифицирован методом исключения одного объекта, б) могут быть некоторые объекты Х~, которые правильно классифицированы С-методом, но неправильно — методом исключения одного объекта. Этот вывод для нормальных распределений является более сильным утверждением, чем неравенство (5.140), так как это неравенство справедиво только для математических ожиданий вероятности ошибки, в то время как вышеприведенное утверждение справедлнво для отдельных объектов экзаменационной выборки.
2 3. Прп Х;)) 1 и А (Х~)/Х (( 1 можно получить простейшую аппрокспмацшо выражения (5.176) в виде д [Хь 32 (Х,)1 = —,' Ж (Х,)!Х .. (5.180) Прим е р 5.8. С-метод и метод исключения одного объекта проверялись с помощью стандартных данных 1= 1, 2, имевших нормальное распределение. Размеры выборок при этом были соответственно равны ~'1 = )х2 = 12, 50, 100, 200 и 400 для каждого класса. В каждом эксперименте генерировалась выборка данных, вычислялись векторы выборочного среднего и ковариационные матрицы М~ и Хь Для вычисления оценок вероятностей ошибки Гл. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
