acl acl2011 acl2011-114 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Truc Vien T. Nguyen ; Alessandro Moschitti
Abstract: In this paper, we extend distant supervision (DS) based on Wikipedia for Relation Extraction (RE) by considering (i) relations defined in external repositories, e.g. YAGO, and (ii) any subset of Wikipedia documents. We show that training data constituted by sentences containing pairs of named entities in target relations is enough to produce reliable supervision. Our experiments with state-of-the-art relation extraction models, trained on the above data, show a meaningful F1 of 74.29% on a manually annotated test set: this highly improves the state-of-art in RE using DS. Additionally, our end-to-end experiments demonstrated that our extractors can be applied to any general text document.
Reference: text
sentIndex sentText sentNum sentScore
1 Nguyen and Alessandro Moschitti Department of Information Engineering and Computer Science University of Trento 38123 Povo (TN), Italy {nguyenthi ,mo s chitt i dis i }@ . [sent-2, score-0.027]
2 it Abstract In this paper, we extend distant supervision (DS) based on Wikipedia for Relation Extraction (RE) by considering (i) relations defined in external repositories, e. [sent-4, score-0.482]
3 We show that training data constituted by sentences containing pairs of named entities in target relations is enough to produce reliable supervision. [sent-7, score-0.449]
4 Our experiments with state-of-the-art relation extraction models, trained on the above data, show a meaningful F1 of 74. [sent-8, score-0.32]
5 Additionally, our end-to-end experiments demonstrated that our extractors can be applied to any general text document. [sent-10, score-0.037]
6 , 2004) concerns the extraction of relationships between two entities. [sent-12, score-0.062]
7 This is typically carried out by applying supervised learning, e. [sent-13, score-0.07]
8 277 The drawbacks above would be alleviated if data from several different domains and relationships were available. [sent-18, score-0.038]
9 A form of weakly supervision, specifically named distant supervision (DS) when applied to Wikipedia, e. [sent-19, score-0.334]
10 The main idea is to exploit (i) relation repositories, e. [sent-25, score-0.258]
11 the Infobox, x, of Wikipedia to define a set of relation types RT(x) and (ii) the text in the page associated with x to produce the training sentences, which are supposed to express instances of RT(x). [sent-27, score-0.396]
12 Previous work has shown that selecting the sentences containing the entities targeted by a given relation is enough accurate (Banko et al. [sent-28, score-0.425]
13 , 2010) used DS to define extractors that are supposed to detect all the relation instances from a given input text. [sent-32, score-0.397]
14 This is a harder test for the applicability of DS but, at the same time, the resulting extractor is very valuable: it can find rare relation instances that might be expressed in only one document. [sent-33, score-0.334]
15 For example, the relation President(Barrack Obama, United States) can be extracted from thousands of documents thus there is a large chance of acquiring it. [sent-34, score-0.302]
16 In this paper, we extend DS by (i) considering relations from semantic repositories different from Wikipedia, i. [sent-36, score-0.272]
17 This allows for (i) potentially obtaining training data Proceedings ofP thoer t4l9atnhd A, Onrnuegaoln M,e Jeuntineg 19 o-f2 t4h,e 2 A0s1s1o. [sent-39, score-0.027]
18 Additionally, by following previous work, we define state-of-the-art RE models based on kernel methods (KM) applied to syntactic/semantic structures. [sent-42, score-0.132]
19 We use tree and sequence kernels that can exploit structural information and interdependencies among labels. [sent-43, score-0.235]
20 Experiments show that our models are flexible and robust to Web documents as we achieve the interesting F1 of 74. [sent-44, score-0.044]
21 Although the experiment setting is different from ours, the improvement of about 13 absolute percent points demonstrates the quality of our model. [sent-50, score-0.044]
22 Finally, we also provide a system for extracting relations from any text. [sent-51, score-0.22]
23 This required the definition of a robust Named Entity Recognizer (NER), which is also trained on weakly supervised Wikipedia data. [sent-52, score-0.071]
24 Consequently, our end-to-end RE system is applicable to any document. [sent-53, score-0.028]
25 The satisfactory RE F1 of 67% for 52 Wikipedia relations suggests that our model is also successfully applicable in real scenarios. [sent-55, score-0.252]
26 1 Related Work RE generally relates to the extraction of relational facts, or world knowledge from the Web (Yates, 2009). [sent-57, score-0.135]
27 To identify semantic relations using machine learning, three learning settings have been applied, namely supervised methods, e. [sent-58, score-0.226]
28 , 2002; Culotta and Sorensen, 2004; Kambhatla, 2004), semi supervised methods, e. [sent-61, score-0.067]
29 Work on supervised Relation Extraction has mostly employed kernel-based approaches, e. [sent-68, score-0.04]
30 However, 1Previous work assumes the page related to the Infobox as the only source for the training data. [sent-75, score-0.036]
31 2 Resources and Dataset Creation In this section, we describe the resources for the creation of an annotated dataset based on distant supervision. [sent-81, score-0.153]
32 We use YAGO, a large knowledge base of entities and relations, and Freebase, a collection of Wikipedia articles. [sent-82, score-0.167]
33 Our procedure uses entities and facts from YAGO to provide relation instances. [sent-83, score-0.464]
34 For each pair of entities that appears in some YAGO relation, we retrieve all the sentences of the Freebase documents that contain such entities. [sent-84, score-0.239]
35 It comprises more than 2 million entities (like persons, organizations, cities, etc. [sent-88, score-0.167]
36 These include the taxonomic Is-A hierarchy as well as semantic relations between entities. [sent-90, score-0.186]
37 familyNameOf; (b) numerical attributes that change over time, e. [sent-94, score-0.163]
38 Therefore, we removed those irrelevant relations and obtained 1,489,156 instances of 52 relation types to be used with our DS approach. [sent-101, score-0.484]
39 Out of them, only 28,074 articles contain at least one relation for a total of 68,429 of relation instances. [sent-105, score-0.568]
40 These connect 744,060 entities, 97,828 dates and 203,981 numerical attributes. [sent-106, score-0.218]
41 Temporal and Numerical Expression Wikipedia articles are marked with entities like Person or Organization but not with dates or numerical attributes. [sent-107, score-0.437]
42 This prevents to extract interesting relations between entities and dates, e. [sent-108, score-0.381]
43 Kennedy was born on May 29, 1917 or between entities and numerical attributes, e. [sent-111, score-0.278]
44 Thus we designed 18 regular expressions to extract dates and other 25 to extract numerical attributes, which range from integer number to ordinal number, percentage, monetary, speed, height, weight, area, time, and ISBN. [sent-114, score-0.274]
45 In traditional DS the point (i) is implemented by the Infobox, which is connected to the sentences by a proximity relation (same page of the sentence). [sent-117, score-0.294]
46 In our extended DS, we relax (i) by allowing for the use of an external DB of relations such as YAGO and any document of Freebase (a collection of Wikipedia documents). [sent-118, score-0.218]
47 The alignment between YAGO and Freebase is implemented by the Wikipedia page link: for example the link http://en. [sent-119, score-0.036]
48 1: for each Wikipedia article in Freebase, we scan all of its NEs. [sent-124, score-0.07]
49 Then, for each pair of entities2 seen in the sentence, we query YAGO to 2Our algorithm is robust to the lack of knowledge about the existence of any relation between two entities. [sent-125, score-0.258]
50 If the relation 279 retrieve the relation instance connecting these entities. [sent-126, score-0.572]
51 Note that a simplified version of our approach is the following: for any YAGO relation instance, scan all the sentences of all Wikipedia articles to test point (ii). [sent-127, score-0.35]
52 Unfortunately, this procedure is impossible in practice due to millions of relation instances in YAGO and millions of Wikipedia articles in Freebase, i. [sent-128, score-0.408]
53 3 Distant Supervised Learning with Kernels We model relation extraction (RE) using state-ofthe-art classifiers based on kernel methods. [sent-131, score-0.452]
54 The main idea is that syntactic/semantic structures are used to represent relation instances. [sent-132, score-0.292]
55 This combines a syntactic tree kernel and a polynomial kernel over feature extracted from the entities: CK1 = α · KP + (1 − α) · TK (1) where α is a coefficient to give more or less impact to the polynomial kernel, KP, and TK is the syntactic tree kernel (Collins and Duffy, 2001). [sent-135, score-0.528]
56 The best model combines the advantages of the two parsing paradigms by adding the kernel above with six sequence kernels (described in (Nguyen et al. [sent-136, score-0.305]
57 SKi) (2) ,6 Such kernels cannot be applied to Wikipedia documents as the entity category, e. [sent-140, score-0.264]
58 This data transformation corresponds to different kernels (see (Cristianini and Shawe-Taylor, 2000)). [sent-144, score-0.173]
59 4 Experiments We carried out test to demonstrate that our DS ap- proach produces reliable and practically usable relation extractors. [sent-145, score-0.318]
60 For this purpose, we test them on instance is not in YAGO, it is simply assumed as a negative instance even if such relation is present in other DBs. [sent-146, score-0.258]
61 The candidate relations are generated by iterating all pairs of entity mentions in the same sentence. [sent-155, score-0.233]
62 We carried out 5-fold cross-validation with the tree kernel toolkit4 (Moschitti, 2004; Moschitti, 2008). [sent-159, score-0.197]
63 2 Results on Wikipedia RE We created a test set by sampling 200 articles from Freebase (these articles are not used for training). [sent-161, score-0.104]
64 An expert annotator, for each sentence, labeled all possible pairs of entities with one of the 52 relations from YAGO, where the entities were already marked. [sent-162, score-0.52]
65 The lower result suggests that the combination of dependency and constituent syntactic structures is very important: +3. [sent-170, score-0.107]
66 08 absolute percent points on CK1, which only uses constituency trees. [sent-171, score-0.044]
67 3 End-to-end Relation Extraction Previous work in RE uses gold entities available in the annotated corpus (i. [sent-181, score-0.167]
68 Dates and numerical attributes required a different treatment, so we use the patterns described in Section 2. [sent-187, score-0.163]
69 We note that, without gold entities, RE from Wikipedia still achieves a satisfactory performance of 67. [sent-194, score-0.038]
70 5 Conclusion This paper proposes two main contributions to Relation Extraction: (i) a new approach to distant supervision (DS) to create training data using relations defined in different sources, i. [sent-196, score-0.45]
71 YAGO, and potentially using any Wikipedia document; and (ii) endto-end systems applicable both to Wikipedia pages as well as to any natural language text. [sent-198, score-0.055]
72 29% on extracting 52 YAGO relations from any Wikipedia document (not only from Infobox related pages). [sent-201, score-0.22]
73 net with 5,025 relations, which indicate that our results based on 52 relations cannot be compared with it (i. [sent-207, score-0.186]
74 On the other hand, the only experiment that can give a realistic measurement is the one on hand-labeled test set (testing on data automatically labelled by DS does not provide a realistic outcome). [sent-210, score-0.058]
75 Although, we do not know how many types of relations were involved in the test of (Hoffmann et al. [sent-215, score-0.186]
76 , 2010), it is clear that only a small subset of the 5000 relations could have been measured. [sent-216, score-0.186]
77 , 2010), only one relation extractor is supposed to be learnt from one article (by using Infobox) whereas we can potentially extract several relations even from the same sentence. [sent-218, score-0.627]
78 The importance of using both dependency and constituent structures (+3. [sent-220, score-0.107]
79 08% when adding dependency information to RE based on constituent trees). [sent-221, score-0.073]
80 For this reason, we decided to make available the DS dataset, the manually annotated test set and the computational data (tree and sequential structures with labels). [sent-226, score-0.034]
81 Learning to extract relations from the web using minimal supervision. [sent-247, score-0.214]
82 The automatic content extraction (ace) programtasks, data, and evaluation. [sent-263, score-0.062]
83 A study on convolution kernels for shallow statistic parsing. [sent-287, score-0.248]
84 Kernel methods, syntax and semantics for relational text categorization. [sent-291, score-0.042]
85 Convolution kernels on constituent, dependency and sequential structures for relation extraction. [sent-297, score-0.495]
86 Discovering relations between named entities from a large raw corpus using tree similarity-based clustering. [sent-324, score-0.427]
87 A composite kernel to extract relations between entities with both flat and structured features. [sent-328, score-0.513]
wordName wordTfidf (topN-words)
[('yago', 0.428), ('wikipedia', 0.282), ('ds', 0.266), ('relation', 0.258), ('freebase', 0.257), ('relations', 0.186), ('hoffmann', 0.175), ('kernels', 0.173), ('entities', 0.167), ('distant', 0.153), ('re', 0.139), ('kernel', 0.132), ('infobox', 0.125), ('nguyen', 0.113), ('numerical', 0.111), ('supervision', 0.111), ('dates', 0.107), ('moschitti', 0.103), ('culotta', 0.103), ('sorensen', 0.1), ('alessandro', 0.091), ('mintz', 0.089), ('zelenko', 0.089), ('repositories', 0.086), ('convolution', 0.075), ('bunescu', 0.069), ('ii', 0.068), ('banko', 0.068), ('barcelona', 0.063), ('extraction', 0.062), ('supposed', 0.062), ('kp', 0.06), ('metaweb', 0.054), ('cristianini', 0.054), ('tk', 0.053), ('spain', 0.052), ('attributes', 0.052), ('articles', 0.052), ('ace', 0.051), ('csk', 0.05), ('entity', 0.047), ('documents', 0.044), ('percent', 0.044), ('constituent', 0.043), ('hasegawa', 0.043), ('suchanek', 0.043), ('relational', 0.042), ('zhang', 0.042), ('giuseppe', 0.041), ('agichtein', 0.041), ('supervised', 0.04), ('instances', 0.04), ('scan', 0.04), ('named', 0.039), ('facts', 0.039), ('doddington', 0.038), ('drawbacks', 0.038), ('satisfactory', 0.038), ('guodong', 0.038), ('razvan', 0.038), ('extractors', 0.037), ('page', 0.036), ('extractor', 0.036), ('tree', 0.035), ('riedel', 0.035), ('structures', 0.034), ('extracting', 0.034), ('mooney', 0.034), ('jian', 0.032), ('external', 0.032), ('polynomial', 0.031), ('weakly', 0.031), ('recognizer', 0.031), ('world', 0.031), ('president', 0.031), ('reliable', 0.03), ('article', 0.03), ('dependency', 0.03), ('carried', 0.03), ('rt', 0.029), ('realistic', 0.029), ('millions', 0.029), ('applicable', 0.028), ('retrieve', 0.028), ('connecting', 0.028), ('extract', 0.028), ('potentially', 0.027), ('discovering', 0.027), ('wind', 0.027), ('asg', 0.027), ('constituted', 0.027), ('semi', 0.027), ('meaningfully', 0.027), ('chitt', 0.027), ('congle', 0.027), ('danmei', 0.027), ('duffy', 0.027), ('interdependencies', 0.027), ('monetary', 0.027), ('nello', 0.027)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000002 114 acl-2011-End-to-End Relation Extraction Using Distant Supervision from External Semantic Repositories
Author: Truc Vien T. Nguyen ; Alessandro Moschitti
Abstract: In this paper, we extend distant supervision (DS) based on Wikipedia for Relation Extraction (RE) by considering (i) relations defined in external repositories, e.g. YAGO, and (ii) any subset of Wikipedia documents. We show that training data constituted by sentences containing pairs of named entities in target relations is enough to produce reliable supervision. Our experiments with state-of-the-art relation extraction models, trained on the above data, show a meaningful F1 of 74.29% on a manually annotated test set: this highly improves the state-of-art in RE using DS. Additionally, our end-to-end experiments demonstrated that our extractors can be applied to any general text document.
2 0.24157053 190 acl-2011-Knowledge-Based Weak Supervision for Information Extraction of Overlapping Relations
Author: Raphael Hoffmann ; Congle Zhang ; Xiao Ling ; Luke Zettlemoyer ; Daniel S. Weld
Abstract: Information extraction (IE) holds the promise of generating a large-scale knowledge base from the Web’s natural language text. Knowledge-based weak supervision, using structured data to heuristically label a training corpus, works towards this goal by enabling the automated learning of a potentially unbounded number of relation extractors. Recently, researchers have developed multiinstance learning algorithms to combat the noisy training data that can come from heuristic labeling, but their models assume relations are disjoint — for example they cannot extract the pair Founded ( Jobs Apple ) and CEO-o f ( Jobs Apple ) . , , This paper presents a novel approach for multi-instance learning with overlapping relations that combines a sentence-level extrac- , tion model with a simple, corpus-level component for aggregating the individual facts. We apply our model to learn extractors for NY Times text using weak supervision from Freebase. Experiments show that the approach runs quickly and yields surprising gains in accuracy, at both the aggregate and sentence level.
3 0.22542123 170 acl-2011-In-domain Relation Discovery with Meta-constraints via Posterior Regularization
Author: Harr Chen ; Edward Benson ; Tahira Naseem ; Regina Barzilay
Abstract: We present a novel approach to discovering relations and their instantiations from a collection of documents in a single domain. Our approach learns relation types by exploiting meta-constraints that characterize the general qualities of a good relation in any domain. These constraints state that instances of a single relation should exhibit regularities at multiple levels of linguistic structure, including lexicography, syntax, and document-level context. We capture these regularities via the structure of our probabilistic model as well as a set of declaratively-specified constraints enforced during posterior inference. Across two domains our approach successfully recovers hidden relation structure, comparable to or outperforming previous state-of-the-art approaches. Furthermore, we find that a small , set of constraints is applicable across the domains, and that using domain-specific constraints can further improve performance. 1
4 0.21060084 277 acl-2011-Semi-supervised Relation Extraction with Large-scale Word Clustering
Author: Ang Sun ; Ralph Grishman ; Satoshi Sekine
Abstract: We present a simple semi-supervised relation extraction system with large-scale word clustering. We focus on systematically exploring the effectiveness of different cluster-based features. We also propose several statistical methods for selecting clusters at an appropriate level of granularity. When training on different sizes of data, our semi-supervised approach consistently outperformed a state-of-the-art supervised baseline system. 1
5 0.17805812 128 acl-2011-Exploring Entity Relations for Named Entity Disambiguation
Author: Danuta Ploch
Abstract: Named entity disambiguation is the task of linking an entity mention in a text to the correct real-world referent predefined in a knowledge base, and is a crucial subtask in many areas like information retrieval or topic detection and tracking. Named entity disambiguation is challenging because entity mentions can be ambiguous and an entity can be referenced by different surface forms. We present an approach that exploits Wikipedia relations between entities co-occurring with the ambiguous form to derive a range of novel features for classifying candidate referents. We find that our features improve disambiguation results significantly over a strong popularity baseline, and are especially suitable for recognizing entities not contained in the knowledge base. Our system achieves state-of-the-art results on the TAC-KBP 2009 dataset.
6 0.16746159 86 acl-2011-Coreference for Learning to Extract Relations: Yes Virginia, Coreference Matters
7 0.14050518 337 acl-2011-Wikipedia Revision Toolkit: Efficiently Accessing Wikipedias Edit History
8 0.13992317 191 acl-2011-Knowledge Base Population: Successful Approaches and Challenges
9 0.13469885 286 acl-2011-Social Network Extraction from Texts: A Thesis Proposal
10 0.13467579 126 acl-2011-Exploiting Syntactico-Semantic Structures for Relation Extraction
11 0.12703799 262 acl-2011-Relation Guided Bootstrapping of Semantic Lexicons
12 0.12552406 196 acl-2011-Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models
13 0.12143553 213 acl-2011-Local and Global Algorithms for Disambiguation to Wikipedia
14 0.10410496 285 acl-2011-Simple supervised document geolocation with geodesic grids
15 0.099883772 85 acl-2011-Coreference Resolution with World Knowledge
16 0.094412565 12 acl-2011-A Generative Entity-Mention Model for Linking Entities with Knowledge Base
17 0.08669319 283 acl-2011-Simple English Wikipedia: A New Text Simplification Task
18 0.086483747 334 acl-2011-Which Noun Phrases Denote Which Concepts?
19 0.084170774 117 acl-2011-Entity Set Expansion using Topic information
20 0.083710991 131 acl-2011-Extracting Opinion Expressions and Their Polarities - Exploration of Pipelines and Joint Models
topicId topicWeight
[(0, 0.187), (1, 0.081), (2, -0.185), (3, 0.029), (4, 0.121), (5, 0.009), (6, 0.009), (7, -0.08), (8, -0.249), (9, -0.013), (10, 0.083), (11, -0.004), (12, -0.033), (13, -0.072), (14, 0.062), (15, -0.038), (16, 0.047), (17, -0.219), (18, 0.004), (19, -0.079), (20, -0.014), (21, -0.023), (22, 0.0), (23, -0.103), (24, 0.095), (25, -0.067), (26, 0.134), (27, 0.023), (28, 0.181), (29, 0.042), (30, -0.098), (31, 0.074), (32, 0.057), (33, 0.018), (34, 0.015), (35, -0.0), (36, -0.075), (37, 0.025), (38, 0.021), (39, -0.03), (40, -0.03), (41, 0.042), (42, 0.12), (43, -0.048), (44, -0.038), (45, 0.002), (46, -0.037), (47, -0.025), (48, 0.067), (49, -0.102)]
simIndex simValue paperId paperTitle
same-paper 1 0.97281516 114 acl-2011-End-to-End Relation Extraction Using Distant Supervision from External Semantic Repositories
Author: Truc Vien T. Nguyen ; Alessandro Moschitti
Abstract: In this paper, we extend distant supervision (DS) based on Wikipedia for Relation Extraction (RE) by considering (i) relations defined in external repositories, e.g. YAGO, and (ii) any subset of Wikipedia documents. We show that training data constituted by sentences containing pairs of named entities in target relations is enough to produce reliable supervision. Our experiments with state-of-the-art relation extraction models, trained on the above data, show a meaningful F1 of 74.29% on a manually annotated test set: this highly improves the state-of-art in RE using DS. Additionally, our end-to-end experiments demonstrated that our extractors can be applied to any general text document.
2 0.80744201 190 acl-2011-Knowledge-Based Weak Supervision for Information Extraction of Overlapping Relations
Author: Raphael Hoffmann ; Congle Zhang ; Xiao Ling ; Luke Zettlemoyer ; Daniel S. Weld
Abstract: Information extraction (IE) holds the promise of generating a large-scale knowledge base from the Web’s natural language text. Knowledge-based weak supervision, using structured data to heuristically label a training corpus, works towards this goal by enabling the automated learning of a potentially unbounded number of relation extractors. Recently, researchers have developed multiinstance learning algorithms to combat the noisy training data that can come from heuristic labeling, but their models assume relations are disjoint — for example they cannot extract the pair Founded ( Jobs Apple ) and CEO-o f ( Jobs Apple ) . , , This paper presents a novel approach for multi-instance learning with overlapping relations that combines a sentence-level extrac- , tion model with a simple, corpus-level component for aggregating the individual facts. We apply our model to learn extractors for NY Times text using weak supervision from Freebase. Experiments show that the approach runs quickly and yields surprising gains in accuracy, at both the aggregate and sentence level.
3 0.73928565 277 acl-2011-Semi-supervised Relation Extraction with Large-scale Word Clustering
Author: Ang Sun ; Ralph Grishman ; Satoshi Sekine
Abstract: We present a simple semi-supervised relation extraction system with large-scale word clustering. We focus on systematically exploring the effectiveness of different cluster-based features. We also propose several statistical methods for selecting clusters at an appropriate level of granularity. When training on different sizes of data, our semi-supervised approach consistently outperformed a state-of-the-art supervised baseline system. 1
4 0.71864563 170 acl-2011-In-domain Relation Discovery with Meta-constraints via Posterior Regularization
Author: Harr Chen ; Edward Benson ; Tahira Naseem ; Regina Barzilay
Abstract: We present a novel approach to discovering relations and their instantiations from a collection of documents in a single domain. Our approach learns relation types by exploiting meta-constraints that characterize the general qualities of a good relation in any domain. These constraints state that instances of a single relation should exhibit regularities at multiple levels of linguistic structure, including lexicography, syntax, and document-level context. We capture these regularities via the structure of our probabilistic model as well as a set of declaratively-specified constraints enforced during posterior inference. Across two domains our approach successfully recovers hidden relation structure, comparable to or outperforming previous state-of-the-art approaches. Furthermore, we find that a small , set of constraints is applicable across the domains, and that using domain-specific constraints can further improve performance. 1
5 0.69601905 262 acl-2011-Relation Guided Bootstrapping of Semantic Lexicons
Author: Tara McIntosh ; Lars Yencken ; James R. Curran ; Timothy Baldwin
Abstract: State-of-the-art bootstrapping systems rely on expert-crafted semantic constraints such as negative categories to reduce semantic drift. Unfortunately, their use introduces a substantial amount of supervised knowledge. We present the Relation Guided Bootstrapping (RGB) algorithm, which simultaneously extracts lexicons and open relationships to guide lexicon growth and reduce semantic drift. This removes the necessity for manually crafting category and relationship constraints, and manually generating negative categories.
6 0.6882022 86 acl-2011-Coreference for Learning to Extract Relations: Yes Virginia, Coreference Matters
7 0.67975694 40 acl-2011-An Error Analysis of Relation Extraction in Social Media Documents
8 0.65855163 126 acl-2011-Exploiting Syntactico-Semantic Structures for Relation Extraction
9 0.65410596 322 acl-2011-Unsupervised Learning of Semantic Relation Composition
10 0.62314636 213 acl-2011-Local and Global Algorithms for Disambiguation to Wikipedia
11 0.59695351 337 acl-2011-Wikipedia Revision Toolkit: Efficiently Accessing Wikipedias Edit History
12 0.5726347 128 acl-2011-Exploring Entity Relations for Named Entity Disambiguation
13 0.5656395 191 acl-2011-Knowledge Base Population: Successful Approaches and Challenges
14 0.53367764 195 acl-2011-Language of Vandalism: Improving Wikipedia Vandalism Detection via Stylometric Analysis
15 0.50140196 291 acl-2011-SystemT: A Declarative Information Extraction System
16 0.4851715 196 acl-2011-Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models
17 0.46277711 222 acl-2011-Model-Portability Experiments for Textual Temporal Analysis
18 0.45834687 12 acl-2011-A Generative Entity-Mention Model for Linking Entities with Knowledge Base
19 0.44493341 294 acl-2011-Temporal Evaluation
20 0.4401361 285 acl-2011-Simple supervised document geolocation with geodesic grids
topicId topicWeight
[(5, 0.023), (9, 0.282), (17, 0.041), (26, 0.021), (31, 0.013), (37, 0.086), (39, 0.069), (41, 0.079), (55, 0.019), (59, 0.064), (72, 0.038), (91, 0.04), (96, 0.134), (97, 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 0.78781241 114 acl-2011-End-to-End Relation Extraction Using Distant Supervision from External Semantic Repositories
Author: Truc Vien T. Nguyen ; Alessandro Moschitti
Abstract: In this paper, we extend distant supervision (DS) based on Wikipedia for Relation Extraction (RE) by considering (i) relations defined in external repositories, e.g. YAGO, and (ii) any subset of Wikipedia documents. We show that training data constituted by sentences containing pairs of named entities in target relations is enough to produce reliable supervision. Our experiments with state-of-the-art relation extraction models, trained on the above data, show a meaningful F1 of 74.29% on a manually annotated test set: this highly improves the state-of-art in RE using DS. Additionally, our end-to-end experiments demonstrated that our extractors can be applied to any general text document.
2 0.72727233 231 acl-2011-Nonlinear Evidence Fusion and Propagation for Hyponymy Relation Mining
Author: Fan Zhang ; Shuming Shi ; Jing Liu ; Shuqi Sun ; Chin-Yew Lin
Abstract: This paper focuses on mining the hyponymy (or is-a) relation from large-scale, open-domain web documents. A nonlinear probabilistic model is exploited to model the correlation between sentences in the aggregation of pattern matching results. Based on the model, we design a set of evidence combination and propagation algorithms. These significantly improve the result quality of existing approaches. Experimental results conducted on 500 million web pages and hypernym labels for 300 terms show over 20% performance improvement in terms of P@5, MAP and R-Precision. 1 Introduction1 An important task in text mining is the automatic extraction of entities and their lexical relations; this has wide applications in natural language processing and web search. This paper focuses on mining the hyponymy (or is-a) relation from largescale, open-domain web documents. From the viewpoint of entity classification, the problem is to automatically assign fine-grained class labels to terms. There have been a number of approaches (Hearst 1992; Pantel & Ravichandran 2004; Snow et al., 2005; Durme & Pasca, 2008; Talukdar et al., 2008) to address the problem. These methods typically exploited manually-designed or automatical* This work was performed when Fan Zhang and Shuqi Sun were interns at Microsoft Research Asia 1159 ly-learned patterns (e.g., “NP such as NP”, “NP like NP”, “NP is a NP”). Although some degree of success has been achieved with these efforts, the results are still far from perfect, in terms of both recall and precision. As will be demonstrated in this paper, even by processing a large corpus of 500 million web pages with the most popular patterns, we are not able to extract correct labels for many (especially rare) entities. Even for popular terms, incorrect results often appear in their label lists. The basic philosophy in existing hyponymy extraction approaches (and also many other textmining methods) is counting: count the number of supporting sentences. Here a supporting sentence of a term-label pair is a sentence from which the pair can be extracted via an extraction pattern. We demonstrate that the specific way of counting has a great impact on result quality, and that the state-ofthe-art counting methods are not optimal. Specifically, we examine the problem from the viewpoint of probabilistic evidence combination and find that the probabilistic assumption behind simple counting is the statistical independence between the observations of supporting sentences. By assuming a positive correlation between supporting sentence observations and adopting properly designed nonlinear combination functions, the results precision can be improved. It is hard to extract correct labels for rare terms from a web corpus due to the data sparseness problem. To address this issue, we propose an evidence propagation algorithm motivated by the observation that similar terms tend to share common hypernyms. For example, if we already know that 1) Helsinki and Tampere are cities, and 2) Porvoo is similar to Helsinki and Tampere, then Porvoo is ProceedingPso orftla thned 4,9 Otrhe Agonnn,u Jauln Mee 1e9t-i2ng4, o 2f0 t1h1e. A ?c s 2o0ci1a1ti Aonss foocria Ctioomnp fourta Ctioomnaplu Ltaintigouniaslti Lcisn,g puaigsetsic 1s159–1168, very likely also a city. This intuition, however, does not mean that the labels of a term can always be transferred to its similar terms. For example, Mount Vesuvius and Kilimanjaro are volcanoes and Lhotse is similar to them, but Lhotse is not a volcano. Therefore we should be very conservative and careful in hypernym propagation. In our propagation algorithm, we first construct some pseudo supporting sentences for a term from the supporting sentences of its similar terms. Then we calculate label scores for terms by performing nonlinear evidence combination based on the (pseudo and real) supporting sentences. Such a nonlinear propagation algorithm is demonstrated to perform better than linear propagation. Experimental results on a publicly available collection of 500 million web pages with hypernym labels annotated for 300 terms show that our nonlinear evidence fusion and propagation significantly improve the precision and coverage of the extracted hyponymy data. This is one of the technologies adopted in our semantic search and min- ing system NeedleSeek2. In the next section, we discuss major related efforts and how they differ from our work. Section 3 is a brief description of the baseline approach. The probabilistic evidence combination model that we exploited is introduced in Section 4. Our main approach is illustrated in Section 5. Section 6 shows our experimental settings and results. Finally, Section 7 concludes this paper. 2 Related Work Existing efforts for hyponymy relation extraction have been conducted upon various types of data sources, including plain-text corpora (Hearst 1992; Pantel & Ravichandran, 2004; Snow et al., 2005; Snow et al., 2006; Banko, et al., 2007; Durme & Pasca, 2008; Talukdar et al., 2008), semistructured web pages (Cafarella et al., 2008; Shinzato & Torisawa, 2004), web search results (Geraci et al., 2006; Kozareva et al., 2008; Wang & Cohen, 2009), and query logs (Pasca 2010). Our target for optimization in this paper is the approaches that use lexico-syntactic patterns to extract hyponymy relations from plain-text corpora. Our future work will study the application of the proposed algorithms on other types of approaches. 2 http://research.microsoft.com/en-us/projects/needleseek/ or http://needleseek.msra.cn/ 1160 The probabilistic evidence combination model that we exploit here was first proposed in (Shi et al., 2009), for combining the page in-link evidence in building a nonlinear static-rank computation algorithm. We applied it to the hyponymy extraction problem because the model takes the dependency between supporting sentences into consideration and the resultant evidence fusion formulas are quite simple. In (Snow et al., 2006), a probabilistic model was adopted to combine evidence from heterogeneous relationships to jointly optimize the relationships. The independence of evidence was assumed in their model. In comparison, we show that better results will be obtained if the evidence correlation is modeled appropriately. Our evidence propagation is basically about using term similarity information to help instance labeling. There have been several approaches which improve hyponymy extraction with instance clusters built by distributional similarity. In (Pantel & Ravichandran, 2004), labels were assigned to the committee (i.e., representative members) of a semantic class and used as the hypernyms of the whole class. Labels generated by their approach tend to be rather coarse-grained, excluding the possibility of a term having its private labels (considering the case that one meaning of a term is not covered by the input semantic classes). In contrast to their method, our label scoring and ranking approach is applied to every single term rather than a semantic class. In addition, we also compute label scores in a nonlinear way, which improves results quality. In Snow et al. (2005), a supervised approach was proposed to improve hypernym classification using coordinate terms. In comparison, our approach is unsupervised. Durme & Pasca (2008) cleaned the set of instance-label pairs with a TF*IDF like method, by exploiting clusters of semantically related phrases. The core idea is to keep a term-label pair (T, L) only if the number of terms having the label L in the term T’s cluster is above a threshold and if L is not the label of too many clusters (otherwise the pair will be discarded). In contrast, we are able to add new (high-quality) labels for a term with our evidence propagation method. On the other hand, low quality labels get smaller score gains via propagation and are ranked lower. Label propagation is performed in (Talukdar et al., 2008; Talukdar & Pereira, 2010) based on multiple instance-label graphs. Term similarity information was not used in their approach. Most existing work tends to utilize small-scale or private corpora, whereas the corpus that we used is publicly available and much larger than most of the existing work. We published our term sets (refer to Section 6. 1) and their corresponding user judgments so researchers working on similar topics can reproduce our results. H eTIsaryApst-eI {N aP nLd(|{iso,}ra (eNisn|.wuPcgalhsu|edwa.gs(e)r{PN|baiPent,c}lg*ur){nd(ai n|dg)o {r}N P,L}* IsA-II NP (is|are|was|were|being) {the, those} NPL IsA-III NP (is|are|was|were|being) {another, any} NPL Table 1. Patterns adopted in this paper (NP: named phrase representing an entity; NPL: label) 3 Preliminaries The problem addressed in this paper is corpusbased is-a relation mining: extracting hypernyms (as labels) for entities from a large-scale, open- domain document corpus. The desired output is a mapping from terms to their corresponding hypernyms, which can naturally be represented as a weighted bipartite graph (term-label graph). Typically we are only interested in top labels of a term in the graph. Following existing efforts, we adopt patternmatching as a basic way of extracting hypernymy/hyponymy relations. Two types of patterns (refer to Table 1) are employed, including the popular “Hearst patterns” (Hearst, 1992) and the IsA patterns which are exploited less frequently in existing hyponym mining efforts. One or more termlabel pairs can be extracted if a pattern matches a sentence. In the baseline approach, the weight of an edge TL (from term T to hypernym label L) in the term-label graph is computed as, ( ) w(TL) ( ) (3.1) where m is the number of times the pair (T, L) is extracted from the corpus, DF(L) is the number of in-links of L in the graph, N is total number of terms in the graph, and IDF means the “inverse document frequency”. A term can only keep its top-k neighbors (according to the edge weight) in the graph as its final labels. 1161 Our pattern matching algorithm implemented in this paper uses part-of-speech (POS) tagging information, without adopting a parser or a chunker. The noun phrase boundaries (for terms and labels) are determined by a manually designed POS tag list. 4 Probabilistic Label-Scoring Model Here we model the hyponymy extraction problem from the probability theory point of view, aiming at estimating the score of a term-label pair (i.e., the score of a label w.r.t. a term) with probabilistic evidence combination. The model was studied in (Shi et al., 2009) to combine the page in-link evidence in building a nonlinear static-rank computation algorithm. We represent the score of a term-label pair by the probability of the label being a correct hypernym of the term, and define the following events, AT,L: Label L is a hypernym of term T (the abbreviated form A is used in this paper unless it is ambiguous). Ei: The observation that (T, L) is extracted from a sentence Si via pattern matching (i.e., Si is a sup- porting sentence of the pair). Assuming that we already know m supporting sentences (S1~Sm), our problem is to compute P(A|E1,E2,..,Em), the posterior probability that L is a hypernym of term T, given evidence E1~Em. Formally, we need to find a function f to satisfy, P(A|E1,… ,Em) = f(P(A), P(A|E1)… P(A|Em) ) (4.1) … … …, For simplicity, we first consider the case of m=2. The case of m>2 is quite similar. We start from the simple case of independent supporting sentences. That is, ( ) ( ) ( ) ( ) ( )( ) By applying Bayes rule, we get, ( (4.2) (4.3) ) ( ( ) )() ( ( ) ) ( ) ( () ) ( ) ( ) (4.4) ( ) ( ) ( ) Then define ( ) ( ( )) ( ( )) ( ( )) Here G(A|E) represents the log-probability-gain of A given E, with the meaning of the gain in the log-probability value of A after the evidence E is observed (or known). It is a measure of the impact of evidence E to the probability of event A. With the definition of G(A|E), Formula 4.4 can be transformed to, ( ) ( ) ( ) (4.5) Therefore, if E1 and E2 are independent, the logprobability-gain of A given both pieces of evidence will exactly be the sum of the gains of A given every single piece of evidence respectively. It is easy to prove (by following a similar procedure) that the above Formula holds for the case of m>2, as long as the pieces of evidence are mutually independent. Therefore for a term-label pair with m mutually independent supporting sentences, if we set every gain G(A|Ei) to be a constant value g, the posterior gain score of the pair will be ∑ If the value g is the IDF of label L, the posterior gain will be, . G(AT,L|E1… ,Em) ∑ ( ) ( ) (4.6) This is exactly the Formula 3. 1. By this way, we provide a probabilistic explanation of scoring the candidate labels for a term via simple counting. … TRaAb:le(2.A/E)Rv(ide)ncHd065epa.9r81sn7t-dIec10ys.7Ae3-1I0timEa2o:8nH0Is.4feA2oa3-r78I0sitna- pattern and inter-pattern supporting sentences In the above analysis, we assume the statistical independence of the supporting sentence observations, which may not hold in reality. Intuitively, if we already know one supporting sentence S1 for a term-label pair (T, L), then we have more chance to find another supporting sentence than if we do not know S1. The reason is that, before we find S1, we have to estimate the probability with the chance of discovering a supporting sentence for a random term-label pair. The probability is quite low because most term-label pairs do not have hyponymy relations. Once we have observed S1, however, the chance of (T, L) having a hyponymy relation in1162 creases. Therefore the chance of observing another supporting sentence becomes larger than before. Table 2 shows the rough estimation of ( ( ) ( ) ) (denoted as RA), ( ( ) ( ) ) (denoted as R), and their ratios. The statistics are obtained by performing maximal likelihood estimation (MLE) upon our corpus and a random selection of term-label pairs from our term sets (see Section 6. 1) together with their top labels3. The data verifies our analysis about the correlation between E1 and E2 (note that R=1 means independent). In addition, it can be seen that the conditional independence assumption of Formula 4.3 does not hold (because RA>1). It is hence necessary to consider the correlation between supporting sentences in the model. The estimation of Table 2 also indicates that, ( ( ) ( )) ( ( ) ( ) ) (4.7) By following a similar procedure as above, with Formulas 4.2 and 4.3 replaced by 4.7, we have, ( ) ( ) ( ) (4.8) This formula indicates that when the supporting sentences are positively correlated, the posterior score of label L w.r.t. term T (given both the sen- tences) is smaller than the sum of the gains caused by one sentence only. In the extreme case that sentence S2 fully depends on E1 (i.e. P(E2|E1)=1), it is easy to prove that ( ) ( ) It is reasonable, since event E2 does not bring in more information than E1. Formula 4.8 cannot be used directly for computing the posterior gain. What we really need is a function h satisfying () ( ( ) ( )) (4.9) and ( )∑ (4.10) Shi et al. (2009) discussed other constraints to h and suggested the following nonlinear functions, ( ) ( ∑ ( )) (4. 11) 3 RA is estimated from the labels judged as “Good”; whereas the estimation of R is from all judged labels. ( ) √ ∑ (p>1) (4.12) In the next section, we use the above two h func- tions as basic building blocks to compute label scores for terms. 5 Our Approach Multiple types of patterns (Table 1) can be adopted to extract term-label pairs. For two supporting sentences the correlation between them may depend on whether they correspond to the same pattern. In Section 5. 1, our nonlinear evidence fusion formulas are constructed by making specific assumptions about the correlation between intra-pattern supporting sentences and inter-pattern ones. Then in Section 5.2, we introduce our evidence propagation technique in which the evidence of a (T, L) pair is propagated to the terms similar to T. 5.1 Nonlinear evidence fusion For a term-label pair (T, L), assuming K patterns are used for hyponymy extraction and the supporting sentences discovered with pattern iare, (5.1) where mi is the number of supporting sentences corresponding to pattern i. Also assume the gain score of Si,j is xi,j, i.e., xi,j=G(A|Si,j). Generally speaking, supporting sentences corre- sponding to the same pattern typically have a higher correlation than the sentences corresponding to different patterns. This can be verified by the data in Table-2. By ignoring the inter-pattern correlations, we make the following simplified assumption: Assumption: Supporting sentences corresponding to the same pattern are correlated, while those of different patterns are independent. According to this assumption, our label-scoring function is, ( ) ∑ ( ) (5.2) In the simple case that ( ) , if the h function of Formula 4. 12 is adopted, then, ( ) (∑ √ ) ( ) (5.3) 1163 We use an example to illustrate the above formula. Example: For term T and label L1, assume the numbers of the supporting sentences corresponding to the six pattern types in Table 1 are (4, 4, 4, 4, 4, 4), which means the number of supporting sentences discovered by each pattern type is 4. Also assume the supporting-sentence-count vector of label L2 is (25, 0, 0, 0, 0, 0). If we use Formula 5.3 to compute the scores of L1 and L2, we can have the following (ignoring IDF for simplicity), Score(L1) Score(L2) One the other hand, if we simply count the total number of supporting sentences, the score of L2 will be larger. The rationale implied in the formula is: For a given term T, the labels supported by multiple types of patterns tend to be more reliable than those supported by a single pattern type, if they have the same number of supporting sentences. √ ; √ 5.2 Evidence propagation According to the evidence fusion algorithm described above, in order to extract term labels reliably, it is desirable to have many supporting sentences of different types. This is a big challenge for rare terms, due to their low frequency in sentences (and even lower frequency in supporting sentences because not all occurrences can be covered by patterns). With evidence propagation, we aim at discovering more supporting sentences for terms (especially rare terms). Evidence propagation is motivated by the following two observations: (I) Similar entities or coordinate terms tend to share some common hypernyms. (II) Large term similarity graphs are able to be built efficiently with state-of-the-art techniques (Agirre et al., 2009; Pantel et al., 2009; Shi et al., 2010). With the graphs, we can obtain the similarity between two terms without their hypernyms being available. The first observation motivates us to “borrow” the supporting sentences from other terms as auxiliary evidence of the term. The second observation means that new information is brought with the state-of-the-art term similarity graphs (in addition to the term-label information discovered with the patterns of Table 1). Our evidence propagation algorithm contains two phases. In phase I, some pseudo supporting sentences are constructed for a term from the supporting sentences of its neighbors in the similarity graph. Then we calculate the label scores for terms based on their (pseudo and real) supporting sentences. Phase I: For every supporting sentence S and every similar term T1 of the term T, add a pseudo supporting sentence S1 for T1, with the gain score, ( ) ( ( ) ) (5.5) where is the propagation factor, and ( ) is the term similarity function taking values in [0, 1]. The formula reasonably assumes that the gain score of the pseudo supporting sentence depends on the gain score of the original real supporting sentence, the similarity between the two terms, and the propagation factor. Phase II: The nonlinear evidence combination formulas in the previous subsection are adopted to combine the evidence of pseudo supporting sentences. Term similarity graphs can be obtained by distributional similarity or patterns (Agirre et al., 2009; Pantel et al., 2009; Shi et al., 2010). We call the first type of graph DS and the second type PB. DS approaches are based on the distributional hypothesis (Harris, 1985), which says that terms appearing in analogous contexts tend to be similar. In a DS approach, a term is represented by a feature vector, with each feature corresponding to a context in which the term appears. The similarity between two terms is computed as the similarity between their corresponding feature vectors. In PB approaches, a list of carefully-designed (or automatically learned) patterns is exploited and applied to a text collection, with the hypothesis that the terms extracted by applying each of the patterns to a specific piece of text tend to be similar. Two categories of patterns have been studied in the literature (Heast 1992; Pasca 2004; Kozareva et al., 2008; Zhang et al., 2009): sentence lexical patterns, and HTML tag patterns. An example of sentence lexical patterns is “T {, T} *{,} (and|or) T”. HTML tag patterns include HTML tables, drop-down lists, and other tag repeat patterns. In this paper, we generate the DS and PB graphs by adopting the best-performed methods studied in (Shi et al., 2010). We will compare, by experiments, the propagation performance of utilizing the two categories 1164 of graphs, and also investigate the performance of utilizing both graphs for evidence propagation. 6 Experiments 6.1 Experimental setup Corpus We adopt a publicly available dataset in our experiments: ClueWeb094. This is a very large dataset collected by Carnegie Mellon University in early 2009 and has been used by several tracks of the Text Retrieval Conference (TREC)5. The whole dataset consists of 1.04 billion web pages in ten languages while only those in English, about 500 million pages, are used in our experiments. The reason for selecting such a dataset is twofold: First, it is a corpus large enough for conducting webscale experiments and getting meaningful results. Second, since it is publicly available, it is possible for other researchers to reproduce the experiments in this paper. Term sets Approaches are evaluated by using two sets of selected terms: Wiki200, and Ext100. For every term in the term sets, each approach generates a list of hypernym labels, which are manually judged by human annotators. Wiki200 is constructed by first randomly selecting 400 Wikipedia6 titles as our candidate terms, with the probability of a title T being selected to be ( ( )), where F(T) is the frequency of T in our data corpus. The reason of adopting such a probability formula is to balance popular terms and rare ones in our term set. Then 200 terms are manually selected from the 400 candidate terms, with the principle of maximizing the diversity of terms in terms of length (i.e., number of words) and type (person, location, organization, software, movie, song, animal, plant, etc.). Wiki200 is further divided into two subsets: Wiki100H and Wiki100L, containing respectively the 100 high-frequency and lowfrequency terms. Ext100 is built by first selecting 200 non-Wikipedia-title terms at random from the term-label graph generated by the baseline approach (Formula 3. 1), then manually selecting 100 terms. Some sample terms in the term sets are listed in Table 3. 4 http://boston.lti.cs.cmu.edu/Data/clueweb09/ 5 http://trec.nist.gov/ 6 http://www.wikipedia.org/ Annotation For each term in the term set, the top-5 results (i.e., hypernym labels) of various methods are mixed and judged by human annotators. Each annotator assigns each result item a judgment of “Good”, “Fair” or “Bad”. The annotators do not know the method by which a result item is generated. Six annotators participated in the labeling with a rough speed of 15 minutes per term. We also encourage the annotators to add new good results which are not discovered by any method. The term sets and their corresponding user anno- tations are available for download at the following links (dataset ID=data.queryset.semcat01): http://research.microsoft.com/en-us/projects/needleseek/ http://needleseek.msra.cn/datasets/ Evaluation We adopt the following metrics to evaluate the hypernym list of a term generated by each method. The evaluation score on a term set is the average over all the terms. Precision@k: The percentage of relevant (good or fair) labels in the top-k results (labels judged as “Fair” are counted as 0.5) Recall@k: The ratio of relevant labels in the topk results to the total number of relevant labels R-Precision: Precision@R where R is the total number of labels judged as “Good” Mean average precision (MAP): The average of precision values at the positions of all good or fair results Before annotation and evaluation, the hypernym list generated by each method for each term is preprocessed to remove duplicate items. Two hypernyms are called duplicate items if they share the same head word (e.g., “military conflict” and “conflict”). For duplicate hypernyms, only the first (i.e., the highest ranked one) in the list is kept. The goal with such a preprocessing step is to partially con- sider results diversity in evaluation and to make a more meaningful comparison among different methods. Consider two hypernym lists for “subway”: List-1 : restaurant; chain restaurant; worldwide chain restaurant; franchise; restaurant franchise… List-2: restaurant; franchise; transportation; company; fast food… There are more detailed hypernyms in the first list about “subway” as a restaurant or a franchise; while the second list covers a broader range of meanings for the term. It is hard to say which is better (without considering the upper-layer applications). With this preprocessing step, we keep our focus on short hypernyms rather than detailed ones. … … … … evidence fusion methods (Term sets: Wiki200 and Wiki100H; p=2 for PNorm) 6.2 Experimental results We first compare the evaluation results of different evidence fusion methods mentioned in Section 4.1. In Table 4, Linear means that Formula 3. 1 is used to calculate label scores, whereas Log and PNorm represent our nonlinear approach with Formulas 4. 11 and 4. 12 being utilized. The performance improvement numbers shown in the table are based on the linear version; and the upward pointing arrows indicate relative percentage improvement over the baseline. From the table, we can see that the nonlinear methods outperform the linear ones on the Wiki200 term set. It is interesting to note that the performance improvement is more significant on Wiki100H, the set of high frequency terms. By examining the labels and supporting sentences for the terms in each term set, we find that for many low-frequency terms (in Wiki100L), there are only a few supporting sentences (corresponding 1165 to one or two patterns). So the scores computed by various fusion algorithms tend to be similar. In contrast, more supporting sentences can be discov- ered for high-frequency terms. Much information is contained in the sentences about the hypernyms of the high-frequency terms, but the linear function of Formula 3.1 fails to make effective use of it. The two nonlinear methods achieve better performance by appropriately modeling the dependency between supporting sentences and computing the log-probability gain in a better way. The comparison of the linear and nonlinear methods on the Ext100 term set is shown in Table 5. Please note that the terms in Ext100 do not appear in Wikipedia titles. Thanks to the scale of the data corpus we are using, even the baseline approach achieves reasonably good performance. Please note that the terms (refer to Table 3) we are using are “harder” than those adopted for evaluation in many existing papers. Again, the results quality is improved with the nonlinear methods, although the performance improvement is not big due to the reason that most terms in Ext100 are rare. Please note that the recall (R@1, R@5) in this paper is pseudo-recall, i.e., we treat the number of known relevant (Good or Fair) results as the total number of relevant ones. MTPLeNainotbhgrlmed5.M012P35A8e96r%5P4f0orRm-.aP40%2rn9ce 50P7o.@625m10p%5 ari0Ps.4o@07%n25 amR307o.@41n526g%0 vaRr0i.3o@8% u5s evidence fusion methods (Term set: Ext100; p=2 for PNorm) The parameter p in the PNorm method is related to the degree of correlations among supporting sentences. The linear method of Formula 3. 1 corresponds to the special case of p=1 ; while p= represents the case that other supporting sentences are fully correlated to the supporting sentence with the maximal log-probability gain. Figure 1 shows that, for most of the term sets, the best performance is obtained for [2.0, 4.0]. The reason may be that the sentence correlations are better estimated with p values in this range. Figure 1. Performance curves of PNorm with different parameter values (Measure: MAP) The experimental results of evidence propagation are shown in Table 6. The methods for comparison are, Base: The linear function without propagation. NL: Nonlinear evidence fusion (PNorm with p=2) without propagation. LP: Linear propagation, i.e., the linear function is used to combine the evidence of pseudo supporting sentences. NLP: Nonlinear propagation where PNorm (p=2) is used to combine the pseudo supporting sentences. NL+NLP: The nonlinear method is used to combine both supporting sentences and pseudo supporting sentences. Wiki200; Similarity graph: PB; Nonlinear formula: PNorm) In this paper, we generate the DS (distributional similarity) and PB (pattern-based) graphs by adopting the best-performed methods studied in (Shi et al., 2010). The performance improvement numbers (indicated by the upward pointing arrows) shown in tables 6~9 are relative percentage improvement 1166 over the base approach (i.e., linear function without propagation). The values of parameter are set to maximize the MAP values. Several observations can be made from Table 6. First, no performance improvement can be obtained with the linear propagation method (LP), while the nonlinear propagation algorithm (NLP) works quite well in improving both precision and recall. The results demonstrate the high correlation between pseudo supporting sentences and the great potential of using term similarity to improve hypernymy extraction. The second observation is that the NL+NLP approach achieves a much larger performance improvement than NL and NLP. Similar results (omitted due to space limitation) can be observed on the Ext100 term set. evidence propagation (Term set: Wiki200; Nonlinear formula: Log) evidence propagation (Term set: Wiki100L) Now let us study whether it is possible to combine the PB and DS graphs to obtain better results. As shown in Tables 7, 8, and 9 (for term sets Wiki200, Wiki100L, and Ext100 respectively, using the Log formula for fusion and propagation), utilizing both graphs really yields additional performance gains. We explain this by the fact that the information in the two term similarity graphs tends 1167 to be complimentary. The performance improvement over Wiki100L is especially remarkable. This is reasonable because rare terms do not have adequate information in their supporting sentences due to data sparseness. As a result, they benefit the most from the pseudo supporting sentences propagated with the similarity graphs. evidence propagation (Term set: Ext100) 7 Conclusion We demonstrated that the way of aggregating supporting sentences has considerable impact on results quality of the hyponym extraction task using lexico-syntactic patterns, and the widely-used counting method is not optimal. We applied a series of nonlinear evidence fusion formulas to the problem and saw noticeable performance improvement. The data quality is improved further with the combination of nonlinear evidence fusion and evidence propagation. We also introduced a new evaluation corpus with annotated hypernym labels for 300 terms, which were shared with the research community. Acknowledgments We would like to thank Matt Callcut for reading through the paper. Thanks to the annotators for their efforts in judging the hypernym labels. Thanks to Yueguo Chen, Siyu Lei, and the anonymous reviewers for their helpful comments and suggestions. The first author is partially supported by the NSF of China (60903028,61070014), and Key Projects in the Tianjin Science and Technology Pillar Program. References E. Agirre, E. Alfonseca, K. Hall, J. Kravalova, M. Pasca, and A. Soroa. 2009. A Study on Similarity and Relatedness Using Distributional and WordNet-based Approaches. In Proc. of NAACL-HLT’2009. M. Banko, M.J. Cafarella, S. Soderland, M. Broadhead, and O. Etzioni. 2007. Open Information Extraction from the Web. In Proc. of IJCAI’2007. M. Cafarella, A. Halevy, D. Wang, E. Wu, and Y. Zhang. 2008. WebTables: Exploring the Power of Tables on the Web. In Proceedings of the 34th Conference on Very Large Data Bases (VLDB’2008), pages 538–549, Auckland, New Zealand. B. Van Durme and M. Pasca. 2008. Finding cars, goddesses and enzymes: Parametrizable acquisition of labeled instances for open-domain information extraction. Twenty-Third AAAI Conference on Artificial Intelligence. F. Geraci, M. Pellegrini, M. Maggini, and F. Sebastiani. 2006. Cluster Generation and Cluster Labelling for Web Snippets: A Fast and Accurate Hierarchical Solution. In Proceedings of the 13th Conference on String Processing and Information Retrieval (SPIRE’2006), pages 25–36, Glasgow, Scotland. Z. S. Harris. 1985. Distributional Structure. The Philosophy of Linguistics. New York: Oxford University Press. M. Hearst. 1992. Automatic Acquisition of Hyponyms from Large Text Corpora. In Fourteenth International Conference on Computational Linguistics, Nantes, France. Z. Kozareva, E. Riloff, E.H. Hovy. 2008. Semantic Class Learning from the Web with Hyponym Pattern Linkage Graphs. In Proc. of ACL'2008. P. Pantel, E. Crestan, A. Borkovsky, A.-M. Popescu and V. Vyas. 2009. Web-Scale Distributional Similarity and Entity Set Expansion. EMNLP’2009. Singapore. P. Pantel and D. Ravichandran. 2004. Automatically Labeling Semantic Classes. In Proc. of the 2004 Human Language Technology Conference (HLTNAACL’2004), 321–328. M. Pasca. 2004. Acquisition of Categorized Named Entities for Web Search. In Proc. of CIKM’2004. M. Pasca. 2010. The Role of Queries in Ranking Labeled Instances Extracted from Text. In Proc. of COLING’2010, Beijing, China. S. Shi, B. Lu, Y. Ma, and J.-R. Wen. 2009. Nonlinear Static-Rank Computation. In Proc. of CIKM’2009, Kong Kong. 1168 S. Shi, H. Zhang, X. Yuan, J.-R. Wen. 2010. Corpusbased Semantic Class Mining: Distributional vs. Pattern-Based Approaches. In Proc. of COLING’2010, Beijing, China. K. Shinzato and K. Torisawa. 2004. Acquiring Hyponymy Relations from Web Documents. In Proc. of the 2004 Human Language (HLT-NAACL’2004). Technology Conference R. Snow, D. Jurafsky, and A. Y. Ng. 2005. Learning Syntactic Patterns for Automatic Hypernym Discovery. In Proceedings of the 19th Conference on Neural Information Processing Systems. R. Snow, D. Jurafsky, and A. Y. Ng. 2006. Semantic Taxonomy Induction from Heterogenous Evidence. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics (COLING-ACL-06), 801–808. P. P. Talukdar and F. Pereira. 2010. Experiments in Graph-based Semi-Supervised Learning Methods for Class-Instance Acquisition. In 48th Annual Meeting of the Association for Computational Linguistics (ACL’2010). P. P. Talukdar, J. Reisinger, M. Pasca, D. Ravichandran, R. Bhagat, and F. Pereira. 2008. Weakly-Supervised Acquisition of Labeled Class Instances using Graph Random Walks. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing (EMNLP’2008), pages 581–589. R.C. Wang. W.W. Cohen. Automatic Set Instance Extraction using the Web. In Proc. of the 47th Annual Meeting of the Association for Computational Lin- guistics (ACL-IJCNLP’2009), gapore. pages 441–449, Sin- H. Zhang, M. Zhu, S. Shi, and J.-R. Wen. 2009. Employing Topic Models for Pattern-based Semantic Class Discovery. In Proc. of the 47th Annual Meeting of the Association for Computational Linguistics (ACL-IJCNLP’2009), pages 441–449, Singapore.
3 0.69295037 277 acl-2011-Semi-supervised Relation Extraction with Large-scale Word Clustering
Author: Ang Sun ; Ralph Grishman ; Satoshi Sekine
Abstract: We present a simple semi-supervised relation extraction system with large-scale word clustering. We focus on systematically exploring the effectiveness of different cluster-based features. We also propose several statistical methods for selecting clusters at an appropriate level of granularity. When training on different sizes of data, our semi-supervised approach consistently outperformed a state-of-the-art supervised baseline system. 1
4 0.67360789 257 acl-2011-Question Detection in Spoken Conversations Using Textual Conversations
Author: Anna Margolis ; Mari Ostendorf
Abstract: We investigate the use of textual Internet conversations for detecting questions in spoken conversations. We compare the text-trained model with models trained on manuallylabeled, domain-matched spoken utterances with and without prosodic features. Overall, the text-trained model achieves over 90% of the performance (measured in Area Under the Curve) of the domain-matched model including prosodic features, but does especially poorly on declarative questions. We describe efforts to utilize unlabeled spoken utterances and prosodic features via domain adaptation.
5 0.60964352 190 acl-2011-Knowledge-Based Weak Supervision for Information Extraction of Overlapping Relations
Author: Raphael Hoffmann ; Congle Zhang ; Xiao Ling ; Luke Zettlemoyer ; Daniel S. Weld
Abstract: Information extraction (IE) holds the promise of generating a large-scale knowledge base from the Web’s natural language text. Knowledge-based weak supervision, using structured data to heuristically label a training corpus, works towards this goal by enabling the automated learning of a potentially unbounded number of relation extractors. Recently, researchers have developed multiinstance learning algorithms to combat the noisy training data that can come from heuristic labeling, but their models assume relations are disjoint — for example they cannot extract the pair Founded ( Jobs Apple ) and CEO-o f ( Jobs Apple ) . , , This paper presents a novel approach for multi-instance learning with overlapping relations that combines a sentence-level extrac- , tion model with a simple, corpus-level component for aggregating the individual facts. We apply our model to learn extractors for NY Times text using weak supervision from Freebase. Experiments show that the approach runs quickly and yields surprising gains in accuracy, at both the aggregate and sentence level.
6 0.5899781 86 acl-2011-Coreference for Learning to Extract Relations: Yes Virginia, Coreference Matters
7 0.58985877 324 acl-2011-Unsupervised Semantic Role Induction via Split-Merge Clustering
8 0.58499008 269 acl-2011-Scaling up Automatic Cross-Lingual Semantic Role Annotation
9 0.58220381 126 acl-2011-Exploiting Syntactico-Semantic Structures for Relation Extraction
10 0.58069295 58 acl-2011-Beam-Width Prediction for Efficient Context-Free Parsing
11 0.57873118 65 acl-2011-Can Document Selection Help Semi-supervised Learning? A Case Study On Event Extraction
12 0.57783908 164 acl-2011-Improving Arabic Dependency Parsing with Form-based and Functional Morphological Features
13 0.57743913 3 acl-2011-A Bayesian Model for Unsupervised Semantic Parsing
14 0.57731211 137 acl-2011-Fine-Grained Class Label Markup of Search Queries
15 0.57524294 128 acl-2011-Exploring Entity Relations for Named Entity Disambiguation
16 0.57519603 170 acl-2011-In-domain Relation Discovery with Meta-constraints via Posterior Regularization
17 0.57338953 196 acl-2011-Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models
18 0.57335651 178 acl-2011-Interactive Topic Modeling
19 0.57323241 209 acl-2011-Lexically-Triggered Hidden Markov Models for Clinical Document Coding
20 0.57188451 40 acl-2011-An Error Analysis of Relation Extraction in Social Media Documents