Abstract: A key issue in semantic reasoning is the computational complexity of inference tasks on expressive ontology languages such as OWL DL and OWL 2 DL. Theoretical works have established worst-case complexity results for reasoning tasks for these languages. However, hardness of reasoning about individual ontologies has not been adequately characterised. In this paper, we conduct a systematic study to tackle this problem using machine learning techniques, covering over 350 real-world ontologies and four state-of-the-art, widely-used OWL 2 reasoners. Our main contributions are two-fold. Firstly, we learn various classifiers that accurately predict classification time for an ontology based on its metric values. Secondly, we identify a number of metrics that can be used to effectively predict reasoning performance. Our prediction models have been shown to be highly effective, achieving an accuracy of over 80 percent.
Bio: Yuan-Fang Li is a Lecturer at the Faculty of Information Technology, Monash University, Australia, and serving as the deputy director of the Faculty's Bachelor of Software Engineering degree. He received both his Bachelor of Computing (with honours) and PhD degrees from National University of Singapore in 2002 and 2006, respectively. His main research interests include the Semantic Web (ontology languages, semantic query & inference, knowledge representation, data management) and software engineering (formal methods & verification, software metrics, software product line). He has published more than 50 research papers in internationally prestigious venues including WWW, ISWC, ICSE, MSR, eScience, Journal of Web Semantics, Journal of Systems and Software, and Future Generation Computer Systems.
- Meston 203