Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 34
Текст из файла (страница 34)
Подставив данное выражение во второе уравнение и выполнив некоторые алгебраические преобразования, получим — „Зое+ — „'," (пзь — п22) (ть — ть)~~ то= ть — гпь. (40) Поскольку направление вектора (т,— т,)(ть — гпь)'е при любом тт СОВПаДаЕт С НаПРаВЛЕНИЕМ ВЕКтОРа Пзь — Гн„те МОЖНО ЗаПИСатЬ Можно показать, что при определенном выборе Ь обнаруживается связь между решением по методу наименьшей квадратичной ошибки и линейным дискрнминантом Фишера.
Доказательство начнем, записав соотношение (32) для а с использованием разложенных матриц: 172 Ге. 5. Лииейиеее ееедееяеуяеее фуееееяии следующее выражение: — „',' (т,— ш,) (т,— ш,)'еч =(1 — а) (ш,— ш,), где а — некоторая скалярная величина. В этом случае соотношение (40) дает ет =алЮ(ге(т,— ш,), (41) что, за исключением скалярного коэффициента, идентично решению для случая линейного дискримннанта Фишера.
Помимо этого, получаем величину порога еае и следующее решающее правило; принять решение е„если УУ'(х — ш))0; иначе принять решение в,. 5.8.3. АСИМПТОТИЧЕСКОЕ ПРИбЛИЖЕНИЕ К ОПТИМАЛЪНОМУ ДИСКРИМИНАНТУ Другое свойство решения по методу наименьшей квадратичной ошибки, говорящее в его пользу, состоит в том, что при условии Ь= =п„и при л-е со оно в пределе приближается в смысле минимума среднеквадратичной ошибки к разделяющей функции Вайеса де(х)=Р (в,1х) — Р (ве)х). (42) Чтобы продемонстрировать данное утверждение, следует предположить, что выборки взяты независимо в соответствии с вероятностным законом р (х)=р (х!в,)Р (в,)+р (х1в,)Р (в,). (43) Решение по методу наименьшей квадратичной ошибки с использованием расширенного вектора у дает разложение в ряд функции д (х) =а'у, где у=у (х).
Если определить среднеквадратичную ошибку аппроксимации выражением а' = ~ (аеу — еге (х))е р (х) е(х, (44) то нашей задачей будет показать, что величина е' минимизируется посредством решения а=у'Ув„. Доказательство упростится при условии сохранения различия между выборками класса! и класса 2. Исходя из ненормированных данных, функцию критерия /, можно записать в виде У, (а) =,'У' ,(а'у — 1)' + ~ч~~ (а'у + 1)' = У Е ~У'Е У ЕЕЕЕ Таким образом, в соответствии с законом больших чисел при стремлении и к бесконечности (17л)l, (а) приближается с вероятностью 1 к Б.8. Процодррм минимизации коадрааинноа ошибки 173 функции Х(а), имеющей вид .( (а) = Р (Ф,) Е, [(а'У вЂ” 1)']+ Р (оо,) Е, [(а'у+ 1)'], (45) где Е, [(асу — 1)о]= ~ (аиду — 1)',о(х(оо,)о(х и Е, [(агу — 1)'] = ~ (а'у+ 1)'р (х ( оо,) о(х. Теперь, если мы из соотношения (42) определим р(х, оь) — р(х, шй р (х) то получим 7(а) = ~ (а'у — 1)' р(х, а,) бх+ ~ (а'у+1)'р(х, о,)о(х= = ) (а'у)'Р(х)йх — 2 ~ а'уело(х) р(х)бх+1= = ) [ау — до (х)]о р (х) дх+ ~1 — ) й', (х) р (х) о(х ] .
(46) Второй член данной суммы не зависит от весового вектора а. Отсюда следует, что а, которое минимизирует 1„также минимизирует и е' — среднеквадратичную ошибку между а'у и до(х). Данный результат позволяет глубже проникнуть в суть процедуры, обеспечивающей решение по методу наименьшей квадратичной ошибки. Аппроксимируя до(х), разделяющая функция а'у дает непосредственную информацию относительно апостериорных вероят- настейР(оо,(х)=1/2(1+до) и Р(оо,(х)=!/2(! — яо). Качество аппроксимации зависит от функций у~ (х) и числа членов в разложении а'у. К сожалению, критерий среднеквадратичной ошибки в основном распространяется не на точки, близкие к поверхности решения яо(х)=0, а иа точки, для которых значение р(х) велико.
Таким образом, разделяющая функция, которая наилучшим образом аппроксимирует разделяющую функцию Байеса, не обязательно минимизирует вероятность ошибки. Несмотря на данный недостаток, решение по методу наименьшей квадратичной ошибки обладает интересными свойствами и широко распространено в литературе. Далее, при рассмотрении методов стохастической аппроксимации, еще предстоит встретиться с задачей среднеквадратичной аппроксимации функции яо (х), 6.8.4. ПРОЦЕДУРА ВИДРОУ вЂ” ХОФФЛ Ранее было отмечено, что функцию l, (а) =((г'а — Ь((' можно минимизировать при помощи процедуры градиентного спуска. У такого подхода есть два преимущества по сравнению с простым выполнением 174 Гл.
3. лин«йиые разд«««ющие кн«чиа псевдообращения: 1) не возникает трудностей в случае, когда матрица У'У вырождена, и 2) устраняется необходимость работы с большими матрицами. Кроме того, необходимые вычисления здесь с успехом реализуются схемой с обратной связью, которая автоматически справляется с некоторыми вычислительными трудностями, округляя или отбрасывая члены. Поскольку М,=2У'(Уа — Ь), то очевидно, что алгоритм спуска может быть представлен в следующем виде: а, произвольно, аз+, —— а„— р„Р (Уаз — Ь). Будет полезно убедиться, что если Рь=р«А где р, — любая положительная константа, то с помощью данного правила можно образовать последовательность весовых векторов, которая сходится к предельному вектору а, удовлетворяющему условию У«(Уа — Ь) =О.
Таким образом, алгоритм спуска всегда дает решение независимо от того, будет ли матрица У'У вырожденной или нет. Несмотря на то что матрица У'У размера «(хд обычно меньше матрицы У1 размера Зхп, сохранившиеся требования могут быть еще далее снижены при последовательном рассмотрении выборок и использовании правила Видроу — Хо(йфа, записанного в виде а, произвольно, а„, =а,+р,(܄— а„'у')у".
На первый взгляд алгоритм спуска представляется таним же, как правило релаксаций. Однако главное их различие состоит в том,'что правило релаксаций является правилом коррекции ошибок, так что а(у«всегда меньше Ью тогда как правило Видроу — Хоффа обеспечивает «коррекцию» вектора аь всякий раз, когда а4у«не равно Ь«. В большинстве случаев, представляющих интерес, невозможно удовлетворить всем равенствам а'у«=Ь„, так что процесс коррекцийбудет непрекращающимся. Таким образом, для сходимоститребуется, чтобы р«уменьшалось вместе с й, выбор р«=р,/й является типичным. Строгий анализ поведения правила Вцдроув Хоффа для детерминированного случая довольно сложен и показывает лишь, что последовательность весовых векторов имеет тенденцию сходиться к требуемому решению.
Вместо дальнейшего разбора этой темы обратимся к очень простому правилу, вытекающему из процедуры стохастического спуска, 8.8. Лрояедури минимизации иоадрашионоа ошидни !75 5.8.5. МЕТОДЫ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ Все итеративные процедуры спуска, рассмотренные ранее, были детерминированными: задавали некоторое множество выборок н образовывали вполне определенную последовательность весовых векторов. В данном пункте придется слегка отступить и рассмотреть процедуры решения по методу наименьшей квадратичной ошибки со случайно формируемыми выборками, что приводит к образованию случайной последовательности весовых векторов. Для полного анализа потребовалось бы использование теории стохастнческой аппроксимации, и мы бы с этим не справились. Однако основные идеи, которые можно дать без доказательства, просты.
Предположим, что выборки взяты независимо путем выделения состояний природы с вероятностью Р(в;) и последующего выбора х в соответствии с вероятностным законом Р(х1в~). Для каждогох введем метку г, такую, что г=+1 при х, соответствующем в„и г= = — 1 при х, соответствующем в,. Тогда данные будут представлять собой бесконечную последовательность независимых пар (х„г1), (хо го),, (хю г„), Даже если метка г будет бинарной, это может быть истолковано как зашумленный вариант байесовской разделяющей функции ко(х).
Данное утверждение вытекает из наблюдения, что Р (г=11х) =Р (в, ~х) Р(г= — 11х)=-Р (в,!х), так что условное среднее для г задается выражением Е,~,(г)=ЯгР(г)х)=-Р(в,)х) — Р(в,)х)=до(х). (48) Предположим, что требуется аппроксимировать до(х) посредст- вом следующего конечного разложения в ряд: 8 д(х) = а'у =,)~ а;у;(х), ~=1 где известны как базисные функции у;(х), так н число членов о(.
Тогда можно определить весовой вектор а, минимизирующий сред- неквадратичную ошибку аппроксимации е' =- Е [(а'у — до (х))'1. (49) Для минимизации е' необходимо знать байесовскую разделяющую функцию у,(х). Однако, исходя из аналогичной ситуации, рассмотренной в п. 5.8.3, можно показать, что весовой вектор а, минимизирующий а', также минимизирует функцию критерия, имеющую вид 7 (а) =Е 1(аоу — г)'].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
