校园春色干妹子,嫩草精品国产黑人在线,久久久成人网

超平面

定義： $\mathbf{w}^T \mathbf{x} + b = 0$

對(duì)于處在超平面兩側(cè)的兩個(gè)點(diǎn) $\mathbf{x_1}$ 和 $\mathbf{x_2}$ ，分別有：
$\mathbf{w}^T \mathbf{x_1} + b > 0$
$\mathbf{w}^T \mathbf{x_2} + b < 0$

Hyperplane

某樣本到超平面的單位法向量為： $\frac{w} {||w||}$
某樣本點(diǎn)到超平面的距離可以表示為： $\gamma = sgn(\frac{w}{||w||} \cdot x + \frac {||w||})$
$sgn(z) =\left\{ \begin{array}{rcl} -1 & & {if \space \space z < 0}\\ 0 & & {if \space \space z = 0}\\ +1 & & {if \space \space z > 0}\\ \end{array} \right.$

所以可以看到圖中原點(diǎn)距離超平面的距離是 $\frac{||w||}$

線性分類問(wèn)題（Linear Classifier）

$y = \mathbf{w}^T \mathbf{x} + b$

利用上述性質(zhì)，y > 0 時(shí)為class A，y < 0時(shí)為class B，y = 0時(shí)，x正好在超平面上，simple and easy。

SVM的作用，是在線性分類器的基礎(chǔ)上，找到一個(gè)合理的間隔（margin），使得樣本到超平面的距離最大。

思路

我們可以在原始的超平面兩側(cè)，平行地添加兩個(gè)超平面作為邊界，并且要求：
$\mathbf{w}^T \mathbf{x} + (b - s) > 0$ 對(duì)于class A中所有樣本成立
$\mathbf{w}^T \mathbf{x} + (b + s) < 0$ 對(duì)于class B中所有樣本成立

Add margin to hyperplane

在上面我們提到，原點(diǎn)距離原始的超平面的距離為： $d = \frac{||w||}$
那么當(dāng)我們像上圖一樣加了兩個(gè)平行線之后，可以得到：
$d_{blue} = \frac{b-s} {||w||}$ ， $d_{green} = \frac{b+s} {||w||}$

于是margin就是：
$m = d_{blue} - d_{green} = \frac{2s} {||w||}$
觀察到margin的大小是個(gè)比例關(guān)系，所以我們可以先簡(jiǎn)單地把看出 $s = 1$ ，那么我們的margin的表達(dá)式就是 $m=\frac{2} {||w||} = \frac{2} {\sqrt{w^T w}}$

于是SVM的優(yōu)化問(wèn)題就變成了：

minize $f_0(\mathbf{w}, b)= \frac{1}{2} \mathbf{w}^T \mathbf{w}$
subject to $f_i(\mathbf{w}, b) = y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 \geq 0$ for $i = 1, ..., N$

$y_i \in \{-1, 1\}$ 表示 $\mathbf{x}_i$ 的class label。這是一個(gè)Constrained convex optimization problem，或確切地來(lái)說(shuō)，是一個(gè)quadratic programming問(wèn)題。

SVM優(yōu)化問(wèn)題的求解

Primal problem

計(jì)算拉格朗日(拉格朗日乘數(shù)法)：
$L(\mathbf{w}, b, \mathbf{\alpha}) = \frac{1}{2} \mathbf{w}^T \mathbf{w} - \sum_{i=1}^{N} \alpha _i[y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1]$
求L關(guān)于 $w$ 和 $b$ 的偏導(dǎo)：
$\nabla_w L(\mathbf{w}, b, \mathbf{\alpha}) = \mathbf{w} - \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i \overset{!}{=} 0$ $\space \space \space \space$ (1)
$\frac{\partial L}{\partial b} = \sum_{i=1}^N \alpha_i y_i \overset{!}{=}0$ $\space \space \space \space$ (2)

于是我們可以得到：weights是訓(xùn)練樣本 $\mathbf{x}$ 的線性組合:
$\mathbf{w} = \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i$ $\space \space \space \space$ (3)

Dual problem

把(2)和(3)式代回到表達(dá)式 $L(\mathbf{w}, b, \mathbf{\alpha})$ 中，可以得到拉格朗日的dual function $g(\alpha)$

于是我們的問(wèn)題變成了：
maximize $g(\alpha) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N y_i y_j \alpha_i \alpha_j \mathbf{x}_i^T \mathbf{x}_j$
subject to $\sum_{i=1}^N \alpha_i y_i = 0$ $\space \space \space \space \space \alpha_i \geq 0$ , for $i = 1, ..., N$

將dual functino $g(\alpha)$ 改成vector的形式，這樣我們就得到了一個(gè)標(biāo)準(zhǔn)的quadratic programming的形式：

$g(\alpha) = \frac{1}{2} \alpha^T \mathbf{Q} \alpha + \alpha^T \mathbb{I}_N$
$\mathbf{Q}$ 是一個(gè)symmetric negative (semi-)definite matrix，約束 $\alpha$ 是線性的。

QP的解法可以用（比如）Sequential minimal optimization (SMO) 得到，由此可以得到 $\alpha$ 的最優(yōu)解 $\alpha^*$ 。

求解 $\mathbf{w}$ 和 $b$ 對(duì)應(yīng)的值

在primal problem中我們提到， $w$ 的值是訓(xùn)練樣本的線性組合：
$\mathbf{w} = \sum_{i=1}^N \alpha^*_i y_i \mathbf{x}_i$

對(duì) $b$ 的求解，我們可以用到互補(bǔ)松弛條件(Complementary slackness condition) $\alpha^* f_i(\mathbf{x}) = \alpha^* \cdot [y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1] = 0$

任意選取一個(gè) $\mathbf{x}_i$ 使得 $\alpha_i \neq 0$ 于是有：
$y_i(\mathbf{w}^T \mathbf{x}_i + b) = 1$ 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=y_i%20%5Cin%20%5C%7B%20-1%2C%201%5C%7D" alt="y_i \in \{ -1, 1\}" mathimg="1"> 所以可以寫(xiě)成：
$(\mathbf{w}^T \mathbf{x}_i + b) = y_i$ 于是：
$b = y_i - \mathbf{w}^T \mathbf{x}_i$

至此我們求解出了 $\mathbf{w}$ 和 $b$ ，超平面的兩個(gè)參數(shù)。

支持向量機(jī)中的Support Vector是怎么得名的？

讓我們回頭再看一看complimentary slackness condition:
$\alpha_i f_i(\mathbf{x}^*) = 0$
$\alpha^* \cdot [y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1] = 0$

也就是說(shuō)，只有當(dāng)某個(gè)訓(xùn)練樣本正好落在了邊界(margin)上的時(shí)候，才會(huì)對(duì)weight vector $\mathbf{w}$ 有貢獻(xiàn)（只有此時(shí) $\alpha_i \neq 0$ ），此時(shí)才會(huì)有 $y_i(\mathbf{w}^T \mathbf{x}_i + b) = 1$
這些訓(xùn)練樣本就被稱作support vector

Support vectors

用SVM進(jìn)行二分類

對(duì)于一個(gè)待預(yù)測(cè)的樣本 $\tilde{\mathbf{x}}$ ，它的類別由 $h(\tilde{\mathbf{x}}) = sgn(\mathbf{w}^T \tilde{\mathbf{x}} + b)$ 給出。
其中 $\mathbf{w} = \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i$ 通過(guò)訓(xùn)練得到， $\mathbf{x_i}$ 為訓(xùn)練樣本。
于是我們有：
$h(\tilde{\mathbf{x}}) = sgn(\sum_{i=1}^N \alpha_i y_i \mathbf{x}_i^T \cdot \tilde{\mathbf{x}} + b)$

由于最終得到的 $\mathbf{\alpha} = [\alpha_1, ..., \alpha_n]$ 是稀疏的（大多數(shù)都是0），我們僅僅需要去記得少數(shù)幾個(gè)作為support vectors的訓(xùn)練樣本 $\mathbf{x_i}$ 此時(shí)它們對(duì)應(yīng)的 $\alpha_i \neq 0$

Reference

本文的內(nèi)容總結(jié)自慕尼黑工業(yè)大學(xué)由Prof. Stephan Günnemann教授的Machine Learning課程。未經(jīng)允許請(qǐng)勿轉(zhuǎn)載。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

SVM支持向量機(jī)(一)：基礎(chǔ)概念

SVM支持向量機(jī)(一)：基礎(chǔ)概念

超平面

線性分類問(wèn)題（Linear Classifier）

思路