机器学习算法—感知机

感知机Perceptron

导读

感知机是二分类的线性分类模型，输入是实例的特征向量（每个属性），输出是实例的类别。感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。

目的：找出将训练数据进行线性划分的分离超平面
导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求出最小值
有原始形式和对偶形式两种
感知机是种线性分类模型，属于判别模型。

应用实例

比如说我们有一个坐标轴（图中的黑色线），横的为x1轴，竖的x2轴。图中的每一个点都是由（x1，x2）决定的。

如果我们将这张图应用在判断零件是否合格上，x1表示零件长度，x2表示零件质量，坐标轴表示零件的均值长度和均值重量，并且蓝色的为合格产品，黄色为劣质产品，需要剔除。

那么很显然如果零件的长度和重量都大于均值，说明这个零件是合格的。也就是在第一象限的所有蓝色点。反之如果两项都小于均值，就是劣质的，比如在第三象限的黄色点。

在预测上很简单，拿到一个新的零件，我们测出它的长度x1，质量x2，如果两项都大于均值，说明零件合格。这就是我们人的人工智能。

image.png

定义

现在假设输入空间是 $X\subseteq{R^n}$ ，输出空间 $Y=\{+1, -1\}$ 。输入 $x\in X$ 表示实例的特征向量，输出 $y\in Y$ 表示实例的类别，其中输入到输出的函数表示如下： $f(x)=sign(w.x+b)$ ，称为感知机

w，b称为感知机模型参数；w称为权值或者权值向量； $b\in R$ 称为偏置bias。 $w \bullet x$ 表示二者的内机，sign表示符号函数：
$sign(x)= \begin{cases} +1, & {x \geq 0} \\ -1, & {x \leq 0} \end{cases}$

感知机的几何解释为线性方程： $w \bullet x+b=0$ 这条直线就是最好的那条线，最优解。特征空间 $R^n$ 对应一个超平面S，其中w是超平面的法向量，b是超平面的截距。超平面将特征空间划分为两个部分。位于两部分的点分为正负两个类别。正类为+1，父类为-1。

栗子（图2.1）：

image.png

策略

给定一个数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 其中 $x_i$ 是输入空间实例的特征向量， $y_i$ 是实例的输出类别，如果存在超平面S满足将数据集的正负实例完全分开，即满足：当 $w.x_i+b>0$ ,有 $y_i=+1$ ；当 $w.x_i+b<0$ ,有 $y_i=-1$ 。此时，将所有的数据分为线性可分数据集，否则称为线性不可分。

感知机中的损失函数误分类点到超平面S的总距离，输入空间中任意一个点 $x_0$ 到距离是 $\frac{1}{||w||}{(w.x_0+b)}$ ，其中||w||表示w的 $L_2$ 范数，即： $||w||=\sqrt{w_1^2+w_2^2+...+w_n^2}$ 对于误分类的点，总有如下结论： $-y_i(w.x_i+b)>0$ 因为在误分类的时候，每个实例点满足：当 $w.x_i+b>0$ ,有 $y_i=-1$ ；当 $w.x_i+b<0$ ,有 $y_i=+1$ 。因此，误分类的点到超平面的距离： $-\frac{1}{||w||}{y_i}{(w.x_0+b)}$ ，假设超平面中的所有误分类的集合M，所有误分类的点到S的总距离为： $-\frac{1}{||w||}\sum_{x_i \in M}{y_i}{(w.x_0+b)}$ ，不考虑 $-\frac{1}{||w||}$ 得到了感知机 $f(x)=sign(w.x+b)$ 的损失函数为： $L(w,b)=\sum_{x_i \in M}{y_i}{(w.x_0+b)}$
M是误分类点的集合
损失函数就是感知机学习的经验风险函数
梯度只是向量，代表下降的方向
通过学习率来控制下降的大小
如果没有误分类点，损失函数是0
误分类点越少，总距离越小，损失函数越小
L是参数(w,b)的连续可导函数

算法

原始形式

算法思想

感知机学习算法的最优化问题就是求解损失函数的最小值，即： $\mathop {\min \limits_{w,b}L(w,b)}=\sum_{x_i \in M}{y_i}{(w.x_0+b)}$ 。感知机的算法是误分类驱动的，具体采用的是随机梯度下降法(stochastic gradient descent)，大致过程如下：

选取任意的超平面 $w_0,b_0$
利用梯度下降方法去不断地极小化目标损失函数L(w, b)
在不断极小化的过程中，不是一次性使用M中所有误分类点进行梯度下降，而是一次随机选取一个误分类点进行梯度下降。
损失函数 $L(w, b)$ 的梯度由如下的式子决定： $\nabla_wL{(w,b)}=-\sum_{x_i \in M}{y_ix_i}$
$\nabla_bL{(w,b)}=-\sum_{x_i \in M}{y_i}$
每次随机选取一个误分类点 $(x_i, y_i)$ ，对 $w, b$ 进行更新： $w\gets{w+\eta{y_ix_i}}$ $b\gets{b+\eta{y_i}}$ 其中 $\eta\in{(0,1]}$ 表示学习率或者步长。通过不断地迭代损失函数 $L(w,b)$ 使其不断的减小，直至为0

算法描述

输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中 $x_i\in X=R^n$ , $y_i \in Y=\{-1, +1\}, i=1,2,....,N$ ；学习率 $0 < \eta \leq 1$

输出：w,b；感知机模型 $f(x)=sign(w.x+b)$

选取初值 $w_0,b_0$ ，一般是0
在训练集中选取数据 $(x_i,y_i)$
如果存在误分类点，即满足： $-y_i(w.x_i+b)\geq {0}$ 或者 $y_i(w.x_i+b)\leq {0}$ ，进行 $(w,b)$ 的更新： $w\gets{w+\eta{y_ix_i}}$ $b\gets{b+\eta{y_i}}$
转到第二步，直至训练集中没有误分类点停止

直观解释：当有一个误分类点在超平面的错误一侧，调整w,b的值，使得分离超平面向着该误分类点的一侧移动，从而较小误分类点和超平面的距离，直至超平面越过该点，使其被正确地分类

栗子（2.1）：

image.png

对偶形式：

算法思想

对偶形式的基本思想是将w,b表示为实例 $x_i$ 和输出类别 $y_i$ 的线性组合的形式，通过求解系数从而求得w和b。

假设 $w,b$ 的初值是都是0，对于误分类点通过： $w\gets{w+\eta{y_ix_i}}$ $b\gets{b+\eta{y_i}}$ 逐步地去修改 $w,b$ ，设修改n次，则 $w,b$ 关于 $(x_i,y_i)$ 的增量分别是 $\alpha _iy_ix_i$ 和 $\alpha_iy_i$ ，其中 $\alpha_i=n_i\eta$ ，通过不断地迭代过程，最终学习到的 $w,b$ 分别表示为： $w=\sum _{i=1}^{N}\alpha _iy_ix_i$ $b=\sum _{i=1}^{N}\alpha _iy_i$

在上面两个迭代式子中， $\alpha_i \geq{0}, i=1,2,....N$ ；当 $\eta=1$ 时，表示第i个实例点由于误分类而进行更新的次数。

算法描述

输入：给定线性可分的训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中 $x_i\in X=R^n$ , $y_i \in Y=\{-1, +1\}, i=1,2,....,N$ ；学习率 $0 < \eta \leq 1$

输出： $\alpha, b$ ；感知机模型 $f(x)=sign(\sum _{j=1}^{N}{\alpha_jy_jx_j}.x+b)$ 其中， $\alpha=(\alpha_1,....,\alpha_N)^T$ ；训练过程为：

1.给定初值 $\alpha \gets 0,b\gets0$

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

3.如果 $y_i(\sum _{j=1}^{N}{\alpha_jy_jx_j}.x+b)\leq 0$ ，进行 $(w,b)$ 的更新： $\alpha \gets{\alpha_i+\eta}$ $b\gets{b+\eta{y_i}}$
4.转到第二步，直至训练集中没有误分类点停止

对偶形式中训练实例仅仅是以内积的形式出现，著名的Gram矩阵 $G=[x_i\bullet y_i]_{N\times N}$

栗子（2.2）：

image.png

算法收敛性

对于原始形式的感知机学习算法，经过有限次迭代之后可以得到一个将训练数据集完全分离的超平面和感知机模型。为了证明过程方便，将偏置b加入权重w中，记作 $\hat w=(w^T,b)^T$ ，同样的输入向量中也加入常数1，记作 $\hat x=(x^T, 1)^T$ 。显然有: $\hat x \in R^{n+1}，\hat w \in R ^{n+1}$ ，则 $\hat w \bullet \hat x=w \bullet x+b$ ，具体证明过程如下图：

image.png