Quantitative Results Concerning the Utility of Explanation-Based Learning

Paper · 1988 · Steven Minton

Summary

Explanation-based learning (EBL) can derive search control knowledge for domain-independent problem solvers such as planners. But learned rules carry a hidden price: each one must be matched during search to check whether it applies. If that matching cost exceeds the savings, learning slows the system down. Minton calls this the utility problem. He also argues that faster hardware or better indexing cannot remove it, because the number and size of learned descriptions are unbounded and matching them can be NP-complete.

The paper describes PRODIGY/EBL, a learner built on a STRIPS-style planner with separate control rules. It addresses the problem in three steps:

it uses heuristics to choose which trace events to explain, across several meta-level target concepts;
it compresses the resulting explanations;
it estimates and then empirically checks the payoff of each rule, discarding rules that do not pay off.

Experiments in three domains show that the system improves performance over large problem sets. Removing any component sharply reduces the benefit. The work matters because it showed that learning must account for both cost and benefit to be useful.

Key points

PRODIGY learns from four meta-level target concepts: SUCCEEDS and GOAL-INTERACTION yield preference rules, FAILS yields rejection rules, and SOLE-ALTERNATIVE yields selection rules.
Evaluation domains were blocksworld, a STRIPS robot domain and a scheduling domain. Most explained examples were filtered out:
- Blocksworld: 328 explained, 69 estimated useful, 19 validated.
- STRIPS domain: 588 explained, 130 estimated useful, 30 validated.
- Scheduling: 946 explained, 243 estimated useful, 37 validated.
Ablations in blocksworld showed each component matters:
- Turning off only domain-specific compression made test performance about 40% worse.
- Turning off both later compression stages made performance slightly worse than no learning at all.
- Skipping empirical validation made performance about 65% poorer.
Learned control rules generally beat selective and unselective macro-operator learning, which sometimes degraded performance. In blocksworld, selective macros matched PRODIGY's speed, but their solutions were roughly 50% longer because they skipped over state-cycle checks.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Institutions

🎓Carnegie Mellon UniversityPittsburgh ·

United States633 works · 195,217 citations

Fields, topics and concepts

📚 Shelves 2Computer Science · 19,503 works Artificial Intelligence · 18,805 works

Cite

Cite as Steven Minton. 1988. Quantitative Results Concerning the Utility of Explanation-Based Learning. AAAI 1988.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{minton1988quantitative,
  title = {{Quantitative Results Concerning the Utility of Explanation-Based Learning}},
  author = {Steven Minton},
  booktitle = {AAAI 1988},
  year = {1988},
  doi = {10.1016/0004-3702(90)90059-9},
  url = {https://doi.org/10.1016/0004-3702(90)90059-9}
}

References

15 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

Brown, F.M. “An Experimental Logic Based on the tun&mental Deduction Principal”. AtiificiaZ Znfelligence 30,2 find
DeJong,G.F. An Alternative and Mooney, R. “Explanation-Based View”. Machine Learning 1,2 (1986). Learning: find
Fikes, R., Hart, P. and Nilsson, N. “Learnin and executing generalized robot plans”. Arti@iaZ ZnteZZigence 3 ,4 (1972). find
Garey, M.R. and Johnson, D.S.. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and co., 1979. find
Kahn, K. “Partial Evaluation as an Exam le of the Relationship between Programming Metho i ology and AI”. AI Magazine 5,l (1984). find
Keller, R. M. Defining Operationality for Explanation-Based Learning. Proceedings of AAAI-87, Seattle, Washington, 1987. find
Minton, S. Selectively Generalizing plans for Problem Solving. Proceedin s of the Ninth International Joint Conference on Arti P lcial Intelligence, Los Angeles, CA, 198.5. — Selectively Generalizing Plans for Problem-Solving
Minton, S. and Carbonell, J.G. Strategies for Learning Search Control Rules: An Explanation-Based Approach. Proceedings of the Tenth International Joint Conference on Artificial Intelligence, Milan, ITALY, 1987. find
Minton, S.. Learning Effective Search Control Knowledge: An E Zanafion-Based Awyoach. Kluwer Academic Publishers, 19 T 8. Also appears as tech. report CMU-CS-88-133, Computer Science Dept., Carnegie-Mellon Univ. find
Mitchell, T., Utgoff, P. and Banerji, R. Learning by Experimentation: Acquiring and Refinin Problem-Solving Heuristics. In Machine Learning: An Arti If ciuZ ZnteZZigence Approach, Carbonell, J., Michalski, R. and Mitchell, T., Eds., Tioga Publishing Co., 1983. find
Mitchell, T., Keller, R. and Kedar-Cabelli, S. “Explanation-Based Generalization: A Unifying View”. Machine Learning 2,l (1986). find
Frieditis, A.E. and Mostow, J. PROLEARN: Toward a Prolog Interpreter that Learns. Proceedings of AAAI-87, Seattle, WA., 1987. find
Rosenbloom, P.S. and Laird, J.E. Map ing explanation-based generalization onto SOAR. Procee cp ings of AAAI-86, Philadelphia, PA, 1986. find
Silver, B. Precondition Analysis. In Machine Learning: An Artif-iciaZ Intelligence A roah, VoZ ZZ, Michalski, R.S., Carbonell, J.G. and Mitchell, T. l!!r ., Eds., Morgan Kaufmann, 1986. find
Tambe, M. and Newell, A. Some Chunks are Expensive. Proceedings of the Fifth International Conference on Machine Learning, Ann Arbor, MI, 1988. find

Updated 3 November 2026

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/minton-1988-quantitative-results-concerning-utility-explanation/