An interesting class of problems in machine learning arises when data points have internal structure. Such problems occur, for example, when analyzing biochemical data where each data point represents a molecule and where one would like to be able to predict whether unseen molecules are `active' (e.g. a useful drug or not). In this case the atom-bond relations and other structural properties of the molecule are clearly important, thus we get a problem of classifying graphs or more generally hypergraphs. Taking a perspective from logic, examples can be seen as models (or interpretations in logic programming) and classifiers as first order formulas, and indeed this problem is known as Learning from Interpretations.

The talk will give an overview of theoretical and empirical results for such problems. In particular I will discuss the complexity of learning from interpretations giving both lower bounds and upper bounds for successful solutions. I will then discuss two implemented systems, one based on logic and one using hypergraph kernels, and their success in classifying datasets of molecules.