亚洲成人二区,大香成人AV,久久久久亚洲AV成人

線性判別函數(shù)

給定若干n維度空間的樣本點(diǎn) $x^{(1)},\cdots,x^{(m)}$ ，我們希望使用超平面將不同類別的點(diǎn)劃分開(kāi)來(lái)。如下圖，考慮兩類的情況，我們需要一個(gè)超平面將兩類數(shù)據(jù)劃分開(kāi)，其由 $g(x)$ 確定，稱 $g(x)$ 為線性判別函數(shù)。

劃分超平面

$g(x)$ 的表達(dá)式如下
$g(x)=w^Tx+b$

間隔最大化

幾何間隔是指某個(gè)樣本 $x^{(i)}$ 到分類界面 $g(x)=0$ 的距離
$\gamma_i=\frac{|w^Tx^{(i)}+b|}{\|w\|}.$
定義樣本集與分類界面之間的幾何間隔為，樣本集中所有樣本與分類界面之間幾何間隔的最小值。

而SVM的目標(biāo)是找到一個(gè)可以正確劃分樣本點(diǎn)，且與樣本集幾何間隔最大的超平面。如下圖，稱距離最優(yōu)分類界面最近的這些訓(xùn)練樣本為支持向量（support vector）。

支持向量

可以看出，最優(yōu)分類界面完全由支持向量決定。設(shè)支持向量 $X_s$ ，那么可以直接通過(guò)最大化間隔，求得 $w$ 和 $b$ 。
$\max_{w,b,x\in X_s} \frac{|w^Tx+b|}{\|w\|}$
但是支持向量正是通過(guò)最優(yōu)分類界面得到的，所以這樣通過(guò)支持向量求最優(yōu)分界面的方法時(shí)行不通的。

目標(biāo)函數(shù)

記樣本 $x^{(i)}$ 的類別標(biāo)記為 $y^{(i)}$ ，那么 $y^{(i)}\cdot g(x^{(i)})>0$ 意味著分類界面正確劃分了樣本 $x^{(i)}$ 。不妨通過(guò) $y^{(i)}\cdot g(x^{(i)})\geq 1$ 表示樣本 $x^{(i)}$ 離分類界面保持一定的距離，這個(gè)距離等于
$\gamma_i = \frac{|w^Tx^{(i)}+b|}{\|w\|} \geq \frac{1}{\|w\|}.$
這時(shí)，最大化幾何間隔，等價(jià)于
$\min_{w,b} \frac{1}{2}\|w\|^2.$
按照這個(gè)思路，我們可以定義如下目標(biāo)函數(shù)
$\begin{align} &\min_{w,b} \frac{1}{2}\|w\|^2,\\ &{\rm s.t.}\ \ \ \ y^{(i)}\cdot \left(w^Tx^{(i)}+b\right)\geq 1, i=1,2,\cdots,m. \end{align}$

Kuhn-Tucker構(gòu)造法

上面的目標(biāo)函數(shù)是一個(gè)有約束最優(yōu)化問(wèn)題，我們首先需要將其轉(zhuǎn)化為一個(gè)無(wú)約束最優(yōu)問(wèn)題。

使用拉格朗日乘子法，可以得到相應(yīng)的拉格朗日函數(shù)
$L(w,b,\alpha)=\frac{1}{2}\|w\|^2+\sum_{i=1}^m\alpha_i\left(1-y^{(i)}\cdot\left(w^Tx^{(i)}-b\right)\right), \alpha_i\geq 0.$
分別對(duì)參數(shù) $w,b$ 求偏導(dǎo)：
$\begin{align} &\frac{\partial L(w,b,\alpha)}{\partial w}=w-\sum_{i=1}^m \alpha _iy^{(i)} x^{(i)},\\ &\frac{\partial L(w,b,\alpha)}{\partial b}=\sum_{i=1}^m \alpha_i y^{(i)}. \end{align}$
令偏導(dǎo)為零，得
$\begin{align} &w=\sum_{i=1}^m \alpha_iy^{(i)}x^{(i)},\\ &\sum_{i=1}^m \alpha_i y^{(i)}=0. \end{align}$
將上面第一個(gè)式子帶入到拉格朗日函數(shù)中得
$L(\alpha)=\sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_i y^{(i)} y^{(j)}{x^{(i)}}^Tx^{(j)}.$
因此原問(wèn)題的對(duì)偶問(wèn)題是
$\begin{align} \max_\alpha\ &L(\alpha)\\ {\rm s.t.}\ \ &\sum_{i=1}^m \alpha_i y^{(i)}=0,\\ &\alpha_i\geq 0,i=1,2,\cdots,m. \end{align}$
這是一個(gè)二次規(guī)劃問(wèn)題。但是該問(wèn)題的計(jì)算規(guī)模正比于訓(xùn)練樣本數(shù)，這會(huì)在實(shí)際任務(wù)中造成很大的開(kāi)銷。為了解決這個(gè)問(wèn)題，人們提出了許多高效的算法，具有代表性的是SMO。這里不進(jìn)行介紹。

假設(shè)通過(guò)解對(duì)偶問(wèn)題得到了 $\alpha_i$ ，那么可通過(guò)下式得到權(quán)向量 $w$
$w=\sum_{i=1}^m \alpha_iy^{(i)}x^{(i)}.$
而對(duì)于支持向量中的樣本 $x_s$ ，有
$y_s\cdot (w^Tx_s+b)=1$
那么那些樣本點(diǎn)是支持向量呢？那些滿足 $\alpha_i>0$ 的樣本 $x^{(i)}$ 。這里不進(jìn)行具體的推導(dǎo)。

松弛變量

當(dāng)訓(xùn)練樣本是線性不可分時(shí)，目標(biāo)函數(shù)是無(wú)解的。這時(shí)，可以通過(guò)引入松弛變量，對(duì)某些對(duì)樣本妥協(xié)，也就是允許某些樣本被分錯(cuò)。

具體來(lái)說(shuō)，改寫(xiě)目標(biāo)函數(shù)
$\begin{align} \min_{w,b,\xi_i}\ &\frac{1}{2}\|w\|^2+C\sum_{i=1}^m \xi_i,\\ {\rm s.t.}\ \ &y^{(i)}\cdot \left(w^Tx^{(i)}+b\right)\geq 1-\xi_i,\\ & \xi_i\geq 0, i=1,2,\cdots,m. \end{align}$
其中， $C(C>0)$ 為懲罰參數(shù)，需要人工設(shè)置。C值越大對(duì)誤分類的懲罰越大。

對(duì)上述目標(biāo)函數(shù)使用拉格朗日乘子法得到
$\begin{align} L(w,b,\alpha,\xi,\mu)=&\frac{1}{2}\|w\|^2+C\sum_{i=1}^m\xi_i\\ & +\sum_{i=1}^m\alpha_i\left(1-\xi_i -y^{(i)}(w^Tx^{(i)}+b) \right)-\sum_{i=1} ^m\mu_i\xi_i, \end{align}$
其中， $\alpha_i\geq 0,\mu_i\geq 0$ 是拉格朗日乘子。令 $L(w,b,\alpha,\xi,\mu)$ 對(duì) $w,b,\xi_i$ 的偏導(dǎo)為零，并代入到拉格朗日函數(shù)中可得原問(wèn)題的對(duì)偶問(wèn)題
$\begin{align} \max_\alpha\ & \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}{x^{(i)}}^Tx^{(i)}\\ {\rm s.t.}\ \ & \sum_{i=1}^m\alpha_iy^{(i)}=0,\\ & 0\leq \alpha_i\leq C, i=1,2,\cdots,m. \end{align}$

核函數(shù)

核函數(shù)的思想類似于神經(jīng)網(wǎng)絡(luò)中的激活函數(shù)。

有時(shí)，通過(guò)函數(shù) $\phi(\cdot)$ 將樣本從原始空間映射到一個(gè)更高維的特征空間，SVM可以找到更加合適的劃分超平面。比如
$\Phi:(x_1,x_2)^T\rightarrow (x_1^2,\sqrt 2x_1x_2,x_2^2)^T.$
這時(shí)候劃分判別函數(shù)變?yōu)?br> $g(x)=w^T\phi(x)+b.$
定義核函數(shù)為
${\cal K}(x^{(i)},x^{(j)})=\phi(x^{(i)})^T\phi(x^{(j)}).$
在SVM求解的過(guò)程中，使用 ${\cal K}(x^{(i)},x^{(j)})$ 替代 $\phi(x^{(i)})^T\phi(x^{(j)})$ ，可大大減少計(jì)算量。常用核函數(shù)有，高斯核、多項(xiàng)式核、Sigmoid核等。