《淺析感知機(二)--學習演算法及python代碼剖析》

在該篇文章中淺析感知機(一)--模型與學習策略 - 知乎專欄我已經表達清楚了感知機的模型以及學習策略,明白了感知機的任務是解決二分類問題,學習策略是優化損失函數L=-sum_{x_{i}in M }^{}{y_{i} (w*x_{i} +b)} ,那麼我們怎麼來進行學習呢?根據書中例子給出python代碼實現!

學習演算法

當我們已經有了一個目標是最小化損失函數,如下圖:

我們就可以用常用的梯度下降方法來進行更新,對w,b參數分別進行求偏導可得:

那麼我們任意初始化w,b之後,碰到誤分類點時,採取的權值更新為w,b分別為:w=w+sum_{x_{i}in M }^{}{y_{i} x_{i} }

b=b+sum_{x_{i}in M }^{}{y_{i}  }

好了,當我們碰到誤分類點的時候,我們就採取上面的更新步驟進行更新參數即可!但李航博士在書中並不是用到所有誤分類點的數據點來進行更新,而是採取隨機梯度下降法(stochastic gradient descent)。步驟如下,首先,任取一個超平面w0,b0,然後用梯度下降法不斷地極小化目標函數,極小化過程中不是一次是M中所有誤分類點的梯度下降而是一次隨機選取一個誤分類點使其梯度下降(有證明可以證明隨機梯度下降可以收斂,並更新速度快於批量梯度下降,在這裡不是我們考慮的重點,我們默認為它能收斂到最優點即可,後面我會寫一篇文章說明一下隨機梯度下降與批梯度下降區別與代碼實現

那麼碰到誤分類點的時候,採取的權值更新w,b分別為:

好了,到這裡我們可以給出整個感知機學習過程演算法!如下:

(1)選定初值w0,b0,(相當於初始給了一個超平面

(2)在訓練集中選取數據(xi,yi)(任意抽取數據點

(3)如果yi(w*xi+b)<0(說明是誤分類點,就需要更新參數)

那麼進行參數更新!更新方式如下:

這種更新方式,我們也有直觀上的感覺,可以可視化理解一下,如下圖:

當我們數據點應該分類為y=+1的時候,我們分錯了,分成-1(說明w*x<0,代表w與x向量夾角大於90度),這個時候應該調整,更新過程為w=w+1*x,往x向量方向更接近了!

第二種更新過程如下圖:

當我們數據點應該分類為y=-1的時候,我們分錯了,分成+1(說明w*x>0,代表w與x向量夾角小於90度),這個時候應該調整,更新過程為w=w-1*x,往x向量方向更接近了!

(4)轉到(2),直到訓練集中沒有誤分類點(能夠證明在有限次更新後,收斂,下篇文章會講到!)

到這裡為止,其實感知機演算法理論部分已經全部講完了,下面我給出演算法python代碼實現以及詳細的代碼注釋!

代碼講解

書上例子講解:

根據上述例子和演算法講解,我實現了python代碼如下,其中過程用詳細注釋解釋了!

核心演算法流程圖如下:

# -*- coding: utf-8 -*-import copytrainint_set = [[(3,3),1],[(4,3),1],[(1,1),-1]] #輸入數據w = [0,0] #初始化w參數b = 0 #初始化b參數def update(item): global w,b w[0] += 1*item[1]*item[0][0] #w的第一個分量更新 w[1] += 1*item[1]*item[0][1] #w的第二個分量更新 b += 1*item[1] print "w = ",w,"b=",b #列印出結果def judge(item): #返回y = yi(w*x+b)的結果 res = 0 for i in range(len(item[0])): res +=item[0][i]*w[i] #對應公式w*x res += b #對應公式w*x+b res *= item[1] #對應公式yi(w*x+b) return resdef check(): #檢查所有數據點是否分對了 flag = False for item in trainint_set: if judge(item)<=0: #如果還有誤分類點,那麼就小於等於0 flag = True update(item) #只要有一個點分錯,我就更新 return flag #flag為False,說明沒有分錯的了if __name__ == "__main__": flag = False for i in range(1000): if not check(): #如果已經沒有分錯的話 flag = True break if flag: print "在1000次以內全部分對了" else: print "很不幸,1000次迭代還是沒有分對"

程序運行結果如下:

實驗證明這與我們書本上的結果是對應的。到這裡已經講完了本次要講的內容,希望對大家理解有幫助~歡迎大家指錯交流!

後續文章預告:

《淺析感知機(三)--收斂性證明與對偶形式》

這裡在安利一下,我是完全按李航博士書籍來學習,歡迎關注交流~哈哈哈哈

參考以下內容:

李航博士《統計學習方法》

林軒田老師《機器學習基石》

袁春老師ppt

致謝:郭江師兄,曉明師兄,德川,皓宇,繼豪,海濤師兄


推薦閱讀:

歷史|文章筆記-從線性分類器到卷積神經網路
Learn R | AdaBoost of Data Mining(一)
李宏毅機器學習2016 第十九講 結構化學習簡介
一位老師,一位領導,一個讓全體學生考上目標學校的故事

TAG:机器学习 | 深度学习DeepLearning | 统计学习方法 |