机器学习之感知机

1.概念与目的

感知机是**二类分类的线性模型,属于判别模型**.
假设训练数据集是线性可分的，感知机学习的目标是**求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面**。如果是非线性可分的数据，则最后无法获得超平面.是神经网络和支持向量机的基础.
**超平面：**在二维空间中超平面是一条线，在三维空间中的超平面是一个平面

2.模型

f(x)=sign(w⋅x+b)
w叫作权值向量,b叫做偏置,sign是符号函数.
几何解释：
wx+b对应于特征空间中的一个分离超平面S,其中w是S的法向量,b是S的截距.S将特征空间划分为两个部分,位于两个部分的点分别被分为正负两类.

3.策略

假设训练数据集是线性可分的,感知机的损失函数是误分类点到超平面S的总距离.因为误分类点到超平面S的距离是:

且对于误分类的数据来说,总有

成立,因此不考虑1/||w||,就得到感知机的损失函数:,

其中M是误分类点的集合.感知机学习的策略就是选取使损失函数最小的模型参数.
问题：为什么不考虑1/||w||？原因可以列为以下两点。
1/||w|| 不影响yi(w⋅xi+b) 正负的判断，即不影响学习算法的中间过程。因为感知机学习算法是误分类驱动的，这里需要注意的是所谓的“误分类驱动”指的是我们只需要判断−yi(w⋅xi+b) 的正负来判断分类的正确与否，而1/||w|| 并不影响正负值的判断。所以1/||w|| 对感知机学习算法的中间过程可以不考虑。
**1/||w|| 不影响感知机学习算法的最终结果。**因为感知机学习算法最终的终止条件是所有的输入都被正确分类，即不存在误分类的点。则此时损失函数为0. 对应于−1/||w||∑i∈Myi(w⋅xi+b) ，即分子为0.则可以看出1/||w|| 对最终结果也无影响。综上所述，即使忽略1/||w|| ，也不会对感知机学习算法的执行过程产生任何影响。反而还能简化运算，提高算法执行效率。

4.算法

**感知机学习算法是对上述损失函数进行极小化，求得w和b。**但是用普通的基于所有样本的梯度和的均值的批量梯度下降法（BGD）是行不通的，原因在于我们的损失函数里面有限定，**只有误分类的M集合里面的样本才能参与损失函数的优化**。所以我们不能用最普通的批量梯度下降,**只能采用随机梯度下降（SGD）**。目标函数如下：

原始形式算法：

对偶形式算法：
假设原始形式中的w0和b0均为0,设逐步修改w和b共n次,令a=nη,最后学习到的w,b可以表示为

那么对偶算法就变为设初始a和b均为0,每次选取数据更新a和b直至没有误分类点为止.对偶形式的意义在于可以将训练集中实例间的内积计算出来,存在Gram矩阵中,可以大大加快训练速度.

5.算法的选择

在向量维数（特征数）过高时，计算内积非常耗时，应选择对偶形式算法加速。
在向量个数（样本数）过多时，每次计算累计和就没有必要，应选择原始算法。

6.代码实现

原始形式算法&对偶形式算法：

# -*- coding: utf-8 -*-
import numpy as np
class Perceptron(object):
    def __init__(self, input_x, feature_num, input_y, learn_rate=1):
        self._input_x = np.array(input_x) # 输入数据集中的X
        self._input_y = np.array(input_y) # 输入数据集中的Y
        self._feature_num = feature_num   # 总共有多少个特征
        self._rate = learn_rate           # 学习速率
        self._final_w = 0                 # 最后学习到的w
        self._final_b = 0                 # 最后学习到的b
        
    def sgd_train(self): #算法原始形式
        total = len(self._input_y)
        feature_num = range(self._feature_num)
        data_num = range(total)
        w = np.zeros(self._feature_num)   #初始化向量w
        b = 0

        while True:
            separted = True
            for i in data_num:           # 遍历数据集，查找误分类点
                inner = np.inner(w, self._input_x[i]) //内积函数
                if self._input_y[i] * (inner+b) <= 0: # 误分类点
                    separted = False
                    w = w + self._rate * self._input_y[i] * self._input_x[i]
                    b = b + self._rate * self._input_y[i]
            if separted:
                break
            else:
                continue
        self._final_w = w
        self._final_b = b
        print(self._final_w, self._final_b)

    def pair_sgd_train(self): # 对偶形式
        total = len(self._input_y)
        feature_num = range(self._feature_num)
        data_num = range(total)
        gram_matrix = self._input_x.dot(self._input_x.T) # Gram 矩阵
        alpha = np.random.random(size=total) # 这里初始化alpha向量为随机值
        b = 0

        while True
            separted = True
            for i in data_num:
                inner = np.sum(alpha * self._input_y * gram_matrix[i])
                if self._input_y[i] * (inner+b) <= 0:  # 误分类点
                    separted = False
                    alpha[i] = alpha[i] + self._rate   # 对偶形式只更新alpha向量中的一个分量
                    b = b + self._rate * self._input_y[i]
            if separted:
                break
            else:
                continue
        self._final_w = (alpha * self._input_y.T).dot(self._input_x)
        self._final_b = b
        print(self._final_w, self._final_b)

input_x = [[3,3], [4,3], [1,1], [2,3]]
input_y = [1,1,-1,-1]

pla = Perceptron(input_x, 2, input_y, 1)
pla.sgd_train()
pla.pair_sgd_train()