第三章 判别函数分类器
经过特征抽取之后，一个模式可以用维特征空间中的一个点来表示，当特征选择适当时，可以使同一类模式的特征点在特征空间中某个子区域内分布，另一类模式的特征点在另一子区域分布（例如苹果和橙子的问题）。这样，我们就可以用空间中的一些超曲面将特征空间划分为一些互不重叠的子区域，使不同模式的类别在不同的子区域中。这些超曲面称为判别界面，可以用一个方程来表示：，其中的是一个从维空间到一维空间的映射，称为是判别函数(Discriminant Function)。
在所有的函数形式中，线性函数是一种最简单的形式，下面我们就从线性判别函数入手来研究判别函数分类器。
3.0 预备知识
在介绍线性判别函数之前，先来帮助大家复习一下有关于矢量和矩阵的知识。
矢量
这里的矢量可以看作是维欧氏空间中的一个点，用一个列矢量表示：
矩阵
有的时候矩阵可以看作是由若干个矢量构成的：
是一个的矩阵，其中的称为是矩阵的行矢量。
矩阵的秩
矩阵所有行向量中的最大无关组个数称为行秩，矩阵所有列向量中的最大无关组个数称为列秩。一个矩阵的行秩等于列秩，称为矩阵的秩。
转置
列矢量的转置为一个行矢量，的矩阵的转置为一个的矩阵。
矢量和矩阵的乘法
设和为维列矢量，为一个的矩阵。则：
，是一个数值，称为与的内积；
，是一个的矩阵；
，是一个维的列矢量
正交
设和为维列矢量，如果和的内积等于零，，则称和正交，也称垂直于。
逆矩阵
设为一个的方阵，的逆阵用表示，满足，为单位阵。一个矩阵的逆阵存在条件是，首先是一个方阵，其次是一个满秩矩阵，即矩阵的秩为。
矩阵的特征值和特征向量
设为一个的方阵，如果存在一个数和一个维的非零列矢量，使得：成立，则称为的特征值，为属于的特征向量。
一般来说一个矩阵应该有个特征值（可能相等），对应有个特征向量。
矩阵的迹和行列式值
设为一个的方阵，的迹为主对角线元素之和：；的行列式值表示为。
如果矩阵有个特征值，则有，。
矩阵微分
矩阵对数值变量微分
如果矩阵的每一个元素是变量的可微函数，则称可微：
其结果还是一个的矩阵。
矩阵函数对矩阵的微分
设，元函数，定义对矩阵的导数为：
其结果是一个的矩阵。
特殊的，函数对一个矢量的微分是一个矢量。
常用微分的性质
设和是维的矢量，是一个维的矩阵，
，；
，；
，。
3.1 线性判别函数
一、两类问题
维空间中的线性判别函数可以表示为：
其中为待识模式的特征矢量，称为权矢量。一般为了处理方便，我们可以将特征矢量和权矢量改为另外一种方式表示：称为增广的特征矢量，称为增广的权矢量。则线性判别函数可以以一种简单的内积形式表示：。
在二维空间中，判别界面可以用一个直线方程来表示：；在三维空间中，判别界面为一个平面；在高维空间中，判别界面为一个超平面。
当我们已知线性判别函数的权矢量时，可以构造这样一个分类器：
但模式处在分类界面上时，，这是一种极端情况，可以采用两种办法来处理，一种是认为它既不属于类，也不属于，拒绝识别；另一种办法是认为。
对于线性判别函数来说，权向量在线性空间中是一个垂直于分类界面的矢量。
二、多类问题
设有个类别，模式为维空间中的矢量。
情况一：每一类模式可以用一个超平面与其它类别分开，即可用线性判别函数将属于和不属于类的模式（记为）分开。这种情况可以把个类别的多类问题分解为个两类问题解决，需要个判别函数。此时判别函数为：
例如在二维空间中的三类问题，判别函数分别为：
，，
分类器可以按照如下规则设计：
当，而且时，判别；
当，而且时，判别；
当，而且时，判别；
其它情况，拒识（对应IR区域）。
情况二：每两类之间可以用一个超平面分开，但是不能用来把其余类别分开。这是需要将个类别的多类问题转化为个两类问题。判别函数为：
，，
其中：。分类器可以采用如下规则：如果，，则决策。
在这种情况下，同样存在着拒识区域，例如图中的阴影区域，，，，所以它不属于任何一个类别。
例3.1：一个三类问题，有三个判别函数：
，，
现有模式，判别它属于哪一类？
带入三个判别函数：
，得；
，得；
，得。
可见，所以可以判别。
情况三：在情况一和情况二中都存在着拒识区域。拒识区域的存在，对某些问题来说是必要的，而对某些问题来说是不必要的。情况三是情况二的一个特例，在这种情况下不存在拒识区域。
首先我们需要对个类别分别个线性函数：
，，
然后按照如下的规则作出判别：
，则。
这样构造的分类器也称为是最大值分类器。它也可以看作是一种特殊形式的情况二的分类器，第类与第类之间的判别函数可以写成：
，，。
实际上，情况三的分类器我们在距离分类器中已经遇到过，使用欧氏距离的独立标准样本距离分类器就是一个最大值分类器。
有个类别，其标准样本分别为，我们可以定义第类的函数为：，经过简化之后可以变为一个线性函数。
首先考虑到开方的单调性，可以去掉开方，对比较大小不会产生任何影响，则：
其次考虑到在每一类别的判别函数中都存在且相等，也可以简化掉，对比较大小不会产生影响，则：
对比一下线性判别函数，令：，，，则可以看作是一个线性函数。判别界面也是一个超平面：
其中表示的模长的平方。分类界面的超平面刚好是垂直于和的连线，并且平分两点之间的连线。（首先垂直于矢量，其次经过点）。
经过上述分析我们可以看出，线性分类器可以用于处理线性可分的两类问题或多类问题，而类别之间的线性可分的条件是：各个类别的区域为互不相交的凸集（如不是凸集，则包含此集合的最小凸集因满足互不相交）。
在线性可分的条件下，都可以用一系列的线性函数实现分类器。这样的线性函数并不是唯一的，可能存在无穷多个。下面的问题就是如何得到这样一个或一组线性函数，这就是下面要讨论的线性分类器的训练问题。
3.2 两类别问题线性判别函数的学习
我们先来介绍一种最简单的情况，用线性函数来判别两类问题。
一、问题的表达
现有个训练样本，分为两个集合，类的训练样本集和类的训练样本集。要求一个向量，使能够区分和，即对于，有；对于，有，所以有：
即：
写成矩阵形式：，其中称为增广矩阵，为零矢量。
由此可见，求取权向量的问题已经转化为了求解线性不等式组的问题。这个解只有在线性可分的条件下才存在，并且也不唯一。下面我们介绍几种求解上述线性不等式组的算法。
二、感知器算法
求解线性不等式方程组，不可能用一个公式来求得，必须要有一个迭代搜索的过程。下面先以一种比较直观的方式来介绍一下感知器算法。
首先我们先来看一下分类界面，分类界面与权矢量垂直，现在我们要求，实际上关心的是它的方向，而不是关心它的长度。其次这个分类界面是一个经过坐标原点的超平面。如下图所示。
开始的时候，我们不知道的值是多少，可以先随便设一个不全为零的初始值，这样可以得到一个初始的分类界面；然后从训练样本集中拿出一个样本进行训练，将带入到辨别函数，计算，如果大于等于0，说明现在的分类界面已经能够正确分类，不需要任何调整，可以从训练样本集中取出下一个样本进行训练，如果小于0，说明现在的分类界面不能够正确分类，需要对分类界面进行调整。
所谓对分类界面进行调整，就是要调整权向量，我们可以按照下面的方式进行调整：，从图中可以看出来新的分类界面已经能够正确分类样本了。这就是感知器算法的主要思想，如果分类界面能够正确分类当前的训练样本时，不需要对其进行调整；如果分类错误时，需要进行调整，调整后的权向量是将原来的权向量与当前的训练样本相加得到的。
图中所表示的情况是经过一次调整，新的分类界面就可以正确分类训练样本，在某些情况下，只经过一次调整并不一定就能够达到目的，需要多次进行调整，但是如果按照上面的方法进行调整，总是向着好的方向发展。因为我们可以看到：
前面的讨论都是以一种形式化的方式给出了感知器算法的思想，下面我们从一个规范的数学方法来推导出感知器算法。
首先我们把求解线性不等式组的问题等价为一个最优化的问题，定义一个准则函数：
其中是我们已知的，由训练样本集构成的增广矩阵，是我们所有求的权值向量。当满足不等式组时，达到最小值0。计算对的偏导数：
其中：
不可能直接进行求解（解不唯一），但是我们可以采用最优化方法中的梯度下降法来迭代求取的值。迭代算法可以表示为：
，
其中为一个随机的初始值，为一个常数。
梯度下降法的思路也比较简单，俗称为瞎子下山法，在这一点上沿着这一点梯度的正方向前进，可以使上升的最快，因此，沿着梯度的负方向前进，可以使下降的最快。常数用来控制下降的速度，应该选择一个比较合适的值，太小则收敛速度太慢，太大则容易不收敛。
由于，所以完整的感知器算法如下：
初始化，置为一个小的随机数，不能为0矢量；
在第步输入训练样本，按照如下公式修正权值：
重复第2步，直到所有训练样本被正确识别。
例3.2
可以证明，当训练样本集满足线性可分条件时，感知器算法经过有限步迭代收敛。
二、最小均方误差算法(LMSE)
感知器算法只有当模式类别线性可分的条件下才能在有限步收敛，在线性不可分的情况下，算法会来回摆动，始终不收敛。同时在线性可分的情况下，也不可能预先知道达到收敛所需要的步数。因此，当迭代多次还不收敛时，我们无法判断类别是否线性可分。
下面介绍一种称为最小均方误差法，可以避免上述问题。此方法也称为Ho-Kashyap算法（H-K算法）。
首先我们把求解线性不等式组的问题等价转换为求解线性方程组的问题，其中，。一般情况下，为一个阶的长方阵，所以无解，只能求取一个近似解。
定义一个误差矢量，建立一个优化的准则函数：
我们所有求的近似解应满足，即误差矢量的模最小。且是的即为所求的解向量。先来求对的梯度：
令：，则：
，即：。
其中为一个的方阵，当非奇异时（当比较大时，很容易成立），存在，则：
记：，称为的伪逆矩阵。。可以通过计算得到，现在如果我们知道，则可求得。但也是一个为止变量。下面来求：
如果直接求解，则是的函数，所以不可能直接求得和，还是需要一个迭代算法来求解。下面还是使用梯度下降法来迭代求解：
一般来说，我们选择，由于我们的寻优结果需要满足条件：，而有可能大于0也可能小于0，所以上述梯度下降法的迭代规则应修改为：
完整的H-K算法如下：
由训练样本集构造增广矩阵，求伪逆矩阵；
初始化，其中每一个分量为一个较小的正值，选取常数，置步数；
计算，；
若，停止迭代，得到；
若，即的全部分量均为负值，则停止，说明线性不可分；
其它情况，即的分量中有正有负，则继续5；
计算
，转到第3步，继续。
算法中的第5步，需要对的每一个分量进行判断，大于0的分量修改相应的分量，小于等于0，则不修改。可以写成下述表达式：
通过第5步的修正规则我们可以看到，当的全部分量均小于等于0时，的修改就会停止，但此时，还没有收敛与最小值0，所以知训练样本集线性不可分。
例3.3
LMSE算法的优点是收敛速度快，同时可以监视收敛过程，即使判断出线性不可分的情况。可以证明当模式是线性可分时，如果取，则单调下降，并且。
3.3 多类别问题线性判别函数的学习
前面已经讲过多类别的识别问题个一转化为多个两类别问题，同样多类别的线性判别函数学习问题也可以转化为多个两类问题线性函数的学习问题。我们还是分成三种情况来讨论。
情况一：一个类的问题可以看作是个两类别问题，设有个类别，转化为两类别问题，由作为判别函数。训练过程可以将类的样本作为一类，而之外的其它类别样本作为一类进行训练。
情况二：设有个类别，将类问题转化为个两类问题，以作为判别函数，训练是以类样本和类样本进行训练。
情况三：对于情况三，我们可以扩展以下感知器算法来进行学习。
对于类的情况需要建立个线性判别函数，假如，则判别。下面给出扩展的感知器学习算法：
现有个训练样本，分别属于不同的类别，，首先对每一个样本进行增广的特征矢量（只须增加一维特征1，而不需要改变符号）。
初始化，个权矢量，选择一个迭代常数，置步数；
输入训练模式的增广特征矢量，计算个判别函数：
，
修改权矢量，规则为：
若，并且，
则，；
若，而
则；
；
，；
重复2，3步骤，当时，检测当前的个判别函数是否能够对全部的训练样本正确分类（亦即权值未经过任何修改），若是，则结束；否则
3.4 非线性判别函数的学习
对于有些问题来说。可以在维空间中构造线性函数来进行分类，而有一些问题，在维空间中是可分的，但不是线性可分的，对于这一类问题就需要使用非线性判别函数进行分类。然而非线性判别函数的构造却是一个比较困难的问题，在本节中我们给出一些学习非线性判别函数的思路。
一、二次判别函数
对于某些问题来说，我们无法用维空间中的一次线性函数进行区分，但是可以一个二次函数来区分。比如说“异或问题”，我们就可以用一个椭圆的二次判别函数来进行分类，椭圆内部的是一类，椭圆外部的是一类。
现在的问题是如何来学习这样的二次判别函数。现在我们以2维空间中的两类问题为例来说明，2维欧氏空间中一个一般的二次函数可以表示为：
解决上述问题，我们可以将一个2维空间中的分类问题转化为5维空间中的分类问题，其它3维由，和构成，如果这个问题在2维空间中是2次判别函数可分的，那么在新的5维空间中，就应该是线性可分的，我们可以首先将训练样本进行扩展，转换到5维空间中，然后利用前面介绍的线性分类器的学习算法训练出一个5维空间中的线性分类器，在转换到2维空间中，就构成了一个2次判别函数。
下面以“异或”问题为例来加以说明：
在2维空间中的训练样本：：，：，转化到5维空间中：：，：，采用感知器算法进行训练，得到一个2次的判别函数：
判别界面如下图所示，是一个双曲线：
这种方法也存在着一定的缺陷，并不是说所有的问题都可以用二次判别函数来解决，当判别函数的次数升高时，相应的特征维数会增加的很多；即使是二次函数，当原始特征维数比较大时，为数增长的也会比较快，对特征矢量来说，进行二次扩展后，维数变为：。一般来说，随着特征维数的增加，训练问题的解决也越难，算法的收敛的速度也越慢。
二、分段线性函数
对于有一些问题来说，我们可以采用分段线性函数来进行分类，比如下图所示的问题：
类别1和类别2无法用一个线性函数区分，但是我们可以用五个线性函数构成一个分段线性函数来建立分类器。但是分段线性函数的确定也还是一个比较困难的问题，下面介绍几种解决方案。
基于聚类的方法
我们可以采用上一章中介绍的聚类分析的办法，现将每个类别聚成若干个子类，比如上图中，类别1聚成两个子类，类别2聚成3个子类，两个类别中的不同子类之间线性可分。这样我们就可以分别对两个类别中的子类建立线性判别函数，然后将这些线性判别函数组合到一起就可以构成一个分段线性的分类界面。
实际上，上一章中介绍的多个标准样本的距离分类器就是一个分段线性的判别函数分类器。只不过分类界面垂直平分对应的两个标准样本的连线。
逐块两分法
如下图所示，首先选择一个超平面将空间分为两部分，由于两类线性不可分，所以在每一个空间中必然都有两类的样本，但是在其中的一个空间中有可能两类已经线性可分了，比如左面的一半空间，那么在这一块空间中可以建立一个线性分类器将两类分开；然而在右面的一半空间中还是线性不可分的，仍然可以采用同样的办法，选择一个超平面，在将这一半空间分为两部分；重复上述过程，直至所有的空间中，两类样本都线性可分为止。将这些选择的超平面和最后建立的线性判别函数组合到一起，就可以构成一个分段线性的判别函数。
这里存在的问题就是，如何来选择超平面将空间分为两部分。选择的好，用很少的线性判别函数就可以解决问题，选择得不好，所用的线性判别函数就会很多。到目前为止还没有一个完美的算法能够找到这种最优的解决方案。只能采用一些次优的方法进行搜索。比如每次选择超平面时，尽量使得同一块空间中同类样本的数目尽量多。
三、其它非线性判别函数方法
非线性判别函数的训练方法还有很多，例如可以用一些比较简单的函数的线性组合来逼近所求的非线性判别函数，可以用多项式函数来逼近非线性函数，也可以用指数函数的线性组合逼近非线性函数。
另外一种比较实用的办法是采用多层感知器，即前馈神经网络来实现非线性的分类问题。
