Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 36
Текст из файла (страница 36)
сокращенной обучпюц1ей последовательностью. Поскольку исключенные объекты Я не влияют на Ит, их исключение не влияет на доказательство сходимости. Кроме того, предположим, что с = 1. Это предположение не уменьшает общности доказательства по следующим причинам: 1. Для правила фиксированного прирагцения изменение параметра с соответствует изменению масштаба системы координат. Это изменение не влияет на структуру данных и линейный классификатор. 2. Правило полной коррекции и градиентное правило коррекции становятся эквивалентными правилу фиксированного приращения, если во всех случаях, когда И"Я, ~ О, дополнять обучающую последовательность последовательностью искусственных ОбЪЕКтОВ Ях = Их+1 =... = Ях~„.
ЗяаЧЕНИЕ И ОПрЕдЕЛяЕтСя уСЛО- виями (7.9) и (7.10) . Сокращенная обучающая последовательность создает соответствующую последовательность векторов Ит~: И А+1 Ит„"+ Я" Пусть Ит, — любой построенный с помощью описанного выше процесса классификатор, удовлетворяющий условию (7.13). Поскольку мы предположили, что распределения линейно разделимы, то для всех объектов должно выполняться следующее неравенство: 213 И',"+1 = И „"+ сг,". (7.28) И";г > И'„"Т вЂ” э 7' ~ о~,, Мж = (1П~) Х Х,. (7. 29) гл. 7.
послкдовАткльнок оцкнивАник пАРАмктРов можно выбрать масштаб И~ так, чтобы И",,Л1, > (а + Ь) /2 > О. (7.19) Изменение масштаба И' не изменяет решающего правила (7.13)' .или (7.2) . Расстояние между векторами параметров И', и И'~ равно !!И,— и„"~12=-~~И,~~'-+((И,",à — 2ИЭГ"„. (7.20) Следовательно, используя (7.15), получим 1~ И, — И Ц2 — (~ И, — И,",+, ~~2 = = ~!И,",~Р— ~!и,",+1à — 2И",,(И,", — И,",+1) = = — 2И'ГЛ"„— Л,"'Я,", + 2И ',г,",, (7.21) *т * Вспоминая, что И'7, Л„~( О, и учитывая неравенства (7.18) и (7.19), имеем 1~ И~з И~А ~~ !1 Из И1р~+1!! > — а + 2 (а + Ь)(2 = — Ь > О. (7.22) Неравенство (7.22) показывает, что при каждом предъявле* нии нового объекта Лд расстояние ~~И', — И'1,~! уменыпается па некоторую фиксированную величину, большую чем Ь.
Поэтому * после конечного числа предъявлений вектор И ~ доли1еп стать равным вектору И',. 7.1.3. Линейный классификатор для задач распознавания со многими классамп. Алгоритм построения линейного классификатора для задач распознавания двух классов можно обобщить на случай многих классов. В случае Л1 классов строятся М линейных разделяющих функций И';, и решающее правило имеет вид 1=-1,2,...,ЛХ, 1Ф~.
(7.23) Если все У~ о>ь 7 = 1, 2, ..., Л1, удовлетворя7от условию (7.23), мы будем говорить, что эти ЛХ классов линейно разделимы. Алгоритм корректировки параметров имеет следующий вид: 1. Если И~';У > И"„:У, ~ =- 1, 2,,..., Л1; 7'Ф ~ при У ~ са,.„ то И'1, =- И'„, й = 1, 2, ..., Л1, ~7.24) 2. Если И'1'У > И";У и И";У > И",У при У ~о>;, то И'1= = И~1 — сУ, И'1= И', + сУ, И'; = И';, ~~7', 1. (7.25) Задачу распознавания многих классов можно свести к задаче распознавания двух классов, если увеличить в М раз размерно- $7,2, стохАстичкскАя АГ1пРоксимАция сти исходного пространства и вектора И~: И' = [И'1... И"; 1И",И";~1 ...
И'1 1И'~И~1+1 ... И'~ц~',. (7.26) Л =- [О'... 0'1"0'... 0' — УтО'... 0']' (7. 27) при условии (7.25). Гогда для сокра7ценной обучающей последовательности Х1, Я2, ...можно получить соответствующую последовательность векторов И', И 1, И 2, . ° ., связанных соотношением Уравнение (7.28) эквивалентно (7.25) . Так как при с = 1 (7.28) совпадает с (7.15), то сходимость (7.28) и, следовательно, сходимость (7.25) доказана в предыдущем разделе. Как говорилось в гл. 4, для разделения многих классов часто используют кусочно-линейный классификатор. К сожалению, доказательство сходпмости для кусочно-линейного классификатора неизвестно. Однако аналогичные алгоритмы корректировки вектора параметров И' можно найти в литературе [Нильсон, 1967; Дуда, 1966].
~ 7.2. Стохастическая аппроксимация Алгоритм последовательного оценивания, описанный в ~ 7.1, не всегда сходится, если векторы наблюдений не являются линейно разделимыми (пример 7.2). Этот факт выдвигает задачу построения алгоритма оценивания, сходимость которого гарантирована. Метод стохастпческой аппроксимации был первоначально разработан как метод оптимизации при наличии случайных помех [Вайлд, 1964; Мендел, 1970]. Этот метод, сходимость которого гарантирована при очень общих условиях, можно применить и для оценивания параметров в задаче распознавания образов. Однако оценить скорость сходимости метода стохастической аппроксимации обычно довольно трудно. Прежде чем перейти к детальному рассмотрению метода, приведем простой пример.
Пусть мы хотим оценить вектор математического ожидания по конечному числу наблюдений, используя последовательный алгоритм оценивания. Обычная оценка М,,; вектора математического ожидания по У наблюдениям Х1, ..., Х„имеет вид 214 гл. 7. последовлтельпое оценивлпие плРАметров Это соотношение можно переписать следующим образом: и — ~ "Кч = [(Л~ — 1)/1Ч] [1/(1Ч вЂ” 1)],'5,' Х,. -]- (1/У) Х 4=1 - [(Л~ — 1)/Л~] М„, + (1/Л ) Х„. (7.30) Другими словами, при добавлении нового объекта Х~ для вычисления оценки М„достаточно помнить только. Предыдущую оценку М„1 и число наблюдений У. Кроме того, по мере увеличения У влияние нового объекта на вектор выборочного среднего значения уыеньшается следующим образом: (7.31) Последовательность коэффициентов 1, '/2, '/з, ..., 1/У, ...
на- зывается гармонической после- Е ф~~щ~цд~~~~~дщ, р/ дова тель пост ью. Приведенный выше простой о о ' пример приводит к мысли взять о о о, о за основу следующий метод последовательного оценивания. 1. Когда имеется математик о ческое выражение для оценки, можно построить процедуру поо следовательного оценивания пу- тем разбиения этого выражения о „Ю+~ Ю. У* на два слагаемых: оценку, рассчитанную по У вЂ” 1 объектам,. и вклад У-го объекта. Рис. 7.3. Задача нахождения корин. 2.
В тех сл чаях к . В случаях, когда для минимизации илп максимизации некоторого критерия мы вынуждены использовать процесс поиска, можно уменьшить влияние У-го объекта с помощью коэффициента, представляющего собой убывающую функцию Х 7.2.1. Задача нахождения корня уравнения регрессии. Наиболее простой вид метод стохастической аппроксимации принимает в задаче нахождения корня уравнения регрессии. Соответствующую процедуру называют также методом Роббинса— Монро. Пусть О и х — две случайные величины, коррелирующие одна с другой, как показано на рис. 7.3. Задача заключается в нахождении корня уравнения регрессии„ т. е. такого значения О, при котором 215 $ 7,2.
стохлстическля АппроксиыАция (7.35) ,~ ан =- оо„ Л=$ «~ а~( оо, м=~ (7.36) Как эти условия используются прн доказательстве сходимости, будет видно в дальнейшем. Однако физический смысл этих условий достаточно очевиден. Смысл условия (7.34) аналогичен смыслу члена 1/У в рассмотренном ранее примере: это условие обеспечивает сходпмость процесса. С другои стороны, условие (7.35) гарантирует, что имеется достаточная возможность коррекции, т.
е. что процесс не остановится раньше, чем мы дойдем до корня. Условие (7.36) гарантирует, что дисперсия накопленного шума будет конечной, так чтобы можно было скорректировать влияние шума. Если последовательность а~ удовлетворяет условиям (7.34)— '(7.36)', оценка О~ сходится к корню О в среднем квадратичном и с вероятностью 1, т. е. 1ип Е )(О 7 — 0)з) =- О„ (7.37) и-+оо 11ш Рг(Ол7 = О) = 1. (7.38) Если бы можно было собрать все объекты с фиксированным :О и оцепить Е (к/О), то корень уравнения /(0) = О можно было бы найти каким-либо методом поиска нулей детерминированной функции например методом Пьютона. Однако, если в каждый 1 момент времени мы можем наблюдать только один ооъект с некоторым значением О и пытаемся использовать это наблюдение для коррекции О, то сильная зашумленность наблюдений /(0) может привести к изменению О в неправильном направлении, особенно вблизи корня.
В методе Рообинса — Монро новая последовательная оценка 6 +~, вычисляемая по текущей оценке О~ и новому наблюдению х,, определяется следующим образом: (7.33) где предполагается, без ограничения общности, что О приближается к корню 0 уравнения (7.32) со стороны больших значений функции, т. е. /(О) ) О для О ) О и /(0) ( О для О ( О, как показано на рис. 7.3. В этом случае а~ — последовательность положительных чисел, удовлетворяющих следующим условиям: 1. 11ш ан — О, (7.34) и-+ов /(О) = Е (г/О). '(7.32) Гармоническая последовательность (7.31) является примером 216 гл. 7.
послкдовлткльнок оцкнивлннк плглмктгов последовательности, удовлетворяющей условиям (7.34) — (7 36)'. Более общий (хотя и не единственно возможный) вид такой последовательности — это а„= 1/Л'", 1 ~ /г - 1/2. (7.39) Прежде чем перейти к вопросу о сходимости метода Роббинса — Монро, рассмотрим систему с обратной связью, реализующую описанный выше процесс. Эта система показана на рис.
7.4, рег Ю Рис. 7.4. Эквивалентная схема с обратной связью. д 1( ) — шум. Коэффициент усиления а (~) в цепи обратно" связи пе фиксирован, а уменьшается со временем. Из теории цепей с обратной связью известно, что уменьпгение а(1) гарантирует устойчивость системы, но может также привести к увеличению времени регулирования.
7.2.2. Доказательство сходимости метода Роббинса — Монро. Сходимость метода Роббинса — Монро доказывается следующим образом. Представим случайную величину кл в виде суммы дву.с слагаемых: функции регрессии /(О.,) и шума 7л. Тогда (7.33) можно переписать следующим образом: в„„= в...,/;0,) (7,40) где Тл~ = ~ж — /'(Ол). (7.41) Из определения функции регрессии /(0) в (7.32) следует, что 7„— случайная величина с пулевым математическим ожиданием Е (7 0;) = Е (к~/О) — /(Ом) = О. (7.42) Кроме того, разумно предположить, что дисперсия 7л ограничена, т. е. Е (72,) ( о' (7.43) и что 7„и Ол статистически независимы.
Рассмотрим разность между корнем уравнения регрессии 0 и его оценкой В~. Из (7.40) следуеее, что (0~,1 — О) = (0~ — О) — ач/(0„) — а„7„. (7.44) 217 ф 7.2. стохлстичкскля лппРОксиылция Возводя (7.44) в квадрат и взяв математическое ожидание от обеих частей, получим Е ((Оле+1 — 0)2( — Е ((Оле — 0) ( = ал,Е (/(Оле)') + + имЕ (У.,,( — 2алЕ ((О~е — 0) /(О 1)) (7 45) Повторяя (7.45) У вЂ” 1 раз (начиная с У = 1) и суммируя, получим е ((в — о)-'( — е ((в, — б)"-( = М вЂ” 1 ж — 1 а~ (Е11/(О;)')+ Е (у';(1 — 2 ~ аЕЕ ((О; — б) /10,.)(. (7.46) =1 1=-1 Предположим, что функция регрессии также ограничена в интересующей нас ооласти е (/(0.)') м.
(7.47) Тогда левая часть (7.46) ограничена выражением е ((в„— о)-"( — е ((о, — б)-'(( Л вЂ” 1 Л вЂ” 1 ( (М + о'),'~,' а2 — 2 ~ а; Е ((О, — О ) / (О, ) (. 1=1 1=1 (7. 48) /(0) > О, если (Π— О) ) О, /(0) = О, если (Π— О) = О, /(О) ( О, если (Π— О) ( О, (7,40) поэтому (7.50) (О 0)/(0) ~ О Е ((о — о)/(о)) - О. '(7.51) Рассмотрим теперь следугощее утверждение: 11 е((в,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
