Synthesis from examples

Section 3.2.4, we define the niche of algorithm synthesis from examples within empirical learning from examples, and give pointers to the literature in Section 3.2.5. 

Algorithm Synthesis from Examples as a Niche of Learning... 

But algorithm synthesis from examples is a highly specialized niche within empirical learning from examples. Table 3-1 summarizes the differences between the concerns of algorithm synthesis (as we view it) and the mainstream concerns (so far) of empirical learning. 

Table 3-1 Algorithm synthesis from examples as a niche of learning...

The mentioned Basic Synthesis Theorem constitutes a major breakthrough, as it provides a firm theoretical foundation to synthesis from examples. Summers also describes a technique that automatically introduces accumulator parameters when no recurrence relations can be found this amounts to descending generalization [Deville 90]. The results of Summers have spawned considerable efforts for generalization and improvement, especially by [Jouannaud and Kodratoff 83] [Kodratoff and Jouannaud 84]. Their achievements are very encouraging as the developed sequence matching algorithms are very efficient. 

Heuristic synthesis from examples involves more or less heavy use of heuristics in order to prune the search space. 

Heuristic synthesis from examples is performed by the systems of [Hardy 75], [Shaw et al. 75], [Siklossy and Sykes 75], and [Biggerstaff 84], in the sense that they fill in the place-holders of a LISP divide-and-conquer schema (see Chapter 8) in a plausible way according to the given examples. 

In Section 3.2.4, we have defined algorithm synthesis from examples as a niche of empirical learning from examples. As a reminder, for algorithm synthesis, we are here only interested in the setting with human specifiers who know (even if only informally) the intended relation, and who are assumed to choose only examples that are consistent with the intended relation. Moreover, the intended relation is assumed to have a recursive algorithm. There is a general consensus that a synthesizer from examples would be a useful component of any larger synthesis system. So we now draw some conclusions about the approaches surveyed in the previous two sections. 

P. Flener. Logic Algorithm Synthesis from Examples and Properties. Ph.D. Thesis, Univ. Catholique de Louvain, Louvain-la-Neuve (Belgium), 1993. 

J.-P. Jouannaud and Y. Kodratoff. Program synthesis from examples of behavior. In [Biermann and Guiho 83], pp. 213-250. 

This material thus constitutes an interesting complement to the field of ILP, as well as a new boost to program synthesis from examples, which is generally believed to be a necessary component of large automatic programming systems. 

---