动态贝叶斯网络推理学习理论及应用-肖秦琨 高嵩 高晓光.pdf
动态贝叶斯网络推理学习理论及应用；动态系统；可靠性评估；故障诊断；贝叶斯网络建模；DBN0212/642007动态贝叶斯网络推理学习理论及应用肖秦琨高嵩高晓光著所·萑宫散社北京图书在版编目(CP数据动态贝叶斯网络推理学习理论及应用/肖秦琨,高嵩,高晓光著.一北京:国防工业出版社,2007.10ISBN9787-11805323-4I.动.Ⅱ.①肖.②高.③高..Ⅲ.贝叶斯推断一研究Ⅳ.0212中国版本图书馆CIP数据核字(2007)第122784号※阍所·宫版社出版发行(北京市海淀区紫竹院南路23号邮政编码100044)京南印刷厂印刷新华书店经售开本850×1168132印张9字数233千字2007年10月第1版第1次印刷印數1-3000册定价20.00元(本书如有印装错误,我社负责调换国防书店:(010)68428422发行邮购:(010)68414474发行传真:(010)68411535发行业务:(010)68472764前言不确定性理论在人工智能、机器学习、自动控制领域已经得到越来越广泛的应用。本书以当前国际上不确定性研究领域的核心工具——动态贝叶斯网络为线索,进行了动态网络推理算法、平稳系统动态贝叶斯网络结构学习模型设计、非平稳系统动态网络变结构学习模型设计、基于概率模型进化算法的动态贝叶斯网络结构寻优算法的研究。推理算法以隐变量作为划分依据,讨论了离散、连续混合模型的推理算法,并进行了算法复杂度及应用领域的讨论;结构学习研究首先从度量体制入手,讨论了动态网络度量体制的可分解性,提出了平稳及非平稳系统网络结构学习模型,以及基于贪婪算法思想的遗传算法寻优思想;最终将推理及结构学习理论用于无人机路径规划、战场态势感知、动态数据挖掘、自主控制领域,并通过大量仿真检验。本书的研究工作得到了西安工业大学专著基金及国家自然科学基金重大研究计划(90205019)的资助。本书全面系统地介绍了动态贝叶斯网络的相关理论,重点介绍了动态网络的经典应用和国内外的新发展。全书共分9章。第1章概述了动态贝叶斯网络的产生与发展、基本操作及表达。第2章和第3章为本书的理论基础部分,首先从静态网络已经取得的理论成果及研究内容人手,由浅入深引出动态贝叶斯网络的基本概念及研究方向,确定本书将要解决的主要问题:DBN推理问题和连续变量的DBN结构学习问题。第4章在第3章基础上,详细讨论了三类动态贝叶斯网络的推理即隐变量离散、隐变量连续隐变量混合DBN推理;隐马尔科夫模型是所有离散动态网络的基础故首先介绍其表达及推理,由此派生出其他离散动态网络,并讨论了如何将复杂离散网络转化为简单HMM的方法,通过算法复杂度实验分析,明确了离散动态网络的相应属性,得出了相应结论,为合理选择DBN推理算法提供依据;在推理中,若系统参数未知或为时变系统,必然涉及参数学习,故在讨论三类网络的推理中亦涉及参数学习问题。第5章从静态网络结构度量机制入手,讨论并推导出动态贝叶斯网络结构用于网络结构度量的BC及BD度量机制;通过描述基于概率模型进化算法的构图基础,引出动态贝叶斯网络结构学习机制,即基于贝叶斯优化(BOA)的动态网络结构寻优算法,BOA算法的关键是根据优良解集学习得到动态贝叶斯网络,以及根据动态贝叶斯网络推理生成新个体,前者更为重要,按照本书提出的基于贪婪算法思想的遗传算法解决动态网络学习,然后应用动态贝叶斯网络前向模拟完成后一步。第6章在此基础上,刻画了基于BD度量体制的平稳动态系统DBN结构学习模型设计,并通过仿真验证了其有效性,针对非平稳随机系统DBN的结构学习模型,提出了一种自适应窗口法用于在线自适应学习变结构DEN结构,仿真结果可行。第7章在第4章DBN推理理论的基础上,从以往UCAV路径规划中使用的方法以及涉及的定义、术语等出发,讨论了静态路径规划、动态路进规划及空间路径规划三方面的基本问题,通过对原始 Voronoi图的改进,提出了平面改进型Voronoi图、空间改进型 Voronoi图的概念,以及平面及空间动态路径重规划区域原则等,为动态路径规划提供有力的整体构型支撑进而应用前几章理论基础,建立基于DBN的战场环境感知模型,仿真结果均表明了构图及动态决策模型的正确性。第8章在DN推理及结构学习的理论基础上,将其用于自主优化及动态数据挖掘。将BOA及基于概率模型的遗传算法的静态图形的优化机制进行推广,提出了一种动态优化的新方法,利用DBN作为t到t+1代转移网络,适时改变优化的基本条件,实时确立新的种群及优化的方向使得自主智能体在无人干预下顺利完成一系列复杂任务成为可能,将变结构DBN结构学习模型设计用于动态数据挖掘,实时确定个因素之间的关系。第9章通过两个典型的应Ⅳ用实例,将DBN推理学习理论进行融合,并用于实际模型。附录给出了与DBN结构度量相关定理、性质的证明,为读者进一步研究和学习动态贝叶斯网络提供参考。本书是作者近年来潜心学习和研究国内外不确定性算法理论、方法和应用成果的一个总结。在本书的编写过程中,得到了西安电子科技大学焦李成教授和清华大学戴琼海教授及英国BankUniversity陈大庆教授的热心指导和鼓励,新加坡南洋理工大学的王海芸博土后审阅了书稿,并提出了许多宝贵意见,特向他们表示衷心的感谢。由于涉及内容广泛及限于作者的学识水平,书中疏漏和不当之处在所难免,希望读者不吝赐教指正。作者目录第1章图模型与贝叶斯网络1.1图模型简介1.2动态贝叶斯网络…1.3动态贝叶斯网络应用研究1.3.1动态时序数据分析与挖掘157781.3.2无人机的态势感知与路径规划1.3.3.进化算法与动态贝叶斯网络混合优化………10第2章静态贝叶斯网络2.1静态贝叶斯置信网络2.2贝叶斯网络的特点与应用范围152.3贝叶斯网络的研究内容162.3.1计算复杂性162.3.2网络结构的确定问题…2.3.3已知结构的参数确定问题……182.3.4在给定结构上的概率计算…………192.3.5贝叶斯网络推理算法…19第3章动态贝叶斯网络基础283.1从静态网到动态网283.1.1概述·28Ⅵ3.1.2推导293.1.3动态贝叶斯网络表达………………313.2动态贝叶斯网络的研究内容353.2.1动态贝叶斯网络推理……………………363.2.2动态贝叶斯网络学习…39第4章动态贝叶斯网络推理…464.1隐变量离散动态网络推理……464.1.1模型数学描述464.1.2隐马尔科夫的研究内容484.1.3隐马尔科夫推理学习仿真…534.1.4隐马尔科夫其他拓扑形式…564.1.5一般离散动态网络和隐马尔科夫关系………………584.2动态贝叶斯网络推理算法性能分析604.2.1动态网络转化隐马尔科夫仿真…………614.2.2离散动态网络推理算法比较仿真…634.2.3连续动态网络推理比较仿真724.3模糊推理与隐马尔科夫结合炮火校射754.3.1概述………………………754.3.2模糊动态网络环境感知框架754.4隐变量连续动态网络推理794.4.1模型数学描述…………794.4.2卡尔曼滤波图模型推理………804.5混合隐状态动态贝叶斯网络…………834.5.1模型数学描述…834.5.2混合动态贝叶斯网络推理…864.5.3混合动态贝叶斯网络学习89第5章动态贝叶斯网络结构学习算法…………………915.1动态贝叶斯网络结构度量体制………915.1.1概述915.1.2动态网络的贝叶斯信息度量………935.1.3动态贝叶斯网络BD度量965.2动态贝叶斯网络度量分解性能分析985.3构建动态网络结构寻优算法1145.3.1基于概率模型的进化算法1155.3.2基于贝叶斯优化构造动态网络结构算法1165.3.3学习动态贝叶斯网络…1185.3.4动态臾叶斯网络推理…1275.4基于贝叶斯优化构建动态网络结构算法仿真………128第6章动态贝叶斯网络结构学习模型…1346.1平稳系统动态网络结构学习模型设计1346.1.1模型设计1356.1.2仿真试验1386.2变结构动态网络自适应结构学习模型设计………1446.2.1模糊自适应双尺度…1446.2.2动态系统非平稳程度和平稳性的测量……1516.3非平稳系统网络结构学习仿真试验153第7章基于动态贝叶斯网络的路径规划……1657.1无人机平面静态路径规划·…1657.1.1基本概念……1657.1.2基于相同威胁体的路径规划…166Ⅷ
- 2021-05-06下载
- 积分：1
浙江大学计算理论复习总结
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。28.文法是CFG的推广,任何CFG都是文法。G=(V,∑,R,S)29.语言被文法生成ⅲ它是re的。30.所有数值函数都是原始递归的31.原始递归函数集是递归可枚举的。32.特殊语言/问题H={"M"w":M在w上停机}lH={"M"w":M是一台在"w"上不停机的TM}H1={"M":M在“M”上停机}H1={w:要么w不是一台TM的编码,要么w是M的编码,M是一台在"M"上不停机的TM}H:re.;H1:re.;-H,-H1:非r.e.;2-SAT∈P;SAT∈NPThe world as We Dont Know itreAsumming P≠APCo『eHrecursiveSATSATCO-A伊II Asumming P=Npr, eCo-r.erecursiveNP= cO-Np= p33没有算法的问题称作不可判定的or不可解的,如TM的停机问题34.证明不可判定通用图灵机U通过递归函数归约到L如果L是递归的则U是递归的ic若L1非递归,并存在L1到L2的归约,则L2也非递归。递归函数是 Turing Computable的35.语言是图灵可枚举的,证存在枚举它的图灵机。(M通过空格代开始,周期性的经过特殊状态q来枚举L,任意顺序且可重复)6.不可判定语言与递归语言互为补集,与rc语言有交集。37语言是re.,if它是图灵可枚举的;语言是递归的,i它是以字典序 turing可枚举的。8.P在并交连接和补运算下封闭NP在并、连接运算下封闭。若NP在补下封闭则NP=P39.H={M"wM在最多2w步后停机}唾P40.所有正则语言和所有CFL都属于P41.NPA.机器角度去定义:被多项式界限非确定型图灵机判定的所有语言的类。B.基于 verifier的定义:NP问题上建立的非确定机包含两步1)非确定地猜一个解2〕用一个确定的算法判定该解是否为可行解判定一个给定猜测值是否满足该问题(可满足性)的算法称作 verifier,一个问题称作NP问题当且仅当存在一个多项式时间的 verifier这两个定义是不矛盾的,因为如果一台非确定TM在多项式时间内可以判定一个非确定选择的翰入是否满足,就是基于 verifier的定义。P和NP的区别a problem is in P if we can decide them in polynomial time. It is in NP if we candecide them in polynomial time, if we are given the right certificate42.若存在计算函数f的多项式界限的图灵机M,则f称为多项式时间可计算的43.若τ1是L1->l2的多项式归约,τ2是L2->I3的多项式归约,则τ1τ2是L1->l3的多项式归约44.证明NP完全法一、按定义:LΣ*,若(a)L∈NP,且(b)对每个语言L∈NP,存在从L到L的多项式归约则L称为NP完全的。法二、归约,对于语言L,(a)若L∈NP(b)一个NP完全问题可以在多项式时间规约到L,ie. SAT 0 is context-free but not regular49.L=L1L2,L是CFL,则L1一定是CFL(x50. Regular-CFL不一定是CFL,如a*b*c*-anbn包含 anben51. 2-way PDalie PDa whose input heads can move both left and right] are more powerfulthan 1-way pda52. Given a PDa M1 and an fa M2, the problem l(M1)cl(M2)is decidable53.DFA/NFA识别的是 exactly正则语言54.Re.只在补和差下不封闭,CFL在交下也不封闭55.非正则语言的可能是正则语言。比如A:[W=w}及所有回文,A=*,为正则语言56.典型非正则:w=wR57.正则语言的子集可能非正则,如 anben是a*b*c*的子集;又如Σ*是正则语言,H≌Σ*58.归约:X到Y的归约可以理解为X到Y问题的映射, reduction可以解释为 at least asdifficult as….比如ⅹ可以被Y的算法解决,则 X is no more difficult than yⅩ可以约到Y,记X≤Y。e.gx2可以归约到任意两数的乘积。若有A≤B,A是不可判定问题>B不可判定A不递归->B不递归B可判定>A可判定B是递归的->A是递归的59.若X多项式时间归约到Y,Y多项式时间可解,则X多项式时间可解若X多项式时间归约到Y,Ⅹ多项式时间不可解,则Y多项式时间不可解60.X多项式时间归约到Y,Y多项式时间归约到Z,则X多项式时间归约到Z61.PRME( COMPOSITE)多项式时间归约到 Factor,但是 Factor多项式时间不能归约到PRIME COMPOSITE )o62.若A≤PB,B∈NP,则A∈NP。证明A≤PB→存在确定图灵机X,可将A归约到B。B∈NP→存在一个非确定图灵机N可判定B。我们希望构造一个新的TM(ⅹN)是的ⅹ*N非确定多项式时间求解A,则A∈NPRunning time of X*N≤1+p(mB>+qp(m)(B多项式时间非确定判定是多项式时间所以A∈NP63若AsPB,B∈P,则A∈P64.若X是NPC的,则X在多项式时间内可解ifP=NP65.SAT多项式时间归约到3SA(3AT是NPC的)66.证明语言L是R/Re, Non rea) Intuitively想想有没有半判定(判定)的TM,有则Rc、(R)。若非R执行下一步。b)用能否由Re.( Non re.)语言归约到该语言,能则Re而非R( Non re)严格用归约函数定义f:A≤B,r1∈A当且仅当r1∈Beg1∈H,M∈L证明Recg2∈非H,iM∈L证明 Non rc注意方向:是从A的实例经过递归函数推向B的实例。详细介绍http://www.cs.rice.edu/nakhleh/comp481/finalreviewsp06sol.pdf67.递归与μ递归等价68.PDA中,若每一个格局至多有一个格局接在它后面,则为确定型的。确定型CF在补下封闭69.M半判定L:w∈L,ifM在w上停机,注意半判定图灵机中不存在“拒绝”状态。只要不接受w,就不停机。70. Chomsky hierarchyElements of the Chomsky HierarchyRecursively enumerable languagesRecursive languageContext sensitive languagesContext ee languageseterministccontext free languagesRegularanguages71.俩证明7.6证明P在并、交、 Kleene*连接和补运算下封闭(1)并:对任意L,LEP,遴n时间图灵机M1和nb时间图灵机M2判定它们且c=max{ab}对L1L2构造判定器MM=“对于输入字符串w1)在W上运行M1,在w上运行M22)若有一个接受则接受,否则拒绝。时间复杂度:设M1为0(n)M2为0(m)。令c=max{ab}第一步用时0(n+n),因此总时间为Oma+n)=0(n9所以L1L2属于P类,即P在并的运算下封闭。(2)连接对任意L1,L2属于P类,设有n时间图灵机M1和m时间图灵机M2判定它们,且c=max{ab}。对L1l2构造判定器MM=“对于输入字符串w=w2灬,Wn对k=0,1,21…,n重复下列步骤。在wW2…wk上运行M1,在wk1wk+2…n上运行M若都接受,则接受。否则继续。若对所有分法都不接受则拒绝。时间复杂度:(n+1x0(n+0m-0(m+4)+0(nb+4=0(nc+),F以L1oL2属于P类,即P在连接的运算下封闭。对任意L属于P类,设有时间0(n)判定器M判定它,对构造判定器MM=“对于输入字符串〔1)在w上运行M12)若M1接受则拒绝,若M1拒绝则接受。时间复杂度为:0(m)。所以属于P类,即P在补的运算下封闭。77证明NP在并和连接运算下封闭。1)并对任意L1,L2∈NP,设分别有n时间非确定图灵机M1和n时间非确定图灵机M2判定它们,且c=max{a,b}。构造判定LL2的非确定图灵机M:M=“对于输入字符串w1)在W上运行M1,在w上运行M2。2)若有一个接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时为O(n-)+O(n),因此总时间为On+n)=0(n。所以LLz∈NP,即NP在并的运算下封闭2)连接对任意L,L2∈NP设分别有na时间非确定图灵机M1和m时间非确定图灵机M2判定它们,且c=max{ab}。构造判定L1oL2的非确定图灵机M:M=“对于输入字符串w:1〕非确定地将分成两段xy,使得w=xy。2)在x上运行M1,在y上运行M23)若都接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时O(n,第二步用时为0(n)+0(m),因此总时间为o(n+m)=0(n。所以L1oL2∈NP,即NP在连接运算下封闭。专题一一图灵机可判定性问题判定以下问题是否可判定:声明:思路—想证明B问题不可解,1.从一个不可解问题A入手(如停机问题)2.创建B的—个实例,从中推出如果能解决B,A也就可以解决了3.所以B是不可解的1.一个图灵机有至少481个状态。我们可以给出这样一个TMN进行cnc(M)a)数M中状态数,直到481b)如果达到了481,N就接受,否则拒绝2.给定图灵机在空串上走了481步还没停机。构造2带图灵机N,a)2a带:写481个0b)1s带在空串上模拟M,每走一步,第2带就删掉一个0c)如果M在所有0都删掉之后停机,则N接受,否则不接受给定图灵机,判定它是否在一些输入上经过481步还没停机?a)按字典序找出所有 length
- 2020-12-01下载
- 积分：1
