Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 37
Текст из файла (страница 37)
Однако такой случай не представляет з) В терминах линейного программирования любое решение, удовлетворяющее налагаемым ограничениям, называется допустимым реиынием. Допустимое решение, аля которого чксло ненулевых переменных не превосходит числа ог- 5.10хь случАЙ линейнО РАзделяемых мнОЖестВ Пусть имеется множество из и выборок у„..., у и требуется найти весовой вектор а, удовлетворяющий неревенству а'уг) )Ь! 0 при всех 1. Как сформулировать эту задачу в терминах линейного программирования? Один из способов состоит в введении так называемой искусственной переменной 1 с помощью выражений а'уг+Г~Ь, и Г вО.
б.10. Процедрры лилейного программирования интереса с точки зрения решения поставленной задачи. Нас интересует как раз случай, когда 1=-0, т. е. тот случай, когда 1 прнннмает минимальное значение, прн которрм еще выполняется условие 1= О, Таким образом, мы приходим к следующей задаче: найти минимальное значение 1 среди всех 1 н а, удовлетворяющих условиям агу;+1~6, н 1~0.
Если в результате 1 окажется равным нулю, то выборки линейно разделяемы н полученный весовой вектор н будет искомым. Если же 1 окажется положительным, то разделяющего вектора не существует н, следовательно, выборки линейно не- разделяемы. Формально наша задача состоит в том, чтобы найти вектор н, минимизирующий целевую функцию г=игн н удовлетворяющий ограничениям Аа )ф н и )О, где с н= а-, ез= О Таким образом, задача линейного црограммнровання содержит из=а+1 переменных н 1э вограннченнй плюс ограничения снмплекс-метода а-вО. Симплекс-метод позволяет за конечное число шагов найти минимальное значение целевой функции г=атп =1; одновременно с этим определяется н вектор й, доставляющий з это значение. Если выборки линейно разделяемы, то минимальное значенне1равно нулю, н вектор решения а можетбыть получен нз ц.
Если же выборки неразделяемы, то минимальное значение будет положительным числом. Полученное значение вектора н обычно не прнгодно в качестве приближенного решения, но по крайней мере позволяет получить доказательство неразделяемостн взятых выборок. бпо.з. МИНИМИЗАЦИЯ ПЕРСЕПТРОННОИ ФУНКЦИИ КРИТЕРИЯ В большинстве прикладных задач классификации образов нельзя а рлоп' предполагать, что выборки линейно разделяемы. Это относится, например, к случаю, когда образы неразделяемы, н все же требуется найти весовой вектор, с помощью которого можно было бы правильно класснфнцнровать как можно большее число выборок. К сожалению, количество ошибок не является линейной функцией компонент весового вектора, а ее минимизация не явля- раннченна (ие считая специального требования симплекс-метода о иеотрнцательностн переменных), называется базисным допустимым реииниеи.
Таким образом, решенве а=б и 1=шахЬг является базисным допустимым решеняем. Наличие такого решення упрощает применение симплекс-метода. Гл, б. линейные раздмяющие Функции 188 ется задачей линейного программирования. Однако оказывается, что задачу мнннмизации персептронной функции критерия можно сформулировать как задачу линейного программирования. Поскольку минимизация такой функции критерия дает разделяющий вектор в случае разделяемых множеств н приводит к разумному решению в случае, когда выборки неразделяемы, такой подход является чрезвычайно привлекательным.
Базисная персептронная функция критерия задается следующим выражением: ~,, (а) =,~ ~( — а'у), (12) УЕВ где 9 (а) — множество выборок, классифицируемых с ошибкой по- средством вектора а. Для того чтобы исключить тривиальное реше. нне а=О, введем положительный вектор допуска Ь и напишем вы- ражение ,1'р(а) = г,' (Ь; — а'у ), У,ЕЗ (84) при ограничениях Очевидно, что для любого фиксированного значения вектора а минимальное значение г в точности равно l'(а), поскольку при имеющихся ограничениях мы получим наилучший результат, если положим г;=шах (О, Ь| — а'у~). Если теперь найти минимум г по всем возможным значениям 1 н а, то мы получим минимально возможное значение Ур(а).
Таким образом, задачу минимизации 1'(а) мы свели к задаче минимизации линейной функции г при наличии ограничений в виде линейных неравенств. Приняв п„за а-мерный единичный вектор, приходим к следующей задаче с т=2с1+л переменными и р=а ограннчеииямн: минимизировать а'и прн условии где у~ Е 6', если а'у~ -Ьь Очевидно, что 1р является не линейной, а кусочно линейной функцией от а, н поэтому непосредственное применение метода линейного программирования здесь невозможно.
Однако если ввести а искусственных переменных н соответствующих им ограничений, то можно построить некоторую эквивалентную линейную целевую функцию. Рассмотрим задачу отыскания векторов а и $, минимизирующих линейную функцию 189 6.10. Процедуры еинеяноео нроераммироеанин Ан е р и п)0, где Уе е А= и= а , а= 0 , р= — у„б О...1 и Уи Выбор а=О и 11 — — Ье обеспечивает базисное допустимое решение, которое позволяет теперь применить алгоритм симплекс-метода. В результате за конечное число шагов может быть определено то значение а, которое доставляет минимум 1р(а). 5.10.4.
ЗАМЕЧАНИЯ Мы описали два способа постановки задачи отыскания линейной разделяющей функции как задачи линейного программирования. Существуют и другие способы, среди которых особый интерес с вычислительной точки зрения представляют те методы, которые сформулированы на основе двойственной задачи. Вообще говоря, методы типа симплекс-метода есть не что иное, как несколько усложненные методы градиентного спуска, предназначенные для отыскания экстремумов линейных функций при наличии ограничений в виде линейных неравенств.
Подготовка алгоритма линейного программирования для решения на ЭВМ обычно представляет собой более сложную задачу по сравнению с такой же операцией, примененной для более простых процедур спуска, которые мы описывали ранее. Однако блоки общего назначения, составленные для задачи линейного программирования, часто могут быть использованы либо без всяких изменений, либо с очень незначительными изменениями в других задачах. Прн этом сходимость процесса гарантирована как в случае линейной разделяемости, так и в случае, когда исходные выборки неразделяемы. Различные алгоритмы для отыскания линейных разделяющих функций, описанные в данной главе, сведены в табл.
5А. Естественно спросить, какой же из этих алгоритмов является наилучшим. Однозначного ответа на этот вопрос дать нельзя. Выбор подходящего алгоритма определяется такими фактами, как необходимые характеристики, простота программирования, количество и размерность выборок.
Если линейная разделяющая функция обеспечивает незначительный процент ошибок, любая из этих процедур при корректном ее применении позволит получить хорошее качество решения. .„.хо...,$„"с в т к т И- сс о И сс!! к к Ю о к сс л о. о. !! о В а 2 + !! сц !! 6 ! о и! !! И". !сч !! и ~«с х аоох к х ох онох Ь хаасс а'со Лх о мИ8„»9 ох ах хааа х нанон о. хна хххоо со сБО *хо о а хоЛ нхнх 'х м а хан ~~3 сС о со И 8 о х а осс ~~н хИ Р аххо ах на ао х "хй Ф о ан О Й~ о ка н хн с Ях о я х д о.- х ~а х х о ъ к ° с ! о.
-1- + а ! И к ! сс + х к»к а а а к о. + + к а а !! ! к М + х ы во хйа аха о хр х в.:„ хЯ а вы о свх а а ах хо х а вохюЗ 4хИай воо ы а вы я ы х х~, а х! й'И. а во ох вова а йа«~й о ау ы аа аов о. о в 2 ы х а,Я хааа ~~в а х оаа ы а ,„Ц а х И х~ овй ы ~~ о Л Чл о в— + 3х а о + + м а л + а ах л + о. ! +ал а а .а о, х, !! !! !! а в в а ! ы !! !! х' ! ':3" х ф л "ъ л ! !! в х йх Кй йй ы ы о ох ао а $ :с а а а х в двБ йй ° ~х ао а айх ф о х а х о.ы аЗ х хахов а ы ъ айаа ыха д ад а ы хх И х а ох ааааа ххо Я ц .ц.
о хааа ы,ыо.х ю ав а х о ай хо»ых их ва "аа а "а оа'аа охло' йЦ$ вхх а З ~аав а а а аа ы Ь вЂ” ха в а $ о о. Ма ох д хы ай о „"" л ы1х а ха ы ахи хах а ох „о ахх хо хха в ы а " о.а и Ы ы ф о х о о.а вью ,а оо о йоши к йо а а х о х ох, Р Бахо", х Р х о 192 Ге, д. Линейные разделяющие финикии Рис.
5.12. Поле распределения нотенциала как разделяющая функция. Π— выборки класса 1, Х вЂ” выборки класса 2. помечено символом оз„то, возможно, функцию, описывающую распределение электростатического потенциала в,.тшом поле, можно будет использовать в качестве разделяЮщей фуйкцйи (рис. 5.12). Если потенциал точки х, соэдаваемый еднниинйм"заррюдом, находящимся в точке хо равен К(х, хз), то потейциал, создаваемый и зарядами в точке х, определяется выражением л д(х)= ~~~~ ~ЯК(х, хз).
з=з (85) Потенциальннпя функция К (х, хз), используемая в классической физике, обратно пропорциональна величине ' [[х — хз[[. Имеется и много других функций, которые с таким же успехом могут быть использованы для наших целей. Существует очевидная' аналогия между функцией К(х, хз) и функцией йарзеновсиого окна зр [(х— — хз)/ы; по своемУ видУ Разделдю1цан фУнццин Я(х) очень похожа на разность оценок парзеновского окна для случая двух б.11. ИЕтОД ПОтв1ЦИЛЛЬННХ ФННЦЦНй Рассмотрение способов определения линейных разделяющих функций будет неполным, если мы не упомянем о методе потенциальных функций. Данный подход тесно связан с некоторыми уже рассмотренными нами методами, такими, как оценки парзеновского окна, метод персептрона и метод стохастнческой аппроксимации, Толчком к созданию метода потенциальных функций послужило следующее обстоятельство; если выборки хз представлять себе как точки некоторого пространства и в эти точки поместить заряды соответственно+дз, если хз помечено символом озз, и — йп если хз бяд Меглод потеяциольяык функций 193 плотностей.
Но поскольку нашей задачей является лишь построение нужной разделяющей функции, в этом смысле значительно меньше ограничений существует при выборе.-нотенциальной функции, чем при выборе функции окна. Наиболее часто используется такая потенциальная функция, которая имеет максимум при х=х, и монотонно убывает до нуля при 11х — хг) оо. Однако в случае необходимости и эти ограничения можно снять. Пусть имеется множество из а выборок, а разделяющая функция сформирована в соответствии с выражением (85). Предположим далее, что при проверке обнаружено, что некоторая выборка, скажем хь, посредством функции д (х) классифицируется с ошибкой. Попробуем исправить ошибку, изменив немного величину дд '). Предположим, что значение у„увеличивается на величину единичного заряда, если х„помечено символом ю„и уменьшается на такую же величину, если хь помечено символом ю,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
