机器学习之感知机
感知机模型是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。感知机学习算法，具有简单而易于实现的优点，分为原始形式与对偶形式。感知机预测是用学习得到的感知机模型对新的输入实例进行分类。
1.首先，我们假定线性方程 wx+b=0 是一个超平面，令 g(x)=wx+b，也就是超平面上的点x都满足g(x)=0。对于超平面的一侧的点满足：g(x)>0; 同样的，对于超平面另一侧的点满足：g(x)<0.
结论一：对于不在超平面上的点x，它到超平面的距离：
证明：如下图所示，O表示原点，Xp表示超平面上的一点，X是超平面外的一点，w是超平面的法向量。
等式1说明：向量的基本运算法则，OX＝OXp+XpX. 因为w是法向量，所以w/||w||是垂直于超平面的单位向量。
等式2说明：将等式1带入g(x)=wx+b；由于Xp在超平面上，所以g(Xp)=w^T*Xp+w0 = 0
以上得证。
2.下面区分一下易混淆的两个概念，梯度下降和随机梯度下降：
梯度下降：一次将误分类集合中所有误分类点的梯度下降；
随机梯度下降：随机选取一个误分类点使其梯度下降。
3.对于误分类的数据来说，当w*xi + b>0时，yi = -1,也就是，明明是正例，预测成负例。因此，误分类点到超平面的距离为：
因此所有误分类点到超平面的总距离为:
忽略1/||w||,我们就可以得到感知机学习的损失函数。
损失函数：
这个损失函数就是感知机学习的经验风险函数。
感知机学习算法
从上面可以，感知机学习问题转化为求解损失函数最优化问题，最优化的方法是随机梯度下降法。感知机学习算法有两种形式：原始形式和对偶形式。在训练数据线性可分的条件下，感知机学习算法是收敛的。
原始形式
在给定训练数据集T={(x1,y1), {x2,y2},…..,{xN,yN}}，我们可以通过求参数w和b使得：
其中M是误分类点。
感知机学习算法是误分类数据驱动的，采用随机梯度下降法，即随机选取一个超平面w0和b0，使用梯度下降法对损失函数进行极小化。极小化不是一次使得所有M集合误分类点梯度下降，而是一次随机选取一个点使其梯度下降。
假设M集合是固定，那么损失函数的梯度为：
随机一个选取一个误分类点（xi, yi）对w和b进行更新。
η（0<=η<=1）是步长，统计学习中称为学习率。通过不断迭代，损失函数不断减小，直到为0。
具体步骤：
1、 随机选取w0和b0
2、 在训练数据中选取（xi，yi）
3、 如果yi(w*xi+b) <= 0
4、 转2，直到训练数据中，没有误分类点。
感知机学习算法直观的解释如下：
当一个实例点被误分类时，即位于分离超平面错误的一边，则调整w和b使得超平面想误分类点一侧移动，减少误分类点到超平面的距离。直到超平面越过该误分类点，被正确分类。
以上即为感知机算法的原始形式，理解起来比较简单，也较容易实现。下面给出其的Python实现
'''感知机的原始形式'''
import numpy as np
import matplotlib.pyplot as plt
import random
def sign(v):
if v >= 0:
return 1
else:
return -1
def train(train_num,train_datas,lr):
w = [0,0]
b = 0
for i in range(train_num):
x = random.choice(train_datas)
x1,x2,y = x
if (y*sign(w[0]*x1 + w[1]*x2 + b)) < 0:
w[0] += lr*x1*y
w[1] += lr*x2*y
b += lr*y
return w,b
def plot_points(train_datas,w,b):
plt.figure()
x1 = np.linspace(0,8,100)
x2 = (-b - w[0]*x1)/w[1]
plt.plot(x1,x2,color='r',label = 'y_label')
for i in range(len(train_datas)):
if (train_datas[i][-1] == 1):
plt.scatter(train_datas[i][0],train_datas[i][1],s=50)
else:
plt.scatter(train_datas[i][0],train_datas[i][1],marker='x',s=50)
plt.show()
if __name__=='__main__':
train_data1 = [[1, 3, 1], [2, 2, 1], [3, 8, 1], [2, 6, 1]] # 正样本
train_data2 = [[2, 1, -1], [4, 1, -1], [6, 2, -1], [7, 3, -1]] # 负样本
train_datas = train_data1 + train_data2 # 样本集
w,b = train(train_num=50,train_datas=train_datas,lr=0.01)
plot_points(train_datas,w,b)
感知机学习算法的对偶形式
相比于原始形式，其对偶形式在理解上没有前者那么直观，网上关于其实现代码的例子也比较少。
在《统计学习方法》一书中，关于对偶形式有如下的描述：
对偶形式的基本想法是，将w和b表示为实例xixi 和标记 yiyi 的线性组合的形式，通过求解其系数而求得w和b.
假设w0=0,b=0,那么从(4)式可以看出，当所有的点均不发生误判时，最后的w,b一定有如下的形式:
(5)
其中αi=niηαi=niη中nini代表对第i个样本的学习次数，感知机对偶形式的完整形式即为(6)式：
- 初始化α=0α=0,b=0b=0.
- 任意选取(xi,yi)
- 如果yi(∑j=1Nαjyjxj⋅xi+b)≤0yi(∑j=1Nαjyjxj⋅xi+b)≤0,即发生误判，则对αi,bαi,b进行更新：
αi←αi+ηbi←bi+ηyiαi←αi+ηbi←bi+ηyi - 重复2直到所有点都被正确分类
简而言之，感知机的对偶形式就是把对w,bw,b的学习变成了对α,bα,b的学习，原始形式中，ww在每一轮迭代错分时都需要更新，而采用对偶形式时，对于某一点(xi,yi)发生错分时，我们只需要更新其对应的αiαi即可，最后按照(5)式即可一次计算出ww.
同时我们上述步骤3中的yi(∑j=1Nαjyjxj⋅xi+b)≤0yi(∑j=1Nαjyjxj⋅xi+b)≤0可以看出，xj⋅xixj⋅xi仅以内积的形式出现，因此我们可以是先计算出x的gram矩阵存储起来，这样正式训练时只需要查表就可以得到xj⋅xixj⋅xi的值，这样做可以方便程序的优化，提高运算的速度。
原始形式和对偶形式对参数b的处理是相同的。
以下是感知机对偶形式的Python实现
'''感知机的对偶形式'''
import numpy as np
import matplotlib.pyplot as plt
import random
def sign(v):
if v >= 0:
return 1
else:
return -1
def train(train_num,train_datas,lr):
w=0.0
b=0
datas_len = len(train_datas)
alpha = [0 for i in range(datas_len)]
train_array = np.array(train_datas)
gram = np.matmul(train_array[:,0:-1] , train_array[:,0:-1].T)
for idx in range(train_num):
tmp=0
i = random.randint(0,datas_len-1)
yi=train_array[i,-1]
for j in range(datas_len):
tmp+=alpha[j]*train_array[j,-1]*gram[i,j]
tmp+=b
if(yi*tmp<=0):
alpha[i]=alpha[i]+lr
b=b+lr*yi
for i in range(datas_len):
w+=alpha[i]*train_array[i,0:-1]*train_array[i,-1]
return w,b,alpha,gram
def plot_points(train_datas,w,b):
plt.figure()
x1 = np.linspace(0,8,100)
x2 = (-b - w[0]*x1)/w[1]
plt.plot(x1,x2,color='r',label = 'y_label')
for i in range(len(train_datas)):
if (train_datas[i][-1] == 1):
plt.scatter(train_datas[i][0],train_datas[i][1],s=50)
else:
plt.scatter(train_datas[i][0],train_datas[i][1],marker='x',s=50)
plt.show()
if __name__=='__main__':
train_data1 = [[1, 3, 1], [2, 2, 1], [3, 8, 1], [2, 6, 1]] # 正样本
train_data2 = [[2, 1, -1], [4, 1, -1], [6, 2, -1], [7, 3, -1]] # 负样本
train_datas = train_data1 + train_data2 # 样本集
w,b ,alpha,gram = train(train_num=50,train_datas=train_datas,lr=0.01)
plot_points(train_datas,w,b)