机器学习算法—感知机

作者: 皮皮大 | 来源:发表于2019-08-18 20:44 被阅读46次

感知机
机器学习算法—感知机
感知机
统计学习方法之感知机
机器学习1|感知机算法
1、深度学习入门-感知机
统计学习方法思路疏导—感知机
python machine learning学习笔记
感知机算法理解与C++实现
机器学习与深度学习目录

author : Peter
date: 2019-08-18

感知机Perceptron

导读

感知机是二分类的线性分类模型，输入是实例的特征向量（每个属性），输出是实例的类别。感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。

目的：找出将训练数据进行线性划分的分离超平面
导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求出最小值
有原始形式和对偶形式两种
感知机是种线性分类模型，属于判别模型。

感知机原理剖析及实现

应用实例

比如说我们有一个坐标轴（图中的黑色线），横的为x1轴，竖的x2轴。图中的每一个点都是由（x1，x2）决定的。

如果我们将这张图应用在判断零件是否合格上，x1表示零件长度，x2表示零件质量，坐标轴表示零件的均值长度和均值重量，并且蓝色的为合格产品，黄色为劣质产品，需要剔除。

那么很显然如果零件的长度和重量都大于均值，说明这个零件是合格的。也就是在第一象限的所有蓝色点。反之如果两项都小于均值，就是劣质的，比如在第三象限的黄色点。

在预测上很简单，拿到一个新的零件，我们测出它的长度x1，质量x2，如果两项都大于均值，说明零件合格。这就是我们人的人工智能。

image.png

定义

现在假设输入空间是 $X\subseteq{R^n}$ ，输出空间 $Y=\{+1, -1\}$ 。输入 $x\in X$ 表示实例的特征向量，输出 $y\in Y$ 表示实例的类别，其中输入到输出的函数表示如下： $f(x)=sign(w.x+b)$ ，称为感知机

w，b称为感知机模型参数；w称为权值或者权值向量； $b\in R$ 称为偏置bias。 $w \bullet x$ 表示二者的内机，sign表示符号函数：
$sign(x)= \begin{cases} +1, & {x \geq 0} \\ -1, & {x \leq 0} \end{cases}$

感知机的几何解释为线性方程： $w \bullet x+b=0$ 这条直线就是最好的那条线，最优解。特征空间 $R^n$ 对应一个超平面S，其中w是超平面的法向量，b是超平面的截距。超平面将特征空间划分为两个部分。位于两部分的点分为正负两个类别。正类为+1，父类为-1。

栗子（图2.1）：

image.png

策略

给定一个数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 其中 $x_i$ 是输入空间实例的特征向量， $y_i$ 是实例的输出类别，如果存在超平面S满足将数据集的正负实例完全分开，即满足：当 $w.x_i+b>0$ ,有 $y_i=+1$ ；当 $w.x_i+b<0$ ,有 $y_i=-1$ 。此时，将所有的数据分为线性可分数据集，否则称为线性不可分。

感知机中的损失函数误分类点到超平面S的总距离，输入空间中任意一个点 $x_0$ 到距离是 $\frac{1}{||w||}{(w.x_0+b)}$ ，其中||w||表示w的 $L_2$ 范数，即： $||w||=\sqrt{w_1^2+w_2^2+...+w_n^2}$ 对于误分类的点，总有如下结论： $-y_i(w.x_i+b)>0$ 因为在误分类的时候，每个实例点满足：当 $w.x_i+b>0$ ,有 $y_i=-1$ ；当 $w.x_i+b<0$ ,有 $y_i=+1$ 。因此，误分类的点到超平面的距离： $-\frac{1}{||w||}{y_i}{(w.x_0+b)}$ ，假设超平面中的所有误分类的集合M，所有误分类的点到S的总距离为： $-\frac{1}{||w||}\sum_{x_i \in M}{y_i}{(w.x_0+b)}$ ，不考虑 $-\frac{1}{||w||}$ 得到了感知机 $f(x)=sign(w.x+b)$ 的损失函数为： $L(w,b)=\sum_{x_i \in M}{y_i}{(w.x_0+b)}$
M是误分类点的集合
损失函数就是感知机学习的经验风险函数
梯度只是向量，代表下降的方向
通过学习率来控制下降的大小
如果没有误分类点，损失函数是0
误分类点越少，总距离越小，损失函数越小
L是参数(w,b)的连续可导函数

算法

原始形式

算法思想

感知机学习算法的最优化问题就是求解损失函数的最小值，即： $\mathop {\min \limits_{w,b}L(w,b)}=\sum_{x_i \in M}{y_i}{(w.x_0+b)}$ 。感知机的算法是误分类驱动的，具体采用的是随机梯度下降法(stochastic gradient descent)，大致过程如下：

选取任意的超平面 $w_0,b_0$
利用梯度下降方法去不断地极小化目标损失函数L(w, b)
在不断极小化的过程中，不是一次性使用M中所有误分类点进行梯度下降，而是一次随机选取一个误分类点进行梯度下降。
损失函数 $L(w, b)$ 的梯度由如下的式子决定： $\nabla_wL{(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\gets{w+\eta{y_ix_i}}$ $b\gets{b+\eta{y_i}}$ 其中 $\eta\in{(0,1]}$ 表示学习率或者步长。通过不断地迭代损失函数 $L(w,b)$ 使其不断的减小，直至为0

算法描述

输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中 $x_i\in X=R^n$ , $y_i \in Y=\{-1, +1\}, i=1,2,....,N$ ；学习率 $0 < \eta \leq 1$

输出：w,b；感知机模型 $f(x)=sign(w.x+b)$

选取初值 $w_0,b_0$ ，一般是0
在训练集中选取数据 $(x_i,y_i)$
如果存在误分类点，即满足： $-y_i(w.x_i+b)\geq {0}$ 或者 $y_i(w.x_i+b)\leq {0}$ ，进行 $(w,b)$ 的更新： $w\gets{w+\eta{y_ix_i}}$ $b\gets{b+\eta{y_i}}$
转到第二步，直至训练集中没有误分类点停止

直观解释：当有一个误分类点在超平面的错误一侧，调整w,b的值，使得分离超平面向着该误分类点的一侧移动，从而较小误分类点和超平面的距离，直至超平面越过该点，使其被正确地分类

栗子（2.1）：

image.png

对偶形式：

算法思想

对偶形式的基本思想是将w,b表示为实例 $x_i$ 和输出类别 $y_i$ 的线性组合的形式，通过求解系数从而求得w和b。

假设 $w,b$ 的初值是都是0，对于误分类点通过： $w\gets{w+\eta{y_ix_i}}$ $b\gets{b+\eta{y_i}}$ 逐步地去修改 $w,b$ ，设修改n次，则 $w,b$ 关于 $(x_i,y_i)$ 的增量分别是 $\alpha _iy_ix_i$ 和 $\alpha_iy_i$ ，其中 $\alpha_i=n_i\eta$ ，通过不断地迭代过程，最终学习到的 $w,b$ 分别表示为： $w=\sum _{i=1}^{N}\alpha _iy_ix_i$ $b=\sum _{i=1}^{N}\alpha _iy_i$

在上面两个迭代式子中， $\alpha_i \geq{0}, i=1,2,....N$ ；当 $\eta=1$ 时，表示第i个实例点由于误分类而进行更新的次数。

算法描述

输入：给定线性可分的训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中 $x_i\in X=R^n$ , $y_i \in Y=\{-1, +1\}, i=1,2,....,N$ ；学习率 $0 < \eta \leq 1$

输出： $\alpha, b$ ；感知机模型 $f(x)=sign(\sum _{j=1}^{N}{\alpha_jy_jx_j}.x+b)$ 其中， $\alpha=(\alpha_1,....,\alpha_N)^T$ ；训练过程为：

1.给定初值 $\alpha \gets 0,b\gets0$

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

3.如果 $y_i(\sum _{j=1}^{N}{\alpha_jy_jx_j}.x+b)\leq 0$ ，进行 $(w,b)$ 的更新： $\alpha \gets{\alpha_i+\eta}$ $b\gets{b+\eta{y_i}}$
4.转到第二步，直至训练集中没有误分类点停止

对偶形式中训练实例仅仅是以内积的形式出现，著名的Gram矩阵 $G=[x_i\bullet y_i]_{N\times N}$

栗子（2.2）：

image.png

算法收敛性

对于原始形式的感知机学习算法，经过有限次迭代之后可以得到一个将训练数据集完全分离的超平面和感知机模型。为了证明过程方便，将偏置b加入权重w中，记作 $\hat w=(w^T,b)^T$ ，同样的输入向量中也加入常数1，记作 $\hat x=(x^T, 1)^T$ 。显然有: $\hat x \in R^{n+1}，\hat w \in R ^{n+1}$ ，则 $\hat w \bullet \hat x=w \bullet x+b$ ，具体证明过程加入下图：

image.png

感知机
感知机感知机模型感知机学习策略感知机学习算法算法的收敛性感知机学习算法的对偶形式感知机实现二分类模型 ...
机器学习算法—感知机
author : Peterdate: 2019-08-18 感知机Perceptron 导读感知机是二分类的...
感知机
感知机感知机算法是很多算法的鼻祖，比如支持向量机算法，神经网络与深度学习。在学习感知机的构造时可以学习到深度学习...
统计学习方法之感知机
1.感知机模型在机器学习中，感知机（perceptron）是二分类的线性分类模型，属于监督学习算法。输入为实例的...
机器学习1|感知机算法
感知机是二分类模型，输入为实例的特征向量，输出为实例的类别，总结如下：总结得比较简洁，主要是为了让抓住重点，思路...
1、深度学习入门-感知机
感知机是什么？感知机（perceptron）：感知机是神经网络（深度学习）的起源算法，学习感知机的构造是通向神...
统计学习方法思路疏导—感知机
机器学习各类算法注意点前言这篇文章主要记录笔者在学习感知机算法过程中，各个算法需要注意的地方，不过过多的提及算...
python machine learning学习笔记
第二章训练机器学习分类算法感知机perceptron 自适应线性神经元adaptive linear neur...
感知机算法理解与C++实现
开始接触机器学习，今天刚刚学习了感知机并用C++实现了算法。现在整理一下，与大家分享，希望能帮到刚刚入门机器学习的...
机器学习与深度学习目录
机器学习：线性回归逻辑回归决策树贝叶斯分类随机森林集成算法支持向量机kmeans聚类k近邻算法深度学习感知器...

机器学习算法—感知机

感知机Perceptron

导读

应用实例

定义

策略

算法

原始形式

算法思想

算法描述

对偶形式：

算法思想

算法描述

算法收敛性

相关文章

感知机

机器学习算法—感知机

感知机

统计学习方法之感知机

机器学习1|感知机算法

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

统计学习方法思路疏导—感知机

python machine learning学习笔记

感知机算法理解与C++实现

机器学习与深度学习目录

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

呆鸟的Python数据分析

人工智能/模式识别/机器学习精华专题

大数据，机器学习，人工智能

深度学习-推荐系统-CV-NLP

机器学习与数据挖掘

机器学习_Python算法