2. 感知机

2018-08-29 本文已影响0人楼桑村小秀才

感知机

输入空间X= $R^n$ , 输出空间Y={-1,+1}. 输入x属于X表示实例的特征向量,对应于输入空间的点; 输出y属于Y表示实例的类别, 由输入空间到输出空间的如下函数
$f(x)=sign(w*x+b)$
称为感知机. w叫做权值,b叫做偏置, w*x表示w和x的内积(点积)

几何解释

w*x+b=0对应于特征空间中的一个超平面S, w是该平面的法向量, b是截距(将平面平移到坐标原点所需距离). 该平面分特征向量为两部分, 分别对应正,负两类.
原点到该平面的距离: $\frac{|b|}{||w||}$ . 任意一点x到超平面S的距离: $\frac{1}{||w||}|w*x+b|$ . (||w||是w的L2范数)

感知机的损失函数

误分类点到超平面S的总距离.

输入空间中任一点x到超平面S的距离: $\frac{1}{||w||}|w*x+b|$
对于误分类的数据 $(x_i,y_i)$ 来说: $-y_i(w*x_i+b)>0$
$w*x_i+b>0, \text{正确分类: }y_i=+1, \text{误分类: }y_i=-1$
$w*x_i+b<0, \text{正确分类: }y_i=-1, \text{误分类: }y_i=+1$
$\text{所以对于误分类的}(x_i,y_i), -y_i(w*x_i+b)>0$
因此误分类的点 $x_i$ 到超平面S的距离是 $-\frac{1}{||w||}y_i(w*x_i+b)$
所有误分类点(集合M)到超平面S的总距离为: $\displaystyle-\frac{1}{||w||}\sum_{x_i\in M}y_i(w*x_i+b)$

定义
给定训练数据集T={ $(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$ }, 其中 $x\in X=R^n, y\in Y=\{+1,-1\}$ , i=1,2,...,N. 感知机f(x)=sign(w*x+b)学习的损失函数定义为:
$L(w,b)=-\sum_{x_i\in M}y_i(w*x_i+b)=\sum_{x_i\in M}|w*x_i+b|\quad\text{其中M为误分类点的集合}$

一个特定样本点的损失函数, 在被误分类时是w,b的线性函数, 在正确分类时是0.
因此对于所有被误分类点的损失函数是w,b的连续可导函数(线性模型)

学习策略

在假设空间中选取使损失函数最小的模型参数(w,b)

学习算法

感知机学习问题转化为求解损失函数的最优化问题.
采用随机梯度下降法, 极小化过程不是一次使M中所有误分类点的梯度下降, 而是一次随机选取一个误分类点使其梯度下降.

损失函数L(w,b)的梯度: $\displaystyle\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i$ , $\displaystyle\nabla_bL(w,b)=-\sum_{x_i\in M}y_i$
随机选取一个误分类点 $(x_i,y_i)$ , 对w,b进行更新: $w\gets w-\lambda(-y_ix_i), b\gets b-\lambda(-y_i)$

感知机学习算法的原始形式:

clipboard.png

感知机由于采用不同的初值或选取不同的误分类点顺序, 解可以不同

Novikoff定理

设训练数据集T={ $(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$ }是线性可分的, 其中 $x\in X=R^n, y\in Y=\{+1,-1\}$ , i=1,2,...,N. 则
1: 存在满足条件||W||=1的超平面 W*X=wx+b=将训练数据集完全正确分开; 且存在 $\gamma$ >0, 对所有的i=1,2,...,N, 有 $y_i(W*X)=y_i(w*x_i+b)\geq\gamma$ . 其中W=<w,b>, X=<x,1>
2: 令R=max(X), 则感知机算法在训练数据集上的误分类次数k满足 $k\leq(\frac{R}{\gamma})^2$

Proof:
设此超平面为 $W_{opt}*X=w_{opt}*x+b_{opt}$ , 使 $||W_{opt}||=1$ ,因此对于所有的i=1,2,...,N有
$y_i(W_{opt}*X_i)=y_i(w_{opt}*x_i+b_{opt})>0$
所以存在
$\gamma=min{y_i(w_{opt}*x_i+b_{opt})}\qquad\text{使得}y_i(W_{opt}*X_i)=y_i(w_{opt}*x_i+b_{opt})\geq\gamma$
设感知机算法从 $W_0$ 开始, $W_{k-1}$ 是第k个误分类实例之前的权重向量(被正确分类的不需要更新权重向量), 即 $W_{k-1}=(w_{k-1}, b_{k-1})$ , 则第k个误分类实例的条件是
$y_i(W_{k-1}*X_i)=y_i(w_{k-1}*x_i+b_{k-1})\leq 0$
另由梯度下降法有
$W_k=W_{k-1}+\lambda y_iX_i\qquad(w_k=w_{k-1}+\lambda y_ix_i; b_k=b_{k-1}+\lambda y_i)$
所以有如下不等式:
$W_K*W_{opt}=W_{k-1}*W_{opt}+\lambda y_iX_i*W_{opt}\geq W_{k-1}*W_{opt}+\lambda\gamma$
$\text{由以上公式递推得到: }W_k*W_{opt}\geq W_{k-1}*W_{opt}+\lambda\gamma\geq W_{k-2}*W_{opt}+2\lambda\gamma\geq k\lambda\gamma$

$\begin{aligned} ||W_k||^2&=||W_{k-1}+\lambda y_iX_i||^2=||W_{k-1}||^2+\lambda^2||X_i||^2+2W_{k-1}*\lambda y_iX_i\qquad(y_i^2=1) \\ &\leq ||W_{k-1}||^2 + \lambda^2||X_i||^2\qquad(0\leq\lambda\leq 1, y_i(W_{k-1}*X_i) \leq 0) \\ &\leq ||W_{k-1}||^2 + \lambda^2R^2\qquad(R=max(X)) \\ &\leq ||W_{k-2}||^2 + 2\lambda^2R^2 \leq ...... \\ &\leq k\lambda^2R^2 \end{aligned}$

$\text{向量点积: }A*B=|A||B|\cos\theta,\qquad\text{得到: }A*B\leq |A||B|$

$k\lambda\gamma \leq W_k*W_{opt}\leq||W_k||*||W_{opt}||\leq\sqrt{k}\lambda R,\qquad\text{由此得到: } k^2\gamma^2\leq kR^2, \text{即}k\leq(\frac{R}{\gamma})^2$