AN EXPERIMENT IN THE APPLICATION OF SIMILARITY-BASED LEARNING TO PROGRAMMING BY EXAMPLE

Programming by example is a powerful way of bestowing on nonprogrammer s the ability to communicate tasks to a computer. When creating proced ures from examples it is necessary to be able to infer the existence o f variables, conditional branches, and loops. This article explores th e role of empirical or ''similarity-based'' learning in this process. For a concrete example of a procedure induction system, we use an exis ting scheme called METAMOUSE which allows graphical procedures to be s pecified from examples of their execution. A procedure is induced from the first example, and can be generalized in accordance with examples encountered later on. We describe how the system can be enhanced with Mitchell's candidate elimination algorithm, one of the simplest empir ical learning techniques, to improve its ability to recognize constrai nts in a comprehensive and flexible manner. Procedure induction is, no doubt, a very complex task. This work revealed usefulness and effecti veness of empirical learning in procedure induction, although it canno t be a complete substitute for specific preprogrammed, domain knowledg e in situations where this is readily available. However, in domains s uch as graphical editing, where knowledge is incomplete and/or incorre ct, the best way to pursue may prove to be a combination of similarity - and explanation-based learning. (C) 1994 John