Machine Learning - Spring 2004 ============================== Lab experiments 2 ----------------- Programs needed: vs.pl Data files: shapes.pl, taxonomy.pl, animals.pl, loandata.pl ---------------------------------------------------------------- 1. USING VS IN INTERACTIVE MODE ------------------------------- ?- ['c:/prolog/vs']. ?- ['c:/prolog/taxonomy']. NOTE that every input should end with FULL STOP (.). "p" stands for positive and "n" for negative. ?- vs. Type the first positive example: | [red,square]. G-set: [[color, shape]] S-set: [[red, square]] Generate next example (y/n) ? n. Type the example: | [blue,rectangle]. Classification of the example ? [p/n] p. G-set: [[color, shape]] S-set: [[mono, 4-sided]] Generate next example (y/n) ? n. Type the example: | [pink, triangle]. Classification of the example ? [p/n] n. G-set: [[color, 4-sided], [mono, shape]] S-set: [[mono, 4-sided]] Generate next example (y/n) ? y. Next example: [orange, rectangle] Classification of the example ? [p/n] p. The consistent generalization is: [color, 4-sided] 2. USING VS IN BATCH MODE (EXAMPLES ARE SUPPLIED IN A FILE) ----------------------------------------------------------- ?- ['c:/prolog/shapes']. NOTE that vs.pl and taxonomy.pl must be also loaded. The class of the first example is assumed to be positive (+). All other classes are considered negative. That is, to learn a concept an example from this concept should appear in the file first. ?- batch. +[red, square] G-set: [[color, shape]] S-set: [[red, square]] +[blue, rectangle] G-set: [[color, shape]] S-set: [[mono, 4-sided]] -[pink, triangle] G-set: [[color, 4-sided], [mono, shape]] S-set: [[mono, 4-sided]] -[blue, ellipse] G-set: [[color, 4-sided], [mono, polygon]] S-set: [[mono, 4-sided]] +[orange, square] G-set: [[color, 4-sided]] S-set: [[color, 4-sided]] The consistent generalization is: [color, 4-sided] NOTE that the concept is learned (G and S sets converge into one hypothesis) after reading the last example in the file (shapes.pl). This is not always the case. Generally there may be two possible situations: 1. The concept is learned before reaching the last example in the file. In this case the algorithm stops, although there may be more examples in the file (both positive and negative) that are consistent with the concept. 2. The algorithm reaches an example that cannot be incorporated into the version space. That is, there are no consistent hypotheses with the supplied set of examples in the given representaion language. Below is an example of Situation 1. Situation 2 is illustrated in Experiment 4. ?- ['c:/Prolog/loandata']. ?- batch. +[yes, comp, f, no] G-set: [[?, ?, ?, ?]] S-set: [[yes, comp, f, no]] -[no, comp, f, yes] G-set: [[?, ?, ?, no], [yes, ?, ?, ?]] S-set: [[yes, comp, f, no]] +[yes, comp, m, no] G-set: [[?, ?, ?, no], [yes, ?, ?, ?]] S-set: [[yes, comp, ?, no]] +[yes, car, f, yes] G-set: [[yes, ?, ?, ?]] S-set: [[yes, ?, ?, ?]] The consistent generalization is: [yes, ?, ?, ?] NOTE that +[yes, car, f, yes] is not the last example in the file loandata.pl. 3. INCONSISTENT HYPOTHESIS SPACE (INTERACTIVE MODE) --------------------------------------------------- ?- vs. Type the first positive example: | [red,square]. G-set: [[color, shape]] S-set: [[red, square]] Generate next example (y/n) ? y. Next example: [red, triangle] Classification of the example ? [p/n] n. G-set: [[color, 4-sided]] S-set: [[red, square]] Generate next example (y/n) ? y. Next example: [red, rectangle] Classification of the example ? [p/n] p. G-set: [[color, 4-sided]] S-set: [[red, 4-sided]] Generate next example (y/n) ? n. Type the example: | [blue,triangle]. Classification of the example ? [p/n] p. There is no consistent concept description in this language ! NOTE that [blue,triangle] is a positive example outside the version space. This example cannot be included in the concept, because of the restriction on the concept representation language not allowing disjunctive concepts. 4. INCONSISTENT HYPOTHESIS SPACE (BATCH MODE) --------------------------------------------- Move example 3 (neg) in the beginning of shapes.pl and then load it. That is, VS now learns the concept of "neg". ?- ['c:/prolog/shapes']. ?- batch. +[pink, triangle] G-set: [[color, shape]] S-set: [[pink, triangle]] -[red, square] G-set: [[color, 3-sided], [poly, shape]] S-set: [[pink, triangle]] -[blue, rectangle] +[blue, ellipse] G-set: [] S-set: [] There is no consistent concept description in this language ! NOTE that after -[blue, rectangle] the G and S sets are not shown. This happens when the boundaries of the version space do not change after the current example. 5. PARTIALLY LEARNT CONCEPT --------------------------- ?- ['c:/prolog/animals']. ?- batch. +[hair, t, t, land, f, f] G-set: [[?, ?, ?, ?, ?, ?]] S-set: [[hair, t, t, land, f, f]] +[none, t, t, sea, f, f] G-set: [[?, ?, ?, ?, ?, ?]] S-set: [[?, t, t, ?, f, f]] +[hair, t, t, sea, t, f] G-set: [[?, ?, ?, ?, ?, ?]] S-set: [[?, t, t, ?, ?, f]] +[hair, t, t, air, f, f] -[scales, f, f, sea, t, t] G-set: [[?, ?, ?, ?, ?, f], [?, ?, t, ?, ?, ?], [?, t, ?, ?, ?, ?]] S-set: [[?, t, t, ?, ?, f]] -[scales, f, f, land, t, f] G-set: [[?, ?, t, ?, ?, ?], [?, t, ?, ?, ?, ?]] S-set: [[?, t, t, ?, ?, f]] -[scales, f, f, sea, t, f] -[feathers, f, t, air, t, f] G-set: [[?, t, ?, ?, ?, ?]] S-set: [[?, t, t, ?, ?, f]] -[feathers, f, t, land, t, f] -[none, f, f, land, t, f] No more examples. NOTE that after all examples are processed the G-set and the S-set do not converge. So, we have a partially learnt concept and need more examples to converge to a single hypothesis.