【统计学习方法】第二章 感知机
感知机模型定位：感知机属于 二分类模型/线性模型/非概率模型/判别模型
回顾：统计学习三要素：模型+策略+算法
算法原理
模型
- 输入空间/特征空间： X ⊆ R n X subseteq R^n X⊆Rn
- 输出空间： y ∈ y in y∈ {-1,+1}
- 输入到输出的映射： y = s g n ( w x + b ) y=sgn(wx+b) y=sgn(wx+b) 【sgn为符号函数】
- 假设空间：{f|f(x)=wx+b}
几何解释：wx+b=0是特征空间中的一个超平面S，w是该平面的法向量，b是截距；
前提假设：当数据集线性可分时，感知机才具有可用性；
策略
感知机的损失函数为误分类的点x到超平面S的距离： 1 ∣ ∣ w ∣ ∣ ∣ w x + b ∣ frac{1}{||w||}|wx+b| ∣∣w∣∣1∣wx+b∣ （点到平面的距离公式），但这种含有绝对值的形式并不利于求导，因此，需要想办法去掉绝对值；
对于误分类的点 x i x_i xi而言，满足以下式子： − y i ( w ⋅ x i + b ) > 0 -y_i(w·x_i+b)>0 −yi(w⋅xi+b)>0，于是，感知机的损失函数为： − 1 ∣ ∣ w ∣ ∣ y i ( w x i + b ) -frac{1}{||w||}y_i(wx_i+b) −∣∣w∣∣1yi(wxi+b)；
不考虑||w||，于是，就得到了感知机的风险/目标函数： L ( w , b ) = − ∑ i y i ( w x i + b ) L(w,b)=-sum_i y_i(wx_i+b) L(w,b)=−∑iyi(wxi+b)，注意，这里的风险函数并没有像均方误差那样取平均【模型的目标函数是需要根据模型的特点设定的】
算法
感知机采用随机梯度下降算法进行最优解的求解；
原始形式
对L(w,b)求偏导，得到梯度：
∇
w
L
(
w
,
b
)
=
−
∑
i
y
i
x
i
nabla_wL(w,b)=-sum_i y_ix_i
∇wL(w,b)=−∑iyixi
∇
b
L
(
w
,
b
)
=
−
∑
i
y
i
nabla_bL(w,b)=-sum_i y_i
∇bL(w,b)=−∑iyi
于是，随机选取一个误分类点xi，w和b的更新如下：【
η
eta
η为学习率】
w
=
w
+
η
y
i
x
i
w=w+eta y_ix_i
w=w+ηyixi
b
=
b
+
η
y
i
b=b+eta y_i
b=b+ηyi
对偶形式【值得仔细理解】
考虑感知机的参数更新过程，假设共进行了k次更新， k = ∑ i k i k=sum_ik_i k=∑iki，其中， k i k_i ki为第i个点的更新次数，那么最后得到的w其实等于 w = ∑ i = 1 m α i k i y i x i w=sum_{i=1}^malpha_i^{k_i}y_ix_i w=∑i=1mαikiyixi，其中， α k i alpha^{k_i} αki 为对第i个样本点的 k i k_i ki次更新之后的参数；
直观理解就是，对每个样本点的更新体现在 α k i alpha^{k_i} αki上，而所有更新之后的样本点之和就是w。
所以，感知机模型可定义为 y = s g n ( ∑ i = 1 m α i y i x i ⋅ x + b ) y=sgn(sum_{i=1}^malpha_iy_ix_i·x+b) y=sgn(∑i=1mαiyixi⋅x+b)，这里 α i alpha_i αi表示模型训练后得到的最优参数
因此，我们可以将对w的更新转换为对 α alpha α的更新，且对误分类点xi而言，参数更新公式为 α i = α i + η alpha_i=alpha_i+eta αi=αi+η
注意：
- 这里的 α alpha α是m维向量，m为输入样本的个数，也就是，对每个样本，都会有一个相应的参数！
- 直观理解参数 α alpha α的更新：若第i个样本被误分类 n i n_i ni次，则 α i alpha_i αi就被更新 n i n_i ni次，每次更新，都增加 η eta η，最后，第i个样本对参数的贡献为 w i = α i x i y i w_i=alpha_ix_iy_i wi=αixiyi，将所有样本的参数贡献求和，就得到了最后的w；
- 对偶形式的好处：每次进行参数更新时，无需将样本点纳入计算；
算法收敛性——Novikoff定理
暂略
Python实现
原始形式
相关说明：
- 输入X：m*n的矩阵，m为样本个数，n为特征个数
- 输出y：m*1的向量
- 参数w：n*1的向量
- 偏置b：实数
特别注意：
- 矩阵运算的实现：谁乘以谁，点乘还是矩阵乘
- 虽然说每次的参数更新是随机选取一个误分类点进行更新，但实际实现过程中，在一轮训练里，一次性更新所有被误分类的点；
'''
Author : Superpig99
Date : 2021/12/05
'''
import numpy as np
class perceptron:
def __init__(self,learning_rate,max_epoch):
self.lr = learning_rate # 学习率
self.me = max_epoch # 最大的训练次数
# 给定X，预测y
def predict(self,X):
y = X @ self.w + self.b # @：矩阵乘法，维数：(m*n) * (n*1) = m*1
y = np.where(y>=0,1,-1) # 符号函数
return y
def fit(self,X,y): # X是m*n的矩阵，y为m*1的向量，m为样本个数，n为特征个数
m,n = X.shape[0],X.shape[1]
# 初始化
self.w = np.zeros((n,1)) # 参数w是n*1的向量
self.b = np.zeros(1)
for i in range(self.me): # 开始训练
yhat = self.predict(X)
wrong_index = np.where((y - yhat)!=0,1,0) # 指示矩阵，指示哪些地方预测错了
self.w = self.w + (self.lr*(wrong_index*y).T @ X).T # 修正w，w = w + lr * y * X，这一步很重要！值得理解
self.b = self.b + self.lr * wrong_index.T @ y # 修正b，b = b + lr * y
# print('epoch:',i)
# print(self.w.T,'n',wrong_index.T)
print('Epoch: %d, Wrong points: %d, Error Rate: %.2f'%(i,np.sum(wrong_index),np.sum(wrong_index)/m))
if np.sum(wrong_index)==0: # 如果全部预测正确，则训练结束
break
return
def evaluation(self,Yhat,Ytrue):
if Yhat.shape == Ytrue.shape:
acu = np.sum(np.where((Yhat - Ytrue)==0,1,0))/Ytrue.shape[0]
return acu
else:
print('the shape of Yhat and Ytrue is different')
if __name__=='__main__':
X = np.array([[3,3],[4,3],[1,1]])
y = np.array([[1],[1],[-1]])
per = perceptron(learning_rate=1,max_epoch=20)
per.fit(X,y)
yhat = per.predict(X)
acu = per.evaluation(yhat,y)
print('Accuarcy is %.2f'%acu)
重点说明：
-
self.w = self.w + (self.lr*(wrong_index*y).T @ X).T该步骤含义：-
wrong_index * y：wrong_index和y的点积（元素积），得到的是m*1的向量，含义为那些被错误分类的点的y值向量； -
(wrong_index*y).T @ X)：y与X的内积，得到的是1*n的向量，含义为该轮训练中，所有被误分类的点的内积之和； -
(self.lr*(wrong_index*y).T @ X).T：乘以学习率后转置，就是该轮训练中，w需要更新的增量；
-
-
self.b = self.b + self.lr * wrong_index.T @ y：类推w的更新，很好理解；
对偶形式
相关说明：
- 输入X：m*n的矩阵，m为样本个数，n为特征个数
- 输出y：m*1的向量
- 参数a：m*1的向量，即 α alpha α
- 偏置b：实数
'''
Author : Superpig99
Date : 2021/12/05
'''
import numpy as np
class DaulPerceptron:
def __init__(self,learning_rate,max_epoch):
self.lr = learning_rate # 学习率
self.me = max_epoch # 最大的训练次数
# 给定X，预测y
def predict(self,X):
m = X.shape[0]
y = self.Gram @ self.c + self.b # 重点！
y = np.where(y>=0,1,-1)
return y
def fit(self,X,y): # X是m*n的矩阵，y为m*1的向量，m为样本个数，n为特征个数
m,n = X.shape[0],X.shape[1]
self.a = np.zeros((m,1)) # 参数a是m*1的向量
self.b = np.zeros(1)
self.Gram = [[0]*m for _ in range(m)] # 计算好Gram矩阵，以便以后使用
for i in range(m):
self.Gram[i][i] = X[i] @ X[i].T
for j in range(i+1,m):
self.Gram[i][j] = X[i] @ X[j].T
self.Gram[j][i] = X[i] @ X[j].T
for i in range(self.me): # 开始训练
self.c = self.a * y # 这个self.c也很重要
yhat = self.predict(X)
wrong_index = np.where((y - yhat)!=0,1,0) # 指示矩阵，指示哪些地方预测错了
self.a = self.a + self.lr*wrong_index # 修正a，a = a + lr
self.b = self.b + self.lr*np.sum(wrong_index*y) # 修正b，b = b + lr * y
# print('epoch:',i)
# print(self.a.T,'n',wrong_index.T)
print('Epoch: %d, Wrong points: %d, Error Rate: %.2f'%(i,np.sum(wrong_index),np.sum(wrong_index)/m))
if np.sum(wrong_index)==0: # 如果全部预测正确，则训练结束
break
return
def evaluation(self,Yhat,Ytrue):
if Yhat.shape == Ytrue.shape:
acu = np.sum(np.where((Yhat - Ytrue)==0,1,0))/Ytrue.shape[0]
return acu
else:
print('the shape of Yhat and Ytrue is different')
if __name__=='__main__':
X = np.array([[3,3],[4,3],[1,1]])
y = np.array([[1],[1],[-1]])
per = DaulPerceptron(learning_rate=1,max_epoch=20)
per.fit(X,y)
yhat = per.predict(X)
acu = per.evaluation(yhat,y)
print('Accuarcy is %.2f'%acu)
重点说明：
之前提到说，对偶形式的感知机可以写成
y
=
s
g
n
(
∑
i
=
1
m
α
i
y
i
x
i
⋅
x
+
b
)
y=sgn(sum_{i=1}^malpha_iy_ix_i·x+b)
y=sgn(∑i=1mαiyixi⋅x+b)，把式子拆看来看，这个表达式其实包含了一个Gram矩阵，元素为(xi,xj)【第i个特征向量与第j个特征向量的内积】，所以在预测的时候，计算表达式其实为y = self.Gram @ self.c + self.b，其中，self.c = self.a * y，self.c需要随着self.a的更新而更新，这一步理解好，剩下的就都不是问题了。
总结
算法看起来很简单，但实现起来会发现有很多知识点会理解出错，比如：
- 对偶形式中的参数alpha，并不是想当然的n*1的向量，而是和样本数对应的；
- Gram矩阵是怎么来的，为什么会想到用Gram矩阵来运算，也很巧妙；
在参数更新这里，虽然表达上是说，随机选取一个样本点进行更新，但实际操作是每轮训练，对所有误分类点都进行的方法【我有看到利用for循环对所有误分类点进行更新的做法，但矩阵运算其实会更快】
疑问：
《统计学习方法》教材说满足
y
i
(
w
x
i
+
b
)
≤
0
y_i(wx_i+b)leq0
yi(wxi+b)≤0的点都是误分类点，教材中举的例子也是按照
y
i
(
w
x
i
+
b
)
≤
0
y_i(wx_i+b)leq0
yi(wxi+b)≤0这个标准来判断误分类点的，但我在代码的过程是按照预测值是否等于实际值来判断的，所以相同的数据和初始参数下，模型更新的过程存在不同。我的疑问在于，为什么满足等于0的点也属于误分类点？