Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 35
Текст из файла (страница 35)
(50) Га о. Линейные разде»ающие функции !А н! -Р(м»1н) Рис. о.!!. Аппроксимация Еайесовской разделяющей фуккцки. применения процедуры градиентного спуска. допустим, что вместо действительного градиента подставлено выражение для зашумленного варианта 2(а'у„— ка) у„. Это приведет к алгоритму спуска следующего вида: а»+, —— а»+ р» (㻠— а'„уа) у», (52) который, по существу, представляет собой правило Вндроу — Хоф. фа. Можно показать, что если матрица Е (уу 1 не вырождена и козф. фициенты р» удовлетворяют условиям 11п! ~», 'р» — — + оо, (53) Р3-Ф В» !пп ~ рз» ( оо, (54) то а» сходится к а в среднеквадратичном: 1нп Е[!!а„— а!1»1=-0.
»- ф (55) Данное заключение также должно следовать из того факта, что г, по существу, является зашумленным вариантом йе(х) (рис. 5.11). Поскольку 17 1„, = 2Е [(а'у — г) у), то можно получить решение в замкнутой форме а = Е [уу'1-' Е [гу1, (51) Таким образом, один нз способов, основанный на использова- нии выборок, состоит в оценке Е 1уу'1 н Е (гу1 н применении выраже- ния (51) с целью получения оптимальной линейной разделяющей функции. Другой метод заключается в минимизации 7 (а) путем г 8.8. Процедуры минимизации квадратичной отабна 177 Причины наложения данных условий на р» просты.
Первое ус- ловие не позволяет весовому вектору сходиться настолько быстро, чтобы систематическая ошибка оставалась бы нескорректирован- ной. Второе условие обеспечивает то обстоятельство, что случайные колебания в конечном счете гасятся. Оба условия удовлетворяются прн соответствующем выборе р» — — 1/л. К сожалению, такой вид убы- вания р» независимо от рассматриваемой задачи часто приводит к очень медленной сходимости. Конечно, указанный алгоритм не единственный и не лучший ал- горитм спуска для минимизации 7„.
Например, если матрицу вто. рых частных производных для 3„задать следующим образом: Р = 2Е (уу!1, то можно видеть, что алгоритм Ньютона для минимизации (формула (11)1 имеет вид а»+, — — а, +Е (уут1 ' Е [(г — а'у) у). Стохастическим аналогом данного алгоритма является а»+, — — и»+ й»+, (㻠— а»у») у» (56) при Е»' =Р».'+у»у» (57) или, что эквивалентно '), )7»у» ()7»у»)' (55) С помощью данного алгоритма также образуется последовательность весовых векторов, сходящихся к оптимальному решению в среднеквадратичном, В этом случае последовательность сходится быстрее, однако требуется выполнение большего количества вычислений за шаг.
Указанные градиентные процедуры могут рассматриваться как методы минимизации функции критерия, нли определения нуля ее градиента, в присутствии помех. В литературе по статистике такие функции, как У„и ЧЯ„вида Е 17 (а, х)), называются регрессионными функциями, а итерационные алгоритмы называются прог(едурами стохастической аппроксимации. Наиболее известными нз них является процедура Кифера — Вольфовица, применяемая для минимизации регрессионной функции, и процедура Роббинса— Монро, используемая для определения корня регрессионной функции. Зачастую легче всего доказать сходимость процедуры спуска или процедуры аппроксимации, показав, что она удовлетворяет ') Данная рекуррентная формула для вычисления и», которое приблизительно равно (!7»)8(уу!)-т, не может быть исаользоаана, если матрица Й» вырож.
дена. Эквивалентность соотнотени» (57) и (58) вытекает из задачи !О гл. 3. Гж К Линейние разделяющие функции условиям сходимости более общих процедур. К сожалению, представление данных методов в полном объеме завело бы нас довольно далеко, и в заключение мы можем лишь посоветоватьинтересующимся читателям обратиться к литературе. 9.9. ПРОЦЕДУРЫ ХΠ— КАШЬЯПА 7„/, =- 2У' (Уа — Ь), а градиент, взятый относительно Ь, задается в виде Уь|,=- — 2(Уа-Ь). (59) (60) 5.9.!. ПРОЦЕДУРА СПУСКА Процедуры, рассмотренные до сих пор, различались в разных отношениях.
При методе персептрона и процедуре релаксаций разделяющий вектор определялся в случае линейно разделяемых множеств, однако в случае неразделяемых множеств сходимости не наблюдалось. Процедуры нахождения решения по методу наименьших квадратов дают весовой вектор как в случае линейно разделяемых, так и в случае линейно неразделяемых выборок, однако нет гарантии, что указанный вектор будет разделяющим вектором в случае разделяемых множеств. Если вектор допуска Ь выбран произвольным образом, то можно сказать, что процедуры для решения по методу наименьших квадратов минимизируют выражение ||Ув— — Ь) |*.
Тогда, если взятые выборки линейно разделяемы, существуют такие а и Ь, что выполняется следующее условие: Уа=Ь) О, где Ь)О„что указывает на положительность каждой компоненты Ь. Очевидно, что при использовании равенства Ь=Ь и применении процедуры решения методом наименьших квадратов был бы получен разделяющий вектор. Конечно, обычно Ь заранее неизвестно.
Однако покажем теперь, ках процедура решения по методу наименьших квадратов может быть модифицирована для получения как разделяющего вектора а, так и вектора допуска Ь. Проводимая идея вытекает из наблюдения, что если выборки разделимы и векторы как а, так и Ь, содержащиеся в функции критерия 1,(а, Ь) =||Уа — Ь||', могут изменяться (при условии, что Ь)0), то минимальное значение /, равно О, а а, которое достигается при данном минимуме, является разделяющим вектором.
Для минимизации 1, будем использовать модифицированную процедуру градиентного спуска. Градиент функции /„ взятый относительно а, записывается в виде Ю.9. Проч~дура Ха — Кашьяпа 179 При любой величине Ь можно всегда принять а =утЬ, (61) получая тем самым 7, 1,=0 и минимизируя 7, по а за один шаг. Больших возможностей для изменения Ь, однако, не имеется, поскольку нужно придерживаться условия Ь~О, так что следует избегать процедуры спуска, которая приводит к Ь=О. Один из способов, препятствующий сходимости Ь к О, заключается в том, чтобы положить вначале Ь:>О и впоследствии ие уменьшать никакую из его компонент.
Этого можнодостичь при сохранении отрицательного градиента, если вначале все положительные компоненты Чьl, взять равными О. Таким образом, если через 1т~ обозначить вектор, компоненты которого суть абсолютные величины компонент вектора ч, то придем к рассмотрению такой процедуры спуска; 1 ~1+1 — Ьа р 2 [Чь~ю ! Чи~яп. Используя соотношения (60) и (61) и несколько более конкретизируя, получим алгоритм Хо — Кашьяпа минимизации функции 7,(а, Ь): Ь,) О, в остальном произвольный, Ьа+, —— Ьа+ 2ре~~, (62) где еь является вектором ошибки: еь=уаь — Ью (62) а е," — положительная составляющая вектора ошибки: е~+ = — (еа+ ~ еа (), „, ! (64) а,=г Ь», Ф й=1, 2, (65) Поскольку весовой вектор а, полностью определяется вектором допуска Ь„, то это, по существу, н есть алгоритм для образования последовательности векторов допуска.
Вектор Ь„с которого начинается последовательность, положителен, и если р)0, то все последующие векторы Ь, будут положительны. Мы можем опасаться, что если ни один из компонент вектора е~ не положительна, так что изменение Ьь прекращается, то мы не получим решения. Однако, как мы увидим, в этом случае либо е„=О и решение получено, либо е,(0 и можно доказать, что выборки линейно не разделяемы. 180 Га. е. Линей»не ииедеииеецие функции в.эдс доклзлткльство сходимости Покажемтеперь, чтоесли выборки линейноразделяемы и 0(р < н;.1, то процедура Хо — Кашьяпа будет давать вектор решения за конечное число шагов.
Чтобы сделать алгоритм конечным, следовало бы добавить правило остановки, по которому процесс коррекций прекратится сразу же, как будет найден вектор решения. Однако более удобно считать процесс коррекций непрерывным и показать, что вектор ошибки е» либо становится нулевым при некотором конечном й, либо сходится к нулевому при А- со. Очевидно, что либо е» вЂ” — 0 при некотором А, скажем при й„ либо в последовательности е„е„... не содержится нулевых векторов. В первом случае, как только нулевой вектор получен, нн один из векторов «», Ь, или е» больше ие изменяется и 1'а»=Ь»)0 для всех А)А,.
Таким образом, при получении нулевого вектора ошибки алгоритм автоматически останавливается, и мы имеем вектор решения. Предположим теперь, что е» никогда не станет нулевым при конечном А. Чтобы показать, что е» тем не менее должно сходиться к нулю, сначала поставим вопрос, возможно ли получение е» с неположительными компонентами.
Указанное обстоятельство должно быть наиболее нежелательным, поскольку требуется, чтобы выполнялось условие Уа»(Ь», и поскольну е+» должно быть нулевым, чтобы прекратилось дальнейшее изменение аю Ь» или е,. К счастью, данная ситуация может никогда не возникнуть, если выборки линейно разделяемы. Доказательство просто и основано иа том факте, что если Руа,=РЬ», то Ре» вЂ” — О. Однако в случае линейно разделяемых выборок существуют такие а и Ь= О, что справедливо соотношение Уа=Ь. Таким образом е»уа = 0 = е»Ь, и поскольку все компоненты вектора Ь положительны, то либо е» вЂ”вЂ” =О, либо по крайней мере одна из компонент е» должна быть положительна. Поскольку случай е»=0 исключен, из этого следует, что е» может ие быть нулем при конечном й. Для доказательства того, что вектор ошибки всегда сходится к нулю, используется тот факт, что матрица УУе симметрична, положительно полуопределена и удовлетворяет соотношению (УУФ) (УУ») -- УУ1.
(66) Хотя этн результаты справедливы и в общем случае, для простоты рассмотрим нх только для невырожденной матрицы У'У. В этом случае Ууе= у(РУ)-'Р, и симметричность очевидна. Поскольку матрица Ру является положительно определенной, то сущест- 18! Ю.У. Процедура Хо — Кааьяяа вует матрица (У'У)-', таким образом, Ь'У (УтУ)-' РЬ~~О при любом Ь, и матрица УУ( является по крайней мере положительно полуопределенной. Итак, соотношение (66) вытекает нз следующего: (УУ")'(УУ') = (У (У'У) 'У') Р' (У'У) 'Л. Чтобы показать, что еь должно сходиться к нулю, исключим аь из (63) — (65) и получим следующее выражение: еь=(УУт — !) Ьм Затем, используя (62), получим рекуррентную формулу ед~, — — (УУт — !)(Ьд+2ре!) = = е„+ 2р (У Ут — !) е'„, так что — )) еь,, !!' = — )) е, (('+ реь~ (УУт — !) е7 -(- '2 р (УУФ вЂ” 1) Е+ ~~а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
