Изменения

[[Файл:SVM_margin.png|300px|thumb|right|Оптимальная разделяющая гиперплоскость в $\mathbb{R}^2$]]Заметим, что при умножении $\vec{w}$ и $b$ на константу $c \neq 0$ уравнение $\langle c\vec{w}, \vec{x} \rangle - cb = 0$ определяет ту же самую гиперплоскость, что и $\langle \vec{w}, \vec{x} \rangle - b = 0$. Для удобства проведём нормировку: выберем константу $c$ таким образом, чтобы $\min\limits_i M_i(\vec{w}, b) = 1$. При этом в каждом из двух классов найдётся хотя бы один "граничный" объектобучающей выборки, отступ которого равен этому минимуму: иначе можно было бы сместить гиперплоскость в сторону класса с большим отступом, тем самым увеличив минимальное расстояние от гиперплоскости до объектов обучающей выборки. Обозначим любой "граничный" объект из класса $+1$ как $\vec{x}_+$, из класса $-1$ как $\vec{x}_-$. Их отступ равен единице, то есть

[[Файл:SVM_margin.png|300px|thumb|right|Оптимальная разделяющая гиперплоскость в $\mathbbbegin{cases}M_+(\vec{w}, b) = (+1)(\langle \vec{w}, \vec{x}_+ \rangle - b) = 1 \\M_-(\vec{Rw}, b) = (-1)(\langle \vec{w}, \vec{x}_- \rangle - b) = 1\end{cases}^2$]] Нормировка позволяет определить ограничить разделяющую полосу между классами: $\{x: -1 < \langle \vec{w}, \vec{x}_i \rangle - b < 1\}$. Внутри неё не может лежать ни один объект обучающей выборки. Ширину разделяющей полосы можно выразить как множество точек, расстояние от которых до проекцию вектора $\vec{x}_+ - \vec{x}_-$ на нормаль к гиперплоскости меньше $1\vec{w}$. Чтобы разделяющая гиперплоскость находилась на наибольшем расстоянии от точек выборки, ширина полосы должна быть максимальной:  $\frac{\langle \vec{x}_+ - \vec{x: }_-, \vec{w} \rangle}{\lVert w \rVert} = \frac{\langle \vec{x}_+, \vec{w} \rangle - \langle \vec{x}_-, \vec{w} \rangle -b + b}{\lVert w \rVert} = \frac{(+1 < )\left(\langle \vec{x}_+, \vec{w}\rangle - b\right) \, + \, (-1)\left(\langle \vec{x}_i _-, \vec{w} \rangle - b < \right)}{\lVert w \rVert} = \\ = \frac{M_+(\vec{w}, b) \, + \, M_-(\vec{w}, b)}{\lVert w \rVert} = \frac{2}{\lVert w \rVert} \to \max \; \Rightarrow \; \lVert w \rVert \to \min$ Это приводит нас к постановке задачи оптимизации в терминах квадратичного программирования: $\begin{cases}\lVert \vec{w} \rVert^2 \to \min\limits_{w,b} \\M_i(\vec{w}, b) \geq 1, \quad i = 1, \ldots, \ell\end{cases}$.  === Линейно неразделимая выборка ===

Если $\hat{x} \in \arg\min f$ — решение задачи точка локального минимума при наложенных ограничениях, то существуют такие множители $\mu_i, i = 1\ldots m$, $\;\lambda_j, j = 1\ldots k$, что для функции Лагранжа $L(x; \mu, \lambda)$ выполняются условия: $$\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)$ $\lambda_i$ — переменные, двойственные к ограничениям $M_i \geq 1 - \xi_i$ $\eta_i$ — переменные, двойственные к ограничениям $\xi_i \geq 0$  Запишем необходимые условия седловой точки функции Лагранжа: $\begin{cases}\frac{\partial \mathscr{L}}{\partial w} = 0, \quad \frac{\partial \mathscr{L}}{\partial b} = 0, \quad \frac{\partial \mathscr{L}}{\partial \xi} = 0 \\\xi_i \geq 0, \quad \lambda_i \geq 0, \quad \eta_i \geq 0, && i = 1, \ldots, \ell \\\lambda_i = 0 \;\text{либо}\; M_i(\vec{w},b) = 1 - \xi_i, && i = 1, \ldots, \ell \\\eta_i = 0 \;\text{либо}\; \xi_i = 0, && i = 1, \ldots, \ell\end{cases}$  Продифференцируем функцию Лагранжа и приравняем к нулю производные. Получим следующие ограничения: $\begin{array}{lcl}\frac{\partial \mathscr{L}}{\partial w} = \vec{w} - \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i = 0 & \Rightarrow & \vec{w} = \sum\limits_{i=1}^\ell \lambda_i y_i \vec{x}_i \\\frac{\partial \mathscr{L}}{\partial b} = -\sum\limits_{i=1}^\ell \lambda_i y_i = 0 & \Rightarrow & \sum\limits_{i=1}^\ell \lambda_i y_i = 0 \\\frac{\partial \mathscr{L}}{\partial \xi_i} = -\lambda_i - \eta_i + C = 0 & \Rightarrow & \eta_i + \lambda_i = C, \quad i = 1, \ldots, \ell\end{array}$ 

Заметим, что $\eta_i \geq 0$, $\lambda_i \geq 0$, $C > 0$, поэтому из последнего ограничения получаем $0 \leq \eta_i \leq C$, $0 \begin{cases}leq \lambda_i \frac{leq C$.  Диапазон значений $\partial L}{lambda_i$ (которые, как указано выше, соответствуют ограничениям на величину отступа) позволяет нам разделить объекты обучающей выборки на три типа: # $\partial x} lambda_i = 0 \quad L(x; \mu, Rightarrow \; \lambda) eta_i = f(x) + C; \sum; \limits_{ixi_i =0; \; M_i \geq 1}^m \mu_i g_i;$ — периферийные (xнеинформативные) + объекты <br> Эти объекты лежат в своём классе, классифицируются верно и не влияют на выбор разделяющей гиперплоскости (см. уравнение для $\sum\limits_vec{j=1w}^k $)# $0 < \lambda_j h_j(x) lambda_i < C \; \ g_i(x) Rightarrow \leq ; 0,< \eta_i < C; \;h_j(x) \xi_i = 0 ; \; M_i = 1 \quad ;$ — опорные граничные объекты <br> Эти объекты лежат ровно на границе разделяющей полосы на стороне своего класса# $\text{(исходные ограничения)} lambda_i = C \; \ Rightarrow \mu_i ; \geq eta_i = 0 ; \quad \text{(двойственные ограничения)} ; \\ \mu_i g_i(x) = xi_i > 0 ; \quad ; M_i < 1 \text;$ — опорные объекты-нарушители <br> Эти объекты лежат внутри разделяющей полосы или на стороне чужого класса {{Определение|definition='''Опорный объект''' (условие дополняющей нежёсткостиопорный вектор, англ. ''support vector'')} — объект $\endvec{casesx}_i$, соответствующий которому множитель Лагранжа отличен от нуля: $\lambda_i \neq 0$.

В качестве аппроксимации функции потерь возьмём $L(x_i\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) = max(, \quad \forall i: \lambda_i > 0, M_i = 1 - M_i(w, w_0))\end{cases}$

Запишем функционал На практике для метода оптимизации эмпирического риска с использованием данной функции потерь и регуляризацииповышения вычислительной устойчивости рекомендуется при расчёте $b$ брать медиану по опорным граничным объектам:

$b = med\{ \sumlangle \limits_vec{i=1w}^\ell (1 - M_i(w, w_0))_+ + \frac{1}vec{2Cx} _i \lVert w rangle - y_i : \rVert^2 lambda_i > 0, M_i = 1, i = 1, \to ldots, \minell\limits_{w, w_0}$

=== Линейно неразделимая Нелинейное обобщение, 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$ подбирать непосредственно ядро.  Постановка задачи с применением ядер приобретает вид: $\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, \quad i = 1, \ldots, \ell \\\sum\limits_{i=1}^\ell \lambda_i y_i = 0\end{cases}$ $a(x) = sign \left(\sum\limits_{i=1}^\ell \lambda_i y_i \color{brown}{K(\vec{x}_i, \vec{x})} - b\right)$ == Преимущества и недостатки SVM == Преимущества SVM перед методом стохастического градиента и нейронными сетями: * Задача выпуклого квадратичного программирования хорошо изучена и имеет единственное решение.* Метод опорных векторов эквивалентен двухслойной нейронной сети, где число нейронов на скрытом слое определяется автоматически как число опорных векторов.* Принцип оптимальной разделяющей гиперплоскости приводит к максимизации ширины разделяющей полосы, а следовательно, к более уверенной классификации. Недостатки классического SVM: * Неустойчивость к шуму: выбросы в исходных данных становятся опорными объектами-нарушителями и напрямую влияют на построение разделяющей гиперплоскости.* Не описаны общие методы построения ядер и спрямляющих пространств, наиболее подходящих для конкретной задачи.* Нет отбора признаков.* Необходимо подбирать константу $C$ при помощи кросс-валидации. ==Модификации ==

<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">// TODOcalculate 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);

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