感知机

感知机是一种二分类的线性分类模型.感知机学习旨在求出将训练数据进行线性划分的分离超平面.

模型定义

假设输入空间(特征空间)是$X \in R^n$,输出空间是$Y={+1,-1}$,输入$x \in X$,对应于输入空间(特征空间)的点,输出$y \in Y$表示实例的类别,由输入空间到输出空间的如下函数$$f(x)=sign(w\cdot x+b)$$称为感知机。其中,w和b为感知器的模型参数,$w \in R^n$叫做权值或者权值向量(weight vector),$b \in R$叫做偏置(bias),$w\cdot x$表示w和x的内积。sign是符号函数,即$$sign(x)=\begin{cases} +1,& \quad x\ge 0 \\ -1,& \quad x<0 \end{cases}$$

几何解释

线下方程$w\cdot x + b = 0$对应于特征空间$R^n$中的一个超平面S,其中w是超平面的法向量,b是超平面的截距,这个超平面将特征空间划分为两个部分。位于两个部分的点(特征向量)分别被分为正负两类。因此,超平面S称为分离超平面(separating hyperplane)

学习策略-损失函数

感知机的损失函数定义为:所有误分类点到超平面S的距离的总和。

在输入空间$R_n$中任取一点$x_0$,该点到平面的距离为:$\frac { \left| w\cdot x_{ 0 }+b \right| }{ \left|\left| \overrightarrow { w } \right|\right| } $。(点到超平面距离公式推导)

对于误分类点($x_i,y_i$)来说:$$-y_{ i }(w\cdot x_{ i }+b)>0$$
因为对于误分类点$w\cdot x_{ 0 }+b >0$时,$y_i<0$,$w\cdot x_{ 0 }+b <0$时$y_i>0$。

假设超平面S点误分类点合集为M,则所有误分类点到超平面S到总距离为:$$ -\frac { 1 }{ \left|\left| \overrightarrow { w } \right|\right| } \sum_{ x_{ i }\in M }^{ }{ y_{ i }(w\cdot x_{ i }+b) } $$

不考虑$$ \frac { 1 }{ \left|\left| \overrightarrow { w } \right|\right| }$$
就得到了感知器的损失函数:$$ L(w,b)=-\sum_{ x_{ i }\in M }^{ }{ y_{ i }(w\cdot x_{ i }+b) } $$

学习算法

输入:训练数据集T={$(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)$},其中$x_{ i }\in X= R^{ n }$,$y_{ i }\in Y={ -1,+1} $,i=1,2,3,…,N;学习率$\eta (0<\eta \le 1)$;
输出:w,b;感知机模型$f(x)=sign(w\cdot x+b)$。
(1)选取初值$w_0b_0$
(2)在训练集中选取数据($x_i,y_i$)
(3)如果$y_{ i }(w\cdot x_{ i }+b)\le 0$,则$$w\leftarrow w+\eta y_{ i }x_{ i }$$ $$b\leftarrow b+\eta y_{ i }$$
(4)转至(2),直至训练集中没有误分类点。
这种学习算法直观上有如下解释:当一个实例点被误分类,即位于分离超平面当错误一侧时,则调整w,b当值,使分离超平面向该误分类点的一侧移动,以减少该误分类点与超平面间点距离,直至超平面越过该误分类点使其被正确分类。

感知机算法的Python实现