Learning and Reasoning with Relational Structures

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

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.