机器学习-2-感知机

感知机

感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。基于误分类的损失函数，利用梯度下降法对损失函数进行最小化，求得感知机模型。

感知机分为原始形式和对偶形式，利用学习得到的感知机模型对新的输入实例进行分类，是神经网络与支持向量机的基础。

感知机模型

假设输入空间（特征空间）$\mathcal{X} \subseteq \mathbf{R}^{n}$，输出空间是$\mathcal{Y}=\{+1,-1\}$。输入$x \in \mathcal{X}$表示实例的特征向量，对应于输出空间（特征空间）的点；输出$y \in \mathcal{Y}$表示实例的类别。感知机表示输入空间到输出空间的函数：

$f(x)=\operatorname{sign}(w \cdot x+b)$

$w \in \mathbf{R}^{n}$和$b \in \mathbf{R}$为感知机模型参数，前者为权值向量，后者为偏置。$w \cdot x$表示$w$和$x$的内积，sign是符号函数：

$\operatorname{sign}(x)=\left\{\begin{array}{ll}{+1,} & {x \geqslant 0} \\ {-1,} & {x<0}\end{array}\right.$

感知机是一种线性分类模型，属于判别模型。

感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合$\{f | f(x)=w \cdot x+b\}$。

感知机的几何解释：线性方程$w \cdot x+b=0$对应于特征空间中的一个超平面$S$，其中$w$是超平面的法向量，$b$是超平面的截距。这个超平面将特征空间划分为两个部分，位于两部分的点分别被分为正、负两类。

mark

感知机学习策略

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面，即确定感知机模型参数$w$和$b$。需要确定一个学习策略，即定义损失函数并将损失函数极小化。

损失函数：选择误分类点到超平面$S$的总距离作为损失函数。

输入空间$\mathbf{R}^{n}$中任一点$x_0$到超平面$S$的距离为：

$\frac{1}{\|w\|}\left|w \cdot x_{0}+b\right|$

其中$|w|$是$w$的$L_2$范数。

对于误分类的数据$(x_i, y_i)$来说，满足：

$-y_{i}\left(w \cdot x_{i}+b\right)>0$

因此，误分类点$x_i$到超平面$S$的距离是：

$-\frac{1}{\|w\|} y_{i}\left(w \cdot x_{i}+b\right)$

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

$-\frac{1}{\|w\|} \sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)$

不考虑$-\frac{1}{|w|}$，可以得到感知机$\operatorname{sign}(w \cdot x+b)$学习的损失函数为：

$L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)$

这个损失函数就是感知机学习的经验风险函数。显然损失函数是非负的，如果没有误分类点，损失函数值为0。而且，误分类点越少，误分类点离超平面越近，损失函数越小。一个特定样本点的损失函数是参数$w$和$b $的线性函数。对于给定训练集，损失函数$L(w, b)$是参数$w$和$b $的连续可导函数。

感知机的学习策略就是在假设空间中选取损失函数最小的模型参数$w$和$b $。

感知机学习算法的原始形式

给定一个训练数据集

$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$

其中$x_{i} \in \mathcal{X}=\mathbf{R}^{n}, \quad y_{i} \in \mathcal{Y}=\{-1,1\}, \quad i=1,2, \cdots, N$，求参数$w$和$b $，使其为以下损失函数极小化问题

$\min _{w, b} L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)$

其中$M$为误分类点的集合。

采用随机梯度下降法求解。首先，任意选取一个超平面$w_0，b_0$，然后用梯度下降法不断地极小化目标函数。极小化过程中不是一次使$M$中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合$M$是古典的，那么损失损失$L(w, b)$的梯度由

$\begin{array}{c}{\nabla_{w} L(w, b)=-\sum_{x_{i} \in M} y_{i} x_{i}} \\ {\nabla_{b} L(w, b)=-\sum_{x_{i} \in M} y_{i}}\end{array}$

给出。

随机选取一个误分类点$(x_i, y_i)$，对$w, b$进行更新：

$\begin{array}{c}{w \leftarrow w+\eta y_{i} x_{i}} \\ {b \leftarrow b+\eta y_{i}}\end{array}$

其中$\eta(0<\eta\le1)$是步长或者学习率。通过迭代可以使损失函数不断减小，直到为0。

算法1：感知机学习算法的原始形式

输入：训练数据集$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$，其中$x_{i} \in \mathcal{X}=\mathbf{R}^{n}, \quad y_{i} \in \mathcal{Y}=\{-1,1\}, \quad i=1,2, \cdots, N$，学习率$\eta(0<\eta\le1)$；

输出：$w, b$；感知机模型$f(x)=\operatorname{sign}(w \cdot x+b)$。

（1）选取初值$w_0，b_0$；

（2）在训练集中选取数据$(x_i, y_i)$；

（3）如果$ y_{i}\left(w \cdot x_{i}+b\right)\le0$

$\begin{array}{c}{w \leftarrow w+\eta y_{i} x_{i}} \\ {b \leftarrow b+\eta y_{i}}\end{array}$

（4）转至（2），直到训练集中没有误分类点。

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

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

算法收敛性：对于线性可分数据集感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。详细证明略。

感知机学习算法的对偶形式

感知机学习算法的原始形式和对偶形式与SVM的原始形式和对偶形式对应。

对偶形式的基本思想是将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得$w$和$b$。将初始值$w_0$，$b_0$都设为0，原始形式中对误分类点$(x_i, y_i)$通过

$\begin{array}{c}{w \leftarrow w+\eta y_{i} x_{i}} \\ {b \leftarrow b+\eta y_{i}}\end{array}$

逐步修改$w$和$b$，设修改$n$次，则$w$，$b$关于$(x_i, y_i)$的增量分别是$\alpha_iy_ix_i$和$\alpha_i y_i$，这里$\alpha_i=n_i\eta$。因此最后学习到的$w$和$b$分别为

$\begin{array}{l}{w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i}} \\ {b=\sum_{i=1}^{N} \alpha_{i} y_{i}}\end{array}$

当$\eta=1$时，表示第$i$个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类。换句话说，这样的实例对学习结果影响最大。

算法2：感知机学习算法的对偶形式

输出：$\alpha, b$；感知机模型$f(x)=\operatorname{sign}(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x+b)$，其中$\alpha=\left(\alpha_{1}, \alpha_{2}, \cdots, \alpha_{N}\right)^{\mathrm{T}}$

（1）选取初值$\alpha\leftarrow0，b\leftarrow0$；

（2）在训练集中选取数据$(x_i, y_i)$；

（3）如果$·$

$\begin{array}{c}{\alpha_i \leftarrow \alpha_i+\eta} \\ {b \leftarrow b+\eta y_{i}}\end{array}$

（4）转至（2），直到训练集中没有误分类点。

算法结束之后带入${w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i}} $得到最终的$w$。

算法解释：对偶形式中训练实例仅以內积的形式出现。为了方便，可以预先将训练集中实例间的內积计算出来并以矩阵的形式存储，即Gram矩阵$G=\left[x_{i} \cdot x_{j}\right]_{N \times N}$。

与原始形式一样，感知机学习算法的对偶形式迭代也是收敛的，存在多个解。

实战

前文已经详细介绍了感知机的原理，包括原始形式和对偶形式，使用iris数据集中两个分类的数据和[sepal length，sepal width]作为特征对感知机进行实现。

代码实现

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris

class Perceptron:
    def __init__(self, data, label, learning_rate = 1):
        self.w = np.zeros(data.shape[1])
        self.b = 0
        self.eta = learning_rate
        self.X = data
        self.y = label

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

    def fit(self):
        flag = False
        while not flag:
            wrongNum = 0
            for x, y in zip(self.X, self.y):
                if y * self.sign(x, self.w, self.b) <= 0:
                    self.w += np.dot(y, x) * self.eta
                    self.b += y * self.eta
                    wrongNum += 1
            if wrongNum == 0:
                flag = True
                print("Fit finished")

    def fit_dual(self):
        a = np.zeros(self.X.shape[0])
        G = self.X @ self.X.T
        flag = False
        while not flag:
            wrongNum = 0
            for i, y in enumerate(self.y):
                if y * self.sign(a * self.y, G[i], self.b) <= 0:
                    a[i] += self.eta
                    self.b += self.eta * y
                    wrongNum += 1
            if wrongNum == 0:
                flag = True
                print("Fit dual finished")

        for j in range(self.X.shape[0]):
            self.w += a[j] * self.X[j] * self.y[j]


if __name__ == '__main__':

    iris = load_iris()
    data = iris["data"][:100, :2]
    label = iris["target"][:100]
    label = np.array([1 if i == 1 else -1 for i in label])

    flag = 1
    if flag == 0:
        # 原始形式
        model = Perceptron(data, label, learning_rate=1)
        model.fit()
    else:
        # 对偶形式
        model = Perceptron(data, label, learning_rate=1)
        model.fit_dual()

    w, b = model.w, model.b
    plt.scatter(data[:50, 0], data[:50, 1], label='-1')
    plt.scatter(data[50:100, 0], data[50:100, 1], label='1')
    plt.xlabel('sepal length')
    plt.ylabel('sepal width')
    plt.legend()
    xHyper = np.linspace(4, 7, 10)
    yHyper = -(w[0] * xHyper + b) / w[1]
    plt.plot(xHyper, yHyper, 'r')
    plt.show()

原始形式结果：
mark
对偶形式结果：
mark
可以看到原始形式和对偶形式都能将数据进行分类。

sklearn实现

from sklearn.linear_model import Perceptron
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris

if __name__ == '__main__':

    iris = load_iris()
    data = iris["data"][:100, :2]
    label = iris["target"][:100]
    label = np.array([1 if i == 1 else -1 for i in label])

    model = Perceptron(max_iter=1000, tol=None)
    model.fit(data, label)
    w, b = model.coef_[0], model.intercept_

    plt.scatter(data[:50, 0], data[:50, 1], label='-1')
    plt.scatter(data[50:100, 0], data[50:100, 1], label='1')
    plt.xlabel('sepal length')
    plt.ylabel('sepal width')
    plt.legend()
    xHyper = np.linspace(4, 7, 10)
    yHyper = -(w[0] * xHyper + b) / w[1]
    plt.plot(xHyper, yHyper, 'r')
    plt.show()