|
|
| Строка 1: |
Строка 1: |
| - | '''SVM (Support Vector Machine, [[машина опорных векторов]])''' - алгоритм машинного обучения, предложенный [[Вапник, Владимир Наумович|{{S|В. Н. Вапником}}]]. Парадигмой машины опорных векторов можно считать выбор наиболее близких к границе классов объектов из обучающего набора, "опорных векторов", по которым и строится опорная гиперплоскость.
| |
| - |
| |
| - | В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной.
| |
| - |
| |
| - | == Постановка задачи линейной классификации ==
| |
| - | {{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>
| |
| - | Используя аппарат функций Лагранжа, переходя к двойственной задаче, можно показать эквивалентность этой задачи и следующей:
| |
| - | {{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 \\ \lambda_i\ge 0\quad i=1,...,l\\ \sum\limits_{i=1}^l\lambda_iy_i=0\quad\right. </tex>
| |
| - |
| |
| - | Таким образом, решив оптимизационную задачу {{eqref|1}}, то есть, найдя вектор <tex>\lambda</tex>, вычислим <tex>w = \sum\limits_{i=1}^l\lambda_ix_iy_i, \qquad w_0=med\{<w_i,x_i>-y_i,\lambda_i>0, i=1,...,l\}</tex>. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены.
| |
| - |
| |
| - | == Смотри также ==
| |
| - | * [[ Машина опорных векторов ]]
| |
| - | * [[ Линейный классификатор ]]
| |
| - | * [[ Численные методы обучения по прецедентам (практика, В.В. Стрижов) ]]
| |
| - | * [[ SVM для линейно неразделимой выборки (пример) ]]
| |
| - | == Литература ==
| |
| - | * Воронцов К.В. Лекции по линейным алгоритмам классификации
| |
| | | | |
| | {{Задание|Алексей Морозов|В.В.Стрижов|28 мая 2010}} | | {{Задание|Алексей Морозов|В.В.Стрижов|28 мая 2010}} |
