感知机——二类分类的线性分类模型

特点

1. 导入基于误分类的损失函数
2. 利用梯度下降法对损失函数进行极小化
3. 求出将训练数据进行线性划分的分离超平面

重要概念表

定位	重要概念	符号	公式	解释
2.2节	误分类点			就是分类错误的点
2.3节	步长（学习率）	$\eta$		用于更新权值$w$和偏置$b$
2.2节	$L_2$范数	$		w
2.1节	权值	$w$	$f(x)=sign(w\cdot x+b)$	超平面的法向量
2.1节	偏置	$b$	$f(x)=sign(w\cdot x+b)$	超平面的截距

2.1 感知机模型

感知机通过函数：

$f(x)=sign(w\cdot x+b)$

来表示输入$x$到输出$f(x)$的关系。

其中：

1.符号函数：

$sign=\left { \begin{aligned} +1,x\ge 0 \ -1,x<0 \end{aligned} \right.$

2.w和x是内积，b是偏置

因此，感知机的意义是，输入一个 x ，通过感知机就能得到它的结果是 -1 或 1，很明显可以用于分类。

补充：

• 把线性方程$w\cdot x+b=0$ 看作是一个超平面，则$w$是超平面的法向量，$b$ 是超平面的截距
• 分类特点：超平面将特征空间划分为两个部分，位于两部分的点分别被分为正负两类

---

2.2 感知机学习策略

【什么叫可以线性可分？】

也就是说，存在超平面，能把数据集的正负实例点完全划分开。

【反过来，用超平面是否能分割数据集，定义该数据集是不是线性可分】

学习策略：

• 定义一个经验损失函数——误分类点到超平面的总距离
• 将损失函数极小化

【怎么选一个好的损失函数？】

此处选择的是——误分类点到超平面的总距离。显然，距离越大，说明误差越大。

感知机$sign(w\cdot x+b)$的损失函数是：

$L(w,b)=-\Sigma_{(x_i\in M)}y_i(w\cdot x_i+b)$

值得注意的是 $y_i$ 只能是1或者-1，由于$y=-1$的存在，在梯度下降算法的过程中（2.3节），才会出现权重或者偏置减小的情况。

【简单分析一下这个损失函数的功效】

如果一个点 x 被误分类，就两种情况：

$w\cdot x_i+b>0$，但是$y_i<0$

$w\cdot x_i+b<0$，但是$y_i>0$

那么这些点都满足$-y_i(w\cdot x_i+b)>0$，多一个误分类点，上面公式中的总和就会大一点，少一个误分类点，总和就会小一点。

---

2.3 感知机学习算法

求解损失函数的最优化问题——随机梯度下降法（SGD：stochastic gradient descent）

1. 先任取权值$w_0$和偏置$b$，也就是选了一个任意超平面
2. 取一个数据，判断一下$y_i(w\cdot x_i+b)$和 0 的关系
3. 如果$y_i(w\cdot x_i+b)\leq0$，说明这个点是个误分类点
4. 那么就要调整权值和偏置，然后再到2步选个点计算，直到训练集中没有误分类点

也就是用梯度下降法不断地极小化目标函数（注意：一次只是随机地选取一个误分类点使其梯度下降）

这里面的核心，解决一个问题，【怎么样调整权值和偏置？】

首先，我们要了解损失函数的极小化和损失函数的梯度：

$min_{w,b} L(w,b)=-\Sigma_{(x_i\in M)} {y_i (w\cdot x+b)}\Longrightarrow \begin{cases} \Delta_w L(w,b)=-\Sigma_{(x_i\in M)} y_i x_i \ \Delta_b L(w,b)= -\Sigma_{(x_i\in M)}y_i \end{cases}$

我们希望的就是损失函数小，那么损失函数的梯度就可以用来调整权值和偏置了：

$w+\eta y_ix_i \to w$

$b+\eta y_i \to b$

其中：步长 $\eta$ (学习率)，对w和b进行更新。

【最后一个问题】

采用不同的初值或者选取不同的误分类点，解可以不同。

【那么一定有解吗？】

一定有解，但是证明比较长，直接看书吧。

其他：文中还讲了原始形式和对偶形式。

PS：对偶形式中，使用了Gram矩阵，也就是《矩阵理论与应用》（研究生教材）中基的度量矩阵