线性判别函数

在这一部分将总结一下关于感知机的一些相关知识点，不过首先我想要介绍下统计学习相关算法的一种分类标准。该部分内容将按照以下几部分进行组织：

• 模型分类-生成式模型与判别式模型
• 线性判别-感知机

模型分类-生成式模型与判别模型

监督学习的任务便是学习一个模型，应用这一模型，对给定的输入$X$预测相应的输出$Y$，该模型一般具有两种形式：

• $Y = f(X)$
• $P = (Y|X)$

第一种模型我们称为判别模型，是函数形式；后一种我们称为生成模型，为条件概率分布的形式。下面列一个表格来对常见机器学习算法按照该标准进行分类：

生成式模型	判别式模型
朴素贝叶斯模型,HMM,GMM	感知机,SVM,k近邻,AdaBoost

线性判别-感知机

感知机模型是一种非常简单的判别式模型，该算法出发点有以下几点：

• 二分类问题
• 假设存在一个超平面，可以将两类样本分开，即要求模型线性可分

对于一个判别式模型，我们需要解决三个问题：

1. 明确模型类
2. 确定准则函数
3. 利用准则函数，结合数据进行模型学习

模型类

首先给出感知机函数定义：

假设输入空间(特征空间)是$\mathcal{X} \subseteq R^n$,输出空间是$\mathcal{Y} = {-1,+1}$。输入$x\in \mathcal{X}$表示实例的特征向量，对应于输入空间(特征空间)的点；输出$y \in \mathcal{Y}$表示实例的类别。由输入空间到输出空间的函数可表示为:

$$f(x) = sign(\omega x+ b)$$

感知机是一种线性分类模型，属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类起，即函数集合${ f|f(x) = \omega x + b}$。

准则函数(损失函数)

损失函数的一个自然选择是误分类点个数。但是这样的损失函数不是参数$\omega,b$的连续可导函数，不易优化。损失函数的另一个选择则是误分类点到超平面的总距离，为此先写出输入空间$R^n$中任意一点$x_0$到超平面$S$的距离：

$$d= \frac{|\omega x_0 +b|}{|| \omega ||}$$

其次，对于误分类的数据$(x_i,y_i)$来说:

$$-y_i(\omega \cdot x_i + b) >0$$

因此，误分类点$x_i$到超平面的距离为：

$$\frac{-y_i(\omega x_i +b)}{|| \omega ||}$$

因此，若假设超平面$S$的误分类点集合为$M$,那么所有误分类点到超平面$S$的距离为：

$$L = -\frac{1}{||\omega||} \sum_{x_i \in M} y_i (\omega x_i + b)$$

由此可见，在该目标函数下，若所有样本均被正确分类，则损失函数为0,因此不管是带范数的几何间隔，还是去掉范数的函数间隔，最终都将收敛到0，为计算方便，因此考虑将损失函数中的$||\omega||$去掉，写出目标函数如下：

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

优化算法

在目标函数确定的情况下，对于该问题的优化考虑采用随机梯度下降法(SGD),首先求的目标函数对$\omega, b$的偏导：

$$\begin{aligned} \nabla_{\omega} L(\omega,b) &= -\sum_{x_i \in M}y_i x_i \\\\ \nabla_{b} L(\omega,b) &= -\sum_{x_i \in M} y_i \end{aligned}$$

接下来对参数进行更新:

$$\begin{aligned} \omega &\leftarrow \omega + \eta y_i x_i \\\\ b &\leftarrow b + \eta y_i \end{aligned}$$

感知机算法收敛性

在该部分将给出定理，但不加证明：

设训练数据集是线性可分的，则：

• 存在满足条件$||\omega|| = 1$的超平面将训练数据集完全分开，且存在$\gamma >0$,对所有$i=1,\dots,N$: $$y_i\omega x_i \geq \gamma$$
• 令$R = max ||x_i||$,则感知机算法在训练集上的误分类次数$k$满足不等式: $$k \leq (\frac{R}{\gamma})^2$$

需要注意的是，当数据线性不可分时，感知机算法便不会收敛，当训练集线性可分时，感知机算法存在无穷多个解，其解由于不同的初值或者迭代顺序而可能有所不同