CAREER: Learning to Understand -- Integrating Reasoning and Learning

由于一阶语言中的通用演绎是不可确定的，因此很难将其融入到实际的关系概念学习中。在这个项目中，PI将探索使用强大的多项式时间演绎推理程序来使关系学习系统受益。这项研究引入了一种新的学习设置，称为“从直接结果中学习”，它被一个多项式时间演绎推理过程参数化，该过程可以被视为定义相对于查询的任何一组公式的“直接结果”。在这种背景下的学习目标是将一组当前不是背景知识的直接结果的例子作为输入，并归纳出目标概念的定义，使得积极的例子成为直接的结果，而消极的例子不会。可以在直接后果和那些对人类显而易见的后果之间进行粗略的类比。当给出一个问题时，人类能够立即确定它的答案是否显而易见，这与低阶多项式时间推理程序可以快速回答相同问题的意义相同。考虑到这种类比，建议的学习环境可以被视为学习一个目标概念，使积极的例子明显被覆盖，而负面的例子显然没有被覆盖。我们将考虑非经典谓词演算的形式表示语言，这些语言旨在促进快速发现有用的直接结果；由此产生的学习系统可以用一种比标准Horn子句语言更具表现力的语言来表达和学习目标概念。这种方法与可能是最著名的高效关系学习系统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.