CAREER: Learning to Understand -- Integrating Reasoning and Learning

由于一阶语言中的通用推理是不可判定的，因此很难将其纳入实际的关系概念学习中。 在这个项目中，PI将探索使用强大的多项式时间演绎推理程序来使关系学习系统受益。该研究引入了一种新的学习设置，称为“从直接后果中学习”，该设置由多项式时间演绎推理过程参数化，该过程可以被视为定义相对于查询的任何公式集的“直接后果”。 这种设置中的学习目标是将一组当前不是背景知识的直接结果的示例作为输入，并归纳目标概念的定义，使得正面示例成为直接结果，但负面示例不会。可以在直接后果和对人类显而易见的后果之间进行粗略的类比。 当给出一个查询时，人类能够立即确定它的答案是否是显而易见的，在同样的意义上，低阶多项式时间推理过程可以快速回答同一个问题。 鉴于这种类比，所提出的学习设置可以被视为学习一个目标概念，使得正面示例明显被覆盖，而负面示例仍然明显未被覆盖。 除了经典的谓词演算之外的形式表示语言将被考虑，其被设计为便于快速发现有用的直接后果; 这种方法与可能是最著名的高效关系学习系统FOIL所使用的方法形成对比，FOIL通过要求所有背景知识被扩展地指定来完全避免通用推理的不可判定性，并不试图在演绎上超越这一规范。 尽管PI的方法和FOIL的方法之间存在差异，但将FOIL和其他关系学习系统的许多想法整合到这个新的学习环境中是可行的，目的是保留这些系统的优势。 这项工作的潜在影响包括改进的归纳和数据挖掘算法，用于许多工业环境。 这些算法在要分析的数据是高度结构化的情况下将特别有利，因此对于当前最先进的属性值学习技术来说并不理想。这项工作将提供手段来识别丰富的数据结构，而不使用昂贵的定理证明技术和/或假设一个广泛代表的背景知识库。 万维网上的自然语言文本数据库形成了学习问题的中心来源，这些问题将受益于结构化表示的有效使用。

Because general-purpose deduction in first-order languages is undecidable, it has been difficult to incorporate into practical relational concept learning. In this project the PI will explore the use of powerful polynomial-time deductive reasoning procedures to benefit relational learning systems. The research introduces a new learning setting called "learning from immediate consequences" which is parameterized by a polynomial-time deductive reasoning procedure that can be viewed as defining the "immediate consequences" of any set of formulas relative to a query. The learning goal in this setting is to take as input a set of examples that are not currently immediate consequences of the background knowledge, and induce a definition of the target concept such that the positive examples become immediate consequences but the negative examples do not. A rough analogy can be drawn between immediate consequences and those consequences that are obvious to humans. When given a query, a human is able to determine immediately whether or not the answer to it is obvious, in the same sense that a low-order polynomial-time inference procedure can quickly answer the same question. Given this analogy, the proposed learning setting can be viewed as learning a target concept that makes the positive examples obviously covered while the negative examples remain apparently uncovered. Formal representation languages other than classical predicate calculus will be considered, which are designed to facilitate discovery of useful immediate consequences quickly; the resulting learning system can express and learn target concepts in a language that is strictly more expressive than the standard Horn clause language.This approach stands in contrast to that used by perhaps the most well-known efficient relational learning system, FOIL, which avoids the undecidability of general-purpose deduction entirely by requiring that all background knowledge be extensionally specified, and making no attempt to go beyond that specification deductively. In spite of the contrast between the PI's approach and that of FOIL, it is feasible to integrate many of the ideas from FOIL and other relational learning systems into this new learning setting, with the intention of retaining the advantages of those systems. The potential impact of this work includes improved induction and data-mining algorithms for use in many industrial contexts. These algorithms will be particularly advantageous in situations where the data to be analyzed are highly structured, and thus are not ideal for current state-of-the-art attribute-value learning techniques. This work will provide means to recognize rich structure in data without using expensive theorem-proving techniques and/or assuming an extensionally represented background knowledge base. Natural language text databases on the world-wide web form a central source for learning problems that will benefit from such efficient use of structured representations.