Ordering Thought: Cognitive Complexity of a Description Logic

Abstract

\noindent Knowledge bases are used in a variety of industries to efficiently represent data, but they sometimes contain errors. The debugging of knowledge bases is, therefore, a vitally important process. Debugging requires explanations of entailments in description logic, because the latter are used for answering knowledge base queries. Such explanations can be generated by axiom pinpointing, which is a technique to find justifications: minimal sets of axioms that entail a certain conclusion. Typically, a large set of justifications is found. It is difficult to select the most explanatory one, i.e. the one which requires the least cognitive effort to understand.

Four contributions are made with this thesis to solve this problem. First, the concept of relative cognitive complexity is defined. Second, the model SHARP is created with the cognitive architecture ACT-R, simulating the process of a human deciding the consistency of so-called ABoxes, the definition of which some justifications satisfy. The scope is restricted to ABoxes in the description logic $\mathcal{ALE}$. SHARP can be used to model cognitive effort, so as to capture the relative cognitive complexity of $\mathcal{ALE}$ ABoxes. Third, an experiment is performed to test the predictions on cognitive behaviour based on SHARP's simulation results. The model performs quite well on the relative cognitive complexity, but also shows some peculiar effects. Fourth, three surrogate modelling techniques were tested to decrease computation times: Random Forests (RF), Support Vector Regression (SVR) and Symbolic Regression (SR). The three techniques achieve similar performance, but SR achieves the lowest computation times, although it required a long training time.