emnlp emnlp2011 emnlp2011-145 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Joel Lang ; Mirella Lapata
Abstract: In this paper we present a method for unsupervised semantic role induction which we formalize as a graph partitioning problem. Argument instances of a verb are represented as vertices in a graph whose edge weights quantify their role-semantic similarity. Graph partitioning is realized with an algorithm that iteratively assigns vertices to clusters based on the cluster assignments of neighboring vertices. Our method is algorithmically and conceptually simple, especially with respect to how problem-specific knowledge is incorporated into the model. Experimental results on the CoNLL 2008 benchmark dataset demonstrate that our model is competitive with other unsupervised approaches in terms of F1 whilst attaining significantly higher cluster purity.
Reference: text
sentIndex sentText sentNum sentScore
1 J Lang- 3 @ sms ed ac Abstract In this paper we present a method for unsupervised semantic role induction which we formalize as a graph partitioning problem. [sent-5, score-0.861]
2 Argument instances of a verb are represented as vertices in a graph whose edge weights quantify their role-semantic similarity. [sent-6, score-0.725]
3 Graph partitioning is realized with an algorithm that iteratively assigns vertices to clusters based on the cluster assignments of neighboring vertices. [sent-7, score-0.866]
4 The term is most commonly used to describe the automatic identification and labeling of the semantic roles conveyed by sentential constituents (Gildea and Jurafsky, 2002). [sent-11, score-0.354]
5 Semantic roles describe the semantic relations that hold between a predicate and its arguments (e. [sent-12, score-0.453]
6 , 2005), a broadcoverage human-annotated corpus of semantic roles and their syntactic realizations. [sent-30, score-0.293]
7 (2006)) has sparked the development of great many semantic role labeling systems most of which conceptualize the task as a supervised learning problem and rely on role-annotated data for model training. [sent-37, score-0.379]
8 Most of these systems implement a two-stage architecture consisting of argument identification (determining the arguments of the verbal predicate) and argument classification (labeling these arguments with semantic roles). [sent-38, score-0.992]
9 Current approaches have high performance a system will recall around 81% of the arguments correctly and 95% of those will be assigned a correct semantic role (see M `arquez et al. [sent-45, score-0.478]
10 Our approach formalizes semantic role induction as a graph partitioning problem. [sent-52, score-0.8]
11 Given a verbal predicate, it constructs a weighted graph whose vertices correspond to argument instances of the verb and whose edge weights quantify the similarity between these instances. [sent-53, score-1.107]
12 The graph is partitioned into vertex clusters representing semantic roles using a variant of Chinese Whispers, a graph-clustering algorithm proposed by Biemann (2006). [sent-54, score-0.855]
13 The algorithm iteratively assigns cluster labels to graph vertices by greedily choosing the most common label amongst the neighbors of the vertex being updated. [sent-55, score-0.987]
14 Beyond extending Chinese Whispers to the semantic role induction task, we also show how it can be understood as a type of Gibbs sampling when our graph is interpreted as a Markov random field. [sent-56, score-0.547]
15 1321 2 Related Work Although the bulk of previous work on semantic role labeling has primarily focused on supervised methods (M` arquez et al. [sent-58, score-0.393]
16 Swier and Stevenson (2004) were the first to introduce an unsupervised semantic role labeling system. [sent-63, score-0.401]
17 Their algorithm induces role labels following a boot- strapping scheme where the set of labeled instances is iteratively expanded using a classifier trained on previously labeled instances. [sent-64, score-0.307]
18 , 2000) for identifying the arguments of predicates and making initial role assignments. [sent-66, score-0.388]
19 VerbNet is a manually constructed lexicon of verb classes each of which is explicitly associated with argument realization and semantic role specifications. [sent-67, score-0.589]
20 Subsequent work has focused on unsupervised methods for argument identification and classification. [sent-68, score-0.348]
21 (2009) recognize the arguments of predicates by relying solely on part of speech annotations whereas Abend and Rappoport (2010) distinguish between core and adjunct roles, using an unsupervised parser and part-of-speech tagger. [sent-70, score-0.329]
22 Grenager and Manning (2006) address the role induction problem and propose a directed graphical model which relates a verb, its semantic roles, and their possible syntactic realizations. [sent-71, score-0.471]
23 Latent variables represent the semantic roles of arguments and role induction corresponds to inferring the state of these latent variables. [sent-72, score-0.683]
24 Following up on this work, Lang and Lapata (2010) formulate role induction as the process of detecting alternations and finding a canonical syntactic form for them. [sent-73, score-0.316]
25 More recently, Lang and Lapata (201 1) propose a clustering algorithm which first splits the argument instances of a verb into fine-grained clusters based on syntactic cues and then executes a series of merge steps (mainly) based on lexical cues. [sent-76, score-0.69]
26 The split phase creates a large number of small clusters with high purity but low collocation, i. [sent-77, score-0.436]
27 , while the instances in a particular cluster typically belong to the same role the instances for a particular role are commonly scattered amongst many clusters. [sent-79, score-0.666]
28 The subsequent merge phase conflates clusters with the same role in order to increase collocation. [sent-80, score-0.335]
29 Like Grenager and Manning (2006) and Lang and Lapata (2010; 2011), this paper describes an unsupervised method for semantic role induction, i. [sent-81, score-0.337]
30 Contrary to these previous approaches, we conceptualize role induction in a novel way, as a graph partitioning problem. [sent-84, score-0.747]
31 A wide range of methods exist for finding partitions in graphs (Schaeffer, 2007), besides Chinese Whispers (Biemann, 2006), which could be easily applied to the semantic role induction problem. [sent-87, score-0.361]
32 The basic idea behind label propagation is to represent labeled and unlabeled instances as vertices in an undirected graph with edges whose weights express similarity (and possibly dissimilarity) between the instances. [sent-98, score-0.9]
33 Label information is then propagated between the vertices in such a way that similar instances tend to be assigned the same label. [sent-99, score-0.347]
34 Analogously, Chinese Whispers works by propagating cluster membership information along the edges of a graph, even though the graph does not contain any human-labeled instance vertices. [sent-100, score-0.364]
35 3 Problem Setting We adopt the standard architecture of supervised semantic role labeling systems where argument identi- fication and argument classification are treated separately. [sent-101, score-0.826]
36 Our role labeler is fully unsupervised with respect to both tasks it does not rely on any role annotated data or semantic resources. [sent-102, score-0.521]
37 In common with most semantic role labeling research, we assume that the input is syntactically analyzed in the form of dependency trees. [sent-104, score-0.34]
38 We view argument identification as a syntactic processing step that can be largely undertaken deterministically through structural analysis ofthe dependency tree. [sent-105, score-0.334]
39 Both types of information are incorporated into our model through a similarity function that assigns similarity scores to pairs of argument instances. [sent-108, score-0.511]
40 4 Argument Identification Supervised semantic role labelers often employ a classifier in order to decide for each node in the parse tree whether or not it represents a semantic argument. [sent-114, score-0.368]
41 Nodes classified as arguments are then assigned a semantic role. [sent-115, score-0.294]
42 In the unsupervised setting, we slightly reformulate argument identification as the task of discarding as many non-semantic arguments as possible. [sent-116, score-0.516]
43 This means that the argument identification component does not make a final positive decision for any of the argument candidates; instead, a final decision is only made in the subsequent argument classification stage. [sent-117, score-0.773]
44 These are mainly based on the parts of speech and syntactic relations encountered when traversing a dependency tree from the predicate node to the argument node. [sent-119, score-0.329]
45 When evaluated on its own, the argument identification component obtained 88. [sent-121, score-0.287]
46 5 Argument Classification After identifying likely arguments for each verb, the next step is to infer a label for each argument instance. [sent-124, score-0.511]
47 Since we aim to induce verb-specific roles (see Section 3), we construct an undirected, weighted graph for each verb. [sent-125, score-0.34]
48 Vertices correspond to verb argument instances and edge weights quantify the similarities between them. [sent-126, score-0.563]
49 This argument-instance graph is then partitioned into clusters of vertices representing semantic roles and each argument instance is assigned a label that indicates the cluster it belongs to. [sent-127, score-1.35]
50 In what follows we first describe how the graph is constructed and then provide the details of our graph partitioning algo- rithm. [sent-128, score-0.625]
51 All pairs of vertices with non-zero similarity are connected through edges that are weighted with a similarity score φ(vi, vj). [sent-130, score-0.497]
52 Upon updating the label for a vertex all neighboring vertices propagate their label to the vertex being updated. [sent-131, score-0.981]
53 The score for each label is determined by summing together the weighted votes for that label and the label with the maximal score is chosen. [sent-132, score-0.343]
54 1 Graph Construction For each verb we construct an undirected, weighted graph G = (V, E, φ) with vertices V, edges E, and edge weight function φ as follows. [sent-134, score-0.649]
55 Each argument instance in the corpus that belongs to the verb is added as a vertex. [sent-135, score-0.343]
56 The function φ quantifies the similarity or dissimilarity between instances; positive values indicate that roles are likely to be the same, negative values indicate that roles are likely to differ, and zero values indicate that there is no evidence for either case. [sent-138, score-0.473]
57 Figure 1 shows an example of a graph for a verb with five argument instances (vertices A–E). [sent-143, score-0.593]
58 Edges are drawn between pairs of vertices with non-zero similarity values. [sent-144, score-0.324]
59 For instance, vertex D is connected to vertex A with weight 0. [sent-145, score-0.482]
60 We assume each vertex vi is assigned a label li ∈ {1. [sent-153, score-0.593]
61 Gletive thne eth niusm minbietiral o vertex labeling, Vthe| algorithm proceeds by iteratively updating the label for each vertex. [sent-163, score-0.407]
62 The update is based on the labels of neighboring vertices and reflects their similarity to the vertex being updated. [sent-164, score-0.649]
63 Intuitively, each neighboring vertex votes for the cluster it is currently assigned to, where the strength of the vote is determined by the similarity (i. [sent-165, score-0.533]
64 The label li of vertex vi is thus updated according to the following equation: li← argl∈ m{1a. [sent-168, score-0.559]
65 I nl }o dtheenro words, for each label we compute a score by summing together the weights of edges to neighboring vertices with that label and select the label with the maximal score. [sent-172, score-0.716]
66 The result of the algorithm is a hard partitioning of the given graph, where the number of clusters is determined automatically. [sent-197, score-0.404]
67 4 Argument-Instance Similarity As described earlier, the edge weights in our graph are similarity scores, with positive values indicating similarity and negative values indicating dissimilarity. [sent-206, score-0.516]
68 Specifically, we measure the similarity of argument instances based on three simple and intuitive criteria: (1) whether the instances are lexically similar; (2) whether the instances occur in the same syntactic position; and (3) whether the instances occur in the same frame (i. [sent-208, score-0.771]
69 The same criteria were used in (Lang and Lapata, 2011) and shown effective in quantifying role-semantic similarity between clusters of argument instances. [sent-211, score-0.499]
70 , that two argument instances vi and vj occurring in the same frame cannot have the same semantic role. [sent-215, score-0.932]
71 es whether two argument instances occur in a similar syntactic position. [sent-218, score-0.384]
72 We define syntactic positions through four cues: the relation of the argument head word to its governor, verb voice (active/passive), the linear position of the argument relative to the verb (left/right) and the preposition used for realizing the argument (if any). [sent-219, score-0.916]
73 The averaging procedure used for updating the graph vertices (Equation 2) appears in some form in most label propagation algorithms (see Talukdar (2010) for details). [sent-233, score-0.596]
74 Assuming equal weight for all edges above, label 3 is chosen for the vertex being updated such that the sum of weights of edges crossing the cut is minimal. [sent-237, score-0.52]
75 In the transformed model each vertex corresponds to a random variable over labels and edges are associated with binary potential functions over vertex-pairs. [sent-242, score-0.309]
76 zero and thus connecting all assigning the label with maximal score to vi, we greedily maximize the sum of intra-cluster edge weights while minimizing the sum of inter-cluster edge weights, i. [sent-249, score-0.375]
77 The dataset provides annotations for verbal and nominal predicate-argument constructions, but we only considered the former, following previous work on semantic role labeling (M` arquez et al. [sent-264, score-0.506]
78 Evaluation Metrics For each verb, we determine the extent to which argument instances in the clusters share the same gold standard role (purity) and the extent to which a particular gold standard role is assigned to a single cluster (collocation). [sent-267, score-1.12]
79 More formally, for each group of verb-specific clusters we measure the purity of the clusters as the 1326 percentage of instances belonging to the majority gold class in their respective cluster. [sent-268, score-0.77]
80 Let N denote the total number of instances, Gj the set of instances belonging to the j-th gold class and Ci the set of instances belonging to the i-th cluster. [sent-269, score-0.306]
81 Finally, we use the harmonic mean of purity and collocation as a single measure of clustering quality: F1=C2·COO+·PPUU (8) Model Parameters Recall that our algorithm prioritizes updates with confidence higher than a threshold θ. [sent-273, score-0.584]
82 6402 Table 1: Evaluation of the output of our graph partitioning algorithm compared that assigns arguments to clusters based on their syntactic function. [sent-294, score-0.834]
83 Comparison Models We compared our graph partitioning algorithm against three competitive approaches. [sent-302, score-0.439]
84 The first one assigns argument instances to clusters according to their syntactic function (e. [sent-303, score-0.593]
85 This baseline has been previously used as a point of comparison by other unsupervised semantic role induction systems (Grenager and Manning, 2006; Lang and Lapata, 2010) and shown difficult to outperform. [sent-306, score-0.422]
86 Our graph partitioning method uses identical cues for as- sessing role-semantic similarity as the method described in Lang and Lapata (201 1). [sent-312, score-0.576]
87 We report cluster purity (PU), collocation (CO) and their harmonic mean (F1) for the baseline (Syntactic Function), our two previous models (the Latent Logistic classifier and Split-Merge) and the graph partitioning algorithm on four datasets. [sent-314, score-1.0]
88 These result from the combination of automatic parses with automatically identified arguments (auto/auto), gold parses with 5This is the number of gold standard roles. [sent-315, score-0.358]
89 673k Table 2: Clustering results for individual verbs on the auto/auto dataset with our graph partitioning algorithm and the syntactic function baseline; the scores were taken from a single run. [sent-340, score-0.561]
90 automatic arguments (gold/auto), automatic parses with gold arguments (auto/gold) and gold parses with gold arguments (gold/gold). [sent-341, score-0.754]
91 This was necessary in order to ensure that the results of our randomized graph partitioning algorithm are stable. [sent-343, score-0.471]
92 When considering F1 in conjunction with purity and collocation, we observe that Graph Partitioning can attain higher purity than the comparison models by trading off collocation. [sent-351, score-0.57]
93 If we were to hand label the clusters output by our system, purity would correspond to the quality of the resulting labeling, while collocation would determine the labeling effort. [sent-352, score-0.733]
94 The relationship is illustrated more explicitly in Figure 3, which plots purity against the average number of clusters per verb on the auto/auto dataset. [sent-353, score-0.506]
95 32 points below the average and the worst purity was 0. [sent-360, score-0.316]
96 This is accompanied by a decreasing tradeoff ratio between collocation and purity: at this stage decreasing purity by one point increases collocation by roughly one point, whereas in earlier iterations a decrease of purity by one point goes together with several points increase in collocation. [sent-364, score-0.867]
97 Figure 4 shows the complete learning curve of our graph partitioning method on the auto/auto dataset (F1 is plotted against the number of iterations). [sent-366, score-0.485]
98 — 8 — Conclusions In this paper we described an unsupervised method for semantic role induction, in which argumentinstance graphs are partitioned into clusters representing semantic roles. [sent-381, score-0.611]
99 The approach is conceptually and algorithmically simple and novel in its for- malization of role induction as a graph partitioning problem. [sent-382, score-0.742]
100 Secondly, the approach is general and amenable to other graph partitioning algorithms and relates to well-known graph-based semi-supervised learning methods. [sent-387, score-0.47]
wordName wordTfidf (topN-words)
[('vj', 0.285), ('purity', 0.285), ('partitioning', 0.253), ('argument', 0.243), ('vertex', 0.241), ('vertices', 0.219), ('vi', 0.218), ('lang', 0.187), ('graph', 0.186), ('role', 0.184), ('arguments', 0.168), ('whispers', 0.158), ('roles', 0.154), ('clusters', 0.151), ('collocation', 0.133), ('lapata', 0.118), ('cluster', 0.11), ('similarity', 0.105), ('label', 0.1), ('instances', 0.094), ('semantic', 0.092), ('induction', 0.085), ('edge', 0.077), ('propbank', 0.072), ('verb', 0.07), ('edges', 0.068), ('labeling', 0.064), ('biemann', 0.062), ('abend', 0.062), ('unsupervised', 0.061), ('gold', 0.06), ('surdeanu', 0.058), ('broke', 0.057), ('propagation', 0.054), ('arquez', 0.053), ('clustering', 0.053), ('grenager', 0.051), ('axis', 0.048), ('syntactic', 0.047), ('dataset', 0.046), ('gj', 0.046), ('identification', 0.044), ('min', 0.043), ('weights', 0.043), ('talukdar', 0.043), ('ball', 0.043), ('maximal', 0.043), ('neighboring', 0.043), ('updates', 0.042), ('update', 0.041), ('alexandrescu', 0.039), ('boykov', 0.039), ('conceptualize', 0.039), ('haffari', 0.039), ('klapaftis', 0.039), ('melli', 0.039), ('prioritization', 0.039), ('schaeffer', 0.039), ('subramanya', 0.039), ('predicate', 0.039), ('chinese', 0.038), ('neighbors', 0.038), ('confidence', 0.038), ('updating', 0.037), ('predicates', 0.036), ('quantify', 0.036), ('parses', 0.035), ('pu', 0.035), ('greedily', 0.035), ('verbal', 0.034), ('conll', 0.034), ('swier', 0.034), ('algorithmically', 0.034), ('pradhan', 0.034), ('assigned', 0.034), ('harmonic', 0.033), ('annotations', 0.033), ('window', 0.033), ('graphical', 0.032), ('cues', 0.032), ('realized', 0.032), ('randomized', 0.032), ('points', 0.031), ('relates', 0.031), ('undirected', 0.031), ('partitioned', 0.031), ('dissimilarity', 0.031), ('fso', 0.031), ('ruppenhofer', 0.031), ('wainwright', 0.031), ('kipper', 0.031), ('governor', 0.031), ('adjunct', 0.031), ('urstenau', 0.031), ('belongs', 0.03), ('gildea', 0.03), ('iteratively', 0.029), ('function', 0.029), ('assigns', 0.029), ('belonging', 0.029)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000012 145 emnlp-2011-Unsupervised Semantic Role Induction with Graph Partitioning
Author: Joel Lang ; Mirella Lapata
Abstract: In this paper we present a method for unsupervised semantic role induction which we formalize as a graph partitioning problem. Argument instances of a verb are represented as vertices in a graph whose edge weights quantify their role-semantic similarity. Graph partitioning is realized with an algorithm that iteratively assigns vertices to clusters based on the cluster assignments of neighboring vertices. Our method is algorithmically and conceptually simple, especially with respect to how problem-specific knowledge is incorporated into the model. Experimental results on the CoNLL 2008 benchmark dataset demonstrate that our model is competitive with other unsupervised approaches in terms of F1 whilst attaining significantly higher cluster purity.
2 0.18638131 7 emnlp-2011-A Joint Model for Extended Semantic Role Labeling
Author: Vivek Srikumar ; Dan Roth
Abstract: This paper presents a model that extends semantic role labeling. Existing approaches independently analyze relations expressed by verb predicates or those expressed as nominalizations. However, sentences express relations via other linguistic phenomena as well. Furthermore, these phenomena interact with each other, thus restricting the structures they articulate. In this paper, we use this intuition to define a joint inference model that captures the inter-dependencies between verb semantic role labeling and relations expressed using prepositions. The scarcity of jointly labeled data presents a crucial technical challenge for learning a joint model. The key strength of our model is that we use existing structure predictors as black boxes. By enforcing consistency constraints between their predictions, we show improvements in the performance of both tasks without retraining the individual models.
3 0.15189674 67 emnlp-2011-Hierarchical Verb Clustering Using Graph Factorization
Author: Lin Sun ; Anna Korhonen
Abstract: Most previous research on verb clustering has focussed on acquiring flat classifications from corpus data, although many manually built classifications are taxonomic in nature. Also Natural Language Processing (NLP) applications benefit from taxonomic classifications because they vary in terms of the granularity they require from a classification. We introduce a new clustering method called Hierarchical Graph Factorization Clustering (HGFC) and extend it so that it is optimal for the task. Our results show that HGFC outperforms the frequently used agglomerative clustering on a hierarchical test set extracted from VerbNet, and that it yields state-of-the-art performance also on a flat test set. We demonstrate how the method can be used to acquire novel classifications as well as to extend existing ones on the basis of some prior knowledge about the classification.
4 0.14174367 14 emnlp-2011-A generative model for unsupervised discovery of relations and argument classes from clinical texts
Author: Bryan Rink ; Sanda Harabagiu
Abstract: This paper presents a generative model for the automatic discovery of relations between entities in electronic medical records. The model discovers relation instances and their types by determining which context tokens express the relation. Additionally, the valid semantic classes for each type of relation are determined. We show that the model produces clusters of relation trigger words which better correspond with manually annotated relations than several existing clustering techniques. The discovered relations reveal some of the implicit semantic structure present in patient records.
5 0.14123198 126 emnlp-2011-Structural Opinion Mining for Graph-based Sentiment Representation
Author: Yuanbin Wu ; Qi Zhang ; Xuanjing Huang ; Lide Wu
Abstract: Based on analysis of on-line review corpus we observe that most sentences have complicated opinion structures and they cannot be well represented by existing methods, such as frame-based and feature-based ones. In this work, we propose a novel graph-based representation for sentence level sentiment. An integer linear programming-based structural learning method is then introduced to produce the graph representations of input sentences. Experimental evaluations on a manually labeled Chinese corpus demonstrate the effectiveness of the proposed approach.
6 0.1268203 128 emnlp-2011-Structured Relation Discovery using Generative Models
7 0.11737058 144 emnlp-2011-Unsupervised Learning of Selectional Restrictions and Detection of Argument Coercions
8 0.11570223 35 emnlp-2011-Correcting Semantic Collocation Errors with L1-induced Paraphrases
9 0.10908768 141 emnlp-2011-Unsupervised Dependency Parsing without Gold Part-of-Speech Tags
10 0.08992736 26 emnlp-2011-Class Label Enhancement via Related Instances
11 0.089483164 107 emnlp-2011-Probabilistic models of similarity in syntactic context
12 0.088159174 53 emnlp-2011-Experimental Support for a Categorical Compositional Distributional Model of Meaning
13 0.086638927 4 emnlp-2011-A Fast, Accurate, Non-Projective, Semantically-Enriched Parser
14 0.085593499 81 emnlp-2011-Learning General Connotation of Words using Graph-based Algorithms
15 0.083997689 50 emnlp-2011-Evaluating Dependency Parsing: Robust and Heuristics-Free Cross-Annotation Evaluation
16 0.081083998 59 emnlp-2011-Fast and Robust Joint Models for Biomedical Event Extraction
17 0.073272809 132 emnlp-2011-Syntax-Based Grammaticality Improvement using CCG and Guided Search
18 0.073050454 100 emnlp-2011-Optimal Search for Minimum Error Rate Training
19 0.069622472 116 emnlp-2011-Robust Disambiguation of Named Entities in Text
20 0.068735868 1 emnlp-2011-A Bayesian Mixture Model for PoS Induction Using Multiple Features
topicId topicWeight
[(0, 0.263), (1, -0.111), (2, -0.192), (3, 0.1), (4, 0.022), (5, -0.086), (6, 0.015), (7, -0.004), (8, 0.034), (9, 0.085), (10, 0.013), (11, 0.0), (12, 0.112), (13, -0.096), (14, 0.001), (15, 0.237), (16, -0.16), (17, 0.137), (18, 0.126), (19, 0.02), (20, -0.067), (21, 0.155), (22, -0.016), (23, 0.046), (24, -0.017), (25, -0.108), (26, -0.122), (27, -0.051), (28, 0.142), (29, 0.19), (30, -0.051), (31, 0.186), (32, -0.048), (33, 0.085), (34, 0.028), (35, -0.089), (36, -0.064), (37, 0.09), (38, -0.001), (39, -0.032), (40, 0.014), (41, -0.067), (42, -0.11), (43, 0.018), (44, 0.11), (45, -0.026), (46, 0.003), (47, -0.025), (48, 0.128), (49, 0.083)]
simIndex simValue paperId paperTitle
same-paper 1 0.96272194 145 emnlp-2011-Unsupervised Semantic Role Induction with Graph Partitioning
Author: Joel Lang ; Mirella Lapata
Abstract: In this paper we present a method for unsupervised semantic role induction which we formalize as a graph partitioning problem. Argument instances of a verb are represented as vertices in a graph whose edge weights quantify their role-semantic similarity. Graph partitioning is realized with an algorithm that iteratively assigns vertices to clusters based on the cluster assignments of neighboring vertices. Our method is algorithmically and conceptually simple, especially with respect to how problem-specific knowledge is incorporated into the model. Experimental results on the CoNLL 2008 benchmark dataset demonstrate that our model is competitive with other unsupervised approaches in terms of F1 whilst attaining significantly higher cluster purity.
2 0.73982614 67 emnlp-2011-Hierarchical Verb Clustering Using Graph Factorization
Author: Lin Sun ; Anna Korhonen
Abstract: Most previous research on verb clustering has focussed on acquiring flat classifications from corpus data, although many manually built classifications are taxonomic in nature. Also Natural Language Processing (NLP) applications benefit from taxonomic classifications because they vary in terms of the granularity they require from a classification. We introduce a new clustering method called Hierarchical Graph Factorization Clustering (HGFC) and extend it so that it is optimal for the task. Our results show that HGFC outperforms the frequently used agglomerative clustering on a hierarchical test set extracted from VerbNet, and that it yields state-of-the-art performance also on a flat test set. We demonstrate how the method can be used to acquire novel classifications as well as to extend existing ones on the basis of some prior knowledge about the classification.
3 0.64398998 7 emnlp-2011-A Joint Model for Extended Semantic Role Labeling
Author: Vivek Srikumar ; Dan Roth
Abstract: This paper presents a model that extends semantic role labeling. Existing approaches independently analyze relations expressed by verb predicates or those expressed as nominalizations. However, sentences express relations via other linguistic phenomena as well. Furthermore, these phenomena interact with each other, thus restricting the structures they articulate. In this paper, we use this intuition to define a joint inference model that captures the inter-dependencies between verb semantic role labeling and relations expressed using prepositions. The scarcity of jointly labeled data presents a crucial technical challenge for learning a joint model. The key strength of our model is that we use existing structure predictors as black boxes. By enforcing consistency constraints between their predictions, we show improvements in the performance of both tasks without retraining the individual models.
4 0.58722687 144 emnlp-2011-Unsupervised Learning of Selectional Restrictions and Detection of Argument Coercions
Author: Kirk Roberts ; Sanda Harabagiu
Abstract: Metonymic language is a pervasive phenomenon. Metonymic type shifting, or argument type coercion, results in a selectional restriction violation where the argument’s semantic class differs from the class the predicate expects. In this paper we present an unsupervised method that learns the selectional restriction of arguments and enables the detection of argument coercion. This method also generates an enhanced probabilistic resolution of logical metonymies. The experimental results indicate substantial improvements the detection of coercions and the ranking of metonymic interpretations.
5 0.49355593 126 emnlp-2011-Structural Opinion Mining for Graph-based Sentiment Representation
Author: Yuanbin Wu ; Qi Zhang ; Xuanjing Huang ; Lide Wu
Abstract: Based on analysis of on-line review corpus we observe that most sentences have complicated opinion structures and they cannot be well represented by existing methods, such as frame-based and feature-based ones. In this work, we propose a novel graph-based representation for sentence level sentiment. An integer linear programming-based structural learning method is then introduced to produce the graph representations of input sentences. Experimental evaluations on a manually labeled Chinese corpus demonstrate the effectiveness of the proposed approach.
6 0.46647161 81 emnlp-2011-Learning General Connotation of Words using Graph-based Algorithms
8 0.39141589 59 emnlp-2011-Fast and Robust Joint Models for Biomedical Event Extraction
9 0.37505504 26 emnlp-2011-Class Label Enhancement via Related Instances
10 0.32854506 100 emnlp-2011-Optimal Search for Minimum Error Rate Training
11 0.32794043 35 emnlp-2011-Correcting Semantic Collocation Errors with L1-induced Paraphrases
12 0.32649049 143 emnlp-2011-Unsupervised Information Extraction with Distributional Prior Knowledge
13 0.32522795 141 emnlp-2011-Unsupervised Dependency Parsing without Gold Part-of-Speech Tags
14 0.32479998 96 emnlp-2011-Multilayer Sequence Labeling
15 0.32324305 132 emnlp-2011-Syntax-Based Grammaticality Improvement using CCG and Guided Search
16 0.30992183 37 emnlp-2011-Cross-Cutting Models of Lexical Semantics
17 0.30739918 111 emnlp-2011-Reducing Grounded Learning Tasks To Grammatical Inference
18 0.3063972 53 emnlp-2011-Experimental Support for a Categorical Compositional Distributional Model of Meaning
19 0.30148086 128 emnlp-2011-Structured Relation Discovery using Generative Models
20 0.29567933 88 emnlp-2011-Linear Text Segmentation Using Affinity Propagation
topicId topicWeight
[(23, 0.118), (36, 0.031), (37, 0.016), (45, 0.063), (53, 0.016), (54, 0.021), (57, 0.013), (62, 0.021), (64, 0.017), (66, 0.044), (69, 0.013), (79, 0.048), (82, 0.02), (90, 0.016), (96, 0.454), (98, 0.016)]
simIndex simValue paperId paperTitle
1 0.96232325 4 emnlp-2011-A Fast, Accurate, Non-Projective, Semantically-Enriched Parser
Author: Stephen Tratz ; Eduard Hovy
Abstract: Dependency parsers are critical components within many NLP systems. However, currently available dependency parsers each exhibit at least one of several weaknesses, including high running time, limited accuracy, vague dependency labels, and lack of nonprojectivity support. Furthermore, no commonly used parser provides additional shallow semantic interpretation, such as preposition sense disambiguation and noun compound interpretation. In this paper, we present a new dependency-tree conversion of the Penn Treebank along with its associated fine-grain dependency labels and a fast, accurate parser trained on it. We explain how a non-projective extension to shift-reduce parsing can be incorporated into non-directional easy-first parsing. The parser performs well when evaluated on the standard test section of the Penn Treebank, outperforming several popular open source dependency parsers; it is, to the best of our knowledge, the first dependency parser capable of parsing more than 75 sentences per second at over 93% accuracy.
same-paper 2 0.924142 145 emnlp-2011-Unsupervised Semantic Role Induction with Graph Partitioning
Author: Joel Lang ; Mirella Lapata
Abstract: In this paper we present a method for unsupervised semantic role induction which we formalize as a graph partitioning problem. Argument instances of a verb are represented as vertices in a graph whose edge weights quantify their role-semantic similarity. Graph partitioning is realized with an algorithm that iteratively assigns vertices to clusters based on the cluster assignments of neighboring vertices. Our method is algorithmically and conceptually simple, especially with respect to how problem-specific knowledge is incorporated into the model. Experimental results on the CoNLL 2008 benchmark dataset demonstrate that our model is competitive with other unsupervised approaches in terms of F1 whilst attaining significantly higher cluster purity.
3 0.7967003 101 emnlp-2011-Optimizing Semantic Coherence in Topic Models
Author: David Mimno ; Hanna Wallach ; Edmund Talley ; Miriam Leenders ; Andrew McCallum
Abstract: Latent variable models have the potential to add value to large document collections by discovering interpretable, low-dimensional subspaces. In order for people to use such models, however, they must trust them. Unfortunately, typical dimensionality reduction methods for text, such as latent Dirichlet allocation, often produce low-dimensional subspaces (topics) that are obviously flawed to human domain experts. The contributions of this paper are threefold: (1) An analysis of the ways in which topics can be flawed; (2) an automated evaluation metric for identifying such topics that does not rely on human annotators or reference collections outside the training data; (3) a novel statistical topic model based on this metric that significantly improves topic quality in a large-scale document collection from the National Institutes of Health (NIH).
4 0.58166993 75 emnlp-2011-Joint Models for Chinese POS Tagging and Dependency Parsing
Author: Zhenghua Li ; Min Zhang ; Wanxiang Che ; Ting Liu ; Wenliang Chen ; Haizhou Li
Abstract: Part-of-speech (POS) is an indispensable feature in dependency parsing. Current research usually models POS tagging and dependency parsing independently. This may suffer from error propagation problem. Our experiments show that parsing accuracy drops by about 6% when using automatic POS tags instead of gold ones. To solve this issue, this paper proposes a solution by jointly optimizing POS tagging and dependency parsing in a unique model. We design several joint models and their corresponding decoding algorithms to incorporate different feature sets. We further present an effective pruning strategy to reduce the search space of candidate POS tags, leading to significant improvement of parsing speed. Experimental results on Chinese Penn Treebank 5 show that our joint models significantly improve the state-of-the-art parsing accuracy by about 1.5%. Detailed analysis shows that the joint method is able to choose such POS tags that are more helpful and discriminative from parsing viewpoint. This is the fundamental reason of parsing accuracy improvement.
5 0.57449597 116 emnlp-2011-Robust Disambiguation of Named Entities in Text
Author: Johannes Hoffart ; Mohamed Amir Yosef ; Ilaria Bordino ; Hagen Furstenau ; Manfred Pinkal ; Marc Spaniol ; Bilyana Taneva ; Stefan Thater ; Gerhard Weikum
Abstract: Disambiguating named entities in naturallanguage text maps mentions of ambiguous names onto canonical entities like people or places, registered in a knowledge base such as DBpedia or YAGO. This paper presents a robust method for collective disambiguation, by harnessing context from knowledge bases and using a new form of coherence graph. It unifies prior approaches into a comprehensive framework that combines three measures: the prior probability of an entity being mentioned, the similarity between the contexts of a mention and a candidate entity, as well as the coherence among candidate entities for all mentions together. The method builds a weighted graph of mentions and candidate entities, and computes a dense subgraph that approximates the best joint mention-entity mapping. Experiments show that the new method significantly outperforms prior methods in terms of accuracy, with robust behavior across a variety of inputs.
6 0.57436031 127 emnlp-2011-Structured Lexical Similarity via Convolution Kernels on Dependency Trees
7 0.56859589 108 emnlp-2011-Quasi-Synchronous Phrase Dependency Grammars for Machine Translation
8 0.56852531 81 emnlp-2011-Learning General Connotation of Words using Graph-based Algorithms
9 0.55596513 78 emnlp-2011-Large-Scale Noun Compound Interpretation Using Bootstrapping and the Web as a Corpus
10 0.54718292 128 emnlp-2011-Structured Relation Discovery using Generative Models
11 0.54264021 144 emnlp-2011-Unsupervised Learning of Selectional Restrictions and Detection of Argument Coercions
12 0.54147333 59 emnlp-2011-Fast and Robust Joint Models for Biomedical Event Extraction
13 0.54010141 126 emnlp-2011-Structural Opinion Mining for Graph-based Sentiment Representation
14 0.53638124 134 emnlp-2011-Third-order Variational Reranking on Packed-Shared Dependency Forests
15 0.53612548 37 emnlp-2011-Cross-Cutting Models of Lexical Semantics
16 0.53317326 33 emnlp-2011-Cooooooooooooooollllllllllllll!!!!!!!!!!!!!! Using Word Lengthening to Detect Sentiment in Microblogs
17 0.5301764 147 emnlp-2011-Using Syntactic and Semantic Structural Kernels for Classifying Definition Questions in Jeopardy!
18 0.53013998 28 emnlp-2011-Closing the Loop: Fast, Interactive Semi-Supervised Annotation With Queries on Features and Instances
19 0.52649218 105 emnlp-2011-Predicting Thread Discourse Structure over Technical Web Forums
20 0.52490979 136 emnlp-2011-Training a Parser for Machine Translation Reordering