# 感知器：线性二分类模型

旨在求出将训练集进行线性划分的超平面。主要是误分类的损失函数，和利用随机梯度(SGD)下降来最小化损失函数。

**感知器 python 实现：** 点击 [这里](https://github.com/TryFire/Machine-Learning-Algos-theory-and-implementation/blob/master/Perceptron/perceptron.py)

**定义**：给定数据集 $(x_1,y_1),\dots,(x_i,y_i),\dots,(x_N,y_N),x_i \in \mathbb{R^n}, y_i \in \{-1,1\}$， $x_i$ 代表第 $i$ 个样本的特征向量，$y_i$ 代表第 $i$ 个样本的标签，那么感知器为：
$$
f(x) = \text{sign}(w^Tx + b)
$$
其中 $w \in \mathbb{R^n}, b \in \mathbb{R}$.

判定函数：
$$
\text{sign}(x) = \left \{ \begin{aligned}
1 & & x \geq 0 \\
-1 & & x < 0
\end{aligned}
\right.
$$
对于感知器，线性方程：
$$
w^Tx+b=0
$$
是对于输入特征空间 $\mathbb{R^n}$ 中的一个超平面，其中 $w$ 是该超平面的法向量，$b$ 是超平面的截距。

- 对 $w$ 是该**超平面法向量**的理解：假设有一个平面 $s$，对 $s$ 上任意的 向量 $x$ ，都存在 一个向量 $w$ 都有 $w^Tx=0$， 那么次向量就是该平面的法向量（垂直于该平面的向量）。垂直于该平面的单位法向量就是 $\frac{w}{||w||}$.

- 对$b$ 是该**超平面的截距**的理解：截距就是原点到该超平面的距离，设为 $h$ 。假设数据集是二维的，如图： 该超平面与 $x^{(1)}$ 轴的交点假设为 $x_1$，与 $x^{(2)}$ 轴的交点假设为 $x_2$，那么根据三角形面积：
$$
\begin{aligned}
& x_1^T x_2 = \sqrt{||x_1||^2 + ||x_2||^2} * h \\
& w^T x_1 + b = 0 \\
& w^T x_2 + b = 0 \\
& \text{可以得出：}
h = -\frac{b}{||w||}
\end{aligned}
$$

- **任意一点 $x$ 到超平面的距离**：任意一点 $x$ 到该超平面的投影点为 $x_0$ ，满足($w^Tx_0+b = 0$)，则点$x$ 到该超平面的距离为：
$$
|\frac{w}{||w||}*(x-x_0)| = |\frac{1}{||w||}(w^Tx - w^Tx_0)| = \frac{1}{||w||}|w^Tx + b|
$$

### 学习策略

感知器的损失函数不是误分类点的总数，因为它不是$w,b$ 的连续可导函数，所以感知器采用的损失函数是**误分类点到超平面的距离**。假设$x_i$ 是误分类点，那么$w^Tx_i +b > 0, y_i=-1$或者$w^Tx_i+b<0,y_i=1$，则
$$
-y_i(w^Tx_i+b)>0
$$
所以此误分类点$x_i$到超平面的距离为
$$
\frac{1}{||w||}|w^Tx_i+b| = -\frac{1}{||w||}y_i(w^Tx_i+b)
$$
假设集合$M = \{\dots,x_j,\dots\}$ 是所以误分类点的集合，那么感知器的损失函数就是所有误分类点到超平面的距离总和（不考虑$\frac{1}{||w||}$）：
$$
L(w,b,y_j) = -\sum_{x_j \in M}y_j(w^Tx_j+b)
$$

### 学习算法

目标是最小化损失函数：
$$
\min L(w,b,y_j) = \min (-\sum_{x_j \in M}y_j(w^Tx_j+b))
$$
可以使用随机梯度下降算法（SGD），损失函数关于$(w,b)$的梯度是：
$$
\begin{aligned}
& \nabla_w L = -\sum_{x_j \in M}x_jy_j \\
& \nabla_b L = -\sum_{x_j \in M}y_j \\
\end{aligned}
$$
每一步随机选择一个误分类的点$(x_i,y_i)$来梯度下降:
$$
\begin{aligned}
& w^{\text{new}} = w^{\text{old}} + \eta x_iy_i \\
& b^{\text{new}} = b^{\text{old}} + \eta y_i \\
\end{aligned}
$$
其中 $\eta$ 是学习速率(learning rate)。

重复 SGD 直到没有误分类的点。

### 对偶形式

对偶形式是通过每个样本对$(w,b)$的线性组合形式来求解$(w,b)$。我们可以用每个样本$(x_i,y_i)$对$(w,b)$的 更新次数来表示$(w,b)$：
$$
\begin{aligned}
& w^{\text{end}} = w^{\text{init}} + \sum_{i=1}^{N}n_i \eta x_iy_i \\
& b^{\text{end}} = b^{\text{init}} + \sum_{i=1}^{N}n_i \eta y_i \\
\end{aligned}
$$
其中 $n_i \geq 0$ 是样本$(x_i,y_i)$ 对 $(w,b)$的更新次数。感知器可以表示为：
$$
f(x) = \text{sign} \left((\sum_{i=1}^{N}n_i \eta x_iy_i)x + b \right)
$$
其中参数就是$n_i=0,i \in [1,N]$，其初始化值为$0$，因为训练开始前没有任何的样本对$(w,b)$进行更新。对任意误分类样本$(x_i,y_i)$，满足$\left((\sum_{i=1}^{N}n_i \eta x_iy_i)x + b \right)y_i <= 0$，更新策略可以表示为:
$$
\begin{aligned}
& n_i^{\text{new}} = n_i^{\text{old}} + 1 \\
& b^{\text{new}} = b^{\text{old}} + \eta y_i \\
\end{aligned}
$$
我们同样可以用SDG随机选择一个误分类点对$n_i$进行更新，直到没有误分类点。

### 收敛性证明

算法收敛代表存在有限次数的更新，而找到一个超平面可以正确分类所有的样本。我们试着找到这个更新次数 $k$。以下用$w$代表$[w^T,b]^T$，对应的$x = [x,1]$。存在这样的超平面代表存在$w_o$ 满足：
$$
w_o x_iy_i \geq \gamma，\forall (x_i,y_i)
$$
其中 $\gamma$ 为所有点到超平面最短的距离。

假设找到可以正确分类所以样本的超平面的最后一次更新为$k$，对应的误分类样本为$(x_i,y_i)$，满足$w^{k-1}x_iy_i \leq 0$那么$w^k = w^{k-1} + \eta x_iy_i$。那么：

$$
\begin{aligned}
w_o w^k &= w_o(w^{k-1} + \eta x_iy_i) \\
&=w_ow^{k-1} + w_o \eta x_iy_i \\
&\geq w_ow^{k-1} + \eta \gamma \\
& \dots (递归可得) \\
& \geq k \eta \gamma
\end{aligned}
$$
假设 $Q = \max_{i \in [1,N]}{||x_i||}$，我们有以下公式：

$$
\begin{aligned}
||w^k||^2 &= (w^{k-1} + \eta x_iy_i)^2 \\
&= ||w^{k-1}||^2 + 2w^{k-1}\eta x_iy_i + (\eta x_iy_i)^2 \\
&\leq ||w^{k-1}||^2 + (\eta x_iy_i)^2 \ (因为(x_i,y_i)是第k步的误分类点，所以：w^{k-1}\eta x_iy_i \leq 0)\\
& \leq ||w^{k-1}||^2 + (\eta Q)^2 \ (因为Q = \max_{i \in [1,N]}{||x_i||})\\
& \dots (递归可得) \\
& \leq k (\eta Q)^2
\end{aligned}
$$
对于$w_o$ ，其超平面为$w_o x = 0$，那么 $\frac{w_ox}{z } \geq \frac{0} z \geq 0, \text{or} \ \frac{w_ox}{z } < \frac{0} z < 0, \forall z > 0$。这代表我们可以对$w_o$ 进行任意缩放而不影响分类结果。所以我们可以对 $w_o$进行缩放而得到 $||w_o|| = 1$。所以我们有：
$$
\begin{aligned}
& k \eta \gamma \leq w_o w^k \leq ||w_o||*||w^k|| =||w^k|| \leq \sqrt k \eta Q \\
& k\gamma \leq \sqrt k Q\\
& k \leq \frac{Q^2}{\gamma^2}
\end{aligned}
$$
因为$\gamma\neq 0, Q \neq \infty$，所以$k$ 是有上界的，代表我们可以经过有限次数更新找到可以正确分类所有样本的超平面。