一唇礁、感知機的定義
感知機是1957年由Rosenblatt提出勾栗，是神經(jīng)網(wǎng)絡(luò)與支持向量機的基礎(chǔ)，是二分類線性分類模型盏筐，輸入為實例的特征围俘，輸出為實例類別，實例類別取+1和-1琢融。感知機是屬于判別模型界牡，因為其求出分離超平面直接將輸入實例劃分為正例和負例。
導(dǎo)入基于誤分類的損失函數(shù)漾抬，利用梯度下降法對損失函數(shù)進行極小化宿亡，求得感知機模型
二、感知機的數(shù)學(xué)表達式
感知機的數(shù)學(xué)表達式可以由下列式子進行表達：
f=sign(w?x+b)
其中纳令，sign(x) 是一個記號函數(shù)她混，表示
當(dāng)x>=0,sign(x)=+1 烈钞；
當(dāng)x<0,sign(x)=?1 ；
三坤按、感知機的幾何意義
幾何意義是將幾何坐標(biāo)系上的點通過分離超平面將其劃分為兩個類別：正例和負例毯欣。【對于二維坐標(biāo)系來說】
如果是多維坐標(biāo)系臭脓，相當(dāng)于是一個多維面了酗钞。比如，二維空間是一條線来累，三維空間是一個面等等砚作。
四、感知機的目標(biāo)函數(shù)
數(shù)據(jù)集線性可分性
感知機的目標(biāo)：在訓(xùn)練數(shù)據(jù)集線性可分的假設(shè)前提下嘹锁，求得一個能夠?qū)⒂?xùn)練集中的正負樣本實例點完全正確分開的分離超平面葫录。
看到這，有人說领猾，訓(xùn)練數(shù)據(jù)集線性可分啥意思啊米同，聽不懂啊，其實就是針對
所有正實例y=+1摔竿，w?x+b>0 面粮；
所有負實例y=?1，w?x+b<0 继低；
一張圖表示其實就是這個樣子的：
這個數(shù)據(jù)集就是可分的熬苍，中間一條虛線即為超平面，將整個數(shù)據(jù)集分為虛線右上和左下部分袁翁。
目標(biāo)函數(shù)推導(dǎo)
通常意義上來說柴底，損失函數(shù)我們可以看誤分類點的總數(shù)。但是這樣來看粱胜，這樣的損失函數(shù)不是參數(shù)w和b的連續(xù)可導(dǎo)函數(shù)似枕，不易優(yōu)化。
因此年柠，感知機選擇另一種形式的損失函數(shù)：
誤分類點到超平面S的總距離。
而平面上一點(x0,y0) 到超平面S 的距離distance0為：
其中褪迟， ||w||是w的L2范數(shù)冗恨。
對于誤分類點有兩種情況：
五、感知機的優(yōu)化方法
目前味赃，感知機的優(yōu)化方法采用的是梯度下降的方法掀抹，也就是我們所熟知的隨機梯度下降或者批量梯度下降。因為感知機有原始形式和對偶形式兩種方式心俗，故而分開來說傲武。
1蓉驹、 原始形式
隨機梯度下降
批量梯度下降
為什么用隨機梯度下降而不用批量梯度下降
這一點在李航大大的書上并沒有提及，只是根據(jù)筆者自己理解來說明原因揪利。
主要是從時間復(fù)雜方向來考慮态兴。
假設(shè)我們有m個樣本【準確來說，這里說m個誤分類樣本更為合適疟位，但是對于我們來說瞻润，我們需要對所有樣本進行判斷，如果誤分類甜刻，更新w和b绍撞。如果不是誤分類，那么不更新得院。其實傻铣，判斷誤分類樣本的過程也相當(dāng)于遍歷整個樣本】，每個樣本有n維特征向量祥绞，我們來分別計算在該場景下的時間復(fù)雜度非洲。
我們寫一下偽代碼：for i in range(0, m+1): if y[i] * (w*x[i]+b) < 0: 更新w, b else: w, b不更新這里時間復(fù)雜度相當(dāng)于是
樣本數(shù)*更新w,b的時間復(fù)雜度。
因此就谜，
對于隨機梯度下降來說怪蔑，每次隨機選取一個誤分類樣本進行更新，樣本數(shù)為1丧荐，其計算的時間復(fù)雜度為O(n)缆瓣，
而對于批量梯度下降來說，每次需要對所有誤分類點進行求和更新虹统，每一個樣本更新w,b的時間復(fù)雜度為O(n) 弓坞，那么對于m 個樣本來說，時間復(fù)雜度為O(m?n)车荔。
我們分3種情況分別討論不同情況下的時間復(fù)雜度情況：
1）當(dāng)樣本量特別少的時候渡冻，即n>>m 時，其實兩者時間復(fù)雜度應(yīng)該差不多忧便。如果更在意精度的話族吻，建議選擇批量梯度下降，因為其更新信息是利用全局誤分類點信息珠增，精度相對于隨機梯度下降更高一些超歌，更新方向更接近全局解。
2）當(dāng)樣本量特別特別大的時候蒂教，即m>>n 巍举，此時批量梯度下降的更新時間的劣勢凸顯更為明顯一些，時間復(fù)雜度陡增凝垛。在可以適當(dāng)舍棄精度的同時懊悯，建議選擇隨機梯度下降蜓谋。
3）當(dāng)樣本量與特征維度近似時，這個時候批量梯度下降的時間復(fù)雜度約為隨機梯度下降的一倍炭分。需要進行準確性和性能兩個方面的綜合考量桃焕。
綜上所述，整體上來說欠窒，從工程和性能兩個方面考慮來說覆旭，可以以犧牲較小的準確性為代價，選擇隨機梯度下降岖妄。
2型将、對偶形式
我們回顧下w,b 的更新方式【這里只看隨機梯度下降方式】：
這里是每次通過修改誤分類點來更新下w,b，這里可以這么來考慮荐虐，我們通過修改次數(shù)來表達w,b的更新七兜。
為什么要轉(zhuǎn)化成對偶形式
這個建議先看完對偶形式的這個小節(jié)再回頭來看原因，當(dāng)然福扬，如果對原始形式和對偶形式都非常熟悉的話腕铸，也可以直接看。
既然有了原始形式铛碑，而且用隨機梯度下降也能達到較好的效果狠裹，那么為什么還要考慮對偶形式，對偶形式的優(yōu)勢具體體現(xiàn)在什么地方呢汽烦？
我們對比下原始形式和對偶形式的w,b 更新形式：
原始形式：
image.png
六涛菠、【代碼】
適用問題：二類分類
實驗數(shù)據(jù)：
由于是二分類器，所以將MINST數(shù)據(jù)集train.csv的label列進行了一些微調(diào)撇吞，label等于0的繼續(xù)等于0俗冻，label大于0改為1。這樣就將十分類的數(shù)據(jù)改為二分類的數(shù)據(jù)牍颈。獲取地址train_binary.csv
實現(xiàn)代碼：
# encoding=utf-8
import pandas as pd
import random
import time
from sklearn.cross_validation import train_test_split
from sklearn.metrics import accuracy_score
class Perceptron(object):
def __init__(self):
self.learning_step = 0.001 # 學(xué)習(xí)率
self.max_iteration = 5000 # 分類正確上界迄薄，當(dāng)分類正確的次數(shù)超過上界時，認為已訓(xùn)練好煮岁，退出訓(xùn)練
def train(self, features, labels):
# 初始化w,b為0,b在最后一位
self.w = [0.0] * (len(features[0]) + 1)
correct_count = 0 # 分類正確的次數(shù)
while correct_count < self.max_iteration:
# 隨機選取數(shù)據(jù)(xi,yi)
index = random.randint(0, len(labels) - 1)
x = list(features[index])
x.append(1.0) # 加上1是為了與b相乘
y = 2 * labels[index] - 1 # label為1轉(zhuǎn)化為正實例點+1讥蔽，label為0轉(zhuǎn)化為負實例點-1
# 計算w*xi+b
wx = sum([self.w[j] * x[j] for j in range(len(self.w))])
# 如果yi(w*xi+b) > 0 則分類正確的次數(shù)加1
if wx * y > 0:
correct_count += 1
continue
# 如果yi(w*xi+b) <= 0 則更新w(最后一位實際上b)的值
for i in range(len(self.w)):
self.w[i] += self.learning_step * (y * x[i])
def predict_(self, x):
wx = sum([self.w[j] * x[j] for j in range(len(self.w))])
return int(wx > 0) # w*xi+b>0則返回返回1,否則返回0
def predict(self, features):
labels = []
for feature in features:
x = list(feature)
x.append(1)
labels.append(self.predict_(x))
return labels
if __name__ == '__main__':
print("Start read data")
time_1 = time.time()
raw_data = pd.read_csv('../data/train_binary.csv', header=0) # 讀取csv數(shù)據(jù)，并將第一行視為表頭画机，返回DataFrame類型
data = raw_data.values
features = data[::, 1::]
labels = data[::, 0]
# 避免過擬合冶伞，采用交叉驗證，隨機選取33%數(shù)據(jù)作為測試集色罚，剩余為訓(xùn)練集
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
time_2 = time.time()
print('read data cost %f seconds' % (time_2 - time_1))
print('Start training')
p = Perceptron()
p.train(train_features, train_labels)
time_3 = time.time()
print('training cost %f seconds' % (time_3 - time_2))
print('Start predicting')
test_predict = p.predict(test_features)
time_4 = time.time()
print('predicting cost %f seconds' % (time_4 - time_3))
score = accuracy_score(test_labels, test_predict)
print("The accruacy score is %f" % score)
實現(xiàn)代碼(用sklearn實現(xiàn))：
# encoding=utf-8
import pandas as pd
import time
from sklearn.cross_validation import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.linear_model import Perceptron
if __name__ == '__main__':
print("Start read data...")
time_1 = time.time()
raw_data = pd.read_csv('../data/train_binary.csv', header=0) # 讀取csv數(shù)據(jù)，并將第一行視為表頭账劲，返回DataFrame類型
data = raw_data.values
features = data[::, 1::]
labels = data[::, 0]
# 隨機選取33%數(shù)據(jù)作為測試集戳护，剩余為訓(xùn)練集
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
time_2 = time.time()
print('read data cost %f seconds' % (time_2 - time_1))
print('Start training...')
clf = Perceptron(alpha=0.0001,max_iter=2000) # 設(shè)置步長及最大迭代次數(shù)
clf.fit(train_features,train_labels)
time_3 = time.time()
print('training cost %f seconds' % (time_3 - time_2))
print('Start predicting...')
test_predict = clf.predict(test_features)
time_4 = time.time()
print('predicting cost %f seconds' % (time_4 - time_3))
score = accuracy_score(test_labels, test_predict)
print("The accruacy score is %f" % score)
【總結(jié)】
感知器模型
適用問題：二類分類
模型特點：分離超平面
模型類型：判別模型
感知機學(xué)習(xí)策略
學(xué)習(xí)策略：極小化誤分點到超平面距離
學(xué)習(xí)的損失函數(shù)：誤分點超平面距離
感知機學(xué)習(xí)算法
學(xué)習(xí)算法：隨機梯度下降
算法的收斂性
證明：Novikoff定理
算法的對偶形式
為了求解更簡單金抡，所以用對偶形式
注：統(tǒng)計學(xué)習(xí)方法——修煉學(xué)習(xí)筆記系列參考學(xué)習(xí)資料：
《統(tǒng)計學(xué)習(xí)方法》第2版 李航
補充學(xué)習(xí)資料：
http://www.reibang.com/p/db7f5e841a56 李威威學(xué)習(xí)筆記
https://blog.csdn.net/weixin_43374508/article/details/102784079 城序猿
https://blog.csdn.net/qfire/article/details/77905787
代碼學(xué)習(xí)資料：https://github.com/WenDesi/lihang_book_algorithm
