On Learning and Logic

摘要

A brief survey is given of learning theory in a logic framework, concluding with some topics for further research. The idea of learning using logic is traced back to Turing's 1951 radio address. An early seminal result is that clauses have a least general generalization. Another important concept is inverse resolution. As the most common formalism is logic programs, the area is often referred to as inductive logic programming, with yearly ILP conferences since 1991. Positive learnability results include an equivalence and membership query algorithm for CLASSIC, a version of description logic, a PAC algorithm obtained with the product homomorphism method, and an algorithm for first-order Horn formulas, which also uses queries but has an efficient implementation using examples only. Each algorithm is based on some kind of product of structures. Positive and negative PAC-learnability results for ILP are surveyed in [3]. The notion of a certificate of exclusion from a concept class, characterizing query complexity, could be of interest outside of learning theory as well. A certificate size upper bound for monadic second order logic over trees, implying a theoretically efficient, though not practical, learning algorithm, is given in [7].