Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 32
Текст из файла (страница 32)
у е зея Таким образом, если выборки являются линейно разделяемыми, то все возможные виды корректирующих векторов составляют линейно разделяемое множество, н если ря удовлетворяет соотношениям (2!) — (23), то последовательность весовых векторов, получаемая посредством алгоритма градиентного спуска для („, всегда будет сходиться к вектору решения. Интересно заметить, что условия, налагаемые на ря, удовлетворяются в тех случаях, когда р» является положительной константой и когда ря убывает как 1/й или даже возрастает с ростом й.
Вообще говоря, предпочтение следует отдавать ря, уменьшающемуся с течением времени. Это замечание становится особенно существенным, когда есть основание считать, что множество выборок линейно неразделяемо, поскольку в данном случае уменьшается отрицательное влияние нескольких «плохих» выборок.
Однако то, что в случае разделяемых выборок при увеличении р, получение решения оказывается все же возможным, кажется довольно странным. Из данного наблюдения вытекает одно из различий между теоретическим и практическим взглядами на эту проблему. С теоретической точки зрения представляется интересным тот факт, что решение можно получить при наличии конечного числа шагов в случае любого ограниченного множества разделяемых выборок, прн любом начальном весовом векторе а„ при любом неотрицательном значении допуска Ь и при любом скалярном коэффициенте ря, удовлетворяющем соотношениям (21) — (23), С практической точки зрения желательно производить разумный выбор указанных величин.
Рассмотрим, например, допуск Ь. Если Ь намного меньше рДу"1Р, т. е. той величины, на которую возрастает аяуя в результате коррекции, то очевидно, что Ь будет оказывать совсем малое влияние. Если Ь намного превосходит величину ряйунй', то потребуется большое число коррекций, чтобы добиться выполнения условия аяуз)Ь. Часто в качестве компромиссного подхода используют величину, близкую к ря11у"й*. Кроме указанных вариантов выбора р„и Ь, большое влияние на результат может оказывать масштабирование компонент вектора у'. Наличие теоремы сходимости не избавляет от необходимости сознательного подхода при использовании данных методик. Гл, Ю. Линейные Ллзоеллмглие Фунняии 5.6. ПРОЦЕДУРЫ РЕЛАКСАЦПП 5.6.1.
АЛГОРИТМ СПУСКА ,г' (а) = ~ (агу)з, у ел! (25) где 9 (а) опять обозначает множество выборок, классифицируемых с ошибкой посредством а. Так же как и в случае функции г'„, основное внимание при использовании функции /» сосредоточивается на выборках, классифицируемых с ошибкой. Главное различие указанных функций состоит в том, что градиент функции 1е является непрерывным, в то время как градиент функции 1р таким свойством не обладает. К сожапению, функция г'е настолько сглажена вблизи границы области решений, что последовательность весовых векторов может сходиться к точке, лежащей на границе. Особое неудобство связано с некоторыми затратами времени, требующимися для определения градиента вблизи граничной точки а=б.
Другая неприятность, связанная с функцией ), состоит в том, что величина данной функции может быть превышена за счет наиболее длинных векторов выборок. Обе зти трудности можно обойти путем применения функции критерия ') следующего вида: 1 чч (агу †)з 2 ~л !)у)!з (26) где 9'(а) теперь обозначает множество выборок, для которых атун-Ь. (Если У(а) определяет пустое множество, то полагаем г', равной нулю.) Таким образом, функция г',(а) никогда не бывает отрицательной и обращается в нуль в том н только том случае, если ат(у))Ь для всех выборок.
Градиент функции г', задается выражес пнем ))у)!' з) Нормирование посредством введении Щ)з упрощает выбор ра. Фактически пронзаодитсв выбор ре — -1, соответствующего оптимальному значению, определиемому соотношеииеи 110). ценный вопрос исследуется в дальнейшем в задаче 13. Функция критерия г' (а) отнюдь не представляется единственной функцией, которую можно построить с целью минимизации в случае, когда а является вектором решения. Близким, но имеющим отличие представляется выражение вида 165 6.6. Працедурм релаксаций так что основной алгоритм спуска представляется в следующем виде: а, произвольно, Ь вЂ” а~у а„э,=а„+р„, —,у. 11у1Р (27) Как и раньше, будем считать, что более простое доказательство сходимости получается при условии, что выборки рассматриваются поодиночке, а не все сразу.
Ограничимся также случаем, когда рд=р. Таким образом, можно опять перейти к рассмотрению последовательности у'„у',..., образованной из выборок, требующихся для коррекции весовых векторов. Правило коррекции по одной выборке аналогично соотношению (27) и записывается в виде а, произвольно, ь — аЬуа а„,=а„+ р у', 11 у' 11' (28) где алсу' -Ь для всех й. Данный алгоритм известен под названием правила релаксаций н имеет простую геометрическую интерпретацию. Величина Ь вЂ” аеу" ел= 11 у' 11 Если Р(1, то пРоизведение ал'„Ул остаетсЯ все же меньшим, чем Ь; если же р~1, то ал+,ул будет больше Ь. Данные условия носят название недорелаксация и перерелаксацил соответственно. Обычно р выбирается из интервала 0(р(2. 5.6.2.
ллОКАЗАТЕЛЬСТВО СХОДИМОСТИ При применении правила релаксаций к множеству линейно разделяемых выборок число коррекций может быть ограниченным или неограниченным. Если число коррекций ограничено, то, естественно, получаем вектор решения. Если число коррекций не огра- представляет собой расстояние от аь до гиперплоскости асул=Ь.
Поскольку отношение уЧ1у"11 определяет единичный нормальный вектор для данной гиперплоскости, то а„содержащееся в уравнении (28), должно смещаться на некоторую часть р этого расстояния от аи к гиперплоскости. Если р=1, тоаь смещается точно до гиперплоскости, так что происходит «релаксация (ослабление— ред.) напряжения», вызванного неравенством аЬу"(Ь, После коррекции по формуле (28) получаем (а„'.,у" — Ь) = (1 — р) (а„'у" — Ь).
Г*. 5. Линвлные разделяющие Фувсчии ничено, то будет показано, что аь сходится к предельному вектору, лежащему на границе области решений. Поскольку область, в которой а'у>6, включена в ббльшую область, где а'у>0 при 6>0, это означает, что аь войдет в эту ббльшую область по меньшей мере один раз, в конечном счете оставаясь в этой области при всех Й, ббльших некоторого конечного й,. Доказательство связано с тем фактом, что если а представляет собой любой вектор, лежащий в области решений, т. е.
удовлетворяющий условию а'у;>6 при всех 1, то с каждым шагом вектор а приближается к вектору а. Данное утверждение сразу же следует из соотношения (28), поскольку ~~аэ+,— а 11' = )! аэ — а ~~' — 2Р (а — аь) У'+Р' (ь .(.~) - , , (ь айуэ) Пу'П' 11у'П' (а — а„)'у' > 6 — а~у' О, так что (~а э,— а ~~'(~~ аз — а ~!' — р(2 — р) (Ь вЂ” аьуэ)~ 11 у'2' Поскольку р изменяется в интервале О~р«2, из этого вытекает, что 11аэ+,— а~К~!аь — а1!. Таким образом, векторы последовательности а„а„...
все более приближаются к а, и в пределе, когда А стремится к бесконечности, величина расстояния 1~аь — а11 будет близка к некоторому предельному значению г(а). Отсюда следует, что при стремлении й к бесконечности аь располагается на поверхности гиперсферы с центром а и радиусом г(а). Поскольку данное утверждение справедливо для любого а, находящегося в области решений, предельйое аь лежит на пересечении гиперсфер, центрами кото ых являются все возможные векторы решений. окажем, что общим пересечением данных гиперсфер является единственная точка, лежащая на границе области решений. Предположим сначала, что существуют по крайней мере две точки а' и а", принадлежащие общему пересечению. Тогда выполняется равенство 11а' — а!1=11а" — а11 для каждого а, находящегося в области решений.
Но это означает, что область решений располагается в (Ы вЂ” 1)-мерной гиперплоскости, содержащей точки, равноудаленные от а' и а", тогда как известно, что область решений является й-мерной. (Точная формулировка такова: если а'у;>О при 1=1,..., а, то для любого и'-мерного вектора ч справедливым будет выражение (а+зч)ту~>Одля(=1,..., п при условии, что е достаточно мало.) Таким образом, аь сходится к единственной точке а. Указанная точка, конечно, не находится внутри области решений, ибо тогда после- 167 З.7. Поведение еРецееуР довательность была бы конечной. Она также не находится и вне данной области, поскольку в результате каждой коррекции вектор веса смещается на величину р, умноженную на его расстояние до граничной плоскости, так что навсегда фиксированного минимально возможного расстояния„на которое вектор может приближаться к границе, не существует.
Отсюда следует, что предельная точка должна лежать на границе. З.7. ПОВЕДЕНИЕ ПРОЦЕДУР В СЛУЧАЕ НЕРАЗДЕЛЯЕМЫХ МНОЖЕСТВ Процедура, основанная на правнле постоянного приращения, н процедура релаксаций дают ряд простых методов для нахождения разделяющего вектора в случае линейно разделяемых выборок. Все зти методы называются процедурами коррекции ошибок, поскольку они вызывают изменение весового вектора в том н только том случае, когда появляется ошибка. Успех указанных процедур обусловлен в основном именно методичным поиском безошибочного решения. На практике возможность непользования этих методов следует рассматривать только в том случае, если можно считать, что уровень ошибки для оптимальных линейных разделяющих функций мал. Конечно, даже в случае, когда можно найти разделяющий вектор на основании конструктивных выборок, не следует предполагать, что полученный классификатор будет хорошо справляться с независимыми проверочными данными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
