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: Data Mining with Weka, More Data Mining with Weka i CS 445/545 @Portland State University oraz w oparciu o materiały udostępniane z podręcznikiem Artificial Intelligence: Foundations of Computational Agents.

1 Wprowadzenie [15 minut]

Przed rozpoczęciem zadań, proszę wypełnij krótką ankietę dotyczącą wiki o sztucznej inteligencji tworzonej w czasie zajęć: https://goo.gl/forms/pbgkA16ycdJw521z2

Czy znasz odpowiedzi na poniższe pytania?

  1. Co to znaczy, że dwa zdarzenia losowe są niezależne?
  2. Jak wygląda twierdzenie Bayesa?
  3. 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 w postaci dwóch zadań:

  1. 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?
  2. 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?

2 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!1)

Przyjmijmy dodatkowe założenia:

  1. wszystkie atrybuty są jednakowo istotne a priori,
  2. 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?

  1. 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.
  2. 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).
  3. 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)$.
  4. 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)$.
  5. 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:

  1. Włącz Wekę i wczytaj plik weather.numeric.arff ze znanego Ci już zbioru danych: data.tar.gz
  2. Przejrzyj ten zbiór danych i przypomnij sobie czego on dotyczy.
  3. Przejdź na zakładkę Classify. Weka udostępnia trzy wersje Naive Bayes. Zapoznaj się z ich opisami:
    • NaiveBayesSimple
    • NaiveBayes
    • NaiveBayesUpdateable
  4. Przetestuj wszystkie trzy wersje algorytmu? Jakie są różnice?
  5. 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:

  1. Wczytaj w Wece plik ReutersGrain-train.arff i zapoznaj się z jego budową. Jakie są atrybuty? Jakie przyjmują wartości?
  2. Przejdź do zakładki Classify, z gałęzi meta wybierz FilteredClassifier:
    1. W ustawieniach wybierz classifier NaiveBayes oraz filter StringToWordVector.
    2. W polu Test options wybierz Supplied test set i wskaż plik ReutersGrain-test.arff.
    3. Uruchom klasyfikację wciskając Start. Zapoznaj się z otrzymanymi wynikami.
  3. Wykonaj klasyfikację w analogiczny sposób korzystając z NaiveBayesMultinomial oraz algorytmu tworzenia drzewa decyzyjnego J48. Porównaj wyniki.
  4. 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ść?

3 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 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.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ł?

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: pobierz.

Przy obliczaniu zdolności kredytowej, następujące zależności brane są pod uwagę:

  1. Im lepsza historia transakcji (payment history) tym bardziej prawdopodobne, ze osoba jest wiarygodna (reliable)
  2. Im starsza osoba, tym bardziej prawdopodobne że będzie bardziej wiarygodna (reliable)
  3. Starsze osoby najczęściej mają świetną historię transakcji (payment history)
  4. Osoby z wysokim stosunkiem długów do przychodu (ratio of debts to income) nie mają zbyt często dobrej historii transakcji (payment history)
  5. Im większy jest przychód (income) danej osoby, tym większe prawdopodobieństwo, ze osoba ma duży majątek (assets)
  6. 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)
  7. 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:

  1. 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.

Podsumowanie [5 minut]

Poznaliśmy dzisiaj dwie nowe metody klasyfikacji: naiwny klasyfikator Bayesowski oraz sieci Bayesowskie. W ramach podsumowania odpowiedz na dwa pytania:

  1. Czym różni się klasyfikacja tymi metodami od klasyfikacji na poprzednich dwóch zajęciach?
  2. 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.
1)
Gdyby nas to nie przybliżało to prawdopodobieństwo warunkowe nie pojawiłoby się w tej instrukcji ;)
pl/dydaktyka/ai/2017/labs/lab_uncertainty.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0