Bayesian ontology languages are a family of probabilistic ontology languages that allow to encode probabilistic information over the axioms of an ontology with the help of a Bayesian network. The Bayesian ontology language BEL is an extension of the lightweight Description Logic (DL) EL within the above-mentioned framework. We present the system BORN that implements the probabilistic subsumption problem for BEL.
ontologies usually have rather small modules, even if the total size of the ontology might be large.
In this paper we describe the implementation of BORN,3 a Bayesian ontology reasoner based on the ideas sketched above. Our first experiments show that reasoning with this system is feasible. 2
The Bayesian Ontology Language BEL
The Bayesian ontology language BEL is a probabilistic extension of the
lightweight DL EL [
PB(V ) = Y PB(x j (x)):
x2V
As with classical DLs, the main building blocks in BEL are concepts, which are syntactically built as EL concepts. In BEL, the domain knowledge is encoded via probabilistic GCIs of the form hC v D : xi where (C v D) is an EL GCI and x is either a literal4 over a fixed set of variables V or the empty set. A BEL TBox is a finite set of probabilistic GCIs over V . A BEL KB is a pair (T ; B) where T is a BEL TBox and B is a BN, both defined over V .
A contextual interpretation is a pair (I; VI ) where I is an EL interpretation and VI is a propositional interpretation. The contextual interpretation (I; VI ) satisfies hC v D : xi iff (i) VI 6j= x, or (ii) I j= C v D. It is a model of the TBox T iff it is a model of all the probabilistic GCIs in T .
Intuitively, axioms of the form hC v D : ;i represent crisp (or classical) axioms. In this view, the DL EL is an instance of BEL where all axioms are of the form hC v D : ;i. For brevity, we often write hC v Di to denote such axioms.
The probabilistic information provided by the BN is handled via the so-called multiple-world semantics. Briefly, a contextual interpretation describes a possible world; by assigning a probabilistic distribution over these interpretations, we describe the required probabilities, which should be consistent with the BN. Definition 1. A probabilistic interpretation is a pair P = (I; PI), where I is a set of contextual interpretations and PI is a probability distribution over I such that PI(I) > 0 only for finitely many interpretations I 2 I.
P is a model of the TBox T if every I 2 I is a model of T . P is consistent with the BN B if for every possible valuation W over V it holds that
X PI(I; W) = PB(W): (I;W)2I 3 Available under http://lat.inf.tu-dresden.de/systems/born 4 We point out that in the general case BEL allows for a set of literals. P is a model of the KB (B; T ) iff it is a model of T and consistent with B. The main reasoning problem in BEL is answering probabilistic subsumption queries. In contrast to classical subsumption, in this case we are interested in computing the probability with which a subsumption relation holds, as given by the BN.
Definition 2 (probabilistic subsumption). Let K be a BEL KB, and A; B BEL concept names. The probability of the subsumption A v B w.r.t. the probabilistic interpretation P = (I; PI) is
PP (A v B) :=
X (I;W)2I;Ij=AvB
PI(I; W): The probability of A v B w.r.t. K is PK(A v B) := infPj=K PP (A v B): We consider special restrictions over a BEL TBox T w.r.t. a valuation VI = W:
TW := fhA v B : ;i j hA v B : xi 2 T ; W j= xg: Intuitively, every valuation defines an EL TBox and to decide the probability of a subsumption A v B it is enough to sum up the probabilities of the valuations W for which the classical entailment relation TW j= A v B holds: PK(A v B) =
X TW j=AvB
PB(W):
Computing the probability of a subsumption query in BEL is shown to be
PP-complete [
BORN accepts a BEL KB (T ; B) and a subsumption query as input and
transforms the input into a probabilistic logic program. BORN is implemented on
top of jcel [
BORN requires a BEL KB (T ; B) and a subsumption query as input. As an answer, BORN returns the probability for the query to hold.
Example 3. Consider the BEL KB K = (ABC; BABC) where
ABC := f hA v 9r:B : x0i ; hA v C : x4i ; hB v 9s:C : :x3i ;
hC u D v E : x5i ; h9r:B v D : :x2i ; hC v E : x3ig; BABC is the BN given in Figure 1 and the subsumption query A v E. The relevant computations yield PK(A v E) = 0:1796: We use the functional syntax throughout the paper for the sake of legibility, but all known OWL syntax paradigms are accepted by BORN. After performing module extraction, all axioms are converted into a set of clauses. For instance, the first axiom is rewritten as: con('a'). con('b'). role('r'). subs('a', exists('r', 'b')) :- x0.
Clearly, con, role and subs are reserved predicate names used to denote concepts, roles and explicit subsumption relations. We assume that the BN and the query use the ProbLog syntax, that is roughly the Prolog syntax enriched with probabilistic annotations. A portion of the BN B from the Example 3 is then given by 0.7::x0. 0.8::x1:-x0. 0::x1:-\+x0. 0.6::x2:-x0,x1. 0.1::x2:-x0,\+x1. 0.5::x2:-\+x0,x1. 0.9::x2:-\+x0,\+x1. and the query from the Example 3 is given as query(sub('a', 'e')).
We use an additional reserved symbol sub to represent all subsumption
relations and not only the explicit ones. This distinction is forced for optimization
reasons. Finally, we implement the deduction rules [
con(X), con(A1), con(A2), con(B). sub(X, exists(R, B)) :- subs(A, exists(R, B)), sub(X, A),
con(X), con(A), con(B), role(R). sub(X, B) :- subs(exists(R, A), B), sub(X, exists(R, Y)), sub(Y, A), con(X), con(Y), con(A), con(B), role(R).
As an answer, BORN returns the subsumption relation with a probability value attached to it: sub('a','e') : 0.1796
The lack of Bayesian ontologies has led additional difficulties in evaluating
BORN. To show some initial results on BORN, we have created the artificial
ontologies listed in Table 1. DBPEDIA is adopted from http://trill.lamping.
unife.it/swish/ and GO is the Gene Ontology [
We ran our experiments on a PC equipped with a 2,3 GHz Intel Core i7 with 8 GB of main memory and obtained feasible execution times for the limited number of queries we have posed. Before moving to a detailed analysis, we stress the fact that all of the results we present here are preliminary. To speak of a general evaluation, there is still the need for further experiments with different types of ontologies and a large number of queries.
Performing module extraction prior to probabilistic inference turns out to be a simple but effective approach. The idea is that a module is usually much smaller than the original TBox. This is, of course, not always the case as evidenced by the module sizes of ABC w.r.t. some queries given in Figure 2. However, for some 0:4 s d n ceo 0:35 is en m i ton 0:3 itcexu E 0:25 6 1 (ABC, BABC) (ABC, BA0BC) Preprocessing (DBPEDIA, BDB) (DBPEDIA, BD0B) Preprocessing 6 2 4 3 Queries 2 4 1 5 0:45 0:4 0:35 real terminologies (e.g. GO) the size of a module turns out to be extremely small compared to the original ontology. Notice that GO is very flat from its nature and leads to really small module sizes.
We report the module sizes (in the number of axioms), the total execution times and the execution times for preprocessing in Figure 2. The delay in preprocessing is mainly due to modularization, but preprocessings times remain rather stable over different queries compared to the total execution time. This time is below 1.4s even for GO, that consists of 23507 normalized axioms originally.
As expected, the size and shape of the network influences the performance greatly. We expect the number of the literals and the conditional dependencies to be much smaller compared to the sizes of terminologies. Given these assumptions, our initial experiments show that BORN is a promising tool for probabilistic reasoning over DL ontologies. 4
We have introduced the Bayesian Ontology reasoner BORN. To the best of our
knowledge BORN is the first Bayesian reasoner over DL ontologies based on
the multiple world semantics. Another probabilistic formalism is PR-OWL [
We plan to create realistic test data and evaluate BORN and generalize the results to extensions of EL as well as to other DL-based ontology languages. Additionally, we think that further optimizations are possible for BORN. Ultimately, we plan to improve BORN to achieve a scalable probabilistic reasoner over arbitrary Bayesian DL ontologies.