Laboratorium 2 - Concept Learning

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

Pliki do pobrania: Contcept Learning

Lista i opis plików

Pliki oznaczone znakiem wykrzyknika (:!:) należy wypełnić własnym kodem

  • 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
  • vs.pl - plik z programem do drugiej części laboratorium
  • animals.pl loandata.pl shapes.pl taxonomy.pl - pliki z danymi do drugiej części laboratorium

Zbiór danych

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

SkyAirTempHumidityWindWaterForecastEnjoy
SunnyWarmNormalStrongWarmSameYes
SunnyWarmHighStrongWarmSameYes
RainyColdHighStrongWarmChangeNo
SunnyWarmHighStrongCoolChangeYes

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.

Hipoteza

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

  • $0$ - oznaczającego, że żadna wartość nie jest akceptowana
  • $Inf$ - 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]

Find-S

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

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

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

List-Then-Eliminate

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 $D$ jest więcej. Te hipotezy określa się mianem tzw. version-spaces. Definiujemy ją następująco:

$$VS_{H,D} = {h \in H | Consistent(h,D)}$$

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

$$ Consistent(h,D) = (\forall<x,c(x)> \in D) h(x) = c(x)$$

Consistent

Zaimplementuj funkcję consistent w pliku consistent.m

Pamietaj, ze hipoteza h jest spójna/zgodna ze zbiorem treningowym X i wartosciami C, wtedy i tylko wtedy gdy dla każdego elementu ze zbioru X zachodzi własność: $h(x) = c(x)$

ListAllHypothesis

Zaimplementuj funkcję listAllHypothesis w pliku listAllHypothesis.m

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

ListThenEliminate

Zaimplementuj w pliku listThenEliminate.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 $H$
  2. Remove from $H$ all hypotheses that are not consistant with $D$, where $D$ is a training set
  3. Output the list of hypotheses

Version Space i Prolog

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:

  • animals.pl
  • loandata.pl
  • shapes.pl
  • taxonomy.pl
  • vs.pl

Prześledź i przeanalizuj działanie programu opisanego poniżej.

Używanie VS w trybie interaktywnym

?- ['vs'].
?- ['taxonomy'].

Uwaga Każde polecenie (łącznie z wprowadzonymi danymi) musi być zakończone znakiem kropki! „p” oznacza pozytywny przykład, „n” oznacza negatywny.

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

Używanie VS w trybie wsadowym (przykłady są dostarczone w pliku)

?- ['shapes'].

Uwaga Pliki vs.pl oraz taxonomy.pl muszą zostać również załadowane! Pierwszy przykład jest uznawany jako pozytywny („p”). Wszystkie pozostałe uznawane są za negatywne („n”). To znaczy, aby nauczyć program jakiegoś pojęcia, przykład z tego pojęcia musi znaleźć się jako pierwszy w pliku.

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

Uwaga! Pojęcie zostało nauczone po przeczytaniu ostatniego przykładu z pliku shapes.pl. Nie zawsze tak musi być. Dopuszczalne są dwie możliwości:

  1. Pojęcie zostaje nauczone przez końcem pliku W tym przypadku algorytm zatrzymuje się, mimo, ze może być więcej przykładów w pliku (pozytywne i negatywne) które są zgodne („consistent”) z pojęciem
  2. Algorytm osiąga przykład, który nie może zostać wcielony do version space. To znaczy - nie ma spójnych hipotez z dostarczonym zbiorem danych.

Poniżej przedstawiona została sytuacja pierwsza.

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

Uwaga =[yes, car, f, yes] nie jest ostatnim przykładem w pliku lonedata.pl

Niespójny zbiór danych (Wersja interaktywna))

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

Uwaga Przykład [blue,triangle] jest przykładem pozytywnym spoza version space. Ten przykład nie może być zawarty w pojęciu ponieważ w tym języku opisu pojęć nie dopuszczamy rozłącznych pojęć.

Niespójne hipotezy (Wersja wsadowa)

Przestaw 3 przykłady neg na początek pliku shapes.pl a anstępnie załaduj go. Dzieki temu VS nauczy się teraz pojęć „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 !

Uwaga Po -[blue, rectangle] G oraz S nie są pokazywane. Dzieje się tak, ponieważ ograniczenia nie zmieniają się po przetworzeniu tego przykaldu.

Częściowe uczenie pojęć

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

Uwaga Po przetworzeniu wszystkich przykładów zbiory G i S nie są zbieżne. W związku z tym otrzymujemy częściowo nauczone pojęcie i brak większej ilości przykładów do tego, aby osiągnąć jedną spójną hipotezę.

Ćwiczenie do domu

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

Uwagi

  • Wzór określający consistent nie był dla wszystkich jasny
  • Trzeba omówić działanie algorytmu Find-S, tłumacząc dokładnie co to jest hipoteza i jakie wartości mogą przyjmować jej parametry (co oznacza more general value)
  • Nie wystarcza czasu żeby zrobić część z Prologu
pl/dydaktyka/ml/lab2.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0