Lazy Partial Evaluation: An Integration of Explanation-Based Generalization and Partial Evaluation

Abstract

In this paper we present lazy partial evaluation (LPE), a new learning technique which is a hybrid of explanation-based generalisation (EBG) and partial evaluation (PE). LPE operates in a similar way to EBG, except that the work performed exploring failed proofs is also generalised and stored. The equivalence of the set of explored proofs to the original goal definition allows LPE to replace (rather than augment) the original definition with them, speeding up proof search for future examples. The resulting learning algorithm is significantly less computationally expensive than EBG, while also avoiding the potentially vast memory requirements of PE. It also removes the undesirable bias which EBG introduces, where EBG's preference for reusing operational proofs may result in a ‘poor’ proof being selected. We describe LPE and compare its performance with PE and EBG on two constraint satisfaction tasks. Finally, we analyse the conditions in which each of the learning techniques is most effective.