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

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
Sprawdź poprawność działania algorytmu skryptem check.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.