0%

《统计学习方法》笔记(二)

[toc]

第二章 感知机

感知机 (perceptron) 是二分类分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别,取+1和-1值。感知机对应于输入空间(特征空间)中将实例划分为正负两类的分离超平面,属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面,为此,导入基于误分类的损失函数,利用梯度下降法对损失函数进行极小化,求得感知机模型

听说感知机应该属于机器学习算法中最简单的一种算法,是一种二分类算法

2.1 感知机模型

​ 类比函数,我们把模型中的自变量叫做输入空间(特征空间),因变量叫做输出空间。所以该模型也是有定义域和值域的。

​ 假设输入空间是$\chi \subseteq R^n$ 输出空间是 y$={+1,-1}$,输入$x\subseteq \chi$表示实例的特征向量,对应于输出空间(特征空间)$y \subseteq $y一个点,由输入空间到输出空间的如下函数:

​ $f(x)=sign(w\cdot x+b)$

​ 成为感知机,其中,$w,b$为感知机模型参数,$w \in R^n$叫做权值(weight)或权值向量(weight vector),$b \in R$叫做偏置(bias),$w \cdot x$表示$w$和$x$的内积,其中sign是符号函数,即:

​ $\begin{equation} sign(x)= \begin{cases} +1 & x \ge 0\ -1& \text{x<0} \end{cases} \end{equation}$

​ 感知机有它的几何解释,在比如二维直角坐标系中$wx+b=0$ 对应的特征空间是一个二维平面,其中w是这个平面的斜率,b是平面的截距,$wx+b$就是一条直线,在直线左侧上方就是-1,在直线右侧就是+1.

​ 推广到三维时,$wx+b$就是一个平面,平面的一侧时+1,另一侧是-1。推广到n维空间,$wx+b$就是n维空间的超平面,其中w是超平面的法向量,b是超平面的截距,这个超平面将特征空间分为两部分,位于两部分的点分别问+1和-1。

2.2 感知机学习策略

2.2.1 数据集的线性可分性

给定一个数据集:

$T={(x_1,y_1),(x_2,y_2),…,(x_n,y_n)}$

其中,$x_i \in \chi = R^n,y_i \in {+1,-1},i=1,2,…,N$,如果存在某个超平面S能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧,即对所有的$y_i=+1$的实例$i$,有$w\cdot x+b\ge0 $,对所有的$y_i=-1$的实例$i$,有$w\cdot x+b<0 $,则称数据集$T$为线性可分数据集(linearly separable data set),否则,称数据集T线性不可分。

2.2.2 感知机学习策略

​ 假设训练数据是线性可分的,感知机的目标就是要求得一个能够将训练集所有的点完全正确分开的分离超平面。为了确定参数$w,b$,需要确定一个学习策略,定义一个损失函数,并将损失函数极小化。

​ 首先写出输入空间 R n 中任一点 $x_0$ 到超平面 S 的距离:

​ $\frac{1}{\parallel w\parallel}\mid w\cdot x_0+b\mid$

这里$\parallel w\parallel$是$w$的$L_2$范数

​ $\parallel w\parallel=\sqrt{\sum_{i=1}^{n}(w_i)^2}$

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

$-y_i(w\cdot x_i+b)>0$ 成立。因为当$w\cdot x_i+b>0$时,$y_i=-1$;而当

$w\cdot x_i+b<0$时,$y_i=+1$。因此,误分类点$x_i$到超平面的距离是

​ $-\frac{1}{\parallel w\parallel}y_i( w\cdot x_i+b)$

​ 这样,假设超平面$S$的误分类点集合为$M$,那么所有误分类点到超平面$S$的总距离为

​ $-\frac{1}{\parallel w\parallel}\sum_{x_i\in M} y_i (w\cdot x_i+b)$

不考虑$\frac{1}{\parallel w\parallel}$,就可以得到感知机的损失函数.

给定一个数据集:

​ $T={(x_1,y_1),(x_2,y_2),…,(x_n,y_n)}$

​ 其中,$x_i \in \chi = R^n,y_i \in {+1,-1},i=1,2,…,N$,求参数$w,b$,使其损失函数极小化,感知机$sign(w\cdot x+b)$学习的损失函数为:

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

​ 其中M为误分类点的集合,这个损失函数就是感知机学习的经验风险函数

​ 感知机学习算法是误分类驱动的,具体采用随机梯度下降法(stochastic gradient descent),首先,任意选取一个超平面$w_0,b_0,$然后用梯度下降法不断地极小化目标函数

​ 假设误分类点集合$M$是固定的,那么损失函数$L(w,b)$的梯度由

​ $\nabla_w L(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=w + \eta y_ix_i$

​ $b=b + \eta y_i$

其中$\eta(0<\eta \leq 1)$是步长,在统计学习中又叫学习率(learning rate).这样通过不断迭代可以期待i损失函数$L(w,b)$不断减小,直到为0。综上所述。得到算法

​ 输入:训练集$T={(x_1,y_1),(x_2,y_2),…,(x_n,y_n)}$

​ 其中,$x_i \in \chi = R^n,y_i \in {+1,-1},i=1,2,…,N$;学习率$\eta(0<\eta \leq 1)$;

​ 输出:$w,b$;感知及模型$f(x)=sign(w\cdot x_i+b)$

​ (1) 选取初值$w_0,b_0$;

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

​ (3) 如果$y_i(w\cdot x_i+b)\leq 0,$

​ $w=w+\eta y_ix_i$

​ $b=b+\eta y_i$

​ (4) 转至(2),直至训练集中没有误分类点

​ 这种学习算法直观上有如下解释:当一个实例点