第7章 分类方法(续)

1、第第7章章 分类方法（续）分类方法（续） 7.5 神经网络算法神经网络算法 人工神经网络（人工神经网络（Artificial Neural Network，ANN）是）是对人类大脑系统特性的一种描述。简单地讲，它是一种数对人类大脑系统特性的一种描述。简单地讲，它是一种数学模型，可以用电子线路来实现，用计算机程序来模拟，学模型，可以用电子线路来实现，用计算机程序来模拟，是人工智能的一种方法。是人工智能的一种方法。神经网络通过对大量历史数据的计算来建立分类和预神经网络通过对大量历史数据的计算来建立分类和预测模型。测模型。 7.5.1 7.5.1 生物神经元和人工神经元生物神经元和人工神经元典型的神

2、经元即神经细胞结构组成：胞体、树突、轴突、突触。典型的神经元即神经细胞结构组成：胞体、树突、轴突、突触。胞体：胞体：神经细胞的本体，完成普通细胞的生存功能。神经细胞的本体，完成普通细胞的生存功能。树突：树突：有大量的分枝，接受来自其他神经元的信号。有大量的分枝，接受来自其他神经元的信号。轴突：轴突：用以输出信号。用以输出信号。突触：突触：神经元相联系的部位，对树突的突触为兴奋性的，使神经元相联系的部位，对树突的突触为兴奋性的，使下一个神经元兴奋；对胞体的突触为抑制性的，阻止下一个下一个神经元兴奋；对胞体的突触为抑制性的，阻止下一个神经元兴奋。神经元兴奋。1、生物神经元、生物神经元p神经元的两种

3、工作状态：神经元的两种工作状态：兴奋兴奋和和抑制抑制。p动态极化原则：在每一个神经元中，信息以预知的确定方动态极化原则：在每一个神经元中，信息以预知的确定方向流动，即从神经元的接收信息部分传到轴突的电脉冲起向流动，即从神经元的接收信息部分传到轴突的电脉冲起始部分，再传到轴突终端的突触，以与其它神经元通信。始部分，再传到轴突终端的突触，以与其它神经元通信。p连接的专一性原则：神经元之间无细胞质的连续，神经元连接的专一性原则：神经元之间无细胞质的连续，神经元不构成随机网络，每一个神经元与另一些神经元构成精确不构成随机网络，每一个神经元与另一些神经元构成精确的联接。的联接。神经元的基本工作机制：神经

4、元的基本工作机制：信号的传递过程：信号的传递过程：接受兴奋电位；接受兴奋电位；信号的汇集和传导；信号的汇集和传导；信号的输出。信号的输出。2. 人工神经元人工神经元人工神经元用于模拟生物神经元，人工神经元可以看做人工神经元用于模拟生物神经元，人工神经元可以看做是一个多输入、单输出的信息处理单元，它先对输入变量进是一个多输入、单输出的信息处理单元，它先对输入变量进行线性组合，然后对组合的结果做非线性变换。行线性组合，然后对组合的结果做非线性变换。因此可以将神经元抽象为一个简单的数学模型。因此可以将神经元抽象为一个简单的数学模型。 其中其中n个输入个输入xi表示其他神经元的输出值，即当前神经表示其

5、他神经元的输出值，即当前神经元的输入值。元的输入值。n个权值个权值wi相当于突触的连接强度。相当于突触的连接强度。f是一个非是一个非线性输出函数。线性输出函数。y表示当前神经元的输出值。表示当前神经元的输出值。神经元的神经元的工作过程工作过程一般是：一般是： 从各输入端接收输入信号从各输入端接收输入信号xi。 根据连接权值根据连接权值wi，求出所有输入的加权和，即。，求出所有输入的加权和，即。 对对net做非线性变换，得到神经元的输出，即做非线性变换，得到神经元的输出，即=f(net)。niiixwnet1f称为称为激活函数激活函数或或激励函数激励函数，它执行对该神经元所获得输，它执行对该神经

6、元所获得输入的变换，反映神经元的特性。常用的激活函数类型如下。入的变换，反映神经元的特性。常用的激活函数类型如下。（1）线性函数）线性函数f(x)=kx+c其中，其中，k、c为常量。线性函数常用于线性神经网络。为常量。线性函数常用于线性神经网络。（2）符号函数）符号函数f(x)=1当当x0f(x)=0当当x0；任何位于决策边界下方的样本（；任何位于决策边界下方的样本（）Xc，可以证明有，可以证明有WXc+b0Yz=- -1当当WXz+b0如果如果Yi=1WXi+b0如果如果Yi=- -1上述表达式可以用下面的不等式统一表示：上述表达式可以用下面的不等式统一表示：Yi(WXi+b)1在满足上述约

7、束条件下，可以通过最小化在满足上述约束条件下，可以通过最小化W2获得具有最大获得具有最大分类间隔的超平面对。也就是说，最大化决策区间的边缘分类间隔的超平面对。也就是说，最大化决策区间的边缘等价于在满足上述约束条件下最小化以下目标函数：等价于在满足上述约束条件下最小化以下目标函数：2)(2WWf或者，在可分情况下，线性或者，在可分情况下，线性SVM的学习任务可以形的学习任务可以形式化描述为以下优化问题：式化描述为以下优化问题：22WMINW受限于受限于Yi(WXi+b)1，i=1，2，N4. 线性可分线性可分SVM的求解过程的求解过程通过标准的拉格朗日乘子方法求解上述优化问题。通过标准的拉格朗日

8、乘子方法求解上述优化问题。首先，必须改写目标函数，考虑施加在解上的约束。新目首先，必须改写目标函数，考虑施加在解上的约束。新目标函数称为该优化问题的拉格朗日函数：标函数称为该优化问题的拉格朗日函数：NiiiiPbXWYWL12) 1)(21其中，其中，i称为称为拉格朗日乘子拉格朗日乘子。拉格朗日函数中的第一项。拉格朗日函数中的第一项与原目标函数相同，而第二项则捕获了不等式约束。与原目标函数相同，而第二项则捕获了不等式约束。（1）求拉格朗日乘子）求拉格朗日乘子i关于关于W、b最小化最小化LP，令，令LP关于关于i所有的导数为零，要所有的导数为零，要求使得约束求使得约束i0（称此特殊约束集为（称此

9、特殊约束集为C1）。）。由于是凸优化问题，它可以等价地求解对偶问题：由于是凸优化问题，它可以等价地求解对偶问题：最大化最大化LP，使得，使得LP关于关于W、b的偏导数为零，并使得的偏导数为零，并使得i0（称此特殊约束集为（称此特殊约束集为C2）。这是根据对偶性得到的，）。这是根据对偶性得到的，即在约束即在约束C2下最大化下最大化LP所得到的所得到的W、b值，与在约束值，与在约束C1下下最小化最小化LP所得所得W、b的值相同。的值相同。令令LP关于关于W、b的导数为零，即：的导数为零，即：由于对偶形式中的等式约束，代入由于对偶形式中的等式约束，代入LP得得拉格朗日乘子有不同的下标，拉格朗日乘子有

10、不同的下标，P对应原始问题，对应原始问题，D对应对应对偶问题，对偶问题，LP和和LD由同一目标函数导出，但具有不同约束。由同一目标函数导出，但具有不同约束。也就是说，线性可分情况下的支持向量训练相当于在也就是说，线性可分情况下的支持向量训练相当于在约束及约束及i0条件下，关于条件下，关于i最大化最大化LD。需要注意的是，该问题仍然是一个有约束的最优化问需要注意的是，该问题仍然是一个有约束的最优化问题，需要进一步使用题，需要进一步使用数值计算技术数值计算技术通过训练样本数据求解通过训练样本数据求解i。NiiiY10（2）求）求W参数参数通过求解出通过求解出W。NiiiiXYW1（3）求）求b参数

11、参数b需满足约束条件为需满足约束条件为Yi(WXi+b)1不等式。不等式。处理不等式约束的一种方法就是把它变换成一组等式处理不等式约束的一种方法就是把它变换成一组等式约束。只要限制约束。只要限制i非负，这种变换是可行的。这种变换导非负，这种变换是可行的。这种变换导致如下拉格朗日乘子约束，称为致如下拉格朗日乘子约束，称为Karuch-kuhn-Tucher（KKT）条件：）条件：i0i(Yi(WXi+b)- -1)=0上述上述KKT条件转化为条件转化为Yi(WXi+b)- -1=0，即：当，即：当Yi=1时，时，b=1- -WXi；当；当Yi=- -1时，时，b=- -1- -WXi。由于由于i

12、采用数值计算得到，可能存在误差，计算出的采用数值计算得到，可能存在误差，计算出的b可能不唯一，通常使用可能不唯一，通常使用b的平均值作为决策边界的参数。的平均值作为决策边界的参数。当求出当求出W、b的可行解后，可以构造出决策边界，分类的可行解后，可以构造出决策边界，分类问题即得以解决。问题即得以解决。【例【例7.67.6】对于二维空间，以表对于二维空间，以表7.14所示的所示的8个点作为训个点作为训练样本，求出其线性可分练样本，求出其线性可分SVM的决策边界。假设已求出每的决策边界。假设已求出每个训练样本的拉格朗日乘子。个训练样本的拉格朗日乘子。点编号点编号iXiYi拉格朗日乘子拉格朗日乘子i

13、x1x210.38580.4687-165.526120.48710.611165.526130.92180.41031040.73820.89361050.17630.0579-1060.40570.3529-1070.93550.81321080.21460.0099-10令令W=(w1，w2)，b为决策边界的参数。这里为决策边界的参数。这里N=8。则：。则：对于训练样本对于训练样本1（Y1=- -1），有：），有：对于训练样本对于训练样本2（Y2=1），有：），有：取取b1、b2的平均值得到的平均值得到b=- -7.93，则决策边界为：，则决策边界为： 6.64x1+9.32x2- -7

14、.93=0对应该决策边界的显示如下图所示。对于训练样本对应该决策边界的显示如下图所示。对于训练样本X=(x1，x2)，若，若6.64x1+9.32x2- -7.930，则划分于类别，则划分于类别1中；中；若若6.64x1+9.32x2- -7.930，则划分于类别，则划分于类别- -1中。中。7.6.2 7.6.2 线性不可分时的二元分类问题线性不可分时的二元分类问题 在实际情况中，很多问题是线性不可分的，如图在实际情况中，很多问题是线性不可分的，如图7.51所所示的样本集便是如此，无法找到一个理想的超平面，能将两示的样本集便是如此，无法找到一个理想的超平面，能将两类样本完全分开。类样本完全分

15、开。由于样本线性不可分，原来对间隔的要求不能达到，由于样本线性不可分，原来对间隔的要求不能达到，可以采用一种称为软边缘的方法，学习允许一定训练错误可以采用一种称为软边缘的方法，学习允许一定训练错误的决策边界。的决策边界。也就是在一些类线性不可分的情况下构造线性的决策也就是在一些类线性不可分的情况下构造线性的决策边界，为此必须考虑边缘的宽度与线性决策边界允许的训边界，为此必须考虑边缘的宽度与线性决策边界允许的训练错误数目之间的练错误数目之间的折中折中。对于线性不可分的问题，原目标函数仍然是对于线性不可分的问题，原目标函数仍然是可用的，但原决策边界不再满足可用的，但原决策边界不再满足Yi(WXi+

16、b)1给定的所有约给定的所有约束。为此使约束条件弱化，以适应线性不可分样本。束。为此使约束条件弱化，以适应线性不可分样本。可以通过在优化问题的约束中引入正值的可以通过在优化问题的约束中引入正值的松弛变量松弛变量来实来实现（松弛变量现（松弛变量用于描述分类的损失），即：用于描述分类的损失），即：2)(2WWfWXi+b1- -i，如果，如果Yi=1WXi+b- -1- -i， 如果如果Yi=- -1其中，对于任何训练样本其中，对于任何训练样本Xi，i0。理解松弛变量理解松弛变量i的含义的含义:显然希望松弛变量显然希望松弛变量最小化（如果最小化（如果=0，则就是前面的线，则就是前面的线性可分问题）

17、。于是，在优化目标函数中使用性可分问题）。于是，在优化目标函数中使用惩罚参数惩罚参数C来来引入对引入对最小化的目标。这样，修改后的目标函数如下：最小化的目标。这样，修改后的目标函数如下：kNiiCWWf122)(这样，求解的问题变为：这样，求解的问题变为： kNiibWCWMIN12,2受限于受限于Yi(WXi)+b)+1)1- -i，i=1，2，N这个优化问题仍然是一个凸优化问题。采用与前一节这个优化问题仍然是一个凸优化问题。采用与前一节类似的方法求解。类似的方法求解。 C是一个必须事先指定的值是一个必须事先指定的值 除了上述软边缘的方法外，还有一种非线性硬间隔方法，除了上述软边缘的方法外，

18、还有一种非线性硬间隔方法，其基本思路是：将低维空间中的曲线（曲面）映射为高维空其基本思路是：将低维空间中的曲线（曲面）映射为高维空间中的直线或平面。数据经这种映射后，在高维空间中是线间中的直线或平面。数据经这种映射后，在高维空间中是线性可分的。性可分的。 SVM有如下主要有如下主要几个特点几个特点：（1）由于）由于SVM的求解最后转化成二次规划问题的求解，的求解最后转化成二次规划问题的求解，因此因此SVM的解是的解是全局唯一的最优解全局唯一的最优解。（2）SVM在解决在解决小样本、非线性及高维模式识别问题小样本、非线性及高维模式识别问题中表现出许多特有的优势中表现出许多特有的优势，并能够推广应用到函数拟合等，并能够推广应用到函数拟合等其他机器学习问题中。其他机器学习问题中。（3）SVM是一种是一种有坚实理论基础有坚实理论基础的新颖的小样本学习的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等，因此不同方法。它基本上不涉及概率测度及大数定律等，因此不同于现有的统计方法。从本质上看，它避开了从归纳到演绎于现有的统计方法。从本质上看，它避开了从归纳到演绎的传统过程，实现了高效的从训练样本到预报样本的的传统过程，实现了高效的从训练样本到预报样本的“转转导推理导推理”，大大简化了通常的分类和回归等问题。，大大简化了通常的分类和回归等问题。（4）SVM的最终决策