Reasoning and Query Answering Using Concept Similarity Measures and Graded Membership Functions
Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
Final Report Abstract
Truly intelligent behaviour usually relies on the availability of relevant knowledge and the ability to reason about this knowledge. Consequently, Knowledge Representation and Reasoning always has been and still is an important subfield of Artificial Intelligence, which introduces and investigates tailor-made representation formalisms with good algorithmic properties of their reasoning procedures. This project has investigated a new family of such formalisms, which extends well-known Description Logics (DLs) underlying the OWL standard. The introduction of this family is motivated by the fact that, in some applications, exact definitions of important notions are hard to come by, and thus it would be useful to allow for approximate definitions of concepts, where most, but not all, of the stated properties are required to hold. Similarly, if a query to a knowledge base has no exact answer, approximate answers that satisfy most of the features the query is looking for could be useful. For example, in clinical diagnosis, diseases are often linked to a long list of medical signs and symptoms, but patients that have a certain disease rarely show all of them. Instead, one looks for the occurrence of sufficiently many of these signs and symptoms. Similarly, in match-making, people looking for a flat to rent, a bicycle to buy, or a movie to watch may have a long list of desired properties, but will also be satisfied if many, but not all, of them are met. Classical logic-based knowledge representation and query formalisms, such as traditional DLs, would need to resort to large disjunctions to express such conditions, which are not only inconvenient to write and comprehend, but also hard to reason about. In a nutshell, the novel representation and query formalisms extending classical Description Logics investigated in this project can describe such concepts and queries in a compact and easy to comprehend way, and have considerably better reasoning complexity than classical formalisms using large disjunctions. On the one hand, motivated by the need for defining concepts in an approximate way, we have considered an approach for extending the DL EL, which underlies the OWL 2 EL profile, by threshold concepts. The semantics of such threshold concepts is defined using the notion of a graded membership function. We have shown that concept measures, which generalize subsumption or equivalence between concepts, can be used to define graded membership functions that yield extensions of EL with good algorithmic properties. The results obtained in this project considerably generalize our previous work on threshold logics by extending the general framework to infinite signatures, dealing both with acyclic and with general TBoxes for a larger class of graded membership functions defined using concept measures, and providing exact complexity results for all the classical reasoning problems. On the other hand, motivated by the need for relaxing queries, we have extended our previous approach for relaxing EL instance queries w.r.t. EL ontologies, which is based on the use of similarity measures on EL concepts, in two directions. On the ontology side, we consider not only EL ontologies, but also DL-Lite ontologies, which correspond to the OWL 2 QL profile. On the query side, we extend from EL concepts as instance queries to regular path queries, which are a well-investigated class of query languages used in the context of semi-structured data, graph databases, and RDF data, and are part of the SPARQL query language. The main results are again exact complexity results for relaxed query answering in different settings. We also investigate an alternative way of relaxing queries, which is based on using so-called rough logics to define the semantics of queries and ontologies. Finally, we show how weighted tree automata can be used to define equivalence-invariant concept (similarity) measures for the DL FL0 , which differs from EL in that existential restrictions are replaced with value restrictions.
Publications
- “Approximation in Description Logics: How Weighted Tree Automata Can Help to Define the Required Concept Comparison Measures in FL0 ”. In: Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. Edited by Frank Drewes, Carlos Martin-Vide, and Bianca Truthe. Volume 10168. Lecture Notes in Computer Science. Springer, 2017, pages 3–26
Franz Baader, Oliver Fernández Gil, and Pavlos Marantidis
(See online at https://doi.org/10.1007/978-3-319-53733-7_1) - “Decidability and Complexity of Threshold Description Logics Induced by Concept Similarity Measures”. In: Proceedings of the ACM Symposium on Applied Computing, SAC 2017. Edited by Ahmed Seffah, Birgit Penzenstadler, Carina Alves, and Xin Peng. ACM, 2017, pages 983–988
Franz Baader and Oliver Fernández Gil.
(See online at https://doi.org/10.1145/3019612.3019715) - “Query Answering for Rough EL Ontologies”. In: Proceedings of 16. International Conference on Principles of Knowledge Representation and Reasoning (KR 2018). Edited by Michael Thielscher and Francesca Toni. AAAI Press. 2018, pages 399–408
Rafael Peñaloza, Veronika Thost, and Anni-Yasmin Turhan
- “Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics”. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI’21). AAAI Press, 2021, pages 6340–6348
Oliver Fernández Gil and Anni-Yasmin Turhan
- Extending the description logic with threshold concepts induced by concept measures, Artificial Intelligence Volume 326, January 2024, 104034
Franz Baader, Oliver Fernández Gil
(See online at https://doi.org/10.1016/j.artint.2023.104034)
