毕业论文外文翻译.pdf

西南交通大学本科毕业设计（翻译） 第 1页 “雪球（系统） ” ：从大量文本集合中提取关系 尤金艾金特路易斯格拉瓦诺 摘要 文本文件通常包含一些有价值的、隐藏在正规的英语句子中的数据。这些数 据， 如果能作为一个关系表，让我们可以用来回答精确的查询或者运行数据挖掘 任务，则是一种最好不过的利用方法。我们探索出了一种，只需要从用户中得到 一些训练的例子，就可以从文档集合中提取这些表的技术。这些例子通常被用来 提取模式，接着可以使新的元组从文档集合中被提取出来。基于这个想法，我们 提出了雪球系统。雪球推出了从纯文本文件中生成模式和提取元组的新策略。 在 每一次迭代的提取过程中， 雪球可以在没有人为干预的情况下对这些模式和元组 的质量进行评价，并为下一次迭代保留最可靠的部分。在本文中，我们还对我们 的任务开发出了一种可扩展的评价方法和指标， 并通过超过30万份的报纸文件对 雪球和类似的技术做了一个周密的实验评估。 1.引言 文本文件往往隐藏着宝贵的结构化数据。例如，报纸上的大量文章可能包含 了一些组织的总部位置的信息。如果我们需要查找总部的位置，也就是说比如查 找微软的总部， 我们可以尝试及使用传统的信息检索技术来寻找包含我们想要查 询13的答案的文件。或者，如果我们以某种方法拥有一张可用的、列出了所有 在我们的文档集合中提到的组织的位置的表， 我们就可以更准确地回答这样的查 询。在这样的表中，元组就表示组织总部 o 是处于 l 这一位置的，同时这一 信息在我们收集的文件中也会被呈现。在我们表中的微软，雷德蒙这一元组 就会给我们的查询提供答案。网页中包含着数以百万计的、隐藏了以结构化形式 被最好地开发的数据的网页文本。在本文中，我们开发出了，在最少人工参与的 情况下从纯文本文件中提取结构化数据的雪球系统。我们的技术是建立在布林3 的双迭代模式扩展法的基础上的。 （1）DIPRE：双迭代模式扩展法 双迭代模式扩展法按计划来说， 是一种成可以从大量超文本标记语言文件中 提取结构化关系（或表）的方法。这种方法在一个像万维网那样的环境中会最好 地应用，因为在那样的环境里表中被提取的元组往往会重复出现在文档（即， 在 西南交通大学本科毕业设计（翻译） 第 2页 可用的超文本标记语言页）集的上下文里。双迭代模式扩展法利用集合中的冗余 和内在结构，在弱监督的情况下来提取目标的关系。 在接下来的文章中，我们会重点介绍上述组织-位置这一关系的情况。在这 种情况下， 双迭代模式扩展法的目的是在一个给定的文档集合中提取表中出现的 所有组织-位置元组。最初，我们只提供用双迭代模式扩展法方法找到的少数有 效的组织-位置对的实例。例如，就是一个有效的对，这意味着 微软是一个总部位于雷蒙德的组织。同样的，如表1所示，我们也提供了一些其 他双迭代模式扩展法的例子。此外，用户一般会提供一个与实体匹配的正则表达 式。这就是双迭代模式扩展法需要从用户得到的所有训练语料。 表1：用户为双迭代模式扩展法提供的元组实例 组织总部位置 微软雷德蒙 埃克森苏格兰 国际商务机器公司阿蒙克市 波音公司西雅图 英特尔圣克拉拉市 最初的训练阶段过后，双迭代模式扩展法将会查找在文本文件中组织和地点 这一关系的实例。然后，双迭代模式扩展法会检查最初元组附近的文本。例如， 双迭代模式扩展法检查到微软和雷蒙德周围的上下文 “计算机服务器在微软总部 雷蒙德”后就可以构建模式“的总部在” 。在图1中还列出了其他可 能的模式。 一个双迭代模式扩展法模式由一个五元组秩序，网址词头，左，中，右 组成， 而且通过事件组合在一起产生与分离字符串相等的实体的元组种子，然后 分别把左、右两边的字符串设置为实体左、右两边上下文的最长公共子字符串。 这一顺序反映了该实体的显示顺序，同时在种子元组被发现的地方，网址前缀被 设置成源网址的最长公共子串。从最初的种子元组产生一批模式后，双迭代模式 扩展法就在文章段落中扫描可用的在文本来匹配模式。作为这一过程的结果， 双 迭代模式扩展法产生新的元组并把它们作为新的“种子”使用。之后双迭代模式 扩展法就重新开始在文件中寻找新的元组用来确定新的、 预期会有比较好的结果 的模式。 （2）相关工作 西南交通大学本科毕业设计（翻译） 第 3页 布林的双迭代模式扩展法系统和我们在本文介绍的雪球系统都可以解决长 期以来一直是信息抽取研究课题的问题。但是，不同的是，在我们的任务中， 我 们并不试图提从每个文档提取所有的相关信息， 虽然这一直是传统信息抽取系统 的目标10。一个信息抽取中的主要挑战就是参与系统中每个新任务的手工劳动的 必要量。这一挑战已经以多种不同的方式解决了。其中的一种方法是为了训练系 统，建立一个强大且直观的图形用户界面，从而使领域专家对每一个新任务14 可以迅速采取相应的系统。然而，这些系统仍然需要大量专家的手工劳动来使系 统转向各自新的领域。相比之下，雪球和双迭代模式扩展法为每个新的场景只要 求少数实例元组。 另一种方法是在一个巨大的手动标注语料库下训练系统， 该系统可以运用机 器学习技术生成抽取模式8。这种方法伴随着需要一个巨大的、已标记的语料库 的难处，这又涉及到大量人工参与。为了解决这个问题，人们已经提出了利用未 标记的语料库来进行训练的一些方法。11即通过文件中手动标记为相关或无关 话题的训练语料，自动生成抽取模式培训。这一方法比标签文件需要的手工劳动 更少，然而其付出的努力是巨大的。同时，机器学习技术6利用文件内容以及互 联网的链接结构，从网络建立了包括实体的类和关系的基础知识库。这种方法需 要在大量拥有手工标记过的相关文件段落的网页， 以及一个大的网页关系的训练 集下训练。 最后，一些系统使用未标记的例子来进行训练。这种研究方向最接近我们的 工作。具体而言，我们沿用的方法是属于引导技术的广阔范畴。引导技术在自动 文本处理中已经被认为是一种有吸引力的替代选择。15论证了了这项引导技术 可以用来消歧。5使用引导对于开发文本中的命名实体利用两个互为正交的特 征，即，实体本身的拼写（例如，有一个后缀名为“公司” ）和实体出现的上下 文，来进行分类。12还展示了一种可以对文本中的命名实体进行提取模式并识 别以及分类的引导技术。16描述了双迭代模式扩展法的一种扩展方法可以对网 页信息进行挖掘得到它们的首字母缩略词以及衍生物。2提出了一种可以把已 标记的和未标记的例子相结合， 让用于网页分类的学习算法有效果提升的方法和 理论。 尽管利用系统输出的结果来生成下一步迭代所需要的训练语料的输入这一 基本原则，与所有方法是相同的，但任务有多种类型、千差万别，所以需要各种 相应的方法来解决。 （3）我们的贡献 正如我们先前讨论的，3描述了一种使用引导技术从网页中提取关系的方 法。在本文中呈现的我们的雪球系统，正是建立在这项工作的基础上。我们的主 要贡献包括如下： 西南交通大学本科毕业设计（翻译） 第 4页 1)模式生成和元组提取的技术： 我们开发了一种可以同时达到灵活又有选择 性地对模式进行定义和描述的新策略， 这样我们就可以捕捉到大部分隐藏在文本 集合中的元组，又可以避免生成无效元组（2.1节和2.2节） 。 2)评估模式和元组的策略：因为雪球只需要最低限度的训练量，所以对于在 抽取过程中生成的模式和元组进行评估是至关重要的。这样，雪球通过进一步处 理可以剔除不可靠的元组和模式。总之，我们开发的战略可以评估所提取的模式 和元组的可靠性（2.3节） 。 3)评价方法和指标：像雪球、双迭代模式扩展法这样的评价系统是非常具有 挑战性的：这些系统本身就是为大量文件集合工作而设计的，所以以手工检查所 有文件来提取元组并建立一张“完美”的表几乎是不可行的。而我们接下来介绍 的这个可扩展的评价方法和相关指标（3节） ，我们用它对部分4和部分5的大量训 练和测试文档集合进行了大规模实验。这些文本集合总数超过300,000。 2.雪球系统 本节中，我们展示了雪球系统（图2）基础双迭代模式扩展法发展的关键成 分。更具体来说，雪球提出了一种从文本文件中生成模式和提取元组的新技术 （2.1节和2.2节） 。同时，雪球提出了一种对提取过程中每一次迭代产生模式和元 组的质量进行评估的战略（2.3节） 。只有那些被视作“充分可靠”的元组和模式 会被雪球保留，用于系统接下来的迭代（2.3节） 。用这些模式和元组的生成和过 滤来显著提高所提取的表的质量的新策略，将作为实验评估在第5节展示。 2.1生成模式 提取表的过程中的一个关键步骤是生成模式来找到文件中新的元组。 理想情 况下，我们希望模式是具有选择性的，这样就不会产生错误的元组，同时具有很 高的覆盖率，这样就能找到很多新的元组。这一节，我们会介绍一种从一组种子 元组和一个文档集合中产生这样的模式的新方法。 雪球最初只给定很少一部分例子元组。 对每一个这样的组织-位置元组的，雪球会找到在文档集合中 o 和 l 彼此相近的文本段落，就像双迭代模式扩展 法做的那样，分析文本中 o 和 l 的“连接点”用以生成模式。雪球从基本的双迭 代模式扩展法改进的一个关键之处，是雪球的模式包含了命名实体标签。 西南交通大学本科毕业设计（翻译） 第 5页 附：英文原文 Extracting Relations from Large Plain-Text Collections EugeneAgichtein Luis Gravano Department of Computer Science Columbia University 12 14Amsterdam Avenue New York, NY 10027-7003, USA ABSTRACT Text documents often contain valuable structured data that is hidden in regular English sentences. This data is best exploited if available as a relational table that we could use for answering precise queries or for running data mining tasks.We explore a technique for extracting such tables from document collections that requires only a handful of training examples from users. These examples are used to generate extraction patterns, that in turn result in new tuples being extracted from the document collection. We build on this idea and present our Snowball system. Snowball introduces novel strategies for generating patterns and extracting tuples from plain-text documents. At each iteration of the extraction process, Snowball evaluates the quality of these patterns and tuples without human intervention, and keeps only the most reliable ones for the next iteration. In this paper we also develop a scalable evaluation methodology and metrics for our task, and present a thorough experimental evaluation of Snowball and comparable techniques over a collection of more than 300,000 newspaper documents. 1 INTRODUCTION Text documents often hide valuable structured data. For example, a collection of newspaper articles might contain information on the location of the headquarters of a number of organizations. If we need to find the location of the headquarters of, say, Microsoft, we could try and use traditional information-retrieval techniques for finding documents that contain the answer to our query Alternatively, we could answer such a query more precisely if we somehow had available a table listing all the organization-location pairs that are mentioned in our document collection. A in such table would indicate that the headquarters of organizationo are in location and that this information was present in a document in our collection. Tuple in our table would then provide the answer to our query. The web contains 西南交通大学本科毕业设计（翻译） 第 6页 millions of pages whose text hidesdata that would be best exploited in structured form. In this paper we develop the Snowball system for extracting structured data from plain-text documents with minimal human participation. Our techniques build on the idea of DIPRE introduced by Brin DIPRE: Dual Iterative Pattern Expansion DIPRE was proposedas an approach for extracting a structured relation (ortable) from a collection of HTML documents. The method works best in an environment like the World-Wide Web, where the table tuples to be extracted will tend to appear in uniform contexts repeatedly in the collection documents (i.e., in the available HTML pages). DIPRE exploits this redundancy and inherent structure in the collection to extract the target relation with minimal training from a user.As in the rest of the paper, we focus the presentation on the organization-location scenario defined above. In this context goal is to extract a table with all the location tuples that appear in a given document collection. Initially, we provide DIPRE with a handful of instances of valid organization-location pairs. For example, we may indicate that is a valid pair, meaning that Microsoft is an organization whose headquarters are located in Redmond. Similarly, we provide DIPRE with a few other examples, as Table 1 shows. In addition, the user provides a general regular expression that the entities must match. This is all the training that DIPRE requires from the user. Table 1: User-provided example tuples for DIPRE. After this initial training phase, DIPRE looks for instances of the example organizations and locations in the text documents. Then, DIPRE examines the text that surrounds the initial tuples. For example, DIPRE inspects the context surrounding Microsoft and Redmond in “computer servers at Microsofts headquarters in Redmond” to construct a tern “s headquarters in .” Other possible patterns are listed in Figure 1. A DIPRE pattern consists of a five tuple and is generated by grouping together occurrences of seed tuples that have equal strings separating the entities (middle) and 西南交通大学本科毕业设计（翻译） 第 7页 then setting the left and right strings to the longest common substrings of the context on the left and on the right of the entities, respectively. The order reflects the order in which the entities appear, and urlprefix is set to the longest common substring of the source URLs where the seed tuples were discovered. After generating a number of patterns from the initial seed tuples, DIPRE scans the available documents in search of segments of text that match the patterns. As a result of this process, DIPRE generates new tuples and uses them as the new “seed.” DIPRE starts the process all over again by searching for these new tuples in the documents to identify new promising patterns. Figure 1: Initial DIPRE patterns. and are regular expressions that would match an organization and a location, respectively. RelatedWork Brins DIPRE method and our Snowball system that we introduce in this paper both address issues that have long been the subject of information extraction research. Our task, though, is different in that we do not attempt to extract all the relevant information from each document, which has been the goal of traditional information extraction systems 10. One of the major challenges in information extraction is the necessary amount of manual labor involved in training the system for each new task. This challenge has been addressed in different ways. One approach is to build a powerful and intuitive graphical user interface for training the system, so that domain experts can quickly adopt the system for each new task 14. Nevertheless, these systems still require substantial expert manual labor to port the system to each new domain. In contrast, Snowball and DIPRE require only a handful of example tuples for each new scenario. Another approach is to train the system over a large manually tagged corpus, where the system can apply machine learning techniques to generate extraction patterns 8. The difficulty with this approach is the need for a large tagged corpus, which again involves a significant amount of manual labor to create. To combat this problem, some methods have been proposed to use an untagged corpus for training. 11 describes generating extraction patterns automatically by using a training corpus of documents that were manually marked as either relevant or irrelevant for the topic. This approach requires less manual labor than to tag the documents, but nevertheless the effort involved is 西南交通大学本科毕业设计（翻译） 第 8页 substantial. 6 describes machine learning techniques for creating a knowledge base from the web, consisting of classes of entities and relations, by exploiting the content of the documents, as well as the link structure of the web. This method requires training over a large set of web pages, with relevant document segments manually labeled, as well as a large training set of page-to-page relations. Finally, a number of systems use unlabeled examples for training. This direction of research is closest to our work. Specifically, the approach we are following falls into the broad category of bootstrapping techniques. Bootstrapping has been an attractive alternative in automatictextprocessing.15demonstratesabootstrappingtechniquefor disambiguating senses of ambiguous nouns. 5 uses bootstrapping to classify named entities in text exploiting two orthogonal features, i.e., the spelling of the entity itself (e.g., having a suffix “Corp.”), and the context in which the entity occurs. 12 also presents a bootstrapping technique to extract patterns to recognize and classify named entities in text. 16 describes an extension of DIPRE to mining the Web for acronyms and their expansions. 2 presents a methodology and theoretical framework for combining unlabeled examples with labeled examples to boost performance of a learning algorithm for classifying web pages. While the underlying principle of using the systems output to generate the training input for the next iteration is the same for all of these approaches, the tasks are different enough to require specialized methodologies. Our Contributions As we have discussed, 3 describes a method for extracting relations from the web using bootstrapping. Our Snowball system, which we present in this paper, builds on this work. Our main contributions include: 1)Techniques for generating patterns and extracting tuples: We develop a new strategy for defining and representing patterns that is at the same time flexible, so that we capture most of the tuples that are hidden in the text in our collection, and selective, so that we do not generate invalid tuples (Sections 2.1 and 2.2). 2)Strategies for evaluating patterns and tuples: Since theamount of training that Snowball requires is minimal, it is crucial that the patterns and tuples that are generated during the extraction process be evaluated. This way, Snowball will be able to eliminate unreliable tuples and patterns from further consideration. We develop strategies for estimating the reliability of the extracted patterns and tuples (Section 2.3). 3)Evaluation methodology and metrics: Evaluating systems like Snowball and DIPRE is challenging: these systems are designed to work over large document 西南交通大学本科毕业设计（翻译） 第 9页 collections, so manually inspecting all documents to build the “perfect” table that should be extracted is just not feasible. We introduce a scalable evaluation methodology and associated metrics (Section 3), which we use in Sections 4 and 5 for largescale experiments over collections of training and test documents. These collections have a total of over 300,000 real documents. 2 THESNOWBALL SYSTEM In this section we present the Snowball system (Figure 2), which develops key components of the basic DIPRE method. More specifi