Изменения

{{в разработке}}  '''Метод опорных векторов''' (англ. ''support vector machine'', ''SVM'') — один из наиболее популярных методов обучения, который применяется для решения задач классификации и регрессии. Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки наиболее оптимальным способом. Алгоритм работает в предположении, что чем больше расстояние (зазор) между разделяющей гиперплоскостью и объектами разделяемых классов, тем меньше будет средняя ошибка классификатора.

На практике линейно разделимые выборки практически не встречаются: в данных возможны выбросы и нечёткие границы между классами. В таком случае поставленная выше задача не имеет решений, и необходимо ослабить ограничения, позволив некоторым объектам попадать на "территорию" другого класса. Для каждого объекта отнимем от отступа некоторую положительную величину $\xi_i$, но потребуем чтобы эти введённые поправки были минимальны. Это приведёт к следующей постановке задачи, называемой также ''SVM с мягким отступом'' (англ. ''soft-margin SVM''):

\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} \\

По теореме Каруша—Куна—Таккера, поставленная нами задача минимизации эквивалентна двойственной задаче для поиска седловой точки функции Лагранжа:

Необходимые условия седловой точки функции Продифференцируем функцию Лагранжаи приравняем к нулю производные. Получим следующие ограничения:

Диапазон значений $\lambda_i$ (которые, как указано выше, соответствуют ограничениям на величину отступа) позволяет нам разделить объекты обучающей выборки на три типа: # $\lambda_i = 0\; \Rightarrow \; \eta_i = C; \; \xi_i = 0; \; M_i \geq 1\;$ — периферийные (неинформативные) объекты<br> Эти объекты лежат в своём классе, классифицируются верно и не влияют на выбор разделяющей гиперплоскости (см. уравнение для $\vec{w}$)# $0 < \lambda_i < C\; \Rightarrow \; 0 < \eta_i < C; \; \xi_i = 0; \; M_i = 1\;$ — опорные граничные объекты<br> Эти объекты лежат ровно на границе разделяющей полосы на стороне своего класса# $\lambda_i = СC \; \Rightarrow \; \eta_i = 0; \; \xi_i > 0; \; M_i < 1\;$ — опорные объекты-нарушители<br> Эти объекты лежат внутри разделяющей полосы или на стороне чужого класса

 Двойственная задачаТеперь подставим ограничения, которые мы получили при дифференцировании, в функцию Лагранжа. Получим следующую постановку двойственной задачи, которая зависит только от двойственных переменных $\lambda$:

Это также задача квадратичного программирования. Решение задачи лежит в пересечении $\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}$, можем выразить решение прямой задачи выражается через решение двойственной:

b = \langle \vec{w}, \vec{x}_i \rangle - y_i, \quad \text{для любого}\; forall i: \lambda_i > 0, M_i = 1

Линейный На практике для повышения вычислительной устойчивости рекомендуется при расчёте $b$ брать медиану по опорным граничным объектам: $b = med\{ \langle \vec{w}, \vec{x}_i \rangle - y_i : \lambda_i > 0, M_i = 1, i = 1, \ldots, \ell\}$ Теперь можем переписать наш линейный классификатор, выразив $\vec{w}$ через $\vec{\lambda}$:

Переход Существует ещё один подход к спрямляющему пространству более высокой решению проблемы линейной разделимости, известный как трюк с ядром (kernel trick). Если выборка объектов с признаковым описанием из $X = \mathbb{R}^n$ не является линейно разделимой, мы можем предположить, что существует некоторое пространство $H$, вероятно, большей размерности: , при переходе в которое выборка станет линейно разделимой. Пространство $H$ здесь называют спрямляющим, а функцию перехода $\psi : X \to H$— спрямляющим отображением. Построение SVM в таком случае происходит так же, как и раньше, но в качестве векторов признаковых описаний используются векторы $\psi(\vec{x})$, а не $\vec{x}$. Соответственно, скалярное произведение $\langle \vec{x}_1, \vec{x}_2 \rangle$ в пространстве $X$ везде заменяется скалярным произведением $\langle \psi(\vec{x}_1), \psi(\vec{x}_2) \rangle$ в пространстве $H$. Отсюда следует, что пространство $H$ должно быть гильбертовым, так как в нём должно быть определено скалярное произведение. Обратим внимание на то, что постановка задачи и алгоритм классификации не используют в явном виде признаковое описание и оперируют только скалярными произведениями признаков объектов. Это даёт возможность заменить скалярное произведение в пространстве $X$ на [[Ядра|ядро]] — функцию, являющуюся скалярным произведением в некотором $H$. При этом можно вообще не строить спрямляющее пространство в явном виде, и вместо подбора $\psi$ подбирать непосредственно ядро.

{{Определение|definition='''Ядро''' (англ. ''kernel'') — функция $KПостановка задачи с применением ядер приобретает вид: X \times X \to \mathbb{R}$, которая является скалярным произведением в некотором гильбертовом пространстве: $K(\vec{x}_1, \vec{x}_2) = \langle \psi(\vec{x}_1), \psi(\vec{x}_2) \rangle$ при некотором $\psi : X \to H$, где $H$ — гильбертово пространство.}}

$\begin{cases}-\mathscr{Теорема|idL}(\lambda) =kernel|author-\sum\limits_{i=|statement=Функция $K(1}^\ell \lambda_i + \vecfrac{x1}_1, \vec{x2}_2)$ является ядром тогда и только тогда, когда выполнены условия: <br>$\beginsum\limits_{casesi=1}K(^\ell \sum\veclimits_{xj=1}_1, ^\ell \lambda_i \lambda_j y_i y_j \veccolor{xbrown}_2) = {K(\vec{x}_2_i, \vec{x}_1) & \text{(симметричность_j)} \to \[1ex] min\forall g: X limits_\to lambda \mathbb{R} \quad 0 \intleq \limits_X lambda_i \intleq C, \limits_X K(quad i = 1, \vec{x}_1ldots, \vec{x}_2) g(ell \\vec{x}_1) g(\vec{x}_2) d sum\veclimits_{xi=1}_1 d ^\vec{x}_2 ell \geq lambda_i y_i = 0 & \text{(неотрицательная определенность)}\end{cases}$}}

# $K(\vec{x}_1, \vec{x}_2) = \langle \vec{x}_1, \vec{x}_2 \rangle \quad$ (скалярное произведение)# $K(\vec{x}_1, \vec{x}_2) = \alpha \quad$ (константа $\alpha \in \mathbb{R}, \alpha > 0$)# $K(\vec{x}_1, \vec{x}_2) = K_1(\vec{x}_1, \vec{x}_2) + K_2(\vec{x}_1, \vec{x}_2) \quad$ (сумма ядер)# $K(\vec{x}_1, \vec{x}_2) = K_1(\vec{x}_1, \vec{x}_2) * K_2(\vec{x}_1, \vec{x}_2) \quad$ (произведение ядер)# $K(\vec{x}_1, \vec{x}_2) = \psi(\vec{x}_1) * \psi(\vec{x}_2) \quad$ (произведение функций $\psi Преимущества SVM перед методом стохастического градиента и нейронными сетями: X \to \mathbb{R}$)# $K(\vec{x}_1, \vec{x}_2) = K_1(\phi(\vec{x}_1), \phi(\vec{x}_2)) \quad$ (ядро от функций $\phi : X \to X$)# $K(\vec{x}_1, \vec{x}_2) = \int\limits_X s(\vec{x}_1, \vec{z}) s(\vec{x}_2, \vec{z}) d \vec{z} \quad$ ($s : X \times X \to \mathbb{R}$ — симметричная интегрируемая функция)# $K(\vec{x}_1, \vec{x}_2) = f(K_1(\vec{x}_1, \vec{x}_2)) \quad$ ($f: \mathbb{R} \to \mathbb{R}$ представима в виде сходящегося степенного ряда с неотрицательными коэффициентами)

== Метод опорных векторов в задаче регрессии Модификации ==// TODO

== Преимущества Существуют различные дополнения и недостатки SVM ==модификации метода опорных векторов, направленные на устранение описанных недостатков:

Преимущества * [http://jmlr.csail.mit.edu/papers/v1/tipping01a.html Метод релевантных векторов (Relevance Vector Machine, RVM)]* [https://papers.nips.cc/paper/2450-1-norm-support-vector-machines.pdf 1-norm SVM (LASSO SVM перед методом стохастического градиента и нейронными сетями)]* [http://www3.stat.sinica.edu.tw/statistica/oldpdf/A16n214.pdf Doubly Regularized SVM (ElasticNet SVM)]* [https://arxiv.org/abs/1901.09643v1 Support Features Machine (SFM)]* [http://www.robots.ox.ac.uk/~minhhoai/papers/SVMFeatureWeight_PR.pdf Relevance Features Machine (RFM)]

* Задача выпуклого квадратичного программирования имеет единственное решение==Примеры кода==* Метод опорных векторов эквивалентен двухслойной нейронной сети===Пример на языке Java===Пример классификации с применением <code>smile.classification.SVM</code><ref>[https://haifengl.github.io/smile/api/java/smile/classification/SVM.html/ Smile, где число нейронов на скрытом слое определяется автоматически как число опорных векторовSVM]</ref>

Недостатки классического SVM<code>Maven</code> зависимость: <dependency> <groupId>com.github.haifengl</groupId> <artifactId>smile-core</artifactId> <version>1.5.2</version> </dependency>

<font color="green">// read train & test dataset</font> '''var''' parser = Модификации new DelimitedTextParser(); parser.setResponseIndex(new NominalAttribute("class"), 0); '''var''' train =parser.parse("USPS Train", this.getClass().getResourceAsStream("/smile/data/usps/zip.train")); '''var''' test =parser.parse("USPS Test", this.getClass().getResourceAsStream("/smile/data/usps/zip.test")); '''var''' classes = Arrays.stream(test.labels()).max().orElse(0) + 1; <font color="green">// build SVM classifier</font> '''var''' svm = new SVM<>(new GaussianKernel(8.0), 5.0, classes, SVM.Multiclass.ONE_VS_ONE); svm.learn(train.x(), train.labels()); svm.finish(); <font color="green">// calculate test error rate</font> '''var''' error = 0; for (int i = 0; i < test.x().length; i++) { if (svm.predict(test.x()[i]) != test.labels()[i]) { error++; } } System.out.format("USPS error rate = %.2f%%\n", 100.0 * error / test.x().length);

Существуют различные дополнения и модификации метода опорных векторов, направленные === Пример на устранение описанных недостатков:языке R ==={{Main|Примеры кода на R}}

* [[Метод релевантных векторов <font color="gray"># importing package and its' dependencies</font> library(caret) <font color="gray">#reading data</font> data <- read.csv(Relevance Vector Machine<font color="green">"input.csv"</font>, <font color="#660099">sep</font> = <font color="green">', RVM'</font>, <font color="#660099">header</font> = FALSE)]]* [[1 <font color="gray"># splitting data into train and test sets</font> index <-norm SVM createDataPartition(LASSO SVM<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</font> = FALSE) training <- data[index,] testing <- data[-index,]* [[Doubly Regularized SVM <font color="gray"># evaluating model</font> fit <- train(ElasticNet SVM)]]target ~ x + y + z, <font color="#660099">data</font> = train_flats, <font color="#660099">method</font> = <font color="green">"svmRadial"</font>,* [[Support Features Machine <font color="#660099">trControl</font> = trainControl(SFM<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>* [[Relevance Features Machine print(RFMfit)]]

* [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]