统计学习方法(2)-感知机

作者: breezez | 来源:发表于2019-07-08 10:00 被阅读0次

统计学习方法-2 感知机
统计学习方法(2)-感知机
统计学习方法第二章：感知机(perceptron)算法及pyth
统计学习方法第三章：k近邻法(k-NN),kd树及python实
统计学习方法第五章：决策树(decision tree),CAR
统计学习方法第四章：朴素贝叶斯法(naive Bayes)，贝叶
统计学习方法第五章：决策树(decision tree),ID3
机器学习好网址
统计学习方法笔记(第二章个人笔记)
感知机理论与实践代码

感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别｛-1,1｝，是一种判别模型。感知机学习的目的在于求出将训练数据进行划分的超平面。

感知机模型

输入空间 $X\epsilon R^{n}$ ,输出空间 $\gamma =\left \{ -1,1 \right \}$ 。
$f(x)=sign(w\cdot x+b)$ $x$ 为输入向量，其中， $w$ 和 $b$ 为感知机模型参数， $w\cdot b$ 表示内积，sign是符号函数。感知机的几何角度理解是： $w\cdot x+b=0$ 是特征空间 $R^{n}$ 的一个超平面， $w$ 是该平面的法向量， $b$ 是截距。这个超平面将特征空间划分为正负两个部分，如下图。

感知机学习策略

感知机学习的目的是为了找到能够将正负实例点正确分开的超平面，也就是要确定参数 $w$ 和 $b$ ，感知机的学习策略便是定义一个损失函数并将其最小化。于是便要选择一个损失函数的依据，可以选择误分类的点的数量作为损失函数，然而该函数不可导，不易于优化，因此选择误分类点到超平面的距离和： $\frac{\left | w\cdot x +b \right |}{\left \| w \right \|}$ 此处 ${\left \| w \right \|}$ 是 $w$ 的第二范数。注意需要优化的只是误分类的点，对于误分类的点有， $-y_i(w\cdot x + b)>0$ 恒成立，因此可去掉绝对值符号，并假设当前超平面的误分类的点的集合为M，由此得到感知机学习的损失函数为 $L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$ 其中M为误分类的点的集合。显然该损失函数是非负的，当没有误分类的点时 $L(w,b)=0$ .只需将损失函数优化到0即得到该分类超平面，不过由该方法得到的超平面的解不是唯一的（显然只需要能够正确分类时算法即停止）。

感知机学习算法

感知机所用优化方法是随机梯度下降法，包括原始形式和对偶形式。

原始形式

前面已经确定了感知机的损失函数，那么其原始形式只需要最小化这个损失函数即可。
$\underset{w,b}{min}L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x+b)$ 其中M为误分类的点的集合。
随机梯度下降法初始时任选 $w_0$ , $b_0$ 作为初始超平面，计算有哪些误分类点，如果有误分类点，随机选取一个误分类点，进行梯度下降。即先计算损失函数的梯度
$\begin{aligned} \triangledown _wL(w,b)&=-\sum_{x_i\in M}y_ix_i \\ \triangledown_wL(w,b)&=-\sum_{x_i\in M}y_i \end{aligned}$ 梯度下降法使参数向反方向变化，使用随机选出的误分类点的数据，根据提前设置好的学习率 $\eta$ 对 $w,b$ 进行更新就可以了
$\begin{aligned} w& \leftarrow w+\eta y_ix_i \\ b& \leftarrow b+\eta y_i \end{aligned}$ 这样便可使损失函数不断减小，直到为0时就得到了可正确分类数据集的超平面。

对偶形式

在原始形式的学习算法中，可以看到每次更新 $w,b$ 的数值都是选中的点 $(x_i,y_i)$ 的线性组合，那么 $w,b$ 必然可以用 $(x_i,y_i)$ 线性表示，这样我们可以通过求解该线性组合的系数找到该超平面。对上节 $w,b$ 的更新中，设总共修改N次，可将每次 $w,b$ 增量表示为 $\alpha _iy_ix_i,\alpha _iy_i$ ，其中 $\alpha = n_i\eta$ ，假设 $w_0=b_0=0$ (这无关线性）。于是更新过程表示为
$\begin{aligned} w&=\sum_i\alpha _iy_ix_i\\ b&=\sum_i \alpha _iy_i \end{aligned}$ 这里 $\alpha _i=n_i\eta _i$ 的含义是在该学习率下 $(x_i,y_i)$ 在最后学习到的 $w,b$ 中所贡献的权重，就是最后平面的 $w,b$ 的系数，也是因该点误分类也进行更新的次数* $\eta$ 。由此，感知机模型可由 $\alpha ,b$ 表出。
$f(x)=sign(\sum_j\alpha _jy_j\cdot x + b)$ 在判断是否是误分类点时用
$y_i(\sum _j\alpha _jy_jx_j\cdot x_i + b)\leqslant 0$ 更新时
$\begin{aligned} \alpha _i &\leftarrow \alpha _i +\eta\\ b &\leftarrow b + \eta y_i \end{aligned}$ 可以看到该计算过程中训练数据全部由内积得到，因此可以提前将内积计算出来由矩阵存储，可以减少算法过程中的计算量，这是Gram矩阵。 $G= [x_i \cdot x_j]_{N*N}$

统计学习方法-2 感知机
感知机（perceptron）属于判别模型，是神经网络与SVM的基础。 2.1 感知机模型 2.2 学习策略2.2...
统计学习方法(2)-感知机
感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别｛-1,1｝，是一种判别模型。感知机学习的...
统计学习方法第二章：感知机(perceptron)算法及pyth
统计学习方法第二章：感知机(perceptron)算法及python实现统计学习方法第三章：k近邻法(k-NN),...
统计学习方法第三章：k近邻法(k-NN),kd树及python实
统计学习方法第二章：感知机(perceptron)算法及python实现统计学习方法第三章：k近邻法(k-NN),...
统计学习方法第五章：决策树(decision tree),CAR
统计学习方法第二章：感知机(perceptron)算法及python实现统计学习方法第三章：k近邻法(k-NN),...
统计学习方法第四章：朴素贝叶斯法(naive Bayes)，贝叶
统计学习方法第二章：感知机(perceptron)算法及python实现统计学习方法第三章：k近邻法(k-NN),...
统计学习方法第五章：决策树(decision tree),ID3
统计学习方法第二章：感知机(perceptron)算法及python实现统计学习方法第三章：k近邻法(k-NN),...
机器学习好网址
统计学习方法代码实现最小二乘法感知机最小二乘法
统计学习方法笔记(第二章个人笔记)
统计学习方法笔记(第二章个人笔记) 标签：机器学习深度学习感知机（P25）感知机是神经网络与支持向量机的基础...
感知机理论与实践代码
本文主要参考李航老师的《统计学习方法》第二章感知机感知机(perceptron)是一个二分类的线性分类模型，输入...