九九热九九操,欧美日韩国产精品观看,中文字幕高潮

圖來源：《機(jī)器學(xué)習(xí)》周志華著

超平面用方程表示為

w^Tx+b=0

，

\gamma=\frac{2}{||w||}

為間隔(margin)。我們需要找到具有最大間隔的劃分超平面，故得到：

\underset{w,b}{argmin}\frac12||w||^2

s.t. y_i(w^Tx+b)>=1,i=1,2,...,m

1.問題求解：

(1)拉格朗日乘子法

定義拉格朗日函數(shù)
$L(w,b,\mu)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}\mu_i(1-y_i(w^Tx+b))$ ，
KKT條件為：
$\begin{cases} \mu _{ i }>=0 \\ 1-y_{ i }(w^{ T }x+b)<=0 \\ \mu_i(1-y_i(w^Tx+b))=0\end{cases}$
求極值，則令
$\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}\mu_iy_ix_i=0$
$\frac{\partial{L}}{\partial}=\sum_{i=1}^{m}\mu_iy_i=0$
得到：
$w=\sum_{i=1}^{m}\mu_iy_ix_i$
$\sum_{i=1}^{m}\mu_iy_i=0$
代入 $L(w,b,\mu)$ 消去 $w$ 和 $b$ ,得到原問題的對偶問題為
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
由KKT條件得到：對于任意訓(xùn)練樣本 $(x_i,y_i)$ 總有 $\mu_i=0$ 或 $y_i(w^Tx_i+b)=1$ ,這就意味著當(dāng) $\mu_i=0$ 時，該樣本并不會對 $f(x)=w^Tx+b$ 產(chǎn)生而任何影響，當(dāng) $y_i(w^Tx_i+b)=1$ 時，此時意味著訓(xùn)練樣本在最大間隔的邊界上，該樣本點(diǎn)稱之為支持向量。

(2)對偶問題求解：

2.核函數(shù)

假設(shè)樣本線性可分，即存在一個超平面對樣本進(jìn)行分類。而實際任務(wù)中，樣本往往是非線性可分。此時，我們將 $x_i$ 映射到高維特征空間，在特征空間中找到超平面使得樣本線性可分，記 $\phi(x_i)$ 為 $x_i$ 映射到高維特征空間所對應(yīng)的特征向量。
因此，對應(yīng)的模型可以表示為
$f(x)=w^T\phi(x)+b$
實際只需要求解如下函數(shù)：
$\underset{w,b}{argmin}\frac12||w||^2$
$s.t. y_i(w^T\phi(x_i)+b)>=1,i=1,2,...,m$
對偶問題為：
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_j\phi(x_i)^T\phi(x_j)$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
當(dāng)特征空間維度很高時，計算 $\phi(x_i)^T\phi(x_j)$ 困難，故定義核函數(shù) $k(.,.)$ 使得 $\phi(x_i)^T\phi(x_j)=k(x_i,x_j)$ ,
則對偶問題重寫為：
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_jk(x_i,x_j)$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
求解該對偶問題得到
$f(x)=\sum_{i=1}^{m}\mu_iy_i\phi(x_i)^Tx+b$
$=\sum_{i=1}^{m}\mu_iy_ik(x_i,x)+b$

3.軟間隔

圖中紅色樣本是被分錯的

前面介紹的支持向量機(jī)形式是要求所有樣本均滿足約束 $y_i(w^Tx+b)>=1,i=1,2,...,m$ ，即所有樣本都必須劃分正確，這稱為"硬間隔" (hard margin)，而軟間隔則是允許某些樣本不滿足約束。當(dāng)然我們是希望這樣不滿足約束的樣本越少越好。因此目標(biāo)函數(shù)定義為
$\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{0/1}( y_i(w^Tx+b)-1)$ ,其中
$l_{0/1}(z)=\begin{cases} 1\quad ,if\quad z<0 \\ 0\quad ,otherwise \end{cases}$

由于 $l_{0/1}$ 非凸、非連續(xù)，常用其他損失函數(shù)替代，如下圖所示:

三種常見的替代損失函數(shù):hinge損失，指數(shù)損失，對率損失

采用hinge損失得到：

\underset{w,b}{argmin}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}max(0, 1-y_i(w^Tx+b))

引入松弛變量得到:

軟間隔支持向量機(jī)

$\underset{w,b}{argmin}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i$
$s.t. y_i(w^Tx+b)>=1-\xi_i,i=1,2,...,m$
$\xi_i>=0,i=1,2,...,m$
采用拉格朗日乘子法
$L(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_{i=1}^{m}\mu_i\xi_i$ ，求極值，令
$\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}\alpha_iy_ix_i=0 \Rightarrow w=\sum_{i=1}^{m}\alpha_iy_ix_i$
$\frac{\partial{L}}{\partial}=\sum_{i=1}^{m}\alpha_iy_i=0$
$\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i$
帶入L得到原問題的對偶問題為:
$\underset{\alpha}{argmax}\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}\alpha_iy_i=0$
$0<=\alpha_i<=C,i=1,2,...,m$
KKT條件要求:
$\begin{cases} \alpha _{ i }>=0, \mu_i>=0\\ 1-\xi_i-y_{ i }(w^{ T }x+b)<=0 \\\xi_i>=0\\ \alpha_{ i }(1-\xi_i-y_{ i }(w^{ T }x+b))=0 \\\mu_i\xi_i=0\end{cases}$
由此可得：

對于任意 $(x_i,y_i)$ ,當(dāng) $\alpha_i=0$ 時，該樣本不會對 $f(x)$ 產(chǎn)生任何影響；當(dāng) $\alpha_i>0$ 時，必有 $y_{ i }(w^{ T }x+b)=1-\xi_i$ ,此時該樣本是支持向量。當(dāng) $\alpha_i<C$ 時， $\mu_i>0$ ,則 $\xi_i=0$ ,此時樣本處于最大間隔邊界上，當(dāng) $\alpha_i=C$ 時， $\mu_i=0$ ，則 $\xi_i>0$ ；若 $\xi_i>1$ ,樣本被錯誤分類;若 $\xi_i<1$ ,樣本落在最大間隔內(nèi)部。
軟間隔支持向量機(jī)模型僅與支持向量有關(guān)。

4.支持向量回歸

（1）考慮 $f(x)$ 與 $y$ 最多允許有 $\varepsilon$ 的誤差
（2）構(gòu)建寬度為 $2\varepsilon$ 的間隔帶，如圖：

落入間隔帶的樣本被認(rèn)為是預(yù)測正確的

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

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{\varepsilon}( f(x_i)-y_i)

l_{\varepsilon}(z)=\begin{cases} 0\quad ,if\quad |z|<=\varepsilon \\|z|-\varepsilon\quad ,otherwise \end{cases}

可允許間隔帶兩側(cè)的松弛程度有所不同，故引入松弛變量

\xi

和

\overset{\wedge}{\xi}

,得到SVR問題：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

s.t. f(x_i)-y_i<=\varepsilon+\xi_i

y_i- f(x_i)<=\varepsilon+\overset{\wedge}{\xi}_i

\xi_i>=0,\overset{\wedge}{\xi}_i>=0,i=1,2,...,m

拉格朗日乘子法

L(w,b,\xi,\overset{\wedge}{\xi},\alpha,\overset{\wedge}{\alpha},\mu,\overset{\wedge}{\mu})=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

+\sum_{i=1}^{m}\alpha_i( f(x_i)-y_i-\varepsilon-\xi_i)+\sum_{i=1}^{m}\overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)

-\sum_{i=1}^{m}\mu_i\xi_i-\sum_{i=1}^{m}\overset{\wedge}{\mu}_i\overset{\wedge}{\xi}_i

，求極值，令

\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i=0 \Rightarrow w=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i

\frac{\partial{L}}{\partial}=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i

\frac{\partial{L}}{\partial{\overset{\wedge}{\xi}_i}}=C-\overset{\wedge}{\alpha}_i-\overset{\wedge}{\mu}_i=0 \Rightarrow C=\overset{\wedge}{\alpha}_i+\overset{\wedge}{\mu}_i

代入L,得到SVR的對偶問題：

\underset{\alpha,\overset{\wedge}{\alpha}}{argmax}\sum_{i=1}^{m}y_i(\overset{\wedge}{\alpha}_i-\alpha_i)-\varepsilon(\overset{\wedge}{\alpha}_i+\alpha_i)

-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)(\overset{\wedge}{\alpha}_j-\alpha_j)x_i^Tx_j

s.t. \sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

0<=\alpha_i,\overset{\wedge}{\alpha}_i<=C,i=1,2,...,m

KKT條件為：

\begin{cases} \alpha_i(f(x_i)-y_i-\varepsilon-\xi_i)=0 \\ \overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)=0 \\ \alpha_i \overset{\wedge}{\alpha}_i=0,\xi\overset{\wedge}{\xi}_i=0\\(C-\alpha_i)\xi=0,(C-\overset{\wedge}{\alpha}_i)\overset{\wedge}{\xi}_i=0 \end{cases}

當(dāng)且僅當(dāng) $f(x_i)-y_i-\varepsilon-\xi_i=0$ , $\alpha_i$ 為非零；當(dāng)且僅當(dāng) $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ , $\overset{\wedge}{\alpha}_i$ 為非零.換言之，樣本 $(x_i,y_i)$ 沒有落在 $\varepsilon$ -間隔帶時， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 為非零。此外， $f(x_i)-y_i-\varepsilon-\xi_i=0$ 和 $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ 不能同時成立。因此， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 至少有一個為零。
由 $f(x)=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i^Tx+b$ 可知，只有 $(\overset{\wedge}{\alpha}_i-\alpha_i)$ 非零時， $(x_i,y_i)$ 為SVR的支持向量，且落在 $\varepsilon$ -間隔帶之外。落在 $\varepsilon$ -間隔帶中的樣本，滿足 $\alpha_i=\overset{\wedge}{\alpha}_i=0$