chapter3-感知机

1.概要

通过上一章最小二乘法的理论与实践，我们知道统计学学习-机器学习-深度学习，它们之间的联系与区别。本章我们将讨论感知机算法，再次讨论他们叁之间的关系。并且很有必要熟悉感知机，虽然它现在在分类模型当中已经不适用，因为泛化能力有限，能力更强的为支撑向量机(svm)。但是它在机器学习和深度学习其他深奥算法上有较大的联系，甚至为其算法逻辑实现基础。掌握它的思想，为进一步的提升，打下坚实的基础。

2.感知机模型原理

首先感知机算法是一种二分类线性算法。当然也可以提升至多维分类模型上，但是都是线性模型，对于非线性的，神经网络了解一下。感知机学习算法：用一个函数输入$x$(一个实值的向量)映射到输出值$f(x)$(一个二元值):
$$
f(x)=\begin{cases}
1 \qquad if \quad w.x + b > 0 \ \
-1 \qquad other wise
\end{cases}
$$

对于多维来说，如果我们有m个样本，每个样本对应于n维特征和一个二元类别输出，如下：
$$
(x_1^{(0)},x_2^{(0)},\cdots ,x_n^{(0)},y_0),\
(x_1^{(1)},x_2^{(1)},\cdots ,x_n^{(1)},y_1),\
(x_1^{(2)},x_2^{(2)},\cdots ,x_n^{(2)},y_2),\
\cdots,\
(x_1^{(m)},x_2^{(m)},\cdots ,x_n^{(m)},y_m)
$$
目标是找到一个如下平面去分割数据，即为：
$$
\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_3+\cdots+\theta_nx_n =0
$$
比较函数$f(x)$我们亦可以找出一个平面作为二分类平面,即为：
$$
f(x)=\begin{cases}
\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_3+\cdots+\theta_nx_n>0 \
\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_3+\cdots+\theta_nx_n<0
\end{cases}
$$
当然，我们是可以进行简化公式3的，拟定一个$x_0=1$，这样就有一个超平面$\sum_{i=0}^n \theta \bullet x$

其中，$\theta$和$x$都是$(n+1)\times1$的向量,之间内积就组成一个平面。

感知机模型定义为，$y=sign(\theta \bullet x)$,其中
$$
sign(x)=\begin{cases}-1 \quad x<0 \ 1 \quad x\geq 0 \end{cases}
$$

3.感知机模型损失函数

从公式(5)可以看出令我们把的结果分为1和-1而不是0，这样我们可以很好的去判断分类结果是否正确，比如$y\theta \bullet x=1$(预测结果与真实样本同号，即为正确)，反之，$y\theta \bullet x=-1$则为分类错误。

对于感知机模型函数，我们目标就是使分类错误的点到超平面$y$的距离和最小，由于$y\theta \bullet x<0$,所以对于每一个被错误分类的样本$i\in M$(其中M个分类错误点)到超平面的距离为：
$$
\frac{-y^{(i)}\theta \bullet x^{(i)}}{\begin{Vmatrix} \theta \end{Vmatrix}_2}
$$
其中${\begin{Vmatrix} \theta \end{Vmatrix}_2}$为L2范数

即可得到初步的损失函数:
$$
J\theta = -\sum_{i=0,i \in M}^{n}\frac{y^{(i)}\theta \bullet x^{(i)} }{\begin{Vmatrix} \theta \end{Vmatrix}_2}
$$
观察公式(7)，容易看出，分子分母都带有$\theta$，利用简单的数学知识可以看出，不管$\theta$如何增加还是减小，对于

$J(\theta)$来说都是同倍数增加减的。所以，我们可以把分子分母中的$\theta$简化一个，即，我们保留分子中的$\theta$。因此，简化后的损失函数为:
$$
J(\theta) = - \sum_{i=0,i \in M}^{n}{y^{(i)}\theta \bullet x^{(i)} }
$$
如果您了解支撑向量机(svm)的话，他的损失函数，是保留的分母，也就是:
$$
min\frac{1}{\begin{Vmatrix}\theta\end{Vmatrix}} \Leftrightarrow min\frac{1}{2}\begin{Vmatrix}\theta\end{Vmatrix}_2
$$

3.感知机模型的优化算法

根据上述的推论。我们已知感知机模型算法的损失函数，因此，我们可以去迭代损失函数去找到最优参数$\theta$,依据原理可知，损失函数是通过对分类错误的样本进行更新，使之模型能够分类，正确。通常感知机模型的优化算法常用梯度下降算法(Gradient Descent)、拟牛顿算法，进行去优化。对于梯度下降算法分为批量梯度下降算法(BGD),随机梯度下降算法(SGD)和小批量随机梯度算法(MBGD)。由于感知机算法是对错误样本进行更新，所以不能够使用BGD,我们将用常用的SGD进行举例说明.

因此，我们对损失函数$J(\theta)$,对$\theta$进行求导可得:
$$
\frac{\partial }{\partial \theta_i}J(\theta_0,\theta_1,\cdots,\theta_j) =-\sum_{x_i\in M}y^{(i)}x^{(i)}
$$
即更新损失函数$J(\theta)$梯度下降公式:
$$
\theta=\theta+\alpha\sum_{x_i\in M}y^{(i)}x^{(i)}
$$
由于我们采用SGD，所以每次仅仅只需对一个误分类样本进行更新梯度。即假设采用第$i$个样本来更新，则可以假话公式为:
$$
\theta=\theta+\alpha y^{(i)}x^{(i)}
$$
其中$\alpha$为步长，$y^{(i)}$为样本输出结果(1 | -1),$x^{(i)}$为$(n+1)\times1$的向量。

4.感知机模型算法

我们已经通过上述讨论，知道感知机模型算法的细枝末节，现在我们来总结，如何去实现此算法。

首先我们确定样本特征。对于特征如下:
$$
(x_1^{(0)},x_2^{(0)},\cdots ,x_n^{(0)},y_0),\
(x_1^{(1)},x_2^{(1)},\cdots ,x_n^{(1)},y_1),\
(x_1^{(2)},x_2^{(2)},\cdots ,x_n^{(2)},y_2),\
\cdots,\
(x_1^{(m)},x_2^{(m)},\cdots ,x_n^{(m)},y_m)
$$
对于样本输出结果$y^{(i)} \in(1,-1)$的二分类。
初始化所有$x_0 = 1$，对于参数$\theta$ 初始化为1,$\alpha$步长初始化0.8。
判断是否有样本满足$y\theta \bullet x=-1$，即为误分类样本，并且从中选择一个样本$x_i$,
对选择样本$x_i$进行更新参数$\theta_i$,更新后进入步骤3。

$$
\theta=\theta+\alpha\sum_{x_i\in M}y^{(i)}x^{(i)}
$$

如果没有误分类样本就结束训练.此时的$\theta$即为最佳参数。

5.感知机算法的对偶形式

感知机算法的对偶形式是对梯度下降过程进行优化，对于函数

$$
f(x)=\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_3+\cdots+\theta_nx_n
$$
求导得到梯度可得:
$$
f(x)=\begin{cases}
\theta_i^{(j)} = \sum_{i=1}^{n}\alpha y_i^{(j)}x_i^{(j)} \quad j \in m\
\theta_0 = \sum_{i=1}^{n} \alpha y_i
\end{cases}
$$
对于梯度函数只对错误样本进行更新梯度，如果错误样本$j \in m$,那么对于错误样本$j$，函数分错一般就在拟合函数之间。如果你知道支持向量机(svm)的话，那么这些点就可能就是支撑向量点。而对于这些点迭代次数为$m_j$的话，由于$\alpha$亦为常数，我就可以令$\alpha m_j=\beta_j$,因此函数可以重写为:
$$
f(x)=\begin{cases}
\theta_i^{(j)} = \sum_{i=1}^{n}\beta_j y_i^{(j)}x_i^{(j)} \quad j \in m\
\theta_0 = \sum_{i=1}^{n} \beta_j y_i
\end{cases}
$$
对于对偶式，将公式(17)代入$y=sign(\theta \bullet x)$(假定了$x_0$=1),对于一次函数来说，有~
$$
f(x)=sign(\theta_1x+\theta_0)=sign(\sum_{j=1}^{m}\beta_j y_jx_j\bullet x_i+\sum_{j=1}^{m} \beta_j y_j) \quad j \in m
$$
即可判断是否为错误分类点公式为:
$$
y_i(\sum_{j=1}^{m}\beta_j y_jx_j\bullet x_i+\sum_{j=1}^{m} \beta_j y_j) < 0\qquad(19)
$$
根据公式(18)，依据$y=\theta_1x+\theta_0$的形式代入公式(5)中，即得。观察公式(18)，我们可以看出有内积$G=x^{(i)}\bullet x^{(j)}$,两个常量矩阵内积令为$G$。我们可以事先算出$G$，进行查矩阵表形式给出值，就可以省下大量的计算。因此优化了梯度下降算法。本质就是对错误样本的删选算法形式进行优化。

因此，感知机对偶形式算法实现为！

1.初始化所有$x_0 = 1$，对于参数$\theta$ 初始化为1,$\alpha$步长初始化0.8，$\beta$为0。同上，不同初始值会带来不同的效果

2.计算样本内积Gram矩阵$G$

3. 在训练集里面选择一个误分类的点$(x^{(i)},y^{(i)})$,这个点应满足公式(19)，在检查是否满足时，就可以通过查询Gram矩阵的$G_{ij}$，的值，快速计算是否小于0

3.对$\beta$错误样本$i$分量进行更新$\beta_i =\beta_i+\alpha$

4.检查训练集里是否还有误分类的点，如果没有，算法结束，此时的$\theta$向量最终结果为下式。如果有,继续第2步

$$
\begin{cases}
\theta_i^{(j)} = \sum_{i=1}^{n}\beta_j y_i^{(j)}x_i^{(j)} \quad j \in m\
\theta_0 = \sum_{i=1}^{n} \beta_j y_i
\end{cases}
$$

6.感知机算法代码实践

6.1.感知机模型算法实现

导入相关工具包

import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
%matplotlib inline

加载数据

# load data
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target

df.columns = [
    'sepal length', 'sepal width', 'petal length', 'petal width', 'label'
]
df.label.value_counts()

数据可视化

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

划分数据集与样本

#iris数据集是三类样本没类样本数量为50 所以只取前两个样本
data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
y = np.array([1 if i == 1 else -1 for i in y])

5.建立感知机模型

# 数据线性可分，二分类数据
# 此处为一元一次线性方程
class Model:
    def __init__(self):
        self.w = np.ones(len(data[0]) - 1, dtype=np.float32)
        self.b = 0
        self.l_rate = 0.1
        # self.data = data

    def sign(self, x, w, b):
        y = np.dot(x, w) + b
        return y

    # 随机梯度下降法
    def fit(self, X_train, y_train):
        is_wrong = False
        while not is_wrong:
            wrong_count = 0
            for d in range(len(X_train)):
                X = X_train[d]
                y = y_train[d]
                if y * self.sign(X, self.w, self.b) <= 0:
                    self.w = self.w + self.l_rate * np.dot(y, X)
                    self.b = self.b + self.l_rate * y
                    wrong_count += 1
            if wrong_count == 0:
                is_wrong = True
        return 'Perceptron Model!'

    def score(self):
        pass

建立对偶形式感知机模型

G = np.dot(X,X.T)
print(G,G.shape,y.shape)

# 数据线性可分，二分类数据
# 此处为一元一次线性方程
class Model_Dual:
    def __init__(self):
        self.w = np.ones(X.shape[1], dtype=np.float32)
        self.beta = np.zeros(data.shape[0], dtype=np.float32)
        self.b = 0
        self.l_rate = 0.1 

        # self.data = data

    def sign(self, x, w, b, y):    
        y_ = np.sum(y*w*x + b)
        return y_

    # 随机梯度下降法
    def fit(self, X_train, y_train):
        is_wrong = False
        while not is_wrong:
            wrong_count = 0
            for d in range(X_train.shape[0]):
              X = G[d]
              y = y_train[d]
              x = X_train[d]
              sum_v = 0 
              for d1 in range(X_train.shape[0]): 
                #print(self.beta[d1] , y_train[d1] , X[d1])
                w1 = self.beta[d1] * y_train[d1] * X[d1]
                b1 = self.beta[d1] * y_train[d1]
                sum_v += (w1 + b1)
              if y*sum_v <= 0:
                  self.beta[d] = self.beta[d] + self.l_rate
                  wrong_count += 1
                  
            if wrong_count == 0:
                is_wrong = True
        return 'Perceptron Model!'

    def score(self):
        pass

训练模型

perceptron = Model()
perceptron.fit(X, y)

#@title Default title text
perceptron = Model_Dual()
perceptron.fit(X, y)

可视化结果()

#普通形式训练结果
x_points = np.linspace(4, 7, 10)
y_ = -(perceptron.w[0] * x_points + perceptron.b) / perceptron.w[1]
plt.plot(x_points, y_)

plt.plot(data[:50, 0], data[:50, 1], 'bo', color='blue', label='0')
plt.plot(data[50:100, 0], data[50:100, 1], 'bo', color='orange', label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

#对偶形式训练结果
print(perceptron.beta.shape,y.shape,X.shape)
perceptron.w = np.dot((np.multiply(list(perceptron.beta),y)),X)
perceptron.b = np.dot(perceptron.beta,y)
#需上诉算出参数
x_points = np.linspace(4, 7, 10)
y_ = -(perceptron.w[0] * x_points + perceptron.b) / perceptron.w[1]
plt.plot(x_points, y_)

plt.plot(data[:50, 0], data[:50, 1], 'bo', color='blue', label='0')
plt.plot(data[50:100, 0], data[50:100, 1], 'bo', color='orange', label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

6.2 感知机算法-sklearn实现

导包

import sklearn
from sklearn.linear_model import Perceptron

sklearn.__version__

建模


clf = Perceptron(fit_intercept=True, 
                 max_iter=1000, 
                 shuffle=True)
clf.fit(X, y)
# Weights assigned to the features.
print(clf.coef_)

# 截距 Constants in decision function.
print(clf.intercept_)

3.训练可视化

# 画布大小
plt.figure(figsize=(10,10))

# 中文标题
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus'] = False
plt.title('鸢尾花线性数据示例')

plt.scatter(data[:50, 0], data[:50, 1], c='b', label='Iris-setosa',)
plt.scatter(data[50:100, 0], data[50:100, 1], c='orange', label='Iris-versicolor')

# 画感知机的线
x_ponits = np.arange(4, 8)
y_ = -(clf.coef_[0][0]*x_ponits + clf.intercept_)/clf.coef_[0][1]
plt.plot(x_ponits, y_)

# 其他部分
plt.legend()  # 显示图例
plt.grid(False)  # 不显示网格
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

4.纠正错误

在上图中，有一个位于左下角的蓝点没有被正确分类，这是因为 SKlearn 的 Perceptron 实例中有一个tol参数。

tol 参数规定了如果本次迭代的损失和上次迭代的损失之差小于一个特定值时，停止迭代。所以我们需要设置 tol=None 使之可以继续迭代：

clf = Perceptron(fit_intercept=True, 
                 max_iter=1000,
                 tol=None,
                 shuffle=True)
clf.fit(X, y)

# 画布大小
plt.figure(figsize=(10,10))

# 中文标题
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus'] = False
plt.title('鸢尾花线性数据示例')

plt.scatter(data[:50, 0], data[:50, 1], c='b', label='Iris-setosa',)
plt.scatter(data[50:100, 0], data[50:100, 1], c='orange', label='Iris-versicolor')

# 画感知机的线
x_ponits = np.arange(4, 8)
y_ = -(clf.coef_[0][0]*x_ponits + clf.intercept_)/clf.coef_[0][1]
plt.plot(x_ponits, y_)

# 其他部分
plt.legend()  # 显示图例
plt.grid(False)  # 不显示网格
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

迭代次数随着tol减少或者不要而增加。模型对样本的数据拟合程度会更高（tol可以间接防止过度拟合样本）

参考文献

@(*.*)@ @(^.^)@ @(*.*)@ @(^.^)@ @(*.*)@ @(^.^)@ @(*.*)@ @(^.^)@ @(*.*)@ @(^.^)@