1 Introduction
Semantic representation of text is of great importance for natural language processing (NLP), since many applications depend on it. For example, semantic representation facilitates inferences and reasoning, which in turn may impact Question Answering, Information Extraction, Text Summarization, and other applications. In this work, we distinguish between semantic roles and semantic relations. Semantic roles depict associations between verbs and their arguments (Baker, Fillmore and Lowe Reference Baker, Fillmore and Lowe1998; Pradhan et al. Reference Pradhan, Ward, Hacioglu, Martin, Jurafsky, Dumais and Roukos2004; Màrquez et al. Reference Màrquez, Carreras, Litkowski and Stevenson2008). Semantic relations depict semantic associations between concepts found in compound nouns, noun phrases, verb phrases, clauses, in addition to verb argument structures. For example, the compound noun car door encodes a part-whole relation: the door is part of the car. Similarly, the statement His extracurricular activities lowered his grades carries a causal relation between the activities and the lowered his grades. Detecting this relation would help answer a number of questions, including Why did he have low grades?
Semantic relations are used to build the semantic structure of a sentence, which in turn helps transform unstructured text into structured knowledge. The interest level is increasing in such semantic technologies and enabling ontologies.
A typical approach for extracting semantic relations between concepts is based on some syntactic methods (rules) and/or patterns that are likely to encode some specific relations (Moldovan et al. Reference Moldovan, Badulescu, Tatu, Antohe and Girju2004; Chang and Choi Reference Chang and Choi2006; Girju et al. Reference Girju, Nakov, Nastase, Szpakowicz, Turney and Yuret2007; Bethard and Martin Reference Bethard and Martin2008; Srikumar et al. Reference Srikumar, Reichart, Sammons, Rappoport and Roth2008). In general, this approach is mostly valid, but overlooks some relations between concepts that do not follow a particular pattern or fails to disambiguate relations that follow the same or similar patterns (Mihalcea and Shi Reference Mihalcea and Shi2005). Moreover, the approach is not able to retrieve the potential relations between concepts that are not within some close proximity from each other. For example, from the sentence ‘John's office is in Carrington Park, located in Highland Lakes district’ a semantic parser would likely extract that John's office is located at Carrington Park and Carrington Park is located at Highland Lakes. However, it is unlikely that it will extract the simple information that John's office is in Highland Lakes.
This observation, where more semantics can be extracted from text in addition to what a semantic parser extracts, was the starting point of our investigation. We propose a method for augmenting already extracted semantics by combining multiple relations over common concepts. We call this composition of semantic relations (CSR). Pairs of relations can be formed and their semantic combinations studied over broad range of concepts and contexts.
In this paper, we focus on the composition of at-location relation with other semantic relations in a sample semantic relations set. The results show the proposed method can increase the total number of instances of semantic relations extracted by a semantic parser. We anticipate that such significant improvements in revealing additional semantics will benefit many semantically based applications.
The CSR proposed here uses axioms that conclude a relation from the original set. The axioms have properties and necessary conditions to apply. There are four main benefits of CSR: (i) the method detects relations that escape a regular Semantic Parser (SP); (ii) the method is able to detect relations between concepts that are far apart from each other; (iii) the method does not require modifications and/or configuration change to existing tools; and (iv) the method has a high precision/accuracy.
Furthermore, CSR has been proven useful in several pragmatic applications, such as the customization of a set of relations to a specific domain, recognizing textual entailment (TE), and commonsense knowledge acquisition.
2 Related previous works
The semantics of relations between concepts has been studied in philosophy, psychology, and anthropology as well as in linguistics. Philosophers have considered the intrinsic physical meaning of space and location as well as how they relate to other concepts, their importance in human and animal life, and impact on several other fields of science (Halsbury Reference Halsbury1962; Whiteman Reference Whiteman1967).
Space and location are very tangible and intuitive notions. Children acquire this knowledge in their early stages of development, partly due to the important survival instinct (e.g., finding the way back home for safety) (Piaget Reference Piaget, Gattegno and Hodgson1952; Heft and Wohwill Reference Heft and Wohwill1987; Golledge et al. Reference Golledge, Gale, Pellegrino and Doherty1992).
Even creatures without the ability to speak are able to use space and location to reason and infer information. It has been claimed that humans also use spatial reasoning more effectively and easily than logical reasoning (Jackendoff Reference Jackendoff1983; Jackendoff Reference Jackendoff1990). Even though spatial cognition is important for the survival of human beings, the amount of spatial reckoning and description may vary across cultures (Levinson Reference Levinson1996). Some cultures may provide fewer locations in their descriptions, assuming that they are obvious. The same behavior can be observed in some other cultures due to ethnocentrisms (Levinson Reference Levinson1996). For example, directions to the same location could be given differently in different cultures because of the difference in linguistic resources. In these cases, automatically augmenting location knowledge from what is already revealed (spatial knowledge) becomes even more important. The at-location semantic relation is used to express the spatial characterization of concepts. Augmenting at-location, then, would carry the same importance.
There have been numerous studies on semantic relations (Szpakowicz and Barker Reference Szpakowicz and Barker1995; Moldovan et al. Reference Moldovan, Badulescu, Tatu, Antohe and Girju2004; Turney Reference Turney2006; Srikumar et al. Reference Srikumar, Reichart, Sammons, Rappoport and Roth2008; Beamer and Girju Reference Beamer and Girju2009) that propose different sets of relations. The question remains still unanswered about the cardinality of the set. One could theoretically choose to use a set of only two relations, e.g., related and not-related. On the other hand, there are proposals with hundreds of very specific relations, such as from-airport and to-airport in an investigative context. Helbig (Helbig Reference Helbig2005), in his detailed study, proposed a set of eighty-nine relations without addressing how to extract them from text, which is a different problem. His relations are fine-grained and his set includes multiple relations for expressing common concepts such as time (e.g., succession, duration, end). Most researchers use no more than a couple of dozens of semantic relations for a generic use. One can argue that there is no exact number nor types of semantic relations. It is simply the application that ultimately dictates a suitable set of relations. In this study, we use a set of twenty-six relations.
In computational linguistics, the most used resources for semantics are (i)WordNet (Miller Reference Miller1995); (ii) FrameNet (Baker et al. Reference Baker, Fillmore and Lowe1998); and (iii) PropBank (Kingsbury, Palmer and Marcus Reference Kingsbury, Palmer and Marcus2002; Palmer, Gildea and Kingsbury Reference Palmer, Gildea and Kingsbury2005).
WordNet is a lexical database in which nouns, verbs, adjectives, and adverbs are grouped into synsets. Each synset expresses a distinct concept and is linked to other synsets by semantic and lexical relations. For example, the relations for nouns include antonym, hypernym, and three types of part-whole (part-of, substance-of, and member-of). It has also relations for verbs including antonym, hypernym, entailment, and cause.
FrameNetFootnote 1 is based on Fillmore's work and defines semantic frames and frame elements as their participants. Then, the lexical units that invoke the frame are selected. For example, the frame body movement may be invoked by a set of verbs including arch, bat, and wave, etc. In this example the core frame elements are the agent and the body part that is to be moved. An instantiation of the frame is [Mary]agent waved [he hand]bodypart. FrameNet also annotates semantics between any two concepts in the sentence and uses a set of predefined frames to be filled or instantiated.
PropBank uses the Penn TreeBank (Marcus, Santorini and Marcinkiewicz Reference Marcus, Santorini and Marcinkiewicz1994) and adds semantic annotation on top by using seventeen semantic roles. It labels the relations between a verb and its arguments. Automatic detection of semantic roles have drown considerable attention (Blaheta and Charniak Reference Blaheta and Charniak2000; Chen and Rambow Reference Chen and Rambow2003; Carreras and Màrquez Reference Carreras, Màrquez, Ng and Riloff2004; Pradhan et al. Reference Pradhan, Ward, Hacioglu, Martin, Jurafsky, Dumais and Roukos2004; Giuglea and Moschitti Reference Giuglea and Moschitti2006; Màrquez et al. Reference Màrquez, Carreras, Litkowski and Stevenson2008), and it has been proven to be useful for several applications. Among others, these are coreference resolution (Ponzetto and Strube Reference Ponzetto and Strube2006), word sense disambiguation (Dang and Palmer Reference Dang and Palmer2005), and machine translation (Wu and Fung Reference Wu and Fung2009).
There have been some recent efforts on semantic relation extraction. Probabilistic models with data mining techniques are used for both implicit relation extraction and relational pattern recognition (Culotta, McCallum and Betz Reference Culotta, McCallum and Betz2006). The SemEval-2007 Task 04 (Girju et al. Reference Girju, Nakov, Nastase, Szpakowicz, Turney and Yuret2007) and SemEval-2010 Task 08 (Hendrickx et al. Reference Hendrickx, Kim, Kozareva, Nakov, Séaghdha, Padó, Pennacchiotti, Romano and Szpakowicz2010) aimed at relations between nominals. The former examined the problem of deciding whether, for a set of seven, any given relation holds (binary classification). The latter considered the more complex problem of which relations hold for a set of nine. The main difference is that, rather than text, our approach takes relations previously extracted, and outputs more relations. It does not require modification in any tool.
Researchers have also studied how to connect concepts following chain of semantic relations. Miller and Johnson-Laird have presented the idea of composing relations that include location in their book titled ‘Language and Perception’ (Miller and Johnson-Laird Reference Miller and Johnson-Laird1976). Harabagiu (Harabagiu Reference Harabagiu1998) uses lexico-semantic connections between concepts from WordNet to derive metonymic coercions. Harabagiu and Moldovan (Harabagiu and Moldovan Reference Harabagiu and Moldovan1998) combine WordNet relations by using part-of-speech (POS) tags. From theoretical point of view, Kenny and Helbig (Kenny Reference Kenny1966; Helbig Reference Helbig2005) offer some inference axioms by using chains of relations. Winston et al. (Winston, Chaffin and Herrmann Reference Winston, Chaffin and Herrmann1987) proposed a larger taxonomy for meronymy and studied the transitivity of meronymy among inclusion relations. The term composition of semantic relations is used in conjunction with the principle of compositionality, that is, the meaning of a complex expression is determined from the meanings of its parts, and the way in which those parts are combined.
There are few studies which focus on a particular semantic relation and its combination of other semantic information. Tatu (Tatu Reference Tatu2007) studies intention in this respect. To the best of our knowledge, the different ways of combining relations have not been deeply studied. In our study, we focus on a formal method for the composition of semantic relations and use the method for augmenting spatial knowledge by doing complete composition analysis of at-location relation within a given set of semantic relations.
3 Semantic relations
3.1 Definition
Semantic relations represent the implicit associations between two concepts expressed by words or phrases. Formally, a semantic relation is denoted by rx, y, where r is the relation type and x and y are the first and second arguments, respectively. r(x, y) should be interpreted as x is r of y. The relation type dictates the nature of the association between the two arguments.
For each relation type, the first and second arguments belong to some restricted sets of concepts. In order to accommodate this restriction, we define these sets as Domain(r) for the first argument and Range(r) for the second, namely, x ∈ Domain(r) and y ∈ Range(r). For example, suppose agent(x, y) encodes x as the agent of activity y. Then, we restrict the first argument x of the relation agent only for objects that can be an agent, filtering out other objects.
A semantic relation r(x, y) is formally defined by stating the following: (i) relation type r: rx, y holds if x is r of y; (ii) Domain(r; and (iii) Range(r). This extended formal definition incorporates the sets of concepts that can appear as the first and second argument for r by Domain(r and Range(r.
In order for a relation r(x, y) to hold, the first requirement is its domain and range compatibility. Formally, r(x, y) is considered domain and range compatible iff: x ∈ Domain(r) and y ∈ Range(r). The second requirement is that the relation type encodes the association for the arguments. If the domain and range compatibility fails, then there is no point checking the relation type for the correct association.
The classification of concepts for domain and range of relations has been attempted by using POS tags (Harabagiu and Moldovan Reference Harabagiu and Moldovan1998). Although this has brought some restrictions for domain and range, it was not sufficient and was too coarse of a classification. For example, say an event can be expressed by a verb (read, play) or a noun (report, card). Consider that agent holds between a noun and a verb, noun restricting the agent and verb restricting the activity. With these restrictions, one could state that agent(pen, read) holds, which clearly should not because the domain of agent relation is the set of animate objects.
Recently, a semantic classification of entities has been proposed in order to formally define the sorts of concepts for domain and range of semantic relations (Helbig Reference Helbig2005). This classification is performed by an ontology of entities, which defines a hierarchy of sorts of concepts following a semantic criteria. For example, agent holds between animate objects (Mary, John, etc.) and situations (read, run, etc.). Therefore, it does not make sense to use inanimate objects (table, book) or abstract objects (Sunday, thought) for the domain of agent.
Defining the sorts of concepts for domain and range can have multiple advantages. For one, it can help differentiate between relations that are semantically close but have a little different concepts in their domain and range. For example, intent and purpose are very close in meaning and they both belong to the same semantic relations cluster (explained later in more detail). However, their domain and range have different sorts of concepts. Only animate objects, aco in Figure 1, can have an intent (Range(intent)=[aco]), while this restriction does not exist for purpose (Range(purpose)=[si ∪ co ∪ ntao]). Therefore, the distinction between intent and purpose can be made easier by taking into account the sorts of concepts involved.
The ontology of sorts of concepts and their acronyms.
Another advantage is to facilitate post filtering to discard the semantic relations that do not comply with the domain and range constraints. A generic semantic parser today determines the semantic relations in a text. Most parsers (Badulescu and Srikanth Reference Badulescu and Srikanth2007) achieve a relatively modest performance, typically yielding high recall but low precision. For example, consider the following sentences: (i) “John works at Starbucks for fun”; and (ii) ”John got the credit for himself”. Since both examples have the same syntactic pattern, a semantic parser would probably extract the following two relations: purpose(fun, working at Starbucks) and perpose(himself, got credit). Utilizing the defined sorts of concepts for the domain of purpose relation (Domain(purpose) = [si ∪ ntao]), it would be easy to filter out the incorrect semantic relation, as in this case himself, which is an animate concrete object, does not belong to the domain of purpose relation (aco ∉ Domain(purpose) and should not be a purpose of “getting credit”.
Sorts of concepts would also help define the rules for combining semantic relations. To combine two semantic relations, they should share at least some sorts of concepts in their domain and range. Therefore, by simply checking domain and range compatibilities, the possible valid combinations of semantic relations can be analyzed to obtain inference axioms.
3.2 The ontology
We use an ontology of entities in the definitions of semantic relations. For the upper ontology of entities, we have adapted the basic structure of an earlier proposal (Helbig Reference Helbig2005), with some modifications. The ontology of this earlier proposal covers the set of its semantic relations (Helbig Reference Helbig2005), which is a larger set than ours. Thus, we simplified the ontology for our set of relations. We also introduced extra sorts of concepts to make the differentiation between some of our relations that are close in meaning.
Figure 1 plots the modified ontology. The root corresponds to entity, which refers to all things about which something can be said (Helbig Reference Helbig2005). At the highest level of the hierarchy there are objects, situations, descriptors, quantities, and qualities.
Objects can be either concrete or abstract. The former occupy space, and are touchable and tangible. The latter are intangible, they are somehow product of human reasoning.
Concrete objects are further divided in animate and inanimate. The former have life, vigor, or spirit; the latter are dull, not enlivened. For example, John and Mary's greyhound are animate; paper and keyboard are inanimate.
Abstract objects are divided into temporal and nontemporal. The first correspond to abstractions regarding points or periods of time (July, yesterday, last month); the second, to any other abstraction (disease, weight, justice). Note that abstract objects can also be sensually perceived. For example, pain, odor, fear, and love are abstract and can be sensed.
Situation is anything that happens at a particular time and place. If a situation implies a change in the status of another entity, then it is called an event (mix, grow), otherwise a state (standing). Situations can be expressed by verbs (move, print) or nouns (party, hurricane, conference).
Descriptors complement entities by stating the properties of their spatial or temporal context. Therefore, they are divided into local/spatial (Texas, Japan, etc.) and temporal descriptors (Week, July, etc.).
Qualities represent characteristics that can be assigned to entities. These may be quantifiable, such as tall and heavy, or unquantifiable such as difficult and sleepy. For example, manner semantic relation uses Qualities to describe the way a situation occurs, manner(difficult, talk).
Quantities represent quantitative characteristics of concepts, for example, a few pounds, twenty-two yards, or two dozens.
3.3 Properties
1. Inverse: The inverse of r is denoted r−1 and can be obtained by simply switching the arguments of r. Given r(x, y), r−1(y, x) always holds. Formally, r(x, y) ↔ r−1(y, x) and (r(x, y))−1 = r −1(y, x). The easiest way to read r−1(y, x) is x is r of y and r−1)−1 = r.
2.Symmetry:r is symmetric iff r(x, y) = r(y, x).
3.4 A list of semantic relations
In this section, we depict a set of twenty-six relations we work with. We believe that the set is specific enough to cover the most frequent semantics of text without overspecialization. Several previous proposals had inspired the set. Fillmore (Fillmore Reference Fillmore1971) introduced a set of nine roles with the notion of case frames. Those include agent, experiencer, intent, object, source, goal, at-location, at-time, path. PropBank annotates seventeen semantic roles in connection with verbs (Palmer et al. Reference Palmer, Gildea and Kingsbury2005). In our set, we considered relations not only between a verb and its arguments, but also between and within noun phrases and adjective phrases. We have used some relations from WordNet (Miller Reference Miller1995), such as is-a, part-whole, and cause, but excluded some of the relations which did not occur frequently enough in our experiments (e.g., antonymy, entailment). While building the set, we have maintained the goal of capturing as much semantics as possible with as few relations as possible. The set and its similar versions have been used in Moldovan et al. (Reference Moldovan, Badulescu, Tatu, Antohe and Girju2004) and Tatu and Moldovan (Reference Tatu and Moldovan2007). Relations are clustered in a semantic way, that is, relations belonging to the same cluster are close in meaning. Working with clusters is useful for several reasons:
Helping to justify the chosen set of relations:Relations are clustered into general meanings. Most of the previous works share with us a general meaning for the relations, but the details about each particular relation may be different. Having a common ground helps comparing and mapping our relations to other proposals and previous annotation efforts.
Allowing to work with different levels of specificity: In some cases, it may be enough to just know the general meaning of the connection between the concepts. For example, if we are asked whether a certain situations 1 has a direct impact on another situations 2, it is good enough to check if any of the relations belonging to the cluster reason holds between the two situations.
Allowing to reason with the relations per cluster basis: Since relations belonging to the same cluster are close in meaning, they tend to behave similarly. This fact allows the creation of inference axioms that involve clusters instead of single relations. By doing so, the number of potential axioms is decreased.
Table 1 tabulates the set of twenty-six relations with their abbreviations and clusters.
Semantic clusters and twenty-six relations
The reason cluster includes relations between a concept having a direct impact on another:
• cause(x, y) holds if y would not hold if x did not happen. This relation can only hold between situations, since objects can be generated or created (encoded by mak), but not caused. For example, He [got a bad grade]yev because he didn't [submit the project]xev; cau(didn't submit the project, got a bad grade).
• justification(x, y) is very close to cau, it encodes a moral cause or motive. If jst(x, y), y would not hold if x did not happen and x is a moral reason or socially convened norm. The distinction between cau and jst depends on the nature of x. For example, They [do not smoke in the hall]yst because it [is forbidden]xst; jst(is forbidden, do not smoke in the hall.
• influence(x, y) encodes a weaker relation than cau(x, y). If ifl(x, y), x affects the intensity of y, but it does not affect the occurrence. An event may have several influencers. For example, [Exercising regularly]xstcan have an affect on [living a healthier life]yst; ifl(Exercising regularly, living a healthier life).
The goal cluster includes the relations intent and purpose, which are very close and sometimes it is difficult to distinguish between them. One intends to do something for a purpose, for example, “Mary intends to buy a dress to look pretty”. Both relations bring uncertainty, since having an intention or purpose does not guarantee that it will hold:
• intent((x, y) encodes intended consequences, which are volitional. Therefore, the range is restricted to animate concrete objects and it does not make sense to consider intentions for abstract objects or other sorts. Situations do not have intentions either, their agents or experiencers might. For example, The [professor]yaco's goal is to [teach students all the material]xev; int(teach students all the material, professor).
• purpose(x, y) can be defined for situations, concrete objects, and nontemporal abstract objects, it is somehow a broader relation than intent. For example, Half of the [garage]yico is used for [storage]xntao; prp(storage, garage).
The object modifiers cluster includes relations that describe attributes of objects and situations:
• source(x, y) holds if x expresses the origin of y. x could be either a physical location or a mental, information or material origin. For example, We had a great time with the [Mexican]xql [students]yaco; src(Mexican, students).
• value(x, y) holds otherwise. For example, Not all [smart]xql [kids]yaco get good grades; val(smart, kids).
The typical syntactic subjects cluster includes relations that encode links between a typical syntactic subject and a situation. The differences rely on the characteristics of the subject and the connection per se:
• agent((x, y). x must be volitional, and therefore only animate concrete objects can be part of the domain of agt. For example, [John]xaco [got married]yev last Spring; agt(John, got married).
• experiencer(x, y). x does not change the situation, only experiences. x does not participate intentionally in y either. The difference between agent and experiencer can sometimes be revealed by the nature of the event. For example, verbs such as drown, find, and occur need an experiencer, and verbs such as dive, search, and think about require an agent. His [cell phone]xico [suffered]yev some water damage at the pool party; exp(cell phone, suffered).
• instrument(x, y). x is used to perform y. x is a tool or device that facilitates y. For example, [The hammer]xico [broke]yev the window; ins(the hammer, broke).
The typical direct objects cluster includes relations encoding typical syntactic direct objects: All of them encode attributes of an event since the presence of any of these relations imply a change.
• theme(x, y) holds if x is affected or directly involved by y, y affects x somehow. For example, John [read]yev [the book]xico twice; thm(the book, read).
• topic(x, y) holds if y is a communication verb, such as talk and argue. For example, John [discussed]yev [the issue]xntao too late; tpc(the issue, discussed).
• stimulus(x, y) holds if y is a perception verb and x and stimulus that makes y happen. y makes x happen somehow.For example, John [perceived]yev [the ship]xico coming over the horizon; sti(the ship, perceived).
The association cluster includes association and kinship. In the cluster, more specific relations are preferred, if they hold and are more suitable to the situation.
• association(x, y) is a very broad relation between any pair of entities. For example, [John]xaco and [Mary]yaco work at the same company; aso(John, Mary).
• kinship(x, y) encodes a particular relation between relatives. If kinship(x, y), then association(x, y) holds. For example, [John]xaco visited [his parents]yaco for Christmas; kin(John, parents).
The rest of the relations do not fall into any particular cluster. These relations are specific and have their own unique characteristics.
• is-a(x, y) holds if x is a kind of y.
• part-whole(x, y) holds if x is part of y.
• make(x, y) holds if x makes or produces y. For example, mak(BMW, cars).
• possession(x, y) holds if y owns x. For example, [John]yaco's [truck]xico encodes pos(truck, John.
• manner(x, y) encodes the way in which a situation occurs. For example, mnr(quick, delivery).
• recipient(x, y) captures the connection between an event and an object which is the receiver of the event. For example, John [gave]yev [Mary]xaco roses and John [stole]yev [Mary]xaco's car.
• synonymy(x, y) holds if x is a synonym of y.
• at-location(x, y) holds if x is at location y. The location relation denoted by at-location in our sample set of twenty-six relations.
• at-time(x, y) holds if x is at time y.
• property(x, y) describes links between a situation or object and its characteristics. For example, pro(height, John).
• quantification(x, y) holds if y is quantitatively determined by x. For example qnt(a dozen, eggs).
4 Composition of semantic relations
The goal of composing semantic relations is to acquire new instances of semantic relations by instantiating inference axioms over already identified instances of relations. An axiom takes two semantic relations as input, called premises, and yields a third relation as conclusion. The conclusion reveals implicitly stated knowledge, building an extra layer of semantics which was neglected before. For example, given “John is in the master bedroom of his condo”, assume that a semantic parser detects, among others, the following semantic relations: at-location(John, master bedroom) and part-whole(master bedroom, his condo), but no connection between John and his condo is explicitly stated. To connect John to his condo, we compose at-location(John, in master bedroom) and part-whole(master bedroom, his condo) relations. As a result, we conclude that John is actually in his condo with a valid relation at-location(John, in his condo). In this example, we actually used an axiom which states that concepts are also located at the whole of its location, in order to infer the missing relation, at-location(John, his condo).
4.1 Formal definition
We define an axiom by using the composition operator ‘∘’. Formally, r1 ∘ r2 → r3, where r1 and r2 are the premises and r3 the conclusion. The composition function has several properties.
Relation-type compatibility: Two relations r1 and r2 are compatible iff Range(r1) ∩ Domain(r2) ≠ ∅. Let us denote Range(r1) ∩ Domain(r2) = I. Unless I = Range(r1) = Domain(r2), a restriction takes place when combining the two relations. A backward restriction takes place if Range(r1) ≠ I and a forward restriction if Domain(r2) ≠ I. In the former case, Range(r1) is reduced; in the later, Domain(r2) is reduced. For example, in thm−1(x, y) o at-l(y, z); y is forward restricted to objects [ev]×[o]; [o ∪ si]×[loc]. Another example for backward restriction is at-l−1(x, y) o thm(y, z); y is backward restricted to events as [loc]×[o ∪ si] ; [o]×[ev]. Note that one can find a forward and backward restriction with the same pair of relations.
Conclusion closure: The composition of r1 ∘ r2 → r3 is said to be closed under composition, if there exists an r3 in the set of relations where Range(r3) ⊆ Range(r2) and Domain(r3) ⊆ Domain(r1). There are restrictions for domain and range. The range restriction exists when Range(r3) ⊂ Range(r2) and the domain restriction exists when Domain(r3) ⊂ Domain(r2).
Conclusion validity: In r1(x, y) ∘ r2(y, z) → r3(x, z), r3 is semantically valid if it holds with arguments x and z. In the example of “John is in the master bedroom of his condo”, the fact that master bedroom is a part of “John's condo” semantically suggests that any concept that is in the bedroom is also in the condo, making at-location(x, y) ∘ part-whole(y, z) → at-location(x, z) composition a valid axiom.
Dominance: If r3 is one of r1 or r2 then, we talk about the dominance of any premises. r1left dominatesr2, denoted by r1 ▷ r2, iff the composition of r1 and r2 yields r1. Formally, r1 ▷ r2 iff r1(x, y) ∘ r2(y, z) → r1(x, z). r1right dominatesr2, denoted by r2 ◁ r1, iff the composition of r2 and r1 yields r1. Formally, r2 ◁ r1 iff r2(x, y) ∘ r1(y, z) → r1(x, z). r1completely dominatesr2, denoted by r1 ⋈ r2, iff r1 ▷ r2 and r2 ◁ r1. Formally, r1 ⋈ r2 iff r1(x, y) ∘ r2(y, z) → r1(x, z) and r2 ∘ r1(y, z) → r1(x, z). In general, if one only states that r1dominates r2, it should be interpreted as r1completely dominates r2.
In order to apply the composition function over r1 and r2 they must fulfill the following necessary conditions: (i) r1 and r2 must be type compatible (relation-type compatibility); (ii) r3 must be closed over the set of relations being used (conclusion closure); (iii) r3 must be a valid conclusion which holds with its premises (conclusion validity).
In principle, one could think of applying the composition for every single pair of relations. However, using the type compatibility, one can easily filter the entire spectrum of pair wise combinations to a smaller set of compatible pairs. However, there are still compatible pairs that do not result in a closed conclusion. For example, in quantification ∘ at-location → r3, quantification(qnt), at-location(atl) are type compatible relations, but they do not compose a closed relation, since there is no r3 in the relation set, where Domain(r3 ⊆ Domain(qnt) and Range(r3) ⊆ Range(at-l). Therefore, we can further filter those pairs that do not yield a closed conclusion.
It is important to note that a pair of compatible relations that yields a closed conclusion relation may not produce a valid conclusion. We call the composition that produces a valid conclusion a valid axiom. Therefore, not any given pair of compatible relations forms a valid axiom. For example, kinship and at-location are compatible and closed, but yield no valid inference. Given kin(Mary, John) and loc(John, Dallas), no relation can be inferred between Mary and Dallas. Thus, the composition is not an axiom.
An axiom r1(x, y) ∘ r2(y, z) → r3(x, z) is instantiated by the instances of premises r1(x, y) and r2(y, z) to generate a conclusion r3(x, z).
As a general rule, any instantiation of an axiom holds. However, sometimes only certain instantiations in specific contexts hold. We name such an axiom plausible axiom and denote as r1 ∘ r2 → plausibler3.
In this study, we are interested in axioms that yield strong and meaningful inferences and thus we do not count plausible axioms in the results. The goal is to find axioms that work regardless of particular instantiations of relations. At the same time, the aim is to extract concrete and narrow knowledge. In this paper, we focus on the composition of at-location and other relations.
If no relation from the given set holds between two concepts, then the relation called other holds. other is represented by the symbol ⊥. Formally, ⊥(x, y) iff ¬∃ri such that ri(x, y).
We define the inverse representation of a relation r, as r −1(y, x) = r(x, y), in short r−1, and r−1 inherits all properties of r. The inverse representation of an axiom is, then, defined as (ri ∘ rj)−1 = rj)−1 ∘ ri)−1.
Lemma 1: ri ∘ rj = (rj−1 ∘ ri−1)−1. The composition of ri and rj is equal to the inverse composition of rj−1 and ri−1.
Lemma 2: ⊥−1 = ⊥. If there is no relation from one concept to another, then there is also no reverse representation. r(x, y) = r−1(y, x); therefore, ▥−1(y, x) iff ¬∃ri−1 such that ri−1(y, x).
Lemma 3: ∀i: ⊥ ⋈ ri. The ⊥ completely dominates any relation. The ⊥ left dominates any relation; ∀i: ⊥(x, y) ∘ri(y, z) → ⊥(x, z), then ⊥ ▷ ri. Similarly, the ⊥ right dominates any relation; ∀i: ri(x, y) ∘ ▵(y, z) → ▥(x, z), then #x25A5; #x25C1; ri. Therefore, ∀i: ri ⋈ ▥.
Using the notation above, we can state the following properties:
• r is transitive iff r(x, y) ∘ r(y, z) → r(x, z).
• r is reflexive iff ∀x: r(x, x).
• r is symmetric iff ∀x, y: there exist r(x, y) and r(y, x).
4.2 Unique composition of two relations
For a given pair of relation types, r1(x, y) and r2(y, z), there are four unique combinations for composition, shown in Table 2.
The four unique axioms taking r1 and r2 as premises and yielding a valid conclusion relation r3 with a diagonal arrow
Any one of these combinations is subject to type compatibility, closure, and validity to qualify for becoming a valid axiom. We classify a pair as a compatible-pair if any one of four combinations is compatible. Similarly, we classify a pair as a closed-pair if any of its four combinations is closed under the relation set that we use.
In general, for n relations there are 
different pairs. For each pair, taking into account the two relations ri and rj and their inverses ri−1 and rj−1, there are 4 × 4 = 16 different possible combinations. Due to the property of ri ∘ rj = (rj−1 ∘ ri−1)−1, there are 
repeating compositions in this set of 16. The remaining 10 compositions are unique: (i) 4 combine r1, r2 and their inverses; (ii) 3 combine r1 and its inverse; (iii) 3 combine r2 and its inverse.
Therefore, for n relations there are 2n 2 + n potential axioms as given below:
When working with twenty-six relations, there are 1,378 potential unique axioms. Many can be discarded by the compatibility test; some compatible pairs do not yield any valid inference.
5 Composition of AT-L relation with other relations
In this section, we analyze the composition of at-l with other relations in the previously explained set of twenty-six relations (see Table 3). The analysis is done on a cluster basis.
Semantic composition of twenty-six relations with at-location relation
5.1 Compatibility of AT-L relation
If any of the arguments of cau, jst, or ifl relations is at a location, then the other argument is also at the same location (see case 1 and case 4 in Table 4). The case 2 and case 3 are not type compatible for composition. The conclusion is not valid, if both situations are having different locations that are explicitly stated.
The four axioms for at-l and reason (N/C stands for not compatible)
Examples:
• “Since John drove his car carelessly in the city, he had an accident.” The following axiom infers that the accident also happened in the city.
at-l−1(in the city, drove carelessly) ∘ cau(drove carelessly, accident) → at-l−(in the city, accident).
• “John drove his car carelessly. Because of that he had an accident on the street”. cau(drove carelessly, accident) ∘ at-l(accident, on the street) → at-l(drove carelessly, on the street). The axiom suggests that the act of driving carelessly also happened on the street.
• “They do not smoke in the restaurant, because it is forbidden.” The axiom can infer that smoking is forbidden in the restaurant. jst(forbidden, do not smoke) ∘ at-l(do not smoke, in the restaurant) → at-l(forbidden, in the restaurant).
• “They do not smoke, because it is forbidden in the restaurant.” The axiom can infer that no-smoking happens in the restaurant. at-l−1(1(in the restaurant, forbidden) ∘ jst(forbidden, do not smoke) → at-l−1(in the restaurant, do not smoke).
• “John misses classes at UTD; therefore his grades are low.” The axiom can infer that John's grades are also at UTD. at-l−1(UTD, missing classes) ∘ ifl(missing classes, low grades) → at-l−1(UTD, low grades).
Since all relations (cau, jst, ifl) in the reason cluster are close in meaning and give the same valid conclusion, we treat this composition between at-l and reason cluster, as seen in Table 4.
5.2 AT-L relation and goal cluster
If the intention int or purpose prp takes place at a location, then the concept which has the intention or purpose shares the same location (see case 4 in Table 5).
The four axioms for at-l and goal (N/C stands for not compatible and N/V stands for not valid)
Examples:
• “Professor intends to teach”; int(teach, professor). The professor may teach in the future. If the professor is at a location now or any time in the future, there is no relation between the location of the professor and the intention. However, if there is a location for the intention such as at-l(teach, in classroom), then the professor has an intention to be in the classroom and probably he will be. at-l−1(in classroom, teach) ∘ int(teach, professor) → at-l−1(in classroom, professor).
• “The purpose for a blue dress is to look pretty at the party.” at-l−1(at the party, look pretty) ∘ prp(look pretty, blue dress) → at-l−1(at the party, blue dress).
Since both relations (int and prp) in goal cluster are close in meaning and give the same valid conclusion, we treat this composition between at-l and goal.
The goal ∘ at-l composition (see case 1 in Table 5) is not valid. Since intentions occur in the future, we cannot infer that the concept and its intention should be at the same location because animate objects may change their locations with time.
5.3 AT-L relation and object modifier cluster
The val relation is type compatible with at-l in case 1; however, it is not closed under the relation set (see also Table 3). The src relation does not result in a valid conclusion, since source of a concept may not share a location.
5.4 AT-L relation and typical syntactic subjects cluster
If the animate object x is the agent (agt) for a situation y and the situation y is at a location z, then the agent is also at that location z (see case 1 in Table 6). The reverse is also valid as in case 4 of Table 6, meaning that if the agent is at a location, it means that the situation(event) is also at that location.
The four axioms for at-l and syn-sub (N/C stands for not compatible)
Examples:
• “John got married in Dallas” is encoded by following two relations: agt(John, married) and at-l(married, Dallas). Therefore, John was in Dallas at some point, at-l(John, Dallas).
agt(John, married) ∘ at-l(married, Dallas) → at-l(John, Dallas).
• “While in Dallas, John got married”; agt(John, married), at-l(John, Dallas). These statements conclude that at-l(married, Dallas).
at-l−1(Dallas, John) ∘ agt(John, married) → at-l−1(Dallas, married).
exp relation follows a similar composition with at-l. If the situation being experienced (exp) is at a location, then the experiencer is (at some point in time) at the same location.
Examples:
• “The cell phone suffered water damage in the swimming pool.”
exp(cell-phone, suffered) ∘ at-l(suffered, in the swimming-pool).
• The reverse is similarly true. The fact that “the cell-phone is in the swimming pool” and “the cell-phone experiences suffering” conclude that suffering also happens in the swimming pool.
at-l−1(swimming pool, cell-phone) ∘ exp(cell-phone, suffering) → at-l−1(swimming pool, suffering).
The ins has the same conclusion in the cluster. If the situation y, which is facilitated by the instrument (or tool) x, is at a location, then the instrument x must be at that location at some point in time.
Examples:
• “The scissors cut the paper in the house” is encoded by these two relations: ins(scissors, cutting and at-l(cutting, in the house). These two relations can give the following axiom stating the location for the tool of “scissors”.
ins(scissors, cutting) ∘ at-l(cutting, in the house) → at-l(scissors, in the house)
• The fact that scissors are in the house may mean that the cutting happens in the house.
at-l−1(house, scissors) ∘ ins(scissors, cutting) → at-l−1(house, cutting)
Since all relations (agt, exp, and ins) in typical syntactic subjects (syn-sub)cluster are close to each other in meaning and give the same valid conclusion, we treat this composition between at-l and syn-sub cluster as shown in Table 6.
5.5 AT-L relation and typical direct objects cluster
The relations (thm, tpc, and sti) in typical direct objects (drct-obj) cluster behave differently. For the composition of thm(x, y) and at-l(y, z), if the event y takes place at a certain location z, then the location for the theme x is also z. Table 7 plots the four potential compositions of the pair.
The four axioms for at-l and thm (N/C stands for not compatible)
Examples:
• The statement “John drew a graph in his room” will result in two relations: thm(graph, drew) and at-l(drew, in his room). Composing these two relations in this order will give a valid axiom:
thm(graph, drew) ∘ at-l(drew, in his room) → at-l(graph, in his room)
• The location of the theme could also infer the location of the activity that is associated with the theme. Following the same example above, if the graph is in the room, then the drawing probably happened in the room as well. Therefore, we instantiate another axiom below:
at-l−1(in his room, graph) ∘ thm(graph, drew) → at-l−1(in his room, drew)
For tpc, the conclusion is not valid. The event and the topic of the event do not share a location.
Example:
• In the statement “The topic of the talk is about cars.” The talk takes place in the classroom, but the cars are not in the class room. Therefore, the composition is not an axiom.
tpc(cars, talk) ∘ at-l(talk, in the classroom) ↛ at-l(cars, in the classroom)
Similarly, the stimulant (sti) and the event that is stimulated may not share a location, since they may be at a quite some distance.
Example:
• In the statement “John heard the train on the beach”, the fact that “John is on the beach” does not mean anything about the location of the train.
sti(train, hearing) ∘ at-l(hearing, on the beach) ↛ at-l(train, on the beach)
5.6 AT-L relation and Association cluster
In aso, being associated for a pair of concepts does not carry any locative feature. Similarly, any two concepts that are related to kinship, kin, do not share a location.
5.7 AT-L relation and other unclustered relations
The full composition of isa relation with at-l produces four valid axioms (see Table 8). Simply, both concepts of an isa relation share the same location because of its inheritance feature.
The four axioms for at-l and isa
Example:
• In a text “Rice in Houston is a research university”, we would have at-l(Rice, Houston) and isa(Rice, research university), which can be composed by the axiom in case 4 resulting below valid at-l instance.
at-l−1(Houston, Rice) ∘ isa(Rice, research university) → at-l−1(Houston, research university)
Axioms involving pw are studied under three subtypes of pw, as defined in WordNet (Miller Reference Miller1995): (i) Part, pwp; (ii) Substance, pws; and (iii) Member pwm. Most examples are from WordNet, especially the part-whole annotation and definitions. Table 9 summarizes the aggregated axioms for at-l and pw semantic composition for all subtypes. The table shows a valid axiom for a case, if at least one subtype in that case produces a valid conclusion.
The four axioms for at-l and pw (N/V stands for not valid)
Case 1: pw(x, y) ∘ at-l(y, z)
This axiom is relatively straightforward and it captures the fact that the parts, substances and members of a whole are at the same location as the whole.
(a) pwp(x, y) ∘ at-l(y, z) → at-l(x, z)
Example:
• Given pwp(horn button, car horn) and at-l(car horn, garage), then at-l(horn button, garage).
(b) pws(x, y) ∘ at-l(y, z) → at-l(x, z)
Example:
• Given pws(caffeine, coffee) and at-l(coffee, pot), then at-l(caffeine, pot).
(c) pwm(x, y) ∘ at-l(y, z) → at-l(x, z)
Example:
• Given pwm(Shiite, Shiah) and at-l(Shiah, Iran), then at-l(Shiite, Iran).
Case 2: pw(x, y) ∘ at-l−1(y, z)
The location y of an object z is the whole of a part x. The case analyzes the potential axioms for all types of pw.
(a) pwp(x, y) ∘ at-l−1(y, z) ↛ at-l(x, z)
For pwp, the fact that something is located at a whole does not necessarily mean that it is also located at a particular part of the whole.
Example:
• Maquiladora is a plant in Mexico at-l(Maquiladora, Mexico) and Acapulco is a part of Mexico as stated in WordNet pwp(Acapulco, Mexico). These two relations cannot conclude that the plant is actually in Acapulco as it may be in any part of Mexico. Therefore, we conclude that the axiom for this case does not hold.
(b) pws(x, y) ∘ at-l−1(y, z) at-l(x, z)
For substance, the conclusion is also similar and does not hold. If a whole constitutes a location for an object or situation, we cannot conclude that the substance of the whole constitutes a location.
(b) pwm(x, y) ∘ at-l−1(y, z) ↛ at-l(x, z)
The member-collection Part-Whole also does not hold. If the collection is a location for an object or situation, then there is no reasonable indication for the member to constitute a location.
Case 3: at-l(x, y) ∘ pw(y, z)
(a) at-l(x, y) ∘ pwp(y, z) → at-l(x, z)
If the location y of a concept x is part of a whole z, then x is located in z.
Example:
• In the statement “Myalgia is a pain in a muscle”, at-l(myalgia, muscle); and “muscle is one of the contractile organs of the body”, pwp(muscle, body). Therefore, at-l(myalgia, body).
(b) at-l(x, y) ∘ pws(y, z) → at-l(x, z)
If the location y of a concept x is a substance of z, then x is located in z.
In regular text, one rarely states a location which is a substance of another concept. However, from a theoretical point of view, the axiom holds.
Example:
• In the statement exostosis is defined as “a benign outgrown located on bone”, at-l(exostosis, bone). If one finds exostosis on the particular bone that is a substance of a horn, pws(bone, horn), then one can infer that at-l(exostosis, horn).
(c) at-l(x, y) ∘ pwm(y, z) → plausible at-l(x, z)
If the location y of a concept x is a member of a whole z, then x might be located in z. In this case, the conclusion is a plausible relation, since depending on the nature of the pwm the inference might not be valid. We note that the sorts of concepts involved in the pwm are the key. If they belong to different hierarchies in the ontology of sorts, the inference does not hold.
Example:
• If “a [meeting] occurs at a [restaurant]co which is a member of a particular [restaurant chain]ao”, one cannot clearly conclude that the meeting occurs in the restaurant chain. On the other hand, if a [bug] is in the oldest [tree]co belonging to the Sequoia National [Forest]co, one can state that the bug is in the Sequoia National Forest.
Case 4: at-l−1(x, y) ∘ pw(y, z)
(a) at-l−1(x, y) ∘ pwp(y, z) → plausible at-l−1(x, z)
The fact that a part y of a whole z is at a location x does not necessarily mean that z is also located at x. As a general rule, if the whole z is not larger than the location x, at-l(x, z) holds.
Positive example:
• WordNet states pwp(time-ball, timepiece). If the particular time-ball which is part of a timepiece is in an observatory, at-l−1(observatory, time-ball), then at-l(timepiece, observatory).
Negative example:
• As a counter example, given at-l−1(Panhandle, Lubbock) and pwp(Lubbock, Texas), one cannot infer that at-l−1(Panhandle, Texas), which is equal to at-l(Texas, Panhandle). In this particular case, the whole Texas is bigger than the location Panhandle; therefore, the inference does not hold. With the existence of positive and negative examples, we conclude that the axiom generates a plausible relation.
(b) at-l−1(x, y) ∘ pws(y, z) → plausible at-l−1(x, z)
pws(x, y) implicitly guarantees that x is somehow merged and not easily separable from y. y is made, among others, of x; when observing or dealing with y one sees the whole, and not the different substance it is made of. Therefore, the location of a substance determines the location of the whole.
Example:
• If at-l−1(glass, tequila) and pwp(tequila, margarita), then at-l−1(glass, margarita).
(c) at-l−1(x, y) ∘ pwm(y, z) → plausible at-l−1(x, z)
The fact that a particular member y of a whole z is at a location x does not necessarily mean that z is also located at x. Only if all the members of z are located in x, one can conclude that z is located in x.
Positive example:
• For example, biota is defined as “the plant and animal life in a particular region”, and has as members vegetation and fauna. Therefore, if at-l−1(Amazonas, vegetation) and pwm(vegetation, biota), then at-l−1(Amazonas, biota) holds.
Negative example:
• A counter example is the following. A particular professor is a member of the faculty, pwm(professor, faculty). Just because that professor is in Cancun, at-l−1(Cancun, professor), we cannot conclude that at-l−1(Cancun, faculty). The inference would be valid if all the professors were in Cancun.
The summary of all pw-related axioms can be seen in Table 10.
Summary of Axioms for part-whole in three subtypes: (1) pwp: part, (2) pws: substance, and (3) pwm: member
For mak relation, the composition produces one valid axiom (see Table 11). If a concept y makes or produces another concept z, mak(y, z) and if asry is at a location x, at-l(y, x), then z is also at the same location at least some point in time, even though the product may be transferred to some other location later on.
The four axioms for at-l and mak (N/C stands for not compatible and N/V stands for not valid)
Examples:
• If GM is located in Arlington and producing trucks, then there are trucks in Arlington, as well.
at-l−1(in Arlington, GM) ∘ mak(GM, trucks) → at-l−1(in Arlington, trucks)
• However, the reverse is not true. If the product is at a location at some point, it does not mean that the producer/maker is also at the same location.
mak(GM, trucks) ∘ at-l(trucks, in Arlington) ↛ at-l(GM, in Arlington)
For pos relation, none of the compositions produces an axiom. Animate objects (people in this case) and their possessions may not share a location; therefore we cannot conclude for the composition of at-l and pos.
Examples:
• pos(Apartment, Oscar) ∘ at-l(Oscar, in Barcelona) ↛ at-l(Apartment, in Barcelona)
• at-l−1(in Barcelona, Oscar) ∘ mak(Oscar, Apartment) ↛ at-l−1(in Barcelona, Apartment)
For mnr relation, the composition does not produce an axiom. The manner and the location of the situation do not make sense.
For rcp relation, the axiom is only plausible. It holds for some verbs where agent and the event may share a location. For example “Give”, “Receive” share a location with the agent. However, the events such as “Steal” and “Lose” may not share a location with the agent; therefore no conclusion can be made.
Positive example:
• “They give the award to Mary at the banquet.”
rcp(Mary, give) ∘ at-l(give, at the banquet) → at-l(Mary, at the banquet)
Negative example:
• “Someone stole Mary's car.” Since stealing does not have to happen at the same location as its recipient's, we have the below invalid axiom.
rcp(Mary, stole) ∘ at-l(stole, on the street) ↛ at-l(Mary, on the street)
The syn relation can compose with at-l relation in all four cases and produce valid conclusions, as shown in Table 12.
The four axioms for at-l and syn
Example:
• “Hershey is a town in Pennsylvania and Keystone State is a synonym for Pennsylvania.”
at-l(Hershey, Pennsylvania) ∘ syn(Pennsylvania, Keystone State) → at-l(Hershey, Keystone State)
The tmp relation is not closed under the given set of semantic relations (see Table 3).
pro does not share a location with the property holder; therefore, the composition does not produce a valid axiom.
The qnt relation is not closed under the given set of semantic relations (see Table 3).
6 Implementation and results
In this section, we report the results of the proposed method for the composition of at-l relation with other relations. There are three clusters and five relations that fulfill the necessary conditions of type compatibility and conclusion closure and produce valid axioms (see Table 3). We apply these axioms to annotated relations in PropBank, WordNet, and eXtended WordNet-Knowledge Base (XWN-KB) to produce new instances of relations. Then, we report the precision of these newly generated instances of relations. We use annotation from PropBank for the reason, typical syntactic subjects, and typical direct obj. clusters along with at-l relation. Following the proposed method, the implementation first searches for all the sentences in PropBank that have the two relations being composed (e.g., at-l and thm) by a valid axiom, say R1(x, y) and R2(y, z), which share a common concept y. Then it produces the conclusion R3(x, z).
For annotated and disambiguated pw relations, we use WordNet Meronymy between synsets in three subtypes: (i) Is-Part; (ii) Is-Member; and (iii) Is-Substance, which were previously discussed in Section 5.7.
For all other relations, we use annotated results from XWN-KB. XWN-KB is an upper ontology built as an extension to eXtended WordNetFootnote 2 (XWN) (Mihalcea and Moldovan Reference Mihalcea and Moldovan2001), which is derived from WordNet (WN). The novelty that XWN-KB brings is that the glosses of synsets have been transformed into semantic relations by using a reliable in-house semantic parser, and verified by human annotators. The semantic parser uses a variety of syntactic realizations to generate semantic relations. For example, knife blade contains pw(blade, knife), whereas carving knife contains prp(carving, knife); the genitive Mary's toy contains pos(toy, Mary), whereas Mary's brother contains kin(brother, Mary). Relations are also extracted from a verb and its arguments (NP verb, verb NP, verb PP, verb ADVP, and verb S), adjective phrases and adjective clauses. The semantic parser first uses a combination of state-of-the-art text processing tools, namely, part-of-speech tagging, named entity recognition, syntactic parsing and word sense disambiguation. After a candidate syntactic pattern has been found, a series of machine learning classifiers are applied to decide whether a relation holds. Four different algorithms are used: decision trees, Naive Bayes, support vector machine, and semantic scattering combined in a hybrid approach. Some algorithms use a per-relation approach (i.e., decide whether or not a given relation holds) and others a per-pattern approach (i.e., which relation, if any, holds for a particular pattern). In addition, human-coded rules are used in a small number of unambiguous cases. The semantic parser participated in the SemEval 2007 Task 4 (Badulescu and Srikanth Reference Badulescu and Srikanth2007). The result is a knowledge base that is highly interconnected. Unlike a domain-specific ontology that is based on open source information, such as news, intelligence reports, etc., XWN-KB uses definitional glosses of WordNet for its synsets.
6.1 Reason cluster
For the reason cluster, both PropBank and XWN-KB annotated relations were available for the application of the valid axioms (see Table 13). In PropBank, there were 46 sentences that have cau and at-l relations with a common shared concept, only seven of which made no sense (negative). Below are positive and negative actual sentences.
Results for LOCATION axioms
Positive: “A half-dozen Soviet space officials, in Tokyo in July for an exhibit, stopped by to see their counterparts at the National Space Development Agency of Japan.” In this example, we have below valid axiom.
cau(exhibit, stop) ∘ at-l(stop, Japan) → at-l(exhibit, Japan)
Negative: “Here, at a soccer stadium near the black township of Soweto yesterday, were eight leaders of the African National Congress, seven of whom had spent most of their adult lives in prison for sabotage and conspiracy to overthrow the government.” This example does not work for the compositional axiom below.
cau(sabotage and conspiracy, spending) ∘ at-l(spending, in prison) ↛ at-l(sabotage and conspiracy, in prison)
In this example, spending and the causing concept do not share the same location.
For PropBank, the precision achieved is 39/46 = 85 per cent. We then repeat the same exercise for WordNet and XWN-KB, and we find thirty-eight instances where at-l and reason cluster relations share a common concept in a composition. We checked all thirty-eight and found that all thirty-eight make sense, resulting in hundred per cent precision.
6.2 Goal cluster
For goal cluster, only XWN-KB annotated relations were available. There were only ninety-one cases where both at-l and a goal cluster relation (int or prp) share a common concept. We checked all ninety-one and eighty-eight made sense giving a precision of ninety-seven per cent.
6.3 Typical syntactic subjects cluster
There are 4,053 sentences in PropBank that have agent and at-location relations sharing a common concept. We randomly selected one hundred of these, and only nine made no sense (negative), resulting ninety-one per cent precision. An example sentence is given below:
“In Seoul, officials began visiting about 26,000 cigarette stalls to remove illegal posters and signboards advertising imported cigarettes”. The axiom that produces a new at-location relation is given below.
agt(officials, began) ∘ at-l(began, in Seoul) → at-l(officials, in Seoul)
A negative example comes from the rather debatable situation below:
“Lorillard Inc., the unit of New York-based Loews Corp. that makes Kent cigarettes, stopped using crocidolite in its Micronite cigarette filters in 1956.” PropBank gives these relations: agt(Lorillard Inc., use) and at-l(use, in Micronite cigarette filters)
However, the conclusion below does not make sense.
agt(Lorillard Inc., use) ∘ at-l(use, in Micronite cigarette filters) ↛ at-l(Lorillard Inc., in Micronite cigarette filters)
The reason for this axiom to result in an odd conclusion is because the “Micronite cigarette filters” was not really the location for “use”; it is indeed the location for “crocidolite”.
Similar experiment was run for WordNet and XWN-KB. There are 503 cases where at-l and all typical syntactic subjects relations share a common concept for semantic composition. We randomly selected one hundred of them and they were all correct, giving hundred per cent precision.
Despite these minor exceptions, the axiom works for the majority of the cases in the experiment, scoring on average high percentage of precision.
6.4 Typical direct object cluster
In typical direct object cluster, thm relation can compose with at-l relation (see Section 5.5). When used PropBank sentences, there are 138 sentences where at-l and thm relations share a concept. We have randomly selected one hundred, finding ninety-seven positive cases where the axiom produced a valid conclusion, scoring (97/100) = 97 per cent precision. In an example with the sentence “An exhibition of American design and architecture opened in September in Moscow and will travel to eight other Soviet cities”, we have thm(exhibit, open) and at-l(open, in Moscow). Then, we have the below axiom that produces a valid instance of a relation.
thm(exhibit, open) ∘ at-l(open, in Moscow) → at-l(exhibit, in Moscow)
We used XWN-KB for the same axioms and found 832 cases in which the two relations share a common concept. A similar random check of one hundred revealed only four negative cases, resulting in ninety-six per cent precision.
6.5 is-a relation
For case 1 (isa o at-l) of at-l and isa composition, we have the following example from XWN-KB for the concept “Tellurian” which has a gloss of “an inhabitant of the earth”. Among the relations that are encoded by the semantic parser are at-l(inhabitant, earth) and isa(Tellurian, inhabitant). These two relations can be semantically composed by the axiom of case 1 and the conclusion below can be obtained:
isa(Tellurian, inhabitant) ∘ at-l(inhabitant, earth) → at-l(Tellurian, earth)
Similar conclusion can be obtained for case 2 (isa ∘ at-l−1). In an example from XWN-KB the concept “alehouse” has the gloss “a tavern where ale is sold” having the following relations produced by the semantic parser:
isa(tavern, alehouse) and at-l(sell, tavern). Using the composition axiom, we arrive at the valid instance below, which did not exist before the application of the axiom.
at-l(sell, tavern) ∘ isa−1(tavern, alehouse) → at-l(sell, alehouse)
The experiment scored a high precision, as shown in the table. The valid axioms for all four cases are applied to isa (Hypernymy, Hyponymy) and at-l relations in WordNet and XWN-KB. We have obtained 1997 conclusive instances with a common shared concept. We randomly checked one hundred and they all made sense, as in Table 13.
6.6 part-whole relation
In this experiment, for the composition of pw and at-l, we use annotated at-l and pw relations in WordNet and XWN-KB.
In the experiment, we encountered 179 cases where the two relations share a common concept. Some of the actual examples are given in Section 5.7.
Of 179, one hundred were checked and all made sense, showing that, using the semantic composition with pw, the precision is hundred per cent.
6.7 make relation
Among all four cases, only case 4 (at-l−1 ∘ mak) has the valid conclusion for the composition of the mak and at-l relations. We did the experiment in XWN-KB and looked for the composition of case 4. Following are some actual examples. The “Ketone body” has the gloss “a ketone that is an intermediate product of the breakdown of fats in the body; any of three compounds (acetoacetic acid, acetone, and/or beta-hydroxybutyric acid) found in excess in blood and urine of persons with metabolic disorders”. The gloss has the following relations: at-l(breakdown of fats, body) and mak(ketone, breakdown of fats). These two relations can compose as in case 4 and produce a valid relation below:
at-l−1(body, breakdown of fats) ∘ mak(breakdown of fats, ketone) → at-l−1(body, ketone)
In this example, we conclude that there is ketone in the body. The problem with this composition is that although the examples are good and make sense; there are not many examples of this kind in XWN-KB; there are only eight cases overall, all of which make sense.
6.8 Synonymy relation
For the experiment, we used XWN-KB. In one example, the “Cecil Rhodes” has a gloss “British colonial financier and statesman in South Africa; made a fortune in gold and diamond mining; helped colonize the territory now known as Zimbabwe; he endowed annual fellowships for Commonwealth and United States students to study at Oxford University (1853−1902)”. From the gloss we have at-l(colonize, territory), and syn(territory, Zimbabwe) relations, which can be composed as below axiom:
at-l(colonize, territory) ∘ syn(territory, Zimbabwe) → at-l(colonize, Zimbabwe)
With the axiom, now we have a relation that states the colonization is in Zimbabwe. A different example from XWN-KB would be for the “spatterdock”. In its gloss of “common water lily of eastern and central North America, having broad leaves and globe-shaped yellow flowers; in sluggish fresh or slightly brackish water”, there is a at-l(spatterdock, brackish water) relation stating a location for the “spatterdock”, which also has very few synonyms in its synset encoded with the relations syn(spatterdock, water lily) and syn(spatterdock, Nuphar advena). Thus, the composition can result in more relations with the axiom below:
syn(water lily, spatterdock) ∘ at-l(spatterdock, brackish water) → at-l(water lily, brackish water)
During the thorough experiment in XWN-KB, we encountered 264 cases of at-l and syn relations. In a random check of one hundred, only two did not make sense, giving ninety-eight per cent precision.
7 Applications and conclusions
There are many use cases and applications that would benefit from CSR. It may facilitate inferring and common sense reasoning. TE is the task of determining if the meaning of one text is entailed, i.e., can be inferred, by another. The interest for TE has grown in recent years, mainly due to the fact that several NLP applications, such as Question Answering, Information Extraction, and Summarizing can take advantage of semantic inferences to improve their performance. The recognising textual entailment (RTE) challenge focuses on the evaluation of systems for recognizing TE. Consider the task of determining if text T entails hypothesis H; pair id=38 in RTE3 (Giampiccolo et al. Reference Giampiccolo, Magnini, Dagan and Dolan2007)
T: “Cote d'Ivoire, once a haven of stability in West Africa and the world's top cocoa producer, has been split in two since a failed coup against Gbagbo in September 2002, pitting rebels from the Muslim-dominated north against the Christian-populated south.”
H: “Cote d'Ivoire is located in Africa.”
Given T, the semantic relation at-l(Cote d'Ivoire, West Africa) can be obtained. From WordNet, we also have pwp(West Africa, Africa). Using case 3 of at-l and pw composition (see Table 9), we conclude at-l(Cote d'Ivoire, Africa). From H, the same semantic relation AT-L(Cote d'Ivoire, Africa) is extracted. We can, therefore, easily conclude that T entails H by simply matching the semantic relations from T and H.
Extending this research, other pairs of relations can also be studied under CSR, potentially enriching the overall semantics of text. For example, cause and purpose yield interesting conclusions that enrich the existing semantics of text. Another interesting improvement would be to introduce constraints for axioms that yield plausible relations. For example, one can tag a size restriction on case 4 (a) in at-l and pwp composition (Section 5.7), which states that the whole should not be larger than the location of its part for the axiom to be valid transforming this axiom from plausible to valid under a condition. This would be a good solution for the problem we mentioned in at-l(Lubbock, Texas) example earlier in this paper. The method can also be used to instantiate axioms that can be used in many other applications; for example, commonsense reasoning.
In summary, we believe that CSR offers great potential for many semantic rich processing applications since it adds more semantics that is otherwise not expressed.
