SVM для линейно разделимой выборки (пример)
Материал из MachineLearning.
(Новая: '''SVM (Support Vector Machine, машина опорных векторов)''' - алгоритм машинного обучения, предложенный [[Вапник, В...) |
|||
| Строка 24: | Строка 24: | ||
Используя аппарат функций Лагранжа, переходя к двойственной задаче, можно показать эквивалентность этой задачи и следующей: | Используя аппарат функций Лагранжа, переходя к двойственной задаче, можно показать эквивалентность этой задачи и следующей: | ||
{{eqno|1}} | {{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 | + | ::<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>. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены. | Таким образом, решив оптимизационную задачу {{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>. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены. | ||
Версия 07:49, 22 апреля 2010
SVM (Support Vector Machine, машина опорных векторов) - алгоритм машинного обучения, предложенный В. Н. Вапником. Парадигмой машины опорных векторов можно считать выбор наиболее близких к границе классов объектов из обучающего набора, "опорных векторов", по которым и строится опорная гиперплоскость.
В данной статье приведен пример решения этой задачи для линейно разделимой выборки. Также исследуется устойчивость алгоритма: зависимость параметров разделяющей гиперплоскости от дисперсии случайной переменной.
Постановка задачи линейной классификации
Задана выборка , где
-признаковое описание i-го объекта,
- идентификатор класса, которому принадлежит i-ый объект. В случае двух классов считаем, что
(это позволяет пользоваться функцией sgn в описании классификатора).
Требуется построить классификатор вида , где
- скалярное произведение, а
- вектор и число, характеризующий данный классификатор. Можно говорить о том, что
-веса признаков,
- порог принятия решения.
Если для данной выборки существуют такие, что
не ошибается на обучающей выборке, то она называется линейно разделимой. В противном случае, выборка называется линейно неразделимой.
Описание алгоритма
Линейно разделимая выборка
Если выборка линейно разделима, то существует бесконечно много линейных классификаторов, не ошибающихся на ней. В алгоритме SVM минимизируется расстояние от опорной гиперплоскости до обоих классов.
Отнормируем вектор нормали к разделяющей гиперплоскости и порог принятия решения
так, чтобы
выполнялось условие
. Это всегда можно сделать, поскольку, во-первых, умножение
на положительную константу не меняет классификатора, а, во-вторых, требование минимального расстояния от гиперплоскости до классов гарантирует нам, что плоскость находится на равном расстоянии от классов.
Нетрудно показать, что при такой нормировке ширина разделяющей полосы может быть представлена в виде: . Максимизация этой величины равносильна минимизации нормы вектора нормали. Таким образом, параметры линейного классификатора определяются из задачи квадратичного программирования:
Используя аппарат функций Лагранжа, переходя к двойственной задаче, можно показать эквивалентность этой задачи и следующей:
Таким образом, решив оптимизационную задачу (1), то есть, найдя вектор , вычислим
. Медиана здесь вычисляется именно из практических соображений неточного решения оптимизационной задачи. Теоретически все значения в множестве, по которому берется среднее, равны. Параметры разделяющей гиперплоскости построены.
