Automatic Ordering of Subgoals --- A Machine Learning Approach

Shaul Markovitch and Paul Scott. Automatic Ordering of Subgoals --- A Machine Learning Approach. In Proceedings of the North American Conference on Logic Programming, 224-242 Cleveland, Ohio, USA, 1989.

Abstract

This paper describes a learning system, LASSY, which explores domains represented by Prolog databases, and use its acquired knowledge to increase the efficiency of a Prolog interpreter by reordering subgoals. The system creates a model of the tasks it faces and uses the model to generate informative training tasks. While performing the training tasks the system updates its inductive knowledge base which includes statistics about number of solutions and costs of various subgoals calling patterns. The collected averages are used by a subgoal ordering procedure to estimate the costs of subgoals sequences during its search for a good ordering. The paper contains a detailed analysis of the cost computation and a detailed account of the ordering procedure. Experiments done with LASSY show an improvement of performance by a factor of 10.

Keywords: Speedup Learning

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Markovitch:1989:AOS,
  Author = {Shaul Markovitch and Paul Scott},
  Title = {Automatic Ordering of Subgoals --- A Machine Learning Approach},
  Year = {1989},
  Booktitle = {Proceedings of the North American Conference on Logic Programming},
  Pages = {224--242},
  Editor = {Ewing Lusk and Ross Overbeek},
  Address = {Cleveland, Ohio, USA},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-Scott-naclp1989.pdf},
  Keywords = {Speedup Learning},
  Secondary-keywords = {Logic Programming, Learning to Order},
  Abstract = {
    This paper describes a learning system, LASSY, which explores
    domains represented by Prolog databases, and use its acquired
    knowledge to increase the efficiency of a Prolog interpreter by
    reordering subgoals. The system creates a model of the tasks it
    faces and uses the model to generate informative training tasks.
    While performing the training tasks the system updates its
    inductive knowledge base which includes statistics about number of
    solutions and costs of various subgoals calling patterns. The
    collected averages are used by a subgoal ordering procedure to
    estimate the costs of subgoals sequences during its search for a
    good ordering. The paper contains a detailed analysis of the cost
    computation and a detailed account of the ordering procedure.
    Experiments done with LASSY show an improvement of performance by
    a factor of 10.
  }

  }