Why PRODIGY/EBL Works

Oren Etzioni

Explanation-Based Learning (EBL) fails to accelerate problem solving in some problem spaces. How do these problem spaces differ from the ones in Minton’s experiments [1988b]? Can minute modifications to problem space encoding drastically alter EBL’s performance? Will PRODIGY/EBL'S success scale to real-world domains? This paper presents a formal theory of problem space structure that answers these questions. The central observation is that PRODIGY/EBL relies on finding nonrecursive explanations of PRODIGY'S problem-solving behavior. The theory explains and predicts PRODIGY/EBL'S performance in a wide range of problem spaces. The theory also predicts that a static program transformer, called STATIC, can match PRODIGY/EBL'S performance in some cases. The paper reports on an array of experiments that confirms this prediction. STATIC matches PRODIGY/EBL'S performance in each of Minton’s problem spaces.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.