支持向量機演講稿

支持向量機演講稿第一頁，共四十六頁，編輯于2023年，星期三SVM的學術文獻引用第二頁，共四十六頁，編輯于2023年，星期三SVM的學術文獻引用

VC維第三頁，共四十六頁，編輯于2023年，星期三SVM的學術文獻引用

結構風險最小化第四頁，共四十六頁，編輯于2023年，星期三SVM的學術文獻引用

結構風險最小化第五頁，共四十六頁，編輯于2023年，星期三SVM的學術文獻引用

結構風險最小化第六頁，共四十六頁，編輯于2023年，星期三SVM的學術文獻引用

結構風險最小化第七頁，共四十六頁，編輯于2023年，星期三SVM的學術文獻引用

結構風險最小化第八頁，共四十六頁，編輯于2023年，星期三SVM的學術文獻引用

結構風險最小化第九頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十一頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十二頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十三頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十四頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十五頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十六頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十七頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十八頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器第十九頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。第二十頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器我們就明白為何要選擇幾何間隔來作為評價一個解優(yōu)劣的指標了，原來幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了我們訓練階段的目標第二十一頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解第二十二頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解第二十三頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解第二十四頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解造成這種結果的原因是在描述問題的時候只考慮了目標，而沒有加入約束條件，約束條件就是在求解過程中必須滿足的條件，體現(xiàn)在我們的問題中就是樣本點必須在H1或H2的某一側（或者至少在H1和H2上），而不能跑到兩者中間。我們前文提到過把間隔固定為1，這是指把所有樣本點中間隔最小的那一點的間隔定為1（這也是集合的間隔的定義，有點繞嘴），也就意味著集合中的其他點間隔都不會小于1，按照間隔的定義，滿足這些條件就相當于讓下面的式子總是成立：yi[(w·xi)+b]≥1(i=1,2,…,l)（l是總的樣本數(shù)）但我們常常習慣讓式子的值和0比較，因而經(jīng)常用變換過的形式：

yi[(w·xi)+b]-1≥0(i=1,2,…,l)（l是總的樣本數(shù)）因此我們的兩類分類問題也被我們轉(zhuǎn)化成了它的數(shù)學形式，一個帶約束的最小值的問題：第二十五頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解第二十六頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解第二十七頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解那么w是誰決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個樣本點，三條直線的位置實際上就唯一確定了（因為我們求的是最優(yōu)的那三條，當然是唯一的），我們解優(yōu)化問題的過程也只不過是把這個確定了的東西算出來而已。樣本確定了w，用數(shù)學的語言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn式子中的αi是一個一個的數(shù)（在嚴格的證明過程中，這些α被稱為拉格朗日乘子），而xi是樣本點，因而是向量，n就是總樣本點的個數(shù)。為了方便描述，下面會用α1x1表示數(shù)字和向量的乘積，而用<x1,x2>表示向量x1,x2的內(nèi)積（也叫點積，注意與向量叉積的區(qū)別）。因此g(x)的表達式嚴格的形式應該是：g(x)=<w,x>+b第二十八頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解但是上面的式子還不夠好，回頭看看圖中正樣本和負樣本的位置，想像一下，不動所有點的位置，而只是把其中一個正樣本點定為負樣本點（也就是把一個點的形狀從圓形變?yōu)榉叫危?，結果怎么樣？三條直線都必須移動（因為對這三條直線的要求是必須把方形和圓形的點正確分開）！這說明w不僅跟樣本點的位置有關，還跟樣本的類別有關（也就是和樣本的“標簽”有關）。因此用下面這個式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn

（式1）其中的yi就是第i個樣本的標簽，它等于1或者-1。其實以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數(shù)，當然，更嚴格的說，這些樣本的一部分就可以確定，因為例如確定一條直線，只需要兩個點就可以，即便有三五個都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點，就叫做支持向量！第二十九頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解式子也可以用求和符號簡寫一下：

因此原來的g(x)表達式可以寫為：第三十頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--線性分類器的求解其實這里已經(jīng)簡化了，只不過在看不見的地方，以這樣的形式描述問題以后，我們的優(yōu)化問題少了很大一部分不等式約束（記得這是我們解不了極值問題的萬惡之源）。但是接下來先跳過線性分類器求解的部分，來看看SVM在線性分類器上所做的重大改進——核函數(shù)。第三十一頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--核函數(shù)之前一直在討論的線性分類器，只能對線性可分的樣本做處理。如果提供的樣本線性不可分，結果很簡單，線性分類器的求解程序會無限循環(huán)，永遠也解不出來。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點我們實在不原意放棄，所以采取這樣的方案。第三十二頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--核函數(shù)這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>在任意維度的空間中，這種形式的函數(shù)都是一個線性函數(shù)（只不過其中的a和y都是多維向量罷了），因為自變量y的次數(shù)不大于1。原來在二維空間中一個線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。第三十三頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--核函數(shù)拿文本分類舉例子，文本分類問題的原始空間是1000維的（即每個要被分類的文檔被表示為一個1000維的向量），在這個維度上問題是線性不可分的?，F(xiàn)在我們有一個2001維空間里的線性函數(shù)f(x’)=<w’,x’>+b它能夠?qū)⒃瓎栴}變得可分。式中的w’和x’都是2000維的向量，只不過w’是定值，而x’是變量，現(xiàn)在我們的輸入是一個1000維的向量x，分類的過程是先把x變換為2000維的向量x’，然后求這個變換后的向量x’與向量w’的內(nèi)積，再把這個內(nèi)積的值和b相加，就得到了結果，看結果大于閾值還是小于閾值就得到了分類結果。第三十四頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--核函數(shù)我們發(fā)現(xiàn)，其實只關心那個高維空間里內(nèi)積的值，那個值算出來了，分類結果就算出來了。而從理論上說，x’是經(jīng)由x變換來的，因此廣義上可以把它叫做x的函數(shù)（有一個x，就確定了一個x’），而w’是常量，它是一個低維空間里的常量w經(jīng)過變換得到的，所以給了一個w和x的值，就有一個確定的f(x’)值與其對應。這讓我們幻想，是否能有這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w’,x’>？如果有這樣的函數(shù)，那么當給了一個低維空間的輸入x以后，g(x)=K(w,x)+bf(x’)=<w’,x’>+b這兩個函數(shù)的計算結果就完全一樣，我們也就用不著費力找那個映射關系，直接拿低維的輸入往g(x)里面代就可以了。當然，這里的g(x)就不是線性函數(shù)啦，因為你不能保證K(w,x)這個表達式里的x次數(shù)不高于1。萬幸的是，這樣的K(w,x)確實存在，它被稱作核函數(shù)（核，kernel），而且還不止一個，事實上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個低維空間里的向量，能夠計算出經(jīng)過某個變換后在高維空間里的向量內(nèi)積值。第三十五頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--核函數(shù)前面說的求一個線性分類器，它的形式應該是：現(xiàn)在這個就是高維空間里的線性函數(shù)，這里就可以用一個低維空間里的函數(shù)（這個低維空間里的函數(shù)就不再是線性的啦）來代替，這個低維的分類函數(shù)為：再次發(fā)現(xiàn)：f(x’)和g(x)里的α，y，b全都是一樣一樣的！這就是說，盡管給的問題是線性不可分的，但是我們就硬當它是線性問題來求解，只不過求解過程中，凡是要求內(nèi)積的時候就用你選定的核函數(shù)來算。這樣求出來的α再和你選定的核函數(shù)一組合，就得到分類器啦！第三十六頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--核函數(shù)遺留的兩個問題：1．既然有很多的核函數(shù)，針對具體問題該怎么選擇？2．如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？第一個問題答案：對核函數(shù)的選擇，現(xiàn)在還缺乏指導原則！各種實驗的觀察結果（不光是文本分類）的確表明，某些問題用某些核函數(shù)效果很好，用另一些就很差，但是一般來講，徑向基核函數(shù)是不會出太大偏差的一種，首選。第二個問題的答案：松弛變量第三十七頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--松弛變量現(xiàn)在假設有另一個訓練集，只比原先這個訓練集多了一個樣本，映射到高維空間以后（當然，也使用了相同的核函數(shù)），也就多了一個樣本點，但是這個樣本的位置是右圖中的樣子。就是圖中黃色那個點，它是方形的，因而它是負類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數(shù)點線性不可分）叫做“近似線性可分”的問題。第三十八頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--松弛變量對于人來說，其實我們會覺得，更有可能的是，這個樣本點壓根就是錯誤，是噪聲，是提供訓練集的同學人工分類時一打瞌睡錯放進去的。所以我們會簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響。但這種對噪聲的容錯性是人的思維帶來的，我們的程序可沒有。由于我們原本的優(yōu)化問題的表達式中，確實要考慮所有的樣本點（不能忽略某一個，因為程序它怎么知道該忽略哪一個呢？），在此基礎上尋找正負類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。因此由上面的例子中也可以看出，硬間隔的分類法其結果容易受少數(shù)點的控制，這是很危險的。第三十九頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--松弛變量第四十頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--松弛變量第四十一頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--松弛變量第四十二頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--松弛變量第四十三頁，共四十六頁，編輯于2023年，星期三SVM的形成思路

--松弛變量一是并非所有的樣本點都有一個松弛變量與其對應。實際上只有“離群點”才有，或者也可以這么看，所有沒離群的點松弛變量都等于0。二是松弛變量的值實際上標示出了對應的點到底離群有多遠，值越大，點就越遠。三是懲罰因子C決定了你有多重視離群點帶來的損失，顯然當所有離群點的松弛變量的和一定時，你定的C越大，對目標函數(shù)的損失也越大，此時就暗示著你非常不愿意放棄這些離群點，最極端的情況是你把C定為無限大，這樣只要稍有一個點離群，目標函數(shù)的值馬上變成無限大，馬上讓問題變成無解，這就退化成了硬間隔問題。四是懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值，指定這個值以后，解一下，得到一個分類器，然后用測試數(shù)據(jù)看看結果怎么樣，如果不夠好，換一個C的值，再解一次優(yōu)化問題，得到另一個分類器，再看看效果，如此就