机器学习 - 感知机(Perceptron)

@Pelom  November 20, 2021

定义

感知机(Perceptron)是二分类的线性分类模型,输入为实例的特征向量,输出为实例的类别
感知机的目的是求得一个能够将正实例点和负实例点完全正确分开的分离超平面

预备知识

  1. 超平面(hyperplane):超平面是$n$维线性空间中维度为$n-1$的子空间,它可以将线性空间分割为不相交的两部分
  2. $\bold{R}^n$:全体$n$维列(行)向量的集合,即$$\bold{R}^n=\{\boldsymbol{\alpha}=(a_1,a_2,\dots,a_n)^{\rm{T}}|a_i\in\mathbb{R},i=1,2,\dots,n\}$$
  3. $\Vert \boldsymbol{x}\Vert$:范数(norm),向量范数表征向量空间中向量的大小,这里用到的是$L_2$范数,即欧氏距离,定义为$$\Vert \boldsymbol{x}\Vert=\sqrt{\sum_{i=1}^n x_i^2}=\sqrt{x_1^2+x_2^2+\dots+x_n^2}$$
  4. 偏导数(partial derivative):对于一个多元函数,关于其中一个变量的导数而保持其他变量恒定
  5. 梯度(gradient):一个向量,函数在该点处沿着该方向(此梯度的方向)变化最快,记作$\nabla$

原理

模型

  1. 给定数据集$T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$
    其中$x_i\in \mathcal{X}=\bold{R}^n,y_i\in \mathcal{Y}=\{+1,-1\},i=1,2,\dots,N$,$x_i$为特征向量,$y_i$为类别,用$\pm 1$分别表示两类
  2. 感知机模型为$f(x)=\mathrm{sign}(w\cdot x_i+b)$
    其中$w^{\rm{T}}\in\bold{R}^n$,$w$称为权值(weight);$b\in\mathbb{R}$,称为偏置(bias
  3. $w$和$b$描述了一个超平面$S:w\cdot x+b=0$
    其中$w$为超平面的法向量,$x$为平面上的点(列向量),$b$为超平面的截距

学习策略

损失函数的选择

感知机最后会学习出一个超平面$S:w\cdot x+b=0$
为了求出这个超平面,需要确定一个损失函数(loss),并将其最小化
要将正负实例完全分开,即使误分类点数为$0$,容易想到以误分类点数为损失函数
但是误分类点数是离散的,不可对$w$,$b$求导,这就会让我们无从下手优化(因为要用梯度下降法)
还有一个选择是误分类点到超平面的总距离,因为最后要无误分类点,也就是总距离为$0$,这也是损失函数的最小值

损失函数的计算

  1. 如何判断一个点被正确分类呢?还记得线性代数中求点到平面距离的公式吗?
    设平面$Ax+By+Cz+D=0$,点$(x_0,y_0,z_0)$
    则$d=\dfrac{Ax_0+By_0+Cz_0+D}{\sqrt{A^2+B^2+C^2}}$
    将其换为法向量的形式,并且点也写成列向量,法向量$w=(A,B,C)$,点$x=(x_0,y_0,z_0)^{\rm{T}}$,记$b=D$
    那么$$d=\dfrac{w\cdot x+b}{\Vert w\Vert}$$
    这个$d$是有向的,其含义为该点与该法向量在平面的同侧($+$)或异侧($-$)
    推广到$n$维的情况,同样有$d=\dfrac{w\cdot x+b}{\Vert w\Vert}$
    因为$\Vert w\Vert$恒为正,可以不看,如果正确分类,那么$w\cdot x_i+b$与$y_i$应该有同样的正负性
    因此误分类点满足$$-y_i(w\cdot x_i+b)>0$$
  2. 记误分类点的集合为$M$,则损失函数为$L(w,b)=\sum\limits_{x_i\in M}\dfrac{|w\cdot x_i+b|}{\Vert w\Vert}$
    同时,因为是误分类点,我们知道$-y_i(w\cdot x_i+b)>0$,可以把绝对值拿掉,所以$L(w,b)=-\dfrac{1}{\Vert w\Vert}\sum\limits_{x_i\in M}y_i(w\cdot x_i+b)$
    因为最终的目标是$L(w,b)=0$,而$\Vert w\Vert$恒为正,所以不用考虑$\dfrac{1}{\Vert w\Vert}$,最终得到$$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

随机梯度下降法(SGD)

  1. 开始时随机选择一组$w,b$,每次选择一个误分类点更新$w,b$,然后重新计算所有误分类点,重复以上过程,直到$L(w,b)=0$
    可见感知机是误分类驱动的
  2. 损失函数下降最快的方向自然是该点梯度的反方向

损失函数的梯度

对损失函数$L(w,b)$求偏导,有

$$ \begin{aligned} &\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i \\ &\nabla_bL(w,b)=-\sum_{x_i\in M}y_i \end{aligned} $$

因为用的是随机梯度下降,若选择的误分类点是$(x_i,y_i)$,则更新时

$$ \begin{aligned} w&\gets w+\eta y_ix_i \\ b&\gets b+\eta y_i \end{aligned} $$

其中$\eta$为学习率(learning rate),取值$(0,1]$

收敛性证明

实现


添加新评论

  1. Terrasse

    O rz

    Reply
  2. Orz

    Reply