A formalization of explanation-based macro-operator learning

摘要: In spite of the popularity Explanation-Based Learning (EBL), its theoretical basis is not well-understood. Using a generalization Probably Approximately Correct (PAC) learning to problem solving domains, this paper formalizes two forms macro-operators and proves sufficient conditions for their success. These EBL, called "Macro Caching" "Serial Parsing," respectively exhibit distinct sources power or "bias": sparseness solution space decomposability problem-space. The analysis shows that exponential speedup can be achieved when either these biases suitable domain. Somewhat surprisingly, it also computing preconditions necessary obtain speedups. oretical results are confirmed by experiments in domain Eight Puzzle. Our work suggests best way address utility EBL implement bias which exploits problem-space structure set domains one interested learning.