This paper is part of a project to match descriptions of real-world instances and probabilistic models, both of which can be described at multiple level of abstraction and detail. We use an ontology to control the vocabulary of the application domain. This paper describes the issues involved in probabilistic matching of hierarchical description of models and instances using Bayesian decision theory, which combines ontologies and probabilities. We have two fielded applications of this framework; one for landslide prediction and one for mineral exploration.
In many problem domains we need to match instances and models of real-world phenomena. For example, in geology, geological surveys of states, provinces and countries publish descriptions of mineral occurrences in their jurisdiction; these form the instances in one of our applications. People spend careers describing probabilistic models of where different minerals can be found. There are two main tasks we consider: • given an instance, determine which models best fits it. This would be used, for example, by someone who has the mineral rights on a piece of land and wants to know what mineral deposits may be there based on the description of the property. • given a model, determine which instances best match the model. This would be used by someone who has a model of where gold can be found, and they want to find which piece of land is most likely to contain gold, based on their model.
These models and instances are typically described by different people at different levels of abstraction (some use more general terms than others) and different levels of detail (some have parts and sub-parts and some may be described holistically). Descriptions of mineral occurrences are recorded at varied levels of abstraction and detail because some areas have been explored in more detail than others. There are some models that people spend careers in developing and that are described in great detail for those parts that the modeler cares about. Other models are less well developed, and described only in general terms. Because the instance and model descriptions are generated asynchronously, the levels of detail cannot be expected to match. We do, however, need to make decisions based on all of the information available.
This work has arisen from from an ongoing project in
which we are building decision-making tools for mineral
exploration (MineMatch) and hazard mapping
(HazardMatch). MineMatch is similar in its goals to the
Prospector expert system [
In MineMatch we work with more than 25,000 instances of mineral occurrences that are described using various taxonomies, including the British Geological Survey Rock Classification scheme1 and the Micronex taxonomy of Minerals2. We also work with more than 100 deposit type models, including those described by the US Geological Survey3 and the British Columbia Geological Survey4. Similarly, in HazardMatch we work with tens of thousands of spatial instances (polygons) described using standard taxonomies of environmental modeling such as rock type, geomorphology and geological age. To date we
2http://micronex.golinfo.com
3http://minerals.cr.usgs.gov/team/depmod.html
4http://www.em.gov.bc.ca/Mining/Geolsurv/
have worked with approximately ten models of landslide
hazards which we compare with the spatial instances.
This work is quite different to other work on combining
probability and ontologies [
Instances are things in the world. We describe instances by naming them and specifying their features (values on various properties). For example, an instance could be a particular rock outcrop, a volcano that used to exist, or apartment #103 at 555 Short St. A feature of that apartment could be that its size is large and it contains two bathrooms. Models are concepts in someone’s head that describe some phenomenon of interest. For example, someone may have a model of what rocks are likely to contain gold, a model of where landslides may occur, or a model of an apartment that Sue would be content to live in. In the system we consider here, models are named and described in terms of probability distributions over the features of an instance that manifests that phenomenon. For example, the gold model will specify the probability over the features of a particular instance that is likely to contain gold. The landslide model will specify the probability over the features for a particular location that predict whether that location is prone to landslides. The model of Sue’s apartment will specify the features that predict whether Sue would be expected to like a particular apartment.
Given an instance and a model, the aim of matching, in the context of this paper, is to determine the probability that the instance manifests the phenomenon of the model. 3
The models and instances are described at different levels of abstraction using ontologies. As part of the ontologies we assume that we have taxonomic hierarchies that specify the vocabulary for different levels of abstraction. The taxonomic hierarchy defines the hierarchical relationship between concepts. Figure 1 shows an example of a taxonomic hierarchy. A bedroom is a kind of room. A masterbedroom is a kind of bedroom. In this figure, room is the topmost class.
We do not assume that the ontologies include uncertainty about properties and relations. Ontologies are created and maintained by communities, which can agree on vocabulary, even if they do not agree on probabilities and models. room bathroom bedroom
livingroom kidsbedroom masterbedroom tvroom The ontologies provide a hypothesis space over which we can have probability distribution. We consider that probabilistic models (scientific theories) that makes probabilistic prediction about a domain will provide the uncertainty knowledge about properties and relations. 4
We adopt the OWL [
An instance is described by its value on various properties. This can include its relationship to other individuals (e.g., its parts). We, however, do not only want to state positive facts, but also negative facts such as that an apartment does not contain a bedroom, or that the kitchen is a red colour but is not a pink (without enumerating all of the non-pink red colours). Thus we will represent instance descriptions with the quadruples of form:
hindividual, property, value, truthvaluei where truthvalue is either present or absent For example, to say that an apartment has a master bedroom, but does not have a kid’s bedroom we could write: hapt1, containRoom, masterbedroom, presenti
hapt1, containRoom, kidsbedroom, absenti It is important to distinguish an instance from its description. An instance is a real physical thing that exists in the world we are reasoning about (the real world at some time, some temporally extended world, or even some imaginary world). A description is a set of quadruples. 4.2
Models describe abstract instances rather than any particular instance. For example, apartment model Apt 13 may large p1 hasSize p2 containsRoom
br1 hasType p5 containsBed
bed1 p8 hasType describe features that Sue would love to have in an apartment, e.g., she usually wants a master bedroom in her apartment5. In particular, a model describes an instance that exhibits some phenomenon. It specifies what must be in an instance, what cannot be there and what we would expect to be there.
A model describes a set of related individuals. One of these individuals is the designated top-level individual. For example, in model Apt 13 the individuals are the apartment, bedrooms, beds etc, and the designated top-level individual is the apartment.
A model is described in terms of quadruples of the form: hind, pro p, val, probi where ind is an individual, pro p is a property, val is either an individual or a class or a primitive value (depending on whether pro p is an objecttype property, or a hasType property, or a datatype property), and prob is the probability. This quadruple specifies that an instance individual that has value val on property pro p will matches the model individual ind with probability pro p.
Example The semantic network representation of part of an apartment model Apt 13 is shown in Figure 2. The nodes represent individuals, classes and data types. The top object in a semantic network represents the individual that we are talking about. The individual Apt 13 in Figure 2 is an apartment. Each arc is labeled with a probability. The value val associated with probability prob, individual ind, and arc from ind to val, labeled with property pro p, represent quadruple hind, pro p, val, probi. For example, individuals Apt 13, 5For this paper do not think of these as preferences. We could have a similar matcher for preferences, but this paper is about models of uncertainty. Think of the model of what Sue would like as the probability that she will move into the apartment and still be there after 6 months. This is, in fact, what the landlord is interested in. br1 and the arc connecting these two individuals represent quadruple hApt 13, containsRoom, br1, p2i. 5
When matching a model with an instance, we need to take into consideration the type uncertainty (because the instance and model are at varied levels of abstraction). To cope with type uncertainty, we consider that taxonomic hierarchies in the ontology are associated with probabilities. In particular, given a taxonomic hierarchy, we want a mechanism that can compute P(C j|Ck), where C j is the subClassOf Ck. This is the probability that an individual is a C j given all that you know about it is that it is a Ck. We are not considering that the probabilities associated with hierarchies are part of individual models. We are considering them as a part of super model.
In this paper we consider only taxonomic hierarchies which are trees and where we can compute P(C j |Ck), as discussed in Section 5.1. We are working on techniques for computing P(C j|Ck), when hierarchies are not trees, and where we need to consider the problem of multiple inheritance, and interdependence between subclasses. 5.1
Each class in a taxonomic hierarchy specifies a probability distribution over its immediate subclasses. That is, each link in the tree hierarchy is associated with a conditional probability. This is the probability that an individual is in a class C j, given that all you know about it is that it is in a class Ck, and that C j is the immediate subClassOf Ck. For example, the class room in the hierarchy shown in Figure 1 has a probability distribution over its immediate subclasses. Suppose we have as part of this distribution:
P(bedroom|room) = 0.3 P(bedroom|room) represents the probability that a random room is a bedroom.
Similarly, we can specify the probability of an immediate subClassOf bedroom given bedroom, with probabilities such as:
P(masterbedroom|bedroom) = 0.2 P(masterbedroom|bedroom) represents the probability that a room is a masterbedroom given all that you know about it is that it is a bedroom.
The prior probability that an individual is in a class can be computed in a recursive manner by multiplying the probabilities up in the tree. The probability that an individual belongs to root class (room) is 1 (as it represents the set of all individuals). That is, P(room) = 1. For example, given the probability as above, P(masterbedroom) can be calculated as follows:
P(masterbedroom) = =
P(masterbedroom|bedroom) × P(bedroom|room) × P(room) 0.2 × 0.3 In this representation, computing the probability that i ∈ Ck given that i ∈ Cj is linear in depth difference of Cj and Ck and otherwise is not a function of the hierarchy’s size. 6
As discussed in Section 4.2 a model describes a concrete instance that matches that model. In particular, it specifies what must be in an instance, what cannot be there and what we would expect to be there. However, a model does not specify what happens when the model doesn’t hold (as that depends on what other models there are, and the background probabilities). The role of the supermodel is to provide background information (that is beyond any model) on how likely individual—property—value triples are. In particular, the super model contains the following: • the supermodel contains the probability distribution of each class in the tree abstraction hierarchies as discussed in Section 5.1. • the supermodel contains quadruples of the form: hcl, prop, val, priori where cl is a class in the taxonomic hierarchy, prop is a property, val is either an individual or a class or a primitive value, and prior is the prior (background) probability.
That is, the prior probability that an individual of type cl has value val for property prop is available from the supermodel. For example, quadruple hroom, hasColour, “green′′, 0.4i tells us that the prior probability of a random room has “green” colour is 0.4. 7
One objective of the matcher is to rank the models or instances given instance and model descriptions. The basic problem is to match an instance with a model. When we say that a model M matches an instance i, we write M ∼ i to mean that M matches with i. Note that M is the top-level individual in the model and i is the top-level individual in the instance. We want to determine the posterior probability of M ∼ i given the i’s description, which specifies the probability that the instance i manifests the phenomenon that the model is modeling.
In general, Mk ∼ i j represents that model individual Mk matches the instance individual i j, where a model individual is one of the individuals described in the model (i.e., it is one of the first elements of a quadruple), and an instance individual is one of the individuals described in the instance description.
We cannot directly determine the match between model and instance unless we know which model individuals correspond to which instance individuals.
We use Mk = i j to denote that model individual Mk corresponds to instance individual i j and Mk =⊥ to denote that individual Mk does not corresponds to any instance individual. A role assignment is a list of correspondence statements of the forms Mk = i j, Mk =⊥ such that each Mk appears exactly once in the list and each i j appears at most once.
Note that match, ∼, does not define the role assignment. It defines the degree of match, given a role assignment. Given a role assignment, the model description defines a Bayesian network. The problem of matching a model M with an instance i reduces to computing P(M ∼ i|observation) from the constructed Bayesian network, where observation is the instance i’s description. 7.1
Given a role assignment, the semantic network defines a Bayesian network. We can construct it dynamically during the inference as follows: • there is a Boolean node Mk ∼ i j for each correspondence statement Mk = i j, where i j 6=⊥ of the role assignment. • there is a Boolean node for each correspondence statement Mk =⊥ of the role assignment, which we will write hMk =⊥i. This node will be observed with value true. • for each individual Mk in the model description and for each functional property prop such that prop is hasType or datatype, there is a random variable which we will write hMk, propi. The domain of hMk, propi is the range of property prop. • for each individual Mk in the model description and for each non-functional property prop such that prop is datatype or the range of prop is class (i.e., prop is hasType) and for each value V in the range of prop, there is a Boolean variable, which we will write hMk, prop,V i. • The probability distribution for each hMk, prop,V i node conditioned on its parent Mk ∼ i j is:
P(hMk, prop,V i = true| Mk ∼ i j = true) P(hMk, prop,V i = true| Mk ∼ i j = f alse) = = p prior where p is the probability associated with value V in the semantic network. That is, quadruple hMk, prop,V, pi exists in the model description. The prior probability prior is defined by the supermodel, i.e., quadruple hMk, prop,V, priori exists in the supermodel.
Example Consider matching the apartment model Apt 13 as shown in Figure 2 with instance apt1 defined as follows: hapt1, hasSize, “large′′i hapt1, containsRoom, R1, presenti hR1,type, masterbedroom, presenti hR1, containsBed, b1, presenti hb1,type, bed, presenti hapt1, containsRoom, R2, presenti hR2,type, room, presenti
P(hMk =⊥i = true| Mp ∼ ip = true) P(hMk =⊥i = true| Mp ∼ ip = f alse) = = 1 − p For the individual br1 of the model as shown in Figure2, 1 − prior we can have the following possible mappings: • the parent of each Mk ∼ i j node, and each hMk =⊥i node, is node Mp ∼ ip such that there is a directed edge from Mp to Mk in the semantic network (i.e., quadruple Mp, prop, Mk, prob exists in the model description). • the parent of each hMk, Pi, and each hMk, P,V i node is node Mk ∼ i j . • the probability distribution of each conditioned on its parent Mp ∼ ip is:
P( Mk ∼ i j = true| Mp ∼ ip = true) P( Mk ∼ i j = true| Mp ∼ ip = f alse) = p = prior where p is the probability associated with the individual Mk in the semantic network. That is, quadruple Mp, prop, Mk, prob is the part of the model description. The prior probability prior is taken from quadruple Mp, prop, Mk, prior that exists in the supermodel. • the probability distribution for each hMk =⊥i node conditioned on its parent Mp ∼ ip is: where p is the probability associated with the individual Mk in the semantic network. That is, quadruple Mp, prop, Mk, p is the part of model description. The prior probability prior is taken from quadruple Mp, prop, Mk, prior that exists in the supermodel. • The domain of a hMk, propi node is the range of prop. To specify the conditional probability of hMk, propi node conditioned on its parent Mk ∼ i j , we do not have the distribution over all the values of hMk, propi, rather, we have the probability for values that model cares about. The conditional probability P(hMk, propi | Mk ∼ i j is: – If the range of
P(hMk, propi | Mk ∼ i j ) is:
P(hMk, propi ∈ V | Mk ∼ i j = true)
P(hMk, propi ∈ V | Mk ∼ i j = f alse) – If prop is datatype property:
P(hMk, propi = V | Mk ∼ i j = true) P(hMk, propi = V | Mk ∼ i j = f alse) = = = = prop is class, where prob is the probability associated with quadruple hMk, prop,V, probi in the model description. The prior probability prior is taken from the quadruple hMk, prop,V, priori that exists in the supermodel. br1 = R1 br1 = R2 br1 =⊥ br2 = R2 br2 =⊥ When br1 maps to R1, we can have the following possible mappings for br2: When both model and instance have many individuals of the same types there are many possible role assignments. For the role assignment: Apt 13 = apt1, br1 = R1, bed1 = b1, br2 =⊥, the semantic network shown in Figure 2 defines a Bayesian network as shown in Figure 3.
The Boolean variable hApt 13 ∼ apt1i denotes whether prob model Apt 13 matches with instance apt1. The Boolean prior variable hbr1 ∼ R1i represents whether individual br1 of the model matches with the individual R1 of the instance. The Boolean variable hbr2, ⊥i represents whether individual br2 of the model does not map to any individual of prob instance. prior The conditional probabilities of the Bayesian network shown in Figure 3 are constructed using the supermodel and Apt 13’s description. Some of these probabilities are shown below:
P(hApt 13 ∼ apt1i = true) P(hApt 13, hasSizei = “large”| hApt 13 ∼ apt1i = true) = = p0 containsRoom large bedRoom
br1 p4 hasType p5containsBed
bed1 p8hasType softbed
+ role assignmnet: A pt 13 = a pt1, br1 = R1, bed1 = b1, br2 =⊥ br2 p6 hasType masterBedRoom p7 containsBed
bed2 hbr1, hasTypei
After constructing a Bayesian network, given a role assignment, from the semantic network, we want to compute the posterior probability of M ∼ i, i.e, P(M ∼ i|observation). The observation is the instance i’s description, which can be at different level of abstraction than M’s description. In the Bayesian network shown in Figure 3, the model individual br1 maps to instance individual R1. The model specifies hbr1,type, bedroom, p4i and instance specifies hR1,type, masterbedroom, presenti, which are at different level of abstraction. To insert the evidence in the constructed Bayesian network, we need to take this difference into consideration. In particular, we need to map the instance description to the evidence for the constructed Bayesian network. An instance description is a set of quadruples of the forms hik, prop,V, presenti, and hik, prop,V, absenti. We map the instance description to the evidence for the constructed Bayesian network as follows: • the quadruple hik, prop,V, presenti, if prop is nonfunctional, provides observation: hik, prop,V i = true for the constructed Bayesian network. • the quadruple hik, prop,V, absenti, if prop is nonfunctional, provides observation: hik, prop,V i = f alse. • the quadruple hik, prop, v, presenti, if prop is functional and datatype, provides observation: hik, propi = v. • the quadruple hik, prop, v, presenti, if prop is functional objecttype or prop is hasType, provides observation: hik, propi ∈ v. We have two cases: – If the observation hik, propi ∈ v implies “true” or “false” for the node Mp, prop , such that Mp = ik exists in the role assignmnet, we do the normal (usual) conditioning in the Bayesian network. – If the observation hik, propi ∈ v does not imply “true” or “false” for the node Mp, prop , such that Mp = ik exists in the role assignment (i.e, v is the superclass of value V of Mp, prop ), we provide soft evidence for the node Mp, prop in the constructed Bayesian network.
For the soft conditioning, we create an observed child hMk, propi of Mp, prop , Mk is the same type as Mp. We observed hMk, propi ∈ v. The conditional probability of hMk, propi ∈ v is: P(hMk, propi ∈ v| Mp, prop ∈ V ) P(hMk, propi ∈ v| Mp, prop 6∈ V ) = = 1.0 P(v|¬V ) Using Bayes rule, probability P(v|¬V )can be computed as follows:
P(v|¬V ) =
P(v) − P(V )
1 − P(V ) where P(v) and P(V ) are the probabilities of classes v and V respectively. We can compute P(v) and P(V ) using the probabilities associated with the abstraction hierarchies6 as discussed in
Section 5.1.
We can compute the posterior probability of match, P(M ∼
i|observation), from the constructed Bayesian network
using any standard inference algorithms, e.g., VE [
In this paper, we have proposed a framework for decision making in rich domains, where we can describe the observations (or instances) in the world at multiple levels of abstraction and detail and have probabilistic models at different levels of abstraction and detail, and be able to use them to make decisions. We can build knowledge-based decision tools in various domains such as mineral exploration and hazard mappings, where we need to have probabilistic reasoning and rich ontologies.
Rita Sharma was partly supported by a MITACS Postdoctoral fellowship.