/*先把標(biāo)題給寫(xiě)了、這樣就能經(jīng)常提醒自己*/

1. 感知機(jī)模型

我們先來(lái)定義一下什么是感知機(jī)。所謂感知機(jī)，就是二類(lèi)分類(lèi)的線(xiàn)性分類(lèi)模型，其輸入為樣本的特征向量，輸出為樣本的類(lèi)別，取+1和-1二值，即通過(guò)某樣本的特征，就可以準(zhǔn)確判斷該樣本屬于哪一類(lèi)。顧名思義，感知機(jī)能夠解決的問(wèn)題首先要求特征空間是線(xiàn)性可分的，再者是二類(lèi)分類(lèi)，即將樣本分為{+1, -1}兩類(lèi)。從比較學(xué)術(shù)的層面來(lái)說(shuō)，由輸入空間到輸出空間的函數(shù)：

???????????????????????????????????????????????????????????????????????????????????????????????????????? （1）

稱(chēng)為感知機(jī)，w和b為感知機(jī)參數(shù)，w為權(quán)值（weight），b為偏置（bias）。sign為符號(hào)函數(shù)：

???????????????????????????????????????????????????????????????????????????????????????????????????????? （2）

感知機(jī)模型的假設(shè)空間是定義在特征空間中的所有線(xiàn)性分類(lèi)模型，即函數(shù)集合{f|f(x) = w·x + b}。在感知機(jī)的定義中，線(xiàn)性方程w·x + b = 0對(duì)應(yīng)于問(wèn)題空間中的一個(gè)超平面S，位于這個(gè)超平面兩側(cè)的樣本分別被歸為兩類(lèi)，例如下圖，紅色作為一類(lèi)，藍(lán)色作為另一類(lèi)，它們的特征很簡(jiǎn)單，就是它們的坐標(biāo)

圖1

作為監(jiān)督學(xué)習(xí)的一種方法，感知機(jī)學(xué)習(xí)由訓(xùn)練集求得感知機(jī)模型，即求得模型參數(shù)w，b，這里x和y分別是特征向量和類(lèi)別（也稱(chēng)為目標(biāo)）。基于此，感知機(jī)模型可以對(duì)新的輸入樣本進(jìn)行分類(lèi)。

前面半抄書(shū)半自說(shuō)自話(huà)把感知機(jī)的定義以及是用來(lái)干嘛的簡(jiǎn)單記錄了一下，作為早期的機(jī)器學(xué)習(xí)方法（1957年由Frank Rosenblatt提出），它是最簡(jiǎn)單的前饋神經(jīng)網(wǎng)絡(luò)，對(duì)之后的機(jī)器學(xué)習(xí)方法如神經(jīng)網(wǎng)絡(luò)起一個(gè)基礎(chǔ)的作用，下一節(jié)將詳細(xì)介紹感知機(jī)學(xué)習(xí)策略。

2. 感知機(jī)學(xué)習(xí)策略

上節(jié)說(shuō)到，感知機(jī)是一個(gè)簡(jiǎn)單的二類(lèi)分類(lèi)的線(xiàn)性分類(lèi)模型，要求我們的樣本是線(xiàn)性可分的，什么樣的樣本是線(xiàn)性可分的呢？舉例來(lái)說(shuō)，在二維平面中，可以用一條直線(xiàn)將+1類(lèi)和-1類(lèi)完美分開(kāi)，那么這個(gè)樣本空間就是線(xiàn)性可分的。如圖1就是線(xiàn)性可分的，圖2中的樣本就是線(xiàn)性不可分的，感知機(jī)就不能處理這種情況。因此，在本章中的所有問(wèn)題都基于一個(gè)前提，就是問(wèn)題空間線(xiàn)性可分。

圖2

為方便說(shuō)明問(wèn)題，我們假設(shè)數(shù)據(jù)集中所有的的實(shí)例i，有；對(duì)的實(shí)例有。

這里先給出輸入空間中任一點(diǎn)到超平面S的距離：

?????????????????????????????????????????????????????????????????????????????????????????????????????????????? （3）

這里||w||是w的范數(shù)。

對(duì)于誤分類(lèi)的數(shù)據(jù)，根據(jù)我們之前的假設(shè)，有

????????????????????????????????????????????????????????????????????????????????????????????????????????? （4）

因此誤分類(lèi)點(diǎn)到超平面S的距離可以寫(xiě)作：

??????????????????????????????????????????????????????????????????????????????????????????????????????????? （5）

假設(shè)超平面S的誤分類(lèi)點(diǎn)集合為M，那么所有誤分類(lèi)點(diǎn)到超平面S的總距離為

??????????????????????????????????????????????????????????????????????????????????????????????????? （6）

這里的||w||值是固定的，不必考慮，這樣就得到了感知機(jī)學(xué)習(xí)的損失函數(shù)。根據(jù)我們的定義，這個(gè)損失函數(shù)自然是越小越好，因?yàn)檫@樣就代表著誤分類(lèi)點(diǎn)越少、誤分類(lèi)點(diǎn)距離超平面S的距離越近，即我們的分類(lèi)面越正確。顯然，這個(gè)損失函數(shù)是非負(fù)的，若所有的樣本都分類(lèi)正確，那么我們的損失函數(shù)值為0。一個(gè)特定的樣本集T的損失函數(shù)：在誤分類(lèi)時(shí)是參數(shù)w，b的線(xiàn)性函數(shù)。也就是說(shuō)，為求得正確的參數(shù)w，b，我們的目標(biāo)函數(shù)為

????????????????????????????????????????????????????????????????????????????????????????? （7）

而它是連續(xù)可導(dǎo)的，這就使得我們可以比較容易的求得其最小值。

感知機(jī)學(xué)習(xí)的策略是在假設(shè)空間中選取使我們的損失函數(shù)（7）最小的模型參數(shù)w,b，即感知機(jī)模型。

根據(jù)感知機(jī)定義以及我們的假設(shè)，得到了感知機(jī)的模型，即目標(biāo)函數(shù)（7），將其最小化的本質(zhì)就是使得分類(lèi)面S盡可能的正確，下一節(jié)介紹將其最小化的方法——隨機(jī)梯度下降。

3. 感知機(jī)學(xué)習(xí)算法

根據(jù)感知機(jī)學(xué)習(xí)的策略，我們已經(jīng)將尋找超平面S的問(wèn)題轉(zhuǎn)化為求解式（7）的最優(yōu)化問(wèn)題，最優(yōu)化的方法是隨機(jī)梯度下降法，書(shū)中介紹了兩種形式：原始形式和對(duì)偶形式，并證明了在訓(xùn)練集線(xiàn)性可分時(shí)算法的收斂性。

3.1 原始形式

所謂原始形式，就是我們用梯度下降的方法，對(duì)參數(shù)w和b進(jìn)行不斷的迭代更新。具體來(lái)說(shuō)，就是先任意選取一個(gè)超平面，對(duì)應(yīng)的參數(shù)分別為和，當(dāng)然現(xiàn)在是可以任意賦值的，比如說(shuō)選取為全為0的向量，的值為0。然后用梯度下降不斷地極小化損失函數(shù)（7)。由于隨機(jī)梯度下降（stochastic?????gradient descent）的效率要高于批量梯度下降（batch gradient descent）（詳情可參考Andrew Ng教授的 講義 ，在Part 1的LMS algorithm部分），所以這里采用隨機(jī)梯度下降的方法，每次隨機(jī)選取一個(gè)誤分類(lèi)點(diǎn)對(duì)w和b進(jìn)行更新。

設(shè)誤分類(lèi)點(diǎn)集合M是固定的，為求式（7）的最小值，我們需要知道往哪個(gè)方向下降速率最快，這是可由對(duì)損失函數(shù)L(w, b)求梯度得到，L(w, b)的梯度為

接下來(lái)隨機(jī)選取一個(gè)誤分類(lèi)點(diǎn)對(duì)w,b進(jìn)行更新

????????????????????????????????????????????????????????????????????????????????????????????????????????????????（8）

??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????（9）

其中為步長(zhǎng)，也稱(chēng)為學(xué)習(xí)速率（learning rate），一般在0到1之間取值，步長(zhǎng)越大，我們梯度下降的速度越快，也就能更快接近極小點(diǎn)。如果步長(zhǎng)過(guò)大，就有直接跨過(guò)極小點(diǎn)導(dǎo)致函數(shù)發(fā)散的問(wèn)題；如果步長(zhǎng)過(guò)小，可能會(huì)耗費(fèi)比較長(zhǎng)的時(shí)間才能達(dá)到極小點(diǎn)。通過(guò)這樣的迭代，我們的損失函數(shù)就不斷減小，直到為0。綜上所述，得到如下算法：

算法1 （感知機(jī)學(xué)習(xí)算法的原始形式）

輸入：訓(xùn)練數(shù)據(jù)集，其中，，i = 1,2,…,N；學(xué)習(xí)率

輸出：w，b；感知機(jī)模型

（1）選取初始值，

（2）在訓(xùn)練集中選取數(shù)據(jù)

（3）如果（從公式（3）變換而來(lái)）

（4）轉(zhuǎn)至（2），直至訓(xùn)練集中沒(méi)有誤分類(lèi)點(diǎn)

這種學(xué)習(xí)算法直觀(guān)上有如下解釋?zhuān)寒?dāng)一個(gè)樣本被誤分類(lèi)時(shí)，就調(diào)整w和b的值，使超平面S向誤分類(lèi)點(diǎn)的一側(cè)移動(dòng)，以減少該誤分類(lèi)點(diǎn)到超平面的距離，直至超平面越過(guò)該點(diǎn)使之被正確分類(lèi)。

書(shū)上還給出了一個(gè)例題，這是我推崇這本書(shū)的原因之一，凡是只講理論不給例子的行為都是耍流氓！

例1? 如圖3所示的訓(xùn)練數(shù)據(jù)集，其正實(shí)例點(diǎn)是，，負(fù)實(shí)例點(diǎn)是，試用感知機(jī)學(xué)習(xí)算法的原始形式求感知機(jī)模型，即求出w和b。這里，

圖3

這里我們?nèi)〕踔担　＞唧w問(wèn)題解釋不寫(xiě)了，求解的方法就是 算法1 。下面給出這道題的Java代碼（終于有一段是自己純?cè)瓌?chuàng)的了）。

          
            package
          
          
             org.juefan.perceptron;

          
          
            import
          
          
             java.util.ArrayList;

          
          
            import
          
          
             org.juefan.basic.FileIO;

          
          
            public
          
          
            class
          
          
             PrimevalPerceptron {
    
    
          
          
            public
          
          
            static
          
           ArrayList<Integer> w  = 
          
            new
          
           ArrayList<>
          
            ();
    
          
          
            public
          
          
            static
          
          
            int
          
          
             b ;
    
    
          
          
            /*
          
          
            初始化參數(shù)
          
          
            */
          
          
            public
          
          
             PrimevalPerceptron(){
        w.add(
          
          5
          
            );
        w.add(
          
          -2
          
            );
        b 
          
          = 3
          
            ;
    }
    
    
          
          
            /**
          
          
            
     * 判斷是否分類(lèi)正確
     * 
          
          
            @param
          
          
             data 待判斷數(shù)據(jù)
     * 
          
          
            @return
          
          
             返回判斷正確與否
     
          
          
            */
          
          
            public
          
          
            static
          
          
            boolean
          
          
             getValue(Data data){
        
          
          
            int
          
           state = 0
          
            ;
        
          
          
            for
          
          (
          
            int
          
           i = 0; i < data.x.size(); i++
          
            ){
            state 
          
          += w.get(i) *
          
             data.x.get(i);
        }
        state 
          
          +=
          
             b;
        
          
          
            return
          
           state * data.y > 0? 
          
            true
          
          : 
          
            false
          
          
            ;    
    }
    
    
          
          
            //
          
          
            此算法基于數(shù)據(jù)是線(xiàn)性可分的，如果線(xiàn)性不可分，則會(huì)進(jìn)入死循環(huán)
          
          
            public
          
          
            static
          
          
            boolean
          
           isStop(ArrayList<Data>
          
             datas){
        
          
          
            boolean
          
           isStop = 
          
            true
          
          
            ;
        
          
          
            for
          
          
            (Data data: datas){
            isStop 
          
          = isStop &&
          
             getValue(data);
        }
        
          
          
            return
          
          
             isStop;
    }
    
    
          
          
            public
          
          
            static
          
          
            void
          
          
             main(String[] args) {
        PrimevalPerceptron model 
          
          = 
          
            new
          
          
             PrimevalPerceptron();
        ArrayList
          
          <Data> datas = 
          
            new
          
           ArrayList<>
          
            ();
        FileIO fileIO 
          
          = 
          
            new
          
          
             FileIO();
        fileIO.setFileName(
          
          ".//file//perceptron.txt"
          
            );
        fileIO.FileRead();
        
          
          
            for
          
          
            (String data: fileIO.fileList){
            datas.add(
          
          
            new
          
          
             Data(data));
        }
    
        
          
          
            /**
          
          
            
         * 如果全部數(shù)據(jù)都分類(lèi)正確則結(jié)束迭代
         
          
          
            */
          
          
            while
          
          (!
          
            isStop(datas)){
            
          
          
            for
          
          (
          
            int
          
           i = 0; i < datas.size(); i++
          
            ){
                
          
          
            if
          
          (!getValue(datas.get(i))){  
          
            //
          
          
            這里面可以理解為是一個(gè)簡(jiǎn)單的梯度下降法
          
          
            for
          
          (
          
            int
          
           j = 0; j < datas.get(i).x.size(); j++
          
            )
                    w.set(j, w.get(j) 
          
          + datas.get(i).y *
          
             datas.get(i).x.get(j));
                    b 
          
          +=
          
             datas.get(i).y;
                    System.out.println(w 
          
          + "\t" +
          
             b);
                }
            }
        }    
        System.out.println(w 
          
          + "\t" + b);        
          
            //
          
          
            輸出最終的結(jié)果
          
          
                }
}
          
        

最后解得(這里應(yīng)該是寫(xiě)錯(cuò)了，最終結(jié)果b=-3）。不過(guò)，如果選取的初值不同，或者選取的誤分類(lèi)點(diǎn)不同，我們得到的超平面S也不盡相同，畢竟感知機(jī)模型的解是一組符合條件的超平面的集合，而不是某一個(gè)最優(yōu)超平面。

3.2 算法的收斂性

一節(jié)純數(shù)學(xué)的東西，用了兩整頁(yè)證明了Novikoff定理，看到這里才知道智商真的是個(gè)硬傷，反復(fù)看了兩遍，又把證明的過(guò)程自己推導(dǎo)了一遍，算是看懂了，如果憑空證明的話(huà)，自己的功力還差得遠(yuǎn)。

Novikoff于1962年證明了感知機(jī)算法的收斂性，作為一個(gè)懶人，由于這一節(jié)涉及大量公式，即使有l(wèi)atex插件也是個(gè)麻煩的工作，具體什么情況我就不談了，同時(shí)，哥倫比亞大學(xué)有這樣的一篇叫《 Convergence Proof for the Perceptron Algorithm 》的筆記，講解了這個(gè)定理的證明過(guò)程，也給了我一個(gè)偷懶的理由 。

3.3 感知機(jī)學(xué)習(xí)算法的對(duì)偶形式

書(shū)上說(shuō)對(duì)偶形式的基本想法是，將w和b表示為實(shí)例和的線(xiàn)性組合形式，通過(guò)求解其系數(shù)而求得w和b。這個(gè)想法及下面的算法描述很容易看懂，只不過(guò)為什么要這么做？將w和b用x和y來(lái)表示有什么好處呢？看起來(lái)也不怎么直觀(guān)，計(jì)算量上似乎并沒(méi)有減少。如果說(shuō)支持向量機(jī)的求最優(yōu)過(guò)程使用對(duì)偶形式是為了方便引入核函數(shù)，那這里的對(duì)偶形式是用來(lái)做什么的呢？暫且認(rèn)為是對(duì)后面支持向量機(jī)的一個(gè)鋪墊吧，或者是求解這種優(yōu)化問(wèn)題的一個(gè)普遍解法。

繼續(xù)正題，為了方便推導(dǎo)，可將初始值和都設(shè)為0，據(jù)上文，我們對(duì)誤分類(lèi)點(diǎn)通過(guò)

來(lái)更新w，b，假設(shè)我們通過(guò)誤分類(lèi)點(diǎn)更新參數(shù)的次數(shù)為次，那么w，b關(guān)于的增量為和，為方便，可將用來(lái)表示，很容易可以得到

????????????????????????????????????????????????????????????????????????????????????????????????????????? （10）

??????????????????????????????????????????????????????????????????????????????????????????????????????????????? （11）

這里i = 1,2,…,N。當(dāng)時(shí)，表示第i個(gè)樣本由于被誤分類(lèi)而進(jìn)行更新的次數(shù)。某樣本更新次數(shù)越多，表示它距離超平面S越近，也就越難正確分類(lèi)。換句話(huà)說(shuō)，這樣的樣本對(duì)學(xué)習(xí)結(jié)果影響最大。

算法2 （感知機(jī)學(xué)習(xí)算法的對(duì)偶形式）

輸入：訓(xùn)練數(shù)據(jù)集，其中，，i = 1,2,…,N；學(xué)習(xí)率

輸出：，b；感知機(jī)模型

其中

（1），

（2）在訓(xùn)練集中選取樣本

（3）如果

（4）轉(zhuǎn)至（2）直到?jīng)]有誤分類(lèi)樣本出現(xiàn)

由于訓(xùn)練實(shí)例僅以?xún)?nèi)積的形式出現(xiàn)，為方便，可預(yù)先將訓(xùn)練集中實(shí)例間的內(nèi)積計(jì)算出來(lái)并以矩陣形式存儲(chǔ)（就是那個(gè)的部分），這就是所謂的Gram矩陣（線(xiàn)性代數(shù)學(xué)的不好的飄過(guò)To T）：

又到例題時(shí)間！再說(shuō)一遍，這本書(shū)最大的好處就是有實(shí)例，凡是只講理論不給例子的行為都是耍流氓！

例2 ?同 例1 ，只不過(guò)是用對(duì)偶形式來(lái)求解。

同樣過(guò)程不再分析，給出我的求解代碼：

          
            package
          
          
             org.juefan.perceptron;

          
          
            import
          
          
             java.util.ArrayList;

          
          
            import
          
          
             org.juefan.basic.FileIO;

          
          
            public
          
          
            class
          
          
             GramPerceptrom {
    
    
          
          
            public
          
          
            static
          
           ArrayList<Integer> a  = 
          
            new
          
           ArrayList<>
          
            ();
    
          
          
            public
          
          
            static
          
          
            int
          
          
             b ;
    
    
          
          
            /*
          
          
            初始化參數(shù)
          
          
            */
          
          
            public
          
           GramPerceptrom(
          
            int
          
          
             num){
        
          
          
            for
          
          (
          
            int
          
           i = 0; i < num; i++
          
            )
            a.add(
          
          0
          
            );
        b 
          
          = 0
          
            ;
    }
    
          
          
            /**
          
          
            Gram矩陣
          
          
            */
          
          
            public
          
          
            static
          
           ArrayList<ArrayList<Integer>> gram = 
          
            new
          
           ArrayList<>
          
            ();
    
          
          
            public
          
          
            void
          
           setGram(ArrayList<Data>
          
             datas){
        
          
          
            for
          
          (
          
            int
          
           i = 0; i < datas.size(); i++
          
            ){
            ArrayList
          
          <Integer> rowGram = 
          
            new
          
           ArrayList<>
          
            ();
            
          
          
            for
          
          (
          
            int
          
           j = 0; j < datas.size(); j++
          
            ){
                rowGram.add(Data.getInner(datas.get(i), datas.get(j)));
            }
            gram.add(rowGram);
        }
    }
    
    
          
          
            /**
          
          
            是否正確分類(lèi)
          
          
            */
          
          
            public
          
          
            static
          
          
            boolean
          
           isCorrect(
          
            int
          
           i, ArrayList<Data>
          
             datas){
        
          
          
            int
          
           value = 0
          
            ;
        
          
          
            for
          
          (
          
            int
          
           j = 0; j < datas.size(); j++
          
            )
            value 
          
          += a.get(j)*datas.get(j).y *
          
             gram.get(j).get(i);
        value 
          
          = datas.get(i).y * (value +
          
             b);
        
          
          
            return
          
           value > 0 ? 
          
            true
          
          : 
          
            false
          
          
            ;
    }
    
    
          
          
            //
          
          
            此算法基于數(shù)據(jù)是線(xiàn)性可分的，如果線(xiàn)性不可分，則會(huì)進(jìn)入死循環(huán)
          
          
            public
          
          
            static
          
          
            boolean
          
           isStop(ArrayList<Data>
          
             datas){
        
          
          
            boolean
          
           isStop = 
          
            true
          
          
            ;
        
          
          
            for
          
          (
          
            int
          
           i = 0; i < datas.size(); i++
          
            ){
            isStop 
          
          = isStop &&
          
             isCorrect(i, datas);
        }
        
          
          
            return
          
          
             isStop;
    }
    
    
          
          
            public
          
          
            static
          
          
            void
          
          
             main(String[] args) {
        ArrayList
          
          <Data> datas = 
          
            new
          
           ArrayList<>
          
            ();
        FileIO fileIO 
          
          = 
          
            new
          
          
             FileIO();
        fileIO.setFileName(
          
          ".//file//perceptron.txt"
          
            );
        fileIO.FileRead();
        
          
          
            for
          
          
            (String data: fileIO.fileList){
            datas.add(
          
          
            new
          
          
             Data(data));
        }
        GramPerceptrom gram  
          
          = 
          
            new
          
          
             GramPerceptrom(datas.size());
        gram.setGram(datas);
        System.out.println(datas.size());
        
          
          
            while
          
          (!
          
            isStop(datas)){
            
          
          
            for
          
          (
          
            int
          
           i = 0; i < datas.size(); i++
          
            )
                
          
          
            if
          
          (!
          
            isCorrect(i, datas)){
                    a.set(i, a.get(i) 
          
          + 1
          
            );
                    b 
          
          +=
          
             datas.get(i).y;
                    System.out.println(a 
          
          + "\t" +
          
             b);
                }
        }
    }
}
          
        

4. 小結(jié)

終于寫(xiě)完一章的內(nèi)容了，用了不少功夫，果然是說(shuō)起來(lái)容易做起來(lái)難呢。不過(guò)通過(guò)這樣記錄的方式（雖然大部分是抄書(shū)），自己對(duì)相關(guān)算法的理論及過(guò)程就又學(xué)了一遍，覺(jué)得這個(gè)時(shí)間還是花的值得的。

本章介紹了統(tǒng)計(jì)學(xué)習(xí)中最簡(jiǎn)單的一種算法——感知機(jī)，對(duì)現(xiàn)在的機(jī)器學(xué)習(xí)理論來(lái)說(shuō)，這個(gè)算法的確是太簡(jiǎn)單了，但這樣簡(jiǎn)單的東西卻是很多現(xiàn)在流行算法的基礎(chǔ)，比如神經(jīng)網(wǎng)絡(luò)，比如支持向量機(jī)，Deep Learning還沒(méi)了解過(guò)，不知道有多大聯(lián)系。當(dāng)然，實(shí)際應(yīng)用價(jià)值不能說(shuō)沒(méi)有，可以用于一些簡(jiǎn)單的線(xiàn)性分類(lèi)的情況，也可以由簡(jiǎn)單的二類(lèi)分類(lèi)擴(kuò)展到多類(lèi)分類(lèi)（詳見(jiàn) 此PPT ），可以用于自然語(yǔ)義處理等領(lǐng)域。

再將思路整理一下，盡量掌握感知機(jī)算法，再好好看看 維基百科鏈接 中的有關(guān)文獻(xiàn)。

?

PS:本文的內(nèi)容轉(zhuǎn)載自?http://www.cnblogs.com/OldPanda/archive/2013/04/12/3017100.html

原博主是Python寫(xiě)的代碼，我這邊改成Java了

對(duì)代碼有興趣的可以上本人的GitHub查看： https://github.com/JueFan/StatisticsLearningMethod/

2014-06-29:倆種算法的代碼都完成了，更新完畢

統(tǒng)計(jì)學(xué)習(xí)方法（二）——感知機(jī)