关于机器学习:机器学习算法系列一-感知器学习算法PLA

浏览本文须要的背景知识点：数学基础知识、一丢丢编程常识

后面一节咱们理解了机器学习算法系列（〇）- 基础知识，接下来正式开始机器学习算法的学习，首先咱们从最简略的一个算法——感知器学习算法（Perceptron Learning Algorithm）开始。

咱们在应用电子邮件时，应该留神到古代邮箱都有反垃圾邮件的性能，零碎依据邮件的内容主动判断是否是垃圾邮件，节俭了咱们的工夫，试想一下这个性能应该如何实现呢？

咱们能够先收集一批邮件，总结出对判断是否是垃圾邮件有用的一些特征值（例如：邮件是否蕴含链接、邮件呈现过多少个营销词语、邮件的发送工夫等等），而后对每一封邮件先人工的判断是否是垃圾邮件，最初试图通过这些数据来找到外面所蕴含的关联关系。当前给到一封新邮件的时候，咱们就能够通过这些关系来判断是否是垃圾邮件了。

回忆一下在初中生物教材上介绍过的神经细胞，它是由树突、轴突、突触和细胞体组成的构造体。神经细胞是否激活并输入电信号是由其接管到的输出信号量和突触的强度所决定的，当其总和超过某个阈值时，细胞体就会冲动并输入电信号。由这一神经细胞的行为，人们提出了感知器的概念和对应的感知器学习算法。

感知器¹（Perceptron）是一种二元线性分类器，将一个线性可分的数据集通过线性组合分成两种类型。在人工神经网络畛域中，感知机也被指为单层的人工神经网络。

几何意义：在二维立体内找到一条直线将两种类型的数据齐全离开。在高维空间里为找到一个超平面将两类数据离开。

<center>By Elizabeth Goodspeed – Own work, CC BY-SA 4.0</center>
数学定义：把矩阵上的输出 X（实数值向量）映射到输入值 h(x) 上（一个二元的值 -1 或 +1）。假如存在 d 个 x，通过 w 的加权求和，大于某个临界值时返回 +1，小于某个临界值时返回 -1。

$$
\begin{array}{cc}
\sum_{i=1}^{d} w_{i} x_{i}>\text {临界值} & +1(A \text { 分类}) \\
\sum_{i=1}^{d} w_{i} x_{i}<\text {临界值} & -1(B \text { 分类})
\end{array}
$$

将上式写成一个函数的模式（sign 函数称为符号函数²，当输出小于 0 则输入 -1，当输出大于 0 则输入 +1）

$$
h(x) = \operatorname{sign}\left(\sum_{i = 1}^dw_ix_i – 临界值 \right)
$$

将负的临界值当作第 0 个 w，正 1 当作第 0 个 x

$$
h(x)=\operatorname{sign}(\left(\sum_{i=1}^{d} w_{i} x_{i}\right)+\underbrace{(-\text { 临界值})}_{w_{0}} \cdot \underbrace{(+1)}_{x_{0}})
$$

可将临界值合到从 1 到 d 的连加运算中，则连加运算的下界变为 0

$$
h(x) = \operatorname{sign}\left(\sum_{i=0}^dw_ix_i\right)
$$

最初函数可改写为两个向量（w、x）的点积模式

$$
h(x) = \operatorname{sign}\left(w^Tx \right)
$$

感知器是一种特地简略的线性分类模型，然而它的实质缺点是不能解决线性不可分的问题，前面的大节将介绍一个能够容许存在一些谬误的产生，能解决线性不可分数据集的算法——口袋算法（Pocket Algorithm）

感知器学习算法（Perceptron Learning Algorithm）- 其核心思想就是以谬误为驱动，逐渐修改谬误最初收敛的过程。

初始化向量 w，例如 w 初始化为零向量

循环 t = 0，1，2 …

按程序或随机遍历全副数据并计算 h(x)，直到找到其中一个数据的 h(x) 与目标值 y 不符

$$ \operatorname{sign}\left(w_{t}^{T} x_{n(t)}\right) \neq y_{n(t)} $$

修改向量 w

$$ w_{t+1} \leftarrow w_{t}+y_{n(t)} x_{n(t)} $$

直到全副数据的后果都没有谬误退出循环，所得的 w 即为一组方程的解

假如最初的指标权重系数为 wf，待优化的权重系数为 w。通过单位 wf 与单位 w 的点积来作为两个向量是否凑近的规范。（两个单位向量的点积越大，阐明两个向量越靠近，当两个向量同向并共线时两者的点积最大）

因为指标权重系数 wf 的全副分类都是正确的，所以每一个数据点计算出的值与目标值的乘积必然大于乘积中的最小值，并且大于 0（分类正确即同号）

$$
y_{n(t)} w_{f}^{T} x_{n(t)} \geq \min _{n} y_{n} w_{f}^{T} x_{n}>0
$$

<center>（公式一）</center>
待优化的权重系数为 w 只在数据集分类谬误的时候做更新，所以在该数据点计算出的值与目标值的乘积必然小于等于 0（分类谬误即异号）

$$
\operatorname{sign}\left(w_{t}^{T} x_{n(t)}\right) \neq y_{n(t)} \Leftrightarrow y_{n(t)} w_{t}^{T} x_{n(t)} \leq 0
$$

<center>（公式二）</center>
权重系数更新规定

$$
w_{t}=w_{t-1}+y_{n(t)} x_{n(t)}
$$

<center>（公式三）</center>
由下面的三个公式能够失去指标权重系数与待优化的权重系数的点积的一个下界：

（1）将公式三带入可得

（2）开展后，应用公式一将第二项替换

（3）通过 T 轮更新后，必然大于等于 w0 + T 个最小值

（4）初始的权重系数为零向量

$$
\begin{aligned}
w_{f}^{T} w_{t} &=w_{f}^{T}\left(w_{t-1}+y_{n(t-1)} x_{n(t-1)}\right) \\
& \geq w_{f}^{T} w_{t-1}+\min _{n} y_{n} w_{f}^{T} x_{n} \\
& \geq \ldots \\
& \geq w_{0}+T \cdot \min _{n} y_{n} w_{f}^{T} x_{n} \\
& \geq T \cdot \min _{n} y_{n} w_{f}^{T} x_{n}
\end{aligned}
$$

由下面的三个公式能够失去待优化的权重系数模的平方的一个上界：

（1）将公式三带入可得

（2）开展平形式

（3）两头一项由公式二可知必然小于等于 0，所以能够化简

（4）因为目标值 y 只有 +1 与 -1，所以平方必然为 1，每一个数据点模的平方必然小于等于最大的数据点模的平方

（5）通过 T 轮更新后，必然小于等于 w0 模的平方 + T 个最大的数据点模的平方

（6）初始的权重系数模的平方为 0

$$
\begin{aligned}
\left\|w_{t}\right\|^{2} &=\left\|w_{t-1}+y_{n(t-1)} x_{n(t-1)}\right\|^{2} \\
&=\left\|w_{t-1}\right\|^{2}+2 y_{n(t-1)} w_{t-1}^{T} x_{n(t-1)}+\left\|y_{n(t-1)} x_{n(t-1)}\right\|^{2} \\
& \leq\left\|w_{t-1}\right\|^{2}+0+\left\|y_{n(t-1)} x_{n(t-1)}\right\|^{2} \\
& \leq\left\|w_{t-1}\right\|^{2}+\max _{n}\left\|x_{n}\right\|^{2} \\
& \leq \ldots \\
& \leq\left\|w_{0}\right\|^{2}+T \cdot \max _{n}\left\|x_{n}\right\|^{2} \\
& \leq T \cdot \max _{n}\left\|x_{n}\right\|^{2}
\end{aligned}
$$

由下面两个推导后果可知单位 wf 与单位 w 的点积的下界

（1）带入下面两个推导后果可得

（2）化简提出惟一一个变量

（3）因为第二个乘数外面所有项都是常数且都为负数，所以单位 wf 与单位 w 的点积的下界只与循环次数 T 无关

$$
\begin{aligned}
\frac{w_{f}^{T}}{\left\|w_{f}\right\|} \frac{w_{t}}{\left\|w_{t}\right\|} & \geq \frac{T \cdot \min _{n} y_{n} w_{f}^{T} x_{n}}{\left\|w_{f}\right\| \sqrt{T \cdot \max _{n}\left\|x_{n}\right\|^{2}}} \\
& \geq \sqrt{T} \cdot \frac{\min _{n} y_{n} w_{f}^{T} x_{n}}{\left\|w_{f}\right\| \sqrt{\max _{n}\left\|x_{n}\right\|^{2}}} \\
& \geq \sqrt{T} \cdot \text {常数}
\end{aligned}
$$

由下面的论断可知，当循环次数增大时，点积越大，阐明两个单位向量越靠近。而因为单位向量的点积最大为 1，阐明循环次数 T 存在一个上界，所以算法最初会停下来。

应用 Python 实现 PLA：

import numpy as np

def pla(X, y):
    """
    感知器学习算法实现
    留神：只能解决线性可分的数据集，输出线性不可分的数据集函数将无奈进行
    args:
        X - 训练数据集
        y - 指标标签值
    return:
        w - 权重系数
    """
    done = False
    # 初始化权重系数
    w = np.zeros(X.shape[1])
    # 循环
    while(done == False):
        done = True
        # 遍历训练数据集
        for index in range(len(X)):
            x = X[index]
            # 断定是否与目标值不符
            if x.dot(w) * y[index] <= 0:
                done = False
                # 修改权重系数
                w = w + y[index] * x
    return w

scikit-learn³实现：

from sklearn.linear_model import Perceptron

# 初始化感知器
clf = Perceptron()
# 用随机梯度降落拟合线性模型
clf.fit(X, y)
# 权重系数
w = clf.coef_

简略训练数据集分类：

简单训练数据集分类：

https://zh.wikipedia.org/wiki…
https://zh.wikipedia.org/wiki…
https://scikit-learn.org/stab…

残缺演示请点击这里

注：本文力求精确并通俗易懂，但因为笔者也是初学者，程度无限，如文中存在谬误或脱漏之处，恳请读者通过留言的形式批评指正
本文首发于微信公众号——AI 导图，欢送关注！

关于机器学习:机器学习算法系列一-感知器学习算法PLA

一、引言

二、模型介绍

三、算法步骤

四、原理证实

五、代码实现

六、第三方库实现

七、动画演示

八、思维导图

九、参考文献