[工学]PR第五章非线性分类.ppt

第五章 非线性分类器,5.1 引言,线性判别函数：简单、实用、经济，但线性不可分时错误率可能较大 问题线性不可分采用非线性分类器 本章介绍几种非线性分类器 分段线性分类器 二次判别函数 神经网络 支持向量机,5.2 分段线性判别函数 (piecewise linear discriminant functions),上一章的多类线性判别函数实际就是分段线性判别函数。 思路：如果两类可以划分为线性可分的若干子类，则可以设计多个线性分类器，实现分段线性分类器。,最简单情况：直接依据样本到各子类中心的距离判别 （距离分类器） 更一般情况：对每个子类求一个线性判别函数。,5.3 二次判别函数 (Quadratic Discriminant),正态分布下贝叶斯决策面一般为二次函数，根据样本学习分类（决策、判别）函数的参数。样本近似正态分布时效果较好。 判别函数 阈值，控制决策椭球大小。 样本到类均值的Mahalanobis距离的平方与阈值的比较,两类的决策面方程： 决策规则：,5.4 多层感知器神经网络,5.4.1 神经元与感知器 神经元（neuron）：细胞体（cell）、树突（dentrite）、轴突（axon）、突触（synapses） 神经元的作用：加工、传递信息（电脉冲信号） 神经系统：神经网：大量神经元的复杂连接 通过大量简单单元的广泛、复杂的连接而实现各种智能活动。,人工神经网络 Artificial Neural Network (NN)的基本结构： 大量简单的计算单元（结点）以某种形式相连接，形成一个网络，其中的某些因素，如连接强度（权值）、结点计算特性甚至网络结构等，可依某种规则随外部数据进行适当的调整，最终实现某种功能。 三个要素： 神经元的计算特性（传递函数） 网络的结构（连接形式） 学习规则,三要素的不同形成了各种各样的神经网模型 基本可分为三大类： 前馈网络 以MLP为代表 反馈网络 以Hopfield网为代表 自组织网络（竞争学习网络） 以SOM为代表 基本的神经元模型 McCulloch-Pitts Model (1943),感知器，感知准则函数,当两类线性可分时，此算法收敛 Minsky等发现并证明(1969)，感知器只能解决一阶谓词逻辑问题，不能解决高阶问题，如不能解决XOR问题。 出路：多个感知器结点结合，引入隐节点，如右图的结构可实现XOR。 如何求多层感知器的权值？,5.4.3 采用反向传播算法的多层感知器,MLP结构 结点采用Sigmoid函数,MLP特性：可以实现任意复杂的非线性映射关系 用于分类： 两层网（一个隐层）可实现空间内任意的凸形成区域的划分。 三层网（两个隐层）可实现任意形状（连续或不连续）区域划分。 问题：如何找到这样的网络结构？权值如何确定？ 反向传播算法-BP算法（Back Propagation Algorithm）,BP算法：LeCun, 1986; Rumelhart, Hinton Parker, 1985 (1) 权值初始化，t=0（用小随机数） (2) 给出一个训练样本 和期望输出 (3) 计算在x输入下的实际输出 (4) 从输出层开始，调整权值，对第l层，有 其中 为学习步长, 计算如下： 对输出层： 对中间层：,(5) 重新计算输出，考查误差指标（或其它终止条件）。如达到终止条件则终止，否则置t=t+1，转（2）。 说明： 算法可能收敛于局部极小点（梯度算法） 与初值、步长等的选择有关，更与网络结构（结点数目）有关，多凭经验或试验选择,5.4.4 用多层感知器网络实现模式识别,输入 样本特征向量（必要时归一化） 输出 类别编码 常用输出编码： 1-of-C编码：c类则c个输出结点，该输出结点值为1则为该类，否则为0 两类：一个输出结点，0、1各代表一类。 也可用c个网络解决c类问题，每个网络只分一类（是与否）。,5.4.5 神经网络结构的选择,三个要素： 神经元的传递函数 - 通常选Sigmoid函数 网络结构 - 通常三层（1个隐层）即可满足常见任务需求，隐层节点数目？ 连接权值 - 通常采用 BP算法学习 过学习（over-fitting）与欠学习（under-fitting）问题 样本数与网络结构问题 隐层节点数目： 根据具体问题进行试探选择：例 隐结点数目小于输入维数 据对问题的先验知识去精心地设计隐层节点的层数和节点数目：例 用算法来推测适当的隐层节点数目：例,前馈神经网络与传统模式识别的关系 感知器，基于感知准则函数的线性分类器 多层感知器，对贝叶斯后验概率的估计 用于分类：前馈神经网络-多层感知器，RBF神经网络 用于函数优化：反馈神经网络Hopfield网 用于聚类（非监督学习）：基于竞争学习的神经网络SOM神经网络,5.5 支持向量机 (Support Vector Machines),统计学习理论 线性可分的情况 非线性可分的情况,分类函数应该使期望风险最小，但实际实现时是使经验风险最小 经验风险是在给定的训练样本上对期望风险的估计 这个估计量怎么样？ 统计学习理论：有限样本下，经验风险和期望风险的关系 在训练误差相同的情况下，学习机器的复杂度越低（VC维越低），期望风险与经验风险的差别越小，学习机器的推广能力越好。,5.5.1 广义线性判别函数,5.5.2 核函数变换与支持向量机,线性支持向量机的对偶问题： 判别函数： 支持向量满足等式,s.t.,特征x进行非线性变换 决策函数： 优化问题变成： 支持向量满足等式,定理（Mercer条件） 对于任意的对称函数 它是某个特征空间中的内积运算的充分必要条件是，对于任意的 有 正定核（positive definite kernels）： 是定义在空间X上的对称函数，且对任意的训练数据 和任意的实系数 都有 。 这样构成的空间是可再生核希尔伯特空间RKHS（reproducing kernel Hilbert space）,核函数 变换空间里的支持向量机 是下列优化问题的解： 支持向量满足等式,常用核函数形式 多项式核函数 径向基（RBF）核函数 Sigmoid函数 核函数及其参数的选择,核函数与相似性度量 SVM的基本思想、优势 SVM和NN SVM的决策过程可以看做是一种相似性比较的过程,5.5.3支持向量机应用举例,5.5.6 用于函数拟合的支持向量机,支持向量回归SVR 用于函数拟合 采用的损失函数不同于SVM,5.6 核函数机器（Kernel Machines）,SVM的两个核心思想 大间隔方法（Large-margin methods）具有良好的推广能力 核函数方法（Kernel m