【作者】 黄涛；

【导师】 张玉芳；

【作者基本信息】 重庆大学 ， 计算机系统结构， 2010， 硕士

【摘要】 概率图模型能很好处理不确定性,一阶逻辑可以简洁地表示知识,将概率与逻辑整合在同一个表示之中一直是人工智能领域的一个长期目标。Markov逻辑网是公式附加权值的一阶逻辑知识库,且可作为构建Markov网的模板。传统的统计方法是基于数据间的独立同分布,并假设这些数据具有相同的结构。但是在现实的Web世界中,存在着大量的半结构化数据,数据本身不但具有复杂的内部结构,而且数据外部通过超链接、引用等联系起来构成关系数据集合。传统的统计方法忽略了这些数据间的关系结构,而这些“关系”却含有更多深层次的语义信息。统计关系学习就是针对“关系”的学习方法,集一阶逻辑/关系表示、不确定性处理和机器学习/数据挖掘于一体,其目的是挖掘关系数据中的似然模型。Markov逻辑网是一种将Markov网与一阶逻辑相结合的统计关系学习模型,已经成为人工智能领域的一个重要研究热点,在互联网、社会网、计算生物学、普适计算等领域应用广泛。本文重点研究了Markov逻辑网在Web领域的相关应用。主要工作归纳如下:1.研究了Markov逻辑网相关理论。本文首先介绍了Markov逻辑网的理论基础,即概率图模型、Markov随机场/Markov网和一阶逻辑。然后研究了Markov逻辑网的概念与特性,包括闭Markov逻辑网、三大基本假设和Markov逻辑网的知识库。最后讨论了Markov逻辑网的权值学习算法和推理算法。2.将Markov逻辑网应用到文本分类中在统计关系学习中,可以通过关系(逻辑)来很好的表示知识,故文本分类问题的Markov逻辑表示也十分的简洁。实验结合了判别式训练的学习算法,MC-SAT、吉布斯抽样和模拟退火等推理算法,结果表明基于Markov逻辑网的分类方法能够取得比传统KNN分类算法更好的效果。3.将Markov逻辑网应用到重复数据删除中本文给出了如何用少量的谓词公式来描述重复数据删除问题中不同方面的本质特征,并将Markov逻辑表示的各方面组合起来形成各种模型。实验采用了判别式训练的学习算法和MC-SAT推理算法,结果表明基于Markov逻辑网的重复数据删除方法涵盖了经典的Fellegi-Sunter模型,其效果明显优于基于聚类算法和基于相似度计算的方法,且可以通过Markov逻辑网构建此类问题的统一框架。4.总结了Markov逻辑网在Web领域的其他潜在应用针对信息抽取问题,本文仅从如何检测域边界的角度出发,构建了Markov逻辑网,虽然不太完善,但其效果略优于传统的隐马模型。而对于超文本分类、信息检索,则给出了较为简单的模型构建方法。综上所述,我们可以得出如下结论:Markov逻辑网是一种功能强大的统计关系学习方法,不仅能够灵活地将大量领域知识采用模块化的形式引入到Markov网中,还可以很好的处理不确定性、允许不完整和矛盾的知识,其应用领域非常广泛。更多还原

【Abstract】 Probabilistic graphical models enable us to efficiently handle uncertainty. First-order logic enables us to compactly represent a wide variety of knowledge. Combining the both in a single representation has been a longstanding goal of AI research. A Markov logic network (MLN) is a first-order knowledge base with a weight attached to each formula, and can be viewed as a template for constructing Markov networks.The traditional statistical methods have focused on data independent and identically distributed (IID), and assumed that data has the same structure. However, there is so much semi-structured relational data in the Web. The data itself not only has a complex internal structure, but also is related to each other via different kinds of relations. The relationship is an important source of semantic information, which is often ignored by the traditional statistical methods.Statistical Relational Learning (SRL), is also known as an relationship learning method, which combines relational/first-order logic representations, Probabilistic reasoning mechanisms, with machine learning/data mining principles together, so as to capture the likelihood model from the relational data. Markov Logic Networks is a new Statistical Relational Learning model in which Markov networks integrates with the first-order logic. It has become concerned in AI research field and has been used in many fields such as World Wide Web, social networks, computational biology and ubiquitous computing.This thesis focuses on applying the Markov logic network in the Web field. The main research work is summarized as following:Firstly, the thesis studies the related theory of Markov Logic Networks.It summarizes the theoretical basises of Markov logic networks, which include probability graph model, Markov random field, Markov network and first-order logic. Then, we study the concepts and features of Markov logic networks, including closed Markov logic networks, three assumptions and Markov logic network knowledge base, and we also discuss two Markov logic network algorithms: weight learning algorithm and reasoning algorithms.Secondly, the thesis studies text classification based on Markov logic networks.In Statistical Relational Learning, relationship enables us to compactly represent a wide variety of knowledge, so the Markov logic of text classification problem is also very concise. Using discriminative learning algorithm for Markov Logic Networks weights, MC-SAT, Gibbs sampling and simulated tempering algorithm for inference in experiments, it proves that the method based on Markov Logic Networks is better than conventional KNN method in text classification.Thirdly, the thesis studies De-duplication based on Markov logic networks.This thesis show how a small number of predicate rules in Markov logic capture the essential features of a problem in De-duplication and combine these rules together to compose all kinds of model. Using discriminative learning algorithm for Markov Logic Networks weights, MC-SAT algorithm for inference in experiments, it proves that the method based on Markov Logic Networks not only covers the original Fellegi-Sunter model, but also achieves a better result than the traditional methods based on Clustering Algorithms and Similarity Measures in De-duplication. The experimental result also shows that Markov logic networks can be used for constructing the common framework for such problems.Fourthly, the thesis summarizes other potential applications of Markov logic networks in Web field.For information extraction, this thesis gives the methods of creating an imperfect Markov logic network in terms of how to detect field boundaries, which achieves a slightly better result than the traditional Hidden Markov Model. As for the hypertext classification, information retrieval, we just give the approaches of creating a relatively model.To sum up, we can draw the following conclusions: Markov logic networks is a powerful Statistical Relational Learning methods, which not only brings various domain knowledge into it in the form of modulars, but also handle uncertainty and permit imperfect and contradictory konwledge. Many important tasks are naturally formulated as instances of Markov logic networks.更多还原