Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 37
Текст из файла (страница 37)
— в)/(в,)(= о. (7.52) Если (7.52) не выполняется, тогда, вследствие условия '(7.35), последний член неравенства (7.48) стремится к — оо. Но это Рассмотрим по отдельности каждый член неравенства (7.48). Во-первых так как Е((0„— О) ') — положительное число, а л Е ((01 — В) 2) — конечное, то левая часть (7.48) ограничена снизу, Первый член правой части (7.48) конечен в силу условия (7.36).
Вспомним (см. рпс. 7.3), что функция регрессии удовлетворяет следующим условиям: 219 Е Ф~ нн,пя ~.ер~„дед, Рис. 7.5. Метод Кифера — Вольфовица. 1пп аА~ = О, Л-~ оо (7. 55) (7. 62) (7.56) дх (9 )/дО 218 Гл. 7. ЦОслкдОВАткльнок Оцкнивлпик пАРА~ч1ктРОВ противоречит тому, что левая часть неравенства (7.48) ограничена снизу. Следовательно, утверждение (7.52) должно быть выполнено. Так как условие (7.50) выполняется для всех О, утверждение (7.52) эквивалентно утверждению: 11ш Рг (01 = О ) = 1. (7.53~ Таким образом, сходимость с вероятностью 1 доказана. Доказа-, тельство сходимости в среднем квадратичном здесь не приводится.
7.2.3. За ач Роббинс д а поиска максимума функции регресс . М . а — Монро легссо модифипировать таким об . ° б ии. ' етод вместо ко разом, чтобы ' рня искать максимум функции регресси1. ак хорошо известно, точка максимума функции /(О) есть корень уравнения ф(0)/ЫО = О. Поэтому, если бы мож б р ть /( )/ЫО, то мы могли бы непосредственно п именить тод Роббинса — Мои о. К а — оиро. 1 сожалению, в большинстве приложений измерение а/(О)/ЫО невозможно. Будем поэтому измерять производную экспериментально, делая пробные шаги, и модифицировать О~ следующим образом: 0„,1 — — ΄— а„[к (О„+ с„) — к (΄— с ) ]/(2с ) .
(7.54) Эта последовательная процедура носит название иетод Кифера— Вольфовича. Рис. 7.5 иллюстрирует этот метод. Коэффициенты а,о и со — это последовательности положительных чисел, стремящиеся к нулю (для того, чтобы процесс был сходящимся ): ~ 7.2. СТОХАСТИЧКСИАЯ АППРОКСИМАЦИЯ Чтобы обеспечить достаточную величину коррекции, т. е. избожать остановки процесса не доходя до максимума, числа а~ должны удовлетворять условию а~ —— оо. (7.57) и=1 Кроме того, для того чтобы погасить накапливающееся влияние шума, долнсно выполняться условие (аА~/сч)2 ( оо. (7.58) я=1 Доказано, что если а; и с~о удовлетворяют этим условиям, оценка О~ сходится к максимуму функции регрессии О в среднем квадратичном и с вероятностью 1 (при условии, что дисперсия шума и крутизна функции регрессии ограничены).
Доказательство аналогично доказательству сходимости метода Роббииса— Монро и здесь не приводится. 7.2.4. Обобщение на многомерный случай. До сих пор метод стохастической аппроксимации рассматривался для случая одной переменной. Это делалось, главным образом, ради простоты изложения. Выводы и критерий для выбора последовательности а,о остаются в силе и для многомерного случая, и предыдущее рассмотрение, включая доказательство сходимости, можно повторить без изменения, если заменить х2 на ))Х((2. Таким образом, для метода Роббинса — Монро процедуру (7.33) можно переписать следующим образом: Й„~, = 9„— а,-Х„, (7.50) где последовательность а~ по-пренснему должна удовлетворять условиям (7.34) — (7.36). При условии, что дисперсия шума и функция регрессии ограничены, эта процедура гарантирует сходпмость в среднем квадратичном и с вероятностью 1.
В методе Кифера — Вольфовица частные производные можно аппроксимировать следующим образом: д2(О,;)/дО; т [г(Ом+ сжЕ;) — 2(Ок), (7.60) д (О )/дО ~ [,(О„+ с,,Е,) — г(0,.„— с,,Е;)]/(2с ), (7.61) где Е; — единичный вектор 1'-й координаты [О 0... 0 1 0... О] '. 'Тогда процедуру (7.54) можно обобщить иа многомерный случай следующим образом: 221 220 Гл. 7. ЦоследоВАтельное ОцениВАние плРАметРОВ $ 7.2. стохлстическля лппРОксимлция и а рис.
7 6 показано, как измеряются частные производные; измерение по формуле (7.60) требует и+ 1 наблюдений, по фо— муле (7.61) — 277 наб:ыодений. Как и в одномерном случае, гарантируется сходимость в среднем квадратичном и с вероятностью 1, при условии, что дисперсии шума и крутизна функп1117 регрессии ограничены. фз ФУки4ы Уырж~иы Рис, 7.6. Метод Кифера — Больфовица длл многомерного случая. Теперь мы можем применить метод стохастической аппроксимации к задаче построения классификатора. Построим классификатор, минимизирующий среднеквадратичную ошибку, т.
е. отклонение желаемого выхода 7 (Я,) от фактического И"У; (4.45), где Л1 = У, для У,~ в1 и Я, = — У1 для У ~ в2. Хотя здесь рассматривается только этот крцтерий, аналогично можно рассмотреть и другие критерии качества классифпг чтора. П ропедуру последовательной корректировки вектора параметров И' (4.48) можно переп11сать следующим образом: И (7+1) = и'(7) — р(7"7'7И) = = И (7) — 2р(17Л) Х (И (г)'г,. — ~(г,)1К, (7.Я) 1=1 Другими словами, для модификации И" (7) используются векторы выборочного среднего случайной величины (И'(7) 'Х вЂ” (Х) ) Х П оэтоыу, если можно использовать все Ю объектов для вычисления вектора выборогного среднего при данном И~, то последовательная корректировка превращается в простой процесс оптимизации функции регрессии.
Когда же для корректировки И:(7) в Таблица 73 П ример построения л. е я клчсс111рпкатора с использованием отдельных объектов тента1ее И Объентв1 на вводе 2Р1т — И' 2)Я 191 1' '19 '12 1/ '19 11 '19 0,6 — 0,9 0,9 — 0,5 0,7 — 0.5 0,0 — 0,9 1,8 0,0 — 0,7 1.0 3,0 4,8 5,1 3,0 5,1 3 4 0 0 О 1,2 — 0,9 О,З 0,9 0,3 0,9 1,3 0,2 0,6 1 0 2 — 1 — 1 — 1 2 0 1 0 2 1 — 1 — 1 29 г, г, 22 г 22 — 0,9 0,6 — 0,3 0,6 0,1 0.8 0,0 К С~ н 1,0 — 0,7 0,0 — 1 2 1~ 19 1/ '17 1( 19 17 19 729 '721 1,2 0,11 1,2 1,0 0,5 0,3 0 9 0,3 0,9 0,9 0,4 0,4 0,3 0,5 1 0 — 1 — 1 1 2 0 2о 71 ~2 гв г га — 0,7 0,0 0,6 — 0.5 — 0,7 — 0,7 5,7 0,2 0,4 — 0,2 — 0,3 0,0 — 0,5 0,4 2,4 5,1 2,4 0,0 — 0,3 0,2 — 1 0 2 1 — 1 — 1 — 1 2 О 1 0 2 1 1 — 1 0,5 О,Π— 0,2 0,2 0 0,4 722 2,2 0,0 0,8 0,4 0 2 О 8 0 8 Результаты показаны в табл.
7.3, где начальное значение раино ~0 О О~', 7(71) = 3 для у = О, 1, ..., 5, а р — последовательность принимающая значения 1/1о, '/1п ... Такая последова! можпо использовать лишь один объект в ка'кдый момент времени, (7.63) принимает вид И (7+1) = и (г) — 2р(И (7) г,— ((г,))гь (7,64), Эта процедура идентична методу Роббинса — Монро для многомерного случая (7.5',1), где 2(И'(7)еЯ, — г(Л~))Я~ в (7.64) соответствует У, (7.59). Таким образом, хотя рассматриваемая задача является задачей поиска максимума, в этом случае имеется возможность вычислить частные про~зводные на каждом шаге и применить более простой метод Рообинса — Монро, а пе метод Кифера — Вольфовица.
П р и м е р 7Л. Применим метод Рообпнса — Монро и задаче классификации шести ооъектов, приведенных в примере 7.2, которые линейно не разделимы и для которых метод предыдущего параграфа не позволяет построить сходящуюся последовательность И~. 223 222 / (Х) — ~ О,.гр,. (Х), 2 1 Г7.652 (7.66) Текущее И' в сл М о хи ~ х ~ 2 ох г, г, г, тР (у — И тг>г 1=1 т — и гог. 2' и:е ю, г, г, г, г, г, г, 0 2 — 1 1 1 1 2 0 — 1 0 2 1 — 1 — 1 — 1 2 0 0 0 0 0 0 0 0 0 0 О 0 0 0 0 0 0 0 0 6 0 — 6 — 6 6 12 — 6 0 6 — 6 — 6 12 12 — 6 0 12 — 6 0 0 2 3 г, г, 72 г г, гз 1 0 2 — 1 — 1 — 1 1 2 0 — 1 0 2 1 — 1 — 1 — 1 2 0 1/ 2 1/ '2 1! ~2 1/ 1' О 2 2 0 2 2 0 2 2 0 2 1 0 2 2 0 2 2 — 0,5 — 3,5 — 0,5 0,5 3,5 0.5 Π— 1 — 3,5 — 3,5 — 1 О 0 — 1 — 3,5 — 3,5 — 1 — 1 7 — 1 7 г г г, 72 г гз 1 0 2 — 1 — 1 — 1 2 0 — 1 0 2 1 — 1 — 1 — 1 2 0 1/ /з 1/ 'з 1/ 1/ 1/ О 0.5 0,5 0 0,5 0,5 0 0,5 0,5 0 0,5 0,5 0 0,5 0,5 0 0.5 0,5 4/ з /з /з /з в,' з 4/ в/ в/ з 0 /з /з 0 0 — '/3 /з 0 /з в/ г (Х) —,~~ О,гр, (Х) О 0 0 — Е[ С 0 0,5 0.5 С гв = — 2Е [ ГЛ.
7. ПОСЛЕДОВАТЕЛЬНОЕ ОЦЕПИВЛНИЕ ПАРАМЕТРОВ тельность выбрана главным ооразом потому, что интуитивно чувствуется, что все шесть объектов должны вносить равный вклад д в построение классификатора (по крайней мере на начальной стадии), а последовательность 1, ~/2, ~/в, ... придает слишком большой вес объекту Уе. Последовательность '/д, '/1~,... удовлетворяет условиям (7.34) — (7.36). Легко видеть, что разделяющая прямая 0,5х~ + 0,5х2 = 0 минимизирует среднеквадратичную ошибку, а табл. 7.3 показывает, что последовательность И' приближается к оптимальному классификатору.
Пример, 7.4. Для сравнения найдем последовательность И~, воспользовавшись процедурой (7.63) вместо (7.64) для тех же Таблица 74 П ример построения классификатора с использованием функции регрессии ести Объектов. В соответствии с этой проце у й модифицируется после того, как предъявлены все шесть объектов. Результаты приведены в табл.
7.4. Начав процесс с И' ~0 0 01', "Г(22) = 3, у = О, 1, ..., 5, и используя последовательность р.= .1, '/2, ..., Получа6м оптимальный классификатор за две итерации. % 7,2. СТОХЛСТИЧЕСКЛЯ ЛППРОКСПМЛЦИЯ 7.2.5. Метед потенциальных функций. В методе стохастичеснои аппр 1 роксимации последовательная аппроксимация применяется для оценки набора параметров, дающих нулевое значение или точку экстремума функции регрессии.
Эти результаты можно ь для оценивания самой функции регрессии. применить д по анной Представим функцию регрессии /(Х) разложением по д системе базисных функций В „, „ожепии, что фу ц р, "да, фу 'цн. р"р"'ни (Х)р еляется множеством параметров О. Это похоже на задачу пост построения линейного классификатора, в котором роль функции гр;(Х) играют случайные величины х1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
