Intended relation

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. 

Let be the relation one has in mind when elaborating a specification of a procedure for predicate r. We call the intended relation, in contrast to the relation actually specified, called the specified relation. This distinction is very important in general, but crucial with incomplete specifications, where one deliberately admits a gap between the two. 

It requires multiple, ground, single-predicate, relational, positive and negative, presynthesis examples that are chosen in a consistent way by a human specifier who knows the intended relation. 

Let be the / -ary intended relation. The final objective is to obtain a logic program that succeeds on the /z-tuples of 1, and fails on the /i-tuples of (which is the complement of in the set of all ground /2-tuples over the universe U of terms). 

It is clear that the specified relation is usually different from the intended relation. It is usually expected to be a subset of the intended relation, though. It is also clear that EP r) is not always the complement of EP (r), We however assume that EP(r) is internally consistent, that is that the intersection between EP (r) and EP (r) is empty. 

Note that 3 captures the intended relation since the interpretation of r/n in 3 is So does not have to be explicitly considered in the correctness criteria. 

The idea behind correctness of a logic algorithm wrt its intentions is to state that the intended relation is identical to the relation computed by LA(r) ... 

Correctness thus states an identity, in the Herbrand models of LA(r), between the intended relation and the interpretation of predicate rin. The second condition, which in general is not a consequence of the first one, is necessary to handle logic algorithms with negation (also see [Deville 90]). 

The total correctness of a logic algorithm wrt its intended relation can however be re-expressed more conveniently, yielding what we call the actual criteria ... 

Finally, there is consistency of a specification wrt the intentions. For instance, consistency of the examples E r) wrt the intended relation HL means that the positive examples are contained in and that the negative examples are contained in its complement %... 

The specified relation of a consistent specification is thus a subset of the intended relation. Moreover, if LA(r) is partially or totally correct wrt E(r) (respectively P(r)), and E(f) (respectively P(r)) is consistent with then LA(f) is partially correct wrt If there is no formal definition of the intended relation then some correctness criteria cannot be applied in a formal way. But they can be used to state features and heuristics of a synthesis mechanism. 

It is also important to compare logic algorithms for the same intended relation % Indeed, this is useful in stepwise synthesis to compare intermediate logic algorithms, and to establish progression criteria. 

The second hypothesis of assertion (2) ensures that the introduced literals are redundant with the already existing ones. In other words, as the proof shows, we then actually have LA r) = LA r). The second hypothesis of assertion (1) ensures that the introduced literals are redundant with the intended relation... 

The reason why only the properties other than Pi are included in % is that the recursive calls of LA r) had better not be resolved using LA r) itself, as we have no guarantee yet of the total correctness of LA r) wrt the intended relation % So these other properties should be used for the resolution of these recursive calls, because properties are assumed to be a consistent, albeit incomplete, approximation of % This is reflected in the search rule described below. 

Let s close in now on the MSG Method. Intuitively, its objective is to infer a logic algorithm of a predicate r n, given a finite set of examples of rhi The method should be applicable if the intended relation (from which the examples are extracted) can be expressed by a logic algorithm that is defined solely in terms of the =/2 primitive (hence is non-recursive, among others). This is feasible iff, in the intended relation, some parameters are somehow syntactically constructed from some other parameters. 

The problem is correctly solved iff the natural extension of (r) is the unknown intended relation This is of course impossible to verify, so the main issue is to infer a logic algorithm that gives maximal confidence that the problem is correctly solved. 

In terms of alternative techniques to the MSG Method, there is of course the whole literature on empirical learning, and inductive logic programming (ILP), as surveyed in Chapter 3. But it should be noted that the MSG Method only aims at the synthesis of a sub-class of concept descriptions, namely non-recursive algorithms that are implemented in terms of the =/2 primitive only, and whose intended relation, though unknown as a whole, is however known to feature a given dataflow pattern between... 

Another crucial question that pops up is Why not use a classical concept learner The reason for not doing so is that a concept learner, in its incremental approach and blind enumeration, doesn t take advantage of the knowledge about the dataflow pattern between the parameters of the intended relation. Concept learners are a reasonable approach if nothing is known about the intended relation. But this is not the case here, and more practical methods can thus be developed. 

Answers such as / don t know should also be taken into account. Classification queries are a particular case of universal queries and of existential queries, namely when there are no variables in A. Universal queries are a particular case of conditional queries, namely when C reduces to true. Similarly to our assumption about the consistency of specifications with intended relations, we assume that the specifier s answers to queries are noise-free. Note that we talk about questions to a (human) specifier here, and not about the more general problem of asking questions to some oracle. At this level of the discourse, we are not interested in knowing whether a mechanized oracle is queried during synthesis or not. 

The sample synthesis ends here. It can be shown that LA-j compress) is totally correct wrt its intended relation. ... 

Assuming a binary intended relation and its corresponding predicate r/2, we suppose there is a specification EP r), whose example set is defined as follows ... 

First, the support of the extrinsic and logarithmic decomposition strategies is quite difficult, as the required knowledge about the intended relation is not available. This apparent drawback may be alleviated however by the observation that the logic algorithms LA r-inhX) and LA r-ext-Y) are by construction quite similar. Compare... 

Example 13-4 During the synthesis of LAipermutation-int-L), the MSG Method is invoked as in Example 10-12. The first result is subject to Heuristic 13-2, because there are too many cliques, which lets expect that LA(pcPermutation) wouldn t behave as intended on a goal such aspcPermutation a,[b,c4,ef]R). The same holds for the second result. The intended relation for LA(pcPermutation) is indeed the one underlying the stuff/3 predicate, and thus requires a recursive logic algorithm. We show in Section 14.2.4 how this can be obtained. 

Negative examples (also called counter-examples) have been omitted from the specification format adopted in Section 11.1. We are now able to provide the motivation for this decision. Counter-examples are useless in a divide-and-conquer approach, because the relation is built from positive examples. And only positive examples can be used in order to explain how a specific positive example is built . Counterexamples could however be used to check whether the synthesized logic algorithm isn t too general compared to the intended relation. This is subject to future research. 

Note that if properties could also be equivalence statements rather than only definite clauses, then properties would actually be a generalization of negative examples, because they would then embody conditions about when the intended relation does not hold. Most properties are actually equivalence statements. For instance, all properties in the sample specifications of Section 6.2, except for the informative property P2 of EP(efface), would also be correct if they were equivalences. The current version of the synthesis mechanism would only use the //parts of such extended properties in Step 7 for the synthesis of the discriminants. But an extended version performing the above-mentioned over-generalization-check could use the only-if parts to infer negative examples, rather than relying on their explicit presence in the specification. 

A possible solution is to automatically infer a property set of the intended relation and then to use an entire synthesis mechanism (such as the one described in the two previous chapters) in order to infer a logic algorithm that is complete wrt the given examples and inferred properties. We here describe such a method, called the Synthesis Method, which is specific to the synthesis of the Processj and Composej predicate-variables of the divide-and-conquer schema. 

This logic algorithm is totally correct wrt the intended relation. Quite a few atoms can be simplified away (the last two, for instance). ... 

The planned use of our synthesis mechanism is for situations where only fragmentary information is available about the intended relation, or where the specifier is unwilling (if not unable) to come up with a more complete description of the intended relation. By the phrase incomplete specifications , we thus mean specifications where some information about the intended relation is deliberately withheld and where the synthesis is expected to extrapolate. We thus exclude incomplete specifications in the sense of evolutionary specifications, where one also deliberately withholds some information, but without expecting any extrapolation. The idea there is to gradually refine an algorithm by adding functionalities to its specification. 

---