A Theory of Unsupervised Speedup Learning

Abstract

Speedup learning seeks to improve the efficiency of search-based problem solvers. In this paper, we propose a new theoretical model of speedup learning which captures systems that improve problem solving performance by solving a user-given set of problems. We also use this model to motivate the notion of "batch problem solving," and argue that it is more congenial to learning than sequential problem solving. Our theoretical results are applicable to all serially decomposable domains. We empirically validate our results in the domain of Eight Puzzle. 1 Introduction Speedup learning seeks to improve the efficiency of search-based problem solvers. While the theory for concept learning is well-established, (for example, see [Valiant 1984; Natarajan 1991]), the theory of speedup learning is rapidly evolving [Cohen 1989; Elkan & Greiner 1991; Etzioni 1990; Greiner 1989; Laird 1990; Natarajan & Tadepalli 1988; Natarajan 1989; Subramanian & Feldman 1990; Tadepalli 1991a, etc.]. In this paper...