感知机
$$
f(x)=sign(w \cdot x + b)
$$
其中，w，b是感知机的模型参数，$w \in R^n$是权值，$ b \in R $是偏置。
$$
sign(x) =
\begin{cases}
+1,&x \ge 0 \
-1, &x \lt 0
\end{cases}
$$
这是一种线性分类模型，属于判别模型。
对它的几何解释：$w \cdot x + b = 0$对应$R^n$中的一个超平面，将特征空间分为两部分；$w$是法向量，$b$是截距。
数据集的线形可分性
设数据集：
$$
T = { (x_1, y_1), \dots, (x_N, y_N)}
$$
如果在$R^n$中，存在$w \cdot x + b = 0$的超平面，将正负实例完全正确地划分到超平面的两侧，则称$T$为线形可分，否则为线型不可分。
对$x_0$的分类
$x_0$到超平面$S$的距离：$\frac{1}{||w||}|w\cdot x_0+b|$，而对于误分类的点，有$y_i(w \cdot x_i + b) \lt 0$。于是误分类的总距离：
$$
-\frac{1}{||w||} \sum\limits_{x_i \in M}y_i(w\cdot w_i + b)
$$
Loss function:
$$
L(w, b) = -\sum\limits_{x_i \in M}y_i(w\cdot w_i + b)
$$
其中$M$是误分类点的集合。
优化过程
$$
\min \limits_{w, b} -\sum\limits_{x_i \in M} y_i(w\cdot x_i + b)
$$
while 存在误分类点:
随机选择误分类点$(x_i, y_i)$
$w$ := $w + \eta y_ix_i$
$b$ := $b + \eta y_i$
Novikoff定理
（1）$\exists || \hat w _{opt} ||= 1$的超平面
$$
\hat w_{opt} \cdot \hat{x} + \hat{b}_{opt} = 0
$$
将线形可分的数据集$T$完全正确地分开；且
$$
\exists \gamma \gt 0, \forall i = 1, 2, \dots, N
$$
，有$y_i(\hat{w}_{opt} \cdot \hat{x}_i) = y_i(w_{opt}\cdot x_i + b_{opt}) \ge \gamma$
（2）令$R = \max \limits_{1 \le i \le N} || \hat{x}_i||$，则感知机算法原始形式在$T$上的误分类次数$k \le \left( \frac{R}{\gamma} \right)^2$
感知机学习算法的对偶形式
感知机模型：$f(x) = sign \left(\sum \limits_{j=1} ^{N} \alpha_j y_j x_j \cdot x + b\right)$，其中$\alpha = (\alpha_1, \alpha_2, \dots, \alpha_n)^T$。
（1）$\alpha := 0, b := 0$
（2）若存在误分类的$(x_i, y_i)$，则$\alpha_i := \alpha_i + \eta$，$b := b + \eta y_i$。
（3）重复（2），直到没有误分类。
证明：样本集$T$线形可分的充要条件是正实例的凸壳与负实例的凸壳互不相交
$S={x_1, x_2, \dots, x_k} \subset R^n$
$S$的凸壳
$$
conv(S) = \left\{ x = \sum\limits_{i=1}^k \lambda_ix_i | \sum\limits_{i=1}^k\lambda_i = 1, \lambda_i \ge 0, i = 1, 2, \dots, k \right\}
$$
证明：分$T$为正实例$T_+$和负实例$T_-$，对应的凸壳分别为$conv(T_+)$和$conv(T_-)$。
(1) 若$T$线形可分，则有超平面$wx+b=0$满足条件。
对于$T_+$中的$x_i$，有
$$
wx_i+b=\epsilon_i \gt 0
$$
对于$conv(T_+)$中的$t_+$，有
$$
wt_++b = \sum\limits_{i=1}^{k} \lambda_i\epsilon_i + b \gt 0
$$
同理，对于$conv(T_-)$中的$t_-$，有$wt_-+b \lt 0$。
显然，同一个式子不能同时大于0和小于0，即以上两式不可能同时成立，即不存在$t_0$使得$t_0 \in conv(T_+) \bigwedge t_0 \in conv(T_-)$，即$conv(T_+) \bigcap conv(T_-) = \emptyset$。
(2)设$||conv(T_+), conv(T_-)|| = \min ||x_+, x_-|| , \forall x_+ \in conv(T_+), \forall x \in conv(T_-)$，并记对应的$x_+, x_-$。
记$w = x_+ - x_-, b = - \frac{x_+ \cdot x_+ - x_- \cdot x_-}{2}$。
易知$T_+ \subseteq conv(T_+)， T_- \subseteq conv(T_-)$。
于是$\forall x_i \in T_+,$
$$
wx_i+b = x_+x_i - x_-x_i - \frac{x_+x_+-x_-x_-}{2} = \frac{||x_–x_i||^2 - ||x_+-x_i||^2}{2}
$$
由于$x_i\in T_+ \subseteq conv(T_+),$
$$
||x_i, x_-|| \gt ||x_i, x_+||
$$
$$
\therefore wx_i+b \gt 0
$$
同理，$\forall x_j \in T_-, wx_j+b \lt 0$
于是，存在超平面$wx+b=0$将$T$正确分开，即$T$线形可分。
证毕。