机器学习之感知机

      感知机是二类分类的线性分类模型，属于监督学习算法。输入为实例的特征向量，输出为实例的类别（取+1和-1）。感知机对应于输入空间中将实例划分为两类的分离超平面。感知机预测是用学习得到的感知机模型对新的实例进行预测的，因此属于判别模型。

      ！：感知机的应用要求数据集为线性可分的。

数据集的线性可分性：

定义：

给定一个数据集 T = {（x1,y1）,(x2,y2),(x3,y3),....,(xn,yn) } ,其中xi

 X = Rn , yi 

 Y={+1,-1} , i = 1,2,3,.....,n, 如果存在某个超平面S ： w * x + b = 0 能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有 yi = +1 的实例 i ,有w * x + b > 0,对所有 yi = -1 的实例 i ,有w * x + b < 0, 则称数据集T为线性可分数据集，否则，称数据集T线性不可分。

感知机定义：

假设输入空间(特征向量)为X⊆Rn，输出空间为Y={-1, +1}。输入x∈X表示实例的特征向量，对应于输入空间的点；输出y∈Y表示示例的类别。由输入空间到输出空间的函数为

f(x)=sign(w⋅x+b)

称为感知机。其中，参数w叫做权值向量weight，b称为偏置bias。w·x表示w和x的点积

sign为符号函数，即

感知机的几何解释：

线性方程： w * x + b = 0 对应于特征空间Rn 中的一个超平面S，其中 w 为超平面的法向量，b 是超平面的截距。这个超平面将特征空间划分为两个部分，因此超平面S又称为分离超平面。

感知机的学习策略：

核心：极小化损失函数。

如果训练集是可分的，感知机的学习目的是求得一个能将训练集正实例点和负实例点完全分开的分离超平面。为了找到这样一个平面（或超平面），即确定感知机模型参数w和b，我们采用的是损失函数，同时并将损失函数极小化。

损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数 w , b 的连续可导函数，不易优化。所以，我们采用的是误分类点到超平面的总距离

先写出输入空间Rn中任一点x0 到超平面S 的距离：

其中||w||是L2范数。（L2范数:  ||x||为x向量各个元素平方和的1/2次方，L2范数又称Euclidean范数或者Frobenius范数）

对于误分类点(xi,yi)来说：

因此，误分类点到超平面的距离为：

假设，超平面S 误分类点集合为M ，那么，所有点到超平面的总距离为：

不考虑 1/||w|| ,就得到感知机的损失函数了。

可以看出，随时函数L(w,b)是非负的。如果没有误分类点，则损失函数的值为0，而且误分类点越少，误分类点距离超平面就越近，损失函数值就越小。同时，损失函数L(w,b)是连续可导函数。

感知机学习算法：

一、原始形式：

感知机学习算法是误分类驱动的，具体采用随机梯度下降法:

  首先，任意选取一个超平面w0, b0, 然后用梯度下降法不断地极小化损失函数 L(w, b).极小化过程中不是一次使M 中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

要使用随机梯度下降法，需要先求出L(w,b)关于w和b的梯度，结果如下：

所谓的随机梯度下降法，就是在训练的时候随机选取一个误分类点

对w和b进行更新，更新方式如下:

其中η>0是学习率，影响优化速率。这样，通过迭代可以期待损失函数不断减少，直至为 0 .

这种学习算法直观上有如下解释： 当一个实例点被误分类，及位于分离超平面的错误一侧时，则调整w, b的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直至超平面越过该误分类点使其被正确分类。

例举一个使用感知机算法的例子:

首先，取初值 w0 = 0, b0 = 0  ,发现此时对于 x1 = (3,3)  ， y1 * (w0 + b0) = 0 ，未能被正确分类，更新 w , b.

w1 = w0 + y1*x1

b1 = b0 + y1

如此继续下去，不断选择误分类点，并更新 w , b ，整理全过程如下：

可见，感知机学习算法由于采用不同的初值或选取不同的误分类点，解可以不同。

代码：

import numpy as np
from matplotlib import pyplot as plt

X=np.array([[3, 3],[4, 3],[1, 1]])
y=np.array([1,1,-1])

# 定义参数初始化函数
def initilize_with_zeros(dim):
    w = np.zeros(dim)
    b = 0.0
    return w, b


# 定义sign符号函数
def sign(x, w, b):
    return np.dot(x,w)+b


# 定义感知机训练函数
def train(X_train, y_train, learning_rate):
    # 参数初始化
    w, b = initilize_with_zeros(X_train.shape[1])
    # 初始化误分类
    is_wrong = False
    while not is_wrong:
        wrong_count = 0
        for i in range(len(X_train)):
            X = X_train[i]
            y = y_train[i]
            # 如果存在误分类点
            # 更新参数
            # 直到没有误分类点
            if y * sign(X, w, b) <= 0:
                w = w + learning_rate*np.dot(y, X)
                b = b + learning_rate*y
                wrong_count += 1
        if wrong_count == 0:
            is_wrong = True
            print('There is no missclassification!')
        
        # 保存更新后的参数
        params = {
            'w': w,
            'b': b
        }
    return params


params = train(X, y, 0.01)
params

plt.plot(X[:2][:,0],X[:2][:,1], 'bo',X[2:][:,0],X[2:][:,1],'rx')
plt.axis([0, 6, 0, 6])
#plt.grid(True)
plt.xlabel('x')
plt.ylabel('y')
plt.title('perceptron')
x_points = np.linspace(-6, 6, 10)
y_hat = -(params['w'][0]*x_points + params['b'])/params['w'][1]
plt.plot(x_points, y_hat)
           

运行结果：

二、对偶形式：

对偶指的是，将 w 和 b 表示为测试数据  i  的线性组合形式，通过求解系数得到 w 和 b 。具体说来，如果对误分类点 i 逐步修改w,b 修改了n次，则w，b关于 i  的增量分别为

，这里

，则最终求解到的参数分别表示为：

（其中 N 为（xi , yi）的个数）。

于是有算法：

代码：

import numpy as np
from matplotlib import pyplot as plt

training_set = np.array([[[3, 3], 1], [[4, 3], 1], [[1, 1], -1]])
 
Gram = None
y = np.array(training_set[:, 1])
x = np.empty((len(training_set), 2), np.float)
for i in range(len(training_set)):
    x[i] = training_set[i][0]
    
    
def cal_gram():
    """
    初始化 Gram
    """
    g = np.empty((len(training_set), len(training_set)), np.int)
    for i in range(len(training_set)):
        for j in range(len(training_set)):
            g[i][j] = np.dot(training_set[i][0], training_set[j][0])
    return g

Gram = cal_gram()


# 定义sign符号函数
def sign(y,i,a,b):
    res = np.dot(a * y, Gram[i]) + b
    return res


# 定义感知机训练函数
def train(X_train, y_train, learning_rate):
    # 参数初始化
    a = np.zeros(len(training_set), np.float)
    b = 0.0
    
    # 初始化误分类
    is_wrong = False
    while not is_wrong:
        wrong_count = 0
        for i in range(len(X_train)):
            X = X_train[i]
            y = y_train[i]
            # 如果存在误分类点
            # 更新参数
            # 直到没有误分类点
            if y * sign(y_train,i,a, b) <= 0:
                a[i] += learning_rate
                b = b + learning_rate*y              
                wrong_count += 1
        if wrong_count == 0:
            is_wrong = True
            print('There is no missclassification!')
        
        # 保存更新后的参数
        params = {
            'w': np.dot(a * y_train, X_train),
            'b': b
        }
    return params


params = train(x, y,1)
params

plt.plot(x[:2][:,0],x[:2][:,1], 'bo',x[2:][:,0],x[2:][:,1],'rx')
plt.axis([0, 6, 0, 6])
#plt.grid(True)
plt.xlabel('x')
plt.ylabel('y')
plt.title('perceptron')
x_points = np.linspace(-6, 6, 10)
y_hat = -(params['w'][0]*x_points + params['b'])/params['w'][1]
plt.plot(x_points, y_hat)
           

运行结果：