感知机模型定位：感知机属于 二分类模型/线性模型/非概率模型/判别模型
回顾：统计学习三要素：模型+策略+算法
算法原理
模型
- 输入空间/特征空间：
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∣∣1?yi?(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)=?∑i?yi?(wxi?+b)，注意，这里的风险函数并没有像均方误差那样取平均【模型的目标函数是需要根据模型的特点设定的】
算法
感知机采用随机梯度下降算法进行最优解的求解；
原始形式
对L(w,b)求偏导，得到梯度：
?
w
L
(
w
,
b
)
=
?
∑
i
y
i
x
i
\nabla_wL(w,b)=-\sum_i y_ix_i
?w?L(w,b)=?∑i?yi?xi?
?
b
L
(
w
,
b
)
=
?
∑
i
y
i
\nabla_bL(w,b)=-\sum_i y_i
?b?L(w,b)=?∑i?yi?
于是，随机选取一个误分类点xi，w和b的更新如下：【
η
\eta
η为学习率】
w
=
w
+
η
y
i
x
i
w=w+\eta y_ix_i
w=w+ηyi?xi?
b
=
b
+
η
y
i
b=b+\eta y_i
b=b+ηyi?
对偶形式【值得仔细理解】
考虑感知机的参数更新过程，假设共进行了k次更新，
k
=
∑
i
k
i
k=\sum_ik_i
k=∑i?ki?，其中，
k
i
k_i
ki?为第i个点的更新次数，那么最后得到的w其实等于
w
=
∑
i
=
1
m
α
i
k
i
y
i
x
i
w=\sum_{i=1}^m\alpha_i^{k_i}y_ix_i
w=∑i=1m?αiki??yi?xi?，其中，
α
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}^m\alpha_iy_ix_i·x+b)
y=sgn(∑i=1m?αi?yi?xi??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?=αi?xi?yi?，将所有样本的参数贡献求和，就得到了最后的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
def predict(self,X):
y = X @ self.w + self.b
y = np.where(y>=0,1,-1)
return y
def fit(self,X,y):
m,n = X.shape[0],X.shape[1]
self.w = np.zeros((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
self.b = self.b + self.lr * wrong_index.T @ y
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
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):
m,n = X.shape[0],X.shape[1]
self.a = np.zeros((m,1))
self.b = np.zeros(1)
self.Gram = [[0]*m for _ in range(m)]
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
yhat = self.predict(X)
wrong_index = np.where((y - yhat)!=0,1,0)
self.a = self.a + self.lr*wrong_index
self.b = self.b + self.lr*np.sum(wrong_index*y)
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}^m\alpha_iy_ix_i·x+b)
y=sgn(∑i=1m?αi?yi?xi??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的点也属于误分类点？
|