{'fraction_non_alphanumeric': 0.03554494168137611, 'fraction_numerical': 0.010417748243519192, 'mean_word_length': 4.864420539882281, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Arguments and Supertypes of Semantic Relations Using Recursive Patterns

A challenging problem in open information extraction and text mining is the learning of the selectional restrictions of semantic relations. We propose a minimally supervised bootstrapping algorithm that uses a single seed and a recursive lexico-syntactic pattern to learn the arguments and the supertypes of a diverse set of semantic relations from the Web. We evaluate the performance of our algorithm on multiple semantic relations expressed using "verb", "noun", and "verb prep" lexico-syntactic patterns. Human-based evaluation shows that the accuracy of the harvested information is about 90%. We also compare our results with existing knowledge base to outline the similarities and differences of the granularity and diversity of the harvested knowledge.


Introduction
Building and maintaining knowledge-rich resources is of great importance to information extraction, question answering, and textual entailment. Given the endless amount of data we have at our disposal, many efforts have focused on mining knowledge from structured or unstructured text, including ground facts (Etzioni et al., 2005), semantic lexicons (Thelen and Riloff, 2002), encyclopedic knowledge (Suchanek et al., 2007), and concept lists . Researchers have also successfully harvested relations between entities, such as is-a (Hearst, 1992;Pasca, 2004) and part-of (Girju et al., 2003). The kinds of knowledge learned are generally of two kinds: ground instance facts (New York is-a city, Rome is the capital of Italy) and general relational types (city is-a location, engines are part-of cars).
A variety of NLP tasks involving inference or entailment (Zanzotto et al., 2006), including QA  and MT (Mt et al., 1988), require a slightly different form of knowledge, derived from many more relations. This knowledge is usually used to support inference and is expressed as selectional restrictions (Wilks, 1975) (namely, the types of arguments that may fill a given relation, such as person live-in city and airline fly-to location). Selectional restrictions constrain the possible fillers of a relation, and hence the possible contexts in which the patterns expressing that relation can participate in, thereby enabling sense disambiguation of both the fillers and the expression itself.
To acquire this knowledge two common approaches are employed: clustering and patterns. While clustering has the advantage of being fully unsupervised, it may or may not produce the types and granularity desired by a user. In contrast pattern-based approaches are more precise, but they typically require a handful to dozens of seeds and lexico-syntactic patterns to initiate the learning process. In a closed domain these approaches are both very promising, but when tackling an unbounded number of relations they are unrealistic. The quality of clustering decreases as the domain becomes more continuously varied and diverse, and it has proven difficult to create collections of effective patterns and high-yield seeds manually.
In addition, the output of most harvesting systems is a flat list of lexical semantic expressions such as "New York is-a city" and "virus causes flu". However, using this knowledge in inference requires it to be formulated appropriately and organized in a semantic repository. (Pennacchiotti and Pantel, 2006) proposed an algorithm for automatically ontologizing semantic relations into WordNet. However, despite its high precision entries, WordNet's limited coverage makes it impossible for relations whose arguments are not present in WordNet to be incorporated. One would like a procedure that dynamically organizes and extends its semantic repository in order to be able to accommodate all newly-harvested information, and thereby become a global semantic repository.
Given these considerations, we address in this paper the following question: How can the selectional restrictions of semantic relations be learned automatically from the Web with minimal effort using lexico-syntactic recursive patterns?
The contributions of the paper are as follows: • A novel representation of semantic relations using recursive lexico-syntactic patterns. • An automatic procedure to learn the selectional restrictions (arguments and supertypes) of semantic relations from Web data.
• An exhaustive human-based evaluation of the harvested knowledge. • A comparison of the results with some large existing knowledge bases.
The rest of the paper is organized as follows. In the next section, we review related work. Section 3 addresses the representation of semantic relations using recursive patterns. Section 4 describes the bootstrapping mechanism that learns the selectional restrictions of the relations. Section 5 describes data collection. Section 6 discusses the obtained results. Finally, we conclude in Section 7.
When research focuses on a particular relation, careful attention is paid to the pattern(s) that express it in various ways (as in most of the work above, notably (Riloff and Jones, 1999)). But it has proven a difficult task to manually find effectively different variations and alternative patterns for each relation. In contrast, when research focuses on any relation, as in TextRunner (Yates et al., 2007), there is no standardized manner for re-using the pattern learned. TextRunner scans sentences to obtain relation-independent lexico-syntactic patterns to extract triples of the form (John, fly to, Prague). The middle string denotes some (unspecified) semantic relation while the first and third denote the learned arguments of this relation. But TextRunner does not seek specific semantic relations, and does not re-use the patterns it harvests with different arguments in order to extend their yields.
Clearly, it is important to be able to specify both the actual semantic relation sought and use its textual expression(s) in a controlled manner for maximal benefit.
The objective of our research is to combine the strengths of the two approaches, and, in addition, to provide even richer information by automatically mapping each harvested argument to its supertype(s) (i.e., its semantic concepts). For instance, given the relation destination and the pattern X flies to Y, automatically determining that John, Prague) and (John, conference) are two valid filler instance pairs, that (RyanAir, Prague) is another, as well as that person and airline are supertypes of the first argument and city and event of the second. This information provides the selectional restrictions of the given semantic relation, indicating that living things like people can fly to cities and events, while non-living things like airlines fly mainly to cities. This is a significant improvement over systems that output a flat list of lexical semantic knowledge (Thelen and Riloff, 2002;Yates et al., 2007;Suchanek et al., 2007).
Knowing the sectional restrictions of a semantic relation supports inference in many applications, for example enabling more accurate information extraction. (Igo and Riloff, 2009) report that patterns like "attack on NP " can learn undesirable words due to idiomatic expressions and parsing errors. Over time this becomes problematic for the bootstrapping process and leads to significant deterioration in performance. (Thelen and Riloff, 2002) address this problem by learning multiple semantic categories simultaneously, relying on the often unrealistic assumption that a word cannot belong to more than one semantic category. How-ever, if we have at our disposal a repository of semantic relations with their selectional restrictions, the problem addressed in (Igo and Riloff, 2009) can be alleviated.
In order to obtain selectional restriction classes, (Pennacchiotti and Pantel, 2006) made an attempt to ontologize the harvested arguments of is-a, part-of, and cause relations. They mapped each argument of the relation into WordNet and identified the senses for which the relation holds. Unfortunately, despite its very high precision entries, WordNet is known to have limited coverage, which makes it impossible for algorithms to map the content of a relation whose arguments are not present in WordNet. To surmount this limitation, we do not use WordNet, but employ a different method of obtaining superclasses of a filler term: the inverse doubly-anchored patterns DAP −1 (Hovy et al., 2009), which, given two arguments, harvests its supertypes from the source corpus. (Hovy et al., 2009) show that DAP −1 is reliable and it enriches WordNet with additional hyponyms and hypernyms.

Recursive Patterns
A singly-anchored pattern contains one example of the seed term (the anchor) and one open position for the term to be learned. Most researchers use singly-anchored patterns to harvest semantic relations. Unfortunately, these patterns run out of steam very quickly. To surmount this obstacle, a handful of seeds is generally used, and helps to guarantee diversity in the extraction of new lexicosyntactic patterns (Riloff and Jones, 1999;Snow et al., 2005;Etzioni et al., 2005).
Some algorithms require ten seeds (Riloff and Jones, 1999;Igo and Riloff, 2009), while others use a variation of 5, 10, to even 25 seeds (Talukdar et al., 2008). Seeds may be chosen at random (Davidov et al., 2007;Kozareva et al., 2008), by picking the most frequent terms of the desired class (Igo and Riloff, 2009), or by asking humans (Pantel et al., 2009). As (Pantel et al., 2009) show, picking seeds that yield high numbers of different terms is difficult. Thus, when dealing with unbounded sets of relations (Banko and Etzioni, 2008), providing many seeds becomes unrealistic.
Interestingly, recent work reports a class of patterns that use only one seed to learn as much information with only one seed. (Kozareva et al., 2008;Hovy et al., 2009) introduce the so-called doubly-anchored pattern (DAP) that has two anchor seed positions " type such as seed and *", plus one open position for the terms to be learned. Learned terms can then be replaced into the seed position automatically, creating a recursive procedure that is reportedly much more accurate and has much higher final yield. (Kozareva et al., 2008;Hovy et al., 2009) have successfully applied DAP for the learning of hyponyms and hypernyms of is-a relations and report improvements over (Etzioni et al., 2005) and (Pasca, 2004).
Surprisingly, this work was limited to the semantic relation is-a. No other study has described the use or effect of recursive patterns for different semantic relations. Therefore, going beyond (Kozareva et al., 2008;Hovy et al., 2009), we here introduce recursive patterns other than DAP that use only one seed to harvest the arguments and supertypes of a wide variety of relations. (Banko and Etzioni, 2008) show that semantic relations can be expressed using a handful of relation-independent lexico-syntactic patterns. Practically, we can turn any of these patterns into recursive form by giving as input only one of the arguments and leaving the other one as an open slot, allowing the learned arguments to replace the initial seed argument directly. For example, for the relation "fly to", the following recursive patterns can be built: "* and seed fly to *", " seed and * fly to *", "* fly to seed and *", "* fly to * and seed ", " seed fly to *" or "* fly to seed ", where seed is an example like John or Ryanair, and ( * ) indicates the position on which the arguments are learned. Conjunctions like and, or are useful because they express list constructions and extract arguments similar to the seed. Potentially, one can explore all recursive pattern variations when learning a relation and compare their yield, however this study is beyond the scope of this paper.
We are particularly interested in the usage of recursive patterns for the learning of semantic relations not only because it is a novel method, but also because recursive patterns of the DAP fashion are known to: (1) learn concepts with high precision compared to singly-anchored patterns (Kozareva et al., 2008), (2) use only one seed instance for the discovery of new previously unknown terms, and (3) harvest knowledge with minimal supervision.

Problem Formulation
The main goal of our research is: Task Definition: Given a seed and a semantic relation expressed using a recursive lexico-syntactic pattern, learn in bootstrapping fashion the selectional restrictions (i.e., the arguments and supertypes) of the semantic relation from an unstructured corpus such as the Web. Figure 1 shows an example of the task and the types of information learned by our algorithm. Given a seed John and a semantic relation fly to expressed using the recursive pattern "* and John fly to *", our algorithm learns the left side arguments {Brian, Kate, bees, Delta, Alaska} and the right side arguments {flowers, trees, party, New York, Italy, France}. For each argument, the algorithm harvests supertypes such as {people, artists, politicians, airlines, city, countries, plants, event} among others. The colored links between the right and left side concepts denote the selectional restrictions of the relation. For instance, people fly to events and countries, but never to trees or flowers.

System Architecture
We propose a minimally supervised bootstrapping algorithm based on the framework adopted in (Kozareva et al., 2008;Hovy et al., 2009). The algorithm has two phases: argument harvesting and supertype harvesting. The final output is a ranked list of interlinked concepts which captures the selectional restrictions of the relation.

Argument Harvesting
In the argument extraction phase, the first bootstrapping iteration is initiated with a seed Y and a recursive pattern "X * and Y verb+prep|verb|noun Z * ", where X * and Z * are the placeholders for the arguments to be learned. The pattern is submitted to Yahoo! as a web query and all unique snippets matching the query are retrieved. The newly learned and previously unexplored arguments on the X * position are used as seeds in the subsequent iteration. The arguments on the Z * position are stored at each iteration, but never used as seeds since the recursivity is created using the terms on X and Y . The bootstrapping process is implemented as an exhaustive breadth-first algorithm which terminates when all arguments are explored.
We noticed that despite the specific lexicosyntactic structure of the patterns, erroneous information can be acquired due to part-of-speech tagging errors or flawed facts on the Web. The challenge is to identify and separate the erroneous from the true arguments. We incorporate the harvested arguments on X and Y positions in a directed graph G = (V, E), where each vertex v ∈ V is a candidate argument and each edge (u, v) ∈ E indicates that the argument v is generated by the argument u. An edge has weight w corresponding to the number of times the pair (u, v) is extracted from different snippets. A node u is ranked by u= ∀(u,v)∈E w(u,v)+ ∀(v,u)∈E w(v,u) |V |−1 which represents the weighted sum of the outgoing and incoming edges normalized by the total number of nodes in the graph. Intuitively, our confidence in a correct argument u increases when the argument (1) discovers and (2) is discovered by many different arguments.
Similarly, to rank the arguments standing on the Z position, we build a bipartite graph G = (V , E ) that has two types of vertices. One set of vertices represents the arguments found on the Y position in the recursive pattern. We will call these V y . The second set of vertices represents the arguments learned on the Z position. We will call these V z . We create an edge e (u , v ) ∈ E between u ∈ V y and v ∈ V z when the argument on the Z position represented by v was harvested by the argument on the Y position represented by u . The weight w of the edge indicates the number of times an argument on the Y position found Z.
Vertex v is ranked as In a very large corpus, like the Web, we assume that a correct argument Z is the one that is frequently discovered by various arguments Y .

Supertype Harvesting
In the supertype extraction phase, we take all <X,Y> argument pairs collected during the argument harvesting stage and instantiate them in the inverse DAP −1 pattern "* such as X and Y". The query is sent to Yahoo! as a web query and all 1000 snippets matching the pattern are retrieved. For each <X,Y> pair, the terms on the (*) position are extracted and considered as candidate supertypes.
To avoid the inclusion of erroneous supertypes, again we build a bipartite graph G = (V , E ). The set of vertices V sup represents the supertypes, while the set of vertices V p corresponds to the X,Y pair that produced the supertype. An edge e (u , v ) ∈ E , where u ∈ V p and v ∈ V sup shows that the pair X,Y denoted as u harvested the supertype represented by v .
For example, imagine that the argument X * = Ryanair was harvested in the previous phase by the recursive pattern "X * and EasyJet fly to Z * ". Then the pair Ryanair,EasyJet forms a new Web query "* such as Ryanair and EasyJet" which learns the supertypes "airlines" and "carriers". The bipartite graph has two vertices v 1 and v 2 for the supertypes "airlines" and "carriers", one vertex u 3 for the argument pair Ryanair, EasyJet , and two edges e 1 (u 3 , v 1 ) and e 2 (u 3 , v 1 ).
Intuitively, a supertype which is discovered multiple times by various argument pairs is ranked highly.
However, it might happen that a highly ranked supertype actually does not satisfy the selectional restrictions of the semantic relation. To avoid such situations, we further instantiate each supertype concept in the original pattern 1 . For example, "aircompanies fly to *" and "carriers fly to *". If the candidate supertype produces many web hits for the query, then this suggests that the term is a relevant supertype.
Unfortunately, to learn the supertypes of the Z arguments, currently we have to form all possible combinations among the top 150 highly ranked concepts, because these arguments have not been learned through pairing. For each pair of Z arguments, we repeat the same procedure as described above.

Semantic Relations
So far, we have described the mechanism that learns from one seed and a recursive pattern the selectional restrictions of any semantic relation. Now, we are interested in evaluating the performance of our algorithm. A natural question that arises is: "How many patterns are there?". (Banko and Etzioni, 2008) found that 95% of the semantic relations can be expressed using eight lexico-syntactic patterns. Space prevents us from describing all of them, therefore we focus on the three most frequent patterns which capture a large diversity of semantic relations. The relative frequency of these patterns is 37.80% for "verbs", 22.80% for "noun prep", and 16.00% for "verb prep". Table 1 shows the lexico-syntactic pattern and the initial seed we used to express each semantic relation. To collect data, we ran our knowledge harvesting algorithm until complete exhaustion. For each query submitted to Yahoo!, we retrieved the top 1000 web snippets and kept only the unique ones. In total, we collected 30GB raw data which was part-of-speech tagged and used for the argument and supertype extraction. Table 1   An interesting characteristic of the recursive patterns is the speed of leaning which can be measured in terms of the number of unique arguments acquired during each bootstrapping iteration. Figure 2 shows the bootstrapping process for the "cause" and "dress" relations. Although both relations differ in terms of the total number of iterations and harvested items, the overall behavior of the learning curves is similar. Learning starts of very slowly and as bootstrapping progresses a rapid growth is observed until a saturation point is reached. The speed of leaning is related to the connectivity behavior of the arguments of the relation. Intuitively, a densely connected graph takes shorter time (i.e., fewer iterations) to be learned, as in the "work on" relation, while a weakly connected network takes longer time to harvest the same amount of information, as in the "work for" relation.

Results
In this section, we evaluate the results of our knowledge harvesting algorithm. Initially, we decided to conduct an automatic evaluation comparing our results to knowledge bases that have been extracted in a similar way (i.e., through pattern application over unstructured text). However, it is not always possible to perform a complete comparison, because either researchers have not fully explored the same relations we have studied, or for those relations that overlap, the gold standard data was not available.
The online demo of TextRunner 2 (Yates et al., 2007) actually allowed us to collect the arguments for all our semantic relations. However, due to Web based query limitations, TextRunner returns only the first 1000 snippets. Since we do not have the complete and ranked output of TextRunner, comparing results in terms of recall and precision is impossible.
Turning instead to results obtained from structured sources (which one expects to have high correctness), we found that two of our relations overlap with those of the freely available ontology Yago (Suchanek et al., 2007), which was harvested from the Infoboxes tables in Wikipedia. In addition, we also had two human annotators judge as many results as we could afford, to obtain Precision. We conducted two evaluations, one for the arguments and one for the supertypes. 2 http://www.cs.washington.edu/research/textrunner/

Human-Based Argument Evaluation
In this section, we discuss the results of the harvested arguments. For each relation, we selected the top 200 highly ranked arguments. We hired two annotators to judge their correctness. We created detailed annotation guidelines that define the labels for the arguments of the relations, as shown in Table 2. (Previously, for the same task, researchers have not conducted such an exhaustive and detailed human-based evaluation.) The annotation was conducted using the CAT system 3 .  We allow multiple labels to be assigned to the same concept, because sometimes the concept can appear in different contexts that carry various conceptual representations. Although the labels can be easily collapsed to judge correct and incorrect terms, the fine-grained annotation shown here provides a better overview of the information learned by our algorithm.
We measured the inter-annotator agreement for all labels and relations considering that a single entry can be tagged with multiple labels. The Kappa score is around 0.80. This judgement is good enough to warrant using these human judgements to estimate the accuracy of the algorithm. We compute Accuracy as the number of examples tagged as Correct divided by the total number of examples. Table 4 shows the obtained results. The overall accuracy of the argument harvesting phase is 91%. The majority of the occurred errors are due to part-of-speech tagging. Table 3 shows a sample of 10 randomly selected examples from the top 200 ranked and manually annotated arguments.

Relation
Arguments (X) Dress: stylish, comfortable, expensive, shabby, gorgeous silver, clean, casual, Indian, black (X) Person: honest, caring, happy, intelligent, gifted friendly, responsible, mature, wise, outgoing (X) Cause: pressure, stress, fire, bacteria, cholesterol flood, ice, cocaine, injuries, wars GoTo (Z): school, bed, New York, the movies, the park, a bar the hospital, the church, the mall, the beach LiveIn (Z): peace, close proximity, harmony, Chicago, town New York, London, California, a house, Australia WorkFor (Z): a company, the local prison, a gangster, the show a boss, children, UNICEF, a living, Hispanics Table 3: Examples of Harvested Arguments.

Comparison against Existing Resources
In this section, we compare the performance of our approach with the semantic knowledge base Yago 4 that contains 2 million entities 5 , 95% of which were manually confirmed to be correct. In this study, we compare only the unique arguments of the "live in" and "work at" relations. We provide Precision scores using the following measures: P r Y ago = #terms f ound in Y ago #terms harvested by system P r Human = #terms judged correct by human #terms harvested by system N otInY ago = #terms judged correct by human but not in Y ago Table 5 shows the obtained results. We carefully analyzed those arguments that were found by one of the systems but were missing in the other. The recursive patterns learn information about non-famous entities like Peter and famous entities like Michael Jordan. In contrast, Yago contains entries mostly about famous entities, because this is the predominant knowledge in Wikipedia. For the "live in" relation, both repositories contain the same city and country names. However, the recursive pattern learned arguments like pain, effort which express a manner of living, and locations like slums, box. This information is missing from Yago. Similarly for the "work at" relation, both systems learned that people work at universities. In addition, the recursive pattern learned a diversity of company names absent from Yago.
While it is expected that our algorithm finds many terms not contained in Yago-specifically, the information not deemed worthy of inclusion in Wikipedia-we are interested in the relatively large number of terms contained in Yago but not found by our algorithm. To our knowledge, no 4 http://www.mpi-inf.mpg.de/yago-naga/yago/ 5 Names of cities, people, organizations among others.  other automated harvesting algorithm has ever been compared to Yago, and our results here form a baseline that we aim to improve upon. And in the future, one can build an extensive knowledge harvesting system combining the wisdom of the crowd and Wikipedia.

Human-Based Supertype Evaluation
In this section, we discuss the results of harvesting the supertypes of the learned arguments. Figure 3 shows the top 100 ranked supertypes for the "cause" and "work on" relations. The x-axis indicates a supertype, the y-axis denotes the number of different argument pairs that lead to the discovery of the supertype. The decline of the curve indicates that certain supertypes are preferred and shared among different argument pairs. It is interesting to note that the text on the Web prefers a small set of supertypes, and to see what they are. These most-popular harvested types tend to be the more descriptive terms.
The results indicate that one does not need an elaborate supertype hierarchy to handle the selectional restrictions of semantic relations.
Since our problem definition differs from available related work, and WordNet does not contain all harvested arguments as shown in (Hovy et al., 2009), it is not possible to make a direct comparison. Instead, we conduct a manual evaluation of the most highly ranked supertypes which normally are the top 20. The overall accuracy of the supertypes for all relations is 92%. Table 6 shows the  top 10 highly ranked supertypes for six of our relations.

Conclusion
We propose a minimally supervised algorithm that uses only one seed example and a recursive lexicosyntactic pattern to learn in bootstrapping fashion the selectional restrictions of a large class of semantic relations. The principal contribution of the paper is to demonstrate that this kind of pattern can be applied to almost any kind of semantic relation, as long as it is expressible in a concise surface pattern, and that the recursive mechanism that allows each newly acquired term to restart harvesting automatically is a significant advance over patterns that require a handful of seeds to initiate the learning process. It also shows how one can combine free-form but undirected pattern-learning approaches like TextRunner with more-controlled but effort-intensive approaches like commonly used. In our evaluation, we show that our algorithm is capable of extracting high quality non-trivial information from unstructured text given very restricted input (one seed). To measure the performance of our approach, we use various semantic relations expressed with three lexico-syntactic patterns. For two of the relations, we compare results with the freely available ontology Yago, and conduct a manual evaluation of the harvested terms.
We will release the annotated and the harvested data to the public to be used for comparison by other knowledge harvesting algorithms.
The success of the proposed framework opens many challenging directions. We plan to use the algorithm described in this paper to learn the selectional restrictions of numerous other relations, in order to build a rich knowledge repository that can support a variety of applications, including textual entailment, information extraction, and question answering.