Applying Abstraction and Simplification to Learn in Intractable Domains

Abstract

In many domains it is computationally intractable to apply EBL to learn knowledge that is operational, complete and correct. Current approaches to solving this problem exploit the trade-off between correctness and operationality, and introduce approximations to learn operational but incorrect knowledge. In this paper we introduce an alternative approach that exploits the trade-off between completeness and operationality to learn knowledge that is both operational and correct, but incomplete, since it only covers a subset of the original domain. We employ a “boot-strapping” approach to incrementally increase coverage of the domain by using the knowledge learned from small problems to simplify learning from more complex problems. Correct knowledge is learned by employing a second order theory of goal achievement to construct abstract proofs that are useful for learning. These proofs are compiled into operational form by employing simplifying assumptions. The advantage of this approach is that learned knowledge is guaranteed to be correct if the simplifying assumptions made during learning hold during problem solving. We illustrate the method in two-person games and present preliminary results in Quinlan's lost-in-n- ply classification problem (1983).