286
правок
Изменения
Пример на языке R
== Метод опорных векторов в задаче классификации ==
=== Линейно неразделимая выборка ===
На практике линейно разделимые выборки практически не встречаются: в данных возможны выбросы и нечёткие границы между классами. В таком случае поставленная выше задача не имеет решений, и необходимо ослабить ограничения, позволив некоторым объектам попадать на "территорию" другого класса. Для каждого объекта отнимем от отступа некоторую положительную величину $\xi_i$, но потребуем чтобы эти введённые поправки были минимальны. Это приведёт к следующей постановке задачи, называемой также ''SVM с мягким отступом'' (англ. ''soft-margin SVM''):
$\begin{cases}
\frac{1}{2} \lVert \vec{w} \rVert^2 \color{redbrown}{+ C \sum\limits_{i=1}^\ell \xi_i} \to \min\limits_{w, b, \color{redbrown}{\xi}} \\M_i(\vec{w}, b) \geq 1 \color{redbrown}{- \xi_i}, \quad i = 1, \ldots, \ell \\\color{redbrown}{\xi_i \geq 0, \quad i = 1, \ldots, \ell} \\
\end{cases}$
$\frac{1}{2} \lVert \vec{w} \rVert^2 + C \sum\limits_{i=1}^\ell \left(1 - M_i(\vec{w}, b)\right)_+ \to \min\limits_{w, b}$
Теперь научимся её решать.
{{Теорема
$$\begin{cases}\frac{\partial L}{\partial x} = 0, \quad L(x; \mu, \lambda) = f(x) + \sum\limits_{i=1}^m \mu_i g_i(x) + \sum\limits_{j=1}^k \lambda_j h_j(x) \\ g_i(x) \leq 0,\;h_j(x) = 0 \quad \text{(исходные ограничения)} \\ \mu_i \geq 0 \quad \text{(двойственные ограничения)} \\ \mu_i g_i(x) = 0 \quad \text{(условие дополняющей нежёсткости)} \end{cases}$$
При этом искомая точка является седловой точкой функции Лагранжа: минимумом по $x$ и максимумом по двойственным переменным $\mu$.
}}
По теореме Каруша—Куна—Таккера, поставленная нами задача минимизации эквивалентна двойственной задаче для поиска седловой точки функции Лагранжа:
$\mathscr{L}(\vec{w},b,\xi; \lambda, \eta) = \frac{1}{2} \lVert w \rVert^2 - \sum\limits_{i=1}^\ell \lambda_i \left(M_i(\vec{w}, b) - 1\right) - \sum\limits_{i=1}^\ell \xi_i \left(\lambda_i + \eta_i - C\right)$
$\eta_i$ — переменные, двойственные к ограничениям $\xi_i \geq 0$
Запишем необходимые условия седловой точки функции Лагранжа:
$\begin{cases}
$\begin{array}{lcl}
{{Определение
}}
$\begin{cases}
\end{cases}$
Это также задача квадратичного программирования. Решение задачи лежит в пересечении $\ell$-мерного куба с ребром $C$ и гиперплоскости $\langle \lambda, y \rangle = 0$, что является выпуклым многогранником размерности $\ell-1$. В этом многограннике нужно найти минимум выпуклого квадратичного функционала. Следовательно, данная задача имеет единственное решение. Существуют различные методы поиска решения: можно воспользоваться универсальным солвером задачи квадратичного программирования ([https://www.ibm.com/analytics/cplex-optimizer CPLEX], [http://www.gurobi.com/ Gurobi]), либо алгоритмом, учитывающим специфические особенности SVM ([https://www.microsoft.com/en-us/research/publication/sequential-minimal-optimization-a-fast-algorithm-for-training-support-vector-machines/ SMO], [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9956 INCAS]). После того, как мы получили вектор коэффициентов $\vec{\lambda}$, можем выразить решение прямой задачи выражается через решение двойственной:
$\begin{cases}
\vec{w} = \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i \\
b = \langle \vec{w}, \vec{x}_i \rangle - y_i, \quad \text{для любого}\; forall i: \lambda_i > 0, M_i = 1
\end{cases}$
$a(x) = sign \left(\sum\limits_{i=1}^\ell \lambda_i y_i \langle \vec{x}_i, \vec{x} \rangle - b\right)$
=== Нелинейное обобщение, kernel trick ===
<font color="gray"># importing package and its' dependencies</font> library(caret) <font color="gray">#reading data</font> data <- read.csv(<font color="green">"input.csv"</font>, <font color= Метод опорных векторов в задаче регрессии "#660099">sep</font> =<font color="green">','</font>, <font color="#660099">header</font> = FALSE) <font color="gray"># splitting data into train and test sets</font> index <- createDataPartition(<font color="#660099">y</font> = data$<strong><font color="#660E7A">target</font></strong>, <font color="#660099">p</font> = <font color="blue">0.8</font>, <font color="#660099">list</ TODOfont> = FALSE) training <- data[index,] testing <- data[-index,] <font color="gray"># evaluating model</font> fit <- train(target ~ x + y + z, <font color="#660099">data</font> = train_flats, <font color="#660099">method</font> = <font color="green">"svmRadial"</font>, <font color="#660099">trControl</font> = trainControl(<font color="#660099">method</font> = <font color="green">"repeatedcv"</font>, <font color="#660099">number</font> = <font color="blue">10</font>, <font color="#660099">repeats</font> = <font color="blue">3</font>)) <font color="gray"># printing parameters</font> print(fit)
== См. также ==
* [[Общие понятия]]
* [[Ядра]]
* [[Обзор библиотек для машинного обучения на Python]]
== Примечания ==
== Источники информации ==
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2 machinelearning.ru {{---}} — Машина опорных векторов]* [https://www.youtube.com/watch?v=Adi67_94_gc&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=5 Лекция "Линейные методы классификации: метод опорных векторов"] {{---}} — К.В. Воронцов, курс "Машинное обучение" 2014* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2 Wikipedia {{---}} — Метод опорных векторов]* Alexey Nefedov {{---}} — [https://svmtutorial.online/ Support Vector Machines: A Simple Tutorial]* John Platt {{---}} — [https://www.microsoft.com/en-us/research/publication/sequential-minimal-optimization-a-fast-algorithm-for-training-support-vector-machines/ Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines]* Shai Fine, Katya Scheinberg — [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.9956 INCAS: An Incremental Active Set Method for SVM]
[[Категория: Машинное обучение]]
[[Категория: Классификация]]
[[Категория: Регрессия]]