Learning and Reasoning with Relational Structures

Tufts University, Medford MA

Investigators

Abstract

This is the first year funding of a three year continuing award. The project is devoted to the study of relational structures in the context of machine learning and reasoning. A lot of progress has been made in these areas in recent years, but much of this work ignores structure in examples and representations. Relational representations are natural for many application areas, e.g. molecular problems in bioinformatics, or sentence structure in natural language processing (NLP). The PI believes that further progress can be made by considering relational structures and techniques explicitly in such contexts. A large part of this project is concerned with algorithms based on first order Horn expressions, where reasoning problems have long been studied, and learning within inductive logic programming . Recent results suggest that some learning problems are feasible if the learner can ask questions. This project will extend that work in an attempt to identify more learnable classes, the associated complexity of the problems, and the limits of the approach. The PI will continue work on the LogAn-H system, so that algorithmic ideas developed can also feed directly into heuristics for learning from examples. The PI will also explore alternative representations and reasoning mechanisms for relational structures, and their effect on learnability. This includes both the use of linear threshold elements (perceptrons) to embed relational structures, and the logic-based approach of reasoning with models. While most of the work is concerned with theoretical foundations, applications in NLP and bioinformatics will be explored. All these directions are part of an effort to develop foundations for systems that learn their knowledge and use it for reasoning.