（计算机软件与理论专业论文）一种bayesian网络结构的并行学习方法.pdf

二弛b ! 竖! 趔圆垡结擅鲍荭短堂卫直壁擅塞 摘要 学习b a y e s i a n 网络问题是人工智能领域的一大热点问题。由于网 络结构的空间分布随着变量的数目和每个变量的状态数量呈指数级 增长，因此学习b a y e s i a n 网络是一个n p 难度问题。为了克服在构建 网络结构中计算和搜索的复杂性，许多学者进行了大量的探索性工 作，提出了很多算法，但都有自身的局限性。对于这样一种n p 难度 问题，使用启发算法来学习是个明智的选择。其中蚁群优化算法a c o 是对解决组合优化问题表现出了卓越的性能和效率，但a c o 算法高 时空复杂度的本质决定了它的局限性，算法精度还有提高空间。随着 高性能计算平台的发展，并行化求解组合优化问题的算法相继出现。 本课题就学习b a y e s i a n 算法问题，提出一种并行算法p a c o b ，分别 将b d e 方式和m d l 方式单独使用到该算法当中，并尝试了同时将两 种打分方式相结合，共同应用于该算法，用混合的方法来学习 b a y e s i a n 网络。对a l a r m 和d j c 数据集进行的实验结果表明， p a c o b 算法取得了较好质量的解，为学习b a y e s i a n 网络提供了一种 新的解决思路。 关键词 并行；学习；b a y e s i a n 网络；蚁群算法；信息素；多处理机；启发式 搜索 作者：潘吉斯 指导老师：吕强、王红玲 a b s t r a c t o n ek n do fp a r a l l e lm e t h o do fl e a r n i n gb a y e s i a nn e t w o r k a b s t r a c t n o w a d a y s ，l e a r n i n gb a y e s i a nn e t w o r ki so n eo ft h eh o t t e s tt o p i c si n t h ed o m a i no fa r t i f i c i a li n t e l l i g e n c e h o w e v e ri ti sn p p r o b l e mi n r e g a r d st ot h es t r u c t u r e so ft h en e t w o r ki n c r e a s i n ge x p o n e n t i a l l yw i t ht h e g r o w t ho ft h en u m b e ro fv a r i a b l e sa n dt h e i rs h i f t i n gs t a t e s i no r d e rt o o v e r c o m et h es h o r t c o m i n go ft h es l u g g i s hc o m p u t a t i o na n ds e a r c hf o rt h e r e f i n e dn e t w o r k s ，ar a n g eo fr e s e a r c h e sh a v eb e e nd o n e ，a n dt h er e l a t e d a l g o r i t h m s w e r e p r e s e n t e d u n f o r t u n a t e l y , t h e y a l lh a v et h e i ro w n l i m i t a t i o n s i nr e s p o n s et os u c hs o r to fp r o b l e m s m e t a h e u r i s t i cm e t h o d s t a n d so u ta n dp r e s e n t sa f a i r l ys a r i s f y i n gp e r f o r m a n c e t h ea c o a l g o r i t h m , w h i c hi s o n eo fm e t a h e u r i s t i ca l g o r i t h m ，s h o w se x c e l l e n t e f f i c i e n c yi ns o l v i n gs u c hc o m b i n a t i o no p t i m i z a t i o np r o b l e m s b u tt h e l i m i t a t i o nd o e se x i s ti nv i e wo fi t sh i g hc o m p l e x i t yo ft i m ea n ds p a c e i t i ss t i l ll o n gd i s t a n c et og ob e f o r et h em e t h o d sa r es o u g h to u tt oi m p r o v e t h e p e r f o r m a n c e a b o u ti t sr e s u l t s w i t ht h e d e v e l o p m e n to fh i g h p e r f o r m a n c ec o m p u t i n gp l a t f o r m ，s o m ea l g o r i t h m s o fc o m b i n a t i o n o p t i m i z a t i o np r o b l e m sb yp a r a l y z e da p p r o a c hc o m ei n t ob e i n gg r a d u a l l y i nt h i sp a p e r , ap a r a l l e la l g o r i t h mo fp a c o bi sp u tf o r w a r dt os o l v et h e p r o b l e mo fl e a r n i n gb a y e s i a nn e t w o r k s i t s h e d sn e wl i g h t so nt h e l e a r n i n go fb a y e s i a nn e t w o r kb ya p p l y i n gt h ea l g o r i t h mo fb d ea p p r o a c h a n dm d l a p p r o a c hs y n e r g i s t i c a l l y k e y w o r d s p a r a l l i z a t i o n ；b a y e s i a nn e t w o r k s ；l e a r n i n g ；a c o ；p h e r o m o n e ； m u l t i p r o c e s s o r ；m e t a - - h e u r i s t i c w r i t t e nb yp a nj i s s u p e r v i s e db yl vq i a n ga n dw a n gh o n g l i n g u 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究做 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：遂兰望j日期 学位论文使用授权声明 如o 1 2 。f o 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：渣垫 日 导师签名： 期：? 钾f 1 2 i o 日期： 一种b a y e s i a n 网络结构的并行学习方法 第一章引言 第一章引言 b a y e s i a n 习络的学习是人工智能领域的一大热点问题，蚁群算法是 求解组合优化问题和n p 难度问题的一种有效手段，使用蚁群算法来学 习b a y e s i a n h - j 题，是目前学b a y e s i a n h - j 题的一个新的手段，使用并行的手 段对这类问题进行改进，则是个全新的尝试。 1 1 课题背景 b a y e s i a n 网络作为一种图形化的建模工具将概率理论与有向无环图结 合起来成为一种有力的知识表达工具，研究人员已经开始尝试直接从数据 中学习并生成b a y e s i a n 网络的方法，并取得了初步成果。但b a y e s i a n 网络学 习是个n p 难度问题【1 】，针对这一问题，提出众多确定性的算法随着问题规 模的扩大而性能降低，显然，这类问题的解决方法，启发手段更加适用。蚁 群算法是一种启发式搜索算法，大量的实验结果表明，在解各类组合优化 问题、任务调度问题以及网络路由等问题时，表现出了卓越的性能和效率， 使用蚁群算法来学习b a y e s i a n 网络是一个新的手段和方法。蚁群算法本质 上来说是一种模拟进化算法，它的贪婪启发式规则有助于在搜索过程的初 期找到可以接受的局部解，但是蚁群算法始终存在搜索时间长，易于停滞 的缺陷，在大规模优化问题中，搜索时间慢，在短期内求解到解的精度不 高。为了更好的将蚁群算法应用到学b a y e s i a n 网络结构问题上，并行蚁 群算法学习b a y e s i 柚网络的研究应运而生。又因蚁群算法与生俱来的并行 性，b a y e s i a n 网络结构学习的可分解性，以及高性能计算平台的发展，为蚁 群算法应用于学习b a y e s i a n 网络结构问题的并行化研究提供了先天的优势。 1 2 课题内容 鉴于以上的课题背景，本文就学b a y e s i a n 网 络问题进行了分类，针 对其中一种已知数据集，未知网络结构的情况进行相关算法的研究，阐 第一章引言一种b a y e s i a n 网络结构的并行学习方法 述了部分b a y e s i a n 学习问题的算法和适用范围，将其中一种学 - - j b a y e s i a n 网 络结构的串行算法a c o b 作为本课题的研究重点，编码实现了a c o b 算法， 同时在该算法的基础上，设计了它的并行模型，编码实现相应的并行算 法p a c o b ，比较了两者之间的性能差异，期望提高算法求解的精度。此外， 还针对a c o b 算法中的打分机制进行了扩展，首次使用m d l 方式的k 3 机制 作为a c o b 算法的打分方法，期望该算法能有更出色的表现：在相同处理器 时间内得到更高质量的解，或者得到相同质量的解需要更少的处理器时间。 1 3 课题意义 蚁群算法【2 】自1 9 9 2 年首次由意大利学者m a r c o d o r i g o 提出以来，在国 内外都有一定的研究，但因其缺乏严格的理论基础，所以相对于其它启发式 算法而言，对这一问题的并行化研究屈指可数。本文的重要意义在于提供了 一种b a y e s i a n 习络结构学习问题的解决方案。因为n p 难度问题一直以来都 是很难求解的，在计算机问世之前，对较大规模的问题可以说根本不可能得 到确定的最好解，尽管有了计算机并且其性能极速发展，但实际问题对计算 能力的需求来说，目前仍显滞后。从这方面讲，本文对其它算法的并行研究 又具有实际意义。 就a c o 问题本身而言，目前一些少量的并行研究是针对t s p 、q a p 等问 题而言的，目前还少有使用a c o 学b a y e s i a n i o 题的并行研究的相关文献。 本文首次针对这一问题提出了自己的并行实现手段，为a c 0 问题研究范围 的扩展，学习b a y e s i 姐网络问题的研究手段都提供了一个全新的视角，为今 后此类问题的研究提供一定的参照依据。 1 4 本文的组织结构 本文在第二章提供了相关知识的介绍；第三章提供t b a y e s i a n 络学习 问题的分类和部分算法的介绍；第四章阐述本文提出的a c o 并行策略及实 现方案；第五章对实验结果做出详细分析；最后一章对本课题进行总结。 2 一种b a y e s i a n 网络结构的并行学习方法第二章相关知识 第二章相关知识 2 1n p 难度问题 定义2 1 p 是所有可在多项式时间内用确定算法求解的判断问题的集 合。n p 是所有可在多项式时间内用不确定算法求解的判定问题的集合。 定义2 2 令l 1 和l 2 是两个问题，如果有一确定的多项式时间算法求解l l ， 而这个算法使用了一个在多项式时间内求解l 2 的确定算法，则称l 1 约化 为l 2 。 定义2 3 若一个问题可以由可满足性问题约化得到，则该问题是n p 难度问 题【3 】。 2 2 组合优化问题 组合优化问题是一个极值化问题。对最小化问题，令解空间为有限集 合s ，首先要通过某种手段从解空间找到若干元素构成集合s ，有s ，s ， 若存在代价函数f ：s 一尺，则组合优化问题就是寻找一个解，s 使得馒 小，即f ( s ) 八j ) ， y s s7 。大部分组合优化问题都是n p 难度的，一般认 为不太可能在多项式时间内找到最优解，因此启发式算法在解这类问题时 显现了较强的优势。典型的组合优化问题有t s p 问题、q a p 问题、v r p 问题 等。 组合优化问题的解通常分为全局最优解和局部最优解，根本区别在于 全局最优的解空间s ，= s ，而局部最优的解空间s cs 。a c o 算法属于局部 最优算法。 2 3 并行计算机 传统的计算机是串行结构的，每一时刻只能按一条命令指令对一个数 据进行操作，事实上这种结构限制了运算速度。从6 0 年代起，并行处理技术 3 第二章相关知识 一种b a y e s i a n 网络结构的并行学习方法 开始引入计算机的结构设计中，以改进系统结构。所谓并行处理就是把一个 传统串行处理的任务分解开来，并将其分配给多个处理器同时处理，即在同 一时间间隔内增加计算机的操作数量。为并行处理所设计的计算机称为并 行计算机。 2 3 1 并行计算机的应用 在科学和工程问题的数值建模和模拟时，常需要对大量数据进行很 多次重复计算以得到有效结果，并且要求计算必须在合理时间内完成， 例如数值气象预报、太空中天体运动预测、虚拟现实以及本文针对的学 b a y e s i a n l 网络等类似组合优化问题，这些应用对计算速度的需要总是在不 断的增长。提高计算速度的一种方法是用多个处理器协同求解一个问题，可 以是带有多个处理器的计算机或是以某种方式互连的若干台独立计算机。 除了加速对问题求解之外，多计算栅多处理机的使用可以在给定时间 内计算更多的求解点，从而获得更精确的解。 2 3 2 并行计算机的类型 根据f l y n n 分类法【3 】，通用的计算机分为s i m d ( s i n g l e i n s t r u c t i o ns t r e a m a n dm u l t i p l ed a t as 仃e 锄) 和订i m d ( m u l t j p l ei n s t r u c t i o ns t r e a ma n dm u l t i p l e d a t as t r e a m ) 机两大类。 s i m d 计算机是所谓的阵列机，它有许多个处理单元( p e ) ，由同一个控 制部件管理，所有p e 都接收控制部件发送的相同指令，对来自不同数据流 的数据集合序列进行操作。 m i m d 计算机包括多处理机和多计算机两类，它们都由可各自执行自 己程序的多处理器组成。其中，多处理机以各处理器共享公共存储器为特 征，而多计算机以各处理器经通信链路传递信息为特征。它们与s i m d 计 算机的根本区别在于：s i m d 机中每台处理器只能执行中央处理器的指令， 而m i m d 机中每台处理器仅仅接受中央处理器分给它的任务，它执行自己 的指令，可达到指令，任务并行。 4 一种b a y e s i a n 网络结构的并行学习方法 第二章相关知识 还有一种分类方法为： 共享存储器多处理机系统。一台通常的计算机由执行存放于主存储器 中程序的处理器组成，主存储器由特定地址定位。扩展单处理器的最自然的 方法就是使多个处理器连到多个存储单元，使得每个处理器以共享存储器 的形式访问任意一个存储单元。共享存储器的多处理机系统使用单地址空 间，这意味着在整个主存储器系统中的每一个单元有一个唯一的地址，用此 地址每个处理器就可以访问该单元。和单处理机系统一样，这里也体现了虚 拟存储器的概念，即每个存储单元仍只有一个唯一的实地址，但各个处理器 能使用不同的虚地址对它进行访问。 消息传递多计算机系统。特点是主存储器分布在各台计算机中，每台计 算机都有自己的地址空间，每个处理器只能访问自己本地的主存单元。系统 中的互连网络用于处理器间的消息传递，这些消息可能含有其他处理器进 行计算所需的数据，由程序指明将数据从一个处理器传递给另一个处理器。 分布式共享存储器系统。在这种系统中，每个处理器使用单一的地址空 间对所有存储器进行访问，当一个处理器要访问的单元不在本地存储器中 时，通过消息传递的方法将数据送到该单元并将其传递到处理器，这种传递 以自动方式进行，以使用户感觉到存储器的共享，尽管事实上它是分布的， 不过这种方式会导致很大的延迟。 2 4 并行算法及编程模型 并行算法可以理解为：适合于在某类并行计算机上求解问题和处理数 据的算法，是一些可同时执行的诸进程的集合，这些进程相互作用和协调作 用，从而达到对给定问题的求解。 2 4 1 并行算法的性能评价 三个标准如下【3 】： 1 并行算法的成本c ( n ) 第二章相关知识 一种b a y e s i a n 网络结构的并行学习方法 定义为并行算法的运算时间t ( n ) 与所需处理机数i ；i p ( n ) 的乘积，即 c ( ，z ) = 丁( ，1 ) - p ( n )( 2 1 ) 它相当于在最坏的情况下求解一个问题的并行总的执行步数，如果求 解问题的并行算法的成本在数量级上等于最坏串行算法最坏情况下串 行求解此问题所需的执行步数，则称该并行算法成本为最优的。 2 加速比s p ( n ) 对于一个求解问题，令t s ( n ) 为最快的串行算法在最坏情况下的运算时 间，t p ( n ) 是求解此问题的某一并行算法在最坏情况下的运算时问，则 此算法的加速比定义为 s p ( n ) = t s ( n ) t p ( n ) ( 2 2 ) 可以看出，并行算法的加速比反映了该算法并行性对运行时间的改善 程度，i s p ( n ) p 研) ，当s p ( ，1 ) = 尸 ) 时称具有此加速比的并行算法 为最优的并行算法。 3 并行算法的效率e p ( n ) 并行算法的效率可定义为加速比与处理器数目的比，即 e p ( n ) = s p ( n ) p ( 咒) ( 2 3 ) 它反映了在执行算法时处理机的利用情况，由于l s p ( n ) 尸) ， 故0 e p ( n ) 1 。若一个并行算法的效率等于1 ，则说明在执行算法 的过程中每台处理机都得到了充分的利用。不过一般情况下，要达 到e p ( n ) = l 是不可能的。 2 4 2 并行编程模型 并行编程模型一共可分为四种： 1 隐式编程模型。 这种编程模型相对显式编程模型而言，程序员不用显式的说明并行性， 6 一种b a y e s i a n 网络结构的并行学习方法第二章相关知识 由编译器、运行支持系统对程序进行并行化。现在比较流行的有以下 几种形式：并行化编译器、自动并行化、用户指导和运行时间并行化。 这种模型突出要解决的问题是数据依赖和控制依赖。并行化编译技术 是一个日趋活跃的研究课题，但是目前由于这种技术还不成熟，性能 让研究者失望。 2 数据并行模型。 该模型适用于s i m d 方式，主要思想是将一组数据分布到多个计算机点 上，在结点计算机并行执行相同的指令或程序。另外有一个全局的存 储空间和数据结构进行并行操作。主要特点是：单线程、聚合数据结构 上的操作、语句级或程序块级的同步、单一地址空间、无需显式同步、 无需显式分配工作负载和数据。 3 消息传递模型。 在各个计算机结点并行执行，消息通过计算机网络进行传递，主要是 指令数据、同步信号、中断信号等。现在流行消息传递模型编程工具 有m p i 、p v m 等。主要特点是：多线程、大粒度并行、异步并行、多地 址空间、显式交互、显式分配工作负载和数据。 4 共享变量模型。 享变量模型和数据并行模型类似，都具有单地址空间。同时又和消息传 递模型类似，因为它是多线程和异步的。由于数据驻留在单一共享地 址空间中，因此不需要对数据加以显式分配，通信通过读写共享变量实 现，但是同步必须是显式的。程序设计手段有o p e n m p 、h p f 、p o s i x 标 准线程库等。 本文重点讨论蚁群算法的并行化策略及实现结果，基于此目标以及硬 件条件的限制，选择最后一种编程模型，即共享存储变量模型，考虑到的正 是这种模型程序设计的直观性及方便性，程序设计采用p o s i xp t h r e a d 机制。 2 5a c o 简介 蚂蚁是一种常见的具有社会属性的昆虫。在蚁群身上体现出的群体动 7 第二章扫关知识一种丑a y e s i a n 网络结构的并行学习方法 物的智能特征引起了一些专家的极大兴趣。他们在观察蚂蚁搜索食物的过 程中发现，蚂蚁总是能找到蚁穴与食物之间的最短路径。经过研究发现蚁 群通过一种叫信息素的物质来通信与协作的。这种信息素遗留在蚂蚁觅食 的路径中，整个蚁群就是通过信息素的正反馈效应使得越来越多的蚂蚁聚 积到最短路径上的。m a r c od o r i g o 于1 9 9 2 年首先提出蚁群算法，由于t s p 问 题与蚁群觅食的天然相似性，首先将蚁群算法应用于t s p 问题，成功利用了 蚁群个体闻简单的信息传递特点，搜索食物与蚁穴间的最短路径，很好的 为t s p 这样的n p 难度问题提供了一种使用蚁群算法的解决方案。该算法还 被应用于背包问题、作业安排调度问题，取得了一系列较好的结果。蚁群算 法本质上来说是种基于种群的模拟进化算法，属于随机搜索、全局优化算 法。对于蚊群算法求解优化问题关键在于三点：( 1 ) 适合的选择机制。( 2 ) 适 合的更新机制。( 3 ) 适合的协调机制。对于不同的优化问题，三者都不尽相 同，但原理上是相通的。当然蚁群算法同其它启发式算法一样存在着自身的 缺点。特别是当问题规模扩大时，蚁群算法存在的搜索时间长，易于停滞， 短时间内的解精度不高等不足更为明显，此外，针对不同优化问题的求解还 需要设计不同的蚁群算法来解决。 2 5 1 基本蚁群系统a s 基本蚁群系统最早应用于 r s e f 司题。t s p 问题可由图( n ，e ) 给定，其 中n 是城市集合，e 是城市之问的路径集合( 一个完全连通图) 。设由为城i 和 城j 之间的距离，两者的距离公式为d u ：1 t ( x i - x ) 2 + ( y i - y j ) 2 。令扫i ( f ) ( f = n 1 ，2 一，1 ) 为在t 时刻i 城市上蚂蚁数，则肌= b i ( t ) 为总的蚂蚁数。每只蚂蚁 i i l 都可以认为是具有下列特征的简单个体： 1 其选择城市的概率是城市之间的距离和连接支路上所包含的当前信息 素余量的函数。 2 为了强制蚂蚁进行合法的周游，直到一次周游完成时，才允许蚂蚁走 已访问过的城市。 8 一种b a y l 三s n n 网络结构的并行学习方法 第二章相关知识 3 当完成一次周游，它在每条访问过的支路( i j ) i - 留下一种叫信息素的物 质。 蚂蚁k 在t 时刻从城市i 选择j 前进的概率公式( 2 4 ) 所示。其中口肋懈矾= f n - t a b u s ，t a b u t 为蚂蚁k 已访问过城市结点的集合，则n - t a b u k 表示蚂蚁k 未 访问的城市结点集合。q ( f ) 为t 时刻边( i j ) 上的信息素强度，聊= 石i ，称为启 发因子或可见度，口、p 反映了二者的相对重要程度。 水f ) ：昂印舭以 ( 2 4 ) 砖( f ) ： “k o m “p u 圹 ( 2 4 ) 【0 o t h e r w i s e 蚂蚁根据上述公式从初始结点依次遍历所有结点，回到初始结点，从而 得到一个解，此过程称为一代，这样m 只蚂蚁就能得到m 个解。之后是信息 素更新阶段，每只蚂蚁会在经过的边上留下给定量的信息素，作为下一代蚂 蚁构造解的依据，规则为 q ( f + 1 ) = ( 1 一p h ( f ) + 吒 ( 2 5 ) 其中p 称为蒸发因子，可使蚂蚁在探索过程中忘记以前做出的较差的决 策，t f 为蚂蚁k 在边( i j ) 上一次释放的信息素， ： 击f ( 盯 ( 2 6 ) 吃2 孑砒羔等1 ( 2 6 ) 其中c 为蚂蚁k 在t 至；j t + l 时间内找到的路径矿的长度。可以看出，c k 越小，路 径矿上得到的信息素增量越多，因而下次被选择的概率越大。蚁群系统被 提出以后，引起了全世界相关研究人员的广泛关注，在它基础上发展了一系 列的改进算法。 2 5 2m m a s ( m a x - m i l la n ts y s t e m ) m m a s 4 是诸多改进算法中的一种，它对a s 主要有四点改进。首先， 它只允许一代中最好的或者是到目前为止最好的一只蚂蚁释放信息素；其 9 第二章相关知识 一种b a y e s l a n n 络结构的并行学习方法 次，每条边上的信息量限制在一个特定的区间【，t m a 。】中；第三，各条边 上的信息量初始化为区问上界t m a ，且使用较小的蒸发因子；第四点是当认 为算法已经收敛或者没有更好的解产生时，将所有边上的信息素重新初始 化。信息素更新规则为： t i j = ( 1 一p ) t u + 豸捌 ( 2 7 ) 其中丁磐= 1 c 胁，负责更新信息素的是当前最好( b e s t s o f a r ) 或者一代中 a 骆( i t e r a t i o n b e s t ) 的蚂蚁，更新方式分别为嗜盯= l 一。和略“= l c 曲， 各参数值在【4 】中有详细讨论。大量实验表明m m a s 的效率和求解能力均有 较好的表现。 2 5 3 a c s ( a n tc o l o n ys y s t e m ) a c s 5 与a s 的不同体现在下边三点。首先状态转换规则有所改动，称 为伪随机转换规则，如公式( 2 8 ) ；其次，信息素的全局更新仅限于当前最短 路径，如公式( 2 9 ) ；第三，增加了局部信息素更新以扩大对解空间的搜索， 如公式( 2 1 0 ) 。 a c s 使用了与以上a c o 算法不同的状态转换规则： 7 ， ，= 尹一妇l f 口础仃谴切二。2 仁s ， j 为结点i 的蚂蚁的下一个目标结点，q 为均匀分布于【0 ，l 】的随机变 量，们为给定参数，j 代表按公式( 2 4 ) 位= 1 ) 进行。卯控制对已有信息的利用 和对解空间探索的力度对比。 a c s 的全局信息素更新同m m a s r o ( t + 1 ) = ( 1 一p ) r o ( t ) + p a 玄v ( i ，d t 如 ( 2 9 ) 其中辔= 1 c h ，a c s 只允许当前最好的蚂蚁全局更新信息素。 a c s 在解的构造过程中，还增加了局部信息素更新，即每只蚂蚁经过任 一条边都会在该边留下给定量的信息素，规则为： 0 2讥 + q 抑 o 一 = 一v 丁 一种b a y e s i a n 网络结构的并行学习方法 第二章相关知识 其中，t o = ( n l b ”) ，n 为问题中城市结点的个数。这种局部更新的作 用在于减少边( i j ) 上的信息素，以增大下一代蚂蚁选择其它未被访问结点的 机率，即扩大算法对解空问的搜索范围，防止过早收敛现象。 a c s 的一个很重要的特点在于，无论是释放还是蒸发，它只修改蚂蚁经 过的边上的信息素，蚂蚁未经过的边信息量不变，换句话说就是完全通过全 局和局部信息素更新公式来控制所有边的信息量。而其它算法对于没有蚂 蚁走过的边，仍然会依据蒸发因子给它一个负增量。大量实验表明，a c s 能 取得较好的结果。 除了上述算法，还有一些针对蚁群算法的改进如e a s 6 、r a s 7 】，一种 基于分布均匀度的自适应蚁群算法【8 】，一种将遗传算法和蚁群算法结合起 来的算法【9 】等等，这些算法的提出从不同角度对蚁群算法提出了改进，并 在性能上取得了较好的结果。 2 5 4a c o 和局部搜索 在a c o 算法中，启发搜索算法与局部搜索算法的结合可以大大改善 解的质量。a c o 中一个蚂蚁构造的解作为局部搜索算法的初始解，经其优 化后得到的路径再作为a c o 信息素更新的对象。这种结合效果显著。事实 上，a c o 构造解的方式与局部搜索中的很不同，使局部搜索从另一个角度 对解优化的概率很大；另一方面，局部搜索需要一个比较好的初始解，它本 身没有能力发现这样的解，而启发搜索算法恰恰能够提供这样一个解。所以 二者的结合能够使彼此相互补充，使最终的解得到明显改善。 本课题中使用了a c o 中的a c s 算法作为整体算法框架来学习b a y e s i 锄网 络结构，局部优化算法使用了一种试探性的贪心算法。 箜三童jb a y e s ! 型哩终结塑一种b a y e s i a n 网络结构的井行学习方法 第三章学习b a y e s i a n 网络结构 3 1 b a y e s i a n 网络 不确定知识的推理是人工智能领域一个重要的研究课题，概率方法是 其中的一个主流方法，而b a y e s i a n 网络作为一种图形化的建模工具，将概率 论与有向无环图结合起来成为一种有力的知识表达工具。在一些领域中，借 助b a y e s i a n 网络，人们发现了许多令人信服的概率依赖关系。 8 0 年代早期，b a y e s i a n 网络就已经成功地应用于专家系统中对不确 定知识的表达，9 0 年代，研究人员已经开始尝试直接从数据中学习并生 成b a y e s i a n 网络的方法，并取得了初步成果。b a y e s i a n 网络的研究与发展与 现实世界的问题需求密切联系。 现实世界中的一个对象通常可以由若干属性变量来描述，这些变量集 的各种取值组合就构成了该对象的状态空间，而这些变量集中的变量问可 能存在着一定的独立或者依赖关系，所以通过对这个变量问属性的研究就 可以得到该对象知识表示。 b a y e s i a n 网络用一组条件概率函数以有向无环图的形式表示不确定的 因果推理模型。b a y e s i a n 络的信息由两部分组成：首先是表示条件独立 性信息的网络结构g ，g 中的每一个结点表示特定域中的一个概念或变量， 在结点间的连接用有向边表示，反映了结点间的因果关系，体现了域知识 定性方面的特征。其次，每个结点都附有与该变量相联系的条件概率分布 函数p 。如果变量是离散的，则它表现为父结点不同取值的组合概率，对 应的概率表c p t ( 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 ) 体现了域知识定量方面的特 征。b a y e s i a n 网络是- - 种表示数据变量间潜在关系定性定量的方法，它使用 这种图形结构指定了一组条件独立声明和用于描述概率依赖程度的条件概 率值。 b a y e s i a n l 踊络表示了因果关系的总体结构，因此，可以被看作是拥有许 多不同组合的一个抽象知识库。一方面将网络看作一种联合概率分布的表 1 2 一种b a y e s i a n 两j 络结构的并行学习方法第三章学习b 棚i a n 网络结构 示，1 p b a y e s i a n 网络表示了网络中各变量的联合概率分布；另一方面将网络 看作条件独立性声明集合的一种表示。这在b a y e s i a n 网络的表达、学习、推 理算法中得到了统一。 正是由于b a y e s i a n 络是联合概率分布和因果关系表示的完美结合，使 得b a y e s i a n l 网络比产生式规则、决策树、人工神经元网络和聚类等机器学习 方法更具优越性 1 0 】： 1 先验知识的易利用性。 先验知识非常重要，它是人们已经认识和掌握的自然界的现象和规律， 尤其是当数据稀少时，先验知识越显珍贵。事实上，一些已商业化的系 统( 如专家系统) 的知识库直接来自于先验知识b a y e s i a n 网络的直接因 果语义使得转化领域专家的知识有依有据，建造初始网络结构的过程 正规、自然，并且因果影响的不确定性容易转换成概率表达式。这样从 先验知识中容易得到一个初始网络( 因果图) ，然后利用数据对初始网络 求精，先验知识和数据能够完美结合。 2 b a y e s i a n l 网络的结构容易理解，并且利于进一步研究。 和”黑盒子”知识表达方式( 如神经元网络) 相比，学到的b a y e s i a n 网络可 以解释为因果关系，不仅容易被理解和接受，而且也利于进行深入研 究。 3 利用b a y e s i a n 网络可以学习现实世界中的因果关系。 因果关系不仅可以对一些客观现象做出解释，而且可以预测人类在客 观世界的行为结果。 4 b a y e s i a n l 潞作为学习工具的优点来自于b a y e s i a n 网络的概率语义。 多种高效的推理算法使b a y e s i a n l 网络能够回答多种概率查询，包括预 测推理和诊断推理。b a y e s i a n 网络没有查询方向的限制，没有输入变量 和输出变量的区别。标准的分类法和回归法( 如前向神经元网络和决策 树) 只能进行一个方向的计算。并且，通过在给定变量值的条件下计算 查询变量的条件概率，b a y e s i a n 网络能应用于不完备数据的学习，而分 类法和回归法都不能用于不完备数据的学习。 第三章学习b a y e s i a n 网络结构 一种b a y l 三s i a n 网络结构的并行学习方法 除此之外，b a y e s i a n l 网络学习的方法已经对其他一些方法，如神经元网 络和隐马尔可夫模型造成了冲击。这些方法已经应用于模式识别和语音识 别。b a y e s i a n 网络有取而代之的势头。神经元网络广泛应用的基石是局部学 习，大量计算及处理噪音数据的优点，这些优点b a y e s i a n i 网络同样具备，因 此，b a y e s i a n 网络具有更好的发展前景。 b a y e s i a n 网络定义如下所示： 定义3 1 有向无环图g = ( z ，e ) ，z 是结点集( 而，恝，) ，e 是结点之间 的有向边集，表示变量间的直接依赖关系。每个结点蔚有相应的条件分 布p ( x i l p a ( x i ) ) 表示该结点的概率和父结点p a ( x i ) 相关，和其它结点无关， 且而的父结点集取值已知，p a ( x i ) ( x i ，x 2 ，碥l ，墨“，而j 。根据条件分 布，结点的联合概率p ( x i ，x 2 ，而) 可分解为： 二 p ( x l ，x 2 ，) = llp ( x i l p a ( x i ) ) ( 3 1 ) ：= f 联合概率p 满足这一分解情况的有向无环图g n q 做b a y e s i a n 网络【1 1 】。因 匕b a y e s i a n 网络s 可以形式化表示为s = 。 3 2 学b a y e s i a n i 网络问题 b a y e s i a n 网络的语义和表达使其能够从数据中进行有效的统计学习。 早期对知识表示的构造方法，仅仅利用专家知识构建知识表示( 如知识 库、b a y e s i a n 网络) 经常是困难、费时而且不准确的，尤其对于b a y e s i a n 网络 来说，大量的概率参数难以确定。而现实世界的数据量不断增加并且具有易 获性，计算机强大的计算能力使机器学习是可行的，并且当前大多数系统和 处理过程采用数据驱动的方法，需要高度的自适应性，这使得机器学习成为 可能。如何从数据中进行机器学习已经成为当今的一个热门研究领域。 随着b a y e s i a n 网络方法的产生和发展，近年来，b a y e s i a n 网络作为一种 新的学习工具，逐渐受到广大研究人员的关注。稀疏的b a y e s i a n 网络是联 合概率分布的简洁表示方法，能够捕捉联合概率分布中的定性结构，对于 推理、决策和利用b a y e s i a n l 网络的学习都是很重要的。如果每个变量的父 1 4 一种b a y e s i a n 网络结构的并行学习方法第三章学习b a y e s i a n 网络结构 结点限定为常量，那么b a y e s i a n 网络中的概率参数是变量的线性倍数，而 无结构表示方式的参数是变量数目的指数幂，因此，网络结构是否已知 对b a y e s i a n 网络的学习问题而言尤其重要。 b a y e s i a n 网络中的有向边被解释为因果关系，每个变量的父结点表示直 接原因，那么从数据中学到的b a y e s i a n l 网络是关于领域知识的非常简洁及准 确的描述。b a y e s i a n 网络不仅仅满足于学习到变量间复杂的相关关系，它还 通过引入隐藏变量等方式，追求变量问更直接的因果关系，从而简化了网络 结构。 3 2 1 学习b a y e s i a n 网络的分类 由于b a y e s i a n 网络s = 由网络拓扑结构g 和局部概率分布的集 合p 两部分组成，因此学习b a y e s i a n 网络问题总体上的被分为如下几方 面【1 0 】： 1 网络拓扑结构即有向无环图的学习，简称为结构学习。 2 网络中每个变量的局部条件概率分布的学习，简称为参数学习。 除此之外，b a y e s i a n 网络在结构学习中结点序列【1 2 】【1 3 】的确定问题和 结构问题密切相关，也是b a y e s i a n 学习问题的一大焦点问题。 总之，结构学习、参数学习及序列学习的问题不是完全独立的。一方面， 结点的条件概率很大程度上依赖于网络的拓扑结构；一方面，网络拓扑结构 直接由联合概率分布函数来决定；另一方面，如果预先就能确定结点的序 列，将有助于提高网络结构的学习效率和学习结果的准确性。然而，以分离 的子阶段进行网络学习是很有好处的，为使获取的参数达到某种信任程度 所需的数据量随着参数数目的增加而迅速增长，并且带有太多边的模型的 计算需要太大的存储空间及冗长繁琐的计算过程。因此，为了使b a y e s i a n 网 络作为知识表示模型是可用的，在学习过程中致力于寻找一种最简单的网 络结构是非常重要的，它含有最少可能的参数及最少可能的依赖关系。 因此，根据网络结构是否已知，数据集是否完整，而把学b a y e s i a n 络的方法分做如下四类 1 4 】： 第三章学习b a y e s i a n 网络结构 一种b a y e s i a n 网络结构的并行学习方法 网络结构已知网络结构未知 数据完备概率参数学习：简单统计估计，m l e 方找最优网络结构：m d l 、b d e 等评价标准， 法、b a y e s i a n 方法 启发式搜索、模拟退火搜索等 数据不完备 找最优概率参数：e m 算法、基于梯度方既要找最佳结构，又要找最优参数：有结 法、蒙特卡洛法、高斯算法等构e m 算法、混合模型等 3 2 2 b a y e s i a n i 网络的参数学习 根据上节的分类，已知网络结构的前提下，进行概率分布的参数学习分 为两类：第一类，完备数据条件下概率分布的学习；第二类，不完备数据条 件下概率分布的学习。 3 2 2 1 完备数据条件下概率分布的参数学习 数据完备：在随机数据集d = c 【1 】，c 【m 】l 有m 个实例( c a s e ) ，每个实 例c i 】中都观察到了所有变量工1 恝，的具体取值，数据集d 也称为样本。 定义0 是不确定变量，其取值0 表示关于变量x 1 ，娩，靠的客观概率，称 为参数，概率密度函数p ( o l z l ) 表示0 的不确定性，叩表示背景环境，称之为状 态信息。为简便计，下文中省去。 利用数据集d 进行参数学习的目标是找到能以概率形式p ( c 吲d ) 概括 数据集d 的0 。参数学习的具体方法和不同的概率分布家族相关，如多项分 布、高斯分布、泊松分布等，但学习的基本思想是一致的。最大似然性估 计m l e 方法和b a y e s i a n 方法是常用的两种计算日的方法，它们有假设前提： 数据集中的数据是完备的。 实例之间是相互独立的。 产生实例的概率分布始终相同。 1 最大似然性估计m l e 方法【1 5 】。 m l e 方法是一种基于统计的方法。 1 6 一种b a y e s i a n 网络结构的并行学习方法 第三章 学习b a y e s i a n 网络结构 似然性是评判具体掰坏的一种标准。似然性函