Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:ml:lab2 [2013/02/20 15:52] esimon [Version Space] |
pl:dydaktyka:ml:lab2 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== Laboratorium 3 - Concept Learning ====== | + | ====== Laboratorium 2 - Concept Learning ====== |
| - | Literatura: Tom M. Mitchell, //Machine Learning//, Rozdział 2. | + | 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 ===== | ===== 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 | * //ex1.m// - skrypt pomagajacy przejśc przez pierwszą część laboratoium | ||
| * :!: //consistent.m// - funkcja sprawdzająca zgodność hipotezy ze zbiorem treningowym | * :!: //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 | + | * //satisfies// - funkcja sprawdzająca czy hipoteza jest prawdziwa dla danego elementu ze zbioru uczącego |
| * :!: //findS.m// - funkcja implementująca algorytm findS | * :!: //findS.m// - funkcja implementująca algorytm findS | ||
| * :!: //listAllHypothesis.m// - funkcja generująca wszystkie możliwe hipotezy dla danego zbioru treningowego | * :!: //listAllHypothesis.m// - funkcja generująca wszystkie możliwe hipotezy dla danego zbioru treningowego | ||
| * :!: //listThenEliminate.m// - funkcja implementująca algorytm List-Then-Eliminate | * :!: //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 | ||
| Linia 69: | Linia 75: | ||
| **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). | **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// \\ | ||
| Linia 80: | Linia 85: | ||
| $$ Consistent(h,D) = (\forall<x,c(x)> \in D) h(x) = c(x)$$ | $$ Consistent(h,D) = (\forall<x,c(x)> \in D) h(x) = c(x)$$ | ||
| + | |||
| + | |||
| + | |||
| ==== Consistent ==== | ==== Consistent ==== | ||
| Zaimplementuj funkcję //consistent// w pliku //consistent.m// | Zaimplementuj funkcję //consistent// w pliku //consistent.m// | ||
| - | Przetestuj jej działanie za pomocą //check.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 ==== | ==== ListAllHypothesis ==== | ||
| Linia 90: | Linia 100: | ||
| Zaimplementuj funkcję //listAllHypothesis// w pliku //listAllHypothesis.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? | **Zastanów się** Jaki rozmiar będzie miała przestrzeń wszystkich hipotez dla naszego przykładu? | ||
| - | ==== LearnThenEliminate ==== | + | ==== ListThenEliminate ==== |
| - | Zaimplementuj w pliku //learnThenEliminate.m// algorytm wyszukujący //version-space// dla naszego zbioru uczącego. | + | Zaimplementuj w pliku //listThenEliminate.m// algorytm wyszukujący //version-space// dla naszego zbioru uczącego. |
| Algorytm można opisać następująco: | Algorytm można opisać następująco: | ||
| Linia 103: | Linia 112: | ||
| - Output the list of hypotheses | - Output the list of hypotheses | ||
| - | Przetestuj jego działanie za pomocą skryptu //ex1.m// oraz //check.m//. | ||
| - | ===== Version Space ===== | + | |
| + | ===== Version Space i Prolog===== | ||
| W Octave programowanie tego typu zagadnień jest nieefektywne i trudne. | W Octave programowanie tego typu zagadnień jest nieefektywne i trudne. | ||
| Znacznie łatwiej poruszać się w problematyce uczenia pojęć używając języka Prolog. | Znacznie łatwiej poruszać się w problematyce uczenia pojęć używając języka Prolog. | ||
| Linia 116: | Linia 125: | ||
| * vs.pl | * vs.pl | ||
| - | Wykonaj polecenia poniżej. | + | Prześledź i przeanalizuj działanie programu opisanego poniżej. |
| - | ==== USING VS IN INTERACTIVE MODE ==== | + | ==== Używanie VS w trybie interaktywnym ==== |
| - | <code> | + | <code prolog> |
| ?- ['vs']. | ?- ['vs']. | ||
| ?- ['taxonomy']. | ?- ['taxonomy']. | ||
| </code> | </code> | ||
| - | NOTE that every input should end with FULL STOP (.). | + | **Uwaga** Każde polecenie (łącznie z wprowadzonymi danymi) musi być zakończone znakiem kropki! "p" oznacza pozytywny przykład, "n" oznacza negatywny. |
| - | "p" stands for positive and "n" for negative. | + | |
| - | <code> | + | |
| + | <code prolog> | ||
| ?- vs. | ?- vs. | ||
| Type the first positive example: | Type the first positive example: | ||
| Linia 159: | Linia 168: | ||
| </code> | </code> | ||
| - | ==== USING VS IN BATCH MODE (EXAMPLES ARE SUPPLIED IN A FILE) ==== | + | ==== Używanie VS w trybie wsadowym (przykłady są dostarczone w pliku)==== |
| - | <code> | + | <code prolog> |
| ?- ['shapes']. | ?- ['shapes']. | ||
| </code> | </code> | ||
| - | 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. | + | **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> | + | <code prolog> |
| ?- batch. | ?- batch. | ||
| +[red, square] | +[red, square] | ||
| Linia 189: | Linia 199: | ||
| </code> | </code> | ||
| - | 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: | + | **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. | ||
| - | - 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. | + | Poniżej przedstawiona została sytuacja pierwsza. |
| - | - 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. | + | <code prolog> |
| - | + | ||
| - | Below is an example of Situation 1. Situation 2 is illustrated in Experiment 4. | + | |
| - | + | ||
| - | <code> | + | |
| ?- ['loandata']. | ?- ['loandata']. | ||
| - | </code> | ||
| - | <code> | ||
| ?- batch. | ?- batch. | ||
| +[yes, comp, f, no] | +[yes, comp, f, no] | ||
| Linia 219: | Linia 225: | ||
| </code> | </code> | ||
| - | NOTE that +[yes, car, f, yes] is not the last example in the file loandata.pl. | ||
| + | **Uwaga** =[yes, car, f, yes] nie jest ostatnim przykładem w pliku //lonedata.pl// | ||
| - | ==== INCONSISTENT HYPOTHESIS SPACE (INTERACTIVE MODE) ==== | ||
| - | <code> | + | |
| + | ==== Niespójny zbiór danych (Wersja interaktywna)) ==== | ||
| + | |||
| + | <code prolog> | ||
| ?- vs. | ?- vs. | ||
| Type the first positive example: | Type the first positive example: | ||
| Linia 250: | Linia 258: | ||
| | [blue,triangle]. | | [blue,triangle]. | ||
| Classification of the example ? [p/n] p. | Classification of the example ? [p/n] p. | ||
| + | There is no consistent concept description in this language ! | ||
| </code> | </code> | ||
| - | There is no consistent concept description in this language ! | ||
| - | NOTE that [blue,triangle] is a positive example outside the | + | **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ęć. |
| - | version space. This example cannot be included in the concept, | + | |
| - | because of the restriction on the concept representation language | + | |
| - | not allowing disjunctive concepts. | + | |
| - | ==== INCONSISTENT HYPOTHESIS SPACE (BATCH MODE) ==== | ||
| - | Move example 3 (neg) in the beginning of shapes.pl and then load it. | + | ==== Niespójne hipotezy (Wersja wsadowa) ==== |
| - | That is, VS now learns the concept of "neg". | + | |
| - | <code> | + | 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']. | ?- ['shapes']. | ||
| Linia 283: | Linia 290: | ||
| </code> | </code> | ||
| - | NOTE that after -[blue, rectangle] the G and S sets are not shown. | + | **Uwaga** Po -[blue, rectangle] G oraz S nie są pokazywane. |
| - | This happens when the boundaries of the version space do not change | + | Dzieje się tak, ponieważ ograniczenia nie zmieniają się po przetworzeniu tego przykaldu. |
| - | after the current example. | + | |
| - | ==== PARTIALLY LEARNT CONCEPT ==== | + | ==== Częściowe uczenie pojęć ==== |
| - | <code> | + | <code prolog> |
| ?- ['animals']. | ?- ['animals']. | ||
| Linia 319: | Linia 327: | ||
| No more examples. | No more examples. | ||
| </code> | </code> | ||
| - | 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. | + | **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ę. |
| Linia 331: | Linia 340: | ||
| 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): | 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:prv:cea.png|}} | + | {{: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]] | 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 | ||
| + | |||
| + | |||
