====== LAB: Reprezentacja niepewności ====== Celem ćwiczeń jest zapoznanie się z budową i możliwościami naiwnego klasyfikatora bayesowskiego oraz sieci bayesowskich, które są jednymi ze sposobów reprezentacji niepewności w systemach inteligentnych. Laboratorium zostało przygotowane w oparciu o materiały z kursów: [[https://www.cs.waikato.ac.nz/ml/weka/courses.html|Data Mining with Weka]], [[https://www.cs.waikato.ac.nz/ml/weka/courses.html|More Data Mining with Weka]] i [[http://web.cecs.pdx.edu/~mm/MachineLearningWinter2019/|CS 445/545 @Portland State University]] oraz w oparciu o materiały udostępniane z podręcznikiem [[http://artint.info/|Artificial Intelligence: Foundations of Computational Agents]]. ===== - Do przygotowania ===== * **[ArtInt]** Sekcje 8.1-8.3 z rozdziału [[https://artint.info/2e/html/ArtInt2e.Ch8.html|Reasoning with Uncertainty]] * **[ArtInt]** [[https://artint.info/2e/html/ArtInt2e.Ch10.S1.SS2.html|Sekcja 10.1.2: Naive Bayes Classifier]] * **[ArtInt]** [[https://artint.info/2e/html/ArtInt2e.Ch10.S4.html|Sekcja 10.4: Bayesian Learning]] * **[AIMA]** Chapter 13: Quantifying Uncertainty * **[AIMA]** Section 14.1: Representing Knowledge in an Uncertain Domain ===== - Wprowadzenie [15 minut] ===== Czy znasz odpowiedzi na poniższe **pytania**? - Co to znaczy, że dwa zdarzenia losowe są niezależne? - Jak wygląda twierdzenie Bayesa? - Czy twierdzenie Bayesa może się przydać "w życiu"? Podaj jakiś przykład. ==== Prawdopodobieństwo warunkowe ==== Na początek mała praktyczna powtórka z prawdopodobieństwa warunkowego. Rozwiąż **jedno** z dwóch zadań: - Załóżmy, że w Twojej skrzynce mailingowej pojawiła się nowa wiadomość, która ma temat "Cześć". Masz statystyki wszystkich swoich maili i wiesz, że: (a) 10% wszystkich wiadomości jest spamem, (b) 50% spamu ma temat "Cześć", %%(c)%% tylko 2% nie-spamu ma temat "Cześć". Jakie jest prawdopodobieństwo, że ta wiadomość jest spamem? - Szacuje się, że 0,05% populacji USA ma HIV. Istnieje test na HIV: (a) jeśli badany ma HIV, test ma 98% szansy na pozytywny wynik; (b) jeżeli osoba nie ma HIV, test ma 3% szansy na pozytywny wynik. Tomek ma wynik pozytywny. Jakie jest prawdopodobieństwo, że ma HIV? [[https://xkcd.com/1236/|{{https://imgs.xkcd.com/comics/seashell.png?200}}]] [[https://xkcd.com/2059/|{{https://imgs.xkcd.com/comics/modified_bayes_theorem.png?300}}]] ===== - Naive Bayes ===== Czy znajomość Twierdzenia Bayesa i prawdopodobieństwa warunkowego może nas w jakiś sposób przybliżyć do rozwiązania problemu klasyfikacji? Tak!((Gdyby nas to nie przybliżało to prawdopodobieństwo warunkowe nie pojawiłoby się w tej instrukcji ;) )) Przyjmijmy dodatkowe założenia: - wszystkie atrybuty są jednakowo istotne a priori, - wszystkie atrybuty są statystycznie niezależne (biorąc pod uwagę atrybut class, który określamy): znając wartość jednego atrybutu, nie jesteśmy w stanie nic powiedzieć o drugim atrybucie. Założenie to nigdy nie jest prawdziwe, ale o dziwo dobrze działa w praktyce. Możemy na tej podstawie zbudować algorytm Naive Bayes:\\ $\mathrm{naiveBayes}(a_1,\dots,a_n) = \mathop{\mathrm{argmax}}_c \ p(C=c) \prod_{i=1}^n p(A_i=a_i\vert C=c)$, \\ gdzie $A_i$ to atrybuty, $C$ to atrybut class. Jak to działa? - Mamy dostępne $m$ przykładów w zbiorze uczącym, każdy opisany jest poprzez $n$ atrybutów i ma przypisaną klasę $c$.\\ Mamy przykład, który chcemy sklasyfikować opisany przez $n$ atrybutów. - Dla każdej wartości klasy $c$, dla każdego atrybutu $a_n$ obliczamy prawdopodobieństwo wystąpienia danej wartości atrybutu (z przykładu do sklasyfikowania) pod warunkiem założenia danej klasy $c$: \\ $p(A_i=a_i\vert C=c)$ \\ (na podstawie zbioru uczącego). - Obliczamy prawdopodobieństwo wystąpienia danego zestawu wartości atrybutów pod warunkiem założenia danej klasy $c$: \\ $\prod_{i=1}^n p(A_i=a_i\vert C=c)$. - Potrzebujemy tak naprawdę prawdopodobieństwo, że dany obiekt jest klasy $c$ pod warunkiem, że mamy dany zestaw wartości atrybutów, czyli $p(C=c\vert A_i=a_i)$, a mamy prawdopodobieństwo $p(A_i=a_i\vert C=c)$ -- jak zmienić jedno w drugie? Zgodnie z twierdzeniem Bayesa, musimy wymnożyć przez $p(C=c)$: \\ $p(C=c) \prod_{i=1}^n p(A_i=a_i\vert C=c)$. - Powtarzamy to dla każdej klasy i wybieramy tę, dla której prawdopodobieństwo jest największe: \\ $\mathop{\mathrm{argmax}}_c \ p(C=c) \prod_{i=1}^n p(A_i=a_i\vert C=c)$. Spróbujmy teraz to przećwiczyć na prostym przykładzie... ==== Rozgrzewka [10 minut] ==== Rozważmy taki prosty zbiór treningowy, w którym każdy przykład ma cztery binarne atrybuty i przydzieloną jedną z dwóch klas (+/-): ^ Przykład ^ Atrybut_1 ^ Atrybut_2 ^ Atrybut_3 ^ Atrybut_4 ^ Klasa ^ | x1 | 1 | 1 | 1 | 1 | + | | x2 | 1 | 1 | 0 | 1 | + | | x3 | 0 | 1 | 1 | 0 | + | | x4 | 1 | 0 | 0 | 1 | + | | x5 | 1 | 0 | 0 | 0 | + | | x6 | 1 | 0 | 1 | 0 | - | | x7 | 0 | 1 | 0 | 0 | - | | x8 | 0 | 0 | 1 | 0 | - | W jaki sposób naiwny klasyfikator Bayesowski, wyuczony na powyższym zbiorze treningowym, zaklasyfikuje poniższy przykład? Policz ręcznie :) ^ Przykład ^ Atrybut_1 ^ Atrybut_2 ^ Atrybut_3 ^ Atrybut_4 ^ Klasa ^ | x9 | 1 | 1 | 0 | 0 | ? | ==== Weka [20 minut] ==== Sprawdźmy jak to działa w Wece wykonując następujące **zadania**: - Włącz Wekę i wczytaj plik ''weather.numeric.arff'' ze znanego Ci już zbioru danych: {{:pl:dydaktyka:psi:data.tar.gz|}} - Przejrzyj ten zbiór danych i przypomnij sobie czego on dotyczy. - Przejdź na zakładkę **Classify**. Weka udostępnia dwie wersje Naive Bayes. Zapoznaj się z ich opisami: * NaiveBayes * NaiveBayesUpdateable - Przetestuj obydwie wersje algorytmu? Jakie są różnice? - Następnie przetestuj te same algorytmy na pliku ''weather.nominal.arff''. Jakie różnice występują teraz? Co jest przyczyną występowania różnic - odpowiedz korzystając z opisów algorytmów. Co gdybyśmy chcieli klasyfikować tekst za pomocą Naive Bayesa? Możemy wziąć atrybuty $A_i$ oznaczające ilość wystąpień słowa $i$, ale... * wystąpienie słowa będzie tak samo istotne jak jego niewystąpienie, * wszystkie słowa (częste i rzadkie) zostaną potraktowane tak samo. Rozwiązaniem jest **__Multinomial Naive Bayes__**: * bazuje tylko na występowaniu słów; pomija słowa, które nie występują, * w różny sposób traktuje słowa częste od rzadkich, * jest szybszy od zwykłego Naive Bayesa, ze względu na pomijanie słów, które nie występują. Sprawdźmy jak to działa wykonując kolejne **zadania**: - Wczytaj w Wece plik ''ReutersGrain-train.arff'' i zapoznaj się z jego budową. Jakie są atrybuty? Jakie przyjmują wartości? - Przejdź do zakładki **Classify**, z gałęzi ''meta'' wybierz **FilteredClassifier**: - W ustawieniach wybierz classifier **NaiveBayes** oraz filter **StringToWordVector**. - W polu ''Test options'' wybierz **Supplied test set** i wskaż plik ''ReutersGrain-test.arff''. - Uruchom klasyfikację wciskając **Start**. Zapoznaj się z otrzymanymi wynikami. - Wykonaj klasyfikację w analogiczny sposób korzystając z **NaiveBayesMultinomial** oraz algorytmu tworzenia drzewa decyzyjnego **J48**. Porównaj wyniki. - Zapoznaj się z opisem filtru **StringToWordVector**. Jak myślisz, które jego opcje mogłyby poprawić klasyfikację? Zwróć uwagę np. na opcje outputWordCounts, lowerCaseTokens, useStoplist. Przetestuj działanie wybranych opcji pojedynczo i w grupach korzystając z algorytmu **NaiveBayesMultinomial**. Jak wpłynęły na jego skuteczność? ===== - Sieci Bayesowskie ===== W poprzedniej sekcji poznaliśmy naiwny klasyfikator Bayesowski. Bazuje on na fałszywych założeniach (wszystkie atrybuty są niezależne), ale o dziwo sprawdza się bardzo dobrze! Możemy z niego wyciągnąć jeszcze więcej, gdy połączymy kilka klasyfikatorów w sieć, w której każdy wierzchołek będzie takim właśnie klasyfikatorem - otrzymamy wtedy byt, który nazwiemy siecią Bayesowską. Jak to wygląda w praktyce? ==== Proste sieci bayesowskie [20 minut] ==== W tej części laboratorium skorzystamy z narzędzia SAMIAM, które można pobrać ze strony [[http://reasoning.cs.ucla.edu/samiam/index.php|UCLA]] (podczas pobierania można podać dowolne dane, nie muszą być prawdziwe, nie wysyłają żadnych maili rejestrujących :) ). W przypadku, gdyby domyślna wersja nie działała, proszę pobrać wersję "Classic". Podczas konstruowania sieci, będziemy wykorzystywać **Edit Mode** aby dodać krawędzie do sieci. Aby włączyć **Edit Mode**, wejdź do **Menu->Edit Mode**. Jeśli opcja jest szara, oznacza że program już znajduje się w tym trybie. Aby dodać krawędź do sieci, idź do **Edit->Add Edge**, a następnie: * kliknij na dowolny węzeł, który ma być rodzicem * kliknij na węzeł, który ma być dzieckiem Podczas modyfikowania sieci, pamiętaj żeby nie zmieniać żadnych innych ustawień poza rozkładem prawdopodobieństwa dla danych w węzłach. Aby zmienić prawdopodobieństwa kliknij w zakładkę **Probabilities**. Pamiętaj aby wyedytować prawdopodobieństwa za każdym razem kiedy dodane zostanie nowe dziecko do węzła. UWAGA: Wartość prawdopodobieństwa należy wpisać z **kropką** jako separatorem dziesiętnym, a nie przecinkiem! W dalszej części będziemy korzystać z **Query Mode**, żeby zobaczyć jak wyglądają prawdopodobieństwa dla poszczególnych przypadków. W celu zmiany trybu na **Query Mode** idź do **Mode->Query Mode**. Żeby podejrzeć prawdopodobieństwa, idź do **Query->Show monitors->Show All**. === Mukowiscydoza === Za ryzyko zachorowania na mukowiscydozę odpowiedzialnych jest pewien gen. Dla uproszczenia założymy, że składa się on jedynie z dwóch alleli, które mogą przyjmować wartości **f** lub **F**. Allel **F** zwiększa ryzyko zachorowania, które można opisać następująco: * osoby z genotypem FF mają 80% szans na zachorowanie * osoby z genotypem Ff mają 60% szans na zachorowanie * osoby z genotypem ff mają 10% szans na zachorowanie Uruchom program SAMIAM i wczytaj plik **{{.:cysticfibrosisbayesnet.zip|cysticFibrosisBayesNet.net}}** Przejdź w tryb **Query Mode** a następnie włącz wszystkie monitory **Query->Show monitors->Show All**. Zobacz jak zmieniają się prawdopodobieństwa w zależności od tego które ze zmiennych podajemy jako **dane**. W szczególności zaobserwuj co dzieje się dla następujących konfiguracji węzłów (czarne węzły oznaczają węzły z zmienną **daną**). Jak zmienia sie rozkład prawdopodobieństwa, gdy "odkolorujemy" dany węzeł? {{ .:cond-indep-1.png?direct&200|}} {{.:cond-indep-2.png?direct&116 |}} {{ .:cond-indep-3.png?direct&116 |}} ==== Zdolność kredytowa [20 minut] ==== //Zadanie dodatkowe.// Korzystając z narzędzia SamIam zamodeluj sposób wyznaczania przez bank zdolności kredytowej klienta na podstawie następujących danych: * przychód (income) * majątek (assets) * współczynnik przychodu do już posiadanych kredytów/długów (ratio of debts to income) * historię transakcji (payment history) * wiek (age) * wiarygoność klienta (reliability) * przyszły dochód (future income) * współczynnik długów do przyszłego dochodu (ratio of debts to income) Zadanie polega na zbudowaniu sieci Bayesowskiej, która na podstawie danych (pewnych, lub wszystkich) udzieli odpowiedzi na temat zdolności kredytowej klienta. **Plik ze szkieletem sieci: {{.:credit_net.net.zip|pobierz}}.** Przy obliczaniu zdolności kredytowej, następujące zależności brane są pod uwagę: - Im lepsza historia transakcji (payment history) tym bardziej prawdopodobne, ze osoba jest wiarygodna (reliable) - Im starsza osoba, tym bardziej prawdopodobne że będzie bardziej wiarygodna (reliable) - Starsze osoby najczęściej mają świetną historię transakcji (payment history) - Osoby z wysokim stosunkiem długów do przychodu (ratio of debts to income) nie mają zbyt często dobrej historii transakcji (payment history) - Im większy jest przychód (income) danej osoby, tym większe prawdopodobieństwo, ze osoba ma duży majątek (assets) - Im większy majątek (assets) danej osoby i im większy jej przychód (income) tym większe prawdopodobieństwo, ze osoba ta będzie miała wysoki przyszły przychód (future income) - Bardziej wiarygodne osoby (reliable) najczęściej maja większą zdolność kredytową. Podobnie osoby z obiecująco wysokim przyszłym dochodem (future income) jak również osoby z niskim stosunkiem długów do przychodu (ratio of debts to income) mają większą zdolność kredytową niż inni. Aby sprawdzić jak wyglądają prawdopodobieństwa po zbudowaniu sieci, przejdź do **Query Mode** i przetestuj działanie sieci. Upewnij się, że algorytm wnioskujący (inference algorithm) ustawiony jest na **hugin**. ==== Weka ==== Sieci Bayesowskie oczywiście są również zaimplementowane w Wece, jednak nie będziemy się nimi zajmować na tym laboratorium ze względu na brak czasu :) Dla zainteresowanych osób: - Weka posiada własny edytor sieci bayesowskich. Aby się do niego dostać należy w **Weka GUI Chooser** z menu **Tools** wybrać **Bayes net editor**. - {{https://www.cs.waikato.ac.nz/~remco/weka.bn.pdf|Dokument opisujący możliwości sieci bayesowskich w Wece}} ==== Podsumowanie [5 minut] ==== Poznaliśmy dzisiaj dwie nowe metody klasyfikacji: naiwny klasyfikator Bayesowski oraz sieci Bayesowskie. W ramach podsumowania odpowiedz na dwa **pytania**: - Czym różni się klasyfikacja tymi metodami od klasyfikacji na poprzednich dwóch zajęciach? - Zastanów się wspólnie z kolegą lub koleżanką nad zaleceniami dla młodych eksploratorów danych odnośnie wyboru odpowiedniej metody do odpowiedniego zbioru danych / odpowiedniego problemu. Spróbuj przygotować co najmniej kilka reguł, które mogą być pomocne przy wyborze metody.