Просмотр

Материал из MachineLearning.

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

'''SVM (Support Vector Machine, [[машина опорных векторов]])''' — алгоритм машинного обучения, предложенный [[Вапник, Владимир Наумович|{{S|В. Н. Вапником}}]]. Парадигмой машины опорных векторов можно считать выбор наиболее близких к границе классов объектов из обучающего набора, «опорных векторов», по которым и строится опорная гиперплоскость. Изначально алгоритм позволял строить линейный классификатор с помощью минимизации ширины полосы раздела классов. Позднее были предложены методы обобщения алгоритма на случай линейно неразделимой выборки (например, введения штрафа за ошибки в функционал качества). В данной статье приведен пример решения этой задачи для линейно неразделимой выборки с использованием [[Функция ядра|{{S|функции ядра}}]] {{S|(в англоязычной литературе приём носит название ''kernel trick'')}}. == Постановка задачи линейной классификации == {{Main|Линейный классификатор}} Задана выборка <tex>X=\{(x_i,y_i)\}_{i=1}^l</tex>, где <tex>x_i</tex>-признаковое описание i-го объекта, <tex>y_i</tex> - идентификатор класса, которому принадлежит i-ый объект. В случае двух классов считаем, что <tex>y_i\in\{-1,1\}</tex> (это позволяет пользоваться функцией sgn в описании классификатора). Требуется построить классификатор вида <tex>a(x)=sign(<w,x>-w_0)</tex>, где <tex><w,x></tex> - скалярное произведение, а <tex>w,w_0</tex> - вектор и число, характеризующий данный классификатор. Можно говорить о том, что <tex>w_i</tex>-веса признаков, <tex>w_0</tex> - порог принятия решения. Если для данной выборки существуют <tex>w,w_0</tex> такие, что <tex>a(x)</tex> не ошибается на обучающей выборке, то она называется ''линейно разделимой''. В противном случае, выборка называется ''линейно неразделимой''. == Описание алгоритма == === Линейно разделимая выборка === Если выборка линейно разделима, то существует бесконечно много линейных классификаторов, не ошибающихся на ней. В алгоритме SVM максимизируется расстояние от опорной гиперплоскости до обоих классов. Отнормируем вектор нормали к разделяющей гиперплоскости <tex>w</tex> и порог принятия решения <tex>w_0</tex> так, чтобы выполнялось условие <tex>\min\limits_{i=1,l} y_i(<w,x_i>-w_0)=1</tex>. Это всегда можно сделать, поскольку, во-первых, умножение <tex>w,w_0</tex> на положительную константу не меняет классификатора, а, во-вторых, требование минимального расстояния от гиперплоскости до классов гарантирует нам, что плоскость находится на равном расстоянии от классов. Нетрудно показать, что при такой нормировке ширина разделяющей полосы может быть представлена в виде: <tex>\frac{2}{||w||}</tex>. Максимизация этой величины равносильна минимизации нормы вектора нормали. Таким образом, параметры линейного классификатора определяются из задачи квадратичного программирования: <tex>\left{<w,w>\rightarrow min\\y_i(<w,x_i>-w_0)\ge1,\qquad i=1,...,l\\ \right.</tex> === Линейно неразделимая выборка === Для линейно неразделимой выборки данная оптимизационная задача не будет иметь решения. Не отказываясь от принципа максимальности зазора, можно видоизменить задачу следующим образом. Разрешим существование неправильно классифицированных объектов, но за каждвый такой объект будем штрафовать: <tex>\left{\frac{1}{2}<w,w>+C\sum\limits_{i=1}^l\xi_i\rightarrow min\\y_i(<w,x_i>-w_0)\ge1-\xi_i,\qquad i=1,...,l\\ \xi_i\ge0,\qquad i=1,...,l\right.</tex> Используя аппарат функций Лагранжа, переходя к двойственной задаче, можно показать эквивалентность этой задачи и следующей. {{eqno|1}} ::<tex>\left{-\sum\limits_{i=1}^l\lambda_i+\frac{1}{2}\sum\limits_{i=1}^l\sum\limits_{j=1}^l\lambda_i\lambda_jy_iy_j<x_i,x_j>\rightarrow \min\limits_\lambda \\ 0\le\lambda_i\le C\quad i=1,...,l\\ \sum\limits_{i=1}^l\lambda_iy_i=0\quad i=1,...,l\right. </tex> При этом выполняются соотношения <tex>w = \sum\limits_{i=1}^l\lambda_ix_iy_i,\qquad\eta_i+\lambda_i=C,\qquad \lambda_i(1-\xi_i)=0, \qquad \xi_i\eta_i=0 \forall i:1,...,l</tex>. Решив эту оптимизационную задачу, то есть, найдя вектор <tex>\lambda</tex>, классифицируем i-ый объект следующим образом: * <tex>\lambda_i=0, \eta_i=C, \xi_i=0.</tex> : В этом случае объект <tex>x_i</tex> классифицировался правильно(т.к. <tex>\xi_i=0</tex>). Но, что важнее, вектор опорной гиперплоскости не зависит от данного объекта. Его можно исключить из выборки, и алгоритм SVM построит ту же самую разделяющую гиперплоскость. Такие объекты называются ''периферийными''. * <tex>0<\lambda_i<C, 0<\eta_i<C, \xi_i=0.</tex> : Объект <tex>x_i</tex> классифицируется правильно и лежит точно на границе разделяющей полосы. Данные объекты называются опорными граничными. * <tex>\lambda_i=C, \eta_i=0, \xi_i>0. </tex> : Данный объект может находить как в граничной полосе со стороны своего класса, так и классифицироваться неправильно. Данные объекты называются опорными нарушителями. Объекты последних двух типов и называются ''опорными векторами''. Разделяющая гиперплоскость зависит только от них, что является одним из главных преимуществ SVM. Можно ожидать, что этих векторов будет не очень много, и оставит только их в памяти, алгоритм классификации ничуть не изменится. Заметим, что на практике оптимизационная задача решается не абсолютно точно. В следствии чего периферийные объекты (представляющие собой вырожденный случай распределения параметров) почти не встречаются. Для каждого объекта вычисляется <tex>\lambda_i</tex> не равное нулю, но для большинства объектов их значение мало "в среднем". Поэтому не составляет труда отсеять периферийные объекты. Важно отметить также, что решение двойственной задачи квадратичного программирования единственно, т.к. функционал является выпуклым и множество ограничений является выпуклым. Таким образом, решив задачу {{eqref|1}}, вычислим <tex>w = \sum\limits_{i=1}^l\lambda_ix_iy_i, \qquad w_0=med\{<w_i,x_i>-y_i|\lambda_i>0,\xi_i=0, i=1,...,l\}</tex>. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены. === Спрямляющее пространство и функции ядра === Описание объекта никогда не может считаться полным, если мы работаем с задачами реального мира. Перейдём к новому описанию выборки, основываясь на её данном признаковом представлении, и в этом новом описании будем вычислять скалярное произведение. В новом пространстве (называемом ''спрямляющим пространством''), если оно большей размерности, выборка может оказаться линейно разделимой. Вычисление разделяющей гиперплоскости в спрямляющем пространстве может привести к удовлетворительному результату в исходном представлении. Однако, этого никто гарантировать не может, и более того, выбор ядра для данной практической задачи является нерешенной теоретической проблемой. Приведенные рассуждения можно записать формальным образом. <tex>\psi:X\rightarrow H</tex>, где X - исходное пространство, а H - гильбертово пространство. Описание <tex>x_i</tex> заменяется описанием <tex>\psi(x_i)</tex>. Тогда скалярное произведение <tex><x_i,x_j>_X</tex> заменяется новым скалярным произведением <tex><\psi(x_i),\psi(x_j)>_H</tex>. Однако заметим, что параметры задачи {{eqref|1}} (которую мы и хотим решить) зависят только от попарных скалярных произведений описаний объектов выборки. Это означает, что,в принципе, нам не требуется знать новые описания объектов, а только вычислять скалярное произведение между ними. Естественным образом введём следующее определение. Функция <tex>K(x,y):X\times X\rightarrow \mathbb{R}</tex> называется ''ядром'', если существует такое преобразование <tex>\psi:X\rightarrow H</tex> и <tex>K(x,y)=<\psi(x),\psi(y)>_H</tex>. В качестве ядра, конечно, подойдёт не любая функция, на вопрос о требованиях к ней отвечает ====[[Теорема Мерсера]]==== Функция двух переменных <tex>$K\(x,x'\)$</tex> является [[Функция ядра|ядром]] тогда и только тогда, когда она *симметрична, то есть <tex>$K\(x,x'\) = K\(x',x\)$</tex>; *неотрицательно определена, то есть <tex>\int_X\int_X K\(x,x'\)g\(x\)g\(x'\)dxdx' \geq 0</tex>. В данном примере мы ограничились ядрами: * <tex>K(x,y)=(<x,y>)^d</tex>, где d - натуральный параметр ''(в вычислительном эксперименте называется Poly)'' * <tex>K(x,y)=(1+<x,y>)^d</tex>, где d - натуральный параметр ''(в вычислительном эксперименте называется FullPoly)'' * <tex>K(x,y)=th(k_0+k_1<x,y>)</tex>, где <tex>k_0,k_1</tex> - положительные параметры (однако, не совсем произвольные) ''(в вычислительном эксперименте называется Sigmoidal)'' :Данное ядро отвечает классической [[Искусственная нейронная сеть|{{S|нейронной сети}}]] с сигмоидными функциями активации. * <tex>K(x,y)=\e{(-\gamma||x-y||^2)}</tex>, где <tex>\gamma>0</tex> ''(в вычислительном эксперименте называется RBF)'' :Данное ядро отвечает [[Искусственная нейронная сеть|{{S|нейронной сети}}]] с радиальными базисными функциями. == Вычислительный эксперимент == Работа алгоритма изучалась на двух выборках: сгенерированной вручную и канонической выборкой ирисов. === Нормальные распределения === Справа на рисунке приведена сгенерированная выборка, состоящая из двух классов по 30 объектов в каждом. [[Изображение:SVMnorm.png|thumb]] Алгоритм запускался на данной выборке с разными ядрами, используя процедуру [[Скользящий контроль|{{S|скользящего контроля}}]]. Для каждого из типов ядер, описанных выше, для набора значений параметров изучалось количество ошибок на обучающей выборке и на контрольной. Приведенные результаты изображены на графике, где одним цветом обозначены ядра одного типа, но с разными параметрами. По оси абсцисс - процент ошибок на обучающей выборке, по оси ординат - на контрольной. [[Изображение:SVM_synth_kernels.png]] Справа приведен увеличенный участок этого изображения, на котором отмечены только точки, отвечающие ядру с сигмоидальной активацией. [[Изображение:SVMneuro_normtest.png|thumb]] Очевидно, выделяется точка, находящаяся ближе всех к началу координат. Разделяющая прямая, построенная с помощью этого ядра изображена ниже. [[Изображение:SVMbestpartition_normtest.png]] === Ирисы Фишера === Ирисы Фишера являются одним из наиболее популярных примеров данных для задачи классификации. Это связано, в первую очередь, с тем, что количество признаков всего 5 и все они численные, а классов всего лишь 3. При этом два из классов линейно отделимы от третьего, но линейно неразделимы между собой. В данном примере для наглядности изображения данных на плоскости были взяты только два признака двух линейно неразделимых классов ирисов. Ниже приведена обучающая выборка. [[Изображение:SVM_Iris_2.png|thumb]] Алгоритм запускался по той же схеме, что и для синтетических данных. Результаты приведены на следующем графике: [[Изображение:SVM_kernels_iris2.png]] Было выбрано ядро, находящееся ближе всего к нулю на данном графике (в смысле евклидового расстояния). Алгоритм с данным ядром строит для ирисов Фишера следующую разделающую гиперплоскость: [[Изображение:SVM_Iris_best.png]] == Исходный код == Код MATLAB можно скачать здесь: [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Sechin2010SVMNonlinear/] == Смотри также == * [[ Машина опорных векторов ]] * [[ Функция ядра ]] * [[ Теорема Мерсера ]] * [[ Линейный классификатор ]] * [[ Искусственная нейронная сеть ]] * [[ Численные методы обучения по прецедентам (практика, В.В. Стрижов) ]] * [[ SVM для линейно разделимой выборки (пример) ]] == Литература == * Воронцов К.В. Лекции по линейным алгоритмам классификации * Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. Статистические проблемы обучения. - Москва, "Наука", 1974. * Cortes C., Vapnik V. Support Vector Networks. {{ЗаданиеВыполнено|Павел Сечин|В.В.Стрижов|28 мая 2010|Pasechnik|Strijov}} [[Категория:Практика и вычислительные эксперименты]] [[Категория:Классификация]] [[Категория:Линейные классификаторы]]

• Шаблон:Eqno
• Шаблон:Eqref
• Шаблон:Main
• Шаблон:Mbox
• Шаблон:Nobr
• Шаблон:S
• Шаблон:Well
• Шаблон:ЗаданиеВыполнено

Возврат к странице SVM для линейно неразделимой выборки (пример).