Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 20
Текст из файла (страница 20)
Поэтому при данном. векторе Г можно выбрать коэффициенты И~ из условия де~/дИ" = О, где градиент де~/дИ" имеет вид (4.80): И'= (1/Ж) бТ, (4.85) или и" (~+1) — (1/л) ст(~+1) — (1/л) (пгд+ рцлг(/)) — и'(~) + (р/ж) олгаз.
(4.86) При заданном Г (1 + 1) оценка И'(1 + 1) минимизирует на этом итеративном шаге среднеквадратичную ошибку е'. Для доказательства сходимости процедуры оптимизации (4.84)' и (4.86) исследуем норму вектора С, который используется при коррекции векторов Г и И". Из выражений (4.83) и (4.79) следует, что !!СР = 0-»- Ут И" = Г-»- е' = О. (4.87) При увеличении номера шага 1 приращение величины !!С(1) Р можно вычислить путем подстановки выражений (4.84) и (4.86) в (4.83).
В результате получим !!с(7+ 1) !! — !!с (е) Р = — 2рс'(У) [1 — (Очи/и) ~ лГ (~) + р~ЛГ'(Е) [1 — (О'Й7/ЦДЛГ(Е). (4.88) С другой стороны, из выражений (4.83), (4.85) и (4.78) имеем Ст~тту (Итти Гт) рту (уИтт Гтут) у 0 (4 89~ 2С'ЛГ = [(С+ !С!)'+ (С вЂ” !С!)') (С+ !С!) =, = (С+ !С!)'(С+ !С!) = ЛГ'ЛГ. (4.90) Поэтол1у выражение (4.88) можно упростить следующим обраЗОЛ1: !!с(г+1) !! — !!с(г) !! = — лг (г) [р'(ги/ж) + (р — р')11лгд= — [р'(!!~/лг(~) !!2//~) + (р — р ) !!лг(/) !!23 О О < р (1 (4.91) Равенство выполняется только при условии, что !!ЛГ!!2=0.
Таким образол1, при увеличении шага 1 величина !!С(7) !!2 монотонно уменьшается до тех пор, пока !!лГР не станет равнылг нулю. с другой стороны, !!лГР мон1ет обратиться в нуль только лири условии, что !! СР 0 или С = — ! С ! . Теперь покажем, что для линейно разделимых классов случай С = — ! С ! никогда не имеет места. Равенство С = — ! С ~ означает, что РИ" < Г, '(4.92) где знак ( показывает, что это неравенство выполняется для всех компонент этих векторов. Предполагая линейную разделимость, имеем '(4.93) У'И" ) О. Поэтому можно найти некоторую константу а ~ 1 такую, что ГИ'< Г(аИ") ( Г. (4.94) Это противоречит тому, что при данном векторе Г коэффициенты В' выбраны из условия минимума среднеквадратичной ошибки е2 вида (4.79).
Таким образом, равенство (4.91) выполняется только при условии, что !!С!!2 = О, т. е. !!С(7) Р на каждом шаге 1 монотонно уменьшается до тех пор, пока !!С!!2 не станет равным нулю. Это завершает доказательство сходимости рекуррентной процедуры для случая линейной разделимости классов. В случае линейной неразделимости классов условие (4.93) и, следовательно, (4.94) не выполняется. Поэтому нельзя распространить доказательство сходимости на этот случай.
Можно только утверждать, что процедура оптимизации сопдется, если на некотором шаге будет выполнено !!СР = 0 или С = — !С~. ~ 4.5. Другие разделяющие функции 11езависимые бинарные входы. Если переменные независимы, то для классов ел1 и ел2 плотности вероятности входного случайного вектора Х определяются ВьтражЕНИЕМ р(х/,) — П р(,/,).
(4.95) Поскольку х; — бинарные случайные величины, то плотность ве- 4.5.1. Линейные разделяющие функции для бинарных входов. Часто в задачах распознавания образов входные величины принимают значения +1 или =1. Поскольку бинарные входные величины можно рассматривать как частный случай общего вида входных величин, то все предыдущие результаты остаются в силе и для бинарных входов.
Однако бинарные входные величины обладают некоторыми характернымп свойствами, которые упрощают рассмотрение определенных вопросов. В .этом параграфе будут рассмотрены те свойства, которые относятся к линейныл1 разделяющим функциям. 120 121 ,'(4.96) Таблица 4.1 где Возможные бинарные входы Х4 Х4 Хв Хо й (х) 1=1 2 1п И + 1 1п 1 21 2 1 Р21 1 — 1 — 1 1 — 1 — 1 1 1 — 1 1 1 — 1 1 — 1 1 1 — 1 — 1 — 1 ХО Х1 Г Х8 ~~1(1 ~21) 11 + ~ 1 ' 1'14 Р~8 ) (4.98) 2( 2) ХЗ 1 1 1 1 1 — 1 Х1Х8 Х1 ХЗ Хг 1'8 Х1хаХ8 2п — 1 (4.99) (4.100) (4.101) 1 1 ... 1 Х)) Х1 ° ° Х 2" — 1 (4.102) 244 ЦЦт — 2и,~ (4.103) трех бинарных (4.99) — (4.103) (4.107) ГЛ. 4.
ЛИНЕЙНЫЕ КЛАССИФИКАТОРЫ роятности р(х;/о1) дискретных переменных можно заменить на вероятность следующим образом: Рг(х; = х,/о)) = Р;; ' (1 — Р„) Р;; = Рг(х, = 1/о)). (4.97) Вместо условного отношения правдоподобия р(Х/4о1)/р(Х/ ) вычислим выражение й(Х) = — 1Н~Рг(Х Х/4о1)/Рг(Х вЂ” Х/,)1. которое является линейной функцией относительно х,.
Поэтому в случае бинарных, независимых входных величин байесовский классификатор является линейным. Зависимые бинарные пере- менные будут рассмотрены в следующей главе. Ортонормированность входных величин. Если имеется и бинарных входных величин, образующих входной вектор Х, то число возможных входов (Хо, ..., Х21 1) равно 2". Компоненты х,), 1 = 1, 2, ..., и вектора Х1 удовлетворяют условиям (1/2") ~ х,, = 0„ 1=о 2П вЂ” 1 (1/2") '~', х2, = 1„ 1=о 2п — 1 (1/2") ~ х1,х;„= 0„ 1=о Если определить выборочную матрицу как то векторы-строки этой матрицы будут взаимно ортонормирова- ны, т. е. Пример 4.4.
В табл. 4.1 приведен пример входных величин. Легко видеть, что условия выполняются. а 4,5, ДРУГИЕ РАЗДЕЛЯ1ОЩИЕ ФУНКЦИИ Пусть 1(Х,) — требуемый выход системы распознавания образов при данном входе Х,, причем 1(Х,) — не обязательно двоичные числа. Одна из возможностей реализации в этой системе д гяющеи функции сОстОит в минимизаЦ1п1 сред еквадрат чной ошибки между 1(Х)) и Г'Х)+ го.
Среднеквад;,и н „шибку можно записать следу1ощпм образом: 2чъ е2 = (1/2") Х 17(Х,) — (ГХя+ Го)Г= 1=о (1/2-) ~и"ц — г') (и'и" — г), (4.1 '4) Где векторы И' и à — те же самые, что и в (4.45)'. Коэффициенты И", минимизирующие среднеквадратичную ошибку е2, будут равны ,де2/дИ' = (2/2") У(У'И" — Г) = 2~ И" — (1/2") УГ1 = 0 (4 105) И" = (1/2") 1/Г. (4.106) Так11м образом, коэффициенты линейной разделяющей функц11и определяются через коэффициент корреляции между требуемыми выходамп и входными величинами Х,. Этот вывод совпадает с выводом, сделанным ранее для обычных линейных разделяющих функций.
Следует, однако, заметить, что для бипарных входных величин условие 4'.) 4'.)' = 1Ч1 выполняется без дополнительного преобразования автоматически. В качестве примера величины 1(Х,) рассмотрим 1(Х,) = р(Х,) (Р(о1/Х,) — Р(4о2/Х1)) = Р ( 4о 1 ) р ( Х)/О 1 ) — Р ( О 2 ) р ( Х) / 0) 2 ) . 122 12З ~,7/~,тlт 2ггу '(4.110) б) Гл. 4. лпнеиные кллссиФиклтоРы Выражение 1(Х;) будет положительным для Р (со() р (Х,/10,) ) ) Р(сог) р(Х(/сог) или Р(со(/Х,) ) Р(402/Х;) и отрицательным в противном случае.
Кроме того, абсолютное значение 1(Х,) зависит от условных плотностей вероятности р(Х,/ю() и р(Х~/сог). При большом и и числе наблюдаемых объектов Л, значительно меньшим 2", р(Х;/401) и р(Х;/сог) отличны от нуля только для наблюдаемого вектора Х;. Поэтому для вычисления коэффициента корреляции, определяемого по формуле (4.106), требуетси вместо 2" только Х умножений и сложений [Фукунага, 1965]. Можно расширить вектор Х; = [хн...х,„1' до вектора У, =(1 х;г ...
х; (х;гх;гг .. (х;гхгг ... х;„г(: (4.10(» г" Тогда выборочпая матрпца для этого расширенного вектора становится квадратной матрицей ° — [~о У, ~г.,1)' (4.109) ггг Векторы-строки г(' янлятотся ортонормированными вектораьш, так что Линейная разделяющая функция для У имеет вид гп г1 и1,у; = и10+ ~ и1,х(+ ~ ~~ и),х,х;+ ... + и1, „,х,... х„. 1=0 г — ( 1 1 (4.111~ Аналогично тому, как была получена формула (4.106)', можно определить коэффициенты И~ разделяющей функции (4.111) И1 = (1/2") У'Г. (4.112) Здесь следует заметить следующее: 1) лгобой требуемый выход можно без ошибки выразить формулой И~'У; 2) поскольку значения у, взаимно ортонормированы, то среднеквадратичная ошибка ег вследствие искл|очения члена и~(у( из выражения И~'У равна (41(, 3)' среднеквадратичная ошибка ег, определяемая линейной разделяющей функцией У'Х+ ио, равна г" — 1 ег = ~ и1;.
(4 113у 3= +1 4.5.2. Кусочно-линейные разделяющие функции. Линейные: разделяющие функции находят широкое применение в задачах ф 4,5. ДРУГИЕ РАЗДЕЛЯЮЩИЕ ФУНКЦИИ распознавания образов для случая двух классов, хотя при этом неизбежна некоторая потеря качества распознавания. Однако при трех или большем числе классов качество распознавания с использованием линейной разделяющей функции часто оказывается неприемлемым. Это может произойти и при двух классах, если каждый класс состоит из нескольких групп объектов.
Если в этих случаях воспользоваться совокупностью линейных разделяющих функций, т. е. кусочно-линейной разделяюи~ей функцией, то появляются дополнительные возможности улучшения качества распознавания. На рис. 4.11 изображен пример задачи распознавания при наличии четырех классов. Рнс. 4.11. '1етыре распределения: а) байесовский классификатор; б) кусоч- но-линейный классифи(;атер, В задачах со многими классами критерин проверки многих гипотез дают наилучшее в байесовском смысле решающее правило, обеспечивающее минимум риска пли вероятности ошибки В соответствии с критерием проверки гипотез плотность вероятности каждого класса или ее логарифм следует сравнить с плотностями вероятности других классов, как следует из (3.114).
П а рис. 4.11, а изображены полученные таким образом границы. Если оценпвание плотностей вероятности является слишком сложной задачей пли границы, определяемые в соответствии с критерием проверки гипотез, достаточно «вычурные», то можно заменить этп сложные границы множеством простых линейных |раниц. Такая замена, конечно, приводит к некоторому ухудшенпю качества распознавания. Однако использование линейных границ особенно эффективно для задач распознавания многих классов, т. е. в тех случаях, когда сложность границ быстро .возрастает с увеличением числа классов, и является желатель- 12Ь 124 51 зт4~и) ,? $ю в,„,4'шииюр Гл. 4.
линейные кллссиФиклтоРы ным некоторое упрощение процедуры синтеза классификатора Например, на рис. 411, б показана замена байесовских грани(т, (рис. 4.11, а) кусочно-линейными границами. Множество линейных функций, соответствующее кусочно-линейной разделя1ощей функции, определяется следующим образом: Ь11(Х) = У';,Х+ иапо, 1, 1 = 1, 2, ..., М, 1~/, (4.114) где М вЂ” число классов. Знаки 1т(; выбираются так, чтобы распределение класса 1 находилось в области положительных значений линейной функции Ьн(Х), а распределение класса 1 — в области отрицательных значений.
Из этого требования следует,- что Ь„(Х) = — Ь;,.(Х). (4 115) Предположим, что для каждого класса соответствующая область является выпуклой, как изображено на рис. 4.11, б. Тогда область класса 1 может быть просто определена следующим образом: Ь(1(Х) ) О, ..., Ь!м(Х) ) О-з-Х~ о)1 (4.116)' (функция Ьн(Х) исключена из рассмотрения). Наличие заштрихованной области на рис. 4.11, б показывает, что М областей, Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
