Learning by Refining Algorithm Sketches

. In this paper we suggest a mechanism that improves significantly the performance of a top-down inductive logic programming (ILP) learning system. This improvement is achieved at the cost of giving to the system extra information that is not difficult to formulate. This information appears in the form of an algorithm sketch: an incomplete and somewhat vague representation of the computation related to a particular example. We describe which sketches are admissible, give details of the learning algorithm that exploits the information contained in the sketch. The experiments carried out with the implemented system (SKIL) have demonstrated the usefulness of the method and its potential in future applications. 1 INTRODUCTION Construction of medium size programs remains still somewhat out of reach of many ILP systems, despite many significant advances in this area. It appears that more information needs to be given besides describing the admissible/inadmissible combinations of input and ..