第2章 感知机

2.1 感知机模型

$$
f(x)=sign(w\cdot x+b),\ sign(x)=\begin{cases}+1,x\ge0\-1,x\lt0\end{cases}
$$

对于特征空间$\mathbf{R}^n$中的一个超平面$S$，其中$w$是超平面的法向量，$b$是超平面的截距。

2.2 感知机学习策略

• 数据集的线性可分性
• 损失函数是参数$w$和$b$连续可导函数：点到超平面的距离 $\frac{1}{|w|}|w\cdot x_i+b|$
• 误分类数据满足：$-y_i(w\cdot x_i+b)\gt0$，$y(w\cdot x+b)$称为样本点的函数间隔

2.3 感知机学习算法

原始形式

输入：数据集、学习率$\eta\ (0\lt\eta\le1)$
输出：$w,b,f(x)=sign(w\cdot x+b)$

1. 选取初始值$w_0,b_0$

2. 在训练集中选取数据$(x_i,y_i)$

3. 如果$y_i(w\cdot x_i+b)\le0$

   $$w\leftarrow w+\eta y_i x_i\
   b\leftarrow b+\eta y_i$$

4. 转至2，直到无误分类点

首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数，在一个过程中一次随机选取一个误分类点使其梯度下降。

Novikoff定理

1. $\exists:y_i(\hat{W}{opt}\cdot\hat{x}i)=y_i(W{opt}\cdot x_i+b{opt})\ge\gamma,|\hat{W}_{opt}|=1$

2. 在训练集上的误分类次数$k$满足不等式：$k\le(\frac{R}{\gamma})^2,R=\max_{1\le i\le N}|\hat{x}_i|^2$

说明误分类有上界；训练集可分时，原始形式收敛，不可分时，不收敛；2可以近似看成线段划分，即特征空间最多可以划分成K个。

当训练集可分时，感知机学习算法存在无穷多解，由于不同的初始值或不同的迭代顺序而有所不同。

对偶形式

输入：数据集、学习率$\eta\ (0\lt\eta\le1)$
输出：$\alpha,b,f(x)=sign(\sum_{j=1}^N\alpha_j y_j x_j\cdot x+b)$

1. 选取初始值$a\leftarrow0,b\leftarrow0$

2. 在训练集中选取数据$(x_i,y_i)$

3. 如果$y_i(\sum_{j=1}^N\alpha_j y_j x_j\cdot x_i+b)\le0$

$$\alpha_i\leftarrow\alpha_i+\eta\
b\leftarrow b+\eta y_i$$

4. 转至2，直到无误分类点

基本思想：将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合，通过求解其系数而得到$w$和$b$。实例点更新次数越多，意味着它距离分类超平面越近，也就越难正确分类。对偶形式中训练实例仅以內积$x_j\cdot x_i$的形式出现（Gram矩阵）。

习题

1. 为什么感知机不能表示异或

2. 样本集线性可分的充要条件是正实例点击所构成的凸壳$^1$与负实例所构成的凸壳互不相交

$^1$设集合$S\subset\mathbf{R}^n$是由$\mathbf{R}^n$中的$k$个点组成的集合，即$S={x_1,x_2,\cdots,x_k}$ 定义$S$的凸壳$conv(S)$为：
$$
conv(S)=\left{x=\sum_{i=1}^k{\lambda_i x_i}\mid\sum_{i=1}^k{\lambda_i=1},\lambda_i\ge0,i=1,2,\cdots,k\right}
$$
最小凸多边形、点集合的边界所围成的区域、点集的线性组合