（应用数学专业论文）贝叶斯网络诱导的内积空间与核函数.pdf

摘要 摘要 贝叶斯网络是用来表示变量间概率关系的图形模型，它提供了一种自然的表示 因果信息的方法，用来发现数据间的潜在关系以其独特的不确定性知识表达形 式、丰富的概率表达能力、综合先验知识的学习特性已成为机器学习、人工智能、 统计推理等应用学科的研究热点通过核函数将线性不可分的数据映射到线性可 分的高维特征空间是数据分类的重要方法本文试图将二者结合，优势互补，为 基于贝叶斯网络的数据分类、概念学习等做出贡献 本文首先给出了在允许一定误差时，近似保持空间的线性可分性和一定的 m a r g i n 值的条件下，将数据集映射到维数低一些的特征空间的可能性和一些限制 的条件为讨论贝叶斯网络诱导的内积空间维数的上界提供了理论支持 其次，结合贝叶斯网络与核方法的优点，本文针对具有两类分类任务的贝叶斯 网络，讨论了变量在布尔域上取值时，某些无约束贝叶斯网络诱导的内积空间， 给出了该内积空间的维数和v c 维数；通过概率分布的等价性，重点讨论了每个变 量取四个值时，某些无约束贝叶斯网络诱导的内积空间，并给出了该内积空间的 维数 关键词：贝叶斯网络核函数内积空间v c 维 a b s t r a c t a b s t r a c t t h eb a y e s i a nn e t w o r k sa r eg r a p h i c a lr e p r e s e n t a t i o no fm u l t i v a r i a t ej o i n tp r o b a b i l i t y d i s t r i b u t i o n , w h i c he x p l o i tt h ed e p e n d e n c ys t r u c t u r eo fd i s t r i b u t i o n st od e s c r i b et h e mi n ac o m p a c ta n dn a t u r a lm a n n e r t h e ya r ea l w a y su s e dt of i n dt h ep o t e n t i a lr e l a t i o n s h i p o ns o m ed a t as e t s t h e r eh a sb e e nag r e a td e a lo fr e s e a r c hf o c u s e do nt h eb a y e s i a n n e t w o r k si nm a c h i n el e a n i n g , a r t i f i o a li n t e l l i g e n c e , a n dp r o b a b i l i t yi n f e r e n c ed u et o t h e i ru n c e r t a i nk n o w l e d g ee x p r e s s i o n ，t h ea b i l i t yt om a t c ht h ep r o b a b i l i t ya n dp r o p e r t y f o r l e a r n i n gb a s e do np r i o rk n o w l e d g e i ti s a ni m p o r t a n tm e t h o di nt h ed a t a c l a s s i f i c a t i o nt om a pt h ed a t ai nt h en o n l i n e a rs e p a r a t o rs p a c et ot h eh i g h - d i m e n s i o n f e a t u r es p a c et h a ti ss e p a r a b l eb yk e r n e lf u n c t i o n i nt h i sp a p e r , w et r yt oc o m b i n et h e k e ya d v a n t a g eo fp r o b a b i l i s t i cm o d e l sw i t hk e r n e l - b a s e dl e a r n i n gs y s t e m st op r e s e n t s o m er e s u l t sf o rd a t ac l a s s i f i c a t i o na n dc o n c e p tl e a r n i n g f i r s t l y , w ed i s c u s st h ep o s s i b i l i t ya n ds e v e r a lc o n s t r a i n tc o n d i t i o n so nm a p p i n gd a t a t ol o w d i m e n s i o nf e a t u r es p a c ea st h a tp r e s e r v ea p p r o x i m a t el i n e a rs e p a r a b i l i t ya n da c e r t a i nm a r g i nv a l u ew i t ha l l o w i n gac e r t a i na m o u n to fe r r o r t h i sr e s u l tp r o 啊d e sa t h e o r ys u p p o r t e df o rt h eu p p e rd i m e n s i o no fi n n e rp r o d u c ts p a c e si n d u c e db yb a y e s i a n n e t w o r k s s e c o n d l y , w ef o c u so nt w o l a b e l c l a s s i f i c a t i o nt a s k sb yc o m b i n i n gt h ek e y a d v a n t a g eo fb a y e s i a nn e t w o r k sa n dk e r n e lm e t h o d s w ed i s c u s si n n e rp r o d u c ts p a c e s i n d u c e db ys o m es p e c i a lu n c o n s t r a i n tb a y e s i a nn e t w o r k so v e rb o o l e a nd o m m n ，a n d g i v et h ee u c l i d e a nd i m e n s i o na n dv cd i m e n s i o no ft h ei n n e rp r o d u c ts p a c e so ft h e c o n c e p tc l a s s e si n d u c e db yt h e m b a s e do ne q u i v a l e n c ep r o p e r t yo fp r o b a b i l i t y d i s t r i b u t i o n ，w em a i n l ys t u d yi n n e rp r o d u c ts p a c e si n d u c e db ys o m es p e c i a l u n c o n s t r a i n tb a y e s i a nn e t w o r k sw i t hf o u r - v a l u e dv a r i a b l e s f u r t h e rw eo b t a i nt h a tt h e d i m e n s i o no ft h ei n n e rp r o d u c ts p a c e so ft h ec o n c e p tc l a s s e si n d u c e db yt h e m k e y w o r d s ：b a y e s i a nn e t w o r k ( b k e r n e lf u n c t i o ni n n e rp r o d u c ts p a c e v c ( v a p n i k - c h e r v o n e n k i s ) d i m e n s i o n 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所里交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 酏莫 日期三! ：! ：里 1 7 1 , 籀1 磁主：2 第一章绪论 第一章绪论 随着数字网络的普及与计算机的普遍使用，数据收集的速度越来越快，对海 量数据处理已经成为计算机科学家与工程师必须面临的挑战性任务适应这一迫 切的任务需求，数据挖掘作为理论性与应用性结合最为密切的一个研究领域，迅 速地发展起来【1 1 在众多的数据挖掘算法中，贝叶斯网络【2 3 】结合图论和统计学方 面的知识，给出了一种很自然的表示因果信息的方法，用来表达随机变量之间复 杂的概率不确定性，发现数据间的潜在关系 1 1 贝叶斯网络简介 贝叶斯网络又称为信念网络、概率网络或因果网络【5 。7 1 ，它主要由两部分构成 【8 】： 1 有向无环 虱( d i r e c t e da c y c l i cg r a p h ，d a g ) ，即网络结构，包括节点集和节 点之间的有向边，每个节点代表一个变量，有向边代表变量之间的依赖关系，指 向节点z 的所有节点称为彳的父节点尽管从节点x 指向节点y 的有向边频繁地 被用来表示x 引起了y 但在贝叶斯网络里这不是对有向边的唯一解释。例如，】r 可能只与x 有关联，但是它不是由x 引起的因此虽然贝叶斯网络能表示因果关 系，但它们并不局限于表示因果关系 图1 1 描述了一个典型的贝叶斯网络的结构其中x ，石，是x 。的父节点在 贝叶斯网络信息管道模型中，把节点看作阀门，节点之间的边看作信息流动的管 道，碰撞节点( 具有汇聚箭头的节点) 所表示的阀门是关闭状态，信息流不能通过， 实例化后处于打开状态非碰撞节点所表示的阀门处于打开状态，实例化后处于 关闭状态两个节点之间考虑弧方向的通路称为有向路径，简称路径，不考虑方 向的通路称为非有向路径，简称链路在贝叶斯网络中，存在两种路径，一种是 不含碰撞节点的路径，称为开路，信息流能够通过，当有节点被实例化后，信息 流被阻塞；另一种是含有碰撞节点的路径，称为闭路，只有当所有碰撞节点被实 例化，非碰撞节点不实例化时信息流才能通过 2 贝叶斯网络诱导的内积空间与核函数 图1 1 贝叶斯网络图 利用贝叶斯网络信息管道模型可形象地描述变量之间存在的三种基本依赖关 系：绝对依赖变量的节点之间存在直接的信息流动，而且信息流不能被其它 节点所阻塞，节点所表示的变量之间不是条件独立的；条件独立节点之间不 存在直接的信息流动，而是由连接两节点之间的开路产生信息流这种信息流被 切割集中的节点所阻塞，以切割集中的节点所表示的变量为条件时，两个节点所 表示的变量之间条件独立：条件依赖这种依赖是由y 结构所导致节点之间 不存在直接的信息流动，而是由v 结构中的碰撞节点诱发信息流，节点所表示的 变量之间无条件独立，以切割集中的节点表示的变量为条件时，两个节点所表示 的变量之间条件独立 2 反映节点之间关联性的局部概率分布集，即概率参数，通常称为条件概率 表( c o n d i t i o n a lp r o b a b i l i t yt a b l e ，c p t ) ，概率值表示节点之间的关联强度或置信 度该表列出了此节点相对于其父节点所有可能的条件概率贝叶斯网络约定以 节点x ，的父节点为条件，x ；与任意非x ，子节点条件独立 贝叶斯理论给出了信念函数在数学上的计算方法，具有稳固的数学基础，贝 叶斯网络作为一种图形化的建模工具，具有一系列的优点【8 】： ( 1 ) 贝叶斯网络将有向无环图与概率理论有机结合，不但具有了正式的概率理 论基础，同时也具有更加直观的知识表示形式一方面，它可以将人类所拥有的 因果知识直接用有向图自然直观地表示出来另一方面，也可以将统计数据以条 件概率的形式融入模型这样贝叶斯网络就能将人类的先验知识和后验的数据无 缝地结合，克服框架、语义网络等模型仅能表达处理定量信息的弱点和神经网络 等方法不够直观的缺点 ( 2 ) 贝叶斯网络与一般知识表示方法不同的是对于问题域的建模因此当条件 或行为等发生变化时，不用对模型进行修正 ( 3 ) 由于贝叶斯网络满足m a r k o v 条件，随机变量间的联合概率得到了简化， 第一章绪论 3 因此能够处理各种不确定性信息 ( 4 ) 贝叶斯网络中没有确定的输入或输出节点，节点之间是相互影响的，任何 节点观测值的获得或者对于任何节点的干涉，都会对其它节点造成影响，并可以 利用贝叶斯网络推理来进行估计预测 ( 5 ) 贝叶斯网络的推理是以贝叶斯概率理论为基础的，不需要外界的任何推理 机制，不但具有理论依据，而且将知识表示与知识推理结合起来，形成统一的整 体 由于上述优点，贝叶斯网络很快就成为数据挖掘领域进行不确定性推理和建 模的一个有效工具。利用贝叶斯网络可以对于事件或者属性间的带有不确定性的 相互关系进行分析 1 2 核函数简介 在模式识别、神经网络等机器学习中，支持向量机是其核心算法，它是基于 统计学习理论提出的，可以有效地解决有限样本条件下高维模型的构建问题，而 且具有很强的推广能力统计学习理论研究小样本( 或有限样本) 的学习问题，采用 统计学习理论中的结构风险最小化准则，既考虑了减小训练集的误差，同时由于 v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 的应用也兼顾了减小学习机的复杂性，从而 保证学习机具有良好的泛化能力；一般而言，v c 维越大则学习机器越复杂，学习 容量就越大 支持向量机分类算法的基本工作原理是，使用一个非线性变换将一个线性不 可分的空间映射到一个高维的甚至是无限维的线性可分的空间( 一般称其为特征空 间) ，并且建立一个具有极小v c 维数的分类器。由该算法得到的分类器仅由大量 样本中的极少量向量，即支持向量确定，且具有最大的边界宽度( 即分类间隔， m a r g i n ) t 9 1 实际上，到高维空间的映射是通过核函数来实现的，即将高维空间优化中的 内积运算用满足m e r c e r 条件的核函数代替核函数的作用不但可将线性不可分的 输入空间变换为线性可分的( 通常是高维的) 特征空间，而且具有非常优秀的泛化能 力在支持向量机方法中，核函数的选择十分重要，对同一类问题，选择不同的 核函数，分类的性能就会相差很大，主要是因为构成核函数k “j ，) 的非线性映射 ( x ) 是隐函数，且这些隐函数类型是多样可变的，这就直接影响了支持向量机分 类的性能 4 贝叶斯网络诱导的内积空间与核函数 1 3 核学习框架下的贝叶斯网络研究 在数据挖掘中，贝叶斯网络用概率测度的权重描述数据间的相关性，在处理 不确定性的知识表达方面体现了明显的优越性，但它以整个属性空间和样本空间 为基础进行分析，没有考虑到属性空间或样本空间局部区域的特殊性另一方面， 大部分的分类算法是内存驻留算法，通常假定数据量很小，算法的可伸缩性意味 着对于海量数据而言是否具有有效的构造模型的能力【8 】 核方法的理论基础是统计学习理论，与传统统计学相比，统计学习理论是一 种专门研究小样本情况下机器学习规则的理论该理论针对小样本统计问题建立 了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要 求，而且追求在现有有限信息的条件下得到最优结果 概率方法与核方法在对系统建模和分析时具有不同的特点f l o 】： 概率方法能够对随机不确定性进行建模，并且能够进行概率推理；概率方法还 能够融合异源的数据和知识；在应用概率模型进行分类时，并不是绝对的把一个 对象分为一个类别，而是通过计算得出该对象属于某一类的概率，然后将具有最 大概率的类别赋予该对象 核方法是一系列非线性数据处理方法的总称，其共同特征是这些方法都应用了 核函数核方法首先采用非线性映射将原始数据由数据空间映射到特征空间，进 而在特征空间中进行对应的线性操作如果数据的坐标分量间的相互作用仅限于 内积，就可使用满足m e r c e r 条件的核函数来代替内积运算，从而越过本来需要计 算的映射，避免维数灾难 如何结合两种方法的优点来解决问题，引起了研究人员的兴趣【1 1 13 1 核方法 能够处理高维特征空间，且具有很强的泛化性，这与概率方法的特点互补当前 应用核方法对贝叶斯网络的研究限于如何提高贝叶斯网络的数据分析能力利用 核方法的特点，探索高效率的建模方法是值得进一步研究的问题 1 4 本文的主要内容 近年来，许多专家和学者对贝叶斯网络技术的各个方面进行了深入的探讨和 研究，取得了极大的成果和进展，使贝叶斯网络技术能够用于多个领域实际问题 的研究和处理，贝叶斯方法正以其独特的不确定性知识表达方式、丰富的概率表 达能力、综合先验知识的增量学习特性成为当前数据挖掘众多方法中最为引人注 目的焦点之一峭j 在机器学习中，核方法能够处理高维的特征空间，而且具有很强 的泛化性目前结合概率方法与核方法的优点来解决问题，已成为现代研究者关 第一章绪论 5 注的热门问题 本文结合概率方法与核方法，讨论了贝叶斯网络中的内积空间，即如何将一 个贝叶斯网络的决策函数表示为维数尽可能小的内积并给出了某些无约束贝叶 斯网络诱导的内积空间维数 第二章。详细地叙述了贝叶斯网络的相关知识，包括：，贝叶斯网络的发展、 应用、构建、参数学习和结构学习、推理以及贝叶斯网络分类器；接着介绍了核 函数、支持向量机的相关理论 第三章，介绍了根据j o h n s o n - l i n d e n s t r a u s s 引理，允许一定误差时，在近似保 持空间的线性可分性和一定的间隔( m a r g i n ) 值的条件下，将数据集映射到维数低一 些的特征空间的可能性和一些限制的条件，为讨论贝叶斯网络诱导的内积空间维 数的上界提供了理论支持 第四章，结合概率方法与核方法，针对两类分类任务，研究了贝叶斯网络诱 导的内积空间的维数，先给出了变量在布尔域上取值时，某些贝叶斯网络诱导的 内积空间的维数；本文的创新点是通过概率等价性，给出了当每个变量取四个值 时，某些特殊贝叶斯网络诱导的内积空间的维数 第五章，总结了本文的主要研究内容，展望了以后的研究方向和有待进一步 解决的问题 第二章贝叶斯网络与核函数 7 第二章贝叶斯网络与核函数 贝叶斯统计和图论的发展为贝叶斯网络理论的发展提供了坚实的理论基础， 而人工智能、专家系统和机器学习在实践中的广泛应用，成为贝叶斯网络拓展的 催化剂在机器学习、模式识别、数据挖掘和人工神经网络等多个学科中，由于 支持向量机是基于统计学习理论中结构风险最小化原则和v c 维理论，具有良好的 泛化能力；又由于核函数与核技巧的应用，成功的将非线性问题转化为线性问题 求解，从而大大减小了计算代价因此研究贝叶斯网络与核函数具有重要的理论 意义和现实要求本章介绍了贝叶斯网络与核函数的相关理论基础及相关术语 2 1 1 贝叶斯网络的应用 2 1 贝叶斯网络 贝叶斯网络是表示变量问概率依赖关系的有向非循环图，通过先验信息和样 本数据来获得对未知样本的估计先验概率既可以借助人的经验、专家的知识来 指定，也可以通过分析样本数据的特点直接获得后者要求有足够多的数据才能 真正体现数据的真实分布贝叶斯方法的优点是可以利用人的先验知识，而缺点 是当假设模型与样本实际分布情况不相符时，就难以获得较好的效果 贝叶斯网络不同于一般的基于知识的系统，它以强有力的数学工具处理不确 定知识，以简单直观的方式表达和解释它们它也不同于一般的概率分析工具， 它将图形表示和数值表示有机的结合起来 贝叶斯网络广泛地用于数据挖掘，是知识发现领域中的一种重要的学习方 法贝叶斯网络在不确定知识表示及推理方面表现出的卓越性能，为人工智能的 其它研究领城提供了有力的工具一批以贝叶斯网络为基础的专家系统也建立了 起来【8 】1 9 7 4 年，d ed o m d a l 等人研制了一个贝叶斯网络概率推理系统，该系统能 够根据已有证据进行诊断和在证据不充分的情况下能够进一步选择可能存在的问 题进行测试，以获得充分的证据2 0 世纪8 0 年代，随着贝叶斯网络理论研究的深 入，出现了大量的应用贝叶斯网络的实际应用系统，代表性的主要有m u n i n ， h u g i n ，p a t h f i n d e r ，q m r - d t ，c o n v i n c e 等 m u n i n ( m u s c l ea n dn e r v ei n f e r e n c en e t w o r k ) 是第一个使用贝叶斯网络建立的 专家系统该系统完全按着严格的条件概率方法来计算某一特征出现的概率然 贝叶斯网络诱导的内积空间与核函数 而利用大量的经验数值来严格估计后验概率是不实际的针对这样的问题， l a u r i t z e n 等人开发了专家系统工具h u g i n ，其思想是使用马尔可夫树代替贝叶斯 网络1 9 9 0 年，针对一般的贝叶斯网络，c o o p e r 证明了概率值的传播问题是n p 问题p a t h f i n d e r 系统是一个淋巴疾病诊断系统，它涉及1 0 0 多种症状，可诊 断6 0 多种疾病【1 1 概括而言，贝叶斯网络目前的应用及研究主要是以下几个方面【8 】= ( 1 ) 故障诊断根据发生的故障特征，找出发生故障的原因，根据经常发生的 故障或系统现有的状态，进行实时监控和故障预防 ( 2 ) 专家系统提供专家水平的推理，模拟人的智能，解决专业领域内的实际 问题例如，贝叶斯网络在医学方面的应用 ( 3 ) 规划根据因果概率推理预测各类事件发生的可能性，对于给定的目标( 例 如：省钱或省时) ，得到一个项目的规划 ( 4 ) 学习对学习提供帮助，帮助初学者快速掌握事件发生的因果关系和规律 ( 5 ) 分类与聚类使用贝叶斯网络进行分类和聚类分析，在数据挖掘和模式识 别中具有重要应用从国际学术界的研究动态可以看出贝叶斯网络正在成为人工 智能研究的热点 现在贝叶斯方法和技术的应用领域不断地扩展，如基于概率因果关系的数据 挖掘、信息的智能检索、实时决策支持系统、语音识别和手写体的识别以及智能 a g e n t 和m a s 的建模等研究人员通过将先验信息与观测数据相结合，实现了多 种网络结构模型的学习算法，进而提出了在没有任何先验信息情况下的相应算 法最近的研究开始减弱甚至放弃某些假设，从更一般意义下研究网络结构的学 习 2 1 2 贝叶斯网络的构建【l 】 定义2 1 贝叶斯网络是： ( 1 ) 表示变量间概率依赖关系的有向无环图g = ( y ，e ，o ) ，y 表示有限点集， e v v 表示边的集合； ( 2 ) 每个节点i v 表示领域变量，每条边( _ ，i ) e 表示变量间的概率依赖关 系； ( 3 ) 参数( 易口) 触胛1 0 。j ，( o ，1 ) ，其中m i 表示节点i 的父节点的个数，即 m i = l u v l ( j ，f ) e ) j 第二章贝叶斯网络与核函数 9 贝叶斯网络的一个关键特征是它提供了一种把联合概率分布分解为局部分布 的方法它的图形结构编码了变量间概率依赖关系，具有清晰的语义特征，这种 独立性的语义指明如何组合这些局部分布来计算变量间联合分布的方法网络的 定量部分给出变量间不确定性的数值度量为叙述方便，我们用大写字母 x = 五，五，以) 表示领域变量，用小写字母x = “，毛，) 表示变量的取值， 那么贝叶斯网络的联合概率分布可以用下面的式子表示： p ( 而) = ilp ( 五l p a r e n t ( x ，) ) ( 2 - 1 ) 一i 一 这样做的好处有：由于在一个由多变量组成的贝叶斯网络中，变量间交互 作用的关系是稀疏的，这种局部概率分布表能指数级的降低联合分布表的容量； 存在许多适合于局部分布表的贝叶斯推理算法；贝叶斯网络中的定量表示 与定性表示的分离有利于知识工程的建模 贝叶斯网络不同于一般的基于知识的系统，它以强有力的数学工具处理不确 定性知识，以简单直观的方式解释它们它也不同于一般的概率分析工具，它将 图形表示和数值表示有机结合起来 构建一个指定领域的贝叶斯网络包括三个任务：标识影响该领域的变量及 其它们的可能值；标识变量间的依赖关系，并以图形化的方式表示出来；学 习变量间的分布参数，获得局部概率分布表这三个任务之间一般是顺序进行的， 然而在构造过程中一般需要在下面两个方面作折中：一方面为了达到足够的精度， 需要构建一个足够大的、丰富的网络模型；另一方面，要考虑构建、维护模型的 费用和考虑概率推理的复杂性一般来讲，复杂的模型结构，它的概率推理的复 杂性也较高，而这往往是影响贝叶斯网络效率的一个重要方面实际上建立一个 贝叶斯网络往往是上述三个过程迭代地、反复地交互过程 第一个任务主要在领域专家的指导下来选取适宜的变量，同时在有些情况下 也需要一定的策略从专家提供的变量中选择重要的因子，如在贝叶斯网络分类中 的m a r k o v b l a n k 的选择后面的两个任务在自动构造贝叶斯网络中是比较关键的 步骤，也是目前比较活跃的研究领域：即所谓的贝叶斯网络的结构学习和参数学 习 一般情况下，有三种不同的方式来构造贝叶斯网络： ( 1 ) 由某领域专家确定贝叶斯网的变量( 有时也成为影响因子) 节点，然后通 过专家的知识来确定贝叶斯网络的结构，并指定它的分布参数这种方式构造的 贝叶斯网完全在专家的指导下进行，由于人类获得知识的有限性，导致构建的网 络与实践中积累下的数据具有很大的偏差： ( 2 ) 由某领域专家确定贝叶斯网络的节点，通过大量的训练数据，来学习贝叶 1 0 贝叶斯网络诱导的内积空间与核函数 斯网的结构和参数这种方式完全是一种数据驱动的方法，具有很强的适应性而 且随着人工智能、数据挖掘和机器学习的不断发展，使得这种方法成为可能如 何从数据中学习贝叶斯网的结构和参数，已经成为贝叶斯网络研究的热点 ( 3 ) 由某领域专家确定贝叶斯网络的节点，通过专家的知识来指定网络的结 构，然后利用机器学习的方法从数据中学习网络的参数这种方式实际上是前两 种方式的折中，当某领域中变量之间的关系较明显的情况下，这种方法能大大提 高学习的效率 综上我们可以看出，在由某领域专家确定贝叶斯网络的节点后，构造贝叶斯 网的主要任务就是学习它的结构和参数很显然，学习结构和参数不是完全独立 的：一方面节点的条件概率很大程度上依赖于网络的拓扑结构；另一方面，网络 的拓扑结构直接由联合概率分布的函数来决定然而，一般情况下，我们还是把 这两个方面分开来进行这是因为，带有太多连接的复杂网络结构所需观测的参 数较多，而使得这些参数达到某种信任程度所需的数据量随着参数数目的增加而 迅速增长，并且复杂的结构需要太多的存储空间及冗长繁琐的计算过程才能产生 预测和解释因此，为使贝叶斯网络成为有效的知识模型，在学习过程中致力于 寻找一种较为简单的网络结构是非常必要的，这种简单的结构模型称之为稀疏网 络，它含有最少可能的参数及最少可能的依赖关系下面描述贝叶斯网络的参数 学习和结构学习 2 1 3 贝叶斯网络的参数学习和结构学习 在贝叶斯网络建模中，两个关键的任务是网络参数的学习和网络结构的学 习从数据中学习贝叶斯网络是当前机器学习的难点问题之一贝叶斯网络推理 实质上是回答任何给定证据下的查询问题，包括预测和诊断两个方面【 ( 1 ) 贝叶斯网络的参数学习 贝叶斯网络的参数学习实质上是在已知网络结构的条件下，来学习每个节点 的概率分布表早期贝叶斯网络的概率分布表是由专家知识指定的，然而这种仅 凭专家经验指定的方法，往往与观测数据产生较大的偏差当前比较流行的方法 是从数据中学习这些参数的概率分布，这种数据驱动的学习方法具有很强的适应 性数据指的是领域变量的一组观测值： d = x i ，a 1 ) ，一= 】，毫，) ( 2 2 ) 根据数据的观测状况，可分为完备数据集和不完备数据集完备数据集中的 每个实例，都具有完整的观测数据，不完备数据集是指对某个实例的观测有部分 缺值或观测异常的情况对不完备数据的学习，一般要借助于近似的方法，如 第二章贝叶斯网络与核函数 m o n t e - c a r l o 方法，g a u s s i a n 逼近，以及e m ( 期望极大化) 算法求m l ( 极大似 然) 或m a p ( 最大后验概率) 等尽管有成熟的算法，但其计算开销是比较大的 对完备数据集d 进行概率参数学习的目标是找到能以概率形式p ( 而1 9 ) 概括样 本d 的参数侈参数学习一般要首先指定一定的概率分布族，如夕分布、多项分布、 正态分布、泊松分布，然后利用一定的策略估计这些分布的参数 在数据挖掘中，从数据中学习是它的基本特性，所以无信息先验分布是贝叶 斯学习理论的主要研究对象研究无信息分布的奠基性工作是贝叶斯假设一参数 的无信息先验分布在参数的取值范围内应是均匀的对参数有界的情况，贝叶斯 假设在实际运用中获得了很大的成功，与经典的参数估计方法是一致的，而当参 数无界时，贝叶斯假设却遇到了困难为此，人们又提出了一些选取先验分布的 原则： 共轭分布：共轭分布假定先验分布与后验分布属于同一种类型这一假定为 后验分布的计算带来很大的方便，同时在认知上，它要求经验的知识与现在的样 本信息有某种同一性，它们能转化为同一类型的经验知识 杰弗莱原则：在贝叶斯假设中，如果对参数选用均匀分布，那么它的函数作 为参数时，也应服从均匀分布然而这种情况是很少见的，为克服这一矛盾，杰 弗莱提出了不变性的要求他认为一个合理的决定先验分布的原则应具有某种不 变性，并且巧妙的利用费歇信息阵的一个不变性质，给出了一个具体的方法求得 适合于要求的先验分布 最大熵原则：利用信息论中熵的理论，在确定无信息先验分布时应取参数变 化范围内熵最大的分布作为先验分布最大熵原则比贝叶斯假设前进了不少，但 在无限区间上产生了各种各样的新问题 贝叶斯密度估计在实际应用中遇到的另一个难题就是不完全数据或者说是在 数据稀疏情况下的密度估计对这一问题简单的处理方法是或者忽略含有不完全 数据的样本，或者把含有不完全数据的样本作为一种特殊的哑状态当含有不完 全数据的样本与待估计的参数相关时，这两种处理方法都会对估计造成较大偏 差当前，比较典型的处理不完全数据的方法有： 期望最大化方法( e x p e c t a t i o nm a x i m i z a t i o ne m ) e m 方法迭代地计算最大似然估计( m a x i m u ml i k e l i h o o de s t i m a t i o nm l e ) 和 最大后验概率( m a x i m u m a p o s t e r i o rm a p ) 它处理不完全数据分为以下几个步骤： 含有不完全数据的样本的缺项用该项的最大似然估计代替；把第一步中的 缺项值作为先验信息，计算每一缺项的最大后验概率，并根据最大后验概率计算 它的理想值。用理想值替换中的缺项重复，直到两次相继估计的 1 2 贝叶斯网络诱导的内积空间与核函数 差在某一固定阈值内e m 算法的一个缺点是易陷入局部最优 g i b b s 抽样1 1 9 】( g i b b ss a m p l i n gg s ) 在贝叶斯推理中，g s 是最为流行的马尔科夫、蒙特卡罗方法之一g s 把含 有不完全数据样本的每一缺项当作待估参数，通过对未知参数后验分布的一系列 随机抽样过程，计算参数的后验均值的经验估计在经过几次迭代之后，这些估 计收敛到某一固定值 这两种方法都是对参数的可靠估计，也是目前处理不完全数据的有效方法然 而它们都面临着收敛性较慢的问题，另外它们都建立在不完全数据的样本是可以 忽略的假定下，当违背这一假定时，它们的精度会大幅下降 b o u n da n dc o l l a p s e ( b c ) b c 方法是m a r c or a m o n 提出来的它分为两个步骤：对每个属性求得它 的上下界值这些界值是通过所有可能的完整数据集计算其最大和最小估计而获 得的，因而是与所有可用信息一致的估计这一步最后返回的是与所有可用信息 一致的概率区间；将这些概率区问根据缺值样本的模式特点汇聚成一个点其 方法是根据缺值样本的模式特点对极点赋以权值，然后取这些极点的线性组合b c 既避免了以上两种方法的收敛性问题，同时在计算复杂性方面也有很大的改进【1 1 ( 2 ) 贝叶斯网络的结构学习 网络结构学习的目标是找到和样本数据d 匹配度最好的贝叶斯网络结构，根 据观察贝叶斯网络的视角不同，可以把学习贝叶斯网络结构的方法分成两类：基 于评分的方法( b a s e do ns c o r i n g ) 和基于条件独立性的方法( b a s e do nc o n d i t i o n a l i n d e p e n d e n c e ) 基于评分的方法把贝叶斯网络看成是含有属性之间联合概率分布 的结构，学习的目的是搜索与数据拟和最好的结构一般的做法是给出评价网络 结构的评分函数( 如贝叶斯后验概率、最小描述长度和k u l l b a c k l e i b e r 熵等) 第 二种方法把贝叶斯网络看作是编码了变量间独立性关系的结构学习的目的是根 据独立性关系( 如卡方检验) 对变量分组 基于评分函数的结构学习算法主要由两部分组成：评分函数和相应的搜索算 法。评分函数给出一定网络结构下联合分布的一种概率度量。常用的评分函数有 基于贝叶斯统计的方法和基于最小描述长度原理( m d l ：m i n i m u md e s c r i p t i o n l e n g t hp r i n c i p l e ) 的方法。搜索方法是从众多的可选网络结构中，找出评分最好的 结构，这是一个n p 问题，一般情况下搜索算法找到的是具有某一特殊结构的网络。 贝叶斯网络被看作是编码了变量问独立性关系的图结构，因此学习网络结构 的目的是找到具有独立性关系的变量组，常用的诊断独立性关系的方法是卡方检 验。 f r i e d m a n 4 1 从理论上证明，基于评分的结构学习在分类中可能导致较坏的分类 性能。同时，基于评分的方法在实际应用时，复杂性较高，而基于独立性检验的 第二章贝叶斯网络与核函数 1 3 方法从原理上更接近于贝叶斯网的语义特性，在实际中获得较好的效果【l 】。 2 1 4 贝叶斯网络推理 在2 0 世纪9 0 年代之前，研究主要集中在建立贝叶斯网络基础理论体系和不 确定性推理，学习贝叶斯网络主要靠专家知识一般贝叶斯网络的构建是首先由 相关领域的专家根据事物间的关系来确定出结构模型，即有向无环图，然后再利 用其它方法确定每个节点的条件概率贝叶斯网络构建的专家系统能够对于不同 事物之间的因果关系进行定性和定量的描述，并根据相应的观测或人工干涉做出 推理【引 2 0 世纪9 0 年代以来，研究主要集中在如何根据数据和专家知识建立贝叶斯网 络，相继出现了许多经典的贝叶斯网络学习算法研究人员借鉴统计学领域对多 变量联合概率分布近似分解的方法，从多个角度对该问题进行研究，形成了基于 独立性检验和基于评价与搜索的两大类算法【1 4 1 在学习贝叶斯网络时，不同的领城和问题采用的学习算法是独特的，与贝叶 斯网络学习不同，推理有一套通用的算法常见的精确推理算法包括因果树算法、 p o l y t r e e 1 5 】算法和j u n c t i o n 缸优【1 6 】算法而流行的近似推理算法有抽样( m o n t ec a r l o ) 方法( 如简单的重点抽样) ，而对高维数据更为有效的方法是m a r k o vc h a i nm o n t e c a r l o ( m c m c ) t 1 刀【18 】方法( 包括吉伯斯抽样【1 9 】和m e t r o p o l i s h a s t i n g s 算法) 和交分方 法( 如m e a n f i e l d 2 0 】逼近等) 贝叶斯推理要用到先验信息，当进行推理而缺乏必要的条件或数据时，依靠 经验或者历史资料，来收集、挖掘和j h t _ 先验信息，形成先验分布进行推理，以 提高挖掘质量由数掘挖掘的过程和目的来看，对一个数据集进行挖掘，事先并 不知道能从数据集中挖掘出什么样的知识，如果用先验信息来弥补这样的不足， 就是说用贝叶斯推理来进行挖掘，那就有可能提高挖掘的质量 贝叶斯网络的推理实际上是进行概率计算具体而言，在给定一个贝叶斯网 络的模型的情况下，根据已知条件，利用贝叶斯概率中的条件概率的计算方法， 计算出所感兴趣的查询节点发生的概率在贝叶斯网络推理中，有些研究者具体 划分以下几种推理方式： ( 1 ) 因果推理，是由原因推结论，也称为由项向下的推理f 2 目的是由原因推 导出结果已知一定的原因( 证据) ，则用贝叶斯网络的推理计算，求出在该原因的 情况下结果发生的概率 ( 2 ) 诊断推理，结论推知原因，也称为由底向上的推理目的是在已知结果时， 找出产生该结果的原因已知发生了某些结果，根据贝叶斯网络推理计算，得到 造成该结果发生的原因和发生的概率该推理常用在病理诊断、故障诊断中，目 1 4 贝叶斯网络诱导的内积空间与核函数 的是找到疾病发生、故障发生的原因 ( 3 ) 支持推理【2 2 1 ，提供解释以支持所发生的现象目的是对原因之间的相互影 响进行分析 贝叶斯网络推理的目的是通过联合概率分布公式，在给定的结构和已知证据 下，计算某一事件发生的概率理论上，在给定网络结构和概率分配表的前提下， 任何查询都可以通过反复应用贝叶斯公式和乘积与求和公式而得到网络的结构 特征和相关查询的类型是选择和设计推理算法应该考虑的主要因素网络的结构 特征主要包括网络的拓扑结构、网络的类型、网络规模的大小、网络中领域变量 的类型和分布特征其中网络的拓扑结构是影响推理性能的关键贝叶斯网络的 独立性断言使得推理算法具有可操作性独立性好的贝叶斯网络能指数级的提高 推理算法的效率有一些近似算法正是从这个角度出发，来找到贝叶斯网络近似 的独立性结构【引 2 1 5 分类知识发现 贝叶斯网络提供了一种自然的表示因果信息的方法，用来发现数据间的潜在 联系在这个网络中，用节点表示变量，有向边表示变量间的依赖关系如果在 贝叶斯网络中把其中代表类别变量的节点作为根节点，其余所有变量都作为它的 子节点时，贝叶斯网络就变成了分类器 分类在数据开采中是一项非常重要的任务分类的目的是学会一个分类函数 或分类模型( 也常常称作分类器) ，该模型能把数据库中的数据项映射到给定类别 中的某一个分类可用于预测，预测的目的是从历史数据记录中自动推导出对给 定数据的推广描述，从而能对未来数据进行预测【1 1 分类的输出是离散的类别值 要构造分类器，需要有一个训练样本数据集作为输入训练集由一组数据库 记录或元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特征 向量，除了这些外，训练样本还有一个类别标记一个具体样本形式可记为： ( m ，匕；c ) ，其中m 表示字段值，c 表示类别 分类器的构造方法有统计方法、机器学习方法、神经网络方法等等 分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺值，有的分 布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合 式的目前普遍认为不存在某种方法能适合于各种特点的数据 贝叶斯分类器是一种典型的基于统计方法的分类模型贝叶斯决策理论是处 理分类问题的基本理论，它把分类问题看作是一种不确定性决策问题决策的依 第二章贝叶斯网络与核函数 据是分类错误率最小或者损失风险最小采用贝叶斯分类器必须满足以下两个条 件【1 】： 1 分类的类别数是一定的； 2 各类类别总体的概率分布是已知的 对于含有，个类别的分类问题，首先要定义，个判趾函数： 或者 z ( x ) = p ( c f l 功 z ( 功= p ( c f ) p o lc f ) ( 2 - 3 ) ( 2 _ 4 ) 对应的决策规则为：若彳( 工) 乃( 工) ，j = l ，2 ，；，f 则z c j 可以证明在这种意义下，取贝叶斯后验概率最大的分类器是错误率最小的分 类器 2 2 1 支持向量机 2 2 核函数学习 支持向量机( s u p p o r tv e c t