第3章智能计算与识别理论基础 

本章给出多源信息融合赖以发展的智能计算与识别理论基础，大部分内容比较新。
3.1概述
3.1.1模式识别的一般概念


模式识别是人类自然智能的一种基本形式。所谓“模式”就是指人类按照时间和空间中可观察的自然属性和认识属性对客观事物的划分。所谓“模式识别”就是依据某些观测获得的属性把一类事物和其他类型的事物区分的过程。例如，人们依据视觉、听觉、触觉等感官所接收的信息，能够正确认识外界事物，并能把一类事物与其他事物正确区分。
然而，我们现在研究的“模式识别”主要属于人工智能的范畴。随着20世纪40年代计算机的出现以及50年代人工智能的兴起，一种以计算机为工具进行“模式识别”的理论和方法便发展起来了，并迅速成为一门新的学科。
目前，模式识别的理论研究主要集中在两方面： 一是关于生物体（包括人）感知客观事物机理的研究，这是生物学家、生理学家、心理学家、神经生理学家等的研究内容，属于认知科学的范畴； 二是针对给定的任务，关于计算机实现模式识别的有关理论和方法研究，这是数学家、信息学家和计算机科学家的研究内容，属于应用信息科学的范畴。
用计算机实现的模式识别系统，一般由三个相互关联而又有明显区别的过程组成，即数据生成、模式分析和模式分类。所谓数据生成是将原始信息转换为向量，成为计算机易于处理的形式； 所谓模式分析是对数据进行加工，包括特征选择、特征提取、数据维数压缩和决定可能存在的类别等； 模式分类则是利用模式分析所获得的信息，对计算机进行训练，从而根据判别准则，以实现模式的分类。
现在通用的模式识别方法有两种，即统计模式识别方法和结构（句法）模式识别方法。所谓统计模式识别方法，就是对模式的统计分类方法，即结合统计概率论的Bayes决策系统进行模式识别的技术，又称决策理论识别方法。利用模式与子模式分层结构的树状信息所完成的模式识别工作，就是结构模式识别或句法模式识别。
模式识别系统已经成功地应用于字符识别、语音识别、指纹识别、人脸识别、医学图像分析、工业产品检测等许多方面。然而，模式识别方法的研究目前仍然是针对具体应用对象的，至今还难以发展成为一种统一的模式识别理论与方法。
3.1.2智能学习与统计模式识别
统计模式识别的基本原理，是根据先验知识，定义模式空间为


Ω={ω1,ω2,…,ωM}（311）


其中，ωk表示一个模式类； 同时可定义样本特征向量（或称为待识别模式）为


Xi=［xi1,xi2,…,xid］T∈XRd,i=1,2,…,N（312）


其中X表示样本特征向量空间，上标T表示转置； N 为样本点数； xij是一个样本特征，d为样本特征数； 所谓统计模式识别方法就是根据属性或特征来定义某个距离函数以判别样本Xi 属于哪个ωk。或者说，把有特征相似性的样本在模式空间中划分为互相接近的若干模式类，并以特征进行“聚类”，从而达到模式分类的目的。
统计模式识别的主要方法有： 判别函数法、k近邻分类法、非线性映射法、特征分析法、主因子分析法等。在统计模式识别中，Bayes决策规则从理论上解决了最优分类器的设计问题，但其实施却必须首先解决更困难的概率密度估计问题。反向传播（BP）神经网络直接从观测数据（训练样本）学习，是更简便有效的方法，因而获得了广泛的应用。但它是一种启发式技术，缺乏坚实的理论基础。统计推断理论研究所取得的突破性成果导致现代统计学习理论——Vapnik Chervonenkis（VC）理论的建立，该理论不仅在严格的数学基础上圆满地回答了人工神经网络中出现的理论问题，而且导出了一种新的学习方法——支持向量机方法。
所谓智能学习就是从样本获得分类的一类数学方法，这些方法具有自学习的智能。
20世纪70年代，波兰学者Pawlak等提出了粗糙集（rough sets）理论，此后，许多科学家在粗糙集的理论和应用方面做了大量的研究工作。至今，粗糙集理论已经成为智能学习的一类标准方法。粗糙集理论是处理模糊和不确定性的一个新的数学工具，用于数据分类分析。粗糙集理论分析的主要目的在于由获取的数据综合出近似的概念。本章3.2节将详细讨论粗糙集理论及应用。然而，Pawlak的粗糙集理论是基于等价关系建立起来的，也就是说分类是严格的，但实际问题往往并不能进行严格分类，于是就引入广义粗糙集（generalized rough sets）的概念，并在此基础上建立容差关系的分类方法。20世纪70年代初，Dempster 和Shafer 建立的一套数学理论，称为DS证据理论（evidence theory），这一理论的核心是超越了概率统计推断的理论框架，可以适应于专家系统、人工智能、模式识别和系统决策等领域的实际问题。而且这一理论的发展很快成为智能学习和多源信息融合的重要组成部分。本章3.3节将对DS证据理论进行详细研究。
G.Matheron于1975年出版了《随机集与积分几何学》一书，从而提出了所谓随机集（random sets）理论，现在已经成为智能学习的又一重要研究方向。随机集处理的是随机集合问题，集值的引入带来许多令人意想不到的奇特结果，有可能发展成为一种更有力的工具。因为它对异类多源信息融合有特别的意义，本章3.4节将专门讨论随机集理论。进而，我们还将介绍随机有限集理论的基本知识。
20世纪90年代中期，统计学习理论和支持向量机（support vector machine）算法的深入研究和成功应用引起了广泛的关注。支持向量机算法具有比较坚实的理论基础和良好的推广能力，并在手写数字识别和文本分类等方面取得了良好的应用效果。特别是利用满足Mercer 条件的核函数实现非线性分类，对于模式识别而言具有划时代的意义。
Bayes网络是另外一种用于智能推断的工具，本章3.7节将进行简单的讨论。
模式识别发展至今，人们已经建立了各种针对具体应用问题的模型和方法，但仍然没有得到对所有模式识别问题都适用的统一模型和统一方法。我们现在拥有的只是一个工具箱，所要完成的工作就是结合具体的问题，把统计模式识别或句法模式识别结合起来，把模式识别方法与人工智能中的启发式搜索方法结合起来，把模式识别方法与支持向量机的机器学习方法结合起来，把人工神经元网络与各种已有技术以及人工智能中的专家系统、不确定推理方法结合起来，深入掌握各种工具的效能和应有的可能性，互相取长补短，不断开创模式识别应用的新局面。
3.2粗糙集理论基础
粗糙集理论由Zdzislaw Pawlak在20世纪80年代早期提出［34］，用于数据分类分析。这些数据可以来自量测，也可以来自人类专家。粗糙集理论分析的主要目的在于由获取的数据综合出近似的概念。
3.2.1信息系统的一般概念
定义3.2.1 一个数据表A=(U,A)称为是一个信息系统（information system），其中U={x1,x2,…,xn}称为对象集（set of objects），A={a1,a2,…,am}称为属性集（set of attributes），都是非空有限集合； 而a: U→Va,a∈A描述了对应关系，其中集合Va是属性a的值集（value set）。
例题3.2.1设有一个信息系统，示于表321，其中有七个对象，两个属性。

表321信息系统A=(U,A)



案例（U）年龄段（a1）近三年患病次数（a2）

x116~3050
x216~300
x331~451~25
x431~451~25
x546~6026~49
x616~3026~49
x746~6026~49

注意，表中案例3和4，以及案例5和7具有完全相同的条件值。在利用这些属性的前提下，这些案例就是成对难识别的案例。□
定义3.2.2一个决策系统（decision system）就是形式如A=(U,A∪{d})的信息系统，其中dA称为决策属性（decision attribute），相应地把A中的元素称为条件属性（conditional attribute），或简称为条件（condition）。
决策属性通常取值为二值，即“是”或“否”（1或0），但也可以取多值。
例题3.2.2针对例题3.2.1，增加决策属性，见表322，其中决策是决定是否复查，所以决策属性取二值。

表322决策系统A=(U,A∪{d})



案例（U）年龄段（a1）近三年患病次数（a2）复查（d）

x116~3050是
x216~300否
x331~451~25否
x431~451~25是
x546~6026~49否
x616~3026~49是
x746~6026~49否

请注意，表中案例x3和x4，以及案例x5和x7仍然具有完全相同的条件值。但第一对取相反的决策值，而第二对取相同的决策值。□
由决策表就可以综合出如下规则： “如果年龄在16~30年龄段，近3年来患病50次，身体复查是必需的。”
在许多应用中，有一种分类结果是已知的，就可以把这种后验知识用决策属性来表示，把这一过程就说成是有监督学习过程。
3.2.2决策系统的不可分辨性
信息系统的知识发现问题本质上是按照属性特征给对象进行分类的问题。为此引入有关关系的概念［1］。
定义3.2.3设有对象集U，其笛卡儿积的子集RU×U就称为U上的一个二元关系R。进而，如果这个二元关系还具有如下特性:
（1） 自返性，如果x∈U（x,x,）∈R； 
（2） 对称性，如果（x,y）∈R（y,x）∈R； 
（3） 传递性，如果（x,y）,（y,z）∈R（x,z）∈R，则称其为等价关系。
定义3.2.4设R是定义在对象集U上的一个等价关系，x∈U的一个等价类定义为


R(x)Δ{y∈U: (x,y)∈R}（321）


定义3.2.5对象集U的某些子集形成的集类U={UiU: i∈I}，如果
（1）∪i∈IUi=U,I是指标集合； 
（2） 对于任意i≠jUi∩Uj=，则称U为U的一个划分。
引理1设R是定义在对象集U上的一个等价关系，R(x)是x∈U的等价类，如果y∈R(x)，则必然有R(y)=R(x)。
证明见文献［1］。▉
引理2设R是定义在对象集U上的一个等价关系，对于x,y∈U，如果R(y)∩R(x)≠，则必然有R(y)=R(x)。
证明见文献［1］。▉
引理3设R是定义在对象集U上的一个等价关系，R(x)是x∈U的等价类，则


∪x∈UR(x)=U（322）


证明见文献［1］。▉
定理3.2.1定义在对象集U上的一个等价关系R，确定了U对等价类的一个划分； 反之，U的任一划分也定义了U上的一个等价关系。
证明见文献［1］。▉
定义3.2.6对象集U按等价关系R形成的等价类所构成的集类称为U关于R的商集，记为U/R。
根据定理3.2.1，商集U/R实际上就是U按R的一个划分。
例题3.2.3设U=Z+表示全体非负整数集合，其上定义了等价关系R如下


(x,y)∈Rx-y能被3整除，x,y∈U


容易验证R是等价关系： ①自返性,x∈Ux-x=0(x,x)∈R; ②对称性,x,y∈U,(x,y)∈Rx-y能被3整除y-x能被3整除，即(y,x)∈R； ③传递性,(x,y),(y,z)∈Rx-y,y-z能被3整除x-z=(x-y)+(y-z)能被3整除，即(x,z)∈R。于是可以得到三个等价类:


R(1)={1,4,7,10,…},R(2)={2,5,8,11,…},R(3)={0,3,6,9,…}


而{R(1),R(2),R(3)}就是U按R的一个划分，即U/R={R(1),R(2),R(3)}。□
一个决策系统（即决策表）表达了有关模型的所有知识。这个决策表的一部分可能没有必要那样大，因为至少按两种方式衡量有多余，即相同的或不可识别的对象可能被表示了几次，或某些属性可能是多余的。
定义3.2.7设A=(U,A)是一个信息系统，与任意BA相联系的等价关系定义为


INDA(B)Δ{(x,x′)∈U×U: a∈B,a(x)=a(x′)}（323）


称其为B不可分辨关系（Bindiscernibility relation）。如果(x,x′)∈INDA(B)，那么按B的属性，x和x′是不可分辨的。B不可分辨关系的等价类记为［x］B。
如果不引起混淆的话，B不可分辨关系的下标A可以略去。
例题3.2.4对于表321，条件属性A的非空子集有B1={a1}={年龄段}、B2={a2}={近三年患病次数}，以及B3={a1,a2}={年龄段，近三年患病次数}，从而有如下三个B不可分辨关系


IND(B1)={{x1,x2,x6},{x3,x4},{x5,x7}}

IND(B2)={{x1},{x2},{x3,x4},{x5,x6,x7}}

IND(B3)={{x1},{x2},{x3,x4},{x5,x7},{x6}}


而 ［x1］B1={x1,x2,x6}，［x1］B2={x1}； ［x6］B2={x5,x6,x7}，［x6］B3={x6},等等。□
3.2.3集合近似
定义3.2.8设A=(U,A)是一个信息系统，BA，XU，定义U的子集合


B(X)Δ{x∈U∶［x］BX}（324）


称为集合X的B下近似（Blower approximation）； 而U的另一子集合


(X)Δ{x∈U∶［x］B∩X≠}（325）


称为集合X的B上近似（Bupper approximation）。
B(X)中的对象是基于B中的知识确定性地分类成X中的元； 而(X)中的对象是基于B中的知识仅仅分类成X中可能的元。
定义3.2.9集合


BNB(X)Δ(X)-B(X)（326）


称为X的B边界区域（Bboundary region），是由不能基于B中的知识确定性地分类成X中元的对象组成。而


OTB(X)ΔU-(X)（327）


称为X的B外部区域（Boutside region），是由基于B中的知识确定性地分类成不属于X中元素的对象组成。
如果对象集合U一个子集X的B边界区域非空，则称其为粗糙集（rough set），或简称为粗集； 否则，如果其B边界区域是空集，则称其为明晰集（crisp set）。
例题3.2.5最常见的情况是按照条件属性综合决策类。在表322中，设结果集是


W={x∈U:  d(x)={是}}={x1,x4,x6}U


于是得到： A(W)={x1,x6}是集合W的A下近似，表示其等价类在W中的对象集合；  (W)={x1,x3,x4,x6}是集合W的A上近似，表示其等价类与W相交非空的对象集合； BNA(W)={x3,x4}是W的A边界区域，是由不能基于A中的知识确定性地分类成W中元素的对象组成； OTA(W)={x2,x5,x7}，W的A外部区域，是由基于A中的知识确定性地分类成不属于W中元素的对象组成。所以W是一个粗集，因为它的边界区域非空。□
集合近似图形表示如图321所示。


图321集合近似的图形表示


定理3.2.2设A=(U,A)是一个信息系统，BA，XU，则有： 
（1） B(X)X(X)（328）
（2） B()=()=，B(U)=(U)=U（329）
（3） (X∪Y)=(X)∪(Y)，B(X∩Y)=B(X)∩B(Y)（3210）
（4） XYB(X)B(Y)且(X)(Y)（3211）
（5） B(X∪Y)B(X)∪B(Y)，(X∩Y)(X)∩(Y)（3212）
（6） B(U-X)=U-(X)，(U-X)=U-B(X)（3213）
（7） B(B(X))=(B(X))=B(X)，((X))=B((X))=(X)（3214）
证明我们只证明式（328）和式（3210），其他可以类似证明。
（1） x∈B(X)［x］BXx∈X［x］B∩X≠x∈(X)
（3） x∈(X∪Y)x∈U,［x］B∩(X∪Y)≠［x］B∩X≠或［x］B∩Y≠
x∈(X)或x∈(Y)x∈(X)∪(Y)
x∈B(X∩Y)x∈U,［x］B(X∩Y)［x］BX且［x］BYx∈B(X)，且x∈B(Y)x∈B(X)∩B(Y)▉



图322表322决策系统集合
近似特性的图形表示

显然，集合的下近似和上近似分别是由不可分辨关系产生的拓扑上集合的内部和闭包。图322给出了表322决策系统集合近似特性的图形表示。
定义3.2.10可以定义如下四种粗集： 
（1） X是粗糙B可定义的（roughly Bdefinable），当且仅当B(X)≠且(X)≠U； 
（2） X是内部B不可定义的（internally Bundefinable），当且仅当B(X)=且(X)≠U； 
（3） X是外部B不可定义的（externally Bundefinable），当且仅当B(X)≠且(X)=U； 
（4） X是完全B不可定义的（totally Bundefinable），当且仅当B(X)=且(X)=U。
X是粗糙B可定义的集合，就意味着借助于集合B，就能确定U中的某些元属于X，以及U中的另外一些元属于U-X。
X是内部B不可定义的集合，就意味着利用集合B，我们就能确定U中的某些元属于U-X，但不能确定U中的任何元是否属于X。
X是外部B不可定义的集合，就意味着利用集合B，我们就能确定U中的某些元属于X，但不能确定U中的任何元是否属于U-X。
X是完全B不可定义的集合，就意味着利用集合B，我们既不能确定U中的任何元是否属于X，也不能确定U中的任何元是否属于U-X。
定义3.2.11粗集也可以用如下系数进行数值表示： 


αB(X)=|B(X)||(X)|（3215）


αB（X）称为近似精度（accuracy of approximation），其中|X|表示集合X的势（当其为有限集时，就是所包含元的个数）； 而


1-αB(X)（3216）


称为近似粗糙度（roughness of approximation）。
显然，0≤αB(X)≤1。如果αB(X)=1，X关于属性集合B是明晰集，或称关于B是精确的（precise）； 否则，αB(X)<1，X关于属性集合B是粗集，或称关于B是含糊的（vague）。
3.2.4属性约简
前一节我们研究了等价类的数据约简问题，即利用给定的属性，在对象集中建立不可分辨的等价类，即完成聚类。我们面临的另一类问题是尽可能使条件属性集变小，并保留原有属性集的分类能力，这就是属性约简（attribute reduction）的问题。然而，计算等价类是容易的，求得最小约简子集（即在所有约简子集中具有最小集合势的约简子集）却是一个NP难题。事实上，这正是把粗集理论应用于实际的一个瓶颈问题。已经发展了一些启发式算法，除了属性集合很大的情况外，可以在能接受的时间范围内计算充分多的约简子集。
例题3.2.6考虑表323的决策表，A′=（U,{文凭，经历，外语，介绍人意见}∪{决策}），我们只考虑条件属性，即信息系统A=（U,{文凭，经历，外语，介绍人意见}）。为了简单起见，每个等价类只包含一个元。

表323招聘问题： 一个不可约简的决策表



对象（U）文凭（d）经历（e）外语（f）介绍人意见（r）决策（dc）

x1MBA中通过很好接收
x2MBA低通过不明确拒绝
x3MCE低通过好拒绝
x4MSc高通过不明确接收
x5MSc中通过不明确拒绝
x6MSc高通过很好接收
x7MBA高否好接收
x8MCE低否很好拒绝

注： MBA： 工商硕士； MCE: 土木工程硕士； MSc： 硕士。

似乎有一个最小的属性集{e,r}，用它识别目标与利用全部属性集识别目标是一样的。不妨利用全部属性集和利用属性集{e,r}来建立不可分辨关系，二者结果是一样的。具有这种特性的最小属性集的结构马上就显现出来了。□
定义3.2.12给定一个信息系统A=（U,A），它的一个约简（reduct）就是一个最小属性集BA，使得INDA(B)=INDA(A)。
换句话说，一个约简集就是属性集A中能保留对总对象集合划分特性的最小属性集合。因此，约简集的分类能力与总属性集的分类能力相同。
定义3.2.13给定一个具有n个对象的信息系统A=（U,A），它的可分辨矩阵（discernibility matrix）就是一个n×n阵C={cij}，且


cij={a∈A: a(xi)≠a(xj)},i,j=1,2,…,n（3217）


其中每个元都由一组属性构成，取决于对象xi与xj属性的不同。
定义3.2.14给定信息系统A=（U,A），它的可分辨函数fA定义为m个Boolean变量a1,a2,…,am（相应于属性a1,a2,…,am）的Boolean函数，定义为


fA（a1,a2,…,am）=∧{∨cij: 1≤j≤i≤n,cij≠}（3218）


其中cij={a: a∈cij}； 而∧表示逻辑“与”运算，∨表示逻辑“或”运算。
注fA的所有主蕴涵（prime implicant）构成的集合确定了A的所有约简构成的集合。所谓Boolean函数f的一个蕴涵就是字符（变量或者其“非”）间的某种关联，使得在变量的任意值v条件下字符取值为“真”时，函数f在v条件下的取值也为“真”。主蕴涵就是最小的蕴涵。我们只对单调Boolean函数的蕴涵感兴趣，因为这些函数不是由“非”来确定。
例题3.2.7仍考虑表323的决策表所定义的信息系统A=（U,A），它的可分辨矩阵如表324所示。

表324可分辨矩阵C={cij}



矩阵［x1］［x2］［x3］［x4］［x5］［x6］［x7］［x8］

［x1］
［x2］e,r
［x3］d,e,rd,r
［x4］d,e,rd,ed,e,r
［x5］d,rd,ed,e,re
［x6］d,ed,e,rd,e,rre,r
［x7］e,f,re,f,rd,e,fd,f,rd,e,f,rd,f,r
［x8］d,e,fd,f,rf,rd,e,f,rd,e,f,rd,e,fd,e,r

而可分辨函数是


fA（d,e,f,r）=(e∨r)(d∨e∨r)(d∨e∨r)(d∨r)(d∨e)(e∨f∨r)

(d∨e∨f)(d∨r)(d∨e)(d∨e)(d∨e∨r)(e∨f∨r)

(d∨f∨r)(d∨e∨r)(d∨e∨r)(d∨e∨r)(d∨e∨f)

(f∨r)(e)(r)(d∨f∨r)(d∨e∨f∨r)

(e∨r)(d∨e∨f∨r)(d∨e∨f∨r)

(d∨f∨r)(d∨e∨f)

(d∨e∨r)


其中每个字符相应于每个属性，而每个括号内就是Boolean表达式的联结； 而“与”运算符号均省略。经过函数的简化计算，结果就是fA（d,e,f,r）=er（即e∧r）。这与前述直观的约简结果是一致的。
注意，可分辨函数中的每一行相应于可分辨矩阵的每一列。而可分辨矩阵是一个对称阵，对角元为空集。于是，倒数第二行就意味着第六个对象（更确切地说是第六个等价类），可以根据文凭（d）、外语（f）和介绍人意见（r）中的任意一个属性与第七个对象进行识别； 可以根据文凭（d）、经历（e）和外语（f）中的任意一个属性与第八个对象进行识别。□
定义3.2.15如果在构造Boolean函数时，把Boolean变量的联结限制在可分辨矩阵中的k列，而不是所有的列，得到的函数称为k相对可分辨函数（krelative discernibility function）； 而由k相对可分辨函数得到的主蕴涵集就确定了A=(U,A)的所有k相对约简（krelative reducts）集。
 这样的约简展现了由其他对象识别xk∈U（更确切地说是［xk］U）所需要的最小信息量。
     利用上述概念，有监督学习问题（即分类结果已知的问题）就是求取决策d的值，这个值应当赋予新的对象，而这个对象的描述借助于条件属性。我们经常要求用来定义对象的属性集达到最小，例如，表323中出现了两个最小属性集{经历（e），介绍人意见（r）}和{文凭（d），经历（e）}，都唯一地定义了对象隶属的决策类。相应的可分辨函数是相对于决策的。现在给出这个概念的形式化描述。
定义3.2.16设决策系统A=(U,A∪{d})给定，映像d(U)={k: d(x)=k,x∈U)的势称为d的秩（rank），记为r(d)，此处假定决策d的值集为Vd={v(1)d,v(2)d,…,v(r(d))d}。
相当多的决策系统中d的秩是2，例如，表323中的决策属性中就是{是，否}或{接收，拒绝}。然而d的秩可以是任意自然数。例如，表323中的决策属性中可以是{接收，保留，拒绝}，则d的秩就成为3。
定义3.2.17决策集d确定了对象集U的一个划分


CLASSA={X（1）A,X（2）A,…,X（r（d））A}


其中等价类X（k）A={x∈U: d(x)=v(k)d},k=1,2,…,r(d)； 这个划分被称为决策系统按决策的对象分类（classification of objects determined by the decision）； 相应地称X（k）A为A的第k个决策类（kth decision class），且等价类XA(u)={x∈U: d(x)=d(u)},u∈U。
例题3.2.8考虑表322的决策表，有如下按决策的对象分类


CLASSA={X（是）A,X（否）A}，X（是）A={x1,x4,x6}，X（否）A={x2,x3,x5,x7}


再考虑表323的决策表所定义的决策系统，则有如下按决策的对象分类


CLASSA={X（收）A,X（拒）A}，X（收）A={x1,x4,x6,x7}，X（拒）A={x2,x3,x5,x8} 

□
定义3.2.18设{X（1）A,X（2）A,…,X（r（d））A}是决策系统A的决策类，则集合


B(X（1）A)∪B(X（2）A)∪…∪B(X（r（d））A)（3219）


称为是A的B正区域（Bpositive region），记为POSB(d)。
例题3.2.9考虑决策表322所定义的决策系统A=（U,A∪{d}），则有如下结果： A(X（是）A)∪A(X（否）A)≠U，这是因为对于对象x3,x4，决策并不唯一。再考虑决策表323所定义的决策系统A=（U,A∪{d}），则有A(X（收）A)∪A(X（拒）A)=U，因为此时所有的决策都是唯一的。□
定义3.2.19决策系统的这一重要特性可以形式化描述如下： 设A=（U,A∪{d}）是一个决策系统，而A中的广义决策（generalized decision）定义为函数A： U→P(Vd)，而


A(x)={i: x′∈U,使得(x,x′)∈IND(A),且d(x)=i}（3220）


决策系统A称为是相容的（确定性的），如果对任意x∈U，总有|A(x)|=1； 否则，决策系统A称为是不相容的（不确定性的）。
     容易看出，一个决策系统A是相容的，当且仅当POSA(d)=U。进而，对于任意一对非空集合B,B′A，如果B=B′，则POSB(d)=POSB′(d)。
例题3.2.10考虑决策表322所定义的决策系统A=（U,A∪{d}），其A正区域是U的一个子集； 而表323所定义的决策系统A=（U,A∪{d}），其A正区域是整个U。前者是非确定性的，而后者是确定性的。□
前面我们已经引入了k相对可分辨函数的概念，因为决策属性是如此重要，对此引入专门的定义是非常有用的。
定义3.2.20设A=（U,A∪{d}）是一个相容的决策系统，而M(A)={cij}是其可分辨矩阵，构造一个新的矩阵


Md(A)={cdij}（3221）


并假定


cdij=,d(xi)=d(xj)

cij-{d},其他（3222）


矩阵Md(A)称为系统A的决策相对可分辨矩阵（decisionrelative discernibility matrix）。与由可分辨矩阵构造可分辨函数相类似，可以由决策相对可分辨矩阵构造决策相对可分辨函数（decisionrelative discernibility function）fdM(A)。
有关文献已经证明，fdM(A)的主蕴涵定义了A的所有决策相对约简（decisionrelative reducts）的集合。
例题3.2.11仍考虑表323所示的决策，重排后如表325所示。该表用来说明如何构造A的决策相对可分辨矩阵和决策相对可分辨函数。为方便起见，把所有接收的行重排在上部，而所有拒绝的行重排在下部。

表325重排的决策表



对象文凭经历外语介绍人意见决策

x1MBA中通过很好接收
x4MSc高通过不明确接收
x6MSc高通过很好接收
x7MBA高否好接收
x2MBA低通过不明确拒绝
x3MCE低通过好拒绝
x5MSc中通过不明确拒绝
x8MCE低否很好拒绝

由这个决策相对可分辨矩阵得到的简化决策相对可分辨函数是fdM(A)=ed∨er。由决策相对可分辨矩阵的定义知，选择其中的一个列，如相应于［x1］的列，简化并给出最小函数，以识别［x1］所属的决策类。例如，第一列给出了Boolean函数是： (e∨r)(d∨e∨r)(d∨r)(d∨e∨f)，经化简后变为ed∨rd∨re∨rf。读者可以检验： “如果介绍人意见是很好，外语是通过，则接收”，这就是x1的情况； 其实，对于别的对象，如x6也是同样情况。
相应的决策相对可分辨矩阵示于表326，这是一个对称矩阵，其中对角元素为空集，而所有决策相同的元素也是空集。

表326决策相对可分辨矩阵



矩阵［x1］［x4］［x6］［x7］［x2］［x3］［x5］［x8］
［x1］
［x4］
［x6］
［x7］
［x2］e,rd,ed,e,re,f,r
［x3］d,e,rd,e,rd,e,rd,e,f
［x5］d,ree,rd,e,f,r
［x8］d,e,fd,e,f,rd,e,fd,e,r

□
3.2.5粗糙隶属度
定义3.2.21一个具有特征函数的集合称为明晰集（crisp set），即U是对象集合（或论域），SU是子集，χS: U→{0,1}是特征函数（characteristic function），则


χS(x)=1,x∈S

0,xS（3223）


模糊集（fuzzy set）的概念是用隶属度函数（membership function）代替了特征函数，即mS: U→［0,1］是隶属度函数，而


mS(x)=α,0≤α≤1,x∈U（3224）


明晰集用于正规地表征一个概念，具有清晰的边界，因此并不反映隶属的不确定性。模糊集是对明晰集的推广，这一概念已经成功地得到应用。
模糊集合可以进行明晰特征化。
定义3.2.22设SU的支持集定义为


supportU(S)={x∈U: mS(x)>0}（3225）


又设A,BU是模糊集合，其包含关系定义为


ABiffmA(x)≤mB(x),x∈U（3226）


（式中iff表示“当且仅当”）而模糊集合的其他运算定义为


并运算： mA∪B(x)=max{mA(x),mB(x)}（3227）

交运算：  mA∩B(x)=min{mA(x),mB(x)}（3228）

补运算： mU-A(x)=1-mA(x)（3229）


定义3.2.23模糊集合X和Y之间的模糊关系（fuzzy relation）R定义为笛卡儿空间X×Y中的一个模糊集合，即


mR: X×Y→［0,1］（3230）


是x和y在R中关系的隶属度。
定义3.2.24X×Y中的模糊关系R和Y×Z中的模糊关系S，合成为X×Z中的复合模糊关系（composition fuzzy relation）RS，定义为


mRS(x,z)Δmaxy∈Y{min［mR(x,y),mS(y,z)］}（3231）


例题3.2.12考虑图323给出的模糊关系，表327描述了关系R，表328描述了关系S； 图323（a）表示两个模糊关系，图323（b）表示复合的模糊关系。表329~表3212分别给出了复合计算过程。


图323模糊关系的复合


表327~表3212给出了运算结果。



表327关系R



mR

y

123

x

10.30.81
20.90.70.4




表328关系S



mS

z

12

y

10.70.6
20.41
30.50.9




表329复合计算过程1


maxy{min［mR（x,y）,mS（y,z）］},x=1,z=1


ymR（1,y）mS（y,1）min

10.30.70.3
20.80.40.4
310.50.5

max0.5



表3210复合计算过程2


maxy{min［mR（x,y）,mS（y,z）］},x=1,z=2


ymR（1,y）mS（y,2）min

10.30.60.3
20.810.8
310.90.9

max0.9




表3211复合计算过程3


maxy{min［mR（x,y）,mS（y,z）］},x=2,z=1


y mR（2,y）mS（y,1）min

10.90.70.7
20.70.40.4
30.40.50.4

max0.7



表3212复合计算过程4


maxy{min［mR（x,y）,mS（y,z）］},x=2,z=2


y mR（2,y）mS（y,2）min

10.90.60.6
20.710.7
30.40.90.4

max0.7



□
定义3.2.25设U={x1,x2,…,xn}是论域，p是概率密度，A是U中的模糊集（事件），则模糊事件的概率（probabilities of fuzzy events）定义为


P(A)=∑ni=1mA(xi)p(xi)（3232）


其中mA(xi)是隶属度。
定义3.2.26对论域U中的模糊集合A寻求一个单值来表示，就是去模糊化（defuzzyfication），常用的方法有两个： 
（1） 最大化法： 


x^=argmaxx∈UmA(x)（3233）


（2） 求重心法： 


x^=∑ni=1ximA(xi)∑ni=1mA(xi)（3234）


定义3.2.27A是论域U中的一个模糊集合，其α截取（alpha cuts）定义为


AαΔ{x∈U: mA(x)≥α}（3235）


其强α截取（strong alpha cuts）定义为


AαΔ{x∈U: mA(x)>α}（3236）


A的α截取是明晰集。
定义3.2.28设A=(U,A)是一个信息系统，BA，XU，粗糙隶属函数（rough membership function）定义为集合X与包含x的等价类［x］B之间相对交迭度（degree of relative overlap）的一种定量化描述，即


μBX: U→［0,1］，且μBX=|［x］B∩X||［x］B|（3237）


粗糙隶属度函数可以解释为给定x关于属性B的信息u=InfB(x)的前提下，x属于X的条件概率P(x∈X|u)的频度估计。
3.2.6广义粗集
等价关系是Pawlak经典粗集模型的一个关键概念，但等价关系的要求对众多应用来讲太过严格，从而大大限制了粗集理论的推广应用。因此，粗集理论研究的一个重要方向便是建立关于非等价关系的广义粗集［58］模型，为此，许多学者做了大量工作，必须对一般关系下的粗集模型进行扩充。
定义3.2.29设(U,A∪{d})是一个决策系统，集合U上关于条件属性A的容差关系定义为


τεAΔ{(u,v)∈U×U: ρA(u,v)≤ε}（3238）


其中ρA: U×U→R+是相对于条件属性集A的对象间距离，ε是一个阈值，则称(U,A∪{d},τεA)为广义粗集模型。
类似地，考虑A的子集B，条件属性子集B上的容差关系定义为


τεB={(u,v)∈U×U: ρB(u,v)≤ε}（3239）


其中距离函数定义为ρB(u,v)Δmaxa∈B{dist(a(u),a(v))}，其中ρB: U×U→R+是相对于条件属性集B的对象间距离； 而dist: Va×Va→R+是相对属性a∈B的值集上的距离函数。
注广义粗集不是粗集，因为容差关系不是等价关系，它虽然满足二元关系的自返性和对称性，但不满足传递性！也就是说，(u,v),(v,w)∈τεA，但不能推出(u,w)∈τεA。
类似地，求得一个信息系统的广义属性约简就是寻找一个最小属性集合，使得它对所有对象的广义分类能力等同于原来属性集合的广义分类能力。
这仍然是一个难以求解的问题。
3.3证据理论基础
证据理论是由Dempster和Shafer于20世纪60年代末和70年代初建立的一套数学理论，是对概率论的进一步扩充，适合于专家系统、人工智能、模式识别和系统决策等领域的实际问题。
3.3.1概述
例题3.3.1设某甲有两个硬币，一个是正常的正反面硬币，另一个是两面都是正面的错币。他投掷硬币10次，每次都出现的是“正面”，问下一次投掷出现正面的概率是多大？我们可以按照古典概率来计算： 
P(正面)=0.5——如果某甲持正常硬币； 
P(正面)=1.0——如果某甲持错误硬币。
我们缺少的正是某甲持哪个硬币的“证据”。
首先我们考虑用Bayes方法来解决。假设某甲持错误硬币的先验概率是α，则N次投掷出现正面后持错误硬币的后验概率是


P(错误硬币|N次出现正面)=2Nα2Nα+(1-α)


显然随着N的增大，这个后验概率很快趋于1。但是，这个先验概率如何得到？是否有其他方法无须给出先验概率，而凭直觉能获得这个硬币是“错币”的证据？□
以前处理类似问题只能利用概率论中事件概率的框架，而现在某些感兴趣的因素却不能用概率的方法来处理。
事实上，有关证据问题在哲学文献里已经做过很深入的研究，而证据在本质上就是基于观测对不同的假设赋予权值的一种方法。根据有关证据的定义，我们简单地给出如下解释： 
（1） 能够处理任意数量的假设； 
（2） 能够把证据的权值解释为一种函数，而这个函数把假设的先验概率空间，映射到基于观测的假设后验概率空间。
3.3.2mass函数、信度函数与似真度函数
定义3.3.1设H表示某个有限集合，称为假设空间，这是一个完备的、元素间相互不交的空间； 又假定O表示观测空间，或称为试验结果集合。对于给定的假设h∈H，μh是观测空间O上的概率，而证据空间定义为


EΔ{H,O,μh1,μh2,…,μhn}（331）


其中n∈N是H中假设的个数。
例题3.3.2在例题3.3.1中，H={h1={正常硬币}，h2={错误硬币}}，而O={z： z={观测1，观测2，…，观测10}}。
设z1={观测1={正面}，观测2={正面}，…,观测10= {正面}}是一个具体的观测，则


μh1(z1)=1210， μh2(z1)=1□




给定假设h∈H，以及观测z∈O，在证据空间中权值为


w(z,h)=μh(z)μh1(z)+…+μhn(z)（332）


注意，不失一般性，考察h1和h2的情况，有w(z,h1)/w(z,h2)=μh1(z)/μh2(z)。
所以，给定h∈H，观测z的权值就是其相对概率，而且w(z,h)∈［0,1］； 对于给定的z∈O，w(z,·)就是H上的一个概率测度。但是，这却不是一个频度或似然。例如，在例题3.3.2中，w(z1,h2)=1/（1+1/210）=210/（210+1）。
定义3.3.2设H表示某个有限集合，称为假设空间； 又假定P（H）表示H的所有子集构成的集类（称为H 的幂集），映射m: P（H）→［0,1］称为一个基本概率赋值（basic propability assignment,BPA）或mass函数，如果


m()=0; ∑AHm(A)=1（333）


那么mass函数实际上就是对各种假设的评价权值。但是，基本概率赋值不是概率，因为不满足可列可加性。也就是说，如果A,B,CH，且A=B∪C,B∩C=，但是m(A)=m(B)+m(C)却不必成立。
例题3.3.3设有两个医生给同一病人诊断疾病，甲医生认为0.9的可能性是感冒，0.1的可能性是说不清楚的病症； 乙医生认为0.2的可能性不是感冒，0.8的可能性是说不清的病症。于是，假设空间是H={h,h-}，其中h表示诊断为感冒，h-表示诊断为不是感冒； P（H）={,{h},{h-},H}，其中表示不可能事件： “既是感冒，又不是感冒”，而H表示事件： “可能是感冒，又可能不是感冒”。从而可以构造所谓mass函数: 
m1(h)=0.9,表示甲医生认为是感冒的可能性; 
m1(H)=0.1,表示甲医生认为是说不清楚何种病症的可能性;
m2(h-)=0.2,表示乙医生认为不是感冒的可能性; 
m2(H)=0.8,表示乙医生认为是说不清楚何种病症的可能性。
问题是判定患者是感冒的可能性究竟有多大，或者判定这种可能性落在什么范围内。注意H={h}∪{h-},且{h}∩{h-}=，但


m1(H)≠m1({h})+m1({h-}) □


定义3.3.3设H表示某个有限集合，P（H）表示H的所有子集构成的集类，映射Bel： P（H）→［0,1］称为信度函数（belief function），如果: 
（1） Bel()=0; Bel(H)=1; （334）
（2） 对H中的任意子集A1,A2,…,An有


Bel∪ni=1Ai≥∑I{1,2,…,n}

I≠(-1)|I|+1Bel∩i∈IAi（335）


式中|I|表示集合I中元素的个数。
这说明信度函数表示对假设的信任程度估计的下限（悲观估计）。假定仅对H中的任意两个子集A1,A2有


Bel(A1∪A2)≥Bel(A1)+Bel(A2)-Bel(A1∩A2)（336）


则称Bel： P（H）→［0,1］为弱信度函数（weak belief function）。
定义3.3.4设H表示某个有限集合，P（H）表示H的所有子集构成的集类，映射Pl: P（H）→［0,1］称为似真度函数（plausibility function），如果
（1） Pl()=0; Pl(H)=1; （337）
（2） 对H中的任意子集A1,A2,…,An有


Pl∩ni=1Ai≤∑I{1,2,…,n}
I≠(-1)|I|+1Pl∪i∈IAi（338）


式中|I|表示集合I中元素的个数。
这说明似真度函数表示对假设的信任程度估计的上限（乐观估计）。假定仅对X中的任意两个子集A1,A2有


Pl(A1∩A2)≤Pl(A1)+Pl(A2)-Pl(A1∪A2)（339）


则称Pl: P（H）→［0,1］为弱似真度函数（weak plausibility function）。
例题3.3.4仍考虑诊断问题，假定先验知识告诉我们病人的疾病只有三种可能性h1,h2,h3，构成基本假设空间H={h1,h2,h3}，于是事件空间为


P（H）={,{h1},{h2},{h3},{h1,h2},{h1,h3},{h2,h3},{h1,h2,h3}}


而三个医生分别按自己的诊断为上述事件空间给出了三个不同的概率P1,P2,P3，它们满足


P1({h1})=0.5,P1({h2})=0,P1({h3})=0.5

P2({h1})=0.5,P2({h2})=0.5,P2({h3})=0

P3({h1})=0,P3({h2})=0.5,P3({h3})=0.5


按概率公式，可计算得到


P1({h1,h2})=0.5,P1({h1,h3})=1,P1({h2,h3})=0.5

P2({h1,h2})=1，P2({h1,h3})=0.5，P2({h2,h3})=0.5

P3({h1,h2})=0.5，P3({h1,h3})=0.5，P3({h2,h3})=1

P1()=P2()=P3()=0


P1(H)=P2(H)=P3(H)=1


对于任意事件A∈P（H），其概率下界和概率上界分别定义为


P*(A)=mini{Pi(A): i=1,2,3}，P*(A)=maxi{Pi(A): i=1,2,3}


于是: 


P*({h1})=P*({h2})=P*({h3})=0

P*({h1,h2})=P*({h2,h3})=P*({h1,h3})=0.5

P*(H)=1，P*()=0

P*({h1})=P*({h2})=P*({h3})=0.5

P*({h1,h2})=P*({h2,h3})=P*({h1,h3})=1

P*(H)=1，P*()=0


这就是概率下界和概率上界。显然，概率下界和概率上界具有如下性质: 
（1） P*()=P*()=0; P*(H)=P*(H)=1
（2） 0≤P*（A）≤P*（A）≤1,A∈P （H）
（3） P*(A)=1-P*(Ac),A∈P(H)（其中Ac=H-A） 
（4） P*(A)+P*(B)≤P*(A∪B)≤P*(A)+P*(B)≤P*(A∪B)≤P*（A）+P*（B）,A,B∈P（H）,A∩B=
概率下界和概率上界虽然满足有界性，但一般不再满足可加性。
显然，因为P*(A∩B)≥0，所以有


P*(A∪B)≥P*(A)+P*(B)-P*(A∩B)，A,B∈P（H）（3310）


从而P*是弱信度函数。
同样地，因为


P*(A∩B)=1-P*(Ac∪Bc)≤1-P*(Ac)-P*(Bc)+P*(Ac∩Bc)

=1-P*(Ac)+1-P*(Bc)-1+P*(Ac∩Bc)

=P*(A)+P*(B)-P*(A∪B)（3311）


从而P*是弱似真度函数。令A1={h1},A2={h2},A3={h3}，而


P*(A1∩A2∩A3)=P*()=0


从而有


P*(A1)+P*(A2)+P*(A3)-P*(A1∪A2)-P*(A2∪A3)-P*(A1∪A3)+

P*(A1∪A2∪A3)=0.5+0.5+0.5-1-1-1+1=-0.5


所以式（338）不成立，从而P*不是似真度函数。□
定理3.3.1设H表示某个有限集合，Bel和Pl分别表示H上的信度函数和似真度函数，则有


Pl(A)=1-Bel(Ac) （3312）

Bel(A)=1-Pl(Ac)（3313）


证明由定义及集合并交运算可证。▉
定理3.3.2设m、Bel和Pl分别是H上的mass函数、信度函数和似真度函数，则对任意A∈P（H）有


Bel(A)=∑DAm(D)（3314）

Pl(A)=∑D∩A≠m(D)（3315）


且Bel(A)≤Pl(A)。
证明根据mass函数定义知，Bel()=m()=0,Bel(H)=∑AHm(A)=1，而且对任意A∈P（H）有Bel(A)≥0，且根据信度函数的定义知


1=Bel(H)=Bel(A∪Ac)≥Bel(A)+Bel(Ac)


从而Bel(A)≤1-Bel(Ac)≤1。对于DH，设A1,A2,…,An是H中的任意子集，记I(D)={1,2,…,n}∩{i: DAi}，显然I(D)≠i∈{1,2,…,n}，使得DAi,而


D∩i∈IAiII(D)


于是，


∑I{1,2,…,n}

I≠(-1)|I|+1Bel∩i∈IAi=∑I{1,2,…,n}

I≠(-1)|I|+1∑II(D),I(D)≠m(D)

=∑I(D)≠m(D)∑I(D)≠,II(D)(-1)|I|+1=∑I(D)≠m(D)

≤∑m(D): D∪ni=1Ai=Bel∪ni=1Ai


所以Bel是信度函数。由Pl(A)=1-Bel(Ac)即可知Pl是似真度函数。▉
定义3.3.5设H是有限集合，Bel和Pl分别是定义在P（H）上的信度函数和似真度函数，对于任意A∈P（H），其信度区间（belief interval）定义为


［Bel(A),Pl(A)］［0,1］（3316）


信度区间表示事件发生的下限估计到上限估计的可能范围。
定理3.3.3设z1,z2,…,zl∈O为l个互斥且完备的观测，即μ(zi)表示zi发生的概率，满足zi∩zj=,i≠j且∑li=1μ(zi)=1； 对于每个zi∈O，当m(·|zi)，Bel(·|zi)，Pl(·|zi)分别是H上的mass函数、信度函数和似真度函数时，则


m(A)=∑li=1m(A|zi)μ(zi)（3317）

Bel(A)=∑li=1Bel(A|zi)μ(zi)（3318）

Pl(A)=∑li=1Pl(A|zi)μ(zi)（3319）


仍分别是H上的mass函数、信度函数和似真度函数。
证明容易证明m()=0，而且


∑AHm(A)=∑AH∑li=1m(A|zi)μ(zi)=∑li=1μ(zi)∑AHm(A|zi)=1


从而m是mass函数。同理可证信度函数和似真度函数。▉
例题3.3.5设某工厂要为某设备的故障A的发生率m(A)做出判断。而根据统计，各指标分类等级发生的概率分别为μ(z1)=0.1，μ(z2)=0.15，μ(z3)=0.3，μ(z4)=0.25，μ(z5)=0.2。已经知道在各检验指标z分类等级条件下故障A的发生率分别为: 
（1） m(A|z1)=0.03，z1表示严重超标; m(A|z2)=0.025，z2表示超标;  
（2） m(A|z3)=0.01，z3表示轻微超标; m(A|z4)=0.005，z4表示良好;  
（3） m(A|z5)=0.001，z5表示优良。

于是，故障A的发生率为


m(A)=0.03×0.1+0.025×0.15+0.01×0.3+

0.005×0.25+0.001×0.2=0.0112□


3.3.3Dempster公式
定理3.3.4（Dempster公式）设m1,m2是H上的两个mass函数，则


m()=0

m(A)=1N∑E∩F=Am1(E)m2(F),A≠（3320）


是mass函数，其中


N=∑E∩F≠m1(E)m2(F)>0（3321）


为归一化系数。
证明m()=0已经给定，只需证明∑AHm(A)=1。而


∑AHm(A)=m()+∑AH,A≠m(A)=∑AH,A≠1N∑E∩F=Am1(E)·m2(F)

=1N∑E∩F≠m1(E)·m2(F)=1NN=1


从而m是mass函数。▉
设m1,m2是H上的两个mass函数，而m是其合成的mass函数，一般记为


m=m1m2（3322）


合成公式满足结合律和交换律。
一般情况下，如果H上有n个mass函数m1,m2,…,mn，如果


N=∑∩ni=1Ei≠∏ni=1mi(Ei)>0（3323）


则有如下合成公式： 


m(A)=(m1…mn)(A)=1N∑∩ni=1Ei=A∏ni=1mi(Ei)（3324）


如果N=0，则所得mass函数存在矛盾。
例题3.3.6在例题3.3.3中，求两个医生诊断的mass函数，以及相应的信度函数和似真度函数。此时


N=∑E∩F≠m1(E)·m2(F)=m1(h)m2(H)+m1(H)m2(h-)+m1(H)m2(H)

=0.9×0.8+0.1×0.2+0.1×0.8=0.82


所以 


m(h)=10.82m1(h)m2(H)=0.9×0.80.82=3641

m(h-)=10.82m1(H)m2(h-)=0.1×0.20.82=141

m(H)=10.82m1(H)m2(H)=0.1×0.80.82=441


这就是得到的mass函数。而按式（3315）和式（3316），则h和h-的信度函数与似真度函数分别为


Bel(h)=∑Dhm(D)=m(h)=3641

Pl(h)=∑D∩h≠m(D)=m(h)+m(H)=36+441=4041

Bel(h-)=∑Dh-m(D)=m(h-)=141

Pl(h-)=∑D∩h-≠m(D)=m(h-)+m(H)=1+441=541


所以h的信度区间为3641,4041，而h-的信度区间为141,541。□
例题3.3.7假定设备的故障有四种类型构成假设空间H={h1,h2,h3,h4}，而检测获取的系统状态估计分别是z1,z2∈O。现在已知给定zi时的mass函数如下


m({h1,h2}|z1)=0.9; m({h3,h4}|z1)=0.1

m(h1|z2)=0.7; m({h2,h3,h4}|z2)=0.3


（此时隐含： 当A≠{h1,h2}或{h3,h4}时，m(A|z1)=0; 当A≠{h1}或{h2,h3,h4}时，m(A|z2)=0）。
假定z1,z2发生的概率分别是μ(z1)=0.8，μ(z2)=0.2，则


m(h1)=m(h1|z2)μ(z2)=0.7×0.2=0.14

m({h1,h2})=m({h1,h2}|z1)μ(z1)=0.9×0.8=0.72

m({h3,h4})=m({h3,h4}|z1)μ(z1)=0.1×0.8=0.08

m({h2,h3,h4})=m({h2,h3,h4}|z2)μ(z2)=0.3×0.2=0.06


所以是mass函数。于是可得


Bel(h1)=∑Dh1m(D)=m(h1)=0.14

Pl(h1)=∑D∩h1≠m(D)=m(h1)+m({h1,h2})=0.14+0.72=0.86

Bel({h1,h2})=∑D{h1,h2}m(D)=m(h1)+m({h1,h2})=0.14+0.72=0.86

Pl({h1,h2})=∑D∩{h1,h2}≠m(D)=m(h1)+m({h1,h2})+m({h1,h2,h3})

 =0.14+0.72+0.06=0.92

Bel({h3,h4})=∑D{h3,h4}m(D)=m({h3,h4})=0.08

Pl({h3,h4})=∑D∩{h3,h4}≠m(D)=m({h3,h4})+m({h2,h3,h4})

  =0.08+0.06=0.14

Bel({h2,h3,h4})=∑D{h2,h3,h4}m(D)=m({h2,h3,h4})=0.06

Pl({h2,h3,h4})=∑D∩{h2,h3,h4}≠m(D)=m({h1,h2})+m({h3,h4})+m({h2,h3,h4})

=0.72+0.08+0.06=0.86


从而h1的信度区间是［0.14，0.86］; {h1,h2}的信度区间是［0.86，0.92］; {h3,h4}的信度区间是［0.08，0.14］; 而{h2,h3,h4}的信度区间是［0.14，0.86］。□
3.3.4证据推理
定理3.3.5设m是假设空间H上的mass函数，P（H）表示H的所有子集构成的幂集，P是H上的概率分布，则有v: P（H）→［0,1］，满足v()=0，且


v(A)=m(A)·P(A)∑≠BHm(B)·P(B)（3325）


以及γ: P（H）→［0,1］，满足γ()=0； 且


γ(A)=m(A)/P(A)∑≠BHm(B)/P(B)（3326）


仍是H上的mass函数。
证明由于v()=0，且 


∑≠AHv(A)=∑≠AHm(A)·P(A)∑≠BHm(B)·P(B)=1


从而v是H上的mass函数。同理可证γ也是H上的mass函数。▉
定理3.3.6设H是有限集合，m1和m2都是定义在P（H）上的mass函数，P是H上的概率分布，则有v: P（H）→［0,1］，满足v()=0，且


v（A）=（γ1γ2）（A）·P（A）∑≠DH（γ1γ2）（D）·P（D），A∈P（H）（3327）


仍是H上的mass函数，其中


γi(A)=mi(A)/P(A)∑≠BHmi(B)/P(B),i=1,2（3328）


记为v(A)=(m1m2)(A)。同时对于AH,A≠，有


(m1m2)(A)=∑E∩F=AP(A)m1(E)P(E)·m2(F)P(F)∑≠DH∑E∩F=DP(D)m1(E)P(E)·m2(F)P(F)（3329）


证明由定理3.3.5知，m1m2是H上的mass函数； 当AH,A≠时，有


(m1m2)(A)=(γ1γ2)(A)·P(A)∑≠BH(γ1γ2)(B)·P(B)


代入γ1γ2的合成公式并进行简化后得


(m1m2)(A)=∑E∩F=A［P(A)·γ1(E)·γ2(F)］∑≠DH∑E∩F=D［P(D)·γ1(E)·γ2(F)］


将式（3328）代入上式做适当化简即得式（3329）。	▉
归纳起来，证据推理的一般模型可用如下方式描述。
定义3.3.6设H={h1,…,hn}表示假设空间，P（H）表示H的所有子集构成的集类； O={z1,z2,…,zl}表示观测空间，μi（zi）表示zi发生的概率，而P是H上的先验概率分布。对于每个zi∈O，m(·|zi)和m(·|z-i)都是H上的mass函数，此处z-i表示zi不发生。证据推理模型描述为


{(H,P),(zi,μi),i=1,2,…,l; m(·|zi),m(·|z-i),i=1,2,…,l}（3330）


其中规则描述如下： 如果观测zi发生，则假设A∈P（H）具有强度m（A|zi）； 如果观测zi不发生，则假设A∈P（H）具有强度m（A|z-i）。
证据推理一般模型的计算步骤是: 
（1） 计算mass函数mi(A)，即


mi(A)=m(A|zi)μi(zi)+m(A|z-i)μi(z-i),i=1,2,…,l（3331）


（2） 利用先验概率P，计算mass函数γi(A)，即


γi(A)=mi(A)/P(A)∑≠BHmi(B)/P(B),i=1,2,…,l（3332）


（3） 利用DempsterShafer合成公式，计算mass函数γ(A)，即


γ(A)=（γ1γ2…γl）(A)（3333）


（4） 计算mass函数v(A)，即


v(A)=γ(A)·P(A)∑≠BHγ(B)·P(B)（3334）



（5） 计算信度函数和似真度函数，即


Bel(A)=∑BAv(B)（3335）

Pl(A)=∑A∩B≠v(B)（3336）


于是，［Bel(A),Pl(A)］就是假设A∈P（H）的信任区间。
3.3.5证据理论中的不确定度指标
描述不确定性的理论与方法很多，比如概率论、模糊集、可能性理论、证据理论以及粗糙集。这些理论可以看作是互补的，分别从不同角度来描述各种不同类型的不确定性。不确定性主要有三类［10］,如图331所示。


图331不确定性类型


本节将介绍几种用于描述不确定性程度的度量或指标——不确定度（measure of uncertainty）。
众所周知，严格的概率测度必须满足概率公理中的可列可加性。任何一个事件（或集合）的概率，必须等于这个事件的所有互斥子事件的概率之和。概率的这种特性就称为协调性。在经典集合论及概率框架中的不确定度主要有两类：
（1） Hartley熵［11］： 


H（A）=log2（|A|）,AΘ（3337）


其中|·|表示集合的势，即该集合包含元素的个数。
（2） Shannon熵［12］： 设p={pθ|u∈Θ}是Θ上定义的概率分布，则熵定义为


S(p)=-∑θ∈Θpθlog2pθ（3338）


这两个熵是建立其他不确定度的基础。对于证据理论而言，mass函数不再遵守可列可加性，即一个事件（或集合）的mass函数，不一定等于这个事件的所有互斥子事件的mass函数之和。对mass函数来说，可定义的不确定度主要包括： 
（1） 非特异度（nonspecificity measure）［13］： 


N(m)=∑AΘm(A)log2|A|（3339）


非特异度是针对非特异性的度量，可看作是所有焦元的Hartley熵的加权和。当一个证据体的所有焦元均为单点时，mass函数退化为概率，非特异性度量达到最小值0。当证据体仅有一个焦元Θ时，非特异性度量达到最大值。
（2） 聚合不确定性度（aggregated uncertainty measure，AU measure）［14］： 设Θ为一有限论域，Bel是定义在Θ上的信度函数。与Bel关联的聚合不确定度定义为


AU（Bel）=maxPBel-∑θ∈Θpθlog2pθ（3340）


这实际上是一个优化求解问题，即在所有可能的概率分布情况下，选取使得式（3340）取值最大的一组概率分布； 这组概率分布要求与给定的信度函数
Bel一致，即满足pθ∈［0,1］,θ∈Θ且∑θ∈Θpθ=1； 同时要求Bel(A)=∑θ∈Θpθ，AΘ。式（3340）中的PBel代表所有满足上述条件的概率分布。
AU满足作为不确定性度的五个条件［15］： 
① 概率一致性条件： 当m定义为概率测度，则AU蜕化为Shannon信息熵。
② 集合一致性条件： 当证据体的焦元只有一个的时候，即AΘ，m(A)=1，B≠A，m(B)=0，AU蜕化为Hartley熵，即AU(m)=log2|A|。
③ 取值范围： 0≤AU(m)≤log2|Θ|。
④ 边缘分布的次可加性条件： 即对任意两个基本概率赋值mX与mY，其联合基本概率赋值m满足： AU(m)≤AU(mX)+AU(mY)。
⑤ 独立边缘分布的可加性条件： 即对任意两个独立的基本概率赋值mX与mY，其联合基本概率赋值m满足： AU(m)=AU(mX)+AU(mY)。
AU的设计也有些不足之处［8］，如计算复杂度、对证据变化的高度不敏感性等。
（3） 总体不确定度（total uncertainty measure，TU measure）： 可以看作是非特异度和AU的线性组合，即


TU(m,δ)=δAU(m)+(1-δ)N(m)（3341）


3.3.6证据理论存在的主要问题与发展

证据理论在表示和处理不确定性问题时具有明显的优势，然而，在处理不确定性推理时也存在一些问题［1718］，主要集中在Dempster证据组合公式的使用上。
（1） 组合爆炸问题。Dempster证据组合规则最为直观的一个缺陷在于在进行证据组合时，会引起“焦元爆炸”问题，焦元数目随着辨识框架元素数目以指数形式递增，造成计算量的激增。如果辨识框架有n个元素，那么可能的焦元数目为2n+n-1个。以20个元素的辨识框架为例，所有可能焦元的数目为1.048576×107。针对这一问题，已经出现了不少解决方法，主要的思路包括预设焦元结构、减少焦元数量以及改进证据组合算法等。比较有代表性的是基于神经网络［19］的证据组合算法以及Barnett提出的方法［20］。
（2） 有限辨识框架及证据体独立性问题。Dempster证据组合规则虽然具有简单的表达式，但其隐含条件是相对苛刻的，实际应用中往往忽略或者弱化这些条件，这样的后果是会带来很多不合理现象。证据组合公式的使用条件包括： 
① DS证据理论讨论的是一种离散且有限的辨识框架（closeworld），这种框架是由一些具有完备性和互斥性（exhaustive and exclusive）的元素构成； 
② 参与证据组合的证据体，被认为是相互独立的。
正是这样两个条件的存在，限制了Dempster组合规则在一些不确定性问题中的应用。针对条件①中说到的辨识框架问题，Schubert在On nonspecific evidence［21］一文中做过讨论。下面介绍的DSmT可以说是对传统证据理论框架的一个拓展，能够从很大程度上解决因辨识框架引起的问题。条件②中提及的证据体独立性问题，在实际应用中往往很难满足,即绝对严格独立的证据体几乎是不存在的。很多研究者致力于研究对相关证据的处理［2224］，对相关证据的mass函数进行去相关性处理，然后再进行证据组合。有学者提出了证据能量、相关系数等概念［25］，并对组合规则做了改进，也得到了一些有意义的结论。
（3） 高冲突证据组合问题。当参与证据组合的证据体之间存在较大冲突时，Dempster组合规则往往无法有效处理，常常会得出有悖常理、违反直觉的结论。关于这方面的研究，已经成了当前热点之一。下面将针对这一问题做出详细的讨论。需要指出的是，这里讨论的“冲突”（conflict）是指参与证据组合的证据体之间的冲突，而上节所述的“冲突”（discord）是针对证据体内部而言的。
此外，在证据理论的实际使用当中，mass函数的生成或获取往往是最困难的一步，也有很多文献致力于设计合理有效的mass函数生成法。Dempster证据组合规则是对称的规则，参与证据组合的证据体没有重要性上的差异。许多研究工作都围绕建立非对称的证据推理规则而展开，特别是条件证据与证据更新。
基于DempsterShafer证据理论，许多研究者都作了拓展性研究，提出了一些新的模型和规则，诸如TBM模型［26］、DSmT［27］等。
（1） 可传递信度模型。可传递信度模型（transferable belief model,TBM）是Philippe Smets于20世纪80年代，在证据理论基础上提出的一种扩展模型。TBM旨在建立一种用不完全概率函数来量化信度表示的理论，主要研究信度随证据变化时的更新问题。
TBM模型是一个双层结构，包括credal层以及pignistic层。其中，在credal层处理的是信度的获取和更新问题； 在pignistic层，将credal层得到的信度转换成pignistic 概率进而据此进行决策。credal层先于pignistic层。在credal层上随时可以对信度进行赋值和更新，在pignistic层仅进行决策。
① credal层： 在credal层对于证据处理的规则包括Dempster 证据组合规则以及式（3342）中的条件推理规则。
定义3.3.7［26］假设m是辨识框架Θ上的mass函数。若新到的证据支持Θ上的一个命题B，即m(B)=1，则定义条件mass函数为


mB(A)=∑Xm(A∪X)1-∑Xm(X),AB

0,其他（3342）


从上式中不难看出： 当新出现的证据支持命题（或事件）B为真，则原有证据中的基本信度赋值m(A)传递到命题A∩B上。可传递信度模型也正是因此而得名。
② pignistic层： 在credal层上做证据处理时，焦元可以是单点的（singleton），也可以是复合的（compound or composite）。所谓单点焦元对应于辨识框架中的一个单一元素（单命题）。而复合焦元对应于辨识框架中元素的组合（复合命题）。依据单点焦元给出的结论是清晰的，而依据复合焦元给出的结论相对是模糊的。证据组合实质上就是一种聚焦过程，使得模糊的结论能够相对清晰化。在TBM模型中，决策时需要将credal层上的各种单命题及复合命题结论都转换成单命题结论，也就是将基于证据理论的信度框架转换到概率框架来进行决策。为此，Smets定义了pignistic概率： 


BetPm(A)=∑BΘm(B)|A∩B||B|（3343）


对于单点焦元，是


BetPm(θ)=∑θ∈B,BΘm(B)|B|（3344）


其中，|·|表示集合中元素的个数。从式（3343）可以看出，一个复合焦元的mass函数赋值是被平均分配到组成该复合焦元的所有单点焦元上的。
（2） DezertSmarandache理论。由Dezert和Smarandache等创立的DezertSmarandache理论（DSmT）［2729］，又称作似真与冲突推理理论（plausible and paradoxical reasoning），其主要创新是在辨识框架中引入了冲突信息。相对于DS证据理论中的幂集2Θ概念，DSmT提出了超幂集（hyperpowerset）DΘ的概念。DΘ是通过辨识框架Θ={θ1,θ2,…,θn}中的基本元素进行交、并运算产生的集合； 即在DSmT中，辨识框架中的元素不再是不可分的。DΘ需要满足以下三个条件： 
① ,θ1,θ2,…,θn∈DΘ； 
② 若A,B∈DΘ，则A∩B∈DΘ且A∪B∈DΘ； 
③ 除了条件①、②中获得的元素之外，再没有其他元素属于DΘ。
对于DSmT来说，由于它是建立在超幂集的概念上的，运算量是个令人头疼的问题，当|Θ|=n时，DΘ的势达到22Θ数量级。
DSmT是从DS证据理论基础上拓展而来，因此也沿袭使用了DS证据理论中的基本概率赋值（mass函数）、信度函数（Bel）以及似真度函数(Pl)等。但由于模型基本框架的变化，DSmT的组合规则不同于DS证据理论中的Dempster组合规则。
定义3.3.8（DSmT证据组合规则）［27］假定辨识框架Θ上性质不同的两个证据，其焦元分别为Bi和Cj（i=1,2,…,n; j=1,2,…,m），其mass函数分别为m1,m2，组合后的mass函数为


m(A)=0,A=

∑Bi,Cj∈DΘ,Bi∩Cj=Am1(Bi)m2(Cj),A≠（3345）


这个规则在实际中有广泛应用。
近年来证据理论又有很大发展。证据距离用来度量两条证据之间的差异程度，证据距离越大，则两条证据差异程度越大。下面给出一些新的概念。
（1） Tessem距离［88］。

dT(m1,m2)=maxAΘ{|BetP1(A)－BetP2(A)|}（3346）

其中，BetP(A)就是前述pignistic概率转换得到的转换概率［89］，定义如式（3343）所示。
（2） 基于模糊隶属度的证据相似性度量［90］。

dFm1,m2=1－∑ni=1(μ（1）(θi)∧μ（2）(θi))∑ni=1(μ（1）(θi)∨μ（2）(θi))（3347）

其中，∧表示合取运算（最小值），∨表示析取运算（最大值）。
（3） Jousselme距离［91］。

dJ(m1,m2)=0.5·(m1－m2)TJac(m1－m2)（3348）

其中，Jac(A,B)是Jaccard加权矩阵，Jac(A,B)=A∩BA∪B。
（4） 基于区间数的证据距离［92］。
假设区间数表示为a～，用a－表示a～的下界，a+表示a～的上界。区间数a～1与a～2之间的Wasserstein距离［6］定义为

dBI(a～1,a～2)=a－1+a+12－a－2+a+222+13a+1－a－12－a+2－a－222（3349）


两个mass函数mii=1,2的信度区间模型如下： 

BIi=［Beli(A1),Pli(A1)］

［Beli(A2),Pli(A2)］

︙

［Beli(A2n－1),Pli(A2n－1)］=
BIi(A1)

BIi(A2)
︙
BIi(A2n－1)


基于Wasserstein距离定义了两种证据距离，Euclidean系列的证据距离定义为

dEBI(m1,m2)=Nc·∑2n－1i=1［dBI(BI1(Ai),BI2(Ai))］2（3350）

其中，Nc=1/2n－1是归一化因子。Chebyshev系列的证据距离定义为

dCBI(m1,m2)=maxAiΘ,i=1,…,2n－1{dBI(BI1(Ai),BI2(Ai))}（3351）

3.3.7关于证据函数不确定性的研讨
关于证据的不确定性是一个值得进一步研讨的问题，如下资料供研究者参考。证据函数的不确定性度量包含两个部分，分别是不一致性（discord）和非特异性（nonspecificity）。常用的不确定性度量方法中有分别针对不一致性和非特异性进行度量的，也有对这两部分进行总体度量的。
1. 关于不一致性的度量方法
（1) Confusion度量（confusion measure）［96］

Conf(m)=－∑AΘm(A)log2(Bel(A))（3352）


(2) Dissonance度量（dissonance measure）［97］

Diss(m)=－∑AΘm(A)log2(Pl(A))（3353）


(3) Discord度量（discord measure）［98］

Disc(m)=－∑AΘm(A)log21－∑BΘm(B)|B－A|B（3354）


(4) Strife度量（strife measure）［99］

Stri(m)=－∑AΘm(A)log21－∑BΘm(B)|A－B|A（3355）

2. 关于非特异性的度量方法
（1) Dubois & Prade非特异性度量［100］

NSDP(m)=∑AΘm(A)log2|A|（3356）


（2) Yager特异性度量［97］

SY(m)=∑AΘm(A)A（3357）


（3) Korner非特异性度量［101］

NSK(m)=∑AΘm(A)·|A|（3358）


（4) Korner非特异性度量（一般形式）［101］

NSf(m)=∑AΘm(A)·f(|A|)（3359）

3. 总体不确定性度量方法
（1) 聚合不确定度（aggregated uncertainty measure, AU）［102］

AU(m)=max-∑θ=Θpθlog2pθ（3360）
s.t.∑θ∈Θpθ=1

pθ∈［0,1］,θ∈Θ

Bel(A)≤∑θ∈Θpθ≤1-Bel(),A∈Θ


(2) 含混度（ambiguity measure, AM）［103］

AM(m)=－∑θ∈ΘBetPm(θ)log2BetPm(θ)（3361）

其中，BetPm(θ)=∑θ∈BΘm(B)/|B|，是pignistic概率转换得到的转换概率［105］。
(3) 基于距离的总体不确定性度量［106］

TUI(m)=1－1n·3·∑ni=1dBI Belθi,Plθi,［0,1］（3362）

其中， dI是信度区间Belθi,Plθi和［0,1］之间的Wasserstein距离［44］。［0,1］是最不确定的情况。Wasserstein距离能够表示两区间数之间的距离。区间数a～，用a－表示a～的下界， a+表示a～的上界。区间数a～1与a～2之间的Wasserstein距离定义为

dBIa～1,a～2=a－1+a+12－a－2+a+222+13a+1－a－12－a+2－a－222（3363）

3.4随机集理论基础
自从G.Matheron于1975年出版了《随机集与积分几何学》一书以来，关于随机集理论的研究方兴未艾［3134］，其成功地用于解决各种问题，现在已经成为信息融合研究领域最受关注的研究方向之一。
3.4.1一般概念
从本质上讲，随机集与随机变量并没有太大的差别，随机变量处理的是随机点问

题，而随机集处理的是随机集合问题，即后者处理的对象是可能结果的一组元素。如果把后者的集值结果看作是某个特殊空间的点，则二者就没有区别了。然而，集值的引入却带来许多令人意想不到的奇特结果，这正是利用随机集建立多源信息融合统一理论方面最吸引人的地方。
考虑一个概率空间(Ω,F,P)和一个可测空间(Y,BY)，其中Y是观测集合，而BY表示相应的Borelσ域。对于一般的随机变量x: Ω→Y而言，概率空间只是一个数学上的概念，而实际观测到的变量在可测空间。定义在概率空间上的概率测度P一般难以直接用于计算，因此通常把它转换成可测空间上的概率分布，即


PxΔPx-1: BY→［0,1］（341）


也就是说，要求x可测，即对于A∈BY，则{ω∈Ω: x(ω)∈A}∈F，而且


Px(A)=P{ω: x(ω)∈A}（342）


下面考虑一个集值映射。
定义3.4.1设(Ω,F,P)是一个概率空间，(Y,BY)是一个可测空间，定义集值映射（setvalued mapping）为


X: Ω→P（Y）（343）


其中P（Y）是Y的所有子集构成的集类。给定A∈BY，其上逆（upper inverse）定义为


X(A)Δ{ω∈Ω: X(ω)∩A≠}（344）


下逆（lower inverse）定义为


X(A)Δ{ω∈Ω: ≠X(ω)A}（345）


逆（inverse）定义为


X-1(A)Δ{ω∈Ω: X(ω)=A}（346）


上述集值映射称为是开的（或闭的或紧的），如果对于任意ω∈Ω，X(ω)是Y中开的（或闭的或紧的）子集。
在不致引起混淆的前提下，我们记


AΔX(A)，
AΔX(A)，
A-1ΔX-1(A)（347）


一个集值映射的上逆和下逆，实质上是对随机变量逆概念的推广，显然有AA。
定理3.4.1设X： Ω→P（Y）是一个集值映射，则如下条件等价： 
① X(ω)≠,ω∈Ω（348）
② X(A)X(A),AY（349）
③ X()=（3410）
④ X(Y)=Ω（3411）
证明见文献［30］。▉
定理3.4.2设X： Ω→P（Ω）是一个集值映射，则如下条件等价： 
① ω∈X(ω),ω∈Ω（3412）
② X(A)A,AΩ（3413）
③ AX(A),AΩ（3414）
证明见文献［30］。▉
定义3.4.2设X： Ω→P（Y）是一个集值映射，定义算子： j: P（Y）→P（Ω），且对于任意A∈P（Y），记


j(A)=X-1(A)Ω（3415）


如果j(A)≠，则称A是j的一个焦集（focus set）； 且令


J Δ{j（A）∈P（Ω）: j（A）≠,AY}（3416）


则必有


∪{j（A）: AY}=Ω

A1,A2∈P（Y）,A1≠A2j（A1）∩j（A2）=
（3417）


这样，J构成对Ω的一个划分，于是称算子j是集值映射X的关系划分函数。
定理3.4.3设P0（Y）=P（Y）-,X: Ω→P0（Y）是一个集值映射，j是X的关系划分函数，则有如下性质： 
① X(A)=∪{j(A′): A′A},AY（3418）
② X(A)=∪{j(A′): A′∩A≠},AY（3419）
③ j(A)=X(A)-∪{X(A′): A′A},AY（3420）
证明见文献［30］。▉
从概念上说，一个随机集就是满足某些可测性条件的集值映射。虽然根据不同的可测性有不同的定义，但大多数都是基于上逆和下逆的概念。
定义3.4.3式（343）定义的集值映射X如果对于A∈BY均有A∈F，则称X是强可测的（strongly measurable）； 而强可测的集值映射X定义为随机集（random set）。
注意，对于A∈BY，因为A=Y∩((Ac))c（注Ac是A在Y中的补集，(B)c是B在Ω中的补集），所以如果X是强可测的，必然对于A∈BY均有A∈F。
随机集是对随机变量概念的推广，是由基本事件空间到观测空间的幂集的一个映射，它比随机变量高了一个复杂层次。随机集不再符合概率公理的一切结论。然而，在解决复杂系统问题时就可能克服所遇到的困难，这种对随机变量的概念进行推广，在一个复杂层次上可以满足系统分析的需要。
定义3.4.4给定一个随机集X： Ω→P（Y），A∈BY的上概率（upper probability）定义为


PX(A)ΔP(A)/P(Y)（3421）


下概率（lower probability）定义为


PX(A)ΔP(A)/P(Y)（3422）


在不致因为不确定哪个随机集诱导上概率和下概率而引起混淆的前提下，记


P=PX，P=PX（3423）


我们可以把随机集视为对一个随机变量x0: Ω→Y不精确观察的结果，这个随机变量就称为原始随机变量（original random variable），而且对于任意ω∈Ω，x0(ω)∈X(ω)。因此，假定对于任意ω∈Ω，X(ω)≠,从而对A∈BY有P(A)=P(A)，P(A)=P(A)。这样，由随机集诱导的上概率和下概率是一对共轭函数。
如果随机集X是对随机变量x0不精确观察的结果，我们有关这个随机变量的所有知识就是它属于X的可测选择类（class of measurable selection）或称为选择器（selector），即


SXΔ{x: Ω→Y是随机变量,x(ω)∈X(ω),ω}（3424）


x0的概率分布属于


PXΔ{Px: x∈SX}（3425）


关于Px0(A)的信息由如下值集（set of values）给出


PX(A)Δ{Px(A): x∈SX}，A∈BY（3426）


还有另外两个概率类在某些场合是有用的，其中第一个是


ΔXΔ{Q是概率分布: Q(A)∈PX(A),A∈BY}（3427）


这是概率分布函数的集合，其值是与随机集给出的信息相容的，显然有PXΔX。如果它们相一致，关于原始变量分布的信息等价于其取值的信息； 而第二个概率类是


MPΔ{Q是概率分布
: Q(A)≤P(A),A∈BY}（3428）


这是由P支配的概率分布函数，或者说是由P生成的纲领集（credal set）。这个概率类是凸的，在实际应用中比PX容易处理。因为不等式P(A)≤Px(A)≤P(A),对于任意x∈SX，A∈BY都有效，我们能够推导出ΔXMP，然后得到PXΔXMP。可以证明，这两个包含关系可能是严格包含的，所以利用上概率和下概率在某些场合会使精度降低，而反过来也会引起某种错误判定。因此，我们感兴趣的是判断在什么情况下利用P和P是合理的。
虽然一个随机集的选择器的分布类和由它诱导的上概率在许多文献中都深入研究过，但必须注意它们之间的联系。对于Y是有限集合的情况，下面将特别予以关注。我们将着重讨论以下两个问题: 
（1） 研究ΔX与MP之间的关系使我们知道，对于某些任意的A∈BY，上概率和下概率关于Px0(A)的值是否提供足够的信息。
（2） 研究什么时候PX=MP，即在什么条件下上概率保持关于Px0(A)的所有信息。
3.4.2概率模型
1. P(A),P(A)作为Px0(A)的模型

首先，我们研究ΔX与MP之间的关系。因为我们已经提到，ΔX是对某些信息的建模，而这些信息给出了BY中元素的概率值。因此，通过研究其与MP的相等关系，则可窥见对于任意A∈BY的“真”概率，
P和P的信息是充足的。
定理3.4.4设
(Ω,F,P)是一个概率空间，(Y,BY)是一个可测空间，X: Ω→P（Y）是随机集，则


ΔX=MPPX(A)=［P(A),P(A)］,A∈BY（3429）


证明见文献［35］。▉
任取A∈BY，然后考虑PX(A)和［P(A),P(A)］，显然后者是前者的扩展集合。为了给出相等条件，我们必须考察PX(A)的最大、最小值是否和P(A),P(A)相一致，而且PX(A)是否是凸的。
文献中已经证明，PX(A)有一个最大值和一个最小值（实际上是［0,1］区间的一个闭子集），而且这些值并不在任意情况下与P(A),P(A)相一致，即使在SX≠的非平凡情况下也是如此。进而，在一般情况下PX(A)也不是凸的。下面的定理给出P(A)=maxPX(A)和P(A)=minPX(A)的充分条件。
定理3.4.5考虑(Ω,F,P)是一个概率空间，(Y,d)是一个度量空间，X： Ω→P（Y）是随机集，则在满足下列任意条件的前提下: 
① Y是可分的度量空间，且X是紧的； 
② Y是可分的度量空间，且X是开的； 
③ Y是光滑的空间，且X是闭的； 
④ Y是σ紧度量空间，且X是闭的; 

则有


P(A)=maxPX(A)，P(A)=minPX(A)，A∈BY（3430）


证明（略）。▉
注该定理对于等式P=maxPX，以及P=minPX给出了充分条件。P的一致性意味着它是所支配有限相加概率集合的上包络。可以证明，在定理规定条件下，它实际上就是选择器诱导的可数相加概率类的上包络。类似地，可以对P做出类似的评论。
定理3.4.6设X： Ω→P（Y）是一个随机集，v: Y→R是一个有界随机变量，只要满足定理3.4.5的几个条件之一，则


∫vdP=sup∫vdPx: x∈SX，∫vdP=inf∫vdPx: x∈SX（3431）


证明（略）。▉
定理3.4.7设X: Ω→P（Y）是一个随机集，且A∈BY，令x1,x2∈SX满足


Px1(A)=maxPX(A)，Px2(A)=minPX(A)


则


PX(A)是凸的x-11(A)-x-12(A)不是不可分的最小元（3432）


证明（略）。▉
注此处所谓不可分的最小元是指对于α∈（0,1），不存在任何可测集B∈F，使得B∈［x-11(A)-x-12(A)］，且
P(B)=αP［x-11(A)-x-12(A)］。
推论设X: Ω→P（Y）是一个随机集，满足定理3.4.5的几个条件之一。如果对于A∈BY，A-A不是不可分的最小元，则


ΔX=MP（3433）


2. P,P作为Px0的模型
现在研究PX与MP之间的相等关系，因为这使我们知道上概率是否保持了原始随机变量分布Px0的所有可用的信息。ΔX与MP之间的相等关系，并不能保证PX与MP之间存在相等关系。那么一种可行的方法就是确定PX=ΔX的充分条件，然后结合上述推论得到所要的结果。不幸的是推论中的式子判定却并不容易。在有限维情况下，表征PX与MP之间的相等关系将更容易，可由此导出Y是可分度量空间条件下的一些有用结果。
当Y是有限集时，给定Y={y1,y2,…,yn}，X: Ω→P（Y）是一个随机集，可以得出： PX=MPPX是凸的。但是这个等价关系对于Y由无限个元构成的集合并不成立。
例题3.4.1设
Y={y1,y2,…,yn}是一个有限集，X: Ω→P（Y）是一个随机集，而P（Y）由2n个Y的可能子集构成（包括空集和Y本身），则X（ω）∈P（Y）,ω∈Ω。设Sn表示序列{1,2,…,n}所有可能的重排构成的集合，而π∈Sn，则有序列{π(1),π(2),…,π(n)}是对原序列的一种重排。对于任意A∈P（Y），则π∈Sn，j=0,1,2,…,n，使得


A={yπ(1),yπ(2),…,yπ(j)}； 当j=0时，A=（3434）


于是有


PX(A)=PX({yπ(1),yπ(2),…,yπ(j)})

P(A)=maxPX(A)

P(A)=minPX(A)（3435）


现在考虑n=3的情况，则


Y={y1,y2,y3}，P（Y）={,{y1},{y2},{y3},{y1,y2},{y1,y3},{y2,y3},Y}


对于A∈P（Y），Px(A)=事件发生的概率。不妨记为


Px()=p000,Px({y1})=p100

Px({y2})=p010,Px({y3})=p001

Px({y1,y2})=p110,Px({y1,y3})=p101

Px({y2,y3})=p011,Px(Y)=p111（3436）


则有表341所示的上概率和下概率。

表341Y={y1,y2,y3}情况下的上概率和下概率



A∈P（Y）P(A)P(A)

00
{y1}(p100+p110+p101+p111)/(1-p000)p100/(1-p000)
{y2}(p010+p110+p011+p111)/(1-p000)p010/(1-p000)
{y3}(p001+p101+p011+p111)/(1-p000)p001/(1-p000)
{y1,y2}(p100+p010+p110+p101+p011+p111)/(1-p000)(p100+p010+p110)/(1-p000)
{y1,y3}(p100+p001+p110+p101+p011+p111)/(1-p000)(p100+p001+p101)/(1-p000)
{y2,y3}(p010+p001+p110+p101+p011+p111)/(1-p000)(p010+p001+p011)/(1-p000)
Y11

此时，PX(A)=［P(A),P(A)］［0,1］。□
例题3.4.2设X: （0,1）→P（［0,1］）是一个随机集，把概率空间((0,1),B(0,1),λ(0,1))映射到可测空间(［0,1］,B［0,1］)，且X(ω)=(0,ω),ω∈(0,1)。容易看出这个映射是强可测的。
（1） 给定x∈S（X），可以验证Px（{0}）=0,Px（［0,ω］）≥ω,ω∈（0,1），而且λ（0,1）（{ω∈（0,1）: Px（［0,ω］）=ω}）=0。
（2） 反之，考虑一个概率测度Q: B［0,1］→［0,1］满足Q（［0,ω)）≥ω，而且对于(0,1)的几乎空子集（all but a null subset）NQ，有Q（［0,ω)）>ω。Q的分位点函数（quantile function）x是一个可测映射，满足Px=Q,x（ω）∈X（ω）,ωNQ。对NQ上的x进行修改，对其可测性不影响，使得它的取值包含在X的值中，据此能够导出Q∈PX。
（3） 能够推导出PX是概率测度类，且Q（{0}）=0,Q（［0,ω］）≥ω,ω； 而且对于［0,1］的几乎空子集，有Q（［0,ω］）>ω，而且容易验证这个类是凸的。
（4） B［0,1］上的Lebesgue测度λ［0,1］满足λ［0,1］（A）≤P*（A）,A∈B［0,1］,因此它属于MP*，而且显然并不以概率1满足λ［0,1］（［0,ω］）>ω，因而PXMP*。□
定理3.4.8设
(Y,d)是一个可分的度量空间，考虑一个集类UBY，使得
（1）  对有限交运算是封闭的； 
（2）  每个开集都是有限集，或者是U中元的可数并,令{Pn}和P都是BY上的概率测度，使得


Pn(A)→n→∞P(A),A∈U（3437）


那么，序列{Pn}弱收敛于P。
证明（略）。▉
3.4.3随机集的mass函数模型
本节将在随机集理论框架内对mass函数模型重新描述，以便得到二者之间的联系。
定理3.4.9考虑(Ω,F,P)是一个概率空间，U是一个有限集合构成的论域空间，而X: Ω→P（U）是随机集，且对ω∈Ω，X(ω)≠,X(ω)≠U，则


m(A)=P{X-1(A)}（3438）

Bel(A)=P{X(A)}（3439）

Pl(A)=P{X(A)}（3440）


分别是P（U）上的mass函数、信度函数与似真度函数,而且


Be(A)=∑A′Am(A′)（3441）

Pl(A)=∑A′∩A≠m(A′)（3442）


于是对任意A∈P（U），Bel(A)≤Pl(A)，Bel(A)=1-Pl(Ac)。
证明因为X(ω)≠，则X-1()=； 同时当A1≠A2时，X-1(A1)∩X-1(A2)=； 且有


∑AYX-1(A)=U


于是X-1(A)是对Ω的关系划分，从而m是mass函数。又因为


Bel(A)=∑A′Am(A′)=∑A′AP(X-1(A′))=P∑A′AX-1(A′)

=P(ω∈Ω: ≠X(ω)A)=P(X(A))


所以式（3439）得证； 类似可证式（3440）。由信度函数与似真度函数的定义即可得到式（3441）和式（3442）。▉
这样，我们把研究随机集的问题与研究证据理论的问题就统一起来了。
定理3.4.10考虑(Ω,F,P)是一个概率空间，U是一个有限集合构成的论域空间，而X1: Ω→P（U），X2: Ω→P（U）是相互独立的随机集，相应的mass函数分别是
m1和m2，则DempsterShafer合成公式就是这两个相互独立随机集的交运算，即


m（A）=P{ω∈Ω: X1（ω）∩X2（ω）=A},A∈P（U）（3443）


证明设m1,m2是P（U）上的两个独立的mass函数，即存在两个独立的随机集X1: Ω→P（U）和X2: Ω→P（U），使得


m1(E)=P{X-11(E)},m2(F)=P{X-12(F)}，
E,FU


任意取m1,m2，假定A=，则m()=0已经给定； 当A≠，选择相互独立的E,FU，使得E∩F=A，则两个mass函数的合成就意味着



m(A)=P(X-1(A))=P{ω∈Ω: X(ω)=A}

=1N∑E∩F=AP{ω∈Ω: X1(ω)=E,X2(ω)=F}

=1N∑E∩F=AP{ω∈Ω: X1(ω)=E}·P{ω∈Ω: X2(ω)=F}

=1N∑E∩F=AP(X-11(E))·P(X-12(F))=1N∑E∩F=Am1(E)·m2(F)


其中N是归一化因子。现在只需证明，即


∑BUm(B)=m()+∑BU,B≠m(B)=∑BU,B≠1N∑E∩F=Bm1(E)·m2(F)

=1N∑E∩F≠m1(E)·m2(F)=1NN=1


从而m是mass函数。▉
注应用如此广泛且理论推导如此晦涩的证据合成理论，用随机集的观点来看竟然是如此简单，仅仅是两个独立随机集的交运算。
Dempster公式的意义在于，两个不同的可能性判断经过合成后变成统一的判断，这是一种形式的信息融合，在许多实际问题中都有应用。注意，这是一种集合运算，与概率的数值计算完全不同。一般情况下，如果U上有n个独立的mass函数m1,m2,…,mn，而且N=∑∩ni=1Ei≠∏ni=1mi(Ei)>0，则有如下合成公式


m(A)=(m1…mn)(A)=1N∑∩ni=1Ei=A∏ni=1mi(Ei)（3444）


如果n=0，则所得mass函数存在矛盾。
对于非独立的几个mass函数的合成，见文献［36］。
3.4.4随机集与模糊集的转换
证据理论是不确定性表示和推理的重要理论和方法之一。对于不确定性推理的定量方法，首先要解决的问题是如何实现对不确定性信息的表示和度量。不同的不确定性推理方法各有其不同的不确定性信息表示与描述方法。证据理论中的不确定性信息表示与描述可通过mass函数来实现。定义在某一辨识框架幂集上的mass函数是对传统概率定义的一种推广。确定一个mass函数应包括两个部分： 焦元结构的确定和相应的mass赋值的确定。得到mass函数，即获得随机集描述，便可以很方便地求取证据理论中的其他函数（信度函数、似真度函数）以及依据证据组合规则进行不确定性推理。在证据理论的实际应用中，mass函数的生成与获取至关重要，却往往也是最困难的一步。目前还没有统一的方法，其生成方法往往与具体应用相关。本节将讨论mass函数生成方法。
定义3.4.5设
(Ω,F,P)是一个概率空间，U是一个有限集合构成的论域空间，而X： Ω→P（U）是随机集，定义 


μX(u)ΔP{ω∈Ω: u∈X(ω)}，u∈U（3445）


称之为该随机集的单点覆盖函数（onepoint covering function）。
单点覆盖函数μX: U→［0,1］可以视为一个模糊隶属函数，这样就把模糊集μX与随机集X联系起来了。注意，这是由随机集（或mass函数）向模糊集的转换，而反过来由模糊集向随机集（或mass函数）的转换要复杂得多。
用模糊集诱导随机集合的方法可以很多，先介绍一种简单的方法。
定义3.4.6设F～是U上的一个模糊集，ω是区间［0,1］上均匀分布的随机变量，则相应的随机集可以定义为


XF～(ω)ΔF～-1［ω,1］（3446）


其中F～-1: A［0,1］→P（U）表示逆映射，从而XF～: ［0,1］→P（U）是一个随机集。
这样，研究模糊集的问题就变成研究随机集的问题。但是，这种转换赋予一个很强的假设： ω是区间［0,1］上均匀分布。这个假设在很多情况下不一定成立。
我们研究mass函数生成的一般方法。
1. 依据目标类型数和环境加权系数确定mass函数［3738］
当考虑目标类型数及传感器（信息源）环境对分类和识别的影响时，可采用如下的经验方法确定mass函数。
设M为传感器目标类型数，N是传感器总数，Ci(oj)是传感器i对目标类型oj的关联系数（j=1,…,M，i=1,…,N）。λi是传感器i的环境加权系数，且定义


αi=max{Ci(oj)|j=1,…,M}

ξi=Mλi∑Mj=1Ci(oj)

βi=(ξi-1)/(N-1),N≥2

Ri=(λiαiβi)∑Nl=1λlαlβl,i=1,…,N（3447）


传感器（信息源）i对目标oj的mass函数转换为


mi({oj})=Ci(oj)∑Ml=1Ci(ol)+M(1-Ri)(1-λiαiβi)

mi({Θ})=M(1-Ri)(1-λiαiβi)∑Ml=1Ci(ol)+M(1-Ri)(1-λiαiβi)，i=1,…,N（3448）


上式是对辨识框架全集的基本概率赋值，用来描述“不知道”或“未知”。
在本方法中，焦元结构预先设定为单点焦元和辨识框架的全集。
2. 基于统计证据的mass函数获取方法［37,39］
若有一批证据是基于统计实验结果获得的，称这批证据为统计证据。统计证据是证据理论在统计问题中的应用，是Shafer用非统计方法研究统计问题的一种尝试。
设统计试验的观测由一组概率模型{pθ|θ∈Θ}确定。pθ是给定θ时的概率密度函数。Shafer的方法给出下面两个假设。
第一个假设： 观测x决定一个似真度函数，满足


Pl({θ})=cpθ(x),θ∈Θ（3449）


其中，c为常数，与θ无关。
第二个假设： 似真度函数应该是一致（consonant）的。所谓“一致”是指所有证据体中焦元都是嵌套（nested）结构的，即对于任一AiΘ，i=1,…,r，总有： m(Ai)>0及∑i=1,…,rm(Ai)=1，AiAj，i<j。
在上述两个假设成立的前提下，得到的一致似真度函数为


Pl(A)=max{pθ: θ∈A}max{pθ: θ∈Θ},A≠,AΘ（3450）


结合式（3449）可得


c=1max{pθ: θ∈Θ}（3451）


相应的支撑函数为


Spx(A)=1-max{pθ: θ∈Ac}max{pθ: θ∈Θ}（3452）


假定Θ0={θ(1),θ(2),…,θ(N)}是Θ的有序集，满足pθ(i)>pθ(j)，1≤i<j≤N，则称Spx(A)为一致支撑函数。相应的mass函数为


mx(A)=pθ(k)(x)-pθ(k+1)(x)pθ(1)(x),A={θ(1),θ(2),…,θ(k)},1≤k≤N-1

pθ(N)(x)pθ(1)(x),A=Θ0=Θ

0,其他 （3453）


上述一致mass函数虽然易于实现，但只适用于满足一致支持假设的特定场合。为此，可通过弱化一致支持假设得到推广方法： 设{W1,W2,…,Wr}是Θ的一个划分，若k=1,…,r，Sp在每个Wk上是一致的，我们说支持函数Sp: 2Θ→［0,1］是部分一致的。若Sp在Θ的一个划分{W1,W2,…,Wr}上部分一致，令Wok={w(1)k,w(2)k,…,w(nk)k}是Wk对应的有序集，使得1≤i<j≤nk，有pw(i)k>pw(j)k。其中∑k=1,…,rnk=N。此时，Sp对应的mass函数为


m(A)=Cp{pw(l)k-pw(l+1)k},A={w(1)k,w(2)k,…,w(l)k},1≤l≤nk-1

Cppw(nk)k,A=Wok,1≤k≤nk-1

0,其他（3454）


其中，Cp=∑k=1,…,rmax{pw: w∈Wk}-1。
3. 基于隶属度函数生成mass函数的方法
经典集合论中，“属于”或“不属于”，两者必取其一，非此即彼。也就是说经典集合中的特征函数与二值逻辑相对应，只能取0,1两个值，也就无法表达现实中存在的“亦此亦彼”的模糊现象。取值推广到［0,1］闭区间，这就形成了模糊数学中的隶属度函数。关于隶属度函数的获取已经出现了许多行之有效的方法，包括模糊统计方法、主观指派方法、二元对比排序法等［4041］。
设Θ={θ1,θ2,…,θn}为辨识框架，{f1,f2,…,fn}为相应的隶属度函数，有如下几种典型的mass函数生成方法。
（1） 依Pi=fi∑j=1,…,nfj将隶属度函数归一化，对应的mass函数生成如下［42］


m({θi})=Pi（3455）


该方法实际上是预设了焦元结构为单点焦元。这样的mass函数定义方式实际上等同于标准的概率定义。单点焦元的优势在于运算简单方便，但无法充分体现证据理论的优势，即无法表达和区分“不确定”和“不知道”。
（2） 依Pi=fi∑j=1,…,nfj将隶属度函数归一化，对应的mass函数生成如下［43］


m({θi})=αPi


m(Θ)=1-α∑ni=1Pi（3456）


其中，α为折扣系数。该方法实际上是预设了焦元结构为单点焦元及辨识框架的全集。将概率值打折扣赋予单点焦元，剩余部分赋给全集，以表征“不知道”。
（3） 依Pi=fi∑j=1,…,nfj将隶属度函数归一化，对应的mass函数生成如下［43］


m({θi})=α·Pi

m({θci})=α·∑j≠iPj

m(Θ)=1-m({θi})-m({θci})=1-α（3457）


其中，α为折扣系数，θci=Θ-θi是θi的余集。该方法实际上是将mass赋值赋予辨识框架中单点焦元及其相应反命题的焦元，剩余部分mass赋值赋予全集，来描述“不知道”。
（4） 依Pi=fi∑j=1,…,nfj将隶属度函数归一化，取i1=argmaxjPj，i2=argmaxj,j≠iPj，对应的mass函数生成如下［44］: 


m(A1)=Pi1,A1={θi1}

m(A2)=Pi2,A2={θi2}

m(Θ)=1-m(A1)-m(A2)（3458）


该方法中，选取隶属度值最高的辨识框架中的两个元素，作为单点焦元，以及辨识框架全集作为焦元结构的定义。归一化过后的隶属度赋值的最大两个赋值赋予上述两个单点焦元，剩余赋值赋予全集，来描述“不知道”。
（5） 协调证据中的隶属度函数向mass函数的转换。协调的mass函数，也称作一致支撑的mass函数，焦元满足依次嵌套。此时隶属度函数等价于单点似真度函数［4546］。此时的单点似真度函数也被称为外形函数或单点覆盖函数。
一般地，设m是一个协调（一致支持）的mass函数，若其焦元为


Ai={xj; j≤i}(i≤n)（3459）


其中，n为辨识框架中元素的个数。ri，i=1,…,n，maxi ri=1为其隶属度函数，则有


m(Ai)=ri-ri+1(i≤n)（3460）


其中，rn+1=0。

该方法求解mass函数，也预设了焦元结构为嵌套形式。
本节介绍的很多方法都是由隶属度函数出发来获取mass函数，这是因为隶属度函数本身是针对单点赋值的，其获取与mass函数的获取（包括焦元结构的确定以及相应的mass赋值的确定）相比，相对较为容易。
还有其他一些mass函数的获取方法，比如文献［47］中，利用目标速度和加速度获取mass函数； 文献［48］中，利用模糊c均值聚类来实现mass函数的获取； 而在文献［49］中，则是利用基于Gauss模型假设的迭代估计来实现mass函数获取； 在文献［50］中，利用广义粗集模型中的容差关系及决策表来生成mass函数。随着证据理论研究的深入和应用的拓展，相信会有越来越多行之有效的mass函数获取方法出现。
3.5随机有限集概略
因为随机有限集理论正在成为多目标跟踪领域的一个研究热点，而且其理论基础与随机集理论有一定的联系，因而本节主要讨论随机有限集的基本概念和理论，然后讨论Mahler的有限集统计理论。
3.5.1概述
在图像研究中，如果物体几何形状是随机变化的，用一个点过程描述这样的问题就很难满足。在目标跟踪中，如果跟踪的目标不是一个点目标，而是一个随机变化的目标群，同样用点过程来描述和处理有本质的困难。
20世纪60年代，人们已经注意到这个问题。Moyal首先提出了群体随机点过程的概念［51］。1975年，Mathéron第一个系统地提出了随机几何的思想，并提出用随机集（闭集）来解决这个问题的思路［52］。随机有限集是具有有限个元的随机集，由于其简单性在处理实际问题时受到特别重视，人们对其进行了更多的研究。1976年Ripley［53］的研究和1984年Baudin ［54］的研究指出，随机有限集在本质上也是随机点过程的研究基础，二者实质上是等价的。随机有限集应用于信息融合领域起始于1990年Mahler提出的有限集统计（Finite Set Statistics，FISST）理论［5561］，并且逐步应用于目标跟踪领域［62］。
3.5.2随机有限集的概念
先考虑Mathèron拓扑，Mathèron拓扑又称为HitorMiss拓扑。在实数域上，经常用到Borel σ代数。同样，在实数域上所有的闭子集，我们希望找到某种意义下的拓扑T。在该意义下，随机闭集的概率属性能够用更为简单的方式刻画出来。
设U=Rd表示d维实数空间，F(Rd)表示Rd上的所有闭子集，Ω表示基本事件空间。定义随机集X: Ω→F，设AU，子集类FA={F∈F: F∩A≠}F，指的是“击中”（Hit）A的所有闭子集类； 而FA的补集类FcA={F∈F: F∩A=}则表示“未击中”（Miss）A的所有子闭子集类。所以以这种方式产生的拓扑称为HitorMiss拓扑。如果仅限于有限可测闭子集，那么这种映射就称为随机有限集，下面给出严格定义。
定义3.5.1对于局部紧的Hausdorff可分空间E（例如Rn），
F(E)是E上所有有限子集构成的集类，称为Mathéron拓扑； Ω表示基本事件空间，定义可测映射［56,63］


Σ: Ω→F(E)（351）


那么，Σ就称为随机有限集（random finite sets，RFS）。
考虑(Ω,B,P)是一个概率空间，定义于概率测度P上的RFS的概率特性为

PΣ(A)=P(Σ-1(A))=P({ω:Σ(ω)∈A})（352）

分别有三种方式进行刻画： 
（1） 概率分布函数。对于任意的Borel子集A∈F（E），随机有限集Σ的分布函数为

PΣ(A)=P(Σ-1(A))=P({ω: Σ(ω)=A})参考文献［55］给出的表达式是PΣ（A）=P（Σ-1（A））=P（{ω: Σ（ω）∈A}）,疑是笔误。（353）

（2） 信度函数（belief mass function，BMF）。对于任意闭子集AE，


βΣ(A)=P({ω: Σ(ω)A})（354）


（3） 空概率（void probability）函数。对于任意闭子集AE，


ζΣ(A)=P({ω: Σ(ω)∩A≠})=βΣ(Ac)（355）


其中,Ac是A的补集。
3.5.3随机有限集的统计
对于一般的随机变量的概率密度（离散情况下是概率质量函数）,可以通过积分（离散情况下求和）获得概率分布函数。同样，对概率分布函数可利用RandonNikedym导数获得概率密度函数。
但对于RFS（随机有限集）来说，定义在可测集E上的置信测度不满足可列可加性，RandonNikedym导数不能直接应用，并且传统的概率分布是定义在区间上的，而对于集合来说，区间不再适用，只能用集合之间的包含关系来定义，因此随机有限集Σ的概率分布定义如下： 

PΣ(S)=P(Σ∈S)（356）


随机有限集的测度和一般概率密度不同，它是定义在可测的有限集上的，而不是Broel集上。它的概率属性一般通过置信函数（belifemass function）来刻画。我们以随机有限集的积分为例来说明随机有限集不能直接套用通常的概率统计理论。设Y∈Rm，它的期望定义为

E(Y)=∫SRmypY(y)dy（357）

其中SRm是概率密度函数pY(y)的分布范围。但是，对于随机有限集Σ来说，必须定义Rm上的某个σ有限测度q，令Y=q(Σ)，根据Robbin公式，Y的期望定义为

E(Y)=E［q(Σ)］=∫μΣ(z)dq(z)（358）

其中μΣ(z)是随机有限集Σ的单点覆盖函数，并且μΣ(z)ΔP(ω∈Ω:z∈Σ(ω))。如果Σ为
随机有限集，并且q(z)是关于Lebesgue测度绝对连续的，就会发现对任何随机有限集，q(z)=0，并且μΣ(z)=0； 因此，Robbin公式只有平凡解。 这说明对随机有限集来说，不能直接套用一般随机变量积分的思路。
由于类似的原因，以及随机有限集问题本身的复杂性，它在实际工程中很难直接应用。为此，Mahler提出了一套面向工程的基于随机有限集的统计方法，即有限集统计理论（FISST）。其关键是解决随机有限集的置信密度和置信函数之间的关系，核心是建立了FISST上的有限集积分和有限集导数。
1. 有限集积分
定义3.5.2对于RFS，YY，Y是目标跟踪空间； 对于Y的任意实值函数f(Y)，在空间SY上的积分定义为

∫Sf(Y)δY=f()+∑∞n=11n!∫Snf({y1,…,yn})dy1…dyn（359）

如果S=Y时满足∫S=Yf(Y)δY=1，那么f(Y)就是密度函数。
此时，似然函数和转移密度同样满足∫fk(Z|X)δZ=1，∫fk+1|k(Y|X)δY=1。
例题3.5.1（全局均匀密度函数）［64］考虑混杂空间R=Rn×W，其中W是有限的离散空间。T为混杂空间R上的一个闭子集，对于所有的有限子集ZR，定义如下集函数为

uT,M(Z)=|Z|!Mλ(T)Z,ZT，|Z|<M

0,其他

那么根据式（359），对于所有闭子集S有


∫SuT,M(Z)δZ=∑∞n=01n!∫SnuT,M({ξ1,…,ξn})dλ(ξ1)…dλ(ξn)
=∑M－1n=01n!∫(T∩S)nn!Mλ(T)ndλ(ξ1)…dλ(ξn)
=1M∑M－1n=0λ(S∩T)nλ(T)n=1□

2. 有限集导数
对于任意随机有限集Y的集函数F(Y)，其导数定义为

δFδy(S)=limν(Ey)→0F(S∪Ey)－F(S)ν(Ey)

δβδY(S)=δnβδyn…δy1(S)=δδn－1βδynδyn－1…δy1(S)（3510）

其中β(S)是置信函数，ν(S)是状态空间S的超体积（Lebesgue测度）。
有限集导数满足如下的和律、积律、常数律和幂律。

和律： δδY(a1β1(S)+a2β2(S))=a1δβ1δY(S)+a2δβ2δY(S)（3511）

其中a1，a2是任意常数。

积律： δY(β1(S)β2(S))=∑WYδβ1δW(S)δβ1δ(Y－W)(S)（3512）
常数律： δδYK=0，如果Y≠（3513）

其中K为常数。
幂律：  如果p(S)是一个置信函数，它具有密度函数fp(y)，则

δδYp(S)n=n!(n－k)!p(S)n－kfp(y1)…fp(yk),k≤n

0,k>n（3514）


例如，对于量测集S和状态集X，S关于X的条件置信函数如下

βk(S|X)=P(ΣkS)=∫Sfk(Z|X)δZ

βk+1|k(S|X)=P(Σk+1|kS)=∫Sfk+1|k(Y|X)δY（3515）

其中Σk,Z均是RFS，那么可以通过求导获得如下的密度函数

fk(Z|X)=δβkδZ(|X)

fk+1|k(Y|X)=δβk+1|kδY(|X)（3516）


例题3.5.2考虑杂波条件下单目标似然函数。假设在k时刻， Σk为量测RFS，Xk为目标状态集，其中目标量测RFS为Φk，杂波量测RFS为Ck，即Σk=Φk∪Ck，量测数据集为Yk={yik}。那么，在量测空间So中置信函数为

βΣk(So|Xk)=P(ΣkSo|Xk)=P(ΦkSo|Xk)P(CkSo)

=βΦk(So|Xk)βCk(So)

利用乘积律，对上式求导并取空集

δδYk(βΦk(So|Xk)βCk(So))=∑WYkδβΦkδW(S)δβCkδ(Yk－W)(S)
=∑ZkYkδβΦkδZk(S)δβCkδ(Yk－Zk)(S)

=∑ZkYkfΦk(Zk|Xk)fCk(Yk－Zk)
=pc(mk)(1－PD)+pc(mk－1)PD∑ifΦk(zik|xk)□


例题3.5.3两个目标似然函数，对于如下的置信函数

βΣ(S|x)=1－PD+PDpf(S|x)
βΣ(S|x1,x2)=［1－PD+PDpf(S|x1)］［1－PD+PDpf(S|x2)］

那么，似然密度分别为

f(|)=1
f(|x)=1－PD
f(z|x)=PDf(z|x)
f(|x1,x2)=(1－PD)2
f(z|x1,x2)=PD(1－PD)f(z|x1)+PD(1－PD)f(z|x2)
f(z1,z2|x1,x2)=P2Df(z1|x1)f(z2|x2)+P2Df(z2|x1)f(z1|x2)

其中，x,x1,x2为不同目标的状态，z,z1,z2对应各自的量测； pf(S|x)是密度为f(z|x)的概率分布函数。□
3.5.4典型RFS（随机有限集）分布函数
分布函数是随机有限集理论的基础，依据分布函数的不同，典型的RFS包括Poisson RFS、单Bernoulli RFS、多Bernoulli RFS等。下面对几种RFS做一个简要的介绍。
1. Poisson RFS
对于状态空间X上的RFS X，若其势|X|满足Poisson分布，就称为Poisson RFS，用v(x)表示其强度函数，则其均值和概率密度函数可以分别表示为=∫v(x)dx和v(x)/。Poisson RFS的概率密度函数可以表示为

π(X)=e－vX（3517）

对于状态空间上的h: X→R，满足hX=∏x∈Xh(x)，规定h=1。
2. Bernoulli RFS
对于状态空间X上的Bernoulli RFS，若用p表示其元素分布的概率密度函数，用r表示其存在概率，则其概率密度函数可以表示为

π(X)=1－r,X=


r·p(x),X={x}（3518）

3. 多Bernoulli RFS
对于多Bernoulli RFS，它是个数固定且彼此之间相互独立的Bernoulli RFS的集合，分别用r(i),p(i)表示每个Bernoulli RFS的存在概率和概率密度函数，且满足r(i)∈(0,1)，i=1,2,…,M，X=∪Mi=1X（i），M表示其中所包含的Bernoulli RFS的数量。由于Bernoulli RFS的概率密度函数仅仅与参数r和p有关，所以完全可以用参数集{(r(i),p(i))}Mi=1对其表示。对参数集进行预测更新即可，其势分布可以表示为∑Mi=1r(i)，概率密度函数如下

π()=∏Mj=1(1－r(j))

π({x1,…,xn})=π()∑{i1,…,in}∈Fn({1,…,M})∏nj=1r(ij)p(ij)(xj)1－r(ij)（3519）

3.5.5标签RFS
不同于传统的RFS，标签RFS为不同目标的状态x(x∈X)添加了可以识别身份的标签l∈L={αi: i∈N}，其中N表示目标的个数。为区别非标签RFS变量，多目标的状态用粗体标签RFS表示为［9495］ 

Xk={(xk,1,l1),…,(xk,N(k),lN(k))}（3520）

其中用大写实体的Xk表示多目标状态集合，用小写实体xk,i表示目标i在k时刻的带标签状态。为了实现不同目标的标签是不同的，用下述方程进行约束

Δ(X)=1,|L(X)|=|X|


0，|L(X)|≠|X|（3521） 

其中，L(X)表示状态集到X标签l的映射，|·|表示集合中元素的个数。
简单地说，标签随机有限集（LRFS）就是在标准RFS中为每个元素增添一个独一无二的标签。这样一来可以用来识别定位跟踪区域内的每个目标，从而生成有效航迹。用L={αi: i∈N}表示标签空间，在原来的状态x∈X上添加一个标签信息l∈L，则目标状态(x,l)定义在了空间X×L上。
1. 标签Poisson RFS
类比于前面提及的Poisson RFS，标签泊松RFS只是添加了一个标签信息，这里就不做过多赘述，直接给出概率密度函数的表达式［95］

π({(x1,l1),…,(xn,ln)})=δL(n)({l1,…,ln})Pois〈v,1〉(n)∏ni=1v(xi)〈v,1〉（3522）

其中，Poisλ(n)=e-λλn/n!表示参数为λ的Poisson分布，L(n)={αi∈L}ni=1。
2. 标签多Bernoulli RFS
若将标签多Bernoulli RFS的参数集表示为{(r(ζ),p(ζ)): ζ∈Ψ}，将与之对应的标签状态表示为α(ζ)，其中，α: Ψ→L是一个单射，在原来状态信息的基础上增添了标签信息，把原来状态空间X上的问题扩展到了空间X×L上，其概率密度函数可以表示为［95］

π({(x1,l1),…,(xn,ln)})=δ(n)(|{l1,…,ln}|)×

∏ζ∈Ψ(1-r(ζ))∏nj=11α(Ψ)(lj)r(α－1(lj))p(α－1(lj))(xj)1－r(α－1(lj))

（3523）


简化公式为

π(X)=Δ(X)1α(Ψ)(L(X))［Φ(X;·)］Ψ（3524）

其中，Δ(X)为表示标签是否唯一的一个指标,δ|X|(|L(X)|)为指示函数，用来表示是否恰好为定位跟踪区域内的每个目标添加了一个唯一的标签，L(X)表示X的标签，则有

Φ(X;ζ)=1－r(ζ),α(ζ)L(X)


r(ζ)p(ζ)(x),(x,α(ζ))∈X（3525）

3. 广义标签多Bernoulli RFS
GLMB为空间X×L上的标签RFS，其分布为［95］

π(X)=Δ(X)∑c∈Cw(c)(L(X))［p(c)］X（3526）

其中，C为离散变量，w(c)(L)，p(c)分别满足

∑l∈L∑c∈Cw(c)(l)=1

∫p(ζ)(x,l)dx=1（3527）

3.5.6随机有限集的Bayes滤波
考虑传统的Bayes滤波公式为

pk|k－1(xk|z1:k－1)=∫pk|k－1(xk|xk－1)pk－1|k－1(xk－1|z1:k－1)dxk－1（3528）
pk|k(xk|z1:k)=gk(zk|xk)pk|k－1(xk|z1:k－1)∫pk(zk|xk)pk|k－1(xk|z1:k)dxk（3529）

其中z1:k－1Δ{z1,z2,…,zk－1}。类似地，对于随机有限集来说，基于信度函数上的集合积分和导数，Mahler给出了FISST框架下的Bayes公式如下

fk|k－1(Xk|Z1:k－1)=∫fk|k－1(Xk|Xk－1)fk－1|k－1(Xk－1|Z1:k－1)δXk－1（3530）
fk|k(Xk|Z1:k)=ρk(Zk|Xk)fk|k－1(Xk|Z1:k－1)∫ρk(Zk|Xk)fk|k－1(Xk|Z1:k－1)δXk（3531）

其中Xk,Z1:k－1分别是系统状态和直到k－1时刻的量测； 而fk|k(·),fk|k－1(·),ρk(·)分别是状态更新、状态提前一步预测和量测噪声的置信密度函数。

FISST框架下的Bayes公式和传统概率框架下的Bayes公式有何异同？有何联系？Vo等给出了如下的命题［65］。
命题1 假设Σ是局部紧的Hausdorff可分空间E上的RFS，并且具有概率测度PΣ和信度函数βΣ，如果PΣ是关于μ绝对连续，μ是一个没有进行正则化的Poisson点过程测度，具有单位K－1，对于任意子集A∈F(E)，定义如下Poisson点过程测度

μ(A)=∑∞i=0λi(Σ－1(A)∩Ei)i!

那么

dPΣdμ=KXd(βΣ)X （3532）

这说明FISST框架下的置信密度函数是带有单位K－|X|的，传统的Bayes公式和FISST框架下的Bayes公式相差单位K－|X|。因此，二者之间存在如下关系

pk－1|k－1(X|Z1:k－1)=K|X|sfk－1|k－1(X|Z1:k－1)

pk|k－1(X|Z1:k－1)=K|X|sfk|k－1(X|Z1:k－1)

pk|k－1(X|Z1:k－1)=K|X|sfk|k－1(X|Z1:k－1)

pk|k－1(X|Xk－1)=K|X|sfk|k－1(X|Xk－1)

pk|k－1(X|Xk－1)=K|X|sfk|k－1(X|Xk－1)

pk|k－1(X|Xk－1)=K|X|sfk|k－1(X|Xk－1)

pk|k－1(X|Xk－1)=K|X|sfk|k－1(X|Xk－1)

pk|k－1(X|Xk－1)=K|X|sfk|k－1(X|Xk－1)

pk|k(X|Z1:k)=K|X|sfk|k(X|Z1:k)

gk(Z|Xk)=K|Z|oρk(Z|Xk)（3533）

其中，pk|k(·),pk|k－1(·)分别表示通常概率意义下的先验密度函数和提前一步预测密度函数，gk(·)是似然函数； 而fk|k(·),fk|k－1(·),ρk(·)分别是相应的置信密度函数。
对随机变量（向量）而言，在线性高斯情况下，利用标准的Kalman滤波器，就可以更新状态变量的一阶矩和二阶矩的估计。然而，对于随机有限集而言，是否存在只需更新前两阶矩的滤波公式呢？这就需要解决两个问题： 首先要确定随机有限集的矩是否存在； 其次在矩存在的前提下，是否存在其递推公式。此外，随机有限集Bayes公式的计算也有着本质的困难。
（1） 计算难度大大增加。根据式（3529）的随机有限集Bayes公式中包含一系列的高维积分，这个在实际中很难应用。此外，式（3529）存在一个假设： 置信密度函数f({y1,…,yn})的分布是对称的，即对于序列{y1,…,yn}的任意的序列重排{yi1,…,yin}，f({yi1,…,yin})与f({y1,…,yn})二者具有相同的分布。
（2） 估计准则的含义是什么？是否存在？对于传统的随机变量（向量），常用的Bayes估计准则包括最小均方差估计（MSE）和极大后验估计（MAP），分别定义如下： 

MSE：  x^k=E(xk|z1:k)
MAP：  x^k=arg maxxk f(xk|z1:k)

但是，对于随机有限集Xk来说，条件期望E(Xk|Z1:k)没有任何意义，或者说根本不存在，更谈不上MSE准则问题。MAP估计则与状态的单位有关系。因此，这些估计准则均不适用于随机有限集的估计。这些困难促使人们寻找更为可行、简化和实用的算法，这一点，我们将在随机有限集多目标跟踪理论中进一步讨论。
3.6统计学习理论与支持向量机基础
1963年Vapnik在解决模式识别问题时提出了支持向量方法，这种方法从训练集中选择一组特征子集，使得对特征子集的划分等价于对整个数据集的划分，这组特征子集被称为支持向量（support vector，SV），这种理论称为支持向量机（support vector machine，SVM）理论。1971年Kimeldorf提出使用线性不等约束重新构造SV的核空间，解决了一部分线性不可分问题； 1990年，Grace、Boser和Vapnik等开始对SVM进行系统研究； 1995年Vapnik正式提出统计学习理论［70］。SVM理论越来越受到人们的关注，而且已经几乎成为数据分类的一种标准方法。
3.6.1统计学习理论的一般概念
机器学习是一种基于数据的学习方法，它主要研究从观测数据（样本）出发寻找规律并构造一个模型，利用该模型可对未知数据或者无法观测的数据进行预测。这种模型被称为学习机（learning machine）。机器学习的过程就是构建学习机的过程。机器学习包含很多种方法，如决策树、遗传算法、人工神经网络、隐Markov链（HMM）等。然而迄今为止，关于机器学习还没有一种被共同接受的理论框架，但关于实现方法大致可以分为三种。
第一种是经典的（参数）统计估计方法（statistical estimation method）。在这种方法下，参数的依赖关系被认为是先验已知的，训练样本用于估计依赖关系的参数。这种方法的缺点在于： 一是因为“维数灾难”，很难将这种方法扩展到高维数据空间； 二是先验的依赖关系在很多情况下难于获取。
第二种方法是20世纪80年代发展起来的经验非线性方法（empirical nonlinear method），如人工神经网络（ANN）和多变量自适应回归分析。这些方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这些方法目前还缺乏统一的数学理论指导。
第三种方法是20世纪60年代后期发展起来的统计学习理论（statistical learning theory或SLT），它是专门用于有限样本情况下非参数估计问题的机器学习理论。与传统统计学相比，这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。Vapnik等从20世纪60至70年代开始致力于此方面研究，到90年代中期其理论发展已趋于成熟，而且统计学习理论开始受到越来越广泛的重视。
统计学习理论建立在一套较坚实的理论基础之上，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题 （如神经网络结构选择问题、局部极小点问题等）； 同时，在这一理论基础上发展了一种新的通用学习方法——支持向量机理论，它已初步表现出很多优于已有方法的性能。一些学者认为,SLT和SVM正在成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发展。
机器学习的目的是根据给定的训练样本求取系统输入输出之间依赖关系的估计，使它能够对系统行为做出尽可能准确的预测。
定义3.6.1设变量y与变量x之间存在一定的未知依赖关系，即遵循某一未知的联合概率分布P(x,y)，机器学习问题就是根据l个独立同分布（i.i.d）的观测样本


(x1,y1),(x2,y2),…,(xl,yl)（361）


在一组函数{f(x,α)}中按某个准则选择一个最优的函数
f(x,α0)对依赖关系进行估计，其中α是参数，而
f(x,α)就称为是一个学习机（learning machine）。如果对于给定的输入x和α的一个选择，其输出f(x,α)总是相同的，这个学习机称为是确定性的（deterministic）； 否则称为不确定性的（uncertainty）。对于确定性学习机中α的一个特定选择，就称其为训练过的学习机（trained machine）。
例题3.6.1考虑具有固定结构的一个人工神经网络，α就是所有的权系数和偏置，在此意义下就是一个学习机。如果给定α的一组值，这个人工神经网络就是一个训练过的学习机。显然，给定一组输入x和α的值，这个人工神经网络输出为确定值，则其为确定性的人工神经网络。□
定义3.6.2对于一个学习机，损失函数（loss function）L(y,f(x,α))表示用f(x,α)对y进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数，针对三类主要的学习问题分别定义如下。
（1） 模式识别问题： 输出变量y是类别标号； 对于只有两种模式的情况y={0,1}或者y={-1,1}，此时损失函数一般定义为


L(y,f(x,α))=0(或-1),y=f(x,α)

1,y≠f(x,α)（362）


（2） 函数逼近问题： y∈R是连续变量，损失函数一般以定义为


L(y,f(x,α))=(y-f(x,α))2或L(y,f(x,α))=12|y-f(x,α)|（363）


（3） 概率密度估计问题： 学习的目的是根据训练样本决定
x的概率密度，设被估计的概率密度为p(x,α)，则损失函数一般定义为


L(p(x,α))=-logp(x,α)（364）


定义3.6.3对于一个学习机，损失函数的期望


R(α)=∫L(y,f(x,α))dP(x,y)（365）


称为期望风险（expected risk）或真实风险（actual risk）。而经验风险（empirical risk）则是训练集上的平均误差，即


Remp(α)=1l∑li=1L(yi,f(xi,α))（366）


注意经验风险中并没有出现概率分布。对于特定的α的一个选择，以及特定的训练样本(xi,yi)，经验风险是一个确定的值。
传统的机器学习方法采用了所谓的经验风险最小化（ERM）准则，即用样本定义经验风险如式（366）所示。该式作为对式（365）的估计，设计学习算法使其最小化，这就是经验风险最小化准则。
3.6.2学习机的VC维与风险界
定义3.6.4考虑相应于两个模式类的识别问题，其中函数f(x,α)∈{1,-1}，x,α。对于给定的一组l 个点，可以按所有2l个可能的方式进行标识； 对于每个可能的标识，如果在{f(α)}中总能取得一个函数，这个函数能够用来正确地区分这些标识，称这l 个点构成的点集能够被{f(α)}分隔（shattered）。函数族{f(α)}的VC维（Vapnik Chervonenkis dimension）定义为能够被{f(α)}分隔的训练点l的最大数目。若对任意数目的样本都有函数能将它们分隔，则函数集的VC维是无限大。
注意，如果VC维是h，那么至少存在一组h个点的集合能够被分隔。但是在一般情况下，任意一组h个点的集合都能被分隔的结论却是不正确的。
例题3.6.2考虑一个分类问题。假定所有的数据来自空间R2。对于空间的任意三个点的集合{x1,x2,x3}，分为“左”“上”“下”，而且有8种（23）可能的标识（见图361（a））


x1→1,x2→-1,x3→1; x1→-1,x2→1,x3→-1; x1→-1,x2→-1,x3→-1

x1→1,x2→1,x3→1; x1→1,x2→1,x3→-1; x1→-1,x2→-1,x3→1

x1→1,x2→-1,x3→-1; x1→-1,x2→1,x3→1


对于这种标识，总可以找到一组有向直线将不同的标识点进行分隔（注意标识不是赋值）。
{f(α)}由有向直线组成，对于给定的直线，在直线一边的所有点规定属于类别1，而所有在另一边的点规定属于类别-1。直线的方向在图361（a）中用箭头表示，其正方向一边的点标识为1。所以R2中一组有向直线的VC维是3。然而，同一直线上的三个点任意标识，却不能保证被有向直线分隔，这却不影响R2中一组有向直线的VC维是3。


图361R2中的VC维


但是，对于空间四个点的集合{x1,x2,x3,x4}，分为“左上”“右上”“左下”“右下”，我们仅取一种标识（见图361（b））： x1→-1,x2→1,x3→1,x4→-1，任何一个有向直线都不能把不同的标识点进行分隔。其实，对于任意四个点的集合，采用16种可能的标识，都不可能找到一组有向直线将不同的标识点完全进行分隔。□
现在考虑Rn中的有向超平面，下面的定理将非常有用。
引理1Rn中两个点集能够被一个超平面分隔的充分与必要条件是其凸包（包含该点集的最小凸集）的交集为空集。
证明见文献［1，67］。▉
定理3.6.1考虑
Rn中m个点的集合，选择其中任何一个点作为原点，那么m个点能够被有向超平面分隔的充分与必要条件是，除了原点外其余点的位置向量是线性独立的。
证明
（1） 其余点的位置向量线性独立m个点能够被有向超平面分隔。把原点标识为O，而且假定其余的m-1个点的位置向量是线性独立的。考虑对任意一种可能的标识，按二值标识把m个点划分为两个子集S1和S2，分别有m1和m2个点，所以m1+m2=m。不妨设S1包含点O，则根据凸组合的定义，S1的凸包C1中所有点的位置向量x满足


x=∑m1i=1αis1i,∑m1i=1αi=1,αi≥0（367）


其中s1i就是S1中m1个点的位置向量（包括原点的零向量）。类似地，S2的凸包C2中所有点的位置向量x满足


x=∑m2i=1βis2i,∑m2i=1βi=1,βi≥0（368）


其中s2i就是S2中m2个点的位置向量。
现在假定C1∩C2=D≠，存在x∈DRn同时满足式（364）和式（365），两方程相减得


∑m1i=1αis1i-∑m2j=1αjs2j=0（369）


这就表明这两组m-1个非零位置向量线性相关，这与线性独立的假设相矛盾。再根据引理1，因为C1∩C2=，则存在一个超平面分隔S1和S2。
（2） m个点能够被有向超平面分隔其余点的位置向量线性独立。反设m-1个非零位置向量线性相关，则存在m-1个数γi使得


∑m-1i=1γisi=0（3610）


如果所有的γi具有相同的符号，则可以通过比例变换使得γi∈［0，1］，且∑iγi=1。
上式表明原点处在其他点的凸包中，根据引理1，不存在超平面可以把原点与其他点分离，所以m个点不能够被有向超平面分隔。
如果所有的γi不具有相同的符号，把所有负号的放在一边，得


∑i∈I1|γi|si=∑j∈I2|γj|sj（3611）


其中I1,I2是对集合S-O的划分所对应的指标集合。变换比例使得下面两组中的任意一组成立


∑i∈I1|γi|=1，且∑j∈I2|γj|≤1

∑i∈I1|γi|≤1，且∑j∈I2|γj|=1（3612）


不失一般性，假设后者成立。那么方程（367）的左边是点集∑i∈I1si∪O的凸包中点的位置向量，右边就是点集∑j∈I2sj的凸包中点的位置向量，所以凸包的交集不空。根据引理1，不存在超平面可以把两个凸包分离，所以m个点不能够被有向超平面分隔。
这与假设相矛盾，所以结论成立。▉
推论Rn中有向超平面集合的VC维是n+1。
证明因为我们总能在Rn中选择n+1个点，其中一个点作为原点，而其余n个点的位置向量线性独立； 但是，我们却不能在Rn中选择n+2个点，其中一个点作为原点，而其余n+1个点的位置向量线性独立（Rn维数的限制）,从而结论成立。▉
注在Rn中至少可以找到一组n+1个点能够被超平面分隔，但不是任意一组n+1个点都能够被超平面分隔。例如把所有点集中在一条直线上的情况就不能被分隔。
定义3.6.5对于一个学习机，假定损失函数以概率1-η取值，其中0≤η≤1，那么下面的误差界成立


R(α)≤Remp(α)+h(log(2l/h)+1)-log(η/4)l（3613）


其中h是VC维，是对上述容量概念的一个度量，上式右边称为风险界（risk bound）,又称为推广性的界。它由两部分组成，第一项是训练误差造成的经验风险，第二项是置信范围，而后者与学习机的VC维及训练样本数有关。
此式表明，在有限训练样本下，学习机的VC维越高 （复杂性越高），则置信范围越大，导致真实风险与经验风险之差可能越大。这就是为什么片面追求经验风险最小化会导致出现过学习（over fitting）现象。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，对新的样本才有较好的泛化能力。
关于式（3613）的风险界，有三点必须注意。一是它不依赖于概率分布P(x,y)，因为我们只是假定训练数据和测试数据是按分布P(x,y)抽取的独立同分布的数据； 二是上式左边通常是无法计算的； 三是只要我们知道了h的值，上式右边的值是很容易计算的。
VC维是对给定的一组函数容量概念的具体化。直观上说，人们可能期望有较多参数的学习机具有更高的VC维，而有较少参数的学习机具有更低的VC维。但是这种直观的认识却是不对的。例如，下面例题中的学习机只有一个参数，但它的VC维却是无限大。
例题3.6.3考虑阶跃函数θ(z),z∈R，θ(z)=1,z>0； θ(z)=-1,z≤0。再考虑一个参数的函数族，定义为


f(x,α)≡θ(sin(αx)),x,α∈R（3614）


选择任意一个l∈N，寻求l个点能够被这一族函数分隔。选择点xi=10-i,i=1,2,…,l； 规定标识y1,y2,…,yl,yi∈{-1,1}。于是，如果我们选择


α=1+∑li=1(1-yi)10i2π（3615）


那么f(α)就能给出这种标识。图362是l=4的一种标识的图形表示。所以这个学习机的VC维是无限大。需要注意的是，虽然在本例题中对任意大的l，总能找到l个点构成的点集，按任意标识都可以被选择的函数族分隔，但并不意味着任意l个点构成的点集都可以被选择的函数族分隔。例如取l=4，xi=i,i=1,2,3,4； 相应的y1,y2,y4=-1,y3=1，就不能被式（3615）的函数族分隔。


图362l=4的一种分隔□





图363VC置信范围随h单调增



现在回过头来考察式（3613）的界，其右边第二项随着h的变化而变化。给定一个置信水平95%（η=0.05），而且假定训练集的样本数是10000，VC置信范围将是h的单调增函数，无论l取值多大均是如此，如图363所示。于是，人们希望在经验风险为零的前提下，选择一个学习机，使得与其相关联的函数具有最小的VC维。然而，这将导致最差的误差界。于是，人们又希望在经验风险非零的前提下，选择一个学习机，使式（3613）的右边为最小。如果采用这一策略，仅仅以式（3613）为导向，只选择概率，就可得到实际风险的上界。这样做并不妨碍具有相同经验风险值的具体的学习机有很高的VC维，而得到更好的性能。
所以可以通过最小化h而达到最小化风险界的目的。
下面将讨论结构风险最小化（structural risk minimization,SRM）的问题。由式（3613）看出，要控制学习机器的实际风险，必须同时控制经验风险和置信范围。而为了使得式（3613）右边两项同时最小化，必须使VC维成为一个可控制的变量。
注意，式（3613）的VC置信范围依赖于函数类的选择，尽管经验风险和实际风险都通过训练过程依赖于具体函数的选择。我们希望在被选择的函数集中找到一些子集，使得对这个子集风险界达到最小。显然因为VC维是整数，我们难以使其平滑变化。于是，通过把整个函数族分解为嵌套的子集引入一种“结构”。对于每个子集，要么计算得到VC维h的值，要么得到h的界。于是，SRM就是求取这些使得实际风险达到最小界的函数子集的一个过程。要做到这一点，通过简单地训练一组学习机来完成，一个学习机对应于一个子集； 而对于给定的子集，训练的目的就是最小化经验风险。然后按序列取训练过的学习机，其经验风险与VC置信范围都是最小的。
统计学习理论提出的结构风险最小化方法，就是以经验风险和置信范围这两项最小化为目标的一种归纳方法。方法是把函数集{f(x,α)}构造成一个嵌套的函数子集结构，即令Sn={f(x,α)： 满足第n种约束}，同时满足


S1S2…Sn…（3616）


各个子集对应的VC维满足


h1≤h2≤…≤hn≤…（3617）


此时机器学习的任务是在每个子集中寻找经验风险最小的函数，在子集间折中考虑经验风险和置信范围，使得实际风险最小，如图364所示。


图364按VC维排序使函数嵌套的结构风险最小化



3.6.3线性支持向量机
我们仍考虑标识过的训练数据{xi,yi}，i=1,2,…,l，其中xi∈Rn，yi∈{-1,1}。现在讨论最简单的情况： 在可分离数据上训练得到的线性学习机。
定义3.6.6设Rn中有一个超平面wTx+b=0，其中w∈Rn是参数向量即超平面的法线，b∈R是截距，|b|/‖w‖是超平面到原点的垂直距离（此处‖·‖是欧氏范数），如果这个超平面可以把标识为正的样本集与标识为负的样本集分离开来，则称其为分离超平面（separating hyperplane）。设d+是分离超平面到正样本集的最短距离，而d-是其到负样本集的最短距离。这个分离超平面的“余度”（margin）定义为d++d-。
定义3.6.7所谓线性支持向量机（linear support vector machine）就是一种算法，以求得具有最大余度的分离超平面，即要求所有训练数据满足如下约束条件


xTiw+b≥+1,yi=+1，


xTiw+b≤-1,yi=-1，i=1,2,…,l（3618）


或者写成一个式子


yi(xTiw+b)-1≥0,i（3619）


而以等式形式满足式（3619）的点称为支持向量（support vector）。
现在我们考察式（3618），满足xTw+b=+1的超平面是H1，其法线仍然是w，它到原点的垂直距离是|1-b|/‖w‖； 而满足xTw+b=-1的超平面是H2，其法线也是w，它到原点的垂直距离是|-1-b|/‖w‖； 这是两个平行的超平面。而且d+=d-=1/‖w‖，余度是2/‖w‖。注意，在平行的两个超平面H1和H2之间没有任何训练点。
于是，线性支持向量机求取一对具有最大余度超平面的问题，即在满足式（3619）的前提下对‖w‖2求最小的问题； 就是如下约束优化问题


minw12‖w‖2

s.t.yi(xTiw+b)-1≥0,i（3620）




图365线性分离超平面： 画圈
的点是支持向量



这是一个典型的凸二次规划问题，因为目标函数本身是凸函数，而满足约束的点集也是凸集。
图365给出了二维情况下典型的线性分离直线。处在H1或H2上的点以等式形式满足式（3619），它们的变化影响余度的变化，即影响问题的解，这就是支持向量。
现在把问题转换到Lagrange公式。这样做的必要性是： ①上述优化问题中的约束条件能够用Lagrange乘子的约束来代替，而后者一般易于处理； ②在把问题重新描述的过程中，训练数据将以向量点积的形式出现，便于推广到非线性情况。针对式（3619）的不等式引入正Lagrange乘子αi,i=1,2,…,l； 于是给出Lagrange函数为


LP=12‖w‖2-∑li=1αiyi(xTiw+b)+∑li=1αi（3621）


而对于式（3620）的优化问题，根据文献［66］中的定理9.5.1，可以等价地求解其所谓Wolfe对偶问题，即


maxw,αLP=12‖w‖2-∑li=1αiyi(xTiw+b)+∑li=1αi

s.t.LPw=w-∑li=1αiyixi=0,αi≥0,i=1,2,…,l（3622）


式中α=(α1,α2,…,αl)T，其解与式（3620）的解取得相同的w值。
注意，上式的约束条件等于给定方程


w=∑lj=1αjyjxj（3623）


同时考虑到


LPb=∑li=1αiyi=0（3624）


把以上两个式子代入式（3621），得


LD=∑li=1αi-12∑li,j=1αiαjyiyjxTixj（3625）


于是，对于可分离的线性支持向量机的训练问题就是如下规划问题


maxαLD=∑li=1αi-12∑li,j=1αiαjyiyjxTixj

s.t.∑li=1αiyi=0，αi≥0,i=1,2,…,l（3626）


把求解得到的最优α值代入式（3623）就得到最优的w值。
    对于约束优化问题，KarushKuhnTucker（KKT）条件无论从理论上或实践上都是非常重要的。对于上述约束优化问题，等价的KKT条件可以写成［67］ 


wjLP=wj-∑li=1αiyixij=0,j=1,2,…,n

bLP=-∑li=1αiyi=0

yi(xTiw+b)-1≥0,i=1,2,…,l

αi≥0,αi(yi(xTiw+b)-1)=0,i（3627）


由此不仅可以得到最优的w值，而且可以求得最优的α值和b值。
一旦我们利用l个样本完成了对SVM的训练，我们如何来利用它对数据进行分类呢？实际上我们只是简单地确定测试数据x处在决策分界面（分类超平面）的哪一边。所以分类函数是


f(x)=sgn(wTx+b)（3628）


其中sgn(·)是符号函数； 只是根据括号内的符号来确定x的模式。



图366非完全线性可分时的分离超平面


以上讨论都是针对完全线性可分情况的。然而当数据非完全线性可分时，支持向量学习方法要通过构造一个“软余度”（soft margin）的分类超平面来达到最优分类的效果，如图366所示。
在非完全线性可分情况下，需要考虑分类误差带来的损失，这时在式（3619）中引入一个松弛变量ξi≥0i=1,…,l，成为


yi(xTiw+b)-1+ξi≥0,i（3629）


这时构造的“软余度”分类超平面是由如下优化问题确定


minw12‖w‖2+C∑li=1ξik

s.t.yi(xTiw+b)-1+ξi≥0,i=1,…,l（3630）


式中C是对分类错误的惩罚因子，由使用者选择，用于调整置信范围和经验误差之间的均衡,较大的C意味着较小的经验误差，而小的C意味着更大的分类余度，而在数据不完全可分的情况下，参数C确定了经验风险的水平。而参数k也是可以选择的正整数，以保证是一个凸规划问题； k=2是二次规划问题。而k=1具有更大的优越性，此时Wolfe对偶问题变为


maxαLD=∑li=1αi-12∑li,j=1αiαjyiyjxTixj

s.t.∑li=1αiyi=0，0≤αi≤C,i=1,2,…,l（3631）


问题的解则由下式给出


w=∑Nsi=1αiyixi（3632）


其中Ns就是支持向量数。这与最优超平面的差别仅仅是αi有上界C，如图366所示。
为了得到KKT条件，原问题的Lagrange函数变为


LP=12‖w‖2+C∑li=1ξi-∑li=1αi［yi(xTiw+b)-1+ξi］-∑li=1μiξi（3633）


其中μi是对于松弛变量ξi非负性的Lagrange乘子。于是，有原约束优化问题的KKT条件是


wjLP=wj-∑li=1αiyixij=0,j=1,2,…,n

bLP=-∑li=1αiyi=0

yi(xTiw+b)-1+ξi≥0,i=1,2,…,l

ξi≥0,αi≥0,μi≥0,i=1,2,…,l

αi(yi(xTiw+b)-1+ξi)=0,i

μiξi=0,i（3634）


类似地，我们可以利用最后两个方程来确定b的值。
3.6.4非线性支持向量机
前面讨论的最优分类面都是线性情况，而实际中的大部分识别问题都不必是线性可分的，其数据的分类需要非线性函数。如何把线性分类的方法推广应用到非线性情况，是SVM研究中关键的问题。此时要获得好的分类效果，必须采用非线性决策函数，统计学习理论采用如下的方法。
定义3.6.8所谓非线性支持向量机（nonlinear support vector machine）通过某种预先选择的非线性映射


Φ: L→H（3635）


进行变换，其中L=Rn是一个低维的欧氏空间，而
H是一个高维内积线性特征空间，一般是Hilbert空间； 定义一个核函数（kernel function）K，使得


K(xi,xj)=〈Φ(xi),Φ(xj)〉，xi,xj∈L（3636）


其中〈·,·〉表示H中的内积,使得式（3626）中的目标函数变为


LD=∑li=1αi-12∑li,j=1αiαjyiyjK(xi,xj)（3637）


这样就把低维空间的非线性分类问题转化为高维空间的线性分类问题，采用的方法与线性支持向量机相同。
注在最优分类面中采用适当的核函数K(xi,xj)就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加。用式（3637）代替式（3626）中的目标函数，优化问题是完全相同的，仅仅把问题由低维空间的线性分类变成高维空间的线性分类。问题在于求得最优解需要得到高维空间H的w，即把式（3623）的xi用Φ(xi)代替，例题3.6.5将说明如何构造Φ。
例题3.6.4常用的一个核函数就是Gauss径向基函数（此时无须知道Φ的具体表示）


K(xi,xj)=exp{-‖xi-xj‖2/（2σ2）}


在此特例中H是一个无限维空间，此时直接应用Φ并不方便，在训练算法中可以处处用K(xi,xj)来代替Φ(xi)与Φ(xj)的内积，从而产生一个新的支持向量机对无限维空间进行分类。□
下面我们将讨论什么样的函数K是允许的。
定理3.6.2（Mercer条件）对于任意的对称函数K(x,y)，x,y∈L，以及一个映射Φ： L→H，它可以表示为特征空间H中的内积运算，即K(x,y)=〈Φ(x),Φ(y)〉的充分必要条件是，对于任意不恒等于零的g∈L2(L)，有下式成立


∫K(x,y)g(x)g(y)dxdy≥0（3638）


证明见文献［72］。▉
例题3.6.5考虑L=R2中的数据，我们选择K(xi,xj)=(xTixj)2，则容易找到空间H，以及映射Φ: R2→H，使得(xTy)2=〈Φ(x),Φ(y)〉。我们选择H=R3，则有


Φ(x)=［x21,2x1x2,x22］T





图367映射Φ作用下B在H中的象


我们定义B=［0,1］×［0,1］R2，它在Φ的作用下H中的象如图367所示。
对于B中的数据，经变换后到了高维空间。
注意，对于给定的核函数，Φ和H都不是唯一的。
例如，对于H=R3，可以选择Φ(x)=12［(x21-x22),2x1x2,(x21+x22)］T； 而且对于H=R4，可以选择Φ(x)=［x21,x1x2,x1x2,x22］T。□
在SVM完成训练后，相应于式（3628）的分类函数为


f(x)=sgn∑Nsi=1αiyiK(si,x)+b（3639）


其中si是支持向量，sgn(·)是符号函数。上面描述的就是一般非线性情况下的支持向量机。
前面我们已经多次提到对映射Φ隐含处理的思想，但是我们也可以先构造Φ，然后再得到核函数。下面的例题就是由Φ构造核函数的例子。
例题3.6.6考虑L=R，对于x∈R，设其可以进行Fourier展开并作前N项近似


g(x)=a02+∑Ni=1［a1icos(ix)+a2isin(ix)］


而且能够视为H=R2N+1中的内积，即设


a=［a0/2,a11,…,a1N,a21,…,a2N］T∈R2N+1


Φ(x)=［1/2,cos(x),…,cos(Nx),sin(x),…,sin(Nx)］T∈R2N+1


则g(x)=〈a,Φ(x)〉=aTΦ(x)； 相应地，核函数可以写成


〈Φ(xi),Φ(xj)〉=K(xi,xj)=sin［(N+1/2)(xi-xj)］2sin［(xi-xj)/2］


这很容易证明。令δ=xi-xj，则有


〈Φ(xi),Φ(xj)〉=12+∑Nl=1cos(lxi)cos(lxj)+sin(lxi)sin(lxj)

=-12+∑Nl=0cos(lδ)=-12+Re∑Nl=0ejlδ

=-12+Re{(1-ej(N+1)δ)/(1-ejδ)}

=［cosNδ-cos(N+1)δ］/［2(1-cosδ)］

=［sin((N+1/2)δ)］/［2sin(δ/2)］


这个方法对于很多用点积表示的数据都是适用的，只是表达形式有差异。□
非线性SVM的常用核函数还有


K(x,y)=(xTy+1)p（3640）


这是一个次方为p的多项式数据分类器，图368是一个3次分类器产生的结果。而


K(x,y)=e-‖x-y‖2/(2σ2)（3641）


是一个Gauss径向基函数（RBF）分类器，而且在此情况下通过SVM训练可以自动得到支持向量si、权值向量α和截距b都能自动产生，而且可以获得比经典RBF更好的结果。同时


K(x,y)=tanh (κxTy-δ)（3642）


是一种特殊的两层sigmoid神经网络分类器。


图3683次多项式核函数产生的分界面： 背景色表示决策面的形状


3.6.5用于孤立点发现的Oneclass SVM算法
以上讨论的均是有监督的机器学习算法，能够处理的都是有标定的数据，1999年Bernhard Scholkopf等提出一种能够处理无标定的数据的Oneclass SVM算法［72］，它是一种无监督学习的方法，主要用于异常检测和孤立点发现。孤立点发现的问题可描述如下。
定义3.6.9给定未标定训练数据x1,…,xl∈L，其中l∈N是训练数据的样本数，L是低维样本空间； 假定训练数据中大部分具备某种特性，而很小部分属于孤立点，Oneclass SVM就是要找到一个函数f(x)，在大部分样本上取值为＋1，而在孤立点上取值为-1。其思路是通过核函数的选择，将低维样本空间变换到高维特征空间，然后在特征空间中寻找一个最优分类面，任一点的f(x)值由其落在分类面的两侧来决定。同分类的SVM类似，这个问题的解由以下优化问题来得到


minw,ξi,b12‖w‖2+1vl∑li=1ξi-b

s.t.wTΦ(xi)≥b-ξi,ξi≥0,i（3643）


其中v∈(0,1)是个控制参数，Φ: L→H是变换。
如果(wT,b)T是上面这个优化问题的解，则决策函数为


f(x)=sgn(wTΦ(x)-b)（3644）


f(x)对数据集中大多数点取值为正，同时要求‖w‖比较小，而优化问题（3643）中的参数v用于控制二者的折中。同样，对于问题（3643）的解首先用核函数将原问题映射到特征空间，并采用Lagrange优化方法，得到原问题的对偶问题


minα12∑li,j=1αiαjK(xi,xj)

s.t.0≤αi≤1vl,∑li=1αi=1（3645）


其中K(xi,xj)是核函数，α=(α1,…,αl)T。其最终判决函数f(x)为


f(x)=sgn∑li=1aiK(xi,x)-b（3646）


这样，就通过核函数将输入空间转化到特征空间中，然后在特征空间中构造超平面，根据数据到原点的距离来实现分类，发现孤立点。
采用不同的核函数K(x,y)，可以实现不同类型非线性决策面的学习机。核函数的形式主要有多项式核函数如式（3640）、Gauss核函数如式（3641）等。
3.6.6最小二乘支持向量机
J.A.K.Suykens在2001年提出最小二乘支持向量机［84］，采用最小二乘线性系统作为损失函数，代替传统所采用的二次规划方法，取得了较好的效果。该方法运算简单，收敛速度快，精度高。算法描述如下。
定义3.6.10设训练样本集D={(xi,yi): i=1,2,…，l}，xi∈Rn是输入数据，yi∈R是输出数据，最小二乘支持向量机（least squares support vector machines，LS SVM）描述为


minw,b,eJ（w,e）=12‖w‖2+12γ∑li=1e2i

s.t.yi=wTΦ（xi）+b+ei,i=1,2,…,l（3647）


其中，Φ: L=Rn→H是非线性映射； 权值向量w∈H，b是偏差量，ei∈R是误差，而e=［e1,…,el］T∈Rl是误差向量,J是损失函数，γ是可调常数。
核空间映射函数的目的是从原始空间中抽取特征，将原始空间中的样本映射为高维特征空间中的一个向量，以解决原始空间中线性不可分的问题。
根据优化函数式（3647），定义Lagrange函数为


L(w,b,e,α)=J(w,e)-∑li=1αi［wTΦ(xi)+b+ei-yi］（3648）


式中，αi∈R是Lagrange乘子，α=［α1,…,αl］T∈Rl； e=［e1,…,el］T∈Rl。对上式进行优化，得


Lw=0w=∑li=1αiΦ(xi)

Lb=0∑li=1αi=0

Lei=0αi=γei,i=1,2,…,l

Lαi=0wTΦ(xi)+b+ei-yi=0,i=1,2,…,l（3649）


消除变量w,e，可得矩阵方程


01T

1Ω+1γIb
α=0
y（3650）


式中，y=［y1,…,yl］T，1=［1,…,1］T∈Rl,而且


Ω={Ωij}l×l，Ωij=ΦT(xj)Φ(xi)=K(xj,xi)（3651）


于是利用最小二乘法可以得到参数［b,αT］T的估计，其中核函数可以有不同的形式，如多项式核、多层感知（MLP）核、样条生成核和RBF核等。LSSVM的预测函数为


y(x)=∑li=1αiK(x,xi)+b（3652）


文献［83］中采用最小二乘支持向量机对时间序列预测进行了研究，取得了良好的效果。
3.6.7模糊支持向量机
在分类问题中我们往往关心的是对重要点的正确分类，并不关心一些像噪声之类的点是否被误分。这样，我们不再要求每个训练点精确属于两个类别中的某一个，而是以某种可能性属于某一类，这就引入模糊支持向量机的概念［75］。
定义3.6.11设给定一组数据集D={(xi,yi,si): i=1,2,…，l}，其中xi∈Rn是训练样本数据，yi∈{-1,1}是标识数据，si∈［σ，1］是xi的隶属度，其中σ>0是无穷小量。定义Φ： Rn→Z是非线性映射，其中Z是特征空间； 模糊支持向量机（fuzzy support vector machine，FSVM）定义为如下优化问题


min12‖w‖2+C∑li=1siξi

s.t.yi(wTzi+b)≥1-ξi,ξi≥0,i=1,2,…,l（3653）


其中zi=Φ(xi)，C是一个常量，ξi是SVM中的误差度量，siξi是不同权值的误差度量。
注意，一个很小的si减少了ξi的作用，因此，相应的xi被认为是不重要的。为了求解这个最优问题，我们构造Lagrange函数


L(w,b,ξ,α,β)=12‖w‖2+C∑li=1siξi-∑li=1αi(yi(wTzi+b)-1+ξi)-∑li=1βiξi
（3654）


这些参数必须满足下面的条件


L(w,b,ξ,α,β)w=w-∑li=1αiyizi=0

L(w,b,ξ,α,β)b=-∑li=1αiyi=0

L(w,b,ξ,α,β)ξi=siC-αi-βi=0，i=1,2,…,l（3655）


将这些条件应用于Lagrange函数式（3654），则问题式（3653）等价地变为


maxJ(α)=∑li=1αi-12∑li=1∑lj=1αiαjyiyjK(xi,xj)

s.t.∑li=1yiαi=0,0≤αi≤siC,i=1,…,l（3656）


类似地也可以得到KuhnTucker条件。
3.6.8小波支持向量机
定义3.6.12设支持向量机的核函数是由能够逼近任意非线性函数的多维小波函数构成，则称其为小波核（wavelet kernal）函数，而相应的支持向量机称为小波支持向量机（wavelet support vector machine，WSVM）［76］。设有小波母函数


ha,c(x)=|a|-1/2hx-ca（3657）


此处x,a,c∈R,a是伸缩因子，c是转移因子。函数f∈L2(R)的小波变换可以写为


Wa,c(f)=〈f(x),ha,c(x)〉（3658）


其中〈·,·〉表示L2(R)中的内积。式（3658）表示函数f(x)在小波基ha,c(x)上的分解。
对于任意小波母函数h(x)，它必须满足下面的条件


Wh=∫∞0|H(ω)|2|ω|dω<∞（3659）


其中H(ω)是h(x)的Fourier变换。我们可以重构f(x)如下


 f(x)=1Wh∫∞-∞∫∞0Wa,c(f)ha,c(x)da/a2dc（3660）


如果对上式取有限项近似，则有


f^(x)=∑li=1Wihai,ci(x)（3661）


对于一个普通的多维小波函数，我们可以把它写成一维小波函数的乘积


h(x)=∏Ni=1h(xi)（3662）


式中x=(x1,…,xn)T∈Rn。这里每个一维小波母函数必须满足式（3659）。
定理3.6.3令h(x)是一个小波母函数，a和c分别表示伸缩和转移因子，x,a,c∈R； 如果x,x′∈Rn，则内积小波核函数为


K(x,x′)=∏ni=1hxi-ciahx′i-c′ia（3663）


转移不变小波核函数（满足转移不变核法则）为


K(x,x′)=∏ni=1hxi-x′ia（3664）


证明见文献［76］中附录A。▉
定理3.6.4考虑具有一般性的小波函数


h(x)=cos(1.75x)(-x2/2)（3665）


并给定伸缩因子a，且a,x∈R； 如果x,x′∈Rn，则小波核函数为


K(x,x′)=∏ni=1hxi-x′ia=∏ni=1{cos［1.75(xi-x′i)/a］exp［-‖xi-x′i‖/(2a2)］}（3666）


证明见文献［76］中附录B。▉
现在，我们给出WSVM作为分类器的决策函数


f(x)=sgn∑li=1αiyi∏nj=1h［(xj-x(i)j)/ai］+b（3667）


式中，x=(x1,…,xn)T∈Rn，x(i)j表示第i个训练样本的第j个分量。
3.6.9核主成分分析
定义3.6.13核主成分分析（kernel principal component analysis，KPCA）就是线性主成分分析的非线性泛化，它把原始数据空间非线性地映射到一个高维特征空间，并在这个特征空间中进行主成分分析。
图369给出了线性PCA与KPCA的比较图。


图369线性PCA与KPCA 


设变换Φ: Rn→F实现了输入空间到特征空间的映射，即把输入空间的样本点x1,x2,…,xl变换为特征空间的样本点Φ(x1),Φ(x2),…,Φ(xl)。假设［80］


∑li=1Φ(xi)=0（3668）


则F空间上的协方差阵为


C=1l∑lj=1Φ(xj)ΦT(xj)（3669）


现在求C的特征值λ≥0和特征向量v∈F＼{0}，


λv=Cv（3670）


因为Cv=1l∑lj=1Φ(xj)<Φ(xj),v>=λv，则所有非零特征值λ≠0对应的特征向量v都在Φ(x1),Φ(x2),…,Φ(xl)张成的平面内，从而存在不完全为零的系数α1,α2,…,αl，使得


v=∑li=1αiΦ(xi)（3671）


这样，对于j=1,2,…,l有


λ〈Φ(xj),v〉=〈Φ(xj),Cv〉=λ∑li=1αi〈Φ(xj),Φ(xi)〉

=1l∑li=1αi〈Φ(xj),∑ls=1Φ(xs)〉〈Φ(xs),Φ(xi)〉（3672）


其中〈·,·〉表示F中的内积。
定义


αΔ［α1,α2,…，αl］T

KΔ{Kij}l×l,Kij=〈Φ(xi),Φ(xj)〉,i,j=1,2,…,l（3673）


则式（3672）可以表示为

lλKα=KKα（3674）

显然，方程

lλα=Kα（3675）

的解则必满足式（3674）。通过对式（3675）的求解，即可获得要求的特征值和特征向量。
图3610给出了线性KPCA的一般原理。


图3610KPCA的一般原理图


3.7Bayes网络基础
过去30多年间，Bayes网络（BN）已经成为人工智能领域内不确定环境中进行知识表示和推理的一种有效工具［8687］。BN不仅对于大规模变量的联合概率分布提供了一种自然的紧凑的表示方式，而且也对于有效的概率推断提供了一个牢固的基础。虽然对于一类特殊的BN如树状网络或单连接网络存在多项式时间的推断算法，但对一般的网络却是一个NP难题。然而，在把BN应用于实际问题时，人们所面临的主要挑战就是如何设计一个简单而有效的近似推断算法，使得对于大规模的概率模型仍然能够满足实时性约束。目前已经发展了许多严格而又近似的BN推断算法，其中有些也是实时算法。本节将提供有关BN推断算法的基础知识，并不对具体算法进行深入讨论。
Bayes网络也称为Bayes置信网络（Bayesian belief network），或因果网络（causal network），或概率网络（probabilistic network），是当前人工智能领域内进行不确定性知识表示和推理的主要工具之一。
3.7.1Bayes网络的一般概念
定理3.7.1（Bayes定理，Thomas Bayes，1763） Bayes更新公式如下


p(H|E,c)=p(H|c)p(E|H,c)p(E|c)（371）


其中,H是假设变量，E是证据变量，c是背景变量（可以不存在）； 左边一项p(H|E,c)称为后验概率，即考虑了E和c的影响之后H的概率； p(H|c)项称为只给定c时H的先验概率； p(E|H,c)是假定假设H和背景信息c为真的条件下证据E发生的概率，称为似然； 而p(E|c)是与假设H无关的证据E的概率。
证明（略）。▉
利用Bayes公式，我们可以把对假设的先验知识通过联合证据而更新成后验知识，从而达到更接近“真实”的目的，这就是Bayes推理的基础。
首先我们给出如下定义。
定义3.7.1一个Bayes网络（Bayesian network，BN）就是一个图，满足如下条件：
（1） 一组随机变量{x1,x2,…,xn}构成了网络的结点，V={1，2，…,n}表示有限结点集合，而与之相应的随机变量构成随机向量x={x1,x2,…,xn}； 
（2） 一组有向边（带箭头的连线）用于连接V中两两结点，由结点k指向结点s的箭头表示随机变量xk直接影响随机变量xs； 而W则表示各结点间有限个有向边的集合； 
（3） 每个结点都有一个局部条件概率表（local conditional probability table，LCPT），用于定量描述其父结点（指向它的结点）对该结点的作用，所有变量的LCPT构成条件概率表（CPT）； 
（4） 该图不存在有向环，因而称为有向无环图（directed acyclic graph，DAG）。
DAG则定义了一个Bayes网络的结构。
为了理解Bayes网络的本质，我们先考虑对一个因果性问题进行建模。
例题3.7.1考虑下面一个所谓“判断妻子是否在家”问题，这是一个不确定判断问题。假定当某甲一个人晚上回家时，在进门以前希望知道妻子是否在家。根据经验，当他的妻子离开家时经常把前门的灯打开，但有时候她希望客人来时也打开这个灯。他们还养着一只狗，当无人在家时，这只狗被关在后院，而狗生病时也关在后院。如果狗在后院，就可以听见狗叫声，但有时听见的是邻居的狗叫。图371给出了这种逻辑关系的描述。


图371“判断妻子是否在家”问题的Bayes网络图□


某甲可能利用这个图来预测他的妻子是否在家。如果妻子外出，狗也外出； 如果灯是亮的，狗也不叫，妻子很可能外出。注意，这个例子的因果链并不是绝对的。也许，他的妻子外出时并没有带狗，也许没有开灯。有时我们能够利用这个图来推断，有时若证据不全时就很难推断。例如，如果灯是亮的但没有听到狗叫，是否能判定妻子在家呢？同样地，听到狗叫，但灯不亮又如何呢？一般情况下我们根据经验规定了相关事件发生的概率（见图371中的概率表，其中根结点规定的是先验概率，而非根结点规定的是条件概率； 其中每个变量均取二值，如a表示该事件发生，a-表示该事件不发生）。利用这个网络，我们只能判断其妻子在家的可能性大小。
3.7.2独立性假设
使用概率论的缺点之一就是荒谬地对大量的事件规定其完全概率分布，如果有n个随机变量，完全分布就要求有2n-1个联合概率分布函数。这对规模较大的系统处理起来是不现实的。Bayes网络必须建立独立性假设。



图372三种连接方式


对于一个Bayes网络，随机变量b与其连接路径上最邻近的两个变量a和c之间存在三种连接方式，如图372所示。其中
① 直线连接（linear connection）： 一个结点在其上，另一个结点在其下； 
② 会聚连接（converging connection）： 两个结点在其上； 
③ 分叉连接（diverging connection）： 两个结点在其下。
以上相应于由b到a和c的箭头三种可能的组合。
下面给出所谓d连接路径的定义。
定义3.7.2在一个Bayes网络中，证据E={e1,e2,…,em}定义为一组观测值。q和r是网络中的两个结点，称由q到r的路径关于证据E是d连接路径（dconnecting path），如果在该路径中的每个结点s具有如下特性之一： 
（1） 是直线连接或分叉连接，而且sE； 
（2） 是会聚连接，且s∈E，或其后代结点属于E。
定义3.7.3称变量a在给定证据E（E可以是空集，也可以非空但不包含a和b）的条件下依赖于变量b，如果给定E时，存在由a到b的一条d连接路径。若给定证据E，变量a不依赖于（dependent on）变量b，则称变量a在给定证据E时独立于（independent on）变量b。
设f是任意随机变量，对于两个随机变量a和b，给定E时彼此独立，但在给定E∪{f}有可能相互依赖。反之，在给定E时彼此依赖，但在给定E∪{f}有可能相互独立。如果两个随机变量a和b相互独立，简单地写成p(a|b)=p(a)，而给定e时有可能使得p(a|b,e)≠p(a|e)。下面我们用例子来说明。
例题3.7.2考虑“判断妻子是否在家”的问题，给定“狗在后院”这一证据，由“妻子外出”到“听见狗叫”之间不存在d连接路径，实际上证据阻断了二者之间的连接。□
在相关文献中，名词“d分离”的应用更加普遍。
定义3.7.4两个结点称为是d分离（dseparation），如果它们之间不存在d连接路径。
粗略地说，两个结点之间是d连接的，要么它们之间就是因果路径（对应于条件1），要么存在证据结点使得这两个结点之间相关（对应于条件2）。
例题3.7.3为了理解这个定义，试想定义中的条件1不成立，那么我们就可以说，一个d连接路径可以不被证据所阻断。但这是不对的，因为已经看到，一旦知道了中间结点的状态，就不需要进一步知道任何事情。
参考图371，我们说“狗生病”和“妻子外出”都能引起“狗在后院”这一状态的发生。但是，“狗生病”的概率依赖于“妻子外出”吗？根本不依赖。（我们可以想象存在某种依赖关系，但这可能要用其他Bayes网络来描述，不属于我们讨论的范围）。注意，它们二者只有一个路径，就是会聚到“狗在后院”。如果两个变量都能引起某个变量状态相同的变化，而它们二者之间又不存在任何联系，就说它们是相互独立的。于是，任何时候都有两种可能的原因引起同一状态变化的情形发生，这样我们就有了会聚结点。Bayes网络常被用来决定是哪个因素引起状态的改变，会聚结点是常用的方法。
现在让我们来考虑定义中的条件2。假定我们已经知道了“狗在后院”这一证据，此时“妻子外出”和“狗生病”是相互独立的吗?非也！虽然在没有证据时它们二者是相互独立的，但知道了“妻子在家”就增大了“狗生病”的概率，因为我们已经在很大程度上排除了“狗外出”的可能性，从而把“不太可能”变成“很大可能”。此时“妻子外出”和“狗生病”之间存在着d连接路径。这个路径通过“狗在后院”这个结点，而这个结点本身是一个条件结点。如果我们并没有“狗在后院”这一证据，而是仅仅“听见狗叫”。在此情况下，我们并不能肯定“狗在后院”，但是我们有了相关的证据“听见狗叫”，使得“狗在后院”的概率提高了。事实上，“听见狗叫”这个证据把它与会聚结点之上的两个结点联系起来了。条件2还说明，如果我们只有影响会聚结点的间接证据，也只能通过会聚结点形成路径。□
如果一个结点随机变量取值的个数增多，CPT的规模也将会随之增大，复杂的网络将会产生NP难题。然而在大多数情况下，实际的网络都由成百上千个结点组成，所以问题的简化将非常重要。
3.7.3一致性概率
在建立Bayes网络时，一个常犯的错误就是规定的概率是非一致性的。
例题3.7.4考虑一个网络，其中有p(a|b)=0.7，p(b|a)=0.3，且p(b)=0.5，仔细看这些数据，好像没有出现什么差错。但是应用Bayes公式会有


p(a)p(b|a)/p(b)=p(a|b)p(a)=p(b)p(a|b)/p(b|a)

p(a)=0.5×0.7/0.3>1


这显然是错误的。□
毋庸置疑，当网络的结点对应的概率取数很多时，问题就变得非常复杂，需要专门的技术来处理概率一致性问题。因此，对于Bayes网络的每个结点，给定与其父结点所有可能的组合数，必须要求: 
（1） 这些数字符合一致性要求； 
（2） 由LCPT规定的概率分布是唯一的。
下面会看到这个要求是正确的。首先要引入联合分布的概念。
定义3.7.5一组随机变量{x1,x2,…,xn}的联合分布（joint distribution）定义为


p(x1,x2,…,xn)（372）


其所有可能的取值之和必须等于1。
例题3.7.5考虑某一Bayes网络的两个随机变量{x1,x2}，而且它们都是二值变量； 所有可能的联合分布是


p(a,b),p(a-,b),p(a,b-),p(a-,b-)


其中p(a,b)=p(x1=a,x2=b)，而且a-表示“非a”； 同时要求它们之和必须等于1，即p(a,b)+p(a-,b)+p(a,b-)+p(a-,b-)=1。从而有


p(a|b)=p(a,b)/p(b)=p(a,b)/［p(a,b)+p(a-,b)］□


一般而言，对于n个随机变量{x1,x2,…,xn}，假定它们都是二值变量，所有可能的联合分布有2n个，而且要求


∑2n可能值p(x1,x2,…,xn)=1（373）


对于一个Bayes网络而言，其联合概率分布由每个随机变量的分布的乘积唯一地进行定义。
设SV是Bayes网络部分结点构成的集合，xs表示与之相应的随机向量； Bayes网络的结构图（graph of structure）就规定了这些变量之间的条件独立关系。设图形结构表示为G=(G1,G2,…,Gn)，其中GiV表示结点i的父结点集合，在给定图形结构的前提下，变量x={x1,x2,…,xn}的概率构成如下


p(x|G,θ)=∏ni=1p(xi|xGi,θ)（374）


其中xGi是xi所有父结点随机变量构成的随机向量，θ是相关的参数，而p(xi|xGi,θ)是局部条件概率分布。
例题3.7.6考虑图371的Bayes网络，来检查其概率一致性
（1） 结点“a”： p（a）=0.15,p（a-）=0.85p（a）+p（a-）=1
（2） 结点“b”： p（b）=0.01,p（b-）=0.09p（b）+p（b-）=1
（3） 结点“c”： 


p(c|a)=0.60,p(c|a-)=0.05p(c-|a)=0.40,p(c-|a-)=0.95

p(a,c)=p(c|a)p(a)=0.60×0.15=0.09,

p(a-,c)=p(c|a-)p(a-)=0.05×0.85=0.0425,

p(a,c-)=p(c-|a)p(a)=0.40×0.15=0.06,

p(a-,c-)=p(c-|a-)p(a-)=0.95×0.85=0.8075,

p(a,c)+p(a-,c)+p(a,c-)+p(a-,c-)

=0.09+0.0425+0.06+0.8075=1


（4） 结点“d”： 


p(d|a,b)=0.99,p(d|a,b-)=0.90,p(d|a-,b)=0.97,p(d|a-,b-)=0.03,

p(d-|a,b)=0.01,p(d-|a,b-)=0.10,p(d-|a-,b)=0.03,p(d-|a-,b-)=0.97

p(a,b,d)=p(d|a,b)p(a)p(b)=0.99×0.15×0.01=0.001485,

p(a,b-,d)=p(d|a,b-)p(a)p(b-)=0.90×0.15×0.99=0.13365,

p(a-,b,d)=p(d|a-,b)p(a-)p(b)=0.97×0.85×0.01=0.008245,

p(a-,b-,d)=p(d|a-,b-)p(a-)p(b-)=0.03×0.85×0.99=0.025245,

p(a,b,d-)=p(d-|a,b)p(a)p(b)=0.01×0.15×0.01=0.000015,

p(a,b-,d-)=p(d-|a,b-)p(a)p(b-)=0.10×0.15×0.99=0.01485,

p(a-,b,d-)=p(d-|a-,b)p(a-)p(b)=0.03×0.85×0.01=0.000255,

p(a-,b-,d-)=p(d-|a-,b-)p(a-)p(b-)=0.97×0.85×0.99=0.816255

p(a,b,d)+p(a,b-,d)+p(a-,b,d)+p(a-,b-,d)+

p(a,b,d-)+p(a,b-,d-)+p(a-,b,d-)+p(a-,b-,d-)

=0.001485+0.13365+0.008245+0.025245+

0.000015+0.01485+0.000255+0.816255=1


（5） 结点“e”： 


p(e|d)=0.70,p(e|d-)=0.01,p(d)=0.168625,p(d-)=0.831375

p(e-|d)=0.30,p(e-|d-)=0.99

p(d,e)=p(e|d)p(d)=0.70×0.168625=0.1180375

p(d-,e)=p(e|d-)p(d-)=0.01×0.831375=0.00831375

p(d,e-)=p(e-|d)p(d)=0.30×0.168625=0.0505875

p(d-,e-)=p(e-|d-)p(d-)=0.99×0.831375=0.82306125

p(d,e)+p(d-,e)+p(d,e-)+p(d-,e-)

=0.1180375+0.00831375+0.0505875+0.82306125=1


所以满足概率一致性要求。同时得到给定网络结构和条件概率表时变量的联合分布。□
3.7.4Bayes网络推断
一个Bayes网络可以看作一个概率专家系统，其中概率知识基础由网络拓扑以及每个结点的LCPT表示。建立这个知识基础的主要目的是用于推断，即计算产生对该领域问题的解答。Bayes网络主要有两种推断方式，即置信更新和置信修正。
定义3.7.6设E表示所有证据结点（evidence node），λ表示证据结点上的观测值，y表示所有询问结点（query node），所谓置信更新（belief update），或称为概率推断（probability inference），就是在给定λ的条件下，求y的后验概率分布


p(y|λ)（375）


可以由CTP得到y的先验分布p(y)，以及似然p(λ|y)，从而可以由Bayes公式得


p(y|λ)=p(λ|y)p(y)∑yp(λ|y)p(y)（376）


而对于y的任意函数f(y)，也可以推断其后验期望，即


E［f(y)|λ］=∑yf(y)p(λ|y)p(y)∑yp(λ|y)p(y)（377）


定义3.7.7所谓置信修正（belief revision）就是在给定观测证据的前提下，对某些假设变量求取最有可能的例证； 产生的结果就是假设变量的一个最优例证表。
很多置信更新算法经过很小的修改就能用于置信修正，反之亦然。本节只讨论置信更新算法。置信更新的计算，在使用Bayes网络时最大的困难就是在一般情况下这是一个NP难题。其次，随着网络规模的增大，计算量则按指数增长。解决这个问题的思路就是： 要么系统规模很小，一般只有数十个结点； 要么结点成千上万，而计算时间可以任意延长。
首先，我们必须澄清是否需要得到精确解。精确解在一般情况下是NP难题，近似解则要求与精确解非常接近，要以很高的概率在正确解的很小邻域内。
首先我们必须从最简单的问题开始研究精确解问题。
定义3.7.8所谓单连接网络（singly connected network）或称多叉树网络（polytree network），就是在相应的基础无向图上任意两个结点之间至多有一个连接路径。
所谓基础无向图（underlying undirected graph）就是忽略箭头后的网络图。
例题3.7.7考虑图373和图374的网络，其相应的基础无向图（不管其方向）任意两点间至多存在一条路径，所以是单连接网络。



图373非单连接网络





图374单连接网络的关系



而图373中，在结点vc和vm之间，除了路径vc-vm之外，还有路径vc-vi-2-vi-vm，所以是非单连接网络。□
对于单连接网络，假定我们只考虑单个询问结点y，我们针对图375的情况分别加以讨论。


图375单连接网络进行推断的几种连接方式



图中，①、②、③均为d分离的，所以比较简单，即
① 分叉连接，但e2∈E。此时如果有证据e1=λ1，e2=λ2，则

p(y|λ)=p(y|λ1,λ2)=p(y|λ2) （378）

② 直线连接，但e2∈E。此时如果有证据e1=λ1，e2=λ2，则

p(y|λ)=p(y|λ1,λ2)=p(y|λ2)（379）

③ 会聚连接，但yE。此时如果有证据e=λ，则


p(y|λ)=∑zp(y|λ,z)（3710）


而其中④、⑤、⑥  均为d连接的，所以相对比较复杂，即
④ 直线连接，且zE。此时如果有证据e=λ，则


p(y|λ)=p(y,λ)p(λ)=∑zp(y,z,λ)p(λ)=∑zp(y|z)p(z|λ)p(λ)p(λ)

=∑zp(y|z)p(z|λ)（3711）


⑤ 会聚连接，且e2∈E。此时如果有证据e1=λ1，e2=λ2，则


p(y|λ)=p(y|λ1,λ2)=p(y,λ1,λ2)p(λ1,λ2)=p(λ2|λ1,y)p(λ1)p(y)∑yp(λ2|λ1,y)p(λ1)p(y)

=p(λ2|λ1,y)p(y)∑yp(λ2|λ1,y)p(y) （3712）


⑥ 直线连接，且yE。这是比较复杂的一种情况。此时如果有证据e1=λ1，e2=λ2，则有


p(y|λ)=p(y|λ1,λ2)=p(y|λ1)p(λ2|y)∑yp(y|λ1)p(λ2|y)（3713）


其中右边分子上第一项为向上连接的后验概率，第二项为向下连接的后验概率,而分母则是分子对所有可能的y值求和。这将使得问题得以大大简化，现在证明如下： 
首先根据Bayes规则，得


p(y|λ1,λ2)=p(y,λ1,λ2)p(λ1,λ2)=p(y)p(λ1|y)p(λ2|λ1,y)p(λ1,λ2)


其次，注意


p(λ2|λ1,y)=p(λ2|y)


这是因为，根据单连接条件，y把λ1和λ2分开来了，从而得到


p(y|λ1,λ2)=p(y)p(λ1|y)p(λ2|y)p(λ1)p(λ2|λ1)


重新调整各项，得到


p(y|λ1,λ2)=p(y)p(λ1|y)p(λ1)·p(λ2|y)p(λ2|λ1)


再对上式右边第一个分式应用Bayes规则，可得


p(y|λ1,λ2)=p(y|λ1)p(λ2|y)p(λ2|λ1)


再利用式（3711），即可得到式（3713）。□
例题3.7.8仍考虑图371的Bayes网络，假定我们已经知道“妻子外出”并“听见狗叫”，问“狗在后院”的后验概率是多少？
此时，λ1=a,λ2=e,y=d，


p(y=d|λ)=p(d|a) =p(d|a,b)p(b)+p(d|a,b-)p(b-)

=0.99×0.01+0.9×0.99=0.900801

p(λ2|y=d)=p(e|d)=0.7


而


p(y=d-|λ1)=p(d-|a) =p(d-|a,b)p(b)+p(d-|a,b-)p(b-)

=0.01×0.01+0.1×0.99=0.0991

p(λ2|y=d-)=p(e|d-)=0.01


所以根据式（3712）有


p(y|λ1,λ2)=p(y|λ1)p(λ2|y)∑yp(y|λ1)p(λ2|y)

=0.900801×0.70.900801×0.7+0.0991×0.01=0.998431


即在知道“妻子外出”并“听见狗叫”的前提下，“狗在后院”的可能性是0.998431。□
例题3.7.9再次考虑图371的Bayes网络，假定我们已经知道“妻子外出”并知道“狗在后院”，问“狗生病”的后验概率是多少？
此时，λ1=a,λ2=d,y=b，


p(λ2|λ1,y=b)=p(d|a,b)=0.99，p(y=b)=0.01


而


p(λ2|λ1,y=b-)=p(d|a,b-)=0.90,p(y=b-)=0.99


根据式（3711）则有


p(y|λ1,λ2)=p(λ2|λ1,y)p(y)∑yp(λ2|λ1,y)p(y)=0.99×0.010.99×0.01+0.90×0.99=0.011


即在知道“妻子外出”并知道“狗在后院”的前提下，“狗生病”的可能性是0.011。
这个后验概率比较接近先验概率。但是，如果改变条件概率


p(λ2|λ1,y=b-)=p(d|a,b-)=0.09


即在“妻子外出”和“狗生病”同时发生时，“狗在后院”的可能性是0.09，则在知道“妻子外出”并知道“狗在后院”的前提下，“狗生病”的可能性变为


p(y|λ1,λ2)=p(λ2|λ1,y)p(y)∑yp(λ2|λ1,y)p(y)=0.99×0.010.99×0.01+0.09×0.99=0.10


使得可能性提高了一个数量级。□
关于Bayes网络推断有许多精确方法和近似方法，而且有所谓参数自适应和结构自适应的方法，此处不再详细讨论。

3.8大数据时代的云计算
正如第1章末所述，随着互联网技术和云计算技术等的飞速发展，信息领域的大数据时代已经来临。我们处理的多源信息融合技术也随着大数据时代的到来发生了重大变化。现代化的军事应用或工业应用系统，大都利用互联网和云计算技术来处理日益复杂的信息融合问题。本节讨论大数据时代的云计算及其对信息融合技术实现的影响。 
3.8.1云计算的概念
近年来，云计算（cloud computing）研究成为各大领域的关注热点。很多学者和专业人士逐步将云计算作为计算机网络技术应用架构的一个核心。云计算服务所提供的庞大网络数据中心不仅存储着大部分的应用软件和数据信息，还掌握着应用程序的管理及信息数据的安全维护工作。在为用户提供查询便利的同时，也可消除诸多安全隐患。
对云计算的定义有多种说法。现阶段广为接受的是美国国家标准与技术研究院（NIST）的定义： 云计算是一种按使用量付费的模式，这种模式提供可用的、便捷的、按需的网络访问，进入可配置的计算资源共享池（资源包括网络、服务器、存储、应用软件和服务等），这些资源能够被快速提供，只需投入很少的管理工作或与服务供应商进行很少的交互。
云计算通常通过互联网来提供动态易扩展且经常是虚拟化的资源。云是网络、互联网的一种比喻说法，云计算甚至可以实现每秒10万亿次的运算能力，拥有这么强大的计算能力可以模拟核爆炸、预测气候变化和市场发展趋势，当然可以用来快速实现网络化的多源信息融合。在许多情况下，用户可以通过计算机、手机等方式接入数据融合中心，按自己的需求进行运算处理。
云计算常与网格计算、效用计算、自主计算相混淆。网格计算是分布式计算的一种，是由一群松散耦合的计算机组成的一个超级虚拟计算机，常用来执行一些大型任务； 效用计算是IT资源的一种打包和计费方式，比如按照计算、存储分别计量费用，像传统的电力等公共设施一样； 自主计算是具有自我管理功能的计算机系统。事实上，云计算部署依赖于计算机集群（但与网格的组成、体系结构、目的、工作方式大相径庭），也吸收了自主计算和效用计算的特点。
换句话说，云计算是分布式计算（distributed computing）、并行计算（parallel computing）、效用计算（utility computing）、网络存储（network storage technologies）、虚拟化（virtualization）、负载均衡（load balance）、热备份冗余（high available）等传统计算机和网络技术发展融合的产物。云计算是继20世纪80年代大型计算机到客户端服务器的大转变之后的又一种巨变。
被普遍接受的云计算特点如下： 
（1） 超大规模。“云”具有相当的规模，Google云计算已经拥有100多万台服务器， Amazon、IBM、微软、雅虎等的“云”均拥有几十万台服务器。企业私有云一般拥有数百上千台服务器。“云”能赋予用户前所未有的计算能力。
（2） 虚拟化。云计算支持用户在任意位置使用各种终端获取应用服务。所请求的资源来自“云”，而不是固定的有形的实体。应用在“云”中某处运行，但实际上用户无须了解，也不用担心应用运行的具体位置。只需要一台笔记本或者一个手机，就可以通过网络服务来实现需要的一切，甚至包括超级计算这样的任务。
（3） 高可靠性。“云”使用了数据多副本容错、计算结点同构可互换等措施来保障服务的高可靠性，使用云计算比使用本地计算机可靠。
（4） 通用性。云计算不针对特定的应用，在“云”的支撑下可以构造出千变万化的应用，同一个“云”可以同时支撑不同的应用运行。
（5） 高可扩展性。“云”的规模可以动态伸缩，满足应用和用户规模增长的需要。
（6） 按需服务。“云”是一个庞大的资源池，用户按需购买； 云可以像自来水、电、煤气那样计费。
（7） 极其廉价。由于“云”的特殊容错措施可以采用极其廉价的结点来构成云，“云”的自动化集中式管理使大量企业无须负担日益高昂的数据中心管理成本，“云”的通用性使资源的利用率较之传统系统大幅提升，因此用户可以充分享受“云”的低成本优势，经常只要花费很少的资金、几天时间就能完成以前需要大量资金、数月才能完成的任务。
（8） 潜在的危险性。云计算服务除了提供计算服务外，还必然提供了存储服务。但是云计算服务当前垄断在私人机构（企业）手中，仅仅能够提供商业信用。对于政府机构、商业用户、军事机构选择云计算服务应保持足够的警惕。一旦商业用户大规模使用私人机构提供的云计算服务，无论其技术优势有多强，都不可避免地让这些私人机构以“数据（信息）”的重要性挟制整个社会。对于信息社会而言，“信息”是至关重要的。另一方面，云计算中的数据对于数据所有者以外的其他云计算用户是保密的，但是对于提供云计算的商业机构而言确实毫无秘密可言。所有这些潜在的危险，是政府机构、商业机和军事机构选择云计算服务，特别是国外机构提供的云计算服务时，不得不考虑的一个重要的前提。
3.8.2云计算的快速发展
2006年8月9日，Google首席执行官埃里克·施密特（Eric Schmidt）在搜索引擎大会（SES San Jose 2006）上首次提出“云计算”的概念。2007年10月，Google与IBM开始在美国大学校园，包括卡内基梅隆大学、麻省理工学院、斯坦福大学、加州大学伯克利分校及马里兰大学等，推广云计算的计划，这项计划希望能降低分布式计算技术在学术研究方面的成本，并为这些大学提供相关的软硬件设备及技术支持。而学生则可以通过网络开发各项以大规模计算为基础的研究计划。2008年1月30日，Google宣布在台湾地区启动“云计算学术计划”，将与台湾大学、台湾交通大学等学校合作，将这种先进的大规模、快速将云计算技术推广到校园。2008年2月1日，IBM宣布将在中国无锡太湖新城科教产业园为中国的软件公司建立全球第一个云计算中心（Cloud Computing Center）。2008年7月29日，雅虎、惠普和英特尔宣布一项涵盖美国、德国和新加坡的联合研究计划，推出云计算研究测试床，推进云计算。该计划要与合作伙伴创建6个数据中心作为研究试验平台，每个数据中心配置1400~4000个处理器。这些合作伙伴包括新加坡资讯通信发展管理局、德国卡尔斯鲁厄大学Steinbuch计算中心、美国伊利诺伊大学香槟分校、英特尔研究院、惠普实验室和雅虎。2008年8月3日，美国专利商标局网站信息显示，戴尔正在申请“云计算”商标，此举旨在加强对这一未来可能重塑技术架构的术语的控制权。2010年3月5日，Novell与云安全联盟（CSA）共同宣布一项供应商中立计划，名为“可信任云计算计划（Trusted Cloud Initiative）”。2010年7月，美国国家航空航天局和包括Rackspace、AMD、英特尔、戴尔等支持厂商共同宣布“OpenStack”开放源代码计划，微软在2010年10月表示支持OpenStack与Windows Server 2008 R2的集成； 而Ubuntu已把OpenStack加至11.04版本中。2011年2月，思科系统正式加入OpenStack，重点研制OpenStack的网络服务。2014年3月，中国国际云计算技术和应用展览会在北京开幕，云计算综合标准化技术体系已形成草案。工信部要我国从五个方面促进云计算快速发展： 一是要加强规划引导和合理布局，统筹规划全国云计算基础设施建设和云计算服务产业的发展； 二是要加强关键核心技术研发，创新云计算服务模式，支持超大规模云计算操作系统，核心芯片等基础技术的研发推动产业化； 三是要面向具有迫切应用需求的重点领域，以大型云计算平台建设和重要行业试点示范、应用带动产业链上下游的协调发展； 四是要加强网络基础设施建设； 五是要加强标准体系建设，组织开展云计算以及服务的标准制定工作，构建云计算标准体系。
3.8.3云计算对多源信息融合技术实现的影响
云计算环境下，软件开发的环境、工作模式也将发生变化。基于互联网技术应用的多源信息融合系统，在云计算环境中也必然发生很大变化。
（1） 多源信息融合系统所开发的软件，必须与云计算相适应，能够与虚拟化为核心的云平台有机结合，适应运算能力、存储能力的动态变化。虽然，传统的软件工程理论不会发生根本性的变革，但基于云平台的开发工具、开发环境、开发平台将为敏捷开发、项目组内协同、异地开发等带来便利。软件开发项目组内可以利用云平台，实现在线开发，并通过云实现知识积累、软件复用。软件测试的环境也可移植到云平台上，通过云构建测试环境； 软件测试也应该可以通过云实现协同、知识共享和测试复用。
（2） 新的软件要能够满足大量用户的使用，包括数据存储结构、处理能力。在云平台上，软件可以是一种服务，如SaaS，也可以就是一个Web Services，如苹果的在线商店中的应用软件等。
（3） 要互联网化，基于互联网提供软件的应用。
（4） 安全性要求更高，可以抗攻击，并能保护私有信息。
（5） 可工作于移动终端、手机、网络计算机等各种环境。
3.9小结
本章主要给出了与多源信息融合相关的智能计算与识别理论基础，不包含已经熟知的神经元网络，以及模式识别教程中的一般内容。本章讨论的大都是二值问题，且与分类问题密切相关。首先给出了有关模式识别、智能学习与统计模式识别的一般概念，然后讲述了信息系统与粗糙集理论的基础知识。然后重点讲述了在信息融合中有特殊意义的证据理论及DS合成公式，以及证据推理的一般方法。随机集理论是近年来颇受学术界关注的信息融合新工具，但其理论基础和方法还有待进一步研究。支持向量机是当前统计学习研究的热点，其优越的性能使得这一方法得到普遍重视。Bayes网络也是一个非常有希望的工具，但实用方法仍需要进一步开发。本章内容相对分散，一般给出比较完整的表述，但难免有支离破碎的感觉，希望读者在此基础上参阅有关文献。
本章最后讲述了大数据时代的云计算及其对信息融合技术实现的影响，这是当前和未来发展的一个重要技术领域。
参考文献


［1］韩崇昭. 应用泛函分析——自动控制的数学基础［M］. 北京： 清华大学出版社,2008.

［2］Marek W,Pawlak Z. Rough sets and information systems［J］. Fundamenta Informaticae，1984,17:  105115.

［3］Pawlak Z. Rough Sets:  Theoretical Aspects of Reasoning about Data［M］. Dordrecht:  Kluwer Academic Publishers,1991.

［4］Pawlak Z. Rough Sets［J］. International Journal of Computer and Information Sciences. 1982,11:  341356.

［5］张文修,梁怡,吴伟志. 信息系统与知识发现［M］. 北京:  科学出版社,2003.

［6］张文修,米据生,吴伟志. 不协调目标信息系统的知识约简［J］. 计算机学报,2003,26(1): 1218.

［7］Yao Y Y. Generalized Rough Set Models［C］//Polkowski L,Skowron A,eds. Rough sets in Knowledge Discovery. Heidelberg:  PhysicaVerlag,1998. 286318.

［8］韩德强. 基于证据推理的多源分类融合理论与方法研究［D］. 西安:  西安交通大学,2008.

［9］Klir G J,Yuan B. Fuzzy Sets and Fuzzy Logic:  Theory and Applications［M］. Upper Saddle River,NJ:  PrenticeHall,1995.

［10］Hartley R V L. Transmission of information［J］. Bell System Technical Journal,1928,7:  535563.

［11］Shannon C E. A mathematical theory of communication［J］. Bell System Technical Journal,1948,27:  379423,623656.

［12］Dubois D,Prade H. A note on measures of specificity for fuzzy sets［J］. International Journal of General Systems,1985,10 (4):  279283.

［13］Harmanec D,Klir G J. Measuring total uncertainty in DempsterShafer theory［J］. International Journal of General Systems,1994,22 (4):  405419.

［14］Klir G J,Wierman M J. UncertainyBased Information［M］.2nd ed.Heidelberg,Germany:  PhysicaVerlag,1999.

［15］Klir G J,Smith R M. Recent developments in generalized information theory［J］. International Journal of Fuzzy Systems,1999,1 (1):  113.

［16］戴冠中,潘泉,张山鹰，等. 证据推理的进展及存在问题［J］. 控制理论与应用,1999,(04):  465469.

［17］杨阳. 证据推理组合方法的分类、评价准则及应用研究［D］. 西安:  西北工业大学,2006.

［18］Denoeux T. An evidencetheoretic neural network classifier［C］//Proceedings of IEEE International Conference on Systems,Man and Cybernetics,Vancouver,1995:  712714.

［19］Barnett J A. Computational methods for a mathematical theory of evidence［C］//Proceedings of the 7th International Joint Conference on Artificial Intelligence,Vancouver,Canada,1981:  868875.

［20］Schubert J. On nonspecific evidence［J］. International Journal of Intelligent Systems,1993,8:  711725.

［21］孙怀江,胡钟山,杨静宇. 学习相关源证据［J］. 南京大学学报(自然科学版),2001,(02):  154158.

［22］孙怀江,杨静宇. 一种相关证据合成方法［J］. 计算机学报,1999,(09):  10041007.

［23］孙怀江,胡钟山,杨静宇. 基于证据理论的多分类器融合方法研究［J］. 计算机学报,2001,(03):  231235.

［24］Wu Y G,Yang J Y,Ke L,et al. On the evidence inference theory［J］. Information Sciences,1996,89 (34):  245260.

［25］Smets P. The transferable belief model ［J］. Artificial Intelligence,1994,66 (2):  191234.

［26］Smarandache F,Dezert J. Advances and Applications of DSmT for Information Fusion Vol II［M］. Rehoboth:  American Research Press,2006.

［27］Dezert J,Smarandache F. On the generation of hyperpowersets for the DSmT［C］//Proceedings of the 6th International Conference on Information Fusion,2003:  11181125.

［28］Dezert J. Foundations for a new theory of plausible and paradoxical reasoning［J］. Information and Security Journal,2002,9:  1357.

［29］Matheron G. Random Sets and Integral Geometry［M］. New York:  John Wiley,1975.

［30］Molchanov I S. Limit Theorems for Union of Random Closed Sets. Lecture Notes in Mathematics［M］. SpringerVerlag,1993.

［31］Peng T,Wang P,Kandel A. Knowledge acquisition by random sets［J］. International Journal of Intelligent Systems,1997,11: 113147.

［32］Sanchez L. A random setsbased method for identifying fuzzy models［J］. Fuzzy Sets and Systems,1998,343454.

［33］NunezGarcia J,Wolkenhauer O. Random Sets and Histograms［EB/OL］.［20100720］. http://www.umist.ac.uk/csc/.

［34］Miranda E,Couso I,Gil P. Extreme points of credal sets generated by 2alternating capacities［J］. International Journal of Approximate Reasoning,2003,33: 95115.

［35］孙怀江，杨静宇.一种相关证据合成方法［J］.计算机学报，1999，22（9）： 272290.

［36］何友,王国宏,路大金，等. 多传感器信息融合及应用［M］. 北京:  电子工业出版社,2000.

［37］Selzer F,Gutfinger D. LADAR and FLIR based sensor fusion for automatic target classification ［C］//Proceedings of SPIE,Montreal,Canada,1988:  236246.

［38］Shafer G. A Mathematical Theory of Evidence［M］. Princeton:  Princeton University Press,1967.

［39］Zadeh L A. Fuzzy sets［J］. Information Control,1965,8:  338353.

［40］谢季坚,刘承平. 模糊数学方法及其应用［M］. 2版.武汉:  华中科技大学出版社,2000.

［41］Bi Y X,Bell D,Wang H,et al. Combining multiple classifiers using Dempsters rule of combination for text categorization［M］//. Lecture Notes in Artificial IntelligenceModeling Decisions for Artificial Intelligence. Berlin： Springer Verlag,2004:  127138.

［42］Valente F,Hermansky H. Combination of acoustic classifiers based on DempsterShafer theory of evidence［C］//Proceedings of IEEE International Conference on Acoustics,Speech and Signal Processing,2007:  IV1129IV1132.

［43］Bi Y X,Bell D,Guan J W. Combining evidence from classifiers in text categorization［C］//Proceedings of the 8th International Conference on KES,Wellington,New Zealand 2004:  521528.

［44］段新生. 证据理论与决策、人工智能［M］. 北京:  中国人民大学出版社,1990.

［45］张文修,梁怡. 不确定性推理原理［M］. 西安:  西安交通大学出版社,1996.

［46］Begler P L. ShaferDempster reasoning with applications to multisensor target identification system［J］. IEEE Transactions on Systems,Man and Cybernetics,1987,17:  968977.

［47］Zhu Y M,Dupuis O,Kaftandjian V,et al. Automatic determination of mass functions in DempsterShafer theory using fuzzy cmeans and spatial neighborhood information for image segmentation［J］. Optical Engineering,2002,41(4):  760770.

［48］Salzenstein F,Boudraa A O. Iterative estimation of DempsterShafers basic probability assignment:  application to multisensor image segmentation［J］. Optical Engineering,2004,43 (6):  12931299.

［49］孙亮. 高维遥感数据融合与分类的知识发现方法研究［D］. 西安:  西安交通大学,2006.

［50］Moyal J E. The general theory of stochastic population processes［J］. Acta Mathematica,1962,108:  131.

［51］Mathéron G. Random Sets and Integral Geometry［M］.  New York: Wiley,1975.

［52］Ripley B. Locally finite random sets:  foundations for point process theory［J］. Annals of Prob,1976,6(4):  983994.

［53］Baudin M. Multidimensional Point Processes and Random Closed Sets［J］. Journal of Applied Prob,1984,21:  173178.

［54］Mahler R. Nonadditive Probability,Finiteset Statistics and,and Information Fusion［C］//New Orleans,LA 1995:  19471952.

［55］ElFallah A,Mahler R,Ravichandrana B,et al. Adaptive Data Fusion Using FiniteSet Statistics［C］//Orlando,Florida 1999:  8091.

［56］Mahler R. Random Sets:  Unification and Computation for Information FusionA Retrospective Assessment［C］//Stockholm,Sweden,2004.

［57］Mahler R P S. “Statistics 101 ” for Multisensor,Multitarget Data Fusion［J］. IEEE A&E SYSTEMS MAGAZINE,2004,19 (1):  5364.

［58］Mahler R P S. The RandomSet Approach to Data Fusion［J］. SPIE,1994,2237:  287295.

［59］Mahler R. Multisensormultitarget statistics. Data Fusion Handbook［M］.Boca Raton： CRC Press,2001.

［60］Mahler R. The search for tractable Bayesian multitarget filters［C］.SPIE，2000:  310320.

［61］Nguyen H T. An Introduction to Random Sets［M］. Taylor & Francis Group,LLC,2006.

［62］Goodman I R,Mahler R P S,Nguyen H T. Mathematics of data fusion［M］. Kluwer academic publishers,1997.

［63］Vo B,Singh S,Doucet A. Sequential Monte Carlo Methods for MultiTarget Filtering with Random Finite Sets［J］. IEEE Transactions on Aerospace and Electronic systems,2005,41(4):  12241245.

［64］Fletcher R. Practical Methods of Optimization［M］. 2nd ed. Hoboken： John Wiley and Sons,Inc.,1987.

［65］Christopher J C Burges. A Tutorial on Support Vector Machines for Pattern Recognition［J］. Data Mining and Knowledge Discovery,1998,2: 121167.

［66］Vapnik V. Estimation of Dependences Based on Empirical Data ［M］. Moscow:  Nauka,1979 (English translation:  New York:  Springer Verlag,1982).

［67］Vapnik V. The Nature of Statistical Learning Theory［M］. New York:  Springer Verlag,1995.

［68］Vapnik V,Golowich S,Smola A. Support vector method for function approximation,regression estimation and signal processing［J］. Advances in Neural Information Processing Systems,1996,9: 281287.

［69］Strang G T. Introduction to Applied Mathematics［M］. Wellesley:  WellesleyCambridge Press,1986.

［70］Scholkopf B,Sung K,Burges C,et al. A comparing support vector machines with Gaussian kernels to radial basis function classifiers［J］. IEEE Trans. Sign. Processing,1997,45: 27582765.

［71］Suykens J A K,Vandewalle J,De Moor B. Optimal Control by Least Squares Support Vector Machines［J］. Neural Networks,2001,14(1):  2335.

［72］Zhu J Y,Ren B,Zhang H X,et,al. Time Series Prediction via New Support Vector Machines［J］. IEEE,In Proceeding of 2002 ICMLC,China Beijing,2002.

［73］Lin C F,Wang S D. Fuzzy Support Vector Machine［J］. IEEE Trans. On Neural Networks,2002,13(2)： 2829.

［74］Zhang L,Zhou W D,Jiao L C. wavelet support vector machine［J］. IEEE Trans. On SMCPart B:  CYBERNETICS,2004,34(1)： 120125.

［75］Zhang Q H,Benveniste A. Wavelet networks［J］. IEEE Trans. Neural Networks,1992,3:  889898.

［76］Szu H H,Telfer B,Kadambe S. Neural network adaptive wavelets for signal representational and classification［J］. Opt. Eng.,1992,31:  19071916.

［77］张恒喜，郭基联，朱家元，等. 小样本多元数据分析方法及应用［M］. 西安:  西北工业大学出版社,2002.

［78］肖健华,吴今培. 基于核的特征提取技术及应用研究［J］. 计算机工程,2002，28（10）： 3638.

［79］Lima A,Zen H,Nankaku Y,et al.On the Use of Kernel PCA for Feature Extraction in Speech Recognition［J］.IEICE Transactions on information and systems,2004,E87D(12): 28022811.

［80］Bernhard S,John C P. Estimating the Support of a HighDimensional Distribution［R］. Microsoft Research Technical Report MSRTR9987,1999,128.

［81］Scholkopf B. Statistical Learning and Kernel Methods［R］. Microsoft Research Technical Report MSRTR200023,2000,129.

［82］Suykens J A K,Vandewalle J,De Moor B. Optimal Control by Least Squares Support Vector Machines［J］. Neural Networks,2001,14(1):  2335.

［83］Charniak E. Bayesian Networks without Tears［EB/OL］. ［20100721］.http://www.aaai.org.

［84］Bottcher S G,Dethlefsen C. Learning Bayesian Networks with R［C］//Proceedings of the 3rd International Workshop on Distributed Statistical Computing (DSC) March 2022,Vienna,Austria,2003.

［85］Koivisto M,Sood K. Exact Bayesian Structure Discovery in Bayesian Networks［J］. Journal of Machine Learning Research 5,2004,549573.

［86］Tessem B. Approximations for efficient computation in the theory of evidence［J］. Artificial Intelligence, 1993, 61(2):  315329.

［87］Smets P. Decision making in the TBM:  The necessity of the pignistic transformation［J］. International Journal of Approximate Reasoning, 2005, 38(2):  133147.

［88］Han D Q, Dezert J, Han C Z,et al. New dissimilarity measures in evidence theory［C］//Proceedings of the 14th International Conference on Information Fusion, Chicago, IL, USA, 2011:  17.

［89］Jousselme A L, Grenier D, Bossé . A new distance between two bodies of evidence［J］. Information Fusion, 2001, 2(2):  91101.

［90］Han DQ, Dezert J, Yang Y. Belief IntervalBased Distance Measures in the Theory of Belief Functions［J］. IEEE Transactions on Systems, Man, and Cybernetics:  Systems, 2018, 48(6):  833850.

［91］Irpino A, Verde R. Dynamic clustering of interval data using a Wassersteinbased distance［J］. Pattern Recognition Letters, 2008, 29(11):  16481658.

［92］Vo B T, Vo B N. A random finite set conjugate prior and application to multitarget tracking［C］//2011 Seventh International Conference on Intelligent Sensors, Sensor Networks and Information Processing. IEEE, 2011:  431436.

［93］Vo B T, Vo B N. Labeled random finite sets and multiobject conjugate priors［J］. IEEE Transactions on Signal Processing, 2013, 61(13):  3460347.

［94］Hhle U. Entropy with respect to plausibility measures［C］//Proceedings of the 12th IEEE International Symposium on MultipleValued Logic, 1982:  167169.

［95］Yager RR. Entropy and specificity in a mathematical theory of evidence［J］. International Journal of General Systems, 1983, 9(4):  249260.

［96］Klir  G J, Ramer A. Uncertainty in the DempsterShafer theory:  a critical reexamination［J］. Int. J. Gen. Syst., 1990, 18(2):  155166.

［97］Klir GJ, Parviz B. A note on the measure of discord［C］//Proceedings of the Eighth International Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers Inc., 1992:  138141.

［98］Dubois D, Prade H. A note on measures of specificity for fuzzy sets［J］. International Journal of General Systems, 1985, 10(4):  279283.

［99］Korner R, Nather W. On the specificity of evidences［J］. Fuzzy Sets and Systems, 1995, 71(2):  183196.

［100］Harmanec D, Klir GJ. Measuring total uncertainty in DempsterShafer theory:  a novel approach［J］. International Journal of General Systems, 1994, 22(4):  405419.

［101］Jousselme A L, Liu C S, Grenier D,et al. Measuring ambiguity in the evidence theory［J］. IEEE Transactions on Systems Man and Cybernetics Part A:  Systems and Humans, 2006, 36(5):  890903.

［102］Smets P. Decision making in the TBM:  The necessity of the pignistic transformation［J］. International Journal of Approximate Reasoning, 2005, 38(2):  133147.

［103］Yang Y, Han D Q. A new distancebased total uncertainty measure in the theory of belief functions［J］. KnowledgeBased Systems, 2016, 94: 114123.

［104］Irpino A, Verde R. Dynamic clustering of interval data using a Wassersteinbased distance［J］. Pattern Recognition Letters, 2008, 29(11):  16481658.