286
правок
Изменения
Пример на языке R
== Метод опорных векторов в задаче классификации ==
Это также задача квадратичного программирования. Решение задачи лежит в пересечении $\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$: {{Определение[[Ядра|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$ — пространство со скалярным произведением.}} Более того, При этом можно вообще не строить спрямляющее пространство $H$ в явном виде, и вместо подбора $\psi$ подбирать непосредственно ядро.
Постановка задачи с применением ядер приобретает вид:
$a(x) = sign \left(\sum\limits_{i=1}^\ell \lambda_i y_i \color{brown}{K(\vec{x}_i, \vec{x})} - b\right)$
Недостатки классического SVM:
Существуют различные дополнения и модификации метода опорных векторов, направленные на устранение описанных недостатков:
<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]]
== Примечания ==