感知機
- 感知機模型
- 感知機學(xué)習(xí)策略
- 感知機學(xué)習(xí)算法
- 算法的收斂性
- 感知機學(xué)習(xí)算法的對偶形式
感知機實現(xiàn)二分類模型
- 梯度下降法
- scikit-learn 感知機學(xué)習(xí)
感知機(perceptron)是二類分類的線性分類模型,其輸入為實例的特征向量猖任,輸出為實例的類別辕棚,取+1和–1二值整吆。感知機對應(yīng)于輸入空間(特征空間)中將實例劃分為正負兩類的分離超平面,屬于判別模型。感知機學(xué)習(xí)旨在求出將訓(xùn)練數(shù)據(jù)進行線性劃分的分離超平面参咙,為此,導(dǎo)入基于誤分類的損失函數(shù)硫眯,利用梯度下降法對損失函數(shù)進行極小化蕴侧,求得感知機模型。
感知機模型
- 假設(shè)輸入空間(特征空間)是
两入,輸出空間是
净宵,輸入
表示實例的特征向量,對應(yīng)于輸入空間(特征空間) 的點裹纳;輸出
表示實例的類別择葡。由輸入空間到輸出空間的如下函數(shù):
稱為感知機。其中和
稱為感知機模型參數(shù)剃氧。
叫作權(quán)值(weight)或權(quán)值向量(weight vector)敏储,
叫作偏置(bias),
表示
和
的內(nèi)積朋鞍。
是符號函數(shù)已添,即
感知機是一種線性分類模型,屬于判別模型滥酥。
- 感知機有如下幾何解釋:線性方程
更舞,對應(yīng)于特征空間
中的一個超平面
,其中
是超平面的法向量坎吻,
是超平面的截距缆蝉。這個超平面將特征空間劃分為兩個部分。位于兩部分的點(特征向量)分別被分為正禾怠、負兩類返奉。因此,超平面
稱為分離超平面(separating hyperplane)吗氏。
感知機學(xué)習(xí)策略
- 給定數(shù)據(jù)集
芽偏,其中,
弦讽,
污尉,
膀哲,如果存在某個超平面
能夠?qū)?shù)據(jù)集的正實例點和負實例點完全正確地劃分到超平面的兩側(cè),即對所有的實例
被碗,有
某宪,對所有
的實例
,有
锐朴,則稱數(shù)據(jù)集
為線性可分數(shù)據(jù)集(linearly separable data set)兴喂;否則,稱數(shù)據(jù)集
線性不可分焚志。
- 損失函數(shù)的一個自然選擇是誤分類點的總數(shù)衣迷。但是,這樣的損失函數(shù)不是參數(shù)
的連續(xù)可導(dǎo)函數(shù)酱酬,不易優(yōu)化壶谒。
- 損失函數(shù)的另一個選擇是誤分類點到超平面
的總距離,這是感知機所采用的膳沽。為此汗菜,首先寫出輸入空間
中任一點
到超平面
的距離:
其次,對于誤分類的數(shù)據(jù)來說挑社,
成立陨界,因為當
時,
痛阻,當
時普碎,
。因此录平,誤分類點
到超平面
的距離是:
這樣,假設(shè)超平面的誤分類點集合為
缀皱,那么所有誤分類點到超平面
的總距離為:
不考慮斗这,就得到感知機學(xué)習(xí)的損失函數(shù)。這個損失函數(shù)就是感知機學(xué)習(xí)的經(jīng)驗風(fēng)險函數(shù)啤斗。
- 證明空間
中任一點
到超平面
的距離:
設(shè)點到超平面
的距離為
表箭,點
在超平面
的投影為
,則
由于向量與
平面的法向量
平行钮莲, 所以
又
所以
即
感知機學(xué)習(xí)算法
- 給定數(shù)據(jù)集
免钻,其中,
崔拥,
极舔,
,求參數(shù)
链瓦,使其為以下?lián)p失函數(shù)極小化問題的解:
其中為誤分類點的集合拆魏。
- 感知機學(xué)習(xí)算法是誤分類驅(qū)動的盯桦,具體采用隨機梯度下降法(stochastic gradient descent)。假設(shè)誤分類點集合
是固定的渤刃,那么損失函數(shù)
的梯度由
給出拥峦。隨機選取一個誤分類點, 對
進行更新:
式中是步長卖子,在統(tǒng)計學(xué)習(xí)中又稱為學(xué)習(xí)率(learning rate)略号。這樣,通過迭代可以期待損失函數(shù)
不斷減小洋闽,直到為0玄柠。
- 感知機模型
1>> 選取初值
2>> 在訓(xùn)練集中選取數(shù)據(jù)
3>> 如果,則
喊递,
4>> 轉(zhuǎn)至 2>>随闪,直至訓(xùn)練集中沒有誤分點。
算法的收斂性
為了方便推導(dǎo)骚勘,將偏置 并入權(quán)重向量
铐伴,記作
,同樣也將輸入向量加以擴充俏讹,記作
当宴。這樣,
泽疆,
户矢。顯然,
殉疼。
- 設(shè)數(shù)據(jù)集
是線性可分的梯浪,其中,
瓢娜,
挂洛,
,則
<1>
存在滿足條件的超平面
將訓(xùn)練數(shù)據(jù)集完全正確分開眠砾;且存在
虏劲,對所有
,有
褒颈。
<2>
令柒巫,則感知機
在訓(xùn)練數(shù)據(jù)集上的誤分類次數(shù)
滿足不等式
。
-
證明
<1>
:由于訓(xùn)練數(shù)據(jù)集是線性可分的谷丸,存在超平面可將訓(xùn)練數(shù)據(jù)集完全正確分開堡掏,取此超平面為,使
刨疼。由于對有限的
布疼,均有
所以存在
使
-
證明
<2>
:感知機算法從開始摊趾,如果實例被誤分類,則更新權(quán)重游两。令
是第
個誤分類實例之前的擴充權(quán)重向量砾层,即
則第個誤分類實例的條件是
若是被
誤分類的數(shù)據(jù), 則
和
的更新是
即
下面推導(dǎo)兩個不等式
1>>
2>>
結(jié)合以上兩個不等式得
- 上述證明表明贱案,誤分類的次數(shù)
是有上界的肛炮,經(jīng)過有限次搜索可以找到將訓(xùn)練數(shù)據(jù)完全正確分開的分離超平面。也就是說宝踪,當訓(xùn)練數(shù)據(jù)集線性可分時侨糟,感知機學(xué)習(xí)算法原始形式迭代是收斂的。
感知機學(xué)習(xí)算法的對偶形式
- 對偶形式的基本想法是瘩燥,將
和
表示為實例
和標記
的線性組合的形式秕重,通過求解其系數(shù)而求得
和
。
- 設(shè)
均為 0厉膀,對誤分類點
, 通過
逐步修改溶耘,設(shè)修改
次,則
關(guān)于
的增量分別是
和
服鹅,這里的
凳兵,最后學(xué)習(xí)到的
可以分別表示為
這里,企软,
庐扫,當
時,表示第i個實例點由于誤分而進行更新的次數(shù)仗哨,即
形庭。實例點更新次數(shù)越多,意味著它距離分離超平面越近厌漂,也就越難正確分類碘勉。換句話說,這樣的實例對學(xué)習(xí)結(jié)果影響最大桩卵。
- 感知機模型
,其中
倍宾。
1>> 選取初值
2>> 在訓(xùn)練集中選取數(shù)據(jù)
3>> 如果雏节,則
,
4>> 轉(zhuǎn)至 2>>高职,直至訓(xùn)練集中沒有誤分點钩乍。
- 對偶形式中訓(xùn)練實例僅以內(nèi)積的形式出現(xiàn)。為了方便怔锌,可以預(yù)先將訓(xùn)練集中實例間的內(nèi)積計算出來并以矩陣的形式存儲寥粹,這個矩陣就是所謂的Gram矩陣(Gram matrix)
例如变过,那么其Gram矩陣為
感知機實現(xiàn)二分類模型
梯度下降法
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
class Perceptron(object):
def __init__(self, s):
# s: 權(quán)重參數(shù)個數(shù)
# omega: 權(quán)重參數(shù)
# b: 斜率
# eta: 學(xué)習(xí)率
self.omega = np.ones(s, dtype=np.float32)
self.b = 0
self.eta = 0.1
# 符號函數(shù)
def sign(self, x, omega, b):
return np.dot(x, omega) + b
# 擬合函數(shù),梯度下降
def fit(self, x_train, y_train):
while True:
errors = 0
for index in range(len(x_train)):
_x = x_train[index]
_y = y_train[index]
if _y * self.sign(_x, self.omega, self.b) <= 0:
self.omega = self.omega + self.eta * np.dot(_y, _x)
self.b = self.b + self.eta * _y
errors += 1
if errors == 0:
break
if __name__ == '__main__':
# 獲取鳶尾花數(shù)據(jù)集
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target
df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
# 生成訓(xùn)練樣本涝涤,只取 sepal length媚狰,sepal width 作為樣本特征
train = np.array(df.iloc[:100, [0, 1, -1]])
x_train, y_train = train[:, :-1], train[:, -1]
y_train = np.array([1 if i==1 else -1 for i in y_train])
# 初始化感知機模型
pmodel = Perceptron(len(train[0])-1)
# 擬合訓(xùn)練
pmodel.fit(x_train, y_train)
print('omage: ', pmodel.omega)
print('b: ', pmodel.b)
# 繪制擬合函數(shù)
length_points = np.linspace(4, 7, 10)
width_points = -(pmodel.omega[0] * length_points + pmodel.b)/pmodel.omega[1]
plt.plot(length_points, width_points, label='fitting')
plt.plot(train[:50, 0], train[:50, 1], 'bo', color='blue', label='0')
plt.plot(train[50:100, 0], train[50:100, 1], 'bo', color='orange', label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
運行結(jié)果:scikit-learn 感知機學(xué)習(xí)
import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
from sklearn.linear_model import Perceptron
def fit(x_train, y_train):
# fit_intercept 訓(xùn)練模型是否需要截距項
pmodel = Perceptron(fit_intercept=True, max_iter=1000, shuffle=False, eta0=0.01)
pmodel.fit(x_train, y_train)
return pmodel
if __name__ == '__main__':
# 獲取鳶尾花數(shù)據(jù)集
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target
df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
# 生成訓(xùn)練樣本,只取 sepal length阔拳,sepal width 作為樣本特征
train = np.array(df.iloc[:100, [0, 1, -1]])
x_train, y_train = train[:, :-1], train[:, -1]
y_train = np.array([1 if i==1 else -1 for i in y_train])
# 使用 sklearn 感知機模型擬合訓(xùn)練
pmodel = fit(x_train, y_train)
print('omage: ', pmodel.coef_)
print('b: ', pmodel.intercept_)
# 繪制擬合函數(shù)
length_points = np.linspace(4, 7, 10)
width_points = -(pmodel.coef_[0][0] * length_points + pmodel.intercept_)/pmodel.coef_[0][1]
plt.plot(length_points, width_points, label='fitting')
plt.plot(train[:50, 0], train[:50, 1], 'bo', color='blue', label='0')
plt.plot(train[50:100, 0], train[50:100, 1], 'bo', color='orange', label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
運行結(jié)果: