A FORMAL FRAMEWORK FOR SPEEDUP LEARNING FROM PROBLEMS AND SOLUTIONS

Speedup learning seeks to improve the computational efficiency of prob lem solving with experience. In this paper, we develop a formal framew ork for learning efficient problem solving from random problems and th eir solutions. We apply this framework to two different representation s of learned knowledge, namely control rules and macro-operators, and prove theorems that identify sufficient conditions for learning in eac h representation. Our proofs are constructive in that they are accompa nied with learning algorithms. Our framework captures both empirical a nd explanation-based speedup learning in a unified fashion. We illustr ate our framework with implementations in two domains: symbolic integr ation and Eight Puzzle. This work integrates many strands of experimen tal and theoretical work in machine learning, including empirical lear ning of control rules, macro-operator learning, Explanation-Based Lear ning (EBL), and Probably Approximately Correct (PAC) Learning.