|
|
pl:dydaktyka:ml:lab2 [2017/07/17 10:08] |
pl:dydaktyka:ml:lab2 [2019/06/27 15:50] (aktualna) |
| ====== 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 |
| * 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 |
| |
| |