《淺析感知機(二)--學習演算法及python程式碼剖析》
在該篇文章中淺析感知機(一)——模型與學習策略 - 知乎專欄我已經表達清楚了感知機的模型以及學習策略,明白了感知機的任務是
解決二分類問題
,學習策略是
最佳化損失函式
:
,那麼我們怎麼來進行學習呢?根據書中例子給出
python程式碼實現!
一、學習演算法
當我們已經有了一個目標是最小化損失函式,如下圖:
我們就可以用常用的梯度下降方法來進行更新,對w,b引數分別進行求偏導可得:
那麼我們任意初始化w,b之後,碰到誤分類點時,採取的權值更新為w,b分別為:
好了,當我們碰到誤分類點的時候,我們就採取上面的更新步驟進行更新引數即可!
但李航博士在書中並不是用到所有誤分類點的資料點來進行更新,而是採取隨機梯度下降法(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
copy
trainint_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
]
‘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
res
def
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
:
“在1000次以內全部分對了”
else
:
“很不幸,1000次迭代還是沒有分對”
程式執行結果如下:
實驗證明這與我們書本上的結果是對應的。到這裡已經講完了本次要講的內容,希望對大家理解有幫助~歡迎大家指錯交流!
後續文章預告:
《淺析感知機(三)——收斂性證明與對偶形式》
這裡在安利一下,我是完全按李航博士書籍來學習,歡迎關注交流~哈哈哈哈
參考以下內容:
李航博士《統計學習方法》
林軒田老師《機器學習基石》
袁春老師ppt
致謝:郭江師兄,曉明師兄,德川,皓宇,繼豪,海濤師兄