2.4.3 Search Control

Given the task of improving a rule YAILS uses the following algorithm :

Obtain the best specialization of the rule

Obtain the best generalization of the rule

IF there is an improvement in some of the transformations THEN

Choose the best transformation and recursively invoke the search procedure with this new point of the search space

ELSE

There is no possible improvement to the actual rule

On the other hand the task of finding the best specialization of a rule is done as follows :

Obtain the candidate set of add condition specializations

Obtain the candidate set of restricting intervals specializations

Choose the best quality complex from the union of those sets

The same type of strategy is followed on the task of obtaining the best generalization of a rule. This operations are of course computationally heavy and highly dependent on the domain which restricts the referred sets. Nevertheless there are several heuristics used inorder to restrict to the maximum the candidate sets. For example whenever YAILS tries to specialize a rule it doesn't try to add all possible selectors to it. Instead of doing that it starts by choosing all attributes not being tested already on the rule. With these attributes YAILS builds a set of candidate selectors using a set of values which is obtained from the difference between the set of all values and the set of the values that the incorrectly covered examples have. For example for the candidate attribute "color" we could have the following situation :

Another example of a search control heuristic is the one used whenever YAILS tries to generalize a rule due to the fact that it didn't cover an example of the same concept. In this case YAILS observes the conditions of the rule that weren't satisfied by the example and only those are used for drop-condition generalizations.