acl acl2011 acl2011-277 knowledge-graph by maker-knowledge-mining

277 acl-2011-Semi-supervised Relation Extraction with Large-scale Word Clustering

Source: pdf

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

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Semi-supervised Relation Extraction with Large-scale Word Clustering Ang Sun Ralph Grishman Satoshi Sekine Computer Science Department New York University { asun ,gri shman , se kine } @ cs . [sent-1, score-0.101]

2 edu Abstract We present a simple semi-supervised relation extraction system with large-scale word clustering. [sent-3, score-0.637]

3 We focus on systematically exploring the effectiveness of different cluster-based features. [sent-4, score-0.088]

4 We also propose several statistical methods for selecting clusters at an appropriate level of granularity. [sent-5, score-0.326]

5 When training on different sizes of data, our semi-supervised approach consistently outperformed a state-of-the-art supervised baseline system. [sent-6, score-0.055]

6 1 Introduction Relation extraction is an important information extraction task in natural language processing (NLP), with many practical applications. [sent-7, score-0.256]

7 The goal of relation extraction is to detect and characterize semantic relations between pairs of entities in text. [sent-8, score-0.672]

8 For example, a relation extraction system needs to be able to extract an Employment relation between the entities US soldier and US in the phrase US soldier. [sent-9, score-1.413]

9 Current supervised approaches for tackling this problem, in general, fall into two categories: feature based and kernel based. [sent-10, score-0.247]

10 Given an entity pair and a sentence containing the pair, both approaches usually start with multiple level analyses of the sentence such as tokenization, partial or full syntactic parsing, and dependency parsing. [sent-11, score-0.159]

11 Then the feature based method explicitly extracts a variety of lexical, syntactic and semantic 521 features for statistical learning, either generative or discriminative (Miller et al. [sent-12, score-0.189]

12 In contrast, the kernel based method does not explicitly extract features; it designs kernel functions over the structured sentence representations (sequence, dependency or parse tree) to capture the similarities between different relation instances (Zelenko et al. [sent-17, score-0.827]

13 Both lines of work depend on effective features, either explicitly or implicitly. [sent-22, score-0.04]

14 The performance of a supervised relation extraction system is usually degraded by the sparsity of lexical features. [sent-23, score-0.743]

15 For example, unless the example US soldier has previously been seen in the training data, it would be difficult for both the feature based and the kernel based systems to detect whether there is an Employment relation or not. [sent-24, score-0.998]

16 Because the syntactic feature of the phrase US soldier is simply a noun-noun compound which is quite general, the words in it are crucial for extracting the relation. [sent-25, score-0.368]

17 This motivates our work to use word clusters as additional features for relation extraction. [sent-26, score-0.863]

18 The assumption is that even if the word soldier may never have been seen in the annotated Employment relation instances, other words which share the same cluster membership with soldier such as president and ambassador may have been observed in the Employment instances. [sent-27, score-1.409]

19 The absence of lexical features can be compensated by Proce dinPgosrt olafn thde, 4 O9rtehg Aon ,n Ju anle M 1e9e-2tin4g, 2 o0f1 t1h. [sent-28, score-0.125]

20 Ac s2s0o1ci1a Atiosnso fcoirat Cio nm foprut Caotimonpaulta Lti nognuails Lti cnsg,u piasgteics 521–529, the cluster features. [sent-30, score-0.145]

21 Moreover, word clusters may implicitly correspond to different relation classes. [sent-31, score-0.834]

22 For example, the cluster of president may be related to the Employment relation as in US president while the cluster of businessman may be related to the Affiliation relation as in US businessman. [sent-32, score-1.468]

23 The main contributions of this paper are: we explore the cluster-based features in a systematic way and propose several statistical methods for selecting effective clusters. [sent-33, score-0.12]

24 We study the impact of the size of training data on cluster features and analyze the performance improvements through an extensive experimental study. [sent-34, score-0.183]

25 The rest of this paper is organized as follows: Section 2 presents related work and Section 3 provides the background of the relation extraction task and the word clustering algorithm. [sent-35, score-0.763]

26 Section 4 describes in detail a state-of-the-art supervised baseline system. [sent-36, score-0.055]

27 Section 5 describes the clusterbased features and the cluster selection methods. [sent-37, score-0.231]

28 2 Related Work The idea of using word clusters as features in discriminative learning was pioneered by Miller et al. [sent-39, score-0.4]

29 (2004), who augmented name tagging training data with hierarchical word clusters generated by the Brown clustering algorithm (Brown et al. [sent-40, score-0.637]

30 They used different thresholds to cut the word hierarchy to obtain clusters of various granularities for feature decoding. [sent-42, score-0.542]

31 Though all of them used the same hierarchical word clustering algorithm for the task of name tagging and reported improvements, we noticed that the clusters used by Miller et al. [sent-45, score-0.593]

32 To our knowledge, there has not been work on selecting clusters in a principled way. [sent-48, score-0.326]

33 We move a step further to explore several methods in choosing effective clusters. [sent-49, score-0.078]

34 A second difference between this work and the above ones is that we utilize word clusters in the task of relation extraction which is very different from sequence labeling tasks such as name tagging and chunking. [sent-50, score-1.045]

35 (2005) and Chan and Roth (2010) used word clusters in relation extraction, they shared the same limitation as the above approaches in choosing clusters. [sent-52, score-0.831]

36 (2005) chose clusters of different granularities and Chan and Roth (2010) simply used a single threshold for cutting the word hierarchy. [sent-54, score-0.437]

37 (2005) only augmented the predicate (typically a verb or a noun of the most importance in a relation in their definition) with word clusters while Chan and Roth (2010) performed this for any lexical feature consisting of a single word. [sent-56, score-0.946]

38 In this paper, we systematically explore the effectiveness of adding word clusters to different lexical features. [sent-57, score-0.484]

39 1 Background Relation Extraction One of the well defined relation extraction tasks is the Automatic Content Extraction1 (ACE) program sponsored by the U. [sent-59, score-0.65]

40 ACE 2004 defined 7 major entity types: PER (Person), ORG (Organization), FAC (Facility), GPE (Geo-Political Entity: countries, cities, etc. [sent-62, score-0.149]

41 An entity has three types of mention: NAM (proper name), NOM (nominal) or PRO (pronoun). [sent-64, score-0.156]

42 A relation was defined over a pair of entity mentions within a single sentence. [sent-65, score-0.73]

43 The 7 major relation types with examples are shown in Table 1. [sent-66, score-0.571]

44 Following most of the previous work, this paper only focuses on relation extraction of major types. [sent-68, score-0.648]

45 Given a relation instance x  (s , mi mj ) , where mi and mj are a pair of mentions and s is the sentence containing the pair, the goal is to learn a function which maps the instance x to a type c, where c is one of the 7 defined relation types or the type Nil (no relation exists). [sent-69, score-1.996]

46 There are two commonly used learning paradigms for relation extraction: Flat: This strategy performs relation detection and classification at the same time. [sent-70, score-0.99]

47 One multi-class classifier is trained to discriminate among the 7 relation types plus the Nil type. [sent-71, score-0.607]

48 Hierarchical: This one separates relation detection from relation classification. [sent-72, score-0.988]

49 edu/ace/ classifier is trained first to distinguish between relation instances and non-relation instances. [sent-80, score-0.585]

50 This can be done by grouping all the instances of the 7 relation types into a positive class and the instances of Nil into a negative class. [sent-81, score-0.655]

51 Then the thresholded output of this binary classifier is used as training data for learning a multi-class classifier for the 7 relation types (Bunescu and Mooney, 2005b). [sent-82, score-0.706]

52 AEcbmhxpnuearoslfimroencsiwepdnalshtenoGmenprtase nompaltenoyr Table 1: ACE relation types and examples from the annotation guideline 2 . [sent-85, score-0.575]

53 2 Brown Word Clustering The Brown algorithm is a hierarchical clustering algorithm which initially assigns each word to its own cluster and then repeatedly merges the two clusters which cause the least loss in average mutual information between adjacent clusters based on bigram statistics. [sent-89, score-0.983]

54 By tracing the pairwise merging steps, one can obtain a word hierarchy which can be represented as a binary tree. [sent-90, score-0.192]

55 A word can be compactly represented as a bit string by following the path from the root to itself in the tree, assigning a 0 for each left branch, and a 1 for each right branch. [sent-91, score-0.159]

56 A high branch may correspond to more general concepts while the lower branches it includes might correspond to more specific ones. [sent-93, score-0.229]

57 (1992) described an efficient implementation based on a greedy algorithm which initially assigned only the most frequent words into distinct clusters. [sent-95, score-0.052]

58 It is worth pointing out that in this implementation each word occupies a leaf in the hierarchy, but each leaf might contain more than one word as can be seen from Table 2. [sent-96, score-0.309]

59 The lengths of the bit strings also vary among different words. [sent-97, score-0.078]

60 PDF 523 Table 2: An example of words and their bit string representations obtained in this paper. [sent-102, score-0.112]

61 4 Feature Based Relation Extraction Given a pair of entity mentions  mi mj  and the sentence containing the pair, a feature based system extracts a feature vector v which contains diverse lexical, syntactic and semantic features. [sent-104, score-0.618]

62 The goal is to learn a function which can estimate the conditional probability p( c c| |v ) , the probability of a relation type c given the feature vector v . [sent-105, score-0.545]

63 The m, type with the highest probability will be output as the class label for the mention pair. [sent-106, score-0.044]

64 We now describe a supervised baseline system with a very large set of features and its learning strategy. [sent-107, score-0.093]

65 1 Baseline Feature Set We first adopted the full feature set from Zhou et al. [sent-109, score-0.069]

66 For space reasons, we only show the lexical features as in Table 3 and refer the reader to the paper for the rest of the features. [sent-111, score-0.079]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('relation', 0.476), ('soldier', 0.299), ('clusters', 0.283), ('employment', 0.242), ('boschee', 0.211), ('ace', 0.196), ('cluster', 0.145), ('extraction', 0.128), ('mj', 0.124), ('roth', 0.12), ('nil', 0.119), ('branch', 0.112), ('entity', 0.105), ('bunescu', 0.1), ('chan', 0.1), ('mooney', 0.098), ('grishman', 0.096), ('mentions', 0.095), ('clustering', 0.093), ('miller', 0.09), ('president', 0.089), ('kernel', 0.085), ('turian', 0.083), ('brown', 0.083), ('name', 0.082), ('granularities', 0.08), ('bit', 0.078), ('hierarchy', 0.077), ('ratinov', 0.07), ('feature', 0.069), ('zhou', 0.067), ('instances', 0.064), ('leaf', 0.06), ('mi', 0.06), ('hierarchical', 0.059), ('supervised', 0.055), ('systematically', 0.054), ('pair', 0.054), ('kine', 0.053), ('occupies', 0.053), ('thresholded', 0.053), ('initially', 0.052), ('types', 0.051), ('vehicle', 0.048), ('affiliation', 0.048), ('shman', 0.048), ('businessman', 0.048), ('compactly', 0.048), ('guideline', 0.048), ('weapon', 0.048), ('clusterbased', 0.048), ('nom', 0.046), ('tracing', 0.046), ('gpe', 0.046), ('pioneered', 0.046), ('compensated', 0.046), ('kambhatla', 0.046), ('qian', 0.046), ('sponsored', 0.046), ('classifier', 0.045), ('mention', 0.044), ('augmented', 0.044), ('major', 0.044), ('facility', 0.043), ('designs', 0.043), ('degraded', 0.043), ('zelenko', 0.043), ('selecting', 0.043), ('tagging', 0.043), ('correspond', 0.042), ('extracts', 0.042), ('cutting', 0.041), ('lexical', 0.041), ('explicitly', 0.04), ('choosing', 0.039), ('us', 0.039), ('explore', 0.039), ('features', 0.038), ('paradigms', 0.038), ('tackling', 0.038), ('cities', 0.037), ('ang', 0.037), ('pro', 0.036), ('loc', 0.036), ('separates', 0.036), ('binary', 0.036), ('seen', 0.035), ('merges', 0.035), ('discriminate', 0.035), ('pointing', 0.035), ('countries', 0.034), ('entities', 0.034), ('detect', 0.034), ('representations', 0.034), ('effectiveness', 0.034), ('branches', 0.033), ('motivates', 0.033), ('membership', 0.033), ('background', 0.033), ('word', 0.033)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 277 acl-2011-Semi-supervised Relation Extraction with Large-scale Word Clustering

Author: Ang Sun ; Ralph Grishman ; Satoshi Sekine

2 0.28835607 86 acl-2011-Coreference for Learning to Extract Relations: Yes Virginia, Coreference Matters

Author: Ryan Gabbard ; Marjorie Freedman ; Ralph Weischedel

Abstract: As an alternative to requiring substantial supervised relation training data, many have explored bootstrapping relation extraction from a few seed examples. Most techniques assume that the examples are based on easily spotted anchors, e.g., names or dates. Sentences in a corpus which contain the anchors are then used to induce alternative ways of expressing the relation. We explore whether coreference can improve the learning process. That is, if the algorithm considered examples such as his sister, would accuracy be improved? With coreference, we see on average a 2-fold increase in F-Score. Despite using potentially errorful machine coreference, we see significant increase in recall on all relations. Precision increases in four cases and decreases in six.

3 0.28412136 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.26847172 126 acl-2011-Exploiting Syntactico-Semantic Structures for Relation Extraction

Author: Yee Seng Chan ; Dan Roth

Abstract: In this paper, we observe that there exists a second dimension to the relation extraction (RE) problem that is orthogonal to the relation type dimension. We show that most of these second dimensional structures are relatively constrained and not difficult to identify. We propose a novel algorithmic approach to RE that starts by first identifying these structures and then, within these, identifying the semantic type of the relation. In the real RE problem where relation arguments need to be identified, exploiting these structures also allows reducing pipelined propagated errors. We show that this RE framework provides significant improvement in RE performance.

5 0.21060084 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.

6 0.18486603 324 acl-2011-Unsupervised Semantic Role Induction via Split-Merge Clustering

7 0.16330005 12 acl-2011-A Generative Entity-Mention Model for Linking Entities with Knowledge Base

8 0.14538036 262 acl-2011-Relation Guided Bootstrapping of Semantic Lexicons

9 0.13168772 196 acl-2011-Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models

10 0.13160732 65 acl-2011-Can Document Selection Help Semi-supervised Learning? A Case Study On Event Extraction

11 0.1310987 39 acl-2011-An Ensemble Model that Combines Syntactic and Semantic Clustering for Discriminative Dependency Parsing

12 0.12979904 190 acl-2011-Knowledge-Based Weak Supervision for Information Extraction of Overlapping Relations

13 0.12691125 40 acl-2011-An Error Analysis of Relation Extraction in Social Media Documents

14 0.12610576 328 acl-2011-Using Cross-Entity Inference to Improve Event Extraction

15 0.12250817 3 acl-2011-A Bayesian Model for Unsupervised Semantic Parsing

16 0.11022758 293 acl-2011-Template-Based Information Extraction without the Templates

17 0.10621174 29 acl-2011-A Word-Class Approach to Labeling PSCFG Rules for Machine Translation

18 0.10496747 128 acl-2011-Exploring Entity Relations for Named Entity Disambiguation

19 0.10198296 137 acl-2011-Fine-Grained Class Label Markup of Search Queries

20 0.097902991 191 acl-2011-Knowledge Base Population: Successful Approaches and Challenges

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.214), (1, 0.075), (2, -0.227), (3, -0.013), (4, 0.167), (5, 0.045), (6, -0.001), (7, -0.069), (8, -0.224), (9, 0.032), (10, 0.107), (11, -0.062), (12, -0.037), (13, -0.01), (14, -0.003), (15, -0.082), (16, -0.156), (17, -0.169), (18, 0.04), (19, 0.087), (20, -0.145), (21, -0.023), (22, 0.083), (23, -0.076), (24, -0.017), (25, -0.043), (26, 0.156), (27, 0.017), (28, 0.116), (29, -0.018), (30, -0.131), (31, 0.027), (32, 0.006), (33, 0.001), (34, -0.049), (35, -0.008), (36, -0.026), (37, -0.002), (38, -0.018), (39, 0.043), (40, -0.055), (41, 0.053), (42, 0.068), (43, 0.019), (44, 0.036), (45, -0.026), (46, 0.037), (47, 0.029), (48, -0.022), (49, 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97791499 277 acl-2011-Semi-supervised Relation Extraction with Large-scale Word Clustering

Author: Ang Sun ; Ralph Grishman ; Satoshi Sekine

2 0.86361355 126 acl-2011-Exploiting Syntactico-Semantic Structures for Relation Extraction

Author: Yee Seng Chan ; Dan Roth

3 0.85313857 86 acl-2011-Coreference for Learning to Extract Relations: Yes Virginia, Coreference Matters

Author: Ryan Gabbard ; Marjorie Freedman ; Ralph Weischedel

4 0.8390435 170 acl-2011-In-domain Relation Discovery with Meta-constraints via Posterior Regularization

Author: Harr Chen ; Edward Benson ; Tahira Naseem ; Regina Barzilay

5 0.79775906 114 acl-2011-End-to-End Relation Extraction Using Distant Supervision from External Semantic Repositories

Author: Truc Vien T. Nguyen ; Alessandro Moschitti

6 0.79563218 40 acl-2011-An Error Analysis of Relation Extraction in Social Media Documents

7 0.79346818 190 acl-2011-Knowledge-Based Weak Supervision for Information Extraction of Overlapping Relations

8 0.74313098 262 acl-2011-Relation Guided Bootstrapping of Semantic Lexicons

9 0.66939712 322 acl-2011-Unsupervised Learning of Semantic Relation Composition

10 0.60664314 293 acl-2011-Template-Based Information Extraction without the Templates

11 0.56786895 196 acl-2011-Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models

12 0.50759631 334 acl-2011-Which Noun Phrases Denote Which Concepts?

13 0.49616832 324 acl-2011-Unsupervised Semantic Role Induction via Split-Merge Clustering

14 0.48748568 231 acl-2011-Nonlinear Evidence Fusion and Propagation for Hyponymy Relation Mining

15 0.46474487 291 acl-2011-SystemT: A Declarative Information Extraction System

16 0.4543364 191 acl-2011-Knowledge Base Population: Successful Approaches and Challenges

17 0.44988924 3 acl-2011-A Bayesian Model for Unsupervised Semantic Parsing

18 0.44438285 319 acl-2011-Unsupervised Decomposition of a Document into Authorial Components

19 0.44090423 85 acl-2011-Coreference Resolution with World Knowledge

20 0.44038403 121 acl-2011-Event Discovery in Social Media Feeds

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(5, 0.024), (9, 0.214), (17, 0.079), (26, 0.024), (37, 0.121), (39, 0.049), (41, 0.096), (55, 0.037), (59, 0.041), (72, 0.034), (91, 0.063), (96, 0.137), (97, 0.014)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.85819364 114 acl-2011-End-to-End Relation Extraction Using Distant Supervision from External Semantic Repositories

Author: Truc Vien T. Nguyen ; Alessandro Moschitti

same-paper 2 0.8198542 277 acl-2011-Semi-supervised Relation Extraction with Large-scale Word Clustering

Author: Ang Sun ; Ralph Grishman ; Satoshi Sekine

3 0.81033194 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 TL (from term T to hypernym label L) in the term-label graph is computed as, ( ) w(TL) ( ) (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.

4 0.78389525 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.73793852 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.73276854 126 acl-2011-Exploiting Syntactico-Semantic Structures for Relation Extraction

7 0.72708952 65 acl-2011-Can Document Selection Help Semi-supervised Learning? A Case Study On Event Extraction

8 0.71646184 86 acl-2011-Coreference for Learning to Extract Relations: Yes Virginia, Coreference Matters

9 0.71560431 324 acl-2011-Unsupervised Semantic Role Induction via Split-Merge Clustering

10 0.71403456 311 acl-2011-Translationese and Its Dialects

11 0.71365237 58 acl-2011-Beam-Width Prediction for Efficient Context-Free Parsing

12 0.71359181 111 acl-2011-Effects of Noun Phrase Bracketing in Dependency Parsing and Machine Translation

13 0.71150625 196 acl-2011-Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models

14 0.70971662 331 acl-2011-Using Large Monolingual and Bilingual Corpora to Improve Coordination Disambiguation

15 0.70889103 209 acl-2011-Lexically-Triggered Hidden Markov Models for Clinical Document Coding

16 0.70786893 119 acl-2011-Evaluating the Impact of Coder Errors on Active Learning

17 0.70662123 246 acl-2011-Piggyback: Using Search Engines for Robust Cross-Domain Named Entity Recognition

18 0.70502818 73 acl-2011-Collective Classification of Congressional Floor-Debate Transcripts

19 0.7038368 36 acl-2011-An Efficient Indexer for Large N-Gram Corpora

20 0.70307076 170 acl-2011-In-domain Relation Discovery with Meta-constraints via Posterior Regularization