什么是機(jī)器學(xué)習(xí) （Machine Learning）

      機(jī)器學(xué)習(xí)是研究計(jì)算機(jī)怎樣模擬或?qū)崿F(xiàn)人類的學(xué)習(xí)行為，以獲取新的知識或技能，重新組織已有的知識結(jié)構(gòu)使之不斷改善自身的性能。它是人工智能的核心，是使計(jì)算機(jī)具有智能的根本途徑，其應(yīng)用遍及人工智能的各個(gè)領(lǐng)域。

機(jī)器學(xué)習(xí)的大致分類：

1）分類（模式識別）：要求系統(tǒng)依據(jù)已知的分類知識對輸入的未知模式（該模式的描述）作分析，以確定輸入模式的類屬，例如手寫識別（識別是不是這個(gè)數(shù)）。

2）問題求解：要求對于給定的目標(biāo)狀態(tài),尋找一個(gè)將當(dāng)前狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)的動作序列。

SVM一般是用來分類的（一般先分為兩類，再向多類推廣一生二，二生三，三生萬物哈）

問題的描述

向量表示:假設(shè)一個(gè)樣本有n個(gè)變量(特征)：Ⅹ= (X1,X2,…,Xn)T

樣本表示方法：

SVM線性分類器

SVM從線性可分情況下的最優(yōu)分類面發(fā)展而來。最優(yōu)分類面就是要求分類線不但能將兩類正確分開(訓(xùn)練錯(cuò)誤率為0),且使分類間隔最大。SVM考慮尋找一個(gè)滿足分類要求的超平面,并且使訓(xùn)練集中的點(diǎn)距離分類面盡可能的遠(yuǎn),也就是尋找一個(gè)分類面使它兩側(cè)的空白區(qū)域(margin)最大。

過兩類樣本中離分類面最近的點(diǎn)且平行于最優(yōu)分類面的超平面上H1,H2的訓(xùn)練樣本就叫做支持向量。

圖例：

問題描述：

假定訓(xùn)練數(shù)據(jù) ：

可以被分為一個(gè)超平面：

進(jìn)行歸一化：

此時(shí)分類間隔等于：

即使得：最大間隔最大等價(jià)于使最小

下面這兩張圖可以看一下，有個(gè)感性的認(rèn)識。那個(gè)好？

看下面這張圖：

       下面我們要開始優(yōu)化上面的式子，因?yàn)橥茖?dǎo)要用到拉格朗日定理和KKT條件，所以我們先了解一下相關(guān)知識。在求取有約束條件的優(yōu)化問題時(shí)，拉格朗日乘子法（Lagrange Multiplier) 和KKT條件是非常重要的兩個(gè)求取方法，對于等式約束的優(yōu)化問題，可以應(yīng)用拉格朗日乘子法去求取最優(yōu)值；如果含有不等式約束，可以應(yīng)用KKT條件去求取。當(dāng)然，這兩個(gè)方法求得的結(jié)果只是必要條件，只有當(dāng)是凸函數(shù)的情況下，才能保證是充分必要條件。KKT條件是拉格朗日乘子法的泛化。之前學(xué)習(xí)的時(shí)候，只知道直接應(yīng)用兩個(gè)方法，但是卻不知道為什么拉格朗日乘子法（Lagrange Multiplier) 和KKT條件能夠起作用，為什么要這樣去求取最優(yōu)值呢？

拉格朗日乘子法和KKT條件

定義：給定一個(gè)最優(yōu)化問題：

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

制約條件：

定義拉格朗日函數(shù)為：

求偏倒方程

可以求得的值。這個(gè)就是神器拉格朗日乘子法。

上面的拉格朗日乘子法還不足以幫我們解決所有的問題，下面引入不等式約束

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

制約條件變?yōu)椋?/p>

定義拉格朗日函數(shù)為：

可以列出方程：

新增加的條件被稱為KKT條件

KKT條件詳解

對于含有不等式約束的優(yōu)化問題，如何求取最優(yōu)值呢？常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標(biāo)函數(shù)全部寫為一個(gè)式子L(a, b, x)= f(x) + a*g(x)+b*h(x)，KKT條件是說最優(yōu)值必須滿足以下條件：

1. L(a, b, x)對x求導(dǎo)為零；

2. h(x) =0;

3. a*g(x) = 0;

求取這三個(gè)等式之后就能得到候選最優(yōu)值。其中第三個(gè)式子非常有趣，因?yàn)間(x)<=0，如果要滿足這個(gè)等式，必須a=0或者g(x)=0. 這是SVM的很多重要性質(zhì)的來源，如支持向量的概念。

二. 為什么拉格朗日乘子法（Lagrange Multiplier) 和KKT條件能夠得到最優(yōu)值？

為什么要這么求能得到最優(yōu)值？先說拉格朗日乘子法，設(shè)想我們的目標(biāo)函數(shù)z = f(x), x是向量, z取不同的值，相當(dāng)于可以投影在x構(gòu)成的平面（曲面）上，即成為等高線，如下圖，目標(biāo)函數(shù)是f(x, y)，這里x是標(biāo)量，虛線是等高線，現(xiàn)在假設(shè)我們的約束g(x)=0，x是向量，在x構(gòu)成的平面或者曲面上是一條曲線，假設(shè)g(x)與等高線相交，交點(diǎn)就是同時(shí)滿足等式約束條件和目標(biāo)函數(shù)的可行域的值，但肯定不是最優(yōu)值，因?yàn)橄嘟灰馕吨隙ㄟ€存在其它的等高線在該條等高線的內(nèi)部或者外部，使得新的等高線與目標(biāo)函數(shù)的交點(diǎn)的值更大或者更小，只有到等高線與目標(biāo)函數(shù)的曲線相切的時(shí)候，可能取得最優(yōu)值，如下圖所示，即等高線和目標(biāo)函數(shù)的曲線在該點(diǎn)的法向量必須有相同方向，所以最優(yōu)值必須滿足：f(x)的梯度 = a* g(x)的梯度，a是常數(shù)，表示左右兩邊同向。這個(gè)等式就是L(a,x)對參數(shù)求導(dǎo)的結(jié)果。（上述描述，我不知道描述清楚沒，如果與我物理位置很近的話，直接找我，我當(dāng)面講好理解一些，注：下圖來自wiki）。

而KKT條件是滿足強(qiáng)對偶條件的優(yōu)化問題的必要條件，可以這樣理解：我們要求min f(x), L(a, b, x) = f(x) + a*g(x) + b*h(x)，a>=0，我們可以把f(x)寫為：max_{a,b} L(a,b,x)，為什么呢？因?yàn)閔(x)=0, g(x)<=0，現(xiàn)在是取L(a,b,x)的最大值，a*g(x)是<=0，所以L(a,b,x)只有在a*g(x) = 0的情況下才能取得最大值，否則，就不滿足約束條件，因此max_{a,b} L(a,b,x)在滿足約束條件的情況下就是f(x)，因此我們的目標(biāo)函數(shù)可以寫為 min_x max_{a,b} L(a,b,x)。如果用對偶表達(dá)式： max_{a,b} min_x  L(a,b,x)，由于我們的優(yōu)化是滿足強(qiáng)對偶的（強(qiáng)對偶就是說對偶式子的最優(yōu)值是等于原問題的最優(yōu)值的），所以在取得最優(yōu)值x0的條件下，它滿足 f(x0) = max_{a,b} min_x  L(a,b,x) = min_x max_{a,b} L(a,b,x) =f(x0)，我們來看看中間兩個(gè)式子發(fā)生了什么事情：

f(x0) = max_{a,b} min_x  L(a,b,x) =  max_{a,b} min_x f(x) + a*g(x) + b*h(x) =  max_{a,b} f(x0)+a*g(x0)+b*h(x0) = f(x0)

可以看到上述加黑的地方本質(zhì)上是說 min_x f(x) + a*g(x) + b*h(x) 在x0取得了最小值，用Fermat定理，即是說對于函數(shù) f(x) + a*g(x) + b*h(x)，求取導(dǎo)數(shù)要等于零，即

f(x)的梯度+a*g(x)的梯度+ b*h(x)的梯度 = 0

這就是KKT條件中第一個(gè)條件：L(a, b, x)對x求導(dǎo)為零。

而之前說明過，a*g(x) = 0，這時(shí)KKT條件的第3個(gè)條件，當(dāng)然已知的條件h(x)=0必須被滿足，所有上述說明，滿足強(qiáng)對偶條件的優(yōu)化問題的最優(yōu)值都必須滿足KKT條件，即上述說明的三個(gè)條件?？梢园袺KT條件視為是拉格朗日乘子法的泛化。

上面跑題了，下面我繼續(xù)我們的SVM之旅。

經(jīng)過拉格朗日乘子法和KKT條件推導(dǎo)之后

最終問題轉(zhuǎn)化為：

最大化：

條件：

這個(gè)是著名的QP問題。決策面：其中 為問題的優(yōu)化解。

松弛變量（slack vaviable）

由于在采集數(shù)據(jù)的過程中，也可能有誤差（如圖）

所以我們引入松弛變量對問題進(jìn)行優(yōu)化。

式子就變?yōu)?img title="clip_image052" alt="" src="http://img.jbzj.com/file_images/article/201712/2017122709083435.jpg" />

最終轉(zhuǎn)化為下面的優(yōu)化問題：

其中的C是懲罰因子，是一個(gè)由用戶去指定的系數(shù)，表示對分錯(cuò)的點(diǎn)加入多少的懲罰，當(dāng)C很大的時(shí)候，分錯(cuò)的點(diǎn)就會更少，但是過擬合的情況可能會比較嚴(yán)重，當(dāng)C很小的時(shí)候，分錯(cuò)的點(diǎn)可能會很多，不過可能由此得到的模型也會不太正確。

上面那個(gè)個(gè)式子看似復(fù)雜，現(xiàn)在我?guī)Т蠹乙黄鹜频挂幌?/p>

……

…(草稿紙上，敲公式太煩人了)

最終得到：

最大化：

條件：

呵呵，是不是感覺和前面的式子沒啥區(qū)別內(nèi)，親，數(shù)學(xué)就是這么美妙啊。

這個(gè)式子看起來beautiful，但是多數(shù)情況下只能解決線性可分的情況，只可以對線性可分的樣本做處理。如果提供的樣本線性不可分，結(jié)果很簡單，線性分類器的求解程序會無限循環(huán)，永遠(yuǎn)也解不出來。但是不怕不怕。我們有殺手锏還沒有出呢。接著咱要延伸到一個(gè)新的領(lǐng)域：核函數(shù)。嘻嘻，相信大家都應(yīng)該聽過這廝的大名，這個(gè)東東在60年代就提出來，可是直到90年代才開始火起來（第二春哈），主要是被Vapnik大大翻出來了。這也說明計(jì)算機(jī)也要多研讀經(jīng)典哈，不是說過時(shí)了就不看的，有些大師的論文還是有啟發(fā)意義的。廢話不多說，又跑題了。

核函數(shù)

那到底神馬是核函數(shù)呢？

介個(gè)咱得先介紹一下VC維的概念。

為了研究經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化函數(shù)集的學(xué)習(xí)一致收斂速度和推廣性，SLT定義了一些指標(biāo)來衡量函數(shù)集的性能，其中最重要的就是VC維(Vapnik-Chervonenkis Dimension)。

VC維定義：對于一個(gè)指示函數(shù)（即只有0和1兩種取值的函數(shù)）集，如果存在h個(gè)樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開，則稱函數(shù)集能夠把h個(gè)樣本打散，函數(shù)集的VC維就是能夠打散的最大樣本數(shù)目。

如果對任意的樣本數(shù)，總有函數(shù)能打散它們，則函數(shù)集的VC維就是無窮大。

看圖比較方便（三個(gè)點(diǎn)分類，線性都可分的）。

如果四個(gè)點(diǎn)呢？哈哈，右邊的四個(gè)點(diǎn)要分為兩個(gè)類，可能就分不啦。

如果四個(gè)點(diǎn)，一條線可能就分不過來啦。

一般而言,VC維越大, 學(xué)習(xí)能力就越強(qiáng),但學(xué)習(xí)機(jī)器也越復(fù)雜。

目前還沒有通用的關(guān)于計(jì)算任意函數(shù)集的VC維的理論,只有對一些特殊函數(shù)集的VC維可以準(zhǔn)確知道。

N維實(shí)數(shù)空間中線性分類器和線性實(shí)函數(shù)的VC維是n+1。

Sin(ax)的VC維為無窮大。

對于給定的學(xué)習(xí)函數(shù)集,如何計(jì)算其VC維是當(dāng)前統(tǒng)計(jì)學(xué)習(xí)理論研究中有待解決的一個(gè)難點(diǎn)問題，各位童鞋有興趣可以去研究研究。

咱們接著要說說為啥要映射。

例子是下面這張圖：

下面這段來自百度文庫

俺覺得寫的肯定比我好，所以咱就選擇站在巨人的肩膀上啦。

我們把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類，兩邊的黑色部分里的點(diǎn)定為負(fù)類。試問能找到一個(gè)線性函數(shù)把兩類正確分開么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。

但我們可以找到一條曲線，例如下面這一條：

顯然通過點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類別（你在橫軸上隨便找一點(diǎn)，算算這一點(diǎn)的函數(shù)值，會發(fā)現(xiàn)負(fù)類的點(diǎn)函數(shù)值一定比0大，而正類的一定比0?。?。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫為：

問題只是它不是一個(gè)線性函數(shù)，但是，下面要注意看了，新建一個(gè)向量y和a：

這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來的g(x)。用內(nèi)積的形式寫你可能看不太清楚，實(shí)際上f(y)的形式就是：

g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)（只不過其中的a和y都是多維向量罷了），因?yàn)樽宰兞縴的次數(shù)不大于1。

看出妙在哪了么？原來在二維空間中一個(gè)線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。

而轉(zhuǎn)化最關(guān)鍵的部分就在于找到x到y(tǒng)的映射方法。遺憾的是，如何找到這個(gè)映射，沒有系統(tǒng)性的方法（也就是說，純靠猜和湊）。具體到我們的文本分類問題，文本被表示為上千維的向量，即使維數(shù)已經(jīng)如此之高，也常常是線性不可分的，還要向更高的空間轉(zhuǎn)化。其中的難度可想而知。

為什么說f(y)=ay是四維空間里的函數(shù)?

大家可能一時(shí)沒看明白。回想一下我們二維空間里的函數(shù)定義   g(x)=ax+b 變量x是一維的，為什么說它是二維空間里的函數(shù)呢？因?yàn)檫€有一個(gè)變量我們沒寫出來，它的完整形式其實(shí)是   y=g(x)=ax+b 即   y=ax+b 看看，有幾個(gè)變量？兩個(gè)。那是幾維空間的函數(shù)？ 再看看 f(y)=ay 里面的y是三維的變量，那f(y)是幾維空間里的函數(shù)？

用一個(gè)具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運(yùn)作，想象一下，我們文本分類問題的原始空間是1000維的（即每個(gè)要被分類的文檔被表示為一個(gè)1000維的向量），在這個(gè)維度上問題是線性不可分的?，F(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù)

f(x')=<w',x'>+b

注意向量的右上角有個(gè) '哦。它能夠?qū)⒃瓎栴}變得可分。式中的 w'和x'都是2000維的向量，只不過w'是定值，而x'是變量（好吧,嚴(yán)格說來這個(gè)函數(shù)是2001維的,哈哈），現(xiàn)在我們的輸入呢，是一個(gè)1000維的向量x，分類的過程是先把x變換為2000維的向量x'，然后求這個(gè)變換后的向量x'與向量w'的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。

你發(fā)現(xiàn)了什么？我們其實(shí)只關(guān)心那個(gè)高維空間里內(nèi)積的值，那個(gè)值算出來了，分類結(jié)果就算出來了。而從理論上說， x'是經(jīng)由x變換來的，因此廣義上可以把它叫做x的函數(shù)（有一個(gè)x，就確定了一個(gè)x'，對吧，確定不出第二個(gè)），而w'是常量，它是一個(gè)低維空間里的常量w經(jīng)過變換得到的，所以給了一個(gè)w 和x的值，就有一個(gè)確定的f(x')值與其對應(yīng)。這讓我們幻想，是否能有這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w',x'>？

如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后，

g(x)=K(w,x)+b

f(x')=<w',x'>+b

這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個(gè)映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了（再次提醒，這回的g(x)就不是線性函數(shù)啦，因?yàn)槟悴荒鼙ＷCK(w,x)這個(gè)表達(dá)式里的x次數(shù)不高于1哦）。

萬幸的是，這樣的K(w,x)確實(shí)存在（發(fā)現(xiàn)凡是我們?nèi)祟惸芙鉀Q的問題，大都是巧得不能再巧，特殊得不能再特殊的問題，總是恰好有些能投機(jī)取巧的地方才能解決，由此感到人類的渺?。?，它被稱作核函數(shù)（核，kernel），而且還不止一個(gè)，事實(shí)上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過某個(gè)變換后在高維空間里的向量內(nèi)積值。幾個(gè)比較常用的核函數(shù)，俄，教課書里都列過，我就不敲了（懶！）。

回想我們上節(jié)說的求一個(gè)線性分類器，它的形式應(yīng)該是：

現(xiàn)在這個(gè)就是高維空間里的線性函數(shù)（為了區(qū)別低維和高維空間里的函數(shù)和向量，我改了函數(shù)的名字，并且給w和x都加上了 '），我們就可以用一個(gè)低維空間里的函數(shù)（再一次的，這個(gè)低維空間里的函數(shù)就不再是線性的啦）來代替，

又發(fā)現(xiàn)什么了？f(x') 和g(x)里的α，y，b全都是一樣一樣的！這就是說，盡管給的問題是線性不可分的，但是我們就硬當(dāng)它是線性問題來求解，只不過求解過程中，凡是要求內(nèi)積的時(shí)候就用你選定的核函數(shù)來算。這樣求出來的α再和你選定的核函數(shù)一組合，就得到分類器啦！

明白了以上這些，會自然的問接下來兩個(gè)問題：

1． 既然有很多的核函數(shù)，針對具體問題該怎么選擇？

2． 如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？

第一個(gè)問題現(xiàn)在就可以回答你：對核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則！各種實(shí)驗(yàn)的觀察結(jié)果（不光是文本分類）的確表明，某些問題用某些核函數(shù)效果很好，用另一些就很差，但是一般來講，徑向基核函數(shù)是不會出太大偏差的一種，首選。（我做文本分類系統(tǒng)的時(shí)候，使用徑向基核函數(shù)，沒有參數(shù)調(diào)優(yōu)的情況下，絕大部分類別的準(zhǔn)確和召回都在85%以上。

感性理解，映射圖：

常用的兩個(gè)Kernel函數(shù)：

多項(xiàng)式核函數(shù)：

高斯核函數(shù)：

定義：

將核函數(shù)帶入，問題又轉(zhuǎn)化為線性問題啦，如下：

求，其中

式子是有了，但是如何求結(jié)果呢？不急不急，我會帶著大家一步一步的解決這個(gè)問題，并且通過動手編程使大家對這個(gè)有個(gè)問題有個(gè)直觀的認(rèn)識。（PS：大家都對LIBSVM太依賴了，這樣無助于深入的研究與理解，而且我覺得自己動手實(shí)現(xiàn)的話會比較有成就感）

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論