Learning and Reasoning with Relational Structures

这是一个为期三年的连续奖励的第一年资助。该项目致力于在机器学习和推理的背景下研究关系结构。 近年来，在这些领域已经取得了很大的进展，但这些工作中的大部分都忽略了示例和表示中的结构。 关系表示对于许多应用领域来说是自然的，例如生物信息学中的分子问题，或自然语言处理（NLP）中的句子结构。 PI认为，通过在这种情况下明确考虑关系结构和技术，可以取得进一步的进展。 这个项目的很大一部分是关于基于一阶Horn表达式的算法，其中推理问题已经研究了很长时间，以及归纳逻辑编程中的学习。 最近的研究结果表明，一些学习问题是可行的，如果学习者可以提出问题。 这个项目将扩展这项工作，试图识别更多的可学习类、相关问题的复杂性以及方法的局限性。 PI将继续在LogAn-H系统上工作，以便开发的算法思想也可以直接用于从示例中学习的算法。 PI还将探索关系结构的替代表示和推理机制，以及它们对可学习性的影响。 这包括使用线性阈值元素（感知器）来嵌入关系结构，以及基于逻辑的模型推理方法。 虽然大部分的工作都与理论基础有关，但将探索NLP和生物信息学中的应用。 所有这些方向都是为学习知识并将其用于推理的系统开发基础的努力的一部分。

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.