We propose a new method for knowledge acquisition and ontology re nement for the Semantic Web utilizing Linked Data available through remote SPARQL endpoints. This method is based on combination of the attribute exploration algorithm from formal concept analysis and the active learning approach from machine learning.
Knowledge acquisition is a process of capturing knowledge, typically from a human expert, and thus it concerns all systems and environments where that kind of knowledge is required. It is also said to be major bottleneck in development of intelligent systems due to its di culty and time requirements. Of course the Semantic Web, as an area concerned with structured and precise representation of information, has to deal with exactly the same issue.
Since the early days of the Semantic Web, building ontologies has been a difcult and laborious task. Frequently people trying to express complex knowledge do not know how to perform this task properly. Mistakes come from di culty in understanding the complex logic formalism supporting OWL.
Frequently an ontology engineer would start collecting vocabulary and
requirements for an ontology, structuralize the vocabulary and later specify more
complex dependencies [
For knowledge acquisition for ontology development many approaches have been
proposed so far. The most basic ones are ontology editors supporting ontology
development, such as Protege3. In addition to that, there are methodologies
helpful in ontologies development, such as the one proposed in NeOn [
In [
In [
The proposed approach is to support the user during attribute exploration by means of machine learning (ML). The ML algorithm's task is to answer simple, non-interesting questions posed by the attribute exploration algorithm and leave for the user only these questions which are non-trivial to answer.
Input of our proposed algorithm is an ontology O, a partial context derived from it, and two thresholds a and r. They are, respectively, thresholds for accepting and rejecting an implication and have to be manually chosen w.r.t. the used ML algorithm. Result of the algorithm is a set of probably valid implications, which can be transformed into subsumptions for extending the ontology. A detailed description of the algorithm is presented below. For sake of clarity its description treats the attribute exploration algorithm as a black box, which provides the next implication to consider. 1. Generate implication L ! R by means of the attribute exploration algorithm. 2. For every r 2 R, do the following sequence of steps: (a) If L ! frg is already refuted by some of the known individuals, go to the next r. (b) If O j= d L v r, remember implication L ! frg as a valid one and go to the next r. (c) Compute probabilities of acceptance pa and rejection pr of the implication L ! frg with the ML algorithm. Note that pa + pr = 1. (d) If pa a, remember the implication L ! frg as a valid one and go to the next r. (e) If pr r, go to the step 2i. (f) Ask user if implication L ! frg is valid. (g) Add considered implication with user's answer to a set of learning examples for the ML algorithm. (h) If the implication is valid, remember it as a valid one and go to the next r. (i) Otherwise, extend the partial context with a counterexample either provided by user or auto-generated.
The purpose of iteration through the set of conclusions R in the algorithm is twofold. We believe that this way user can more easily decide if the presented implication is valid or not, because she does not have to consider complex relation between two conjunctions of attributes.
The other thing is that this way automated generation of counterexamples provides more concrete results. For an arbitrary implication L ! R a counterexample can be generated and said to have all attributes from L and to not have at least one attribute from R. This is not in line with the method of partial context induction, as it is unclear which exactly attribute from R the counterexample does not have. Because of that partial context can not re ect knowledge base accurately anymore, and the attribute exploration algorithm can start to generate invalid implications. If the implication has a single attribute in its right-hand side, it is clear which attribute the counterexample does not have. 3.1
Application of machine learning The task which ML algorithm is to solve can be seen as a kind of active learning with a binary classi cation. Every implication is classi ed as valid or invalid and if the algorithm is unsure, the user is asked.
One should note that not every classi er generates reasonable probabilities. For example, rule-based or tree-based systems usually are not suitable for that purpose. Problem of generating probabilities can be also seen as a regression problem.
Moreover costs of both types of mistakes are di erent and distribution of learning examples can be heavily imbalanced, i.e. implications with one decision may appear much often than with other decision. To re ect these fact a classi er suitable for cost-sensitive learning is required.
To apply machine learning techniques, a way to transform implications to
feature vectors is required. We apply three approaches to this problem. First
of all, a single purely syntactic measure is used: the number of attributes in
the left-hand side divided by the number of all attributes. Secondly, there are
features made of values of measures typical for association rules mining. Their
computation is based on features of individuals in the ontology. Following the
naming convention from [
Finally, we use a mapping from the set of the attributes to Linked Data
in order to obtain the number of objects in an RDF repository supporting an
implication or its parts. Every attribute is mapped to a SPARQL graph pattern
with a single featured variable denoting the object identi er. Following the same
name convention from [
Such a feature vector is later labeled with the classi er mentioned above and given answer (valid/invalid/unsure) is used to either re ne the ontology or ask the user. If the user is asked, her answer is then used as a correct label for the feature vector and the classi er is relearned.
As we are proposing a method which is to make development and re nement of domain-speci c ontologies easier, our main goal for evaluation is to validate its practical usability. We plan to apply our method to a selection of domain-speci c ontologies concerning some knowledge of general type such as literature, music and movies. We plan to use a crowdsourcing service to validate our hypotheses. We hope that with ontologies with a theme being general enough and additional information available in the Internet, the crowd will be able to validate our decisions about implications and Linked Data mappings.
We believe that our approach is promising and will be able to help ontology engineers in the process of ontology re nement. We are combining three technologies very suitable for this kind of a task. First of all, the attribute exploration algorithm that has been developed especially for discovering additional relations between attributes. Moreover, Linked Data is supposed to describe parts of the world. Obviously, this description can not be assumed to be neither accurate nor complete, yet it should be su cient to support the user in a process of ontology re nement. Finally, the whole purpose of machine learning algorithms is to adapt themselves, and thus they are suitable to replace the user in uniform, repeatable tasks.
Acknowledgement. Jedrzej Potoniec and Agnieszka Lawrynowicz acknowledge support from the PARENT-BRIDGE program of Foundation for Polish Science, co nanced from European Union, Regional Development Fund (Grant No POMOST/2013-7/8 LeoLOD { Learning and Evolving Ontologies from Linked Open Data).