手机毛片在线,a毛片基地免费全部香蕉,国产精品久久久久久久久久妇女

SVM學(xué)習(xí)

2014.05.26

前幾篇侃了侃SVM的基本原理和一些相關(guān)知識(shí)，尤其是在SVM學(xué)習(xí)——軟間隔優(yōu)化這一篇，提到了SVM學(xué)習(xí)器的兩種形式，常被叫做L1-SVM和L2-SVM，這兩種形式的區(qū)別在損失函數(shù)的形式上，令訓(xùn)練樣例為 $(x_i,y_i)$ ， $y_i$ 取值為-1或+1，

軟間隔優(yōu)化的原始形式為：

$min\quad\quad\quad\quad \frac{1}{2}<w,w>+C\sum\limits_{i=1}^{n}\xi(w,b,x_i,y_i)$

當(dāng)損失函數(shù) $\xi(w,b,x_i,y_i)$ $=max(0,(1-y_i(<w,x_i>+b)))$ 時(shí)就叫做L1-SVM，當(dāng)損失函數(shù) $\xi(w,b,x_i,y_i)$ $={max(0,(1-y_i(<w,x_i>+b)))}^2$ 時(shí)叫做L2-SVM，實(shí)際當(dāng)中解這個(gè)問(wèn)題其實(shí)可以從原始形式開(kāi)始，也可以從其對(duì)偶形式開(kāi)始：

設(shè) $\alpha=(\alpha_1,\alpha_2,...\alpha_i)^T$ ， i=(1,2,...n) ，則兩種軟間隔優(yōu)化的對(duì)偶形式可以用統(tǒng)一的形式表示：

$max\quad \quad \quad W(\alpha)=e^T\alpha-\frac{1}{2}\alpha^TM\alpha$

$s.t. \quad\quad\quad 0\leq \alpha \leq U$ 其中： e^T 為單位列向量， M=M^'+D ， $M_{i,j}^'=y_iy_j<x_i,x_j>$ ，為對(duì)角矩陣

對(duì)于L1-SVM： $D_{ii}=0$ && U=C ；對(duì)于L2-SVM： $D_{ii}=1/(2C)$ && $U=+\infty$ 。

不管哪種形式，都是一個(gè)凸二次規(guī)劃問(wèn)題，不論是向量維度大或者是樣本量很大的時(shí)候，求解這個(gè)優(yōu)化問(wèn)題難度都不小，于是在解得稀疏性(比如只需要得到支持向量)、目標(biāo)函數(shù)的凸性等方面動(dòng)腦筋，得到一些較有效率的方法，比如SMO(Sequential Minimal Opimisation)、梯度下降法、Trust Region Newton Method、Coordinate Desent Method 等等，這里面呢，我對(duì)Coordinate Desent Method 比較感興趣，我就把我學(xué)到的東西說(shuō)一下。

先了解幾個(gè)概念：

1、度量空間：它是一個(gè)集合，在其中可以定義這個(gè)集合中元素之間的距離（叫做度量）的概念，這個(gè)距離滿足非負(fù)性、同一性、對(duì)稱(chēng)性以及三角不等式(類(lèi)似于咱們小時(shí)候?qū)W的，任意三角形，兩邊之和大于第三邊)，見(jiàn)http://zh.wikipedia.org/zh-cn/%E5%BA%A6%E9%87%8F%E7%A9%BA%E9%97%B4。

2、Lipschitz 函數(shù)：對(duì)于一個(gè)實(shí)值函數(shù)以及定義在實(shí)數(shù)域(實(shí)數(shù)域包含有理數(shù)和無(wú)理數(shù)而且它是完備的)上的集合，如果存在常數(shù)L>0，使得 $|f(x_2)-f(x_1)|\leq L||x_2-x_1||$ ，則這個(gè)函數(shù)叫做Lipschitz 函數(shù)（這里用2-范數(shù)來(lái)度量集合中兩個(gè)向量 x_1 和 x_2 的距離），它的幾何意義其實(shí)就是：曲線上的任意兩點(diǎn)的連線的斜率都有一個(gè)相同的上界，見(jiàn)http://zh.wikipedia.org/zh-cn/%E5%88%A9%E6%99%AE%E5%B8%8C%E8%8C%A8%E9%80%A3%E7%BA%8C。

直觀的看滿足Lipschitz 條件條件的函數(shù)一定是連續(xù)函數(shù)，而且曲線更加光滑，反之不然，比如在[0,1]上的函數(shù) $f(x)=\sqrt{x}$ ，顯然它不滿足Lipschitz 條件。

$T]_TQUFDEV6G~FHX9C{~$20$

定理1：如果定義在實(shí)數(shù)域上的集合是一個(gè)凸集，實(shí)值函數(shù)連續(xù)可微且在內(nèi)其梯度有界，則 $L=sup\{||\nabla f(x)||:x \in P\}$ 。

偶簡(jiǎn)單推導(dǎo)一下：

是一個(gè)凸集，那么根據(jù)凸集定義：對(duì)于凸集中的任意向量 x_1 和 x_2 (不是一般性，假設(shè) x_2>x_1 )，有 $\lambda x_1+(1-\lambda)x_2\in P$ ，其中 $0<\lambda<1$ 。顯然在[ x_1 , x_2 ]上連續(xù)，在( x_1 , x_2 )內(nèi)可導(dǎo)，而 $x_2-\lambda(x_2-x_1)$ 在 x_1 與 x_2 之間，根據(jù)拉格朗日中值定理有， $|f(x_2)-f(x_1)|=|(x_2-x_1)^T\nabla f(z)|$ ，其中 $x_2-\lambda(x_2-x_1)$ ，顯然 $|f(x_2)-f(x_1)|\leq sup\{||\nabla f(z)||:z\in P\}||x_2-x_1||$ 。

之所介紹Lipschitz 條件是因?yàn)?，如果可微函?shù)的梯度滿足Lipschitz連續(xù)條件，即： $||\nabla f(x)-\nabla f(x^')|| \leq L||x-x^'||$ ，則有：

$f(x) \leq f(x^') + \nabla f(x^')(x-x^')+\frac{L}{2}||x-x^'||^2$ (證明過(guò)程比較直白，偶就不寫(xiě)了，只要把f展開(kāi)成二階泰勒級(jí)數(shù)，然后代入Lipschitz連續(xù)條件得證)

基于梯度下降(GD)的算法應(yīng)該是最為大家所熟知的一類(lèi)算法(最速下降法、牛頓法、阻尼牛頓法、擬牛頓法等等)，我把滿足上述條件的不等式換成另一種寫(xiě)法吧：

$f(x) \leq f(x^{(k)}) + \nabla f(x^{(k)})(x-x^{(k)})+\frac{L}{2}||x-x^{(k)}||^2$

對(duì)于最小化問(wèn)題，總是希望每次迭代都可以讓 $f(x^{(k+1)}) \leq f(x^{(k)})$ ，這樣我們會(huì)越來(lái)越接近目標(biāo)，對(duì)于上式的右邊部分用函數(shù)代替，可以很容易知道，在 $x=S(x^{(k)}-\frac{\nabla f(x^{(k)})}{L} )$ 點(diǎn)，取到極小值(嘿嘿，比如求導(dǎo))，于是，梯度下降算法可以被概括為：

GD Algorithm：

1、選擇初始點(diǎn) $x^{(0)}$ ，令 k=0 ；

2、 while (不滿足結(jié)束條件){

$x^{(k+1)}=S(x^{(k)}-\frac{\nabla f(x^{(k)})}{L})$ ； //這里的S是個(gè)保序操作符（是保序操作符，指如果 $x\geq y$ ，則有 $T(x)\geq T(y)$ ）

k=k+1 ；

}

與GD較為不同的另一類(lèi)算法就叫做Coordinate Desent Method，這種方法的特點(diǎn)是，算法有兩層迭代，最內(nèi)層迭代是一個(gè)搜索過(guò)程，搜索是依據(jù)n維向量的n個(gè)坐標(biāo)方向分別搜索，每次迭代會(huì)將除了當(dāng)前方向外的其他方向分量固定，然后在此基礎(chǔ)上最小化目標(biāo)函數(shù)，下次迭代時(shí)會(huì)選擇另外一個(gè)分量進(jìn)行相同的處理，經(jīng)過(guò)了n次迭代后得到一個(gè)n維向量，然后更新目標(biāo)向量，接著繼續(xù)進(jìn)行外層的迭代，概括這個(gè)過(guò)程如下：

CD Algorithm ：

1、選擇初始點(diǎn) $x^{(0)}$ ，令 k=0 ；

2、 while (不滿足結(jié)束條件){

$x^{(k,0)}=x^{(k)}$

for(j=1;i<l;j++) { //假設(shè)特征空間維度為

$x_j^{(k,j)}=S(x_j^{(k,j-1)}-\frac{[\nabla f(x_j^{(k,j-1)})]_j }{L})$ ; //這里的S是個(gè)操作符

$x_i^{(k,j)}=x_i^{(k,j-1)}$ ; ( i <> j ）

}

$x^{(k+1)}=x^{(k,d)}$ ;

k=k+1 ；

}

還記著開(kāi)篇提到的L1-SVM和L2-SVM的統(tǒng)一形式吧，稍微轉(zhuǎn)換一下形式，并把 x_i^T 擴(kuò)展為 [x_i^T,1] ，把 w^T 擴(kuò)展為 [w^T,b] ：

$min \quad \quad \quad W(\alpha)=\frac{1}{2}\alpha^T M \alpha -e^T\alpha$

$s.t. \quad\quad\quad 0\leq \alpha \leq U$ 其中： e^T 為單位列向量， M=M^'+D ， $M_{i,j}^'=y_iy_j<x_i,x_j>$ ，為對(duì)角矩陣

對(duì)于L1-SVM： $D_{ii}=0$ && U=C ；對(duì)于L2-SVM： $D_{ii}=1/(2C)$ && $U=+\infty$ 。

下面介紹一種基于Coordinate Descent 的算法，該算法出自《A Dual Coordinate Descent Method for Large-scale Linear SVM》一文。

整個(gè)算法架構(gòu)同CD Algorithm。

1、假設(shè)樣本數(shù)為，當(dāng)前外層循環(huán)的索引為，當(dāng)前內(nèi)層循環(huán)索引為，其取值為 1....l+1 ,對(duì)于 $\alpha$ 向量有表示形式：

$\alpha^{k,i}=[\alpha_{1}^{k+1},\alpha_{2}^{k+1},\quad....\alpha_{i-1}^{k+1},\alpha_{i}^{k},\quad.....\alpha_{l}^{k}]^T$ ， $\forall i=2,.....l$ ；

$\alpha^{k,1}=\alpha^{k}$ ，表示還沒(méi)有開(kāi)始內(nèi)層循環(huán)時(shí)的狀態(tài)， $\alpha^{k,l+1}=\alpha^{k+1}$ ，表示對(duì)所有分量更新完畢。

2、內(nèi)層循環(huán)中的S操作的過(guò)程是求解子問(wèn)題：

$min \quad\quad\quad W(\alpha^{k,i}+de_i )$

$s.t. \quad\quad\quad 0 \leq \alpha^k_i \leq U$ ，其中 e_i=[0,... 0,1, 0,...0]T ，第個(gè)分量的值為1。

大家可以在紙上稍作推導(dǎo)，上面這個(gè)問(wèn)題的目標(biāo)函數(shù)可以表示為：

$W(\alpha^{k,i}+de_i)=\frac{1}{2}M_{i,i}d^2+\nabla _{i}W(\alpha^{k,i})d+\frac{1}{2}\alpha^TM\alpha -e^T\alpha$ ，其中 $\nabla _{i}f$ 表示梯度 $\nabla f$ 的第個(gè)分量

這是一個(gè)二次函數(shù)，除了帶d的部分以外可以看做一個(gè)常量，即上述形式為：

$W(\alpha^{k,i}+de_i)=\frac{1}{2}M_{i,i}d^2+\nabla _{i}W(\alpha^{k,i})d+Constant$

令 $\nabla_i^' W(\alpha)= \begin{cases} \nabla_i W(\alpha) & if \quad 0<\alpha_i<U\min(0,\nabla_i W(\alpha)) & if \quad \alpha_i=0\max(0,\nabla_i W(\alpha)) & if \quad \alpha_i=U \end{cases}$

1)、當(dāng) $\nabla_i^P W(\alpha^{k,i})=0$ 時(shí)不需要對(duì)當(dāng)前分量進(jìn)行更新；

2)、對(duì)上式求K-T點(diǎn)并考慮 $s.t. \quad\quad\quad 0 \leq \alpha^k_i \leq U$ 約束條件，如果 $M_{i,i}>0$ 則有：

$\alpha_i^{k,i+1}=min(max(\alpha_i^{k,i}-\frac{\nabla_iW(\alpha^{k,i})}{M_{i,i}},0),U)$

計(jì)算 $\nabla_i W(\alpha)=(M\alpha)_i-1=\sum\limits_{j=1}^l M_{i,j}\alpha_j-1$ ，就是將核矩陣的第行向量和 $\alpha$ 向量做內(nèi)積，這個(gè)操作代價(jià)很高，但是對(duì)于線性SVM，有 $w=\sum\limits_{i=1}^ly_i\alpha_ix_i$ (還記得那個(gè)互補(bǔ)條件吧，嘿嘿)，又有 M=M^'+D 、 $M_{i,j}^'=y_iy_j<x_i,x_j>$ ，于是上式就變成了 $\nabla_iW(\alpha)=y_iw^Tx_i-1+D_{i,i}\alpha_i$ ，這個(gè)計(jì)算的代價(jià)就沒(méi)有那么高了，顯然在更新 $\alpha$ 的時(shí)候需要對(duì)也更新，要是每次都計(jì)算 $w=\sum\limits_{i=1}^ly_i\alpha_ix_i$ 就代價(jià)太高了，所以文中利用 $\alpha$ 更新前和更新后的值來(lái)確定，如下：

$w=w+(\alpha-\alpha^')y_ix_i$ (這個(gè)方法很巧)

3)、當(dāng) $M_{ii}=0$ 時(shí)候，可知 x_i=0 ，這種情況只會(huì)出現(xiàn)在L1_SVM中，且此時(shí)沒(méi)有閾值項(xiàng)，就是那個(gè)向量里的分量1，否則 x_i=0 不可能滿足，此時(shí)新的 $\alpha$ 分量值就取 $U=C<\infty$ 。

A dual coordinate descent method for Linear SVM算法描述如下：

1、選擇初始點(diǎn) $\alpha$ ，

令 k=0 ，

$w=\sum\limits_{i=1}^ly_i\alpha_ix_i$ ；

2、 while (不滿足結(jié)束條件，這里可以設(shè)置一個(gè)精度條件){

for(j=1;i<l;j++) {

$G=y_iw^Tx_i-1+D_{i,i}\alpha_i$ ；

$PG= \begin{cases} G & if \quad 0<\alpha_i<U\min(0,G) & if \quad \alpha_i=0\max(0,G) & if \quad \alpha_i=U \end{cases}$ ；

$if(|PG| \neq 0)$ {

$\alpha_i^'=\alpha_i$ ；

$\alpha_i=min(max(\alpha_i-G/M_{i,i},0),U)$ ；

$w=w+(\alpha-\alpha^')y_ix_i$ ；

}

$x^{(k+1)}=x^{(k,d)}$ ;

k=k+1 ；

}

與GD方法相比，coordinate descent 類(lèi)方法的特點(diǎn)是每次迭代的代價(jià)較低，由于 $\alpha$ 各分量之間有前后依賴(lài)關(guān)系，所以感覺(jué)要實(shí)現(xiàn)并行有點(diǎn)困難，但是總的來(lái)說(shuō)，沒(méi)有最好的方法只有最適合的方法。

本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。

打開(kāi)APP，閱讀全文并永久保存查看更多類(lèi)似文章

當(dāng)支持向量機(jī)遇上神經(jīng)網(wǎng)絡(luò)：這項(xiàng)研究揭示了SVM、GAN、Wasserstein距離之間的關(guān)系

支持向量機(jī)(SVM)的約束和無(wú)約束優(yōu)化、理論和實(shí)現(xiàn)

數(shù)據(jù)挖掘十大經(jīng)典算法(3)：SVM支持向量機(jī)

深度學(xué)習(xí)六十問(wèn)！一位算法工程師經(jīng)歷30+場(chǎng)CV面試后總結(jié)的常見(jiàn)問(wèn)題合集下篇（含答案）

必看！10個(gè)最新圖像處理面試題，嘔心瀝血整理…

整理一份萬(wàn)字機(jī)器學(xué)習(xí)資料！

更多類(lèi)似文章 >>

免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版