Proceedings

Towards a General Framework for Composing Disjunctive and Iterative Macro-operators

Download BibTeX Cite

Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Machine Learning. Pages 596-601.

© 1989 International Joint Conferences on Artificial Intelligence

Abstract

Inducing disjunctive and iterative macro-operators from empirical problem-solving traces provides a more powerful knowledge compilation method than simple linear macro-operators. Whereas earlier work focused on w hen to create iterative macro-operators, this paper addresses how to form them, combining proven optimization methods such as extraction of loop invariants, with techniques for further optimizing RETEmatch efficiency. The disjunctive and iterative composition processes have been implemented in FERMI and its underlying production system language. Empirical results confirm substantial rule-match speedups and system performance improvements in different application domains.

  1. [Anderson, 1983] Anderson, J. A. Acquisition of Proof Skills in Geometry. In R. S. Michalski, J. G. Carbonell and T. M. Mitchell (editors), Machine Learning, An Ar- tificial Intelligence Approach. Tioga Press, Palo Alto, CA,1983.
  2. [Bentley et al, 1978] Bentley, J., Haken, D. and Saxe, J. A General Method for Solving Divide-and-Conquer Recur- rences. Technical Report, Carnegie Mellon University Computer Science Department, 1978.
  3. [Carbonell, 1983] Carbonell, J. G. Learning by Analogy: Formulating and Generalizing Plans from Past Ex- perience. In R. S. Michalski, J. G. Carbonell and T. M. Mitchell (editors), Machine Learning, An Artificial Intelligence Approach. Tioga Press, Palo Alto, CA. 1983.
  4. [Carbonell, 1986] Carbonell, J. G. Derivational Analogy: A Theory of Reconstructive Problem Solving and Expertise Acquisition. In Michalski, R. S., Carbonell, J. G. and Mitchell, T. M. (editors), Machine Learning, An Artificial Intelligence Approach, Volume II. Morgan Kaufmann, 1986.
  5. [Carbonell & Hood, 1986] Carbonell, J. G. and Hood, G. The World Modelers Project: Learning in a Reactive Environment. In Mitchell, T. M., Carbonell, J. G. and Michalski, R. S. (editors), Machine Learning: A Guide to Current Research, pages 29-34. Kluwer Academic Press, 1986.
  6. [Cheng & Carbonell, 1986] Cheng, P. W. and Carbonell, J. G. Inducing Iterative Rules from Experience: The FERMI Experiment. In Proceedings of AAAI-86, 1986.
  7. [DeJong & Mooney, 1986] DeJong, G. F. and Mooney, R. Explanation-Based Learning: An Alternative View. Machine Learning Journal, 1(2), 1986.
  8. [Doyle, 1984] Doyle, J. Expert Systems Without Com- puters. AI Magazine, 5(2):59-63, 1984.
  9. [Fikes, 1971] Fikes, R. E. and Nilsson, N. J. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 2:189-208, 1971. IJCAI
  10. [Forgy, 1982] Forgy, Charles L. Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem. Artificiallntelligence, 19:17-37, 1982.
  11. [Hammond, 1987] Hammond, K. J. Learning and Reusing Explanations. In Proceedings of the Third International Workshop on Machine Learning, pages 141-147, 1987.
  12. [Iba, 1979] Iba, G. A. Learning Disjunctive Concepts From Examples. Master's thesis, M.I.T., 1979.
  13. [Iba, 1988] Iba, G. A Heuristic Approach to the Discovery of Macro-Operators. Technical Report, GTE Laboratories, 1988. Tech Report TR88-506.1. Korf, 1985]
  14. Korf, R. E. Macro-operators: A Weak Method for Learning. Artificial Intelligence , 26:35-77, 1985.
  15. [Laird et al, 1986] Laird, J. E., Rosenbloom, P. S. and Newell, A. Chunking in SOAR: The Anatomy of a General Learning Mechanism. Machine Learning, 1(1):11-46, 1986.
  16. [Minton, 1985] Minton, S. Selectively Generalizing Plans for Problem Solving. Proceedings of AAAI-85, 1:596-599, 1985. IJCAI
  17. [Minton & Carbonell, 1987] Minton, S. N. and Carbonell, J. G. Strategies for Learning Search Control Rules: An Explanation-Based Approach. In Proceedings of IJCAI-87, Milan, Italy, 1987. IJCAI
  18. [Minton et al, 1988] Minton, S. N., Carbonell, J. G., Knoblock, C. A. and Kuokka, D. R. Explanation-Based Learning: Improving Problem Solving Performance through Experience. In Carbonell, J. (editor), Paradigms for Machine Learning. (to appear), 1988.
  19. [Mitchell et al, 1986] Mitchell, T. M., Keller, R. M. and Kedar-Cabelli, S. T. Explanation-Based Generalization: A Unifying View. Machine Learning, 1:47-80, 1986.
  20. [Newell, 1981] Newell, A. and Rosenbloom, P. Mechanisms of Skill Acquisition and the Law of Practice. In J. R. Anderson (editor), Cognitive Skills and Their Acquisition. Hillsdale, NJ: Erlbaum Assoc., 1981.
  21. [Quinlan, 1986] Quinlan, J. R. Induction of Decision Trees. Machine Learning, 1:81-106, 1986.
  22. [Riddle, 1988] Riddle, Patricia J. An Approach for Learning Problem Reduction Schemas and Iterative Macro- operators. In Proceedings of the First International Workshop in Change of Representation and Inductive Bias, 1988.
  23. [Sankoff, 1983] Sankoff, David and Kruskal, Joseph B. An Anthology of Algorithms and Concepts for Sequence Comparison. In David Sankoff and Joseph B. Kruskal (editors), Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, pages 265-310.
  24. [Schank, 1982] Schank, R. C. Dynamic Memory. Cambridge University Press, 1982.
  25. [Schank, 1983] Schank, R. C. The Current State of AI: One Man's Opinion. AI Magazine, IV(1):1-8, 1983.
  26. [Shavlik & DeJong, 1987] Shavlik, F. W. and DeJong, G. F. An Explanation-Based Approach to Generalizing Number. In Proceedings of IJCAI-87, 1987. IJCAI
  27. [Shell & Carbonell, 1986] Shell, P. and Carbonell, J. G. The FRuleKit Reference Manual. 1986.CMU Computer Science Department internal paper.
  28. [Tallis, 1988] Tallis, H. Tuning Rule-Based Systems to Their Environments. In Proceedings of the Fourth Inter- national Workshop on Machine Learning, pages 8-14, 1988.
  29. [Tambe, 1988] Tambe, M. and Newell, A. Some Chunks are Expensive. In Proceedings of the Fourth International Workshop on Machine Learning, pages 451-458, 1988.
  30. [Wulf, 1975] Wulf, William A. The Design of an Optimiz- ing Compiler. American Elsevier Pub. Co., 1975.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards