空间中有两类线性可分的样本，感知机算法希望找出一条直线（超平面），恰好把这两类点分开。感知机原理很简单，这里研究二维平面的情况，不失一般性。
算法
样本集为 ${x^n}$，其中第 $t$ 个样本点为 $(x^t_1, x^t_2)$，标签为 $y^t$。分类直线用 $\theta = (\theta_0, \theta_1, \theta_2)$ 表示。该直线方程为：
$$
\theta_0 + \theta_1\cdot x_1 + \theta_2\cdot x_2 = 0
$$
为了能用矩阵乘法表示，扩充 $x$，令其第 0 维值为1，即
$$
\theta^T\cdot x = [\theta_0, \theta_1, \theta_2]\cdot\left[
\begin{matrix}
1 \\
x_1 \\
x_2
\end{matrix}
\right]
$$
约定：如果点 $(x^t_1, x^t_2)$ 在直线上方，则 $\theta^T\cdot x$ 大于0，对应的标签 $y^t=+1$，反之 $\theta^T\cdot x$ 小于0，$y^t=-1$。
算法很简单，初始化 $\theta$ 为 0。用 $\theta$ 来分类样本，每遇到一个分类结果与标签不符的样本，则将 $\theta$ 加上该样本向量乘以它的标签（$\theta = \theta + y^t\cdot[1, x_1, x_2]^T$）。
原理如下：
分类错的情况有两种：
$\theta^T\cdot x^t<0$ 但 $y^t = 1$
$\theta^T\cdot x^t>0$ 但 $y^t=-1$
站在向量点乘的角度，第一种情况说明 $\theta$ 与 $x^t$ 的夹角过大，优化目标是减小 $\theta$ 与 $x$ 的夹角，第二种情况则说明 $\theta$ 与 $x^t$ 的夹角过小，优化目标是增大 $\theta$ 与 $x$。针对这两种情况，如果分别用 $\theta$ 加上或减去误分点 $x^t$，则可以减小或增大 $\theta$ 与 $x^t$ 的夹角。因此可以采用 $\theta = \theta + y^t\cdot[1, x_1, x_2]^T$ 来更新 $\theta$。
对应的算法如下图所示：
收敛性证明
如果两类样本线性可分，那么一定存在
$$
\left| \theta^* \right| = 1
$$
使得对任意 $t=1,…,n$
$$
y^t\cdot(\theta^{*T}\cdot x^t) \geq \gamma
$$
对于有限个样本，总能找到一个 $R$ 使得对任意 $t=1,…,n$ 有
$$
\left| x^t \right| \leq R
$$
假设第 $k$ 次更新所使用的样本为 $x^t$，根据更新规则：
$$
\begin{align}
\theta^{k+1}\cdot\theta^* &= (\theta^k+y^t\cdot x^t)^T\cdot \theta^* \\
&= \theta^{kT}\cdot\theta^*+y^t\cdot \theta^{*T}\cdot x^t \\
&\geq \theta^{kT}\cdot\theta^* + \gamma
\end{align}
$$
将 $\theta^1$ 初始化为 0 向量，则有：
$$
\theta^{k+1}\cdot\theta^* \geq k\gamma
$$
而两个向量的点乘一定小于等于它们模的乘积，且已知 $\theta^*$ 的模为1，故：
$$
\left| \theta^{k+1} \right| \geq k\gamma
$$
接下来研究 $\left|\theta^{k+1}\right|$。
$$
\begin{align}
\left| \theta^{k+1} \right|^2 &= (\theta^k+y^t\cdot x^t)^2 \\
&= \left| \theta^k\right|^2+ \left|x^t\right|^2+2y^t(x^{tT}\cdot\theta^k) \\
&\leq \left| \theta^k\right|^2+R^2 \\
&\leq kR^2
\end{align}
$$
因此 $\theta^{k+1}$ 同时满足：
$$
\left| \theta^{k+1} \right| \geq k\gamma
$$
$$
\left| \theta^{k+1} \right|^2 \leq kR^2
$$
也就是：
$$
k^2\gamma^2\leq kR^2
$$
因此
$$
k \leq \frac{R^2}{\gamma^2}
$$
不等号右边即为迭代次数的上限。
示例代码
|
|