对基于种子的关系挖掘的经典论文的总结.docx

对基于种子的关系挖掘的经典论文的总结

摘要：本文主要简要总结了基于种子的关系挖掘的几篇经典论文。基于种子的关系挖掘，相对于基于聚类的关系挖掘，其主要特点是在对语料库或网络信息进行处理时，需要少量种子元组作为输入，在具体算法的处理过程中，通常会用到迭代等方法。从对这几篇论文的纵向比较可以看出其基于种子的关系挖掘算法的发展脉络。
关键字：关系挖掘 种子元组 模型 迭代算法

一、背景介绍
随着网络的不断发展,Web网已成为一个巨大的分布式信息空间。关系挖掘就是指利用各种关系挖掘算法，从信息量很可观的网络中挖掘出两个或多个实体中存在的各种关系。同其它网络数据挖掘类似，关系挖掘要处理的信息量大。一般都是开放的万维网或相当大的语料库。处理所得结果的规模也比较大，否则不具有较高的应用价值。关系挖掘在关系挖掘领域，已有学者做出大量研究，总结出两大类关系挖掘的算法：基于种子的关系挖掘算法及基于聚类的关系挖掘算法。这两种算法所采用的机理不同，各有自己的优势及缺点。
基于种子的关系挖掘，相对于基于聚类的关系挖掘，其主要特点是在对语料库或网络信息进行处理时，需要少量种子元组作为输入。根据其种子元组的关系特点，进行下一步的关系抽取处理，通常会用到迭代等方法。从其算法的根本思想可以看出，基于种子的关系挖掘方法对种子元组有一定的依赖。选取的种子元组的优劣，会对最终的抽取结果产生一定的影响。
基于聚类的关系挖掘，与之相反，则不需要若干元组进行输入，而是利用一定的聚类算法，对语料库中的各实体对进行分析处理，将关系相近的一类实体对聚成一类，再利用特定算法，解析出他们的关系，即实现关系挖掘的过程。
对于基于种子的关系挖掘，已有很多学者对其进行长时间的研究，其成果也都在发表的论文中有所体现。关系挖掘领域的若干经典论文，和这些论文提出的算法如Extracting Patterns and Relations from the World Wide Web(Sergey Brin,1997)提出的DIPRE算法，为以后的基于种子的关系挖掘算法奠定了基础。很多后来的研究都是在这些经典论文的基础之上的。而本文就是对基于种子的关系挖掘的经典论文做出归纳和总结，以理清关系挖掘领域基于种子的挖掘算法的发展脉络，以为后面的学习与研究提供提示与参考。
本方将要涉及到的经典论文如下：Extracting Patterns and Relations from the World Wide Web (In International Workshop on the Web and Database, 1998), Snowball: Extracting Relations from Large Plain-Text Collections (In International Conference on Digital Libraries, 2000), StatSnowball: a Statistical Approach to Extracting Entity Relationships(In the Proceedings of the 18th international World Wide Web conference , 2009). 这几篇论文都是基于种子的关系挖掘方法的经典论文。但其所使用的算法及思想也存在着交叉与递进。本文将以由简到繁，由易到难的顺序依次介绍这几篇论文。介绍时分别以文章的目的，思想（算法），及其做出的探索与改进为线索依次介绍。
二、经典论文介绍
1. Extracting Patterns and Relations from the World Wide Web
这篇论文及其提出的DIPRE算法为后来关系挖掘领域的相关研究奠定了基础。很多后来基于种子的算法研究都是以这篇论文为基础，进行了扩展和完善。后续的算法虽然不断改进，但是其根本思想还是由DIPRE算法沿袭而来。这篇文章主要探索的目标是从信息量大且信息极其分散的万维网中抽取出具有一定关系且数量可观的元组对。
朝着这个目标，作者提出了关系抽取算法——DIPRE。在描述这个算法之前，作者首先讨论了模型与关系两者间的双重对应特点。简而言之，就是如果两个实体（即一对元组）间存在一定关系，那么在数据量庞大的万维网数据库中，这两个实体出现时一般情况下会存在若干个模型与之相对应。而对于两个总是以若干一定模型出现的实体来说，它们之间很可能存在着某种关系。基于这个思想，作者引入了利用关系与模型的这种特点的DIPRE算法。在具体的算法中，为了算法的最终实现，作者对模型及关系都采用了数学的方式，进行了精准的定义。算法的大体思想如下：
1. 根据已经得到元组（第一次迭代则是手工输入的种子元组），从语料库中找到这些种子元组共现的上下文。
2. 从这些上下文关系中，根据要求提取出这些种子元组共现时的模型。
3. 根据规则对模型进行筛选，确定出若干可用的模型。
4. 将这些模型投入到语料库中，与若干元组进行匹配，根据匹配结果，得到一些新的、满足所给的种子元组关系的元组对。
5. 如果已经得到足够数量的元组对，或者，多次迭代元组数量无显著增长，则停止算法，否则返回第一步。
文章还对算法运行过程中的一些参数或阈值进行了讨论。如在对根据现
上下文所得到的模型进行评估时，引入了特异度参数，来描述这个模型的优劣。值得提出的一点是，算法运行过程中，还需要少量的人工干预。根据作者基于此方法进行的实验结果可以看出，DIPRE算法基本解决了关系二元组的抽取问题，并取得可以接受的召回率与准确率。
2. Snowball: Extracting Relations from Large Plain-Text Collections
这篇论文系统介绍了Snowball系统，这个系统的构造正是基于的Sergey Brin的DIPRE的算法之上的。与上篇论文相比，这篇论文的基本思路及方法没有大的变化。在其构建成的Snowball系统中，主要有两个大的改进措施。一是在引入命名标签机制，在确认实体对的标签之前，首先对各个实体打上属性标签（这一行为可由专门的命名实体标签工具来做），这样做可以提高产出模型及抽取关系元组的正确率。二是引入了专门的、具有一定规模的评估模型及元组质量的评价系统。DIPRE虽然也对模型进行了评价，但是其评价方式比较粗略与笼统。从后来的对比实验可以看出，Snowball系统中的评估系统，可有效提高最后抽取的元组的质量。
Snowball系统主要由以下几个部分构成,且各部分的功能阐述如下:
1. 找到共现对。即根据系统输入时的种子元组，到待进行关系挖掘的语料库中搜索到所有种子元组的共现对。
2. 对实体打标签。在Snowball系统中，实体是具有标签的，且关系挖掘过程中所产生的模型也是具有标签的。在对模型的匹配过程中，共现实体对不仅仅要匹配模型中的上下文定义，而且对应实体的标签属性也要相匹配，才能被认为是与一个模型相匹配。
3. 产生模型。在Snowball系统中，模型被定义为一个五元组，且对应表示上下文的三个向量（left, middle, right）具有权重，权重体现了每个项目在相对的上下文中的重要程度。产生模型的算法，与在DIPRE算法中的思想基本一致。都是根据多对共现实体对的上下文相同的部分来产生模型。
4. 对产生的模型进行评估。这是该系统与DIPRE系统的主要不同。在本文中，作者引入了多个参数（如可信度，对数可信度），来考察产生的模型及后文要提到的抽取的元组的质量。在这个评估体系中，作者首先用高质量的种子元组来评估模型，得到高质量的模型后，又反过来用这些模型来评价新抽取得到的元组。
5. 抽取元组。即通过经过过滤的模型，放回到语料库中进行元组匹配，最后得到一定数量的元组。
6. 评估元组。在对模型的评价中已经提到，该系统还会对产生的元组进行评价。在评估元组中，系统会通过元组与高质量模板的匹配程度，来计算出该元组的可信度。
同DIPRE算法类似，Snowball系统没有解决关系抽取过程中需要人工干预的问题。但该系统对模型的精准定义上有了很大的改进，提高了关系抽取过程的效率与准确率。同时，该系统对模型及元组的质量的评估做出了很大的探索，形成了一个规模化了评估体系。通过实验数据，可看出应用该体系后，抽取元组的正确率和准确率有了大幅提升。
3. StatSnowball: A Statistical Approach to Extracting Entity Relationships
基于Snowball系统，微软亚洲研究院的研究人员对其进行改进，引入了MLN（马尔可夫逻辑网络）来评判模型的质量，提出了StatSnowball系统模型。与Snowball相比，此系统对MLE（最大似然估计）的应用，使得系统在评估与选择模型上更为精准。在此系统中，模型中每一项目权重的确定可以通过MLN学习自动得到，而不像Snowball系统还需要专门的启发式规则来确定每一项目权重。同时，StatSnowball易于扩展。
该系统的总体可以分为以下几个部分，每个部分的功能阐明如下：
1. 输入部分。同其它基于种子的关系挖掘系统类似，StatSnowball系统需要少量种子元组作为输入，以启动后续挖掘的迭代过程。
2. 模型训练。得到种子元组后，StatSnowball会在线对种子元组进行学习，得到一系列模型。在这个过程中，StatSnowball的模型产生算法与Snowball大同小异。值得指出的是，同Snowball采用启发式限制不同，StatSnowball系统采用了概率模型来训练关键字与模型。这样一来，StatSnowball系统克服了若干Snowball的缺点，可以同等的处理特定模型及一般模型。
3. 模型筛选。针对某些种子元组得到了若干关系模型后，还要对模型进行筛选。本文所涉及的模型筛选问题，可以看作是一个马尔克夫随机场中的特征消减问题。StatSnowball系统应用了l1-norm的MLE来定义并解决这个问题。本文针对传统的Snowball所应用的评估筛选方法及文中所采用了方法进行了对比实验，结果表明，这一改进显著提高模型质量，并最终提高了元组准确率与召回率。
4. 产生元组。利用上一步所得模型，到开放环境中进行元组匹配和关系抽取。将得到的元组投入到下一轮的迭代过程中去。
5. 关系聚类。对产生元组，运用一定的聚类算法，对其进行聚类处理。并获得聚得的每一类的关键词，以标记这一类元组的关系属性。
由此可以看出，StatSnowball系统是对Snowball系统的进一步加工与细化。基于这个系统研制开发而成的人立方系统已投入使用，并在不断的进行着改进和优化。
四、总结
由以上介绍可以看出，这三篇基于种子的关系挖掘论文在其上一篇的基础上思想在一脉相承，方法上不断的做出了探索与改进，以得到更高的准确率及召回率。每一篇所对应系统或算法跟前一篇相比都做出了改进。在对某一领域的研究中，这一现象或作法是相当普遍的，对于一个初步提出的笼统的算法或思想，其理论或指导思想上比较成熟，但在实际的实现上还可能有不少的可以改进的空间。我们可以结合其它领域用到的思维方法，对这一算法或系统的某部分进行优化，从而达到了对这一问题更为深入的探索，同时也可能得到解决这一问题的更好方式。

参考文献
[1] S. Brin. Extracting Patterns and Relations from the World Wide Web (In International Workshop on the Web and Database, 1998).
[2]Snowball: Extracting Relations from Large Plain-Text Collections (In International
Conference on Digital Libraries, 2000).
[3]StatSnowball: a Statistical Approach to Extracting Entity Relationships (In the Proceedings
of the 18th international World Wide Web conference, 2009).
[4]Proceedings of the Sixth Message Understanding Conference.( Morgan Kaufman, 1995).
[5] Unsupervised models for named entity classification. (In Proceedings of the Joint SIG- DAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora, 1999).
[6] Learning to construct knowledge bases from the World Wide Web, (Mark Craven, Dan DiPasquo, Dayne Freitag, Andrew McCallum, Tom Mitchell, Kamal Nigam , Sean Slattery, Artificial Intelligence, April 2000).
[7] Mixed-initiative development of language processing systems, (David Day , John Aberdeen , Lynette Hirschman , Robyn Kozierok , Patricia Robinson , Marc Vilain, Proceedings of the fifth conference on Applied natural language processing, p.348-355, March 31-April 03, 1997, Washington, DC ).
[8] Description of the UMass system as used for MUC-6.(David Fisher , Stephen Soderland , Fangfang Feng , Wendy Lehnert, Proceedings of the 6th conference on Message understanding, November 06-08, 1995, Columbia, Maryland)