1. 感知机模型及其学习策略

• 感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。其模型函数为：$f(x)=sign(w·x+b)$，其中，$w$为权值向量，$b$为偏置。$sign(x)=\begin{cases} +1, \geq 0 \ -1, <0\end{cases}$

• $w·x+b=0$对应特征空间的超平面，$w$是超平面的法向量，$b$是超平面的截距，这个超平面将特征空间划分为两部分。

• 若数据集$T={(x_1,y_1),(x_2,y_2),…(x_i,y_i)}$，$y={+1,-1}$，存在一个超平面$w·x+b=0$，能够将数据集的正实例点和负实例点完全正确的划分到超平面的两侧，即对所有$y_i=+1$，有$w·x+b>0$，对所有$y_i=-1$，有$w·x+b<0$，则称该数据集为线性可分数据集，否则为线性不可分。

• 感知机模型中，所有误分类点$x_i$到超平面的距离是：

$$
-\frac{1}{||w||}\sum_{x_i\in M}y_i(w·x_i+b)
$$

其中$||w||$为$w$的$L_2$范数，M为误分类点的集合，不考虑$-\frac{1}{||w||}$，就得到感知机$sign(w·x+b)$的损失函数：
$$
L(w,b)=-\sum_{x_i\in M}y_i(w·x_i+b)
$$
误分类的点满足：$y_i(w·x_i+b)$<0

• 感知机的学习算法，就是采用随机梯度下降法，不断极小化损失函数，损失函数的梯度由：

$$
\nabla_w L(w,b)=-\sum_{x_i\in M}y_ix_i
$$

$$
\nabla_b L(w,b)=-\sum_{x_i\in M}y_i
$$

随机选取一个误分类点$(x_i,y_i)$，对$w,b$进行更新：
$$
w\leftarrow w+\eta y_ix_i
$$

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

式中$\eta(0<\eta\leq1)​$是步长，在统计学习中又称为学习率。通过不断迭代，是损失函数不断变小，直到为0.

• 感知机学习算法的对偶形式，$w$可以表示为：
  $$
  w=\sum_{i=1}^{N}a_iy_ix_i
  $$
  $a_i=a_i\eta$，当$\eta=1$时，$a_i$表示第i个实例点由于误分而进行更新的次数。

  感知机模型则表示为：$f(x)=sign(\sum_{i=1}^N a_iy_ix_i·x+b)$

  随机选取一个误分类点$(x_i,y_i)$，则：$a_i \leftarrow a_i+\eta$ ， $b\leftarrow b+\eta y_i$

对偶形式中，可以预处理训练集中实例间的内积并以矩阵存储，该矩阵即 Gram 矩阵(Gram matrix) ：
$$
G=\left[ x_i·x_y\right]_{N*N}
$$

2. 章后习题

2.1 习题1

异或点关系为(0,0)=(1,1)=0；(1,0)=(0,1)=1，即$\begin{bmatrix} 1 & 0 \0 & 1 \ \end{bmatrix} $ ，这种情况下是无法使用一条直线将0,1进行区分的，也就是说异或的数据集线性不可分，所以感知机不能表示异或。

3. 总结

感知机是一个二分类线性模型，感知机的学习过程，就是寻找一个超平面，将训练集中的数据进行二分类的过程。这个超平面存在多个解，求解的过程就是使用误差集，最小化损失函数的过程，可以使用梯度下降法，对$w，b$进行逼近，$\eta$为步长。对偶形式中，$\eta=1$，可以将求$w$转化为求$a_i$的过程。对偶形式中需要用到Gram矩阵。