Integrating Syntactic and Semantic Analysis into the Open Information Extraction Paradigm

1 Introduction

One of the long standing problems of Artificial Intelligence is Machine Reading (MR) [Mitchell, 2005; Etzioni et al., 2006; Poon and et al., 2010], i.e. the problem of automatic, unsupervised understanding of text. Over time the Natural Language Processing (NLP) community has developed many tools for this problem. One major approach to the MR problem is via the Open Information Extraction (OIE) paradigm [Etzioni et al., 2008; Wu and Weld, 2010], that is the extraction of a large number of relations from huge corpora such as the Web. However, these techniques are mainly concerned with the surface, i.e. textual, realization of relations, without performing any semantic or deep syntactic analysis.

Taking semantics explicitly into account is the main goal of knowledge acquisition techniques, which represent another important set of tools for tackling the MR problem. Such approaches are typically based on a small number of ontologized semantic relation types. One of the most wellknown representative approaches is the Never Ending Language Learner (NELL) [Carlson et al., 2010], which focuses on the continuous learning/extraction of a small, fixed number of semantic relations from the Web. Other approaches extract taxonomic structure information from raw text [Velardi et al., 2013], or exploit semi-structured resources [Hovy et al., 2013] such as WordNet [Miller et al., 1990], Wikipedia 1 and Freebase 2 . The main outputs of these approaches are taxonomies [Ponzetto and Strube, 2011], ontologies [Poon and Domingos, 2010; Hoffart et al., 2013], semantic networks [Navigli and Ponzetto, 2012a; Nastase and Strube,

1 http://en.wikipedia.org/

2 http://www.freebase.com/

2013], relation extraction rules [Krause et al., 2012] and enriched computational lexicons [Pennacchiotti and Pantel, 2006; Navigli, 2005]. These techniques have already been shown to enhance the performance of automatic approaches for a wealth of tasks related to the MR problem, such as Word Sense Disambiguation [Navigli and Ponzetto, 2012b; Miller et al., 2012], Information Extraction [Hoffmann et al., 2011] and many others [Schierle and Trabold, 2008; Fern´andez et al., 2011]. Nonetheless, one major drawback of these approaches is that, either they are not "open", i.e. they are limited in the number of learned relation types [Carlson et al., 2010; Hoffart et al., 2013; Nastase and Strube, 2013], or they do not scale with the dimension of the input corpus [Poon and Domingos, 2010].

Starting with Soderland and Mandhani [2007], middle ground approaches have been proposed which combine the "open" nature of OIE with the semantic awareness of knowledge acquisition techniques. The last year, especially, has seen an increasing interest in semantically-enhanced OIE [Nakashole et al., 2012; Min et al., 2012; Moro and Navigli, 2012; Sun and Grishman, 2012]. At the core of this new paradigm lie the language phenomena of synonymy and polysemy, both of which require deep language understanding. However, none of the existing approaches fully addresses these issues. In this paper we aim at filling this gap by providing the following novel contributions:

• we leverage syntactic analysis to improve the quality of the extracted surface realizations of relations;
• we integrate distributional semantics into syntactic analysis and define a new kernel-based similarity measure which we use for merging synonymous surface realizations into full-fledged semantic relations;
• we exploit category-based distributional semantics to provide semantic type signatures for the acquired semantic relations.

2 RelatedWork

Since the introduction of the OIE paradigm, the NLP community has begun to adopt a new point of view for the study of relation extraction: extending the textual-based ideas of the OIE paradigm towards a deeper and more complete understanding of text based on semantic analysis. Over the last year several approaches have been presented to the problem of ontologizing semantic relations, i.e. automatically identifying synonymous relational phrases together with a semantic description of their typical arguments. A major difficulty of the ontologization problem regards two well-known features of language: synonymy and polysemy. One way to deal with synonymy is to exploit the distributional semantics of the relational phrases [Sun and Grishman, 2012; Moro and Navigli, 2012]. First the context terms occurring in a window surrounding the relational phrases are collected. Then, cosine similarity is utilized for identifying relational phrases with similar contexts. However, this approach suffers from the problem of data sparsity, in that it needs the exact relational phrases to occur several times within a given text. A second approach exploits the arguments of the relationship, in order to determine the similarity of relational phrases [Nakashole et al., 2012]. However, the same arguments can be related by several semantic relations (e.g. married to, is a friend of, started a company with).

As for the problem of polysemy, to date soft clustering techniques have been applied. Soft clustering allows relational phrases to belong to one or more clusters. However, the current approaches address this problem, either when the set of semantic relations is small and known in advance [Min et al., 2012], or by considering static methods, i.e. fixing a threshold and clustering together those relational phrases above the threshold [Moro and Navigli, 2012]. In contrast, in this paper we present an approach to clustering relational phrases into an unknown number of semantic relations by exploiting a soft version of the K-medoids algorithm [Han and Kamber, 2006].

The state-of-the-art systems most closely related to our approach are PATTY [Nakashole et al., 2012] and WiSeNet [Moro and Navigli, 2012], neither of which, however, exploits deep syntactic analysis or advanced soft clustering techniques. In this paper we take the problem of the automatic ontologization of semantic relations to the next level, by integrating deep syntactic analysis together with distributional semantics into a new shortest path kernel method for clustering synonymous relational phrases. The use of a soft version of the K-medoids algorithm enables us to effectively take into account the problems of synonymy and polysemy associated with relational phrases.

3 Integrating Syntax and Semantics into OIE

Our approach consists of three steps: relation extraction, relation ontologization and relation disambiguation. During the first step we extract relational phrases fromWikipedia by exploiting deep syntactic analysis, e.g. we extract the relational phrases is a member of, is a part of, is a territory of. In the second step we define a shortest path kernel similarity measure that integrates semantic and syntactic features to automatically build relation synsets, i.e. clusters of synonymous relational phrases with semantic type signatures for their domain and range. For instance, we cluster together the relational phrases is a member of and is a part of, while we group together, in a separate cluster, is a part of and is a territory of. Finally, we disambiguate the relational phrases extracted fromWikipedia using these relation synsets, obtaining a large set of automatically ontologized semantic relations, e.g. we recognize that the relational phrase is a part of is a synonym of is a territory of when we consider the sentence Nunavut is a part of Canada, while it is a synonym of is a member of for the sentence Taproot Theatre Company is a part of Theatre Communications Group.

3.1 Step 1: Relation Extraction

In this section we describe the approach that we used to extract a large number of relational phrases and relation instances fromWikipedia.

Definition 1 A relational phrase π is a sequence of words that comprises at least one verb and that can be used to express a semantic relation between a subject and an object.

For instance, a good relational phrase is: is located in; a bad relational phrase is: and located in.

Definition 2 A relation instance is a triple (p1, π, p2) where p1, p2 are concepts (i.e., Wikipedia pages) and π is a relational phrase.

For instance, (Nunavut, is a part of, Canada) is a valid relation instance. We build upon the heuristic presented by Moro and Navigli [2012], summarized in the first part of Algorithm 1 (lines 4-13). During this first part, the algorithm analyzes each sentence of each Wikipedia page and extracts a huge number of relational phrases between hyperlink pairs using shallow syntactic analysis (line 10 in Algorithm 1). In contrast to [Etzioni et al., 2008], this heuristic exploits the manual annotations in Wikipedia, by extracting unambiguously hyperlinked arguments. Even so, we still extract overspecific and noisy information (e.g. is the name Gulliver gives his nurse in Book II of and but then lost to). To overcome this problem, first, we filter out all the relational phrases that do not extract more than a minimum number η of relation instances (lines 14-17 in Algorithm 1, see Section 4 for details on tuning). Second, and more importantly, we apply a novel constraint to the surviving relational phrases based on their syntactic structure. As we have already extracted relation instances, we propose a simplified and computationally efficient 3 test to check if each relational phrase relates its arguments as subject and object. We build an artificial phrase for each relational phrase π by concatenating the character "x", the relational phrase π and the character "y", i.e. we obtain "x π y". Then we apply a dependency parser and check whether "x" and "y" are marked as subject of a word in π and object of a, not necessarily the same, word in π (see lines 18-22 of Algorithm 1). For example, the relational phrase is located in satisfies the constraint (see Figure 1a), while the relational phrase and located in does not (see Figure 1b).

3.2 Step 2: Relation Ontologization

As a result of the first step we obtain a set I of relation instances and a set P of relational phrases (line 23 of Algorithm 1). In this second step we ontologize the relational phrases P .

3 The whole Wikipedia corpus consists of 88 million sentences with a mean length of 30 words, while using our approach we syntactically parsed just half a million sentences with a mean length of 10.

Algorithm 1 Extracting relation instances and relational phrases fromWikipedia.

1: input: W, the set of Wikipedia pages. 2: output: I, the set of relation instances; P, the set of relational phrases. 3: function EXTRACTRELATIONINSTANCESANDPHRASES(W) 4: I := ∅; P := ∅; 5: for each page ∈ W do 6: for each sent ∈ page do 7: H(sent) := all the pairs of hyperlinks in sent 8: for each (h1, h2) ∈ H(sent) do 9: π := text between h1 and h2 10: if π contains a verb then 11: I := I ∪ {(h1, π, h2)} 12: count[π] + + 13: P := P ∪ {π} 14: for each π ∈ P do 15: if count[π] < η then 16: I := I \ {(p, π, q) ∈ I : ∃p, q ∈ W} 17: P := P \ {π} 18: for each π ∈ P do 19: dG := depParser("x " +π +" y") 20: if according to dG, x is not a subject of a word in π or y is not an object of a word in π then 21: I := I \ {(p, π, q) ∈ I : ∃p, q ∈ W} 22: P := P \ {π} 23: return I, P

Like any other language component, relational phrases are affected by the well-known phenomena of synonymy (e.g. is situated in and is located in) and polysemy 4 (e.g. is part of can be replaced with is a territory of and is a member of depending on the context). To take into account these issues we exploit soft clustering techniques to synergistically cluster synonymous relational phrases, while at the same time letting polysemous relational phrases belong to more than one cluster. Finally, we create two semantic type signatures of the subjects and objects considered by the relational phrases in each cluster.

In order to perform this step, we consider three different aspects of each relational phrase: its dependency structure, the distributional semantics of its words and the semantics of its arguments.

Distributional Semantics and Shortest Path Dependency Kernel. Given a relational phrase π and the dependency tree of the artificial phrase "x π y", we define πsp as the sequence of words on the shortest path between x and y and πsp [i] as the i-th word on the path. For instance, given π = is located in we have πsp = (located, in) and πsp [2] = in (see Figure 1a). Given two relational phrases π1 and π2, we assume that π1 and π2 can be synonyms only if they share the same sequence of dependency relations and semantically close words within their shortest paths. We formulate this assumption as follows:

4 Min et al. [2012] estimated that roughly 20% of relational phrases can represent at least two different interpretations as different semantic relations.

where type(πsp j [i], πsp j [i+1]) is the syntactic dependency between the i-th and (i + 1)-th words of the shortest path πsp j , dsim(w1,w2) is a measure of semantic similarity between words and g(πsp 1 , πsp 2 ) is our kernel, described hereafter, and Z is a normalization factor.

Since state-of-the-art kernel methods are either used to find synonymous phrases without considering the special role of the shortest paths between the arguments of the phrases [Croce et al., 2011], or they are exploited to learn a classifier for a specific set of relations [Bunescu and Mooney, 2005], we define a new kernel similarity measure based on our shortest path assumption.

Our kernel computes the similarity score between two relational phrases sharing their shortest path as follows:

Our kernel sums the distributional similarity of the words along the considered shortest paths and that of their children (i.e. the function f(n1, n2) in the above equation). Consider π1 = is a territory of and π2 = is a part of. We start by comparing the first word of each shortest path, i.e. territory and part (see Figure 2), and, since they are not the same, we consider their distributional similarity score which is equal to 0.8. Then we consider the corresponding children (i.e. is and a), that are not on the shortest paths, of these nodes. In this case, they are equal in number, type of edges and words, and so we add 1 for the word is and another 1 for the word a to our score. Finally, we do the same for the last node on the shortest path of, obtaining a score of 3.8. We then normalize this score by the maximum number of considered words, i.e. 4, obtaining a similarity score of 0.95. Instead, the similarity score between is a territory of and is a member of is 0.75.

To calculate the aforementioned distributional similarity measure dsim(w1, w2) between the words w1 and w2, we exploit the distributional hypothesis. Given a word w, following Mitchell and Lapata [2010], we define a distributional vector distrV ectl(w) for the words occurring in the left window of w in which each component is computed as the probability of a given context word cw to occur on the left of w divided by its prior probability, Pleft(cw|w) Pleft(cw) . Similarly, we define the distributional vector distrV ectr(w) for the context words that appear to the right of the word w. The probabilities are estimated from a big corpus (see Section 4 for details). Then, we compute the cosine similarity of the left and right vectors:

and finally, by applying the harmonic mean between the two scores above, we obtain a single value of distributional similarity for each pair of words:

Distributed Soft Kernel K-medoids Algorithm. We will now describe the clustering algorithm that we use to build the set Σ of relation synsets.

Definition 3 A relation synset σ is a set of synonymous relational phrases.

For instance, σ = {is a territory of, is a part of }. To obtain the set Σ of relation synsets we exploit a soft version of the Kmedoids algorithm, whose pseudocode is shown in Algorithm 2. As our initial centers C we select all the relational phrases in P (line 4), thereby avoiding tuning the number of clusters K. We use the K-medoids algorithm instead of K-means because we cannot explicitly compute the centroids, but instead have to select the best approximation by finding the relational phrase that maximizes the similarity scores against the other relational phrases in the cluster [Zhang and Rudnicky, 2002].

Next, we start the distributed soft kernel K-medoids algorithm. We define a membership matrix M which describes the assignment of relational phrases to clusters. Because we selected each relational phrase as an initial center of a cluster, M is a |P| × |P| square matrix. The i-th row contains the membership scores of the i-th relational phrase with respect to the various clusters, while the j-th column contains the membership scores of the relational phrases against the j-th cluster.

Algorithm 2 Distributed Soft Kernel K-medoids

1: input: P, the set of relational phrases. 2: output: Σ, the set of relation synsets. 3: function SOFTCLUSTERS(P) 4: C := P 5: repeat 6: Distributed update of M using equation 2; 7: C ′ := C; 8: C := Distributed update of C using equation 3; 9: until C ′ ̸= C 10: return Σ := Extract the relation synsets fromM;

During the first phase of the iterations, we update the membership matrix with the new membership scores with respect to the current centers (line 6 in Algorithm 2). We distribute this computation over all the relational phrases, as this phase requires only the old membership scores of the considered relational phrase and the similarity scores against the current centers. We use the following equation to update the membership score of a relational phrase π against the i-th cluster represented by its center ci ∈ C:

where t is the number of the current iteration of the algorithm. We use an exponential update of the membership scores to ensure a smoother convergence of the algorithm. Moreover, we discard all the membership scores less than a threshold θ2 so as to limit the number of clusters each relational phrase belongs to (see Section 4 for tuning details). During the second phase of the clustering algorithm we compute the new centers C for each cluster Ci = {πj : M(j, i) > 0} in the following manner:

In order to select each center ci, Formula 3 considers only the relational phrases in the i-th cluster Ci, so we can distribute the computation over the number of clusters (line 8 in Algorithm 2). Notice that, as we select the best centroid approximation, some of the clusters end up being merged during the iterations by selecting the same relational phrase as center.

We run the algorithm until the centers remain stable (the convergence is assured by the exponential update) and then we extract, from the membership matrix, the description of the automatically created relation synsets Σ, i.e. we create a set of synonymous relational phrases for each column in the membership matrix by selecting those relational phrases with a positive membership score.

Semantic Type Signatures of the Relation Synsets. We now describe the construction of the semantic description of the relation synsets that will be used to identify which kind of arguments a relation synset considers and that will be used in the next step to disambiguate ambiguous relational phrases.

Definition 4 The semantic type signatures for the domain (i.e. the concepts occurring to the left) and range (i.e. the concepts occurring to the right) of a relation synset σ are two distributional vectors d(σ) and r(σ) of Wikipedia categories.

Since the arguments of our relation instances, extracted during the first step (see Section 3.1), are Wikipedia pages, we can exploit the categories associated with each Wikipedia page to build semantic type signatures for the domain and range of relational phrases.

We define a category vector catV ectd(π) for the concepts in the domain of π. Each component of the vector is computed as the probability that a given category will appear within the domain of π divided by its prior probability: Pdomain(category|π) Pdomain(category) . Similarly, we define the category vector catV ectr(π) for the range of π.

In order to avoid overspecific Wikipedia categories and to keep the number of dimensions low, we consider only the categories which are at distance ≤ 2 from the root 5 of the Wikipedia category hierarchy. In this way we obtain a set C of 657 top-level categories. Given a relational phrase π we have at least η Wikipedia pages in the domain and range of π (see lines 14-17 of Algorithm 1). We count the number of times we reach each top-level category in C starting from the categories of the Wikipedia pages and going up the Wikipedia category hierarchy. Using these counts we estimate the aforementioned probabilities for the domain and range of π.

To extend these category vectors from relational phrases to relation synsets we merge (using a weighted arithmetic mean on the number of extracted relation instances) each category vector of the relational phrases contained in the same relation synset. As a result, we obtain two category vectors d(σ) and r(σ) for each relation synset σ, i.e. our semantic type signature of σ. In Table 1 we show some of the obtained relation synsets.

3.3 Step 3: Relation Disambiguation

After the first step we obtained a set I of relation instances and a set P of relational phrases. Then, in the second step we ontologized the relational phrases in P obtaining a large set of relation synsets Σ. Now, in the third step, we disambiguate each textual relation instance in I with the semantically closest relation synset in Σ.

To disambiguate a relation instance (p1, π, p2) ∈ I we consider all the relation synsets Σπ = {σ ∈ Σ : π ∈ σ} that contain π and we select the semantically closest relation synset:

(p1, argmax σ∈Σπ semsim(p1, σ, p2), p2).

Given a relation synset σ with its semantic type signatures d(σ) and r(σ) and given the distributional vectors catV ect(p1) and catV ect(p2) computed similarly to catV ectl(π) and catV ectr(π), we calculate the cosine similarity between them:

ssd(p1, σ) = cos(catV ect(p1), d(σ))

Then we combine these values into their harmonic mean:

semsim(p1, σ, p2) = HaMean(ssd(p1, σ), ssr(p2, σ)).

5 en.wikipedia.org/wiki/Category:Main topic classifications

4 Experimental Setup

Step 1. To run our relation extraction step we used the English Wikipedia dump of December 1st, 2012. To fix the value of our parameter η = 2 (see line 15 of Algorithm 1) we manually evaluated the accuracy of a random set of 250 relational phrases for η = {1, . . . , 5}. To syntactically parse the phrases we used the Stanford parser [Marneffe et al., 2006].

Step 2. To obtain the distributional description of the words within the relational phrases we used Gigaword [Parker et al., 2011]. The probabilities of the distributional vectors of domain and range were also estimated from Gigaword, using the optimal parameters of Mitchell and Lapata [2010]. To set up the two thresholds θ1 and θ2 (see Formula 1 and 2) needed by our system we built a tuning set composed of 200 manually clustered relational phrases. Then we selected the values that maximized the pair-counting F-Measure (i.e. the number of relational phrase pairs clustered in the same way as the tuning set). We found the following optimal values: θ1 = 0.6, θ2 = 0.86.

Evaluations. We used Amazon Mechanical Turk for our evaluations. To ensure high-quality annotations by competent Turkers we built a gold standard for each evaluation task which will be described in the following section. To evaluate the agreement between judges we used the free-margin multirater kappa [Warrens, 2010] obtaining an agreement greater than 85% for each setup.

Statistics. During the first step we extracted 2, 271, 807 relation instances with 278, 945 distinct relational phrases. As a result of step 2, after 80 iterations, we obtained 29, 440 relation synsets with two or more relational phrases and 155, 207 relation synsets with a single relational phrase. The number of ambiguous relational phrases, i.e. occurring in multiple synsets, was 18, 457 with a mean ambiguity of almost 3.

5 Experiments

Step 1: Ambiguous relation instances. We created a random sample of 2, 000 relation instances extracted during the first step. For each relation instance (p1, π, p2), we presented three judges with the title of p1 and p2 and the relational phrase π together with the first paragraph of the Wikipedia page of p1 and p2. Then we asked if the relation instance was correct. The results are shown in the first row of Table 2 together with the accuracy of our closest competitor, i.e. WiSeNet. An error analysis identified the wrong hyperlinks annotation in Wikipedia as the main class of error, e.g. (Rajura, lies in the heart of the, Coal) is extracted from the sentence: Rajura lies in the heart of the coal- and cementproducing areas of Maharashtra, where coal is a hyperlink and Maharashtra is not linked.

Step 1: Relational phrases. We created a second random sample of 2, 000 relational phrases. We presented the judges with each relational phrase and we asked if they could think of a subject and an object that would fit the phrase. The results are shown in the second row of Table 2. An error analysis identified the wrong syntactic parsing of relational phrases as the main class of error, e.g. x site and was designated a y in which site is considered as a verb instead of a noun compound modifier.

Step 2: Relation synsets. The third sample consisted of 2, 000 randomly chosen relation synsets which contained at least two relational phrases. We asked the judges if two relational phrases randomly chosen from the considered relation synset could be exchanged with each other to express the same semantic relation. The results are shown in the third row of Table 2. Antonymy was identified as the main class of error, i.e. we cluster together was a predecessor of and was the successor of.

Step 3: Disambiguated relation instances. In this evaluation we considered only the relation instances (p1, π, p2) which contained relational phrases associated with more than one relation synset, i.e. ambiguous relational phrases which we disambiguated with our relation synsets in step 3. We created a random sample containing 2, 000 of these disambiguated relation instances. We presented three judges with the title of p1 and p2 and a randomly chosen relational phrase from the disambiguated relation synset together with the first paragraph of the Wikipedia page of p1 and p2. We then asked if the relation instance was correct, as in the first evaluation. The results are shown in the fourth row of Table 2.

Discussion. In conclusion, our four evaluations showed the high quality of our outputs and greater accuracy over that reported by WiSeNet. More importantly, the last evaluation on the disambiguated relation instances shows that our intermediate steps are strong, as we maintain a small gap (roughly 3%) between the accuracy of the relation instances extracted during the first step and the relation instances disambiguated in the last step, while our closest competitor has a gap of more than 6%.

5.1 Coverage of Semantic Relations

To assess the coverage of the extracted semantic relations we compared our relation synsets against a public dataset described in [Nakashole et al., 2012]. This dataset is made up of 163 semantic relations manually identified in five Wikipedia pages about musicians. The dataset's authors calculated the number of these relations covered by well-known knowledge bases, i.e. YAGO2 [Hoffart et al., 2013], DBpedia [Auer et al., 2007], Freebase [Bollacker et al., 2008], NELL [Carlson et al., 2010] and PATTY [Nakashole et al., 2012] (see Table 3). As was done in [Nakashole et al., 2012], we manually associated each of these semantic relations with one of our relation synsets that best represented the considered semantic relation in terms of relational phrases and semantic type signatures, obtaining an increase in the number of recognized semantic relations over the best system, i.e. PATTY. As can be seen from Table 3, the number of semantic relations contained in the other resources is considerably lower, showing that those resources are still missing a lot of useful information. In contrast, our approach and PATTY demonstrate their ability to find and extract a wealth of semantic relations. Moreover, in contrast to PATTY, our approach takes into account the phenomenon of polysemous relational phrases.

6 Conclusions and FutureWork

We presented an approach that provides a novel integration of automatic ontologization of semantic relations into the OIE paradigm by exploiting syntactic and semantic analysis. We demonstrated the quality of our approach by carrying out extensive manual evaluations and by comparing our approach against state-of-the-art resources, with competitive results.

The main contributions of this paper can be summarized as follows: i) we presented an efficient way to integrate syntax into the OIE workflow; ii) we introduced a new kernel similarity measure that combines syntax and distributional semantics; iii) we presented an algorithm for associating a semantic description with the typical arguments of a set of synonymous relational phrases, and which can also be exploited to disambiguate semantic relation instances.

We will release all the data to the research community (http://lcl.uniroma1.it/wisenet). As future work we plan to extend our current approach from binary to n-ary semantic relations, test the approach on other languages and, most importantly, build a hierarchical structure on the relation synsets along the lines of PATTY.

Acknowledgments

The authors gratefully acknowledge the support of the ERC Starting Grant MultiJEDI No. 259234.