Perceptron

作者: BigPeter | 来源:发表于2018-12-14 23:05 被阅读0次

概括

Perceptron学习算法是1957年由Rosenblatt提出的分类算法，是SVM和Neural Network的基础。Perceptron是一个线性分类器，基于误分类准则学习分离超平面的参数(w, b).通过对偶学习法的推导可以通过运用核技巧使Perceptron可以分类非线性数据。

模型是线性分类器

$f(x)=w^Tx+b$

决策函数是

$y=sign(f(x))=sign(w^Tx+b)$

给定线性可分数据集 $T=\{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}$ ,需要确定Perceptron模型的参数（w, b）将数据集正确分类。如何确定学习的损失函数呢？

首先想到的损失函数是误分类点的个数，但是误分类点的个数不是参数(w, b)的连续可导函数，不易于模型的学习。

可以将误分类点到分离超平面距离作为损失函数。点 $(x_i,y_i)$ 到分离超平面的距离为

$\frac{|w^Tx_i+b|}{||w||}, ||w|| \ is\ L_2\ norm\ of \ vector\ w$

误分类点到分离超平面的距离为

$\frac{-y_i(w^Tx_i+b)}{||w||}$

令M是误分类点的集合，因此总距离为

$\frac{-1}{||w||}\sum_{x_i \in M}y_i(w^Tx_i+b)$

不考虑 $\frac{1}{||w||}$ (函数距离)就得到Perceptron的损失函数

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

该损失函数是(w, b)的连续可导函数，可以通过优化算法求解最优参数。

学习的目标是

$\min_{w, b}L(w, b)=\min_{w, b}-\sum_{x_i \in M}y_i(w^Tx+b)$

Perceptron采用随机梯度下降来学习参数(w, b)：

首先选取任意的 $(w_0,b_0)$ .

选取一个误分类点 $(x_i, y_i)$ ,计算损失函数对(w, b)的导数

$\frac{\delta L(w, b)}{\delta w}=-y_ix_i \\\frac{\delta L(w, b)}{\delta b}=-y_i$

然后更新当前的(w, b)

$w_{k+1}=w_{k}+\eta y_ix_i\\b_{k+1}=b_{k} + \eta y_i$

一直循环知道没有误分类点，得到参数最优解 $(w^*, b^*)$ .

该学习算法有一个直观的理解就是每一个迭代是分离超平面向误分类数据点的方向倾斜，直到最后没有数据点被误分。

对于线性可分数据集，Perceptron在有限的迭代里一定会找到一个分离超平面将数据集正确划分，但是这个分离超平面不是唯一的。

对于线性不可分数据集，Perceptron学习算法不会结束，因为存在超平面不可分离的数据点，学习后期的超平面会一直“震荡”。

对偶形式的想法是将(w, b)表示为实例 $x_i$ 和标记 $y_i$ 的线性组合的形式（方便使用核技巧）。在上面的原始学习过程中，假设初始化的w,b为0，在最后得到成功分离数据集的超平面后，实例 $x_i$ 共错误了 $n_i$ 次，所以

$w^*=\sum_{i}^Nn_i\eta y_ix_i \\ b^*=\sum_{i}^Nn_i\eta y_i$

$n_i$ 越大说明实例 $x_i$ 离超平面越近，较难正确分类。

模型表示为

$f(x)=sign(\sum_{i=1}^Nn_i\eta y_i(x_i\cdot x)+\sum_{i=1}^Nn_i\eta y_i)$ ,

我们发现式子中出现了内积项，可以使用核技巧隐含的在更合适的特征空间寻找分类超平面。

对偶算法：和原始算法大致一样，但是在学习过程中更新 $n_i$ ，通过上式计算超平面。

由于在对偶学习过程中，需要不断计算数据集中实例两两之间的内积，可以提前计算数据集中实例的Gram矩阵： $Gram_{i,j}$ 是实例i和实例j的内积。

可以将Perceptron认为一个两层的神经网络，输入层是向量x，输出层是一个激活函数为 $f(x)=sign(x)$ 的节点。

可以认为全连接网络（多层感知机，Multi Layer Perceptron）是由perceptron构成的。

[Stay Sharp]Perceptron
What is Perceptron? Perceptron is a single layer neural n...
Python Machine Learning study no
1.Perceptron 1.1 Description of Perceptron Rosenblatt pro...
Perceptron
概括 Perceptron学习算法是1957年由Rosenblatt提出的分类算法，是SVM和Neural Net...
【机器学习基础】从感知机模型说起
感知机（perceptron）感知器（perceptron）1957年由Rosenblatt提出，是神经网络与支...
2018-11-06 深度学习 deep learning 简介
一.deep learning的发展史 1.perceptron感知机假设数据集线性可分，perceptron的...
XOR Perceptron
XOR Perceptron 一个 XOR 感知器就是个逻辑门，如果输入相同返回 0，输入不同返回 1。与之前的感...
Perceptron感知器
Introduction Perceptron is a single layer neural network ...
支持向量机（Support Vector Machine）
支持向量机 linear regression ， perceptron learning algorithm ，...
《Machine Learning Foundation》读书笔
Learning to Answer Yes/No 一、 Perceptron Hypothesis Set 引入...
【ML】Neural Network Architecture
Perceptron(感知器): The simplest kind of neural network is a...