Literatura: Tom M. Mitchell, Machine Learning, Rozdział 2.

• ex1.m - skrypt pomagajacy przejśc przez pierwszą część laboratoium
• consistent.m - funkcja sprawdzająca zgodność hipotezy ze zbiorem treningowym
• satisfies - funkcja sprawdzająca czy hipoteza jest prawdziwa dla danego elementu ze zbioru uczącego
• findS.m - funkcja implementująca algorytm findS
• listAllHypothesis.m - funkcja generująca wszystkie możliwe hipotezy dla danego zbioru treningowego
• listThenEliminate.m - funkcja implementująca algorytm List-Then-Eliminate

Załóżmy, że mamy następujący zbiór danych:

Opisuje on dni ocenione przez pływaka pod względem tego czy sprzyjamy one treningowi, czy nie. Pierwsze cztery kolumny zawierają dane na temat poszczególnych parametrów pogodowych dnia, natomiast kolumna EnjoySport przechowuje ocenę pływaka.

Każdy z parametrów może przyjmować następujące wartości, które w Octave zapiszemy za pomocą liczb:

Sky = [1,2,3];      %['Sunny','Rainy','Cloudy'];
AirTemp = [1,2];    %['Warm','Cold'];
Humidity =[1,2];    %['Normal','High'];
Wind = [1,2];       %['Strong','Weak'];
Water = [1,2];      %['Warm','Cool'];
Forecast =[1,2];    %['Same','Change'];
Enjoy = [0,1];      %['No','Yes'];

Analogicznie, zbiór danych treningowych będzie zatem wyglądał tak:

%Sky, AirTemp, Humidity, Wind, Water, Forecast
X = [1,1,1,1,1,1;
    1,1,2,1,1,1;
    2,2,2,1,1,2;
    1,1,2,1,2,2]
%Enjoy
C = [1;1;0;1];

Uwaga Ostatnią kolumnę tabeli (Enjoy) przechowujemy w osobnej macierzy C.

Zakładamy, że dla każdego atrybutu funkcja hipotezy będzie opisana za pomocą

• - oznaczającego, że żadna wartość nie jest akceptowana
• - oznaczającego, że każda wartość jest akceptowalna dla tego atrybutu (ekwiwalen z Mitchela)
• konkretnej wartości danego atrybutu np. Warm, wskazując że tylko ta wartość jest akceptowalna dla tego atrybutu.

Na przykład hipoteza opisująca sytuację, ze pływak uważa jedynie zimne dni z dużą wilgotnością (AirTemp = Cold,Humidity = High) za odpowiednie do treningu wyglądałaby następująco:

h = [Inf,2,2,Inf,Inf,Inf]

Zaimplementuj algorytm Find-S, w pliku findS.m. Algorytm wygląda następująco:

1. Initialize to the most specific hypothesis in
2. For each positive training instance
   1. For each attribute constraint in
      1. If the constraint is satisfied by , then do nothing
      2. Else replace in by the next more general constraint that is satisfied by
3. Return

Uwaga Zwróć uwagę, że the most specific hypothesis in H to w przypadku naszej notacji: h=[0,0,0,0,0,0]; Wykorzystaj funkcję zeros, tak aby algorytm działał dla innych danych wejściowych (o innych wymiarach).

Przetestuj działanie za pomocą skryptu ex1.m

Jednym z ograniczeń algorytm Find-S jest to, że podaje on wyłącznie jedno rozwiązanie, podczas gdy hipotez, które są prawdziwe dla naszego zbioru uczącego jest więcej. Te hipotezy określa się mianem tzw. version-spaces. Definiujemy ją następująco:

To że funkcja jest zgodna ze zbiorem uczącym (consistent) oznacza, że:

Zaimplementuj funkcję consistent w pliku consistent.m

Przetestuj jej działanie za pomocą check.m

Zaimplementuj funkcję listAllHypothesis w pliku listAllHypothesis.m

Przetestuj jej działanie za pomocą check.m

Zastanów się Jaki rozmiar będzie miała przestrzeń wszystkich hipotez dla naszego przykładu?

Zaimplementuj w pliku learnThenEliminate.m algorytm wyszukujący version-space dla naszego zbioru uczącego.

Algorytm można opisać następująco:

1. List all possible hypotheses based on attribute domains and assign it to
2. Remove from all hypotheses that are not consistant with , where is a training set
3. Output the list of hypotheses

Przetestuj jego działanie za pomocą skryptu ex1.m oraz check.m.

W Octave programowanie tego typu zagadnień jest nieefektywne i trudne. Znacznie łatwiej poruszać się w problematyce uczenia pojęć używając języka Prolog. Wykorzystując pliki: Wykonaj polecenia poniżej.

?- ['vs'].
?- ['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]

?- ['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.

1. 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.

?- ['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.

?- 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.

Move example 3 (neg) in the beginning of shapes.pl and then load it. That is, VS now learns the concept of „neg”.

?- ['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.

?- ['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.

Generowanie wszystkich możliwych hipotez dla danego zbioru uczącego jest wysoce niewydajne w przypadku danych, których atrybuty moga przyjmować wiele wartości.

Algorytm Candidate-Elimination podaje wszystkie możliwe hipotezy pasujące do danego zbioru uczącego za pomocą dolnego G (najbardziej ogólnego ograniczenia zgodnego ze zbiorem uczącym) i górnego ograniczenia S (najbardziej szczegółowego ograniczenia zgodnego ze zbiorem uczącym):

Spróbuj zaimplementować algorytm Candidate-Elimination w Octave, bazując na instrukcjach: Instrukcje