Изменения

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

Существуют различные методы поиска решения: можно воспользоваться универсальным солвером задачи квадратичного программирования ([[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]]).

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

Существует ещё один подход к решению проблемы линейной разделимости, известный как трюк с ядом ядром (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{L}(\lambda) = -\sum\limits_{i=1}^\ell \lambda_i + \frac{1}{2} \sum\limits_{i=1}^\ell \sum\limits_{j=1}^\ell \lambda_i \lambda_j y_i y_j \color{brown}{K(\vec{x}_i, \vec{x}_j)} \to \min\limits_\lambda \\0 \leq \lambda_i \leq C, можно вообще не строить спрямляющее пространство $H$ в явном виде\quad i = 1, \ldots, и вместо подбора $\psiell \\\sum\limits_{i=1}^\ell \lambda_i y_i = 0\end{cases}$ подбирать непосредственно ядро. Теорема Мерсера определяет условия, при которых функция может являться ядром:

{{Теорема|id=kernel|author=Мерсер|statement=Функция $Ka(\vec{x}_1, \vec{x}_2)$ является ядром тогда и только тогда, когда выполнены условия: <br><br>$= sign \begin{cases}Kleft(\vec{x}_1, sum\veclimits_{xi=1}_2) = K(^\vec{x}_2, ell \vec{x}_1) & lambda_i y_i \textcolor{(симметричность)brown} \\[1ex] \forall g: X \to \mathbb{R} \quad \int\limits_X \int\limits_X K(\vec{x}_1_i, \vec{x}_2) g(\vec{x}_1) g(- b\vec{x}_2) d \vec{x}_1 d \vec{x}_2 \geq 0 & \text{(неотрицательная определенностьright)}\end{cases}$}}

Проверка неотрицательной определённости является довольно трудоёмкой, поэтому на практике теорема явно не используется. Проблема выбора лучшего ядра на сегодняшний день остаётся открытой, лучшие из известных на данный момент решений основываются на генетических алгоритмах<ref>[https://www.researchgate.net/publication/221080223_An_Evolutionary_Approach_to_Automatic_Kernel_Construction T.Howley, M.G.Madden — An Evolutionary Approach to Automatic Kernel Construction]</ref>). Обычно в практических реализациях ограничиваются перебором нескольких функций, про которые известно, что они являются ядрами, == Преимущества и выбирают среди них лучшую при помощи кросс-валидации. Кроме того, существуют правила порождения ядер, которые также применяются для расширения пространства перебираемых функций.недостатки SVM ==

# $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}_+$)# $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}$ представима в виде сходящегося степенного ряда с неотрицательными коэффициентами)

* $K(\vec{x}_1, \vec{x}_2) = (\langle \vec{x}_1, \vec{x}_2 \rangle + c)^d, \quad c, d \in \mathbb{R}$ — полиномиальное ядро* $K(\vec{x}_1, \vec{x}_2) = \sigma(\langle \vec{x}_1, \vec{x}_2 \rangle)$ — нейросеть с заданной функцией активации $\sigma(z)$ (не при всех $\sigma$ является ядром)* $K(\vec{x}_1Существуют различные дополнения и модификации метода опорных векторов, \vec{x}_2) = \exp(-\beta \lVert \vec{x}_1 - \vec{x}_2 \rVert^2)$ — сеть радиальных базисных функций (англ. ''RBF'') == Преимущества и недостатки 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]