Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 36
Текст из файла (страница 36)
(67) Как второй, так н третий члены значительно упрощаются. Поскольку еьУУ=О, второй член представляется в виде ре((УУт — !) е8 = — ре,'еь' — — — р й еД', Таким образом, 4 ась!~ — !! еь ~~ ) =Р() — р) !! е„'~!'+р'е УУ~ е~+, (68) Поскольку предполагается, что вектор е4 ненулевой и матрица УУт является положительной полуопределенной, то 1 ~еь Ц') 1!еь~, ~ р, если О<р«-Е Таким образом, последовательность Це,~Р, Це,Ц',... будет монотонно убывающей и должна сходиться к некоторому предельному значению ЦеЦ'. Однако в случае рассматриваемой сходнмости е4 должно сходиться к нулю, так что все положительные компоненты еь должны сходиться к нулю.
И поскольку е~ьЬ= =О для всех й, отсюда следует, что все компоненты вектора еь должны сходиться к нулю. Таким образом, при условии, что ОС <р«! и выборки линейно разделяемы, аь будет сходиться к вектору решения при й, стремящемся к бесконечности. Если на каждом шаге проверяются знаки компонент вектора Уаь н алгоритм останавливается при условии, что они положительны, ненулевые компоненты вектора е; являются положительными компонентами вектора еь. Поскольку матрица УУт симметрична и равна произведению (УУт)' (УУт), третий член упростится до следующего выражения: '8 р (УУт — 1) е~+ й* =р'е~+'(УУт — !)'(УУт — !) е~+ = = р' )) е'„)~' — р'е~'УУте~. Гя.
5. Линейные раедееякяиие 4 нкяии 1Ва то фактически получаем разделяющий вектор в случае конечного числа шагов. Это следУет из того. факТа, что г'а,=Ья+ен н что компоненты вектора Ьд никогда не убывают. Таким образом, если Ь ге является наименьшей компонентой вектора Ь, и если ея сходится к нулю, то вектор ея должен попасть в гнперсферу ~ ~ееЦ=Ь ги после конечного числа шагав, пРи котоРом )еаи)О. ХотЯ в целЯх УпРощения доказательства условия остановки были исключены, указанное условие должно всегда применяться на практике. зтЬЗ. ПОВЕДЕНИЕ В СЛУЧАЕ НЕРАЗДЕЛЯЕМЫХ МНОЖЕСТВ Если только что приведенное доказательство сходимости рассмотреть с целью выяснения использования предположения о разделяемости, то окажется, что данное предположение было использовано дважды.
Во-первых, было использовано соотношение еАв=О, чтобы показать, что либо еи=О при некотором конечном й, либо е+я никогда не станет нулевым и коррекции не прекратятся. Во-вторых, такое же условие было использовано с целью показать, что если е$ сходится к нулю, то еи тоже должно сходиться к нулю. Если выборки линейно не разделяемы, то нз этого больше ие следует, что прн е+», равном нулю, еи тоже должно быть равным нулю. Действительно, для задачи с иеразделяемым множеством вполне можно получить ненулевой вектор ошибки с положительными компонентамн.
Если это происходит, алгоритм автоматически останавливается и обнаруживается, что выборки неразделяемы. Что получается, если образы неразделяемы, а ее никогда не обращается в нуль? В данном случае все же выполняются ея+, — — ея+ 2р(у)ет — 1) ее+, (67) 4(Ц иЦ Ц яееЦ) 1( р)Ц яЦ +" Таким образом, последовательность ЦеДе, Це,Ц', ...
все еще сходится, хотя предельное значение ЦеЦе может не быть равным нулю. Поскольку условие сходимостн требует, чтобы вектор е3 сходился к нулю, можно сделать заключение, что либо ее=О при некотором конечном й, либо е'„сходится к нулю, тогда как значение ЦеиЦ отличается от нулевого.
Таким образом, алгоритм Хо — Кашьяпа дает разделяющий вектор для случая разделяемых множеств и явно обнаруживает неразделяемость для случая неразделяемых множеств. Однако не существует ограничения числа шагов, необходимых для обнаружения неразделяемости. ь.у.
Прои»дур»» Хо — Кашьяпа !83 Е.ззи НЕКОТОРЫЕ СВЯЗАННЫЕ ПРОЦЕДУРЫ Если записать равенство У» =(У'У)-'У' и использовать соотношение У'е» вЂ” — О, то алгоритм Хо — Кашьяпа можно представить в виде Ь, ) О, в остальном произвольно, а, =У»Ь„ Ь»ь, — — Ь»+р (е»+ ~ е»~), а»ь, = а»+РУ» ~ е» (, где, как обычно, (69) е»= У໠— Ь». (70) Таким образом, ~( е»+, !)» = ~ е» ~' (р'У К У'У К У вЂ” 2рУ КУ»+ 1) ) е* ~ и (~е»'й» вЂ” 'ве», йь=(У'~е»~)'А (Уь~е»)), где А = 2РК вЂ” р~КУ»К. (72) (73) Данный алгоритм отличается от алгоритмов персептрона и релаксаций для решения линейных неравенств по крайней мере тремя свойствами: 1) он изменяет как весовой вектор а, так и вектор допуска Ь, 2) он явно обнаруживает наличие неразделяемостн, однако 3) требует псевдообращения У. Даже при однократном проведении указанного вычисления необходимо затратить некоторое время и применить специальную обработку, если матрица УЧ' вырождена.
Другой алгоритм, представляющий интерес, имеет сходство с (69), но исключает необходимость вычисления У(, Он записывается следующим образом: Ь, ) О, в остальном произвольно, а, произвольно, Ь», — — Ь»+ (е»+ ~ е» ~), (71) а»„= а»+ рКУ' ~ е» ~, где К является произвольно выбранной постоянной положительно определенной матрицей размера ь(хд. Покажем, что при правильном выборе р данный алгоритм также будет давать вектор решения за конечное число шагов, при условии что решение существует.
Более того, если решение не существует, вектор У'~е»~ либо обращается в нуль, указывая на неразделяемость, либо сходится к нулю. Доказательство проводится весьма непосредственно. В случае, когда выборки либо линейно разделяемы, либо линейно неразделяемы, соотношения (70) и (71) показывают, что е» „, = Уа»+, — Ь»+, — — (РУКУ' — 1) ~ е» ~. Гл.
З. йтииеяиые ритделяаяцие функции Очевидно, что если р положительно, но достаточно мало, матрица А будет приблизительно равна 2р!с и, следовательно, будет положительно определенной. Таким образом, если У'~еа~чьО, получим йеайз> 1~еа+зйа. Здесь следует провести различие между случаями разделяемых и неразделяемых множеств. При наличии разделяемого множества существуют векторы а и Ь>0, удовлетворяющие выражению Уа=Ь. Таким образом, если ~еа~чьО, то справедливо соотношение ~ еа ~'Уа = ~ еа ~гЬ > 0 так что вектоР Успев~ не может быть нУлевым, если еь не Равно нУ- лю.
Таким образом, последовательность !~ей', 1~еа~Р,... является монотонно убывающей и должна сходиться к некоторому предельному значению йейа. Однако в условиях рассматриваемой сходимости вектор Р !еа~ должен сходиться ') к нулю, откуда вытекает, что ~еь ~ и, следовательно, еь также должен сходиться к нулю. Поскольку еь начинается с положительного значения и никогда не убывает, отсюда следует, что а„должен сходиться к разделяющему вектору. Более того, при использовании вышеприведенного утверждения решение фактически получается после конечного числа шагов.
В случае неразделяемых множеств вектор еь может либо быть ненулевым, либо не сходиться к нулю. Может оказаться, что на не. котором шаге будет Р ~ед ~=О; это доказывает наличие неразделяемости множеств. Однако возможна и другая ситуация, при которой коррекции никогда не прекращаются. В данном случае из этого опять следует, что последовательность йезй', йене, ... должна сходиться к предельному значению 1~ейач~:0 и что вектор Рйеай должен сходиться к нулю. Таким образом, опять получаем очевидность неразделяемости в случае неразделяемых множеств.
Заканчивая разбор данной темы, коротко рассмотрим вопрос выбора р и !с. Простейшим вариантом выбора !с является единичная матрица, в случае которой А=2р! — р'У'У. Данная матрица будет положительно определенной, что гарантирует условие сходимости, если Ос рс.2/Х,„, где лт„,„является наибольшим собственным значением матрицы РУ.
Поскольку след матрицы У'У представляется как суммой собственных значений матрицы УтУ, так и суммой квадратов элементов матрицы У, то при выборе величины р может быть использована пессимистическая граница, а именно Ю,„( Х! И'. Более интересный подход состоит в выборе такого значения р на каждом шаге, котороеминимизирует выражение йеайа — йеа,да. ') Возможно, конечно, что на некотором шаге получим еа=-о, н тогда сходимость будет наблюдаться в данной точке. ддд. Проигдурм аиигдного арограммирооаиия Из соотношений (72) и (73) получаем 11 ее 11г — ~~ ее+, 11' = ~ ее ~ГУ (2р)с — РЯ УТ)т) Уг ~ ее 1.
(74) Дифференцируя по р, получаем оптимальную величину рю выражаемую отношением ~ еи 1'уеду' ~ ее ~ 1 ее 1г У оУ~У о У~ 1еи1 ' которое при й=! упрощается до выражения 11 У' ! ее 1 6' (76) 11ууе~ее ~ 11е Такой же подход можно применить для выбора матрицы )г. Заменяя )7 в соотношении (74) симметричной матрицей )с+бег и отбрасывая члены второго порядка, получаем выражение 6 (11 ео йг — 11 е„+, ~~') = ) е„) У 16)г' (7 — РУгУ)с) + +(7 — РИП)М)У !ее!.
Таким образом, уменьшение вектора квадратичной ошибки максимизируется при выборе )г= — (У'У) ', (77) Р и, поскольку рггУ'=У1, алгоритм спуска становится, по существу, аналогичным первоначальному алгоритму Хо — Кашьяпа. З.10. ПРОЦЕДУРЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5. 10.1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Методы персептроиа, релаксаций и Хо — Кашьяпа являются по сущеетву Методами градиентного спуска, приспОСОбленными для решения систем линейных неравенств. Техника линейного программирования сводится к процедурам максимизации или минимизации линейных функций, удовлетворяющих линейному уравнению и наложенным на них ограничениям в виде линейных неравенств (заметим, что решение этих неравенств является частью общего решения задачи линейного программирования).
В этом разделе будут рассмотрены два возможных подхода к решению таких задач. Для усвоения излагаемого материала от читателя не потребуется никаких предварительных знаний из области линейного программирования, хотя они могли бы оказаться полезными при решении практических задач. Классическая задача линейного программирования формулируется следующим образом: найти вектор н = (им и„..., и„)', Гл. 5, Линейные разделлюаГае фрнлиаи !88 который минимизирует линейную целевую функцию г =- и'и (78) и удовлетворяет ограничению Ан~(), (78) где а есть (тх 1)-вектор цен, (1 — 1х 1-вектор и А — 1хт-матрица. Для решения поставленной задачи может быть использован сималекс-метод; его описание можно найти в любой книге по линейному программированию. Симплекс-метод представляет собой классическую итеративную процедуру.
Его использование требует введения еще одного ограничения для вектора и, а именно н)0. (80) Если искать и в виде некоторого весового вектора а, то такое ограничение неприемлемо, так как в большинстве случаев вектор решения будет иметь как положительные, так и отрицательные компоненты. Однако если представить а в виде а =а+ — а, (81) где а+ — (! а!+ а) (82) а = — ()а~ — а), 1 (83) то и а+, и а- будут неотрицательны. Отождествляя компоненты и, например, с компонентами ач и а, мы можем наложить ограниче- ние ц- О, Если 1 достаточно велико, зги условия выполняются без труда, например если а=-0 и гг шах Ь1 ').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
