--- pl:dydaktyka:ml:lab2 [2013/03/07 09:22]
esimon [Uwagi]
+++ pl:dydaktyka:ml:lab2 [2017/07/17 10:08]
@@ Linia 1: / Linia 1: @@
-====== 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,2,1,1,1;
-,2,2,1,1,2;
-,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

pl/dydaktyka/ml/lab2.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

Różnice