Probabilistic Graphical Models (PGMs) are powerful tools for representing and reasoning under uncertainty. Although useful in several domains, PGMs su er from their building phase known to be mostly an NP-hard problem which can limit in some extent their application, especially in real world applications. Ontologies, from their side, provide a body of structured knowledge characterized by its semantic richness. This paper proposes to harness ontologies representation capabilities in order to enrich the process of PGMs building. We are in particular interested in object oriented Bayesian networks (OOBNs) which are an extension of standard Bayesian networks (BNs) using the object paradigm. We show how the semantical richness of ontologies might be a potential solution to address the challenging eld of structural learning of OOBNs while minimizing experts involvement which is not always obvious to obtain. More precisely, we propose to set up a set of mapping rules allowing us to generate a prior OOBN structure by morphing an ontology related to the problem under study to be used as a starting point to the global OOBN building algorithm.
Knowledge representation (KR) is one of the principal areas of Arti cial Intelligence which was studied by di erent techniques coming from various disciplines. In this work we will focus on probabilistic graphical models and ontologies which are considered within the most e cient frameworks in KR.
Probabilistic graphical models (PGMs) provide an
efcient framework for knowledge representation and
reasoning under uncertainty. Ontologies allow
logical reasoning about concepts linked by semantic
relations within a knowledge domain. Even though they
represent two di erent paradigms, PGMs and
ontologies share several similarities which has led to some
research directions aiming to combine them. Concern
for the majority of them was to extend ontologies in
order to support uncertainty. This is either by adding
additional markups to represent probabilistic
information or by mapping the ontology into a PGM in order
to enrich ontology reasoning with probabilistic queries.
Few works intend to construct PGMs using ontologies.
In this area, Bayesian networks (BNs)
We are in particular interested in object oriented
Bayesian networks
The remainder of this paper is organized as follows: In sections 2 and 3 we provide a brief representation of our working tools. In section 4, we show how to bene t from knowledge provided by an ontology to de ne the structure of an OOBN. In section 5 we represent a survey on existing approaches trying to nd a combination between PGMs and ontologies. The nal section summarizes conclusions reached in this work and outlines directions for future research. 2
Probabilistic graphical models (PGMs) provide an e
cient framework for knowledge representation and
reasoning under uncertainty. In the literature, we
distinguish a panoply of PGMs sharing two common
components: a graphical one (i.e. a set of nodes and
links) and a numerical one allowing the quanti
cation of di erent links de ned in the graphical
component via probability distributions. Among the most
used PGMs we can mention Bayesian networks (BNs)
HT is the set of internal nodes including instantiations of classes which do not contain instantiations of T . They are protected nodes that can't have parents or children outside t.
OT is the set of output nodes. They are nodes from the class usable outside the instantiations of the class and they can not have parents outside t. An output node of an instantiation can be a reference node if it is used as an output node of the class containing it.
Internal nodes, which are not instantiations of classes, and output nodes (except those that are reference nodes) are considered as real nodes and they represent variables. In an OOBN, nodes are linked using either directed links (i.e., links as in standard BNs) or reference links. The former are used to link reference or real nodes to real nodes, the latter are used to link reference or real nodes to reference nodes. Each node in the OOBN has its potential, i.e. a probability distribution over its states given its parents. To express the fact that two nodes (or instantiations) are linked in some manner we can use construction links ( ) which only represent a help to the speci cation. When some classes in the OOBN are similar (i.e. share some nodes and potentials), their speci cation can be simpli ed by creating a class hierarchy among them. Formally, a class S over (IS ; OS ; HS ) is a subclass of a class T over (IT ; OT ; HT ), if IT IS ; OT OS and HT HS .
Example 1. Figure 1 represents the insurance
network adapted to the OOBN framework
Age T:Theft
CO:CarOwner C:Car
A:Accident
D:Driver
stands for probabilistic inference and this requires to
translate the OOBN into a BN or a multiply sectioned
Bayesian network (MSBN)
In this paper we are interested in the learning process.
The standard approach proposed by
Over the last few years, there has been an
increasing interest in the application of ontologies in
various domains (e.g., linguistics, semantic web,
bioinformatics). They represent not only a xed structure
but also the basis for deductive reasoning. For the
AI community, an ontology is an explicit speci cation
of a conceptualization
Cp = fcp1; : : : cpng is the set of n concepts (classes) such that each cpi has a set of k properties (attributes) Pi = fp1; : : : pkg.
R is the set of binary relations between elements of Cp which consists of two subsets:
Loan Amount Decision
Couple Total income
NbChildren constituted of
constituted of requests Man Military service is-a
Woman Maiden name
is-a
Person Name Age Salary
Employment { HR which describes the inheritance relations among concepts. { SR which describes semantic relations between concepts. That is, each relation cpisRcpj 2 SR has cpi as a domain and cpj as a range.
I is the set of instances, representing the knowledge base.
A is the set of the axioms of the ontology. A consists of constraints on the domain of the ontology that involve Cp, R and I.
Axioms are of the form A B (A and B are equivalent), R1 R2 (R1 is a subproperty of R2), R1(x; y) (x is related to y by the relation R1), A(x) (x is of type A), etc. Where A and B are concepts, R1 and R2 are relations and x and y are instances. Example 2. Figure 2 is an example of a joint credit ontology.
Cp = fLoan; Couple; M an; W oman; P ersong. For instance PLoan = fAmount; Decisiong. SR = frequests(Couple Loan), constituted of(Couple M an), constituted of(Couple W oman)g. Is-a relations represent HR and are equivalent to subsumption axioms, e.g., Man Person. For instance, we can have an instance p of the concept Man p fP aul; 30; 2000$; teacher; T g, p.Name = Paul, p.Age = 30, p.Salary = 2000$, p.Employment = teacher and p.Military service = T. 4
Clearly PGMs and ontologies share several similarities even they are derived from di erent frameworks. Thus our idea is to use the ontological knowledge in the OOBN learning process by morphing the ontology in hand into the a prior OOBN structure. To this end, we rst de ne the common points and similarities between these two paradigms, then we describe the main steps of our proposal. 4.1
In this part, we highlight the common points and similarities between ontologies and object oriented Bayesian networks. The main components of an ontology (i.e., concepts and relations) may be viewed as a start-up to de ne the main components of an OOBN (i.e., classes and relations among them).
Ontology concepts are translated into classes of the OOBN framework. Hence, for each class so de ned, concept properties will constitute the set of its random variables (real nodes). It is clear that the set of the concept properties does not cover the three sets of nodes of a class. Let: { cpi be the concept of the ontology translated to the class ci in the underlying OOBN, where ci is a DAG over Ic; Hc and Oc. { Pi = fp1 : : : pkg be the set of properties of cpi. { Hc0 = Hc n Hc inst is the set of ininst, where Hc ternal nodes which are instantiations of other classes. { Oc0 = Oc n Ocref , where Ocref is the set of output nodes which are reference nodes. Pi allows us to generate Hc0 [Oc0. Reference nodes, namely, Ic [ Ocref , are pointers to nodes de ned in other classes. Consequently their set of states as well as parameters are copied from the referenced nodes. These latter are properties of other concepts in the ontology side. Reference nodes as inst will be derived from the semantic well as Hc relations.
As ontological inheritance relations already model a hierarchical feature, then all concepts connected by an is-a relation in the ontology will be represented by a class hierarchy in the OOBN framework.
Having two concepts fcpi; cpj g 2 Cp2 related by a semantic relation means that there is at least one property of one of them that a ects at least one property of the other, which means that the definition of one of them depends on the existence of the other. In the underlying OOBN, this allows to set up dependencies among nodes from di erent classes. Suppose that the property pk of concept cpi a ects the property pk0 of concept cpj . Then, the node that represents pk in the class ci will be either an output node connected directly using directed links to the internal node representing pk0 in the class cj , in this case cj could only be an encapsulating class of the instance of ci, or an output node referenced, using reference links, by a reference node in the class cj , this reference node is either an input node, parent of the node that represents pk0 in cj or an output reference node of the class containing an instance of ci and communicates with cj .
Semantic relations might provide an information about classes interfaces and instantiations organization in the OOBN. However, the link direction of the semantic relation can not provide a good informer about dependence relations among the variables of the OOBN, which variable depends on the other? So, it is required that the semantic relations be designed from the beginning of a causal or an anti-causal orientations. The choice of a xed orientation is a determining factor to specify which instantiation Ii could be referenced from an instantiation Ij . Suppose that all semantic relations are of causal orientation, the cause is then conceived as the direct explanation of the fact and it is involved in its production. consequently, the de nition of the concept range depends on the existence of the concept domain. In the OOBN side, this means that the de nition of the class representing the concept domain is part of the class representing the concept range. This can be translated in the OOBN by instantiating the class representing the concept domain within the speci cation of the class representing the concept range.
In what follows, we assume that all semantic relations have a causal orientation. Thus, 8 fcpi; cpj g 2 Cp2 related by a semantic relation, where cpi is the domain and cpj is the range, cpi is considered as the cause of cpj and this latter is the e ect.
In fact, the ontology conceptual graph is simply the result of the ontology components de nition. Thus, we require that semantic relations de nition to be, from the beginning, done following a causal reasoning that is considered as an intuitive re exion of the ontologist. Then, if we require to have all semantic relations to be anti-causal, we just have to reverse their de nitions (i.e., de ne the domain as range and vice versa). 4.2
To ensure the morphing process, we need to traverse the whole ontology. To provide this, we assume that the ontology is a directed graph whose nodes are the concepts and relations (semantic and hierarchical ones) are the edges. Our target is to accomplish the mapping of the ontology graphical representation into an OOBN while browsing each node once and only once. To this end, we propose to adapt the generic Depth-First Search (DFS) algorithm for graph traversing. The idea over the Depth-First Search algorithm is to traverse a graph by exploring all the vertices reachable from a source vertex: If all its neighbors have already been visited (in general, color markers are used to keep track), or there are no ones, then the algorithm backtracks to the last vertex that had unvisited neighbors. Once all reachable vertices have been visited, the algorithm selects one of the remaining unvisited vertices and continues the traversal. It nishes when all vertices have been visited. The DFS traversal allows us to classify edges into four classes:
Tree edges: are edges in the DFS search tree. Back edges: join a vertex to an ancestor already visited.
Forward edges: are non-tree edges connecting a vertex to a descendant in a DFS search tree.
Cross edges: all other edges.
We use these classes of edges to determine actions to do on each encountered concept. Tree edges allow to de ne actions on concepts encountered for the rst time, while forward and cross edges allow to dene actions to do on concepts that are already visited crossing another path and so having more than one parent. According to their de nition, back edges allow cycle detection, in our case these edges will never be encountered. As our edges respect a causal orientation having a cycle of the form X1 ! X2 ! X3 ! X1 means that X1 is the cause of X2 which is the cause of X3 so this latter can't be the cause of X1 at the same instant t but rather at an instant t + . We are limited to ontologies that do not contain cycles, because such relationships invoke the dynamic aspect which is not considered in this work.
A deep study of the similarities discussed above shows that the morphing process can be done in three main steps, namely initialization, discovery and closing. At each step, we de ne a set of actions that might be done: i. Initialization step: All concepts are undiscovered, we generate the OOBN class and a class to Algorithm 1: Generate OOBN Input: An ontology O O is of an anti-causal orientation.
For all concepts, the color must be initialized to "white" before running the algorithm. begin
CREATE OOBN GLOBAL ; for each concept cp 2 Cp do
RECORD PREDECESSOR[cp]=NULL;
CREATE CLASS(cp) for each concept cp 2 Cp do if color[cp]= white then
Handling Process(O, cp) each concept: CREATE OOBN GLOBAL : creates the OOBN class.
CREATE CLASS(Concept cp): transforms a concept cp to a class ccp. ii. Discovery step: The classes of edges are used to determine actions to do on each encountered concept. These actions allow us to de ne input, internal and output sets for each class of the OOBN. ADD INPUT NODE(Node n, Class c) : adds an input node n to a class c. this action is invoked on all properties of a concept which is related by an out edge to another one. Its properties are considered as candidate input nodes of the class representing the second concept.
ADD INTERNAL NODE(Node n, Class c): adds an internal node n to a class c. The set of internal nodes of a class consists of instantiations of other classes representing concepts that are related by an out edge to the corresponding concept of the class c in the ontology and this edge is in the same DFS search tree.
ADD OUTPUT NODE(Node n, Class c): adds an output node n to a class c. all properties of a concept are transformed into variables of its corresponding class in the OOBN. These nodes are considered as candidate output nodes of the class. ADD OUTREF NODE(Class c1, Class c2): adds output reference nodes to classes containing c1 until reaching c2. In fact, some concepts might have parents coming from more than one DFS search tree or from di erent paths. Let cpi be a concept having two parents cp1i and cp2i coming from two di erent branches. Then, ccpi would to be instantiated within the speci cation of only one of them. However, ccpi has its output nodes Algorithm 2: Handling Process Input: An ontology O, A concept S.
We use color markers to keep track of which vertices have been discovered: white marks vertices that have yet to be discovered, gray marks a vertex that is discovered but still has vertices adjacent to it that are undiscovered and black marks discovered vertex that is not adjacent to any white vertices. begin color[S]:= gray; for each property p of S do
ADD OUTPUT NODE(p; cS ) for each V 2 adjacent[S] do if color[V ]=white then
RECORD PREDECESSOR[V ]=S; Handling Process(O, V ); ADD INTERNAL NODE (INSTANCE OF(cV ), cS); if (S; V ) is an inheritance relation then
ADD CONSTRUCT LINK
INSTANCE OF(cV ),INSTANCE OF(cS)) if (S; V ) is a semantic relation then for each node n 2 GET OUTPUT(cV ) do
ADD REFERENCE LINK (n,ADD INPUT NODE(n,cS)) if color[V ]=black then if (S; V ) is an inheritance relation then
ADD CONSTRUCT LINK
INSTANCE OF(cS),INSTANCE OF(cV )) if (S; V ) is a semantic relation then for each node n 2 GET OUTPUT(cV ) do
ADD INPUT NODE(n, cS ) ADD OUTREF NODE (INSTANCE OF(cS),INSTANCE OF(cV ) color[S]:= black; if RECORD PREDECESSOR[S] = N ull then ADD INTERNAL NODE (INSTANCE OF(cS),GLOBAL OOBN CLASS) to be referenced by output reference nodes of the class containing it until reaching its second parent (see gure 3).
ADD CONSTRUCT LINK(Class c1, Class c2): a construct link appears between instantiations of superclasses and instantiations of their subclasses (see gure 4). All properties of the super-concept are considered as properties of its subconcepts. ADD REFERENCE LINK(Node n1, Node n2): allows the communication between classes interfaces. We also de ne the INSTANCE OF (Class c) which allow to instantiate a class c and the GET OUTPUT(Class c) which returns all output nodes of a class c.
All these actions are used in Algorithms 1 and 2. The Handling Process function (see algorithm 2) provides actions to do at each vertex.
Example 3. We assume that all random variables are modeled in the corresponding ontology 5(b) as concepts properties and that all semantic relations present in the ontology are of an anti-causal orientation.
We will follow the steps of the Generate OOBN algorithm (see algorithm 1)to generate our prior OOBN structure.
First of all, we start by generating the Global OOBN class Prior OOBN. Then we create a class to each concept of the ontology, that is, we create 11 classes ccpi ; i = f1; : : : 11g which are initially empty. their sets of nodes will be discovered during the generation process.
Initially, all concepts are white. cp1 is the source concept, it is grayed and all its properties are declared as output nodes of the class representing it in the prior OOBN. Then, each concept adjacent to cp1 is recursively visited if it is white and its properties are treated in the same way. cp1 has cp2 as adjacent concept, it is painted gray and it has cp5 as adjacent concept, so on until reaching cp9. cp9 is grayed and all its properties are declared as output nodes of the class representing it in the prior OOBN (ccp9 ). As it has no adjacent, it is instantiated within its ancestor ccp6 . As cp6 and cp9 are related by an inheritance relation then, we add a construction link between ccp6 and ccp9 and all properties of the super-class ccp9 are considered as properties of its subclass ccp6 . The concept cp9 is nished and blackened. We backtrack to the cp6 concept, it is gray and it has nished his adjacent concepts so, it is instantiated within its ancestor ccp11 . As cp11 and cp6 are related by a semantic relation then, all its output nodes are considered as input nodes of the ccp11 class linked by reference links. cp6 is blackened and we go back to cp11 it is gray and it has nished his adjacent concepts so, it is instantiated within its ancestor ccp5 . As ccp11 and ccp5 are related by an inheritance relation then, we add a construction link between them. cp11 is blackened and we go back to the second adjacent of the cp5 concept. cp5 is gray and cp9 is black, so (cp5,cp9) is a cross/forward edge, means that cp9 has already been instantiated so, we add output reference nodes from ccp6 until reaching the ccp5 class. cp5 is gray and it has nished his adjacent concepts so, it is instantiated within its ancestor and so on until backtracking to the concept ccp1 , it is gray and it has not ancestors, so it is blackened and instantiated within the speci cation of the Prior OOBN class. The rst DFS tree is nished, so we choose an undiscovered node from the remainder nodes and we apply the algorithm until discovering all the concepts. The result of this process is shown in gure 5.(b)) shows the nal result. 5
In recent years, a panoply of works have been proposed in order to combine PGMs and ontologies so that one can enrich the other. We can outline two main directions for these proposed approaches. The rst aims to enhance ontologies capabilities to support probabilistic inference. While the second aims to enhance PGMs construction by integrating ontologies.
Ontologies provide a support for logical reasoning, but
they do not support uncertainty. Hence, several
extensions have been proposed to overcome this limitation.
One line of research aims to extend existing ontology
languages, such as OWL1, to be able to catch
uncertainty in the knowledge domain. Proposed methods,
such as BayesOWL
I1 cp2.1 Cp11.1 cp5.1 I2 (a) The ontology to morph
Cp7
cp7.1
Cp8
cp8.1
vidual concepts and properties in OWL ontologies.
The result is then a probabilistic annotated ontology
that can be translated into a BN to perform
probabilistic inference. Other works de ne transition actions in
order to generate a PGM given an ontology with the
intention of extending ontology querying to handle
uncertainty while keeping the ontology formalism intact
On the other hand, some solutions proposed the use of
ontologies to help PGMs construction. Some of them
are designed for speci c applications
However, all these solutions are limited to a restrained range of PGMs, usually BNs. So, they neglect some ontology important aspects such as representing concepts having more than one property, non taxonomic relations, etc. In our approach we used OOBNs which are much richer graphical model than standard BNs. They allowed us to address an extended range of ontologies, we focused on concepts, their properties, hierarchical as well as semantic relations and we showed how these elements would be useful to automatically generate a prior OOBN. Our proposal concerns exclusively the OOBN structure de nition through the use of ontologies.
The crossing-over of PGMs and ontologies can allow us to improve relevant tasks related to each of them. In this paper, we showed how we take advantage of the semantic richness provided by ontologies to generate a prior OOBN structure and this is by exploring similarities between these two paradigms. The use of the OOBN framework has enabled us to handle an extended range of ontologies unlike works which were limited to the use of standard Bayesian networks, which brings us to say that this work is an initiative aiming to set up new bridges between these two paradigms.
The nal structure resulting from the learning process may also be useful to make the initial ontology evolve, and this is by trying to nd how the new relations discovered by the learning process can a ect the (semi) automatic ontology enrichment process. Thus, as an ongoing work, we aim to analyze the elements that are common to both tasks and provide a two-way approach that uses ontology power in representing knowledge to help the hard process of OOBN structure learning by proposing new metrics, based on ontological knowledge, allowing to assess better the choice of the best structure. Then, uses novel relations discovered by the learning process in order to improve the hard activity of ontology enrichment.