Изменения
нет такого понятия "наиболее оптимальный". Оптимальный - это и так самый лучший.
== Метод опорных векторов в задаче классификации ==
Это также задача квадратичного программирования. Решение задачи лежит в пересечении $\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}$
=== Нелинейное обобщение, kernel trick ===
Существует ещё один подход к решению проблемы линейной разделимости, известный как трюк с ядом ядром (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$ подбирать непосредственно ядро.
== Преимущества и недостатки SVM ==
Преимущества SVM перед методом стохастического градиента и нейронными сетями:
* Задача выпуклого квадратичного программирования хорошо изучена и имеет единственное решение.* Метод опорных векторов эквивалентен двухслойной нейронной сети, где число нейронов на скрытом слое определяется автоматически как число опорных векторов.* Принцип оптимальной разделяющей гиперплоскости приводит к максимизации ширины разделяющей полосы, а следовательно, к более уверенной классификации.
Недостатки классического SVM:
* Неустойчивость к шуму: выбросы в исходных данных становятся опорными объектами-нарушителями и напрямую влияют на построение разделяющей гиперплоскости.* Не описаны общие методы построения ядер и спрямляющих пространств, наиболее подходящих для конкретной задачи.* Нет отбора признаков.* Необходимо подбирать константу $C$ при помощи кросс-валидации.
== Модификации ==
Существуют различные дополнения и модификации метода опорных векторов, направленные на устранение описанных недостатков:
* [[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> <code>Maven</code> зависимость: <dependency> <groupId>com.github.haifengl</groupId> <artifactId>smile-core</artifactId> <version>1.5.2</version> </dependency> '''import''' smile.classification.SVM; '''import''' smile.data.NominalAttribute; '''import''' smile.data.parser.DelimitedTextParser; '''import''' smile.math.kernel.GaussianKernel; '''import''' java.util.Arrays; <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);
== См. также ==
* [[Общие понятия]]
* [[Ядра]]
* [[Обзор библиотек для машинного обучения на 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]
[[Категория: Машинное обучение]]
[[Категория: Классификация]]
[[Категория: Регрессия]]