2. 感知机

作者: 楼桑村小秀才 | 来源:发表于2018-08-29 11:05 被阅读0次

2. 感知机
感知机模型(Perceptron)详细解读 | 统计学习方法学习
2018-05-27
CH2 感知机|2.1感知机模型&2.2学习策略《统计学
感知机
1、深度学习入门-感知机
深度学习入门(1)感知机
神经网络概述
动手学深度学习(三) 多层感知机
多层感知机 2020-02-18

感知机

输入空间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$

以上证明表面: 当训练数据集线性可分时, 误分类的次数K是有上限的, 即经过有限次搜索一定可以找到将训练数据集完全正确分开的分离超平面.

感知机学习算法的对偶形式:

clipboard.png

其中的 $a_i=n_i\lambda, n_i$ 表示第i个数据被误分类的次数, 则w,b关于 $(x_i,y_i)$ 的增量分别是 $a_iy_ix_i$ 和 $a_iy_i$
$w=\sum_{i=1}^Na_iy_ix_i,\qquad b=\sum_{i=1}^Na_iy_i$

Gram矩阵: 预先将训练集中实例间的内积计算出来并以矩阵的形式存储

对偶形式和原始形式本质是一致的, 对偶形式会事先计算实例间的内积, 所以比原始形式有更快的速度

2. 感知机
感知机输入空间X=, 输出空间Y={-1,+1}. 输入x属于X表示实例的特征向量,对应于输入空间的点; 输出y...
感知机模型(Perceptron)详细解读 | 统计学习方法学习
本文包括： 1.走近感知机 - 感知机与童话2.重要概念3.感知机模型的数学形式4.构建感知机的损失函数5.如何取...
2018-05-27
Deep Learning ：感知机的前世今生 1.什么是深度学习 2.什么是感知机 3.感知机能够做什么 4.感...
CH2 感知机|2.1感知机模型&2.2学习策略《统计学
文章原创,最近更新：2018-06-21 1.感知机模型2.学习策略参考链接:1、机器学习十七：感知机前言：...
感知机
感知机感知机模型感知机学习策略感知机学习算法算法的收敛性感知机学习算法的对偶形式感知机实现二分类模型 ...
1、深度学习入门-感知机
感知机是什么？感知机（perceptron）：感知机是神经网络（深度学习）的起源算法，学习感知机的构造是通向神...
深度学习入门(1)感知机
感知机感知机基础知识感知机是神经网络（深度学习）的起源算法。感知机可以接收多个输入信息，输出一个信号。感知...
神经网络概述
感知机最小的神经网络结构，无论多复杂的神经网络都由许多感知机构成。感知机结构：输入层、输出层感知机感知机是一...
动手学深度学习(三) 多层感知机
多层感知机多层感知机的基本知识使用多层感知机图像分类的从零开始的实现使用pytorch的简洁实现多层感知机...
多层感知机 2020-02-18
多层感知机多层感知机的基本知识使用多层感知机图像分类的从零开始的实现使用pytorch的简洁实现多层感知机...

2. 感知机

感知机

几何解释

感知机的损失函数

学习策略

学习算法

相关文章

2. 感知机

感知机模型(Perceptron)详细解读 | 统计学习方法学习

2018-05-27

CH2 感知机|2.1感知机模型&2.2学习策略《统计学

感知机

1、深度学习入门-感知机

深度学习入门(1)感知机

神经网络概述

动手学深度学习(三) 多层感知机

多层感知机 2020-02-18

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读