|
|
pl:dydaktyka:ml:lab2 [2013/03/07 09:22] esimon [Uwagi] |
pl:dydaktyka:ml:lab2 [2017/07/17 10:08] |
====== Laboratorium 2 - Concept Learning ====== | |
Literatura: Tom M. Mitchell, //Machine Learning//, [[http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/mlbook/ch2.pdf|Rozdział 2]]. | |
| |
Pliki do pobrania: {{:pl:dydaktyka:ml:concept-learning.zip|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: | |
^Sky^AirTemp^Humidity^Wind^Water^Forecast^Enjoy^ | |
|Sunny|Warm|Normal|Strong|Warm|Same|Yes| | |
|Sunny|Warm|High|Strong|Warm|Same|Yes| | |
|Rainy|Cold|High|Strong|Warm|Change|No| | |
|Sunny|Warm|High|Strong|Cool|Change|Yes| | |
| |
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: | |
<code octave> | |
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']; | |
</code> | |
| |
Analogicznie, zbiór danych treningowych będzie zatem wyglądał tak: | |
<code octave> | |
%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]; | |
</code> | |
| |
**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: | |
<code octave>h = [Inf,2,2,Inf,Inf,Inf]</code> | |
| |
| |
| |
| |
===== Find-S ===== | |
| |
Zaimplementuj algorytm Find-S, w pliku //findS.m//. Algorytm wygląda następująco: | |
- Initialize $h$ to the most specific hypothesis in $H$ | |
- For each positive training instance $x$ | |
- For each attribute constraint $a_i$ in $h$ | |
- If the constraint $a_i$ is satisfied by $x$, then do nothing | |
- Else replace $a_i$ in $h$ by the next more general constraint that is satisfied by $x$ | |
- 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: | |
- List all possible hypotheses based on attribute domains and assign it to $H$ | |
- Remove from $H$ all hypotheses that are not consistant with $D$, where $D$ is a training set | |
- 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 ==== | |
| |
<code prolog> | |
?- ['vs']. | |
?- ['taxonomy']. | |
</code> | |
| |
**Uwaga** Każde polecenie (łącznie z wprowadzonymi danymi) musi być zakończone znakiem kropki! "p" oznacza pozytywny przykład, "n" oznacza negatywny. | |
| |
| |
<code prolog> | |
?- 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] | |
</code> | |
| |
==== Używanie VS w trybie wsadowym (przykłady są dostarczone w pliku)==== | |
| |
| |
<code prolog> | |
?- ['shapes']. | |
</code> | |
| |
**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. | |
| |
<code prolog> | |
?- 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] | |
</code> | |
| |
**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: | |
- 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 | |
- 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. | |
| |
<code 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, ?, ?, ?] | |
</code> | |
| |
| |
**Uwaga** =[yes, car, f, yes] nie jest ostatnim przykładem w pliku //lonedata.pl// | |
| |
| |
| |
==== Niespójny zbiór danych (Wersja interaktywna)) ==== | |
| |
<code prolog> | |
?- 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 ! | |
</code> | |
| |
| |
**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". | |
| |
| |
<code 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 ! | |
</code> | |
| |
**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ęć ==== | |
| |
| |
<code 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. | |
</code> | |
| |
| |
**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): | |
| |
{{:pl:dydaktyka:ml:cea.png|}} | |
| |
Spróbuj zaimplementować algorytm //Candidate-Elimination// w Octave, bazując na instrukcjach: [[http://ai.ia.agh.edu.pl/wiki/_media/pl:prolog:prolog_lab:ml:zmv-ml-ch4.pdf|Instrukcje]] | |
| |
===== Uwagi ===== | |
* Wzór określający //consistent// nie był dla wszystkich jasny | |
| |
| |