Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 30
Текст из файла (страница 30)
Очевидно, что в случае общего разложения в ряд функции я(х) можно легко прийти к совершенно нереальным требованиям в отношении процесса вычислений н необходимых данных. В случае обобщенной линейной разделяющей функции, хотя н трудно реализовать ее потенциальные преимущества, по крайней мере достигается удобство записи д(х) в виде однородной функцнн а'у. В частном случае линейной разделяющей функции вида я (х) =гик+ ~ ев;х! (3) ! =! йл. Случай двух классов можно написать Г1 х1 У= х (6) хаз шл Данный переход от й-мерного пространства х к (д+1)-мерному пространству у с математической точки зрения тривиален и тем не менее достаточно удобен. Добавление постоянной компоненты к х не нарушает соотношений в расстояниях между выборками.
Все получаемые векторы у лежат в с1-мерном подпространстве, являющемся самим х-пространством. Определяемая соотношением а'у=О гиперплоскость поверхности решений Й всегда проходит через начало координат у-пространства, несмотря на то что соответствующая гиперплоскость Н может располагаться в х-пространстве произвольным образом. Расстояние от у до Й выражается отношением 1а'у Да~~, илн 1Е(х)Ща11.
Поскольку 11а1>~!чу11, то данное расстояние меньше или в лучшем случае равно расстоянию от х до Н. При использовании указанного отображения задача нахождения весового вектора ту и величины порога в, сводится к определению одного весового вектора в. З.4. СЛУЧАЙ ДВУХ ЛИНЕЙНО РАЗДЕЛИМЫХ КЛАССОВ 5.4йк ГЕОМЕТРИЯ И ПРИНЯТАЯ ТЕРМИНОЛОГИЯ Предположим теперь, что имеется множество н выборок у„...
..., у„, часть которых помечена ов„а часть овч. Данные выборки мы хотели бы использовать для определения весов в линейной разделяющей функции д(х)=а'у. Предположим, имеется основание считать, что существует решение, для которого вероятность ошибки очень и очень мала. Тогда разумный подход будет заключаться в нахождении весового вектора, который правильно классифицировал бы все выборки. Если такой весовой вектор существует, то выборки называются линейно разделяемыми. Гк.
у. Пикейные ршдеккюсцие функции Выборка у, классифицируется правильно, если а'ус)О и у, помечен ш, или если а'ус«О и у~ помечен ш,. Можно заметить, что во втором случае ус будет классифицироваться правильно, если 0 — бссссрки класси 1 П - — сссссрки «касса с Рис. 5.6. Линейно разделяемые выборки н область решения в весовом простран- стве. а — случай с нормированием, б — случай без нормирования. Рис.
5.7. Влияние допуска на область решения. а — случай Ь=О, б — случай Ь=ЩР. В,4. Слу«ас д«дя клааса« а'( — у«)=»0. Это наводит на мысль о введении нормирования, с помощью которого будет упрощено рассмотрение случая двух классов, а именно будет произведена замена всех выборок, обозначенных символом «а„их отрицаниями. При введении указанного нормирования можно забыть об индексах и искать такой весовой вектор а, чтобы для всех выборок ныполнялось соотношение а'у, »О. Данный весовой вектор называется разделяющим вектором или вектором решения.
Можно считать, что весовой вектор а определяет точку в весовом пространстве. Каждая выборка у, накладывает ограничение на возможное расположение вектора решения. Уравнение а'у,=0 определяет гиперплоскость, проходящую через начало координат в весовом пространстве, для которой у1 является нормальным вектором. Вектор решения, если он существует, должен находиться с положительной стороны каждой гиперплоскости. Таким образом, вектор решения должен лежать в пересечении и полупространств, и любой вектор, находящийся в данной области, будет являться вектором решения, Соответствующая область называется областью решений. На рис.
5.6 изображена область решений при нормировании и без нормирования на примере двумерного случая. Из сказанного следует, что если существует вектор решения, то он не единствен. Дополнительные ограничения на вектор решения можно получить разными способами. Одна из возможностей заключается в поиске единичного вектора, который бы максимизировал минимальное расстояние от выборок до разделяющей плоскости. Другим способом является нахождение минимального весового вектора, удовлетворяющего условию а'у~~~Ь для всех 1, где Ь вЂ” положительная константа, называемая допуском. Иногда бывает удобным, чтобы выполнялось лишь условие а'у;)Ь. Как показано на рис.
5.7, область решений, получившаяся в результате пересечения полупространств, для которых а~у;)Ь)0, находится внутри прежней области и отделена от старых границ расстоянием пуф. Попытки определения вектора решения, расположенного ближе к «середине» области решения, основывались на интуитивном предположении, что полученное решение с большей вероятностью будет давать правильную классификацию новых выборок. Однако в случаях, подлежащих рассмотрению, для нас удовлетворительным будет любое решение, принадлежащееобласти решения. Основное внимание должно быть сосредоточено на том, чтобы любая используемая итеративная процедура не вызывала приближения к предельной точке, лежащей на границе. Данная задача всегда может быть решена путем введения допуска, т.
е. выполнением требования а'у,) )Ь)0 для всех 1. Ге. 5. Линейные уиейекпощие функции 5.4.2. ПРОЦЕДУРЫ, ОСНОВАННЫЕ НА МЕТОДЕ ГРАДИЕНТНОГО СПУСКА Метод, используемый для нахождения решения системы линейных неравенств аеу~)0, состоит в определении функции критерия 1(а), которая минимизируется при условии, что а является вектором решения. Данный подход сводит рассматриваемую задачу к минимизации скалярной функции, что часто можно осуществить прн помощи процедуры градиентного спуска. Принцип процедуры спуска очень прост.
Она начинается с выбора некоторого произвольного весового вектора а, и вычисления градиентного вектора Ю (а,). Следующее значение а, получается при смещении на некоторое расстояние относительно вектора а, в направлении наискорейшего спуска, т. е. вдоль отрицательного градиента. В общем случае а»+, получают нз а» по алгоритму а»+, — — ໠— р»71 (а»), (8) где р» есть положительный скалярный коэффициент, определяющий величину шага. По-видимому, такая последовательность весовых векторов должна сходиться к решению, минимизирующему функцию У(а).
Известно, что с процедурами градиентного спуска связан целый ряд проблем. В нашем случае мы сможем уйти от наиболее серьезных из этих проблем, поскольку сами будем конструировать функции, которые хотим минимизировать. Единственное, с чем мы столкнемся неоднократно, это выбор скалярного коэффициента р,, Если коэффициент р» очень мал, наблюдается слишком медленная сходимость; если Р, слишком велик, то процесс коррекций даст пере- регулирование и может оказаться даже расходящимся. Предположим, что функция критерия может быть достаточно точно аппроксимнрована разложением второго порядка: е' (а) ж е' (а»)+»КР (а — а»)+ — (а — а»)'В (а — а»), (9) гдеее является матрнцей частных производных второго порядка дЧ/да,дп;, вычисленных при условии а=а,.
Тогда, используя а»+„взятое из соотношений (8) и (9), можно получить следующее выражение: е (а»+,) м е' (а») — р» й 7/ ))е ~- — Р»»7.гей7У, нз чего следует, что функцию 1(а»+,) можно минимизировать, выбрав Р»= — ° 11 7Х !!е 7 е~1~7е' (10) 5Х Минимиеация нереентронноа Функции критерия 157 Другую процедуру спуска можно получить, если, не используя (8), выбирать а» „минимизирующее это разложение второго порядка.
Это приводит и алгоритму Ньютона, имеющему вид: аяе, = ая — 1л-Жг. (11) 5.5. МИНИМИЗАЦИЯ ПЕРСЕПТРОННОй ФУНКЦИИ КРИТЕРИЯ 5.5.1. ПЕРСЕПТРОННАЯ ФУНКЦИЯ КРИТЕРИЯ Рассмотрим теперь задачу определения функции критерий для решения линейных неравенств вида а'у; ь О. Проще всего взять в качестве функции 1(а; у„..., у„) число выборок, классифицируемых с ошибкой посредством а. Однако, поскольку данная функция является кусочно постоянной, очевидно, что она будет плохо соответствовать задаче градиентного анализа. Лучшим вариантом является функция персепперона ,1р(а) = ~ ( — а'у), уе~ где 5 (а) — множество выборок, классифицируемьех с ошибкой посред- ством а. (Если выборок, классифицируемых с ошибкой, нет, то гр полагается равной нулю.) Тан как а'у(0, если у классифицируется с ошибкой, то функция Ур (а) не может быть отрицательной. Она до- стигает нулевого значения, когда а является вектором решения нли же находится на границе области решений.
Геометричеснифунк- ция ер(а) пропорциональна сумме расстояний от выборок, класси- фицируемых с ошибкой, до границы области решениЕ На рис. 5.8 изображена функция Хр для простого двумерного случая. Поскольку ся компонента градиента 1р выражается в виде ча- стной производной д,(р1даь из формулы (12) следует, что У1р= 2' ( — у), хеЗ (12) Вообще говоря, один шаг алгоритма Ньютона обычно более эффективен, нежели шаг алгоритма простого градиентного спускадаже при оптимальном значении рю Однако если матрица 1л вырожденна, то алгоритм Ньютона неприменим. Более того, даже при условии, что матрица 0 иевырожденна, потери времени, связанные с ее обращением, могут легко свести на нет указанные преимущества. Фактически зачастую небходимость сделать несколько лишних коррекций, если в качестве р„ взято заниженное значение р, приводит и меньшим затратам времени, чем вычисление оптимального р„ на каждом шаге.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
