Partial knowledge about geospatial categories is critical for knowledge modelling in the geospatial domain but is beyond the scope of conventional ontologies. Degree of overlaps between geospatial categories, especially those based on geospatial actions concepts and geospatial enitity concepts need to be specified in ontologies. We present an approach to encode probabilistic information in geospatial ontologies based on the BayesOWL approach. This paper presents a case study of using road network ontologies. Inferences within the probabilistic ontologies are discussed along with inferences across ontologies using common concepts of geospatial actions within each ontology. The results of machine-based mappings produced are verified with human generated mappings of concepts.
Ontologies, which allow the use of probabilistic representation of categories, are under increasing focus [1]. Reasoning mechanisms using such probabilistic information, which not only allow inferring equivalent concepts but also the ‘most similar’ or the ‘least similar’ concepts are best suited for practical use of ontologies. Support for such mechanisms can also be found in cognitive sciences, which assume conceptual spaces to denote a concept [2] and distances between such spaces to explain the notion of similarity between two concepts [3]. Cognitive basis for the specification of geospatial ontologies have been favoured by many researchers [4]. However, current work in geospatial ontologies does not provide sufficient insight into the use of probabilistic knowledge in ontologies. Although mechanisms to specify such information have already been attempted, for the semantic web [5], such probabilistic ontologies have not been explored inside the geospatial domain.
This paper aims to explore this gap and illustrates the use of probabilistic ontologies in the geospatial domain. We employ the approach of BayesOWL [5] to specify probabilistic geospatial ontologies primarily related to road network entities. While we draw extensively on the ideas of BayesOWL, our work mainly concentrates on (1) extracting and using probablistic information in geospatial ontologies, (2) Inferences across geospatial ontologies based on the assumption of geospatial action concept names, and (3) its applicability to enabling semantic reference. The use of probabilistic geospatial ontologies for practical tasks of semantic translations is the main contribution of this paper.
Existing literature in geographical information science points out the significance of geospatial ontologies as tools to represent conceptualizations in the geospatial domain. Such knowledge representation tools are mostly used to resolve semantic differences and promote interoperability between applications across information communities [6].
Agarwal [7] has discussed that a unified approach to ontology specification in the geospatial domain does not exist. Different approaches including the approaches of formal ontologies [8] and algebraic approaches [9], Rüther et al. [10] have evolved in parallel to the conventional approaches of Description Logic (DL) based specifications. Geospatial ontology engineering has been also proposed to enable a supportive environment for knowledge representation in the geospatial domain [11]. However the challenges for geospatial ontologies as tools of knowledge representation remain unresolved to a large extent. The primary questions that need to be answered include the following: · Gomez-Perez and Benjamins [12] have stated that the number of ontologies specified is not large enough for their use in practical and industrial scale applications. This is true for the geospatial domain and practically verified ontologies are still to be produced. In their absence it is impossible to verify their utility and hence their contributions to semantic interoperability. · With a similar point of view, it has been discussed that the tools and principles of ontologies are still viewed with skepticism even after years of research. Agarwal [7] has pointed out that geographic concepts and categories have inherent indeterminacy and vagueness; especially that emerge from human reasoning and conceptualization. It is therefore unlikely that the semantic ambiguities can be resolved without accounting for the uncertainty factor. · Geospatial ontologies have either looked at geographic space either from the point of view of the geospatial entities with it or from that of geospatial actions. A unified view, which incorporates knowledge of geospatial actions in ontologies of geospatial entities and which treats both these components of knowledge as equally important, is necessary. Kuhn [13] advocates the inclusion of actions and affordances in geospatial ontologies.
Geospatial ontologies are in need of innovative approaches to ensure their practical use. In order that geospatial conceptualizations can be encoded in ontologies, emerging techniques in ontological specifications and knowledge representation need to be adapted and experimented in the geospatial domain. These include probabilistic ontologies and inclusion of knowledge about geospatial actions and their hierarchies [14]. 2.1
We have already mentioned that uncertainties are abundant in categories of geospatial entities. Zhang and Goodchild [15] state “…and in the face of fuzziness, Boolean logic is surely less versatile in dealing with discourse that is full of heuristic metaphors, linguistic hedges and other forms of subjectivity”. One of the arguments against knowledge engineering based on conventional ontologies has been against the use of rigid categories as opposed to partial, incomplete, or probablistic categories of the real world. It is also important to note that differences between such real world categories are measurable in terms of a similarity (or a dissimilarity) score. As opposed to crisp, binary classification of instances into a certain geospatial category, it is usual to express the relative suitability of an instance to a category (such as Road) in comparison to others (say, Motorway). Note that the definition of the category itself is precise but there is only a probability, given the current knowledge about inclusions and overlaps between categories that a certain instance fits into a certain category. Although there is a tendency to associate probablistic cateogories with natural geospatial entities we need to note, that since our categories are precise, using examples of man-made entities from the transportation domain is appropriate as well.
To comprehend the notion of uncertainity or partial information, which we attempt to address it, is important to understand that there are overlaps between categories modelled within an ontology. For example, while modelling concepts of a road network ontology (shown in Fig 1), besides knowing that a class FootPath Figure 1 (a) Representation of five classes of a road network ontology. While Highway and Street are subclasses of Road, Footpath is a subclass of Path. Evidently this representation shows that Highway and Footpath are small subclasses of Road and Path respectively. Street has a major overlap with Path allthough it is not a subclass. (b) Representation of the five classes as a subsumption relation in a conventional ontology (note that in this diagram, arrows point to the subclass). is a subclass of class Path, one may also know and wish to express that “Footpath is a small subclass of the class Path”; or in another case where a class Street and Path are not logically related, one may still want to say that “Street and Path are largely overlapped with each other”. Users of ontologies would therefore like to know how close is a Street from a Road or a degree of similarity between Road and Street. Such tasks are beyond the scope of conventional ontologies [5], as partial knowledge is ignored as shown in the subsumption hierarchy of figure 1(a). Therefore, a mechanism to specify probabilistic ontologies and carry out reasoning tasks on them is also critical for practical use of geospatial ontologies.
Probabilistic specifications have a strong relation in the context of using affordances and functions of geospatial entities in ontologies. The concept of categorization of manmade geospatial entities such as roads and road network components is closely associated with the functions or actions that they afford. Often, the association of such functions with certain entities is not deterministic and context sensitive. However, based on personal experience, humans are able to provide a relative value of the association between an entity and a function. Thus a Motorway is more strongly associated to the function of driving as compared to a Street or a Path. At the same time, we can argue that Driving is not associated to Footpaths. In a probabilistic ontology framework, the associations between entities and functions can be specified as probabilistic linkages. The overlaps of categories such as Road or Footpath and things that afford driving as shown in Figure 2 below are such links and we attempt to use such overlaps in probabilistic ontologies.
It is important to note that translation of meanings of symbols used to represent certain entities between two agents is directly related to the affordances of the entities with respect to different geospatial actions. Affordances and functions are always in relation to a certain agent and its goals [16]. This requires that the mapping of functions and entities be updated on the basis of the context in hand. Our framework seeks to provide a mechanism for flexible translations based on reviseable probabilistic values of enitity-action linkages in a given context. Such mechanisms to specify contexts are critical for enabling pragmatics as discussed by Brodaric (2007).
PR-OWL [1] and BayesOWL [5] are two approaches that use a BN based representation of ontologies. Of these, BayesOWL provides an approach for specification and reasoning.
Ding et al [5] developed a mechanism of expressing OWL ontologies as Bayesian networks termed as BayesOWL. The important steps to construct such ontologies are as below: Construction of the Directed Acyclic Graph (DAG): The entity classes to be used are listed first and the topmost (most universal) concept is added to the top of the DAG as a node. Child concepts of this concept are added below the parent concept as individual nodes and the complete DAG is created by constructing the links. Each node has only 2 states (True, False) Regular Nodes and L Nodes: The nodes created above are called Regular nodes.
There are another category of nodes called L Nodes, which help in constructing Union, Intersection, Disjoint and Equivalent relationships. Since we do not use any of these relationships in our ontologies we shall ignore construction of L Nodes. Allocating conditional probabilities: Regular nodes (other than the top node) have one conditional probability value each for its parent node. It is suggested that such conditional probability values are learnt from text classification techniques. We use the relatedness values from WordNet similarity modules to derive these values. Applying IPFP iterations to impose P Space: Finally with given CPT values it is important for the network to learn the real values given the probability constraints to arrive at a condition where all LNodes are true. This is achieved by an Iterative Proportional Fitting Procedure (IPFP) [17]. In case there are no L Nodes to be considered, this iterative step can be overlooked.
The principal reasoning tasks in our Bayesian network are based on computation of joint probability distributions and utilize the three methods suggested by Ding et al[5]. These are: · Concept Satisfiablity: if a concept based on certain states of given nodes in the network can exist. This is defined by verifying if P (e|t) = 0, where e is the given concept. For example already as discussed in § 1.2, given that a concept belongs to Motorway (thus P(t)=1) it cannot be a member of “Entities that afford walking” P (e|t) = 0 . Hence a concept of a Motorway, which affords walking, is not satisfied as per the representation in Figure 2. · Concept Overlap: the degree of overlap between a given concept and any other concept in the network is determined by P (e|C,t). Thus in Figure 2 we see that the overlap between Road and “Entities that afford walking” is significant whereas overlap between Motorway and the later is null. · Concept similarity: The advocated measure of similarity is based on Jaccard coefficient provided by Rijsbergen [18]. This measure is the ratio of the probability that an instance of the top level concept is a member of either of the two classes, with respect to the probability that the instance is a member of both the classes. The value ranges from 0 to 1. To demonstrate this if we assume that the overlap between classes as shown in figure 2, we know that the probability that an instance is a Motorway given that it is a Road is P(C|e); given that the likelihood that any instance of a road network entity (i) is a Road (say P(e)) (ii) is a Motorway (say P(C) . The similarity between the two concepts is equal to MSC(e,C) = P(e Ç C) / P(eÈC). (2)
= P(e,C) / (P(e) + P(C) – P(e,C)) In case one of the classes is a subclass of the other, as in the case of a Road and a Motorway, the value of P(C,e) turns out to be 1 since any instance of Motorway is also an instance of Road. Thus in this case M SC (e,C) = 1 and MSC(e,C)=P(e)/P(C) which means that most similar concept among subclasses of a given class is its most specific subsumer. On the other hand, if P(C,e) = 0 for any case (and hence MSC(e,C)=0), it means that the two concepts are most disimilar. We use these equations extensively for our case studies and for further clarification of the computations the reader may refer to the explaination of BayesOWL [5].
Traffic code texts such as the Highway Code of UK1 (HWC) and the New York Driver’s Manual2 (NYDM) are examples of formal texts, which not only mention the entities in a road network but also specify the permissible actions in the respective geographic jurisdiction. Kuhn has advocated the extraction of ontologies from such formal texts. Our case study involves the extraction of such ontologies from each of these traffic codes. We extract most frequently occurring entities and construct hierarchies of such entities. We also extract most frequently occurring actions in relation to these entities and construct hierarchies of actions as well. A further text analysis provides co-occurrence values of entity-action pairs, which are used to establish linkages between entities and their actions. 1 www.highwaycode.gov.uk/ 2 http://www.nydmv.state.ny.us/dmanual/
In this section we discuss the extraction of probabilistic ontologies based on the text analysis. We also discuss the inferences obtained from such ontologies as opposed to conventional ontologies. It is important to note that the extraction of ontologies in this case is based on linguistic analysis and although analysis of formal texts is suggested to be a good source for building ontologies, our main purpose is to demonstrate the use of a probabilistic framework for geospatial ontologies. It is to be noted that linguistic analysis is not the cornerstone of our framework for probabilistic ontologies; rather, it serves as one of the tools, which assists in building such ontologies. Nevertheless, simplistic ontologies (as Directed Acyclic Graphs) have been developed from analysis of formal texts and we further the same methodology by using probabilistic values in the place of binary values for affordances of different road network entities. 3.1
The steps listed in § 2.1 are used to construct the BN based ontologies. The important constituents required for these are extracted from the text as follows. 1. Both texts are subjected to a Part Of Speech (POS) analysis which not only analyze the part of speech but also provides the sense of the words [19]. 2. The most frequently occurring entities are used to construct a hierarchy of geospatial entities using hypernyms relations of noun terms from the WordNet lexicon [20]. 3. Similarly hierarchies of geospatial action terms are used to construct the hierarchy of actions. Hypernym relations between verbs are used to construct such hierarchies. 4. WordNet-similarity modules [21] are used to extract the conditional probabilities between class and subclass relations in the two hierarchies. The CPTs thus obtained allow us to construct individual BayesOWL ontologies of entities and actions separately. 5. We go beyond this step by using the linkages between noun-verb pairs from the text analysis to link the two hierarchies together. A table of enitity concepts along with their assesed values of affordance for the given geospatial action concepts is used. The combined DAGs from the two texts are represented in figure 3 and 4 respectively. We need to clarify that the node denoting action concepts, when used in a combined DAG, represents the class of road network entities, which afford that particular action. Since the top concept for action concepts is move, we assume the top concept to be “all road network entities which afford the action move”
The main purpose of our experiments was to evaluate the utility of the developed Bayesian network based ontologies to carry out inferencing tasks for our case study.
Given the Bayesian network ontologies as shown in figure 3 and 4, we now proceed to determine the most similar matches and most dissimilar matches within the same ontology. This is done using the notion of concept similarity described in § 2.2. We try to obtain the action concept matches in relation to the entity concepts. Table 2 depicts the results.
Finally we arrive at the bigger and more practical task of reasoning across ontologies. Since our two texts have differences in the list of geospatial entity concepts (the Highway code contains mention of Footpath and Motorway whereas the NY driver’s manual mentions Crosswalk and Expressway, our task is to obtain the degree of overlap between these two concepts and the most similar concepts given their linkages with the common function concepts. To do this, we make an assumption that action concepts remain invariant across the ontologies such that the meanings of walk or drive remain the same (although the meaning of a Road and a Highway can differ). We create a virtual node for each node of the given ontology in the target ontology based on its conditional probabilities in respect to the action concepts (common to both ontologies). Thereafter we obtain the most similar and most dissimilar concepts based on the approach already used in § 3.2.1. Table 3 lists these top matches obtained from the two BNs.
We have already stated that a simplistic evaluation of the machine based values of similarity and hence the mapping between concepts of two ontologies is not appropriate. This section explains human subjects testing based on the first case study and tries to compare the results of the machine based mappings vis-à-vis human generated ones. 4.1
Human subject testing was conducted for 20 participants who were native English speakers or were highly proficient speakers and long-term residents of Englishspeaking countries. Participants were given two sets of cards, which had names of road network entities from each ontology (the Highway Code and NY Driver’s Manual). The cards bearing names of Highway Code concepts were arranged in one row. Participants were asked to arrange the cards bearing NY Driver’s Manual concepts in such a way that the entities that they believed were most similar were kept closest. After this task was completed, they were asked to flip the cards and read the sections of the texts relevant to the respective entities, which occurred in the corresponding traffic code texts. These sections provided information about the different actions that were permissible on that particular road network entity. After taking as much time as they needed to read the cards, participants repeated the matching task.
The mappings generated before and after flipping the cards (and hence before and after the knowledge about entity functions was available) were recorded and analyzed. The tests took not more than 20 minutes and were administered with no interference once the initial instructions were given. All 20 participants volunteered willingly and were debriefed at the end of the tests. 4.2
by subjects who have driven in both countries was found to be slightly lower than those who have driven only in one but this was fairly insignificant (0.09).
We have already discussed that there is a close resemblance in the machine based mappings and the human based mappings although they are not identical. It is possible to report precision and recall of the mappings in terms of false positives (when a true match is overlooked) and false negatives (when a incorrect match is reported), using a unique name assumption (assuming that entities which have same names in both ontologies are the same entities). This is not a good evaluation of the performance of the machine based mapping because naming heterogeneity is abundant in most cases. For example, the term Highway is used differently in the HWC and the NYDM and this is concurrent with the use of the word in the two countries as well. This is also evident from the results of our human subject tests. Thus evaluation of machine-based mappings warrants the use of human subjects testing to ascertain the goodness of the results.
The Graph 2 (below) compares the precision and recall values based on the unique name assumption and on the mappings produced by the human subject tests. The recall value remains the same (mainly due to the mismatch of the entity Street in the machine-based mappings). However recall has been shown to improve.
The use of probabilistic geospatial ontologies for mappings between most similar entities mimics, to a large extent, the human mechanism of semantic translations of entity names. Our results provide support to the hypothesis that knowledge about geospatial actions and affordances to such actions are a critical part of geospatial knowledge.
This is only a first step in our experimental validation and our experience has shown that there exist many themes for future work. These include (1) Inclusion of Disjoint, Equivalent, Intersection and Union relations: For simplification of our case study these relations were avoided although these relations can be easily determined from WordNet during text analysis. Using such relations in future will require use of some iterative algorithm such as Decomposed IPFP in order to enforce truth conditions of the LNodes in BayesOWL [17]. (2) Testing on industrial scale: this experiment, although at a prototype scale aims, in the end, to solve semantic problems, which occur at industrial scale. (3) Machine based learning: The human mappings, especially that of the experts, are considered as the ideal mappings. Human interactions and judgments for most similar concepts can be used to improve heuristics involved in specification of entity-action linkages.
The work presented in this paper was funded by Ordnance Survey, UK. Coments from three anynomus reviewers helped to improve the paper to its present form. The author is also thankful to members of MUSIL for their inputs. 18. 19. 20. 21.
Rüther, C., W. Kuhn, and Y. Bishr. An algebraic description of a common
ontology for ATKIS and GDF. in 3rd AGILE Conference on Geo
Klien, E. and F. Probst. Requirements for Geospatial Ontology Engineering. in Conference on Geographic Information Science (AGILE 2005). 2005. Estoril, Portugal.
Gomez-Perez, A. and V.R. Benjamins, Knowledge Engineering and Knowledge Management. Ontologies and the Semantic Web - 13th International Conference, EKAW 2002 (LNAI 2473). 2002: Springer-Verlag Heidelberg.
Kuhn, W., Ontologies in Support of Activities in Geographic Space. International Journal of Geographical Information Science, 2001. 15(7): p. 613-631.
Sen, S. and K. Janowicz. Semantics of Motion verbs. in Workshop on Spatial Language and Dialogue (5th Workshop on Language and Space). 2005. Delmenhorst, Germany.
Zhang, J.X. and M. Goodchild, Uncertainty in Geographical Information. 2002, Taylor and Francis: New York.
Norman, D., Affordance, Conventions, and Design. Interactions, 1999(May + June): p. 38-42.
Peng, Y. and Z. Ding. Modifying Bayesian Networks by Probability Constraints. in 21st Conference on Uncertainty in Artificial Intelligence (UAI-2005). 2005. Edinburgh, Scotland.
Rijsbergen, V., Information Retrieval. 2nd ed. 1979, London: Butterworths. Decadt, B., et al. GAMBL, Genetic Algorithm Optimization of MemoryBased WSD. in Third International Workshop on the Evaluation of Systems for the Semantic Analysis of Text (Senseval-3). 2004. Barcelona, Spain. Miller, G., Wordnet: An Online Lexical Database. Int. Journal of Lexicography, 1990. 3(4): p. 235-312.
Patwardhan, S. and T. Pedersen. Using WordNet Based Context Vectors to Estimate the Semantic Relatedness of Concepts. in EACL 2006 Workshop Making Sense of Sense - Bringing Computational Linguistics and Psycholinguistics Together. 2006. Trento, Italy.