玖玖黄色视频,嗯嗯嗯嗯啊啊啊啊啊,久热在线98

概述

支持向量機(jī)（Support Vector Machine）是一個(gè)分類(lèi)算法，主要思想是間隔最大化。推導(dǎo)過(guò)程中將間隔最大化轉(zhuǎn)化為帶約束條件的凸優(yōu)化問(wèn)題，通過(guò)引入拉格朗日乘子法和對(duì)偶學(xué)習(xí)法來(lái)簡(jiǎn)化該優(yōu)化問(wèn)題，最后轉(zhuǎn)為為拉格朗日乘子的帶約束條件的優(yōu)化問(wèn)題。在整個(gè)推導(dǎo)過(guò)程中由于引入對(duì)偶學(xué)習(xí)很自然的引入了核方法。最后的優(yōu)化問(wèn)題通過(guò)SMO算法解決。

線性可分支持向量機(jī)

對(duì)于線性可分?jǐn)?shù)據(jù)集，一定存在將數(shù)據(jù)集完全分離的超平面，假設(shè)某分離超平面是 $y=w^Tx+b$ ，某個(gè)數(shù)據(jù)點(diǎn) $(x_i, y_i)$ 到超平面的函數(shù)距離為 $\hat{r_i}=|w^Tx_i+b| =y_i(w^Tx_i+b)$ ,當(dāng)超平面和數(shù)據(jù)點(diǎn)確定時(shí)，超平面可由無(wú)數(shù)對(duì)（w,b）確定，函數(shù)距離會(huì)隨著w，b的變化而變化，引入幾何距離 $r_i=\frac{|w^Tx_i+b|}{||w||}=\frac{\hat{r_i}}{||w||}$ ，幾何距離不隨著（w,b）的變化變化。定義數(shù)據(jù)點(diǎn)到超平面的幾何距離為 $r=\min_{i} r_i =\min_{i}\frac{\hat{r_i}}{||w||}$ .

SVM的思想是最大化數(shù)據(jù)點(diǎn)到超平面的距離，即 $\max_{w,b}r\\s.t. r_i\geq r, for \ i=1,2 \ldots n$

即

$\max_{w,b}\frac{\hat{r}}{||w||}\\s.t. \hat{r_i}\geq \hat{r}, for \ i=1,2 \ldots n$

因?yàn)槠矫婧忘c(diǎn)固定時(shí)函數(shù)距離可取任意非負(fù)值，令 $\hat{r}=1$ 不會(huì)改變上面的優(yōu)化問(wèn)題，得

$\max_{w,b}\frac{1}{||w||}\\s.t. \hat{r_i}\geq 1, for\ i=1,2 \ldots n$

最大化 $\frac{1}{||w||}$ 等價(jià)于最小化 $\frac{1}{2}||w||^2$ ,得

$\min_{w,b}\frac{1}{2}||w||^2\\s.t. y_i(w^Tx_i+b)\geq 1, for\ i=1,2 \ldots n$

得到上面最優(yōu)化問(wèn)題的解 $(w^*, b^*)$ 后，間隔最大的分離超平面就是 $y={w^*}^Tx+b^*$ .

可以通過(guò)Lagrange Multiplier解上述問(wèn)題，Lagrange Function為

$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\\ s.t.\alpha_i\geq0, for \ i=1,2\ldots,n$

令 $\theta =\max_{\alpha, \alpha \geq0} L(w,b,\alpha)=\max_{\alpha, \alpha \geq0} \{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}$ ,可知在滿(mǎn)足約束條件的情況下 $\theta =\frac{1}{2}||w||^2$ (如果有某個(gè)數(shù)據(jù)點(diǎn)違反了約束條件，即 $y_i(w^Tx_i+b)-1<0$ ),那么 $\theta$ 無(wú)窮大），優(yōu)化問(wèn)題變?yōu)?/p>

$\min_{w,b}\theta =\min_{w,b}\max_{\alpha, \alpha \geq0} L(w,b,\alpha)=\min_{w,b}\max_{\alpha, \alpha \geq0} \{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}=P^*$

該問(wèn)題稱(chēng)為原始問(wèn)題,對(duì)偶問(wèn)題為

$\max_{\alpha, \alpha \geq0}\min_{w,b} L(w,b,\alpha)=\max_{\alpha, \alpha \geq0}\min_{w,b}\{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}=Q^*$ ，

且有 $Q^*\leq P^*$ .

最優(yōu)化問(wèn)題滿(mǎn)足Slater條件即存在 $x_i$ 使得不等式嚴(yán)格成立，所以 $Q^*= P^*$ ，可以通過(guò)求解對(duì)偶問(wèn)題來(lái)獲得原始問(wèn)題的解。

K.K.T條件是 $Q^*= P^*$ 的充分必要條件，表達(dá)為

$\triangledown_wL(w^*,b^*,\alpha^*)=0\\ \triangledown_bL(w^*,b^*,\alpha^*)=0\\ \triangledown_\alpha L(w^*,b^*,\alpha^*)=0\\ \alpha_i(y_i(w^Tx_i+b)-1)=0,for\ i=1,2\ldots,n\\ \alpha_i\geq0,for\ i=1,2\ldots,n\\ y_i(w^Tx_i+b)-1 \geq 0, for\ i=1,2\ldots,n$

求解 $\min_{w,b}L(w,b,\alpha)$ ,對(duì)w,b求偏導(dǎo)，有

$\frac{dL(w,b,\alpha)}{dw}=w-\sum_{i=1}^n\alpha_iy_ix_i =0$

$\frac{dL(w,b,\alpha)}{db}=-\sum_{i=1}^n\alpha_iy_i =0$

即

$w=\sum_{i=1}^n\alpha_iy_ix_i\\\sum_{i=1}^n\alpha_iy_i=0$

有

$\begin{align*}\min_{w,b} L(w,b,\alpha)&=\min_{w,b}\{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}\\&=\frac{1}{2}w^T(\sum_{i=1}^n\alpha_iy_ix_i)-w^T\sum_{i=1}^n\alpha_iy_ix_i -\sum_{i=1}^n\alpha_iy_ib+\sum_{i=1}^n\alpha_i \\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}w^T(\sum_{i=1}^n\alpha_iy_ix_i)\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\&s.t. \sum_{i=1}^n\alpha_iy_i=0\\&\alpha_i\geq0, for \ i=1,2,\ldots, n\end{align*}$

優(yōu)化問(wèn)題變?yōu)?/p>

$\max_{\alpha}\sum_{i=1}^n\alpha_i-\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\s.t. \sum_{i=1}^n\alpha_iy_i=0\\\alpha_i\geq0, for \ i=1,2,\ldots, n$

該優(yōu)化問(wèn)題可以通過(guò)SMO有效求解。假設(shè)得到的最優(yōu)解為 $\alpha^*$ ,則

$w^*=\sum_{i=1}^n\alpha^*_iy_ix_i=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_ix_i$

通過(guò)kkt條件， $b^*=\frac{1}{y_j}-{w^*}^Tx_j=y_j-\sum_{i=1}^n\alpha^*_iy_i(x_i\cdot x_j),for\ some\ \alpha^*_j\gt0$

分離超平面為 $y={w^*}^Tx+b^*=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_i(x_i\cdot x)+b^*$

通過(guò)推導(dǎo)過(guò)程可知，如果 $\alpha_i\gt 0$ ,則 $y_i(w^Tx_i+b)=1$ ，對(duì)應(yīng)的實(shí)例 $x_i$ 是支持向量，位于間隔邊界上。如果 $\alpha_i=0$ ，則實(shí)例 $x_i$ 位于正確分類(lèi)的間隔邊界外。

線性支持向量機(jī)

線性可分支持向量機(jī)不能處理線性不可分?jǐn)?shù)據(jù)集，因此引入線性支持向量機(jī)。線性支持向量機(jī)在線性可分支持向量機(jī)的基礎(chǔ)上引入松弛變量 $\xi$ 來(lái)處理離異點(diǎn)。

最優(yōu)化問(wèn)題變?yōu)?/p>

$\min_{w,b}\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i\\ s.t.\ y_i(w^Tx_i+b)\geq 1-\xi_i, for \ i=1,2\ldots,n \\ \xi_i\geq 0, for \ i=1,2\ldots,n$

其中 $\sum_{i=1}^n\xi_i$ 是離異點(diǎn)偏差量的懲罰，C是常數(shù)超參，用來(lái)控制“間隔最大化”和“離異點(diǎn)偏差量最小”。

Lagrange function為

$L(w,b,\xi,\alpha,\beta)=\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(w^Tx_i+b) - (1-\xi_i))-\sum_{i=1}^n\beta_i\xi_i \\ s.t.\ \alpha_i\geq0, for \ i=1,2,\ldots,n\\\beta_i\geq0, for \ i=1,2,\ldots,n$

使用對(duì)偶學(xué)習(xí)法，先求內(nèi)層最小化。L對(duì)w,b,\xi求導(dǎo)，有

$\frac{dL}{dw}=w-\sum_{i=1}^n\alpha_iy_ix_i=0\\ \frac{dL}{db}=-\sum_{i=1}^n\alpha_iy_i=0 \\ \frac{dL}{d\xi_i}=C-\alpha_i-\beta_i=0$

即

$w=\sum_{i=1}^n\alpha_iy_ix_i\\ \sum_{i=1}^n\alpha_iy_i=0\\ C -\alpha_i-\beta_i=0, for \ i=1,2,\ldots, n$

所以外層最大化的函數(shù)為

$\begin{align*}L(w,b,\xi,\alpha,\beta)&=\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(w^Tx_i+b) - (1-\xi_i))-\sum_{i=1}^n\beta_i\xi_i \\ &=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i\xi_i-\sum_{i=1}^n\beta_i\xi_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^n(C-\alpha_i-\beta_i)\xi_i\\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)\end{align*}\\ s.t. \sum_{i=1}^n\alpha_iy_i=0\\ \alpha_i\geq0, for \ i=1,2,\ldots,n\\ \beta_i\geq0, for \ i=1,2,\ldots,n\\C-\alpha_i-\beta_i=0, for \ i=1,2,\ldots,n$

約束條件可簡(jiǎn)化為

$\sum_{i=1}^n\alpha_iy_i=0\\0\leq\alpha_i\leq C, for \ i=1,2,\ldots,n$

解決該最優(yōu)化問(wèn)題后得到最優(yōu)解 $\alpha^*$ ,則

$w^*=\sum_{i=1}^n\alpha^*_iy_ix_i=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_ix_i$

通過(guò)kkt條件， $b^*=\frac{1}{y_j}-{w^*}^Tx_j=y_j-\sum_{i=1}^n\alpha^*_iy_i(x_i\cdot x_j),for\ some\ 0 \lt\alpha^*_j\lt C$

最后得到分離超平面 $y={w^*}^Tx+b^*$

軟間隔的支持向量在：間隔邊界，間隔邊界和分離超平面之間或分離超平面誤分一側(cè)。如果 $\alpha_i=0$ ,實(shí)例位于正確分類(lèi)的間隔邊界外；如果 $0\lt \alpha_i\lt C$ ,則 $\beta_i\gt0$ , $\xi_i=0$ , $y_i(w^Tx_i+b)=1$ ,實(shí)例剛好在間隔邊界上，是支持向量；若 $\alpha_i=C$ ,則 $\beta=0$ , $\xi_i\gt0$ ,如果 $\xi_i<1$ ,實(shí)例位于分離超平面和間隔邊界之間，如果 $\xi_i=1$ ,實(shí)例位于分離超平面上，如果 $\xi_i\gt1$ ，實(shí)例位于分離超平面誤分一側(cè),都屬于支持向量。

合頁(yè)損失(hinge loss)函數(shù)： $Loss(x, y)=[k-distance(x, plane)]_+$ ,如果x到分離超平面的距離小于k，損失為兩者的差，大于等于k時(shí)，為0.確保當(dāng)距離足夠大(k)時(shí)損失才為0.

從損失函數(shù)的角度看，支持向量機(jī)可看作是模型是 $y=sign(w^Tx+b)$ ,損失函數(shù)為

$Loss(x, y|w, b)=\sum_{i=1}^n[1-y_i(w^Tx_i+b)]_++\lambda ||w||^2$

的分類(lèi)模型，損失函數(shù)第一項(xiàng)是經(jīng)驗(yàn)損失，可以理解為當(dāng)實(shí)例被正確劃分且確信度夠高（實(shí)例到分離超平面的距離大于等于1）時(shí)損失為0，否則損失為 $1-y(w^Tx+b)$ 。損失函數(shù)第二項(xiàng)是權(quán)重為 $\lambda$ 的正則項(xiàng)，w的 $L_2$ 范數(shù)?？梢宰C明該損失函數(shù)與原來(lái)的最優(yōu)化問(wèn)題等價(jià)。令 $\xi_i\gt0,[1-y_i(w^Tx_i+b)]_+=[\xi_i]_+=\xi_i$ ,有

$Loss(x, y|w, b)=\sum_{i=1}^n\xi_i+\lambda||w||^2$

取 $\lambda=\frac{1}{2C}$ ,得到原來(lái)的最優(yōu)化問(wèn)題。

注：損失函數(shù)中第一項(xiàng)用函數(shù)距離是因?yàn)楹?jiǎn)單。假設(shè)超平面不變，成比例的增大w,b,損失函數(shù)會(huì)增大；成比例的減小w,b,對(duì)于正確分類(lèi)的點(diǎn)損失函數(shù)可能會(huì)增大，錯(cuò)誤分類(lèi)的點(diǎn)損失函數(shù)會(huì)減小，此時(shí)最小距離有下界1，因此在某個(gè)臨界的w,b后，成比例的減小w，b損失函數(shù)不會(huì)變小，需要改變超平面。效果和使用幾何距離一樣。

非線性支持向量機(jī)

在前面對(duì)偶學(xué)習(xí)法的推導(dǎo)中我們發(fā)現(xiàn)最優(yōu)化的目標(biāo)函數(shù)和決策函數(shù)都只涉及實(shí)例間的內(nèi)積，因此可以用核方法替代這個(gè)內(nèi)積，從而將輸入空間擴(kuò)展到更高維的特征空間，來(lái)處理更復(fù)雜的線性不可分?jǐn)?shù)據(jù)集。

目標(biāo)函數(shù)變?yōu)?/p>

$\max_{\alpha}\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(x_i, x_j)$

決策函數(shù)變?yōu)?/p>

$f(x)=sign(\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_iK(x_i, x)+b^*)$

這樣做的思路是通過(guò)一個(gè)非線性變換將輸入空間轉(zhuǎn)換到特征空間，使輸入空間線性不可分的數(shù)據(jù)在特征空間中線性可分，從而可以使用前面的線性支持向量機(jī)來(lái)解決問(wèn)題。上面兩個(gè)式子中，原來(lái)的 $(x_i\cdot x)$ 用 $K(x_i,x)$ 替換了，相當(dāng)于隱式地將 $x_i$ 和 $x$ 轉(zhuǎn)換到更高維的特征空間再計(jì)算內(nèi)積，在這個(gè)特征空間里數(shù)據(jù)集可能是線性可分的。

SMO

【待更新】

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

SVM

SVM

概述

線性可分支持向量機(jī)

線性支持向量機(jī)

非線性支持向量機(jī)

SMO

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

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

SVM

概述

線性可分支持向量機(jī)

線性支持向量機(jī)

非線性支持向量機(jī)

SMO

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

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