链事件图的推理和学习

发布时间：2018-01-05 21:06

本文关键词：链事件图的推理和学习　出处：《西安电子科技大学》2015年硕士论文　论文类型：学位论文

【摘要】：概率图模型的主要研究内容包括表示理论、推理理论和学习理论,基于不同的表示理论,人们提出不同的模型以满足各种问题的需要.在传统的概率图模型中,常常使用节点表示变量,使用节点之间的边表示变量间的依赖关系.基于新的表示理论,Jim Q.Smith等人于2005年首次提出链事件图的概念,引起了国内外的广泛关注.链事件图作为一类新兴的概率图模型,与经典的贝叶斯网络相比,可以更加全面精细地描述问题,更加方便简单地进行概率推理.链事件图的前期研究重点在于完善其表示理论,目前的研究内容侧重于模型的学习算法研究.已有的结构学习算法都是基于模型评分和模型优化思想从链事件图结构空间中选择评分最高的模型,此类算法的优点是结果精确可靠,缺点是时间复杂度高、适用范围小.针对这些问题,本文的主要工作如下:详细介绍了链事件图的相关基础知识,引入了链事件图的相关定义和术语,结合具体事例阐述了其表示理论和推理理论.同时解释了链事件图的构造原理,对链事件图的推理理论也进行了相应的研究.与贝叶斯网络相比,尽管它们的推理理论差异较小,但其表示理论对于已经熟悉传统概率图模型的人们来说可谓是耳目一新.论文创新性的提出了基于列联表独立性检测的结构学习算法.通过理论证明和实验仿真验证了新算法的可行性、正确性和高效性.与已有的AHC算法不同的是,新算法并未使用评分学习的思想,而是改用独立性检测来确定事件树中的情形融合和阶段划分.理论证明了阶段划分和位置划分的等价性,并将其应用于新算法.与已有算法相比,新算法在实验仿真中可以极大的降低时间复杂度,平均运行时间约为AHC算法的5.25%.同时,实验验证了新算法的精确度随着学习数据量的增加而明显上升.
[Abstract]:The main research contents of probabilistic graph model include representation theory, reasoning theory and learning theory. Based on different representation theory, different models are proposed to meet the needs of various problems. Nodes are often used to represent variables and edges between nodes are used to represent dependencies between variables. Jim Q. Smith and others first proposed the concept of chain event graph in 2005 based on the new representation theory. As a new kind of probabilistic graph model, chain event graph can describe the problem more comprehensively than classical Bayesian network. It is more convenient and simple to do probabilistic reasoning. The emphasis of the previous research on chain event graph is to improve its representation theory. The existing structural learning algorithms are based on model scoring and model optimization ideas from the chain event graph structure space to select the model with the highest score. The advantage of this kind of algorithm is that the result is accurate and reliable, the disadvantage is that the time complexity is high and the scope of application is small. In view of these problems, the main work of this paper is as follows: the basic knowledge of chain event graph is introduced in detail. This paper introduces the definition and terminology of chain event graph, expounds its representation theory and reasoning theory with concrete examples, and explains the construction principle of chain event graph. The reasoning theory of chain event graph is also studied. Compared with Bayesian network, the difference of reasoning theory is small. However, the representation theory is new to those who are familiar with the traditional probabilistic graph model. This paper proposes an innovative structure learning algorithm based on column table independence detection, which is proved by theory and experimental simulation. The feasibility of the new algorithm is verified. Different from the existing AHC algorithm, the new algorithm does not use the idea of score learning. Instead of using independence detection to determine the case fusion and phase partition in the event tree, the theory proves the equivalence between the stage partition and the location partition, and applies them to the new algorithm, compared with the existing algorithms. The new algorithm can greatly reduce the time complexity in the experimental simulation, the average running time is about 5.25% of the AHC algorithm. Experiments show that the accuracy of the new algorithm increases with the increase of learning data.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】