2020深度学习—感知机(2)

machine_learning.jpg

感知器算法(Perceptron Algorithm)

随机选择 $W$ 和 $b$
取一个训练样本
- 若 $W^TX + b > 0$ 且 $y=-1$ 则 $W = W -X\,b=b-1$
- 若 $W^TX + b < 0$ 且 $y=+1$ 则 $W = W -X\,b=b+1$
再取另一个 $(X,y)$ 回到(2)
终止条件: 直到所有输入输出对都不满足(2)中(i)和(ii)之一，退出循环

SVM 与神经网

SVM 适合处理小样本，而感知机特别是后来神经网络需要的大数据。神经网模型没有 SVM 那么美，也没有 SVM 那么严谨。

SVM 首先将 X 和 y 全部输入到模型，然后所有样本来建立一个很大优化问题，然后再去解这个优化的问题。以全局眼光来看所有样本来做这件事。感知器与 SVM 最大不同就是感知器一批一批接收样本然后不断地优化参数来实现模型训练。

而感知机，每次只看一部分模型，然后进行学习更新参数，最后看看结果怎么样，如果结果不算好，继续投入样本进行学习更新参数。这样学习过程更加符合我们人类实际情况。

$W^TX + b > 0$ 的情况下会将 y 分类到 +1 所以也就是说明目前的 $W^TX + b$ 不能对 X 正确分类，所以接下来做了 $W = W -X\,b=b-1$ 来更新参数
$\begin{aligned} W_{new}^TX + b_{new}\\ = (W - X)^TX + (b-1)\\ = (W^TX + b) -(||X||^2 + 1) \end{aligned}$

那么我们想一下，现在我们希望将 $W^TX + b$ 向负方向移动，那么移动距离就是 $(||X||^2 + 1)$

$W^TX + b < 0$ 的情况下会将 y 分类到 -1 所以也就是说明目前的 $W^TX + b$ 不能对 X 正确分类，所以接下来做了 $W = W + X\,b=b+1$ 来更新参数

这里存在一个问题，经过反复调整也不会停止情况，如果数据是线性可分，经过调整最终调整会停止下来。但是感知机分开效果没有 SVM 那么好。

定义一个增广向量 $\vec{X}$ ,若 $y=+1$ 则 $\vec{X} = \begin{bmatrix} X & 1 \end{bmatrix}^T$ ，若 $y=-1$ 则 $\vec{X} = \begin{bmatrix} -X & -1 \end{bmatrix}^T$ ，所谓增广就是给 X 增加一个维度。这样写方便，增广的 W 如下 $W = \begin{bmatrix} W & b \end{bmatrix}^T$ 我们可以用增广的 $\vec{X}$ 和 $W$ 来打入上式

输入 $\vec{X_i}$
随机选择 W
取一个训练样本
- 若 $W^T\vec{X_i} < 0$ 则 $W=W+ \vec{X_i}$
再取另一个 $(X,y)$ 回到(2)
终止条件: 直到所有输入输出对都不满足(2)中(i)和(ii)之一，退出循环。现在我们用 $W^T\vec{X_i} < 0$ 替换掉上面两个不等式。现在找 $W$ 使满足 $W^T\vec{X_i} \ge 0$

感知器算法收敛算法定理

输入增广向量 $\{ \vec{X_i} \}_{i=1-N}$ 若线性可分，即存在 $W_{opt}$ 使 $W_{opt}^T\vec{X_i} > 0$ 则利用上述感知器算法，经过有限步得到一个 $W$ ，使 $W\vec{X_i} > 0 \,$

证明: 不失一般性，设 $||W_{opt}||=1$ , 这样做的原因是 $W_{opt}$ 也 $a W_{opt}$ 是同一个平面，所以可以用 a 参数对其进行调整，假设第 k 步的 $W$ 是 $W_k$ , 且有一个 $\vec{X_i}$ 使 $W_k^T \vec{X_i} < 0$ ,根据感知机算法:

$\begin{aligned} W_{k+1} = W_k + \vec{X_i} \\ W_{k+1} - a W_{opt} = W_k + \vec{X_i} - a W_{opt} \\ ||W_{k+1} - a W_{opt}||^2 = ||W_k + \vec{X_i} - a W_{opt}||^2 \\ ||W_{k+1} - a W_{opt}||^2 = ||(W_k - a W_{opt})+ \vec{X_i} ||^2 \\ = ||(W_k - a W_{opt})||^2 + ||\vec{X_i} ||^2 + 2 W_k\vec{X_i} - 2aW_{opt}^T\vec{X_i} \end{aligned}$

既然存在 $aW_{opt}$ 存在，而根据上面假设则有 $aW_{opt}^T\vec{X_i} > 0$ $W_k\vec{X_i}$ 一定可以取很大 a 使得 $||(W_{k+1} - a W_{opt})||^2 < ||W_k - a W_{opt}||^2$ 然后经过不断迭代都会使 $W_{k+1}$ 到 $W_{opt}$ 距离变小。

定义一个 $\beta = \max_{i=1-N}\{||\vec{X_i}||\}$ 定义一个 $\gamma = \min_{i=1-N}(W_{opt^T}X_i)$ 如果取 $a = \frac{\beta^2 +1}{2 \gamma}$ 则
$||(W_{k+1} - a W_{opt})||^2 < ||W_k - a_{opt}||^2 - 1$