《支持向量机理论及其在网络安全中的应用》课件第2章

第2章统计学习理论基础2.1统计学习理论基础2.2最优分类超平面2.3支持向量机2.4小结

2.1统计学习理论基础

2.1.1机器学习

机器学习一种基于数据的学习方法，它主要研究从观测数据(样本)出发寻找规律并构造一个模型，利用该模型可对未知数据或者无法观测的数据进行预测[11]。这种模型就叫做学习机器(LearningMachine)。机器学习的过程就是构建学习机器的过程。一个简单的学习系统如图2.1.1所示[12]。图2.1.1一个简单的学习系统模型

1.学习机器的产生

关于机器学习的研究，可以追溯到20世纪50年代，当时人们就从仿生学的角度开展了研究，希望弄清楚人类大脑及神经系统的学习机理。

2.学习理论基础的创立

Rosenblartt的感知器推动了其他类型的学习机器的研究，如利用自适应学习机、隐马尔可夫模型等来解决实际问题。但这些学习机器只是解决实际问题的工具，并非学习问题的一般模型。

3.神经网络的创立

1986年，研究者提出了同时构造感知器所有神经元的向量系数的方法，即后向传播的方法。这一方法的思想很简单，在修改的模型中，新的神经元的合成是一个连续的函数。

4.统计学习理论

Vapnik等人从六七十年代开始致力于统计学习理论的研

究[15,16,17]。到20世纪90年代中期，随着其理论的不断发展和

成熟，人们研究的重点转移到对神经网络的这种替代方法的

研究上。学习问题可以看做是利用有限数量的观测来寻找待求的依赖关系的问题[1]。学习问题可以一般地表示为输出变量y和输入变量x之间存在的未知依赖关系，即遵循某一未知的概率测度F(x,y)。机器学习问题就是根据l个独立同分布(i.i.d)观测样本：

(2.1.1)在一组函数{f(x,w)}中，求一个最优的函数f(x,w0)，对依赖关系进行估计，使期望风险

(2.1.2)

最小。其中，{f(x,w)}称做预测函数集，w为函数的广义参数。{f(x,w)}可以表示任何函数集。L(y,f(x,w))为由于使用f(x,w)对进行预测而造成的损失函数。不同类型的学习问题有不同形式的损失函数。学习问题的形式化表述涉及面很广，它包括了很多特殊的问题。最基本的机器学习问题有三类：模式识别(分类)、函数逼近(回归估计)和概率密度估计[15]。对于模式识别问题，输出可分别表示为y={0,1}或{1,－1}。被预测函数称作指示函数，损失函数可以定义为

(2.1.3)对于这个损失函数，式(2.1.2)的风险泛函确定了训练机器和指示函数f(x,w)所给出的不同概率。把训练机器的输出和指示函数的输出不同的情况称为分类错误。所以对模式识别问题来讲，学习问题就是根据给定的样本数据，在概率测度F(x,w)未知的情况下，寻找使得分类错误概率最小的函数f(x,w0)。在函数回归估计问题中，y是连续变量，损失函数定义为

(2.1.4)

回归函数就是在损失函数下使风险泛函式(2.1.2)最小的函数。

对于概率密度估计问题，学习的目的是根据训练样本确定x的概率密度，被估计的密度函数记做，此时的损失函数可定义为

(2.1.5)在上面的问题表述中，学习的目标在于使期望风险最小化，但是，由于概率测度F(x,y)未知，我们可以利用的信息只有式(2.1.1)所示的样本，式(2.1.2)表示的期望风险无法计算，因此传统的学习方法中采用了所谓经验风险最小化准则，即采用样本误差定义的经验风险

(2.1.6)作为对式(2.1.2)的估计，设计学习算法使它最小化。对式(2.1.3)所示的损失函数，经验风险就是训练样本错误率；对式(2.1.4)所示的损失函数，经验风险就是平方训练误差；而采用式(2.1.5)所示的损失函数的经验风险最小化准则就等价于最大似然方法。一些经典的方法，如回归问题中的最小二乘法、极大似然法都是经验风险最小化准则在特殊损失函数下的应用。传统的神经网络学习方法也应用了经验风险最小化准则。文献[18]给出了一个实验例子，在有噪声条件下用模型

产生10个样本，分别用一个一次函数和一个二次函数根据经验风险最小化准则去拟合，结果显示，虽然真实模型是二次，但由于样本数有限且受噪声的影响，用一次函数预测的结果却要比二次函数更好。

由此可看出，在有限样本情况下：

(1)经验风险最小并不一定意味着期望风险最小；

(2)学习机器的复杂性不但应与所研究的系统有关，而且还要和有限数目的样本相适应。2.1.2统计学习理论

主要内容包括以下四个方面[13,15]。

(1)经验风险最小化准则下，统计学习一致性(Consistency)的条件；

(2)在这些条件下关于统计学习方法推广性的界的结论；

(3)在这些界的基础上建立的小样本归纳推理准则；

(4)实现新的准则的实际方法(算法)。2.1.3统计学习理论的发展历程

1.学习一致性及条件

定义2.1.1(经验风险最小化一致性)对于指示函数集和概率分布函数，如果下面两个序列概率地收敛到同一极限，即

(2.1.7)

(2.1.8)

则称为经验风险最小化原则对函数集L(y,w)和概率分布函数F(y)是一致的。

定理2.1.1(学习理论的关键定理)设函数集

满足下列条件：

(2.1.9)

那么ERM原则一致性的充分必要条件是：经验风险在整个函数集上以式(2.1.10)所示意义一致收敛于期望风险R(w)。

(2.1.10)此定理是Vapnik和Chervonenkis于1989年提出的。由于这一定理在统计学习理论中的重要性，因此被称做学习理论的关键定理。它把学习一致性的问题转化为式(2.1.10)的一致收敛问题。回顾期望风险和经验风险的定义可知，它既依赖于预测函数集，也依赖于样本的概率分布。定理中的式(2.1.10)称做单侧一致收敛，与此相对应的是双侧一致收敛，即

(2.1.11)

2. VC维

定义2.1.2(随机熵，VC熵)设，是界限损耗函数集。使用这个函数集和训练集，可以构造下列维向量：

定理2.1.2

函数集学习过程双侧一致收敛(满足式(2.1.11))的充分和必要条件是下式成立：

(2.1.12)

换言之，VC熵与观察数的比值应随观察数增加而减少到零。

推论2.1.1

在指示函数集一定的可测条件下，双侧一致收敛的充分和必要条件为

它是式(2.1.12)的特例。在统计学习理论中，收敛速度快的定义为，如果对应任意的，下式都成立

则称渐进收敛的速度是快的。其中c>0是常数。

定义2.1.3(生长函数)函数集的生长函数定义为它是在所有可能的样本集上的最大随机熵，即

(2.1.13)

也就是说，生长函数反映了函数集把l个样本分成两类的最大可能的分法数目。显然，。由于它是在所有可能的样本集中取最大，因此与样本分布无关。

定义2.1.4(退火的VC熵)在讨论函数集的分类能力时，统计学习理论还定义了另外一个重要的指标，就是退火的VC熵，其定义是

(2.1.14)

根据Jensen不等式，有。

因此，VC熵、退火的VC熵和生长函数之间存在如下关系：

(2.1.15)

定理2.1.3

函数集学习过程收敛速度快的充分条件是：

(2.1.16)

定理2.1.4

函数集学习过程一致收敛的充分必要条件是对任意的样本分布，都有

(2.1.17)

且这时学习过程收敛速度一定是快的。

定义2.1.5(指示函数集的VC维的直观定义)假如存在一个有h个样本的样本集能够被一个函数集中的函数按照所有可能的2h种组合分为两类，则此函数集能够把样本数为的样本集打散(Shattering)。指示函数集的VC维就是用这个函数集中的函数所能够打散的最大样本集的样本数目。也就是说，如果存在h个样本的样本集能够被函数集打散，而不存在能被此函数集打散的且有h+1个样本的样本集，则函数集的VC维就是h。如果对于任意的样本数，总能找到

一个样本集能够被这个函数集打散，则函数集的VC维就是无穷大。

3.推广性的界

统计学习理论系统地研究了对于各种类型的函数集、经验风险和期望风险之间的关系，即推广性的界[25]。关于两类分类问题，结论是：对指示函数集中的所有函数(包括使经验风险最小的函数)，经验风险和期望风险之间以至少

的概率满足如下关系[1]：

(2.1.18)

其中h是学习机器函数集的VC维，l是样本数。这一结论从理论上说明了学习机器的期望风险是由两部分组成的：第一部分是经验风险(训练误差)；另一部分称做置信范围。它和学习机器的VC维及训练样本数有关。式(2.1.18)可以简单地表示为

(2.1.19)它表明，在有限训练样本下，学习机器的VC维h越高(复杂性越高)则置信范围越大，导致真实风险与经验风险之间的差别可能越大。这就是为什么会出现过学习现象的原因。式(2.1.19)说明机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的期望风险，即对未来样本有较好的推广性。

4.结构风险最小化准则

从前面的讨论可以看到，传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的，因为机器学习过程不仅需要最小化经验风险，同时也要最小化置信范围。事实上，在传统方法中，我们选择学习模型和算法的过程就是优化置信范围的过程，如果选择的模型比较适合现有的训练样本(相当于值适当)，则可以取得比较好的效果。比如在神经网络中，需要根据问题和样本的具体情况来选择不同的网络结构(对应不同的VC维)，然后进行经验风险最小化。在模式识别中，选定了一种分类器形式(比如线性分类器)，就确定了学习机器的VC维。实际上，这种做法是在式(2.1.19)中首先通过选择模型来确定，然后固定，通过最小化经验风险来求最小期望风险。因为缺乏对的认识，这种选择往往是根据先验知识和经验进行的，造成了神经网络等方法对使用者“技巧”的过分依赖。对于模式识别问题，虽然很多问题并不是线性的，但当样本数有限时，我们用线性分类器往往能得到不错的结果，其原因就是线性分类器的VC维比较低，有利于在样本较少的情况下得到小的置信范围。从上述分析可看到，要对风险的界式(2.1.18)(或式(2.1.19))右边的两项同时最小化，必须使VC维成为一个

可以控制的变量。统计学习理论提出了一种新的策略，即把函数集分解为一个函数子集序列：使各个子集按照VC维的大小排列为

在每个子集中寻找经验风险最小的函数，在子集间折中考虑经验风险和置信范围，取得期望风险的最小化。这种思想称做结构风险最小化原则。如图2.1.2所示，综合考虑经验风险与置信范围的变化，可以求得最小的真实风险边界，它所对应的函数集的中间子集S*可以作为具有最佳推广能力的函数集合。图2.1.2结构风险最小化原理图根据这一分析，可以得到以下两种运用结构风险最小化归纳原理构造的学习机器的思路。

(1)给定了一个函数集合，按照上面的方法来组织一个嵌套的函数结构，在每个子集中求取最小经验风险，然后选择经验风险与置信风险之和最小的子集。但是当子集数目较大的时候，此方法较为费时，甚至不可行。

(2)构造函数集合的某种结构，使得在其中的各函数子集均可以取得最小的经验风险(如使得训练误差为0)，然后选择适当的子集使得置信风险最小，则相应的函数子集中使得经验风险最小的函数就是所求解的最优函数。

2.2最优分类超平面

2.2.1最优超平面

定义2.2.1(最优超平面)假定训练数据,

，可以被超平面

(2.2.1)

无错误地分开，且距离超平面最近的向量与超平面间的距离最大，则称向量集合被最优超平面(最大间隔超平面)分开，如图2.2.1所示。图2.2.1最优分类超平面为了描述分类超平面，使用不等式和

，合并为一个紧凑的形式为

(2.2.2)

容易验证，最优超平面就是满足条件式(2.2.2)且使得

(2.2.3)

关于向量w和标量b最小化的超平面。2.2.2Δ-间隔分类超平面

定义2.2.2(Δ-间隔分类超平面)如果超平面,

以如下的形式将向量x分类：

(2.2.4)

则称之为Δ－间隔分类超平面。

显然，式(2.2.2)定义的就是Δ－间隔分类超平面，其中。

定理2.2.1

设向量位于一个半径为R的球中，那么Δ－间隔分类超平面集合的VC维h有下面的界：

(2.2.5)

推论以概率1－h可以断定，测试样本不能被Δ－间隔超平面正确分类的概率有下面的界：

(2.2.6)

其中，，m是没有被Δ－间隔超平面正确分类的训练样本数目，h是VC维的界。2.2.3构造最优超平面

1.构造线性可分最优超平面

定义2.2.3(线性可分问题)考虑训练数据,

，，若存在，和正数e，使得对所有使的下标i，有；而对于所有使的下标，有，则称训练数据线性可分，同时称相应的分类问题是线性可分的[27]。

为了构造最优超平面，需要用系数的模最小的超平面把属于两个不同类的样本集中的向量xi分开。为了得到这样的超平面，需要在约束条件为

(2.2.7)

时最小化泛函为

(2.2.8)它的解由Lgarnage泛函的鞍点给出：

(2.2.9)

其中为Lagrnage乘子。在鞍点上，解必须满足以下条件：

(2.2.10)进一步考虑式(2.2.10)可得到：

(1)对最优超平面，系数必须满足约束

(2.2.11)

(2)最优超平面(向量)是训练集中的向量的线性组合：

(2.2.12)根据优化理论的KKT(Kuarsh-Kuhn-Tukcer)条件，最优超平面要满足下面的等式：

(2.2.13)

将w0的表达式(支持向量展开式)代入Lgarnage泛函式(2.2.9)，考虑KKT条件，可以得到下面的泛函：

(2.2.14)问题变为在非负象限

(2.2.15)

以约束条件

(2.2.16)

来最小化泛函式(2.2.14)。为了构造最优超平面，只需求解一个简单的二次规划。设是二次规划的最优解，与最优超平面对应的向量w0的模为

(2.2.17)

基于最优超平面的分类规则就是下面的指示函数：

(2.2.18)常数b0可以由支持向量根据KKT条件得到：

(2.2.19)

其中，表示属于第一类的某个支持向量，表示属于第二类的某个支持向量[28]。

2.构造线性不可分最优超平面

为了在数据为线性不可分的情况下构造最优超平面，引入非负变量和函数，其中参数。

在约束条件

(2.2.20)

(2.2.21)

下最小化泛函。对于足够小的，这个优化问题的解定义了这样一个超平面，它的参数属于式(2.2.21)定义的子集，即由常数

所决定的结构，它使得训练错误数最少。

3.构造Δ-间隔分类超平面在约束条件为时

最大化泛函

(2.2.22)

4.构造软间隔超平面

(2.2.23)

只是约束条件略有不同：

(2.2.24)

2.3支 持 向 量 机

支持向量机实现了这样的思想：通过某种事先选择的非线性映射将输入向量映射到一个高维特征空间Z，在这个空间中构造最优分类超平面，如图2.3.1所示[13]。图2.3.1支持向量机实现的思想2.3.1高维空间中的推广能力

(2.3.1)

2.3.2核函数

在Hilbert空间中，内积的一般表达式是

(2.3.2)

其中X是输入空间中的向量x在特征空间中的映射，

称为核函数(KernelFunction)。

定理2.3.2(Mercer定理)要保证L2下的对称函数

能以正的系数展成

(2.3.3)

即描述了某个特征空间中的一个内积，其充分必要条件是对使得的所有，以下条件成立：

(2.3.4)支持向量机中不同的核函数将形成不同的算法，目前研究最多的核函数主要有以下三类。

(1)多项式核函数：

(2.3.5)

其中q为自由度，所得到的是q阶多项式分类器。

(2)径向基函数(RBF)：

(2.3.6)

其中，g为形状参数，所得分类器与传统RBF方法的重要区别是，这里每个基函数中心对应一个支持向量，它们及输出权值都是由算法自动确定的。

(3) Sigmoid函数：

(2.3.7)

其中，S(·)为Sigmoid函数，这时SVM实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在困扰神经网络方法的局部极小点问题。2.3.3构造支持向量机

根据核函数的理论，就可以构造在输入空间中的非线性决策函数：

(2.3.8)

其中SV是支持向量，式(2.3.8)等价于在高维特征空间

中的决策函数

(2.3.9)在线性可分的情况下，要求得系数，只需寻找下列泛函的最大值(式(2.3.10))：

(2.3.10)

其约束条件是：

(2.3.11)在线性不可分情况下，则在下列约束条件(式(2.3.12))下最大化泛函式(2.3.10)：

(2.3.12)使用式(2.3.8)类型的决策函数构造的学习机器称为支持向量机，构造支持向量机的复杂度取决于支持向量的数目而非特征空间的维数。概括地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，在这个空间中求(广义)最优分类面。SVM分类函数形式上类似于一个神经网络，输出是中间节点的线性组合，每个中间节点对应一个支持向量，如图2.3.2所示。图2.3.2支持向量机示意图2.3.4支持向量分类机下面给出用数学语言描述的分类问题定义[27]。

定义2.3.1(两类分类问题)给定训练集

(2.3.13)

其中，，。根据训练集寻找空间上的一个实值函数，使得决策函数

(2.3.14)

可推断任一输入x对应的输出y。图2.3.3使用直线完全划分的线性分类机图2.3.4使用直线近似划分的一般分类机图2.3.5使用曲线划分的一般分类机由训练集给出的分类问题可分为多种情况，由此对应了使用支持向量机理论所构造的多种分类机，线性硬间隔支持向量分类机处理的是线性可分问题。把它推广改造于线性不可分问题有两种方式：线性软间隔支持向量分类机和非线性硬间隔支持向量分类机。综合这两种方式，便得到了非线性软间隔支持向量分类机，即通常所说的C－支持向量分类机。几种支持向量分类机的逻辑关系如图2.3.6所示[27]。图2.3.6几种支持向量分类机的逻辑关系

定义2.3.2(多类分类问题)根据给定的训练集

(2.3.15)

其中，，，寻找一个决策函数f(x)：。2.3.5支持向量回归机

首先给出一个简单的回归问题：考虑两个量x和y的关系。设已测得若干个x值和其所对应的y值：

(2.3.16)图2.3.7简单回归问题的几何示意

定义2.3.3(回归问题)设给定训练集

(2.3.17)

其中，，。假定训练集是按

上的某个未知概率分布选取的独立同分布的样本点，又设给定损失函数，试寻求一个函数，使得期望风险

(2.3.18)

达到极小[27]。

e－不敏感损失函数为

(2.3.19)当然根据实际回归问题的需要，我们还可以选择其他类型的损失函数。不同的损失函数对应不同类型的支持向量回归机模型。下面简单给出采用一般的损失函数时的支持向量回归模型。为了和e-不敏感损失函数具有统一的形式，这里定义一般的损失函数为下面的形式：

(2.3.20)

其中，可以取不同的函数类型。采用非线性映射将样本集映射到高维空间，然后用核函数代替高维空间中的内积运算。于是，一般损失函数下的回归问题为

(2.3.21)

约束为

(2.3.22)

(2.3.23)

(2.3.24)

其中，可取如下的形式。(1)拉普拉斯损失函数：