Ontological reasoning has become a very useful technique for several different applications. However, the use of large knowledge bases has shown that reasoning can be a very resource intensive task which does not scale well. The goal of this work is to explore the development of scalable reasoning approximation methods based on machine learning. Our most important concern is determining in which contexts would such methods be more convenient than currently available approximate reasoning techniques. For this purpose, we will study the use of currently available approximation approaches, and we will develop new machine learning based methods to compete with them. Our preliminary results already provide evidence that this is possible. However, there are several questions that need to be answered, e.g. what reasoning tasks can be efficiently approximated, or what is the appropriate feature representation for such purposes. Finally, it will be important to determine the degree of completeness and correctness of such methods based on machine learning, and compare them with approximate methods based on standard reasoning.
While approximate methods are indeed more efficient than using sound and
complete reasoning, they come with the intrinsic limitation with which they were designed.
This means that their accuracy depends more on the expressiveness of the dataset to
which they are applied. Consequently, what we propose in this work is the use of
machine learning methods to approximate ontological reasoning in a more flexible way.
More specifically, we propose to represent reasoning tasks as supervised learning
problems, which require the use of a reasoner to label the training data. Our preliminary
results already show that ABox consistency checking can be effectively represented as
a binary classification problem [
All of this leads us to our main research questions: is it possible to approximate ontological reasoning with machine learning methods? And if so, in what context are machine learning methods more convenient than other existing approximate methods? This proposal elicits several further questions, both theoretical and practical, which we will address in more detail in the following sections. We hope that the feedback from the Doctoral Consortium can help us direct our efforts towards answering some of them. 2
There is already a considerable amount of research done in search of more efficient
ways to reason with ontologies. There are early approaches where the deduction process
is approximated by simplifying the inference algorithm [
More recently, the use of less expressive languages has been a widely explored
approach. An example of this is the DL-Lite family of description logics, which allow for
the definition of basic ontological languages while providing reasoning tasks in
polynomial time [
While machine learning has been used at times in reasoning related environments,
e.g. for ontology learning [
The works cited in the paragraph above use machine learning methods to
approximate reasoning tasks. However, while we may share the approach and could learn from
them, we do not in principle share the motivation. These methods, as well as methods
employed in relational machine learning [
We now describe our proposal (Section 3.1), and our preliminary results (Section 3.2). 3.1
Our basic idea is that given a reasoning task, a TBox, and a set of ABoxes which use the vocabulary defined in the TBox, we could use a reasoner with only a portion of the data and then use this as labelled data to train a machine learning algorithm. This would result in a model that simulates the reasoning task at hand, which could then be applied to the whole dataset. Such an approach would free us from using the reasoner on the whole dataset, which might be considerably more costly.
This idea implies that the reasoning task we want to approximate should be modeled as a supervised learning problem. Moreover, since machine learning algorithms do not take DL assertions as input, but rather feature vectors, a crucial aspect of this approach is the transformation of ontological information into an appropriate feature representation.
As a starting point of this work, and as proof of concept, Paulheim and
Stuckenschmidt [
An important step in that process was obtaining a number of ABoxes which would be large enough to train an accurate model. For the datasets which came from the Web Data Commons corpus, this was as simple as defining that all assertional axioms belonging to a single website constituted an ABox. As such, the authors were able to build as many ABoxes as the number of websites which were a source of this corpus. This resulted in ABoxes ranging from a small number of assertions to several dozens. For the DBpedia and YAGO datasets, they had to determine a way to systematically break down the ABox into small ABoxes. This meant that any inconsistency that involved the information of more than one ABox would not be detected by their method. For this purpose, the authors defined that an ABox consisted of a relational assertion along with all the type assertions for its subject and object.
For the transformation of ABoxes into feature vectors, the authors used the notion of
path kernels as defined by Loesch et al. [
The following example illustrates the importance of having the right the feature transformation procedure in a machine learning based approach. Let A1 be an ABox made up of the following assertions: A(a), B(b), C(c), P (a; b), S(a; c), A(d), B(d).
However, another ABox A2 which consists of all the assertions found in A1 except for A(d) and B(d) would have almost the same corresponding graph as A1 (the node d would not exist), but this would still result in the exact same feature representation as A1. This can be a problem in a setting where the TBox has the axiom A v :B, because if A1 is labelled as inconsistent by a reasoner, a machine learning approach would classify A1 as inconsistent too, even though that would be incorrect. Consequently, these are important considerations for reasoners based on machine learning.
In order to compete with [
The results from [
The results in Table 1 show that both approximation methods require considerably lower time to check the consistency of a single ABox when compared with a full reasoner, but both require considerably more time for preprocessing the data in order to train their approximate reasoner. Moreover, while both approximate methods are highly accurate, the caching method does have an advantage in these datasets. 4
Our main research question is to determine whether machine learning can be used to
approximate ontological reasoning. Consequently, we are also concerned with the
following more specific questions:
1. What feature representation is required in order to accomplish this?
The feature transformation method used in [
This will require finding real life datasets with different expressiveness in order to
test the performance of each method and the flexibility of machine learning based
approaches. We could also generate artificial settings in order to test the limits of
what the models can learn.
4. What is the relation between the expressiveness of the TBox and the feature
representation used in machine learning methods for reasoning approximation?
Since the correctness and accuracy of a machine learning based reasoner will largely
depend on the feature representation which is used, exploring different methods for
obtaining feature representations, and studying how these relate to the
expressiveness of the TBox, will be a key aspect of our research.
5. Is it possible to use standard machine learning methods? Or are modifications
required which allow the learned models to perform better?
As mentioned in Section 2, there have been proposals where standard machine
learning based methods are adapted for the purpose of approximating reasoning.
Consequently, an important question is whether such models are more effective for
this purpose. Moreover, due to the monotonicity of the reasoning tasks, developing
models which consider this property is surely an advantage worth considering.
6. Is it possible to use explanations in order to make these methods more competitive?
Another possible direction would be to consider working with explanations, either
by developing a similar method to the one described in [
Finally, our hypothesis is that ontological reasoning can be approximated by using machine learning, that machine learning based methods can be at least as efficient as current methods, and that machine learning based methods can be more flexible by adapting to each dataset and learning what is required for them. All of this means that we will explore the use of existing approximation methods, we will develop new methods based on machine learning, and we will test their strengths and weaknesses. 5
As this research is in its very early stages, we propose a reseach plan with two initial stages. After that, different directions might be considered depending on the results obtained in the first two stages.
For the first stage, we will continue working with consistency checking as the
reasoning task to be approximated. In this stage we will focus on studying the role of
feature representation in this context. This implies finding a feature representation which
is adequate for fully representing ontological information, and also compiling a list of
specific examples of assertional data which could be used as benchmarks to see whether
a given feature representation accurately represents them. Additionally, in this stage we
plan on extending our caching method presented in [
In a second stage, we plan on approximating new reasoning tasks and seeing what
effect this has on the feature representation. Moreover, on this stage we plan to explore
the possibility of generating monotone models, and to consider extensions of standard
machine learning approaches, such as the ones presented in [
Regarding evaluation, if successful our method should be able to be trained on different datasets and learn a model which efficiently approximates specific ontological reasoning tasks. Moreover, since rather than relying on design restrictions to make it more efficient, our method would learn what is required for each dataset, it should be competitive with different approximate methods which may be designed for the specific datasets which we will use for testing.
I would like to thank Prof. Dr. Heiner Stuckenschmidt, Prof. Dr. Heiko Paulheim and Dr. Christian Meilicke for their guidance and support in the realization of this work.