模式识别复习

第一章 导引模式识别：就是利用计算机对某些物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观事物相符。模式：广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。模式的直观特性：可观察性可区分性相似性模式识别系统的目标：在特征空间和解释空间之间找到一种映射关系，这种映射也称之为假说。特征空间：从模式得到的对分类有用的度量、属性或基元构成的空间。解释空间：将c个类别表示为 其中为所属类别的集合，称为解释空间。数据聚类：目标：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集。是一种非监督学习的方法，解决方案是数据驱动的。统计分类：基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。特征向量分布的获得是基于一个类别的训练样本集。是一种监督分类的方法，分类器是概念驱动的。结构模式识别：该方法通过考虑识别对象的各局部之间的联系来到达识别分类的目的。识别采用结构匹配的形式，通过计算一个匹配程度值来评估一个未知的对象或未知对象某些局部与某种典型模式的关系如何。当成功地制定出了一组可以描述对象局部之间关系的规那么后，可以应用一种特殊的句法模式识别，来检查一个模式基元的序列是否遵守某种规那么，即句法规那么或语法。神经网络：神经网络是受人脑组织的生理学启发而创立的。由一系列互相联系的、相同的神经元组成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联系的权重系数来实现。神经网络可以实现监督和非监督学习条件下的分类。模式识别系统的根本构成：数据获取数据获取特征提取和选择预处理分类决策分类器设计

聚类分析K-均值算法分类。P27判别函数和可训练确实定性分类器线性判别函数：一个n维线性判别函数的一般形式：其中w0=(w1,w2,…,wn)T称为权向量〔或参数向量〕,x=(x1,x2,…,xn)T。d(x)也可表示为：d(x)=wTx其中，x=(x1,x2,…,xn,1)T称为增广模式向量，w=(w1,w2,…,wn+1)T称为增广 权向量。既然有线性判别函数，为什么还要引进非线性判别函数？试分析由“线性判别函数”向“非线性判别函数”推广的思想和方法。答：实际中有很多模式识别问题并不是线性可分的，这时就需要采用非线性分类器，比方当两类样本分布具有多峰性质并互相交错时，简单的线性判别函数往往会带来较大的分类错误。这时，树分类器作为一种分段线性分类器，常常能有效地应用于这种情况。对于n维x向量，假设用r次多项式，判别函数d(x)的权系数的总项数为：势函数法——一种确定性的非线性分类算法。P64统计判别及其可训练的模式分类器贝叶斯最小错误率。P67贝叶斯最小风险决策。P69特征选择和特征提取K-L变换降维分类特征提取。P120

神经网络什么是人工神经网络？所谓人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息处理系统〔计算机〕。有什么主要特点？优点固有的并行结构和并行处理知识的分布存储容错性自适应性缺点不适于高精度的计算不适于做类似顺序计数的工作学习和训练往往是一个艰难的过程必须克服时间域顺序处理方面的困难硬件限制正确的训练数据的收集人工神经网络模型的选取原那么？网络大小所需输出类型联想记忆类型训练方法时间的限定

误差反传算法〔BP算法〕的原理BP算法是有指导训练的前馈多层网络训练算法，是靠调节各层的加权，使网络学会由输入输出对组成的训练组。其学习过程由信号的正向传播与误差的反向传播两个过程组成。正向传播：输入样本——>输入层——>隐蔽层——>输出层如果输出层实际输出与期望输出不符，那么反传误差。误差反向传播：输出误差——>隐蔽层——>输入层将误差分摊给各层所有单元，从而获得各层单元的误差信号，进而修正各单元的权值。误差反传算法〔BP算法〕的步骤初始化输入训练样本对，正向计算各层输出计算网络输出误差反向计算各层误差信号调整各层权值检查网络总误差是到达到精度要求，如果满足，那么结束，否那么返回第2步。

BP训练算法实现步骤准备：训练数据组。设网络具有m层，这里，m代表层号，而不是向量的类号。表示第m层中第j个结点的输出。〔零层输出〕等于xj，即第j个输入。表示从到的连接加权。将各加权随机置为小的随机数。可用均匀分布的随机数，以保证网络不被大的加权值所饱和。从训练数据组中选一数据对(xk,Tk)，将输入向量加到输入层〔m=0〕，使得对所有端点i：，k表示向量类号信号通过网络向前传播，即利用关系式：计算从第一层开始的各层内每个结点i的输出，直到输出层的每个结点的输出计算完为止。计算输出层每个结点的误差值〔利用公式(1)〕〔对Sigmod函数〕它是由实际输出和要求目标值之差获得。计算前面各层各结点的误差值〔利用公式(2)〕这里逐层计算反传误差，直到将每层内每个结点的误差值算出为止。利用加权修正公式和关系修正所有连接权。一般η=0.01~1，称为训练速率系数。返回第2步，为下一个输入向量重复上述步骤，直至网络收敛。BP算法推算过程当参加第k个输入时，隐蔽层h结点的输入加权和为：相应点的输出：同样，输出层j结点的输入加权和为：相应点的输出：这里，各结点的阈值等效为一个连接的加权θ=w0h或w0j,这些连接由各结点连到具有固定值-1的偏置结点，其连接加权也是可调的，同其它加权一样参与调节过程。误差函数为：为了使误差函数最小，用梯度下降法求得最优的加权，权值先从输出层开始修正，然后依次修正前层权值，因此含有反传的含义。根据梯度下降法，由隐蔽层到输出层的连接的加权调节量为：其中为输出结点的误差信号： (1)对于输入层到隐蔽层结点连接的加权修正量Δwih，必须考虑将E(W)对wih求导，因此利用分层链路法，有：其中： (2)可以看出，式(1)和(2)具有相同的形式，所不同的是其误差值的定义，所以可定义BP算法对任意层的加权修正量的一般形式：假设每参加一个训练对所有加权调节一次，那么可写成：其中，下标o和in指相关连接的输出端点和输入端点，yin代表输入端点的实际输入，δo表示输出端点的误差，具体的含义由具体层决定，对于输出层由式(1)给出，对隐蔽层那么由式(2)给出。输出层可直接计算，于是误差值很容易得到。对前一隐蔽层没有直接给出目标值，不能直接计算，而需利用输出层的来计算：因此，算出后，也就求出了。如果前面还有隐蔽层，用再按上述方法计算和，以此类推，一直将输出误差δ一层一层推算到第一隐蔽层为止。各层的δ求得后，各层的加权调节量即可按上述公式求得。由于误差相当于由输出向输入反向传播，所以这种训练算法成为误差反传算法〔BP算法〕。

句法模式识别句法模式识别系统框图句法模式识别系统的组成:图像预处理图像分割基元及其关系识别句法分析句法模式识别系统处理过程:待识别的输入图像，经过增强、去噪声等处理后，按识别的具体对象分割成子图；然后将子图分割成更简单的模式基元；判别基元之间的关系；基元本身包含的结构信息已不多，仅需少量特征即可识别；如果用有限个字符代表不同的基元，那么由基元按一定结构关系组成的子图或图形可以用一个有序的字符串来代表；假设事先用形式语言的规那么从字符串中推断出能生成它的文法，那么最后通过句法分析，按给定的文法来辨识由基元字符组成的句子，从而判别它是否属于由该给定文法所能描述的模式类，到达分类的目的。文法G=(VN,VT,P,S)VN:非终止符的有限集，也称变量。VT:终止符的有限集，也称常量。P:生成式的有限集，也称重写规那么。S:起始符，也称根符。

有限状态机A=(Σ,Q,δ,q0,F)Σ:输入字母表，为一有限集。Q:内部状态的有限集。δ:内部状态转换的映射。q0:自动机A的起始状态。F:终止状态，也是Q的一个子集。按有限态自动机确定正那么文法举例：P147设一有限态自动机A=({0,1},{q0,q1,q2},δ,q0,{q2})，δ定义如下：δ(q0,0)=q2，δ(q1,0)=q2，δ(q2,0)=q2，δ(q0,1)=q1，δ(q1,1)=q0，δ(q2,1)=q1试求等价的正那么文法，使得L(G)=T(A)设由A得一正那么文法G=(VN,VT,P,S)，那么VN={S,x1,x2}，VT={0,1}，S=q0由δ(q0,1)=q1，得生成式S->1x1由δ(q1,1)=q0，得生成式