Inductive Learning - Advanced Artificial Intelligence - page 278

3. Select a description g in G , and take g as a conjunction term of solution set. g does not
cover any negative instance, but it will cover part of positive instances. Then eliminate all
positive instances specific than g from positive instance set (i.e. positive instances
covered by g).
4. For residual positive instances and negative instances, repeat step1, 2 and 3 until all
positive instances are covered. Disjunction of g gotten from each repeat is required
concept.
The disjunction does not cover any negative instance, and every does not

cover any negative instance either. The disjunction covers all positive instances,
and every g covers positive instances eliminated by it. Notice, since there is not a
procedure to modify

g

S , g does not cover all positive instances. However, g at

least covers the positive instance at first step, so g should at least eliminate this

positive instance.
The second solution is referred to as AQ algorithm(Michalski, 1975), which
is similar to the former algorithm. But AQ algorithm uses heuristics to select a
positive instance at the first step, requiring the positive instance is not covered by
several past . Larson improves AQ algorithm, and applies it to spread predicate

calculus representation.

g

7.5 AQ Algorithm for Inductive Learning

In 1969, Michalski proposed AQ learning algorithm, which is an example-based
learning algorithm. AQ algorithm generates disjunction of selected assumption,
which covers all positive examples but does not cover any negative example. Its
basic algorithm is:

Algorithm 7.3 Simple AQ Learning Algorithm

1. Randomly select one positive example as a seed.
2. Generate consistent generalization expression of the example (referred to as star).
3. According to bias standard, select the optimal generalization expression from star. If
needed, it specialize the assumption.
4. If this hypothesis covers all positive examples, then go to step 2.

Michalski proposed AQ11 in 1978 (Michalski and Larson, 1978). AQ11
algorithm searches rule space, repeatedly eliminate candidate elements, and gets
general rules. AQ11 algorithm turns problems of learning discriminative rules
into a series of problems of learning single concept. In order to get rules of class
C i , it takes examples of class C i as positive examples, and all examples of other

classes as negative examples. It can get descriptions that cover all positive
examples but do not cover any negative example, which can be taken as rules of