Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 38
Текст из файла (страница 38)
Если обозначить значение разделяющей функции после коррекции через д'(х), то алгоритм формирования данной функции может быть записан в следующем виде: п(х)+К(х, ха), если хь обозначен е, и д(ха)(0, о (х) я(х) — К(х, х„), если х, обозначен ю, и д(ха) ~0,(86) Ы(х) в противном случае. Данное правило коррекции ошибок имеет много общего с правилом постоянных приращений. Природа этой связи станет вполне понятна, если представить К(х, хь) в виде симметричного конечного разложения Р К(х, х„) = ~ уг(х) рг(хь) =уьгу, 1=1 (87) где у=у(х) и уа=у(хь). Подставив данное выражение в (85), получим я(х) =агу, где л а = ~л~~ дгуг г=г г) Если пики потенциальной функции являются достаточно острыми (по сравнению с расстояниями между ними), то всегда можно изменить величины зарядов таким образом, чтобы все выборки классифвцировались правильно.
Еслк же потенциальная функция сравнительно полога и имеет медленно спадающие вершины, то безошибочнаи классификация не может быть гарантирована. Более того, алгоритм для вычисления д' (х) иа основе использования и (х) представляет лишь ненормированное правило постоянных при- Гл. б. Линейные раэделяюи(ие функции 194 ращений; а+у», если у, помечено символом пт, и агу»(0, а'= а — у», если уа помечено символом итз и а'уа)~0, а в остальных случаях. Таким образом, если К(х, ха) может быть представлено в виде выражения (87), сходимость доказывается точно так же, как и для правила постоянных приращений. Более того, является очевидным, что при использовании других процедур, таких, как метод релаксаций, метод наименьшей квадратичной ошибки и метод стохастической аппроксимации, можно сразу же получить «параллельные» им процедуры, основанные на применении потенциальных функций; при этом доказательства сходимости таких «параллельных» процедур совершенно аналогичны.
Метод потенциальных функций, конечно, ие ограничивается использованием только таких функций, которые имеют вид конечной суммы. Любая подходящая для наших целей функция, такая, например, как аз К(х, х)= итти кн нли )('(х, х.) =ехР~ —,—,~)~х — ха'1)'1 1 может быть выбрана в качестве потенциальной '); разделяющая функция получится, если рассматривать выборки последовательно: х', х', ..., х', ...
и использовать какую-либо итеративную процедуру, например йа+,(х) =да(х)+г„(х, х") 7('(х, ха), где г, — некоторая функция ошибки. При практическом применении метода потенциальных функций встречаются те же трудности, что и при использовании оценок парзеновского окна. Необходимо очень внимательно отнестись к выбору потенциальной функции, чтобы получить хорошую интерполяцию между точками выборки.
При большом числе выборок появляются значительные трудности, связанные с процессом вычисления. Вообще использование метода потенциальных функций наибо- х) Те, кто знаком с интегра.чьиыми уравнениями, заметят сходство между К(х, хк) и ядром К (з, 1). При определенных условиях симметричные ядра можно представить в виде бесконечных рядов х~;(з)99(г)/дь где фг и дг — собственные функции и собственные значения К соответственно (см.
Курант и Гильберт, гл. 1И, 1953). Известные ортогональные функции математической физики являются собственными функциями симметричных ядер, и их часто рекомендуют использовать при формировании потенциальных функций. Однако зги рекомендации вызваны скорее математическим изяществом, чем практической пользой.
Ю.12. Обобщении для слован мноеик классов 195 лее оправдано в случае, когда либо число выборок невелико, либо размерность х достаточно мала, чтобы функцию д(х) можно было представить в виде таблицы дискретных значений х. 5.12. ОБОбЩЕНИЯ ДЛЯ СЛУЧАЯ МНОГИХ КЛАССОВ 5.12.1. МЕТОД КЕСЛЕРА У нас пока не существует единого универсального метода, с помощью которого можно было бы распространить все процедуры для двух классов на случай многих классов.
В разд. 8.2.2 было приведено определение классификатора для случая многих классов, названного линейной машиной; классификация образов осуществляется линейной машиной путем вычисления с линейных разделяющих функций яс(х)=чв,'х+ш;„1=1, ..., с, при зтом х относится к тому классу, которому соответствует наибольшая д, (х), Это довольно естественное обобщение с точки зрения результатов, полученных в гл. 2 для задачи с многомерным нормальным распределением. Следующий шаг, очевидно, может быть связан с обобщением понятия линейной разделяющей функции; введем вектор-функцию у(х), зависящую от х, и напишем выражение дс(х)=а,'у, 1=1...с, (88) где х снова ставится в соответствие со;, если ле(х) >81(х) для всех )~Е. Обобщение процедур, рассмотренных для линейного классифи. катора двух классов, на случай линейной машины для многих клас.
сов наиболее просто осуществляется при линейно разделяемых выборках, Пусть имеется множество помеченных выборок у„у„... ...., у„, причем число л, выборок, принадлежащих подмножеству 1Уо помечены о»о число и, выбоРок, пРинадлежащих подмножеству 81„помечены со„... и число пе выборок подмножества гУ, помечены со,. Говорят, что данное множество линейно разделяемо в том случае, если существует такая линейная машина, которая правильно классифицирует все выборки. Далее, если зги выборки линейно разделимы, то существует множество весовых векторов а„..., а„таких, что если у» Е 81о то а,'.у» > агу» (89) для всех )Ф1.
Одним из преимуществ такого определения является то, что, несколько видоизменив неравенства (89), можно свести задачу для многих классов к случаю двух классов. Предположим на минуту, Гн. 5. Линейные разденнеицие 4уккции что у ~ бо так что выражение (89) принимает вид а,'у — ае~у) О, 1=2, ..., с. (90) Это множество (с — 1) неравенств можно интерпретировать как тре- бование существования се(-мерного весового вектора а, а, а= который бы правильно классифицировал вее (с — 1) се(-мерных вы- борок Г О О У вЂ” У О У ° ~ Чне Чее = С вЂ” У~ вц2.2.
ПРАВИЛО ПОСТОЯННЫХ ПРИРАЩЕНИЙ В данном пункте для доказательства сходимости обобщенного на случай линейной машины правила постоянных приращений используется метод Кеслера. Пусть имеется множество а линейно разделяемых выборок у„..., у„; сформируем на их основе бесконечную последовательность, в которой каждая из выборок по- В более общем случае, если у ~Юо то формируется (с — 1) сегмерных выборок н)ы с разбиением Чи на се(-мерные подвекторы, причем 1-й подвектор равен у, 1ьй равен — у, а все остальные являются нулевыми. Очевидно, что если а'Чм иО для всех 1~1, то линейная машина, соответствующая компонентам вектора а, будет правильно классифицировать у.
В описанной процедуре, которая была предложена К. Кеслером, размерность исходных данных увеличивается в с раз, а число выборок — в с — 1 раз; это делает ее непосредственное применение достаточно трудоемким и поэтому малопригодным. Значение же данного метода определяется тем, что он позволяет свести процедуру коррекции ошибок в задаче многих классов к случаю двух классов, а последнее чрезвычайно важно для доказательства сходнмости указанной процедуры. б.72. Обода»гния для сгуигя многих к»ассов 197 является бесконечное множество раз. Обозначим через Е» линейную машину с весовыми векторами а, (и),..., а,(й). Начиная с исходной, произвольно выбранной линейной машины Ь, и используя последовательность выборок, сформируем последовательность линейных машин, сходящуюся к решающей линейной машине, причем зта последняя будет классифицировать все выборки правильно.
Предложим правило коррекции ошибок, в соответствии с которым изменения весов производятся только в том случае, если текущая линейная машина делает ошибку прн классификации одной из выборок. Обозначим й-ю выборку, которой необходима коррекция, через у» и предположим, что у" ~ 9;. Поскольку коррекция вызвана ошибкой при классификации у', то должно существовать по крайней мере одно )чй, для которого а; (н)»у»(а,,(л)'у».
(91) Тогда правило постоянных приращений для коррекции А» примет вид а;(й+1) =-а;(7г)+у», а7(й+1) =а7(й) — у', а,(й+1) =-а,(й), 1Ф1 и 1~1. (92) а, (7г) (93) а, (й) Для каждой выборки у ~ З; существуют с — 1 выборок»)м (правило их формирования описано в предыдущем пункте).
В частности, для вектора у", удовлетворяющего неравенствам (91), существует вектор у» -1 » Чд Покажем теперь, что данное правило должно привести к решающей машине после конечного числа коррекций. Доказательство проводится достаточно просто. Каждой линейной машине соответствует весовой вектор 198 Гя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
