Open for all UnRAVeL Members: Research Seminar by RTG QuantLA: Frank Wolter: Separating Positive and Negative Data Examples in the Presence of an Ontology

Tuesday, December 15, 2020, 1:00pm

Location: Online Session

Speaker: Frank Wolter (University of Liverpool)



Finding a logical formula that separates positive and negative examples given in the form of labeled data items is fundamental in applications such as concept learning,  reverse engineering of database queries, and generating referring expressions.
In this talk, I will discuss recent results on the existence of a separating formula for incomplete data in the presence of an ontology. Both for the ontology language and the separation language, we concentrate on fragments of first-order logic, including description logics. We consider several forms of separability that differ in the treatment of negative examples and in whether or not they admit the use of additional helper symbols to achieve separation. We characterize separability in a model-theoretic way, compare the separating power of the different languages, and determine the computational complexity of separability as a decision problem.
We also point out very close links to the existence problem for least common subsumers, most specific concepts, and Craig interpolants.