Katedra

Podstaw

Konstrukcji

Maszyn

Wydział

Mechaniczny

Technologiczny

Politechnika

Śląska

ul. Konarskiego 18a

44-100 Gliwice

tel. [phone]
fax [phone]

http://kpkm.polsl.pl

Metody Sztucznej
Inteligencji

Instrukcja do ćwiczeń laboratoryjnych

Ćwiczenie 3

Temat

Sieci przekonań

Opracował: dr inż. M. Bednarski

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się z zagadnieniami modelowania z zastosowaniem sieci bay-

esowskich i nabycie praktycznych umiejętności definiowania i stosowania tych sieci. W ramach

ćwiczeń stosowane będzie oprogramowanie NETICA, którego wersja demonstracyjna (wystar-

czająca do przeprowadzenia ćwiczenia) jest dostępna poprzez witrynę http://www.norsys.com/

wybierając ”Downloads” i ”Netica”.

2. Wprowadzenie

2.1. Sieć bayesowska

Sieć bayesowska to acykliczny (nie zawierający cykli) graf skierowany w którym węzły reprezen-

tują zmienne (np. temperaturę jakiegoś źródła, stan pacjenta, cechę obiektu itp.) a skierowane

gałęzie informacyjną lub przyczynową zależność pomiędzy tymi zmiennymi. Zależność ta jest

określona przez warunkowe prawdopodobieństwo, które jest przypisane do każdego połączenia

pomiędzy węzłami w sieci. Zmienne reprezentowane przez węzły przyjmują wartości dyskretne

(np.: TAK, NIE). Rysunek 1 przedstawia prostą sieć bayesowską. Opisuje ona relacje przy-

czynowe pomiędzy wystąpieniem zachmurzenia i zraszaniem trawy, pomiędzy wystąpieniem

zachmurzenia a wystąpieniem deszczu i pomiędzy zraszaniem trawy, i wystąpieniem deszczu

a mokrą trawą. Obok każdego węzła przedstawiono tablicę prawdopodobieństw warunkowych

np. dla węzła

D prawdopodobieństwo, że działał zraszacz (B = T ak), nie padał deszcz

(

C = Nie) i trawa jest mokra (D = T ak) jest równe 0, 9 (drugi wiersz).

2.2. Konstruowanie sieci bayesowskiej

Aby wnioskować na podstawie danych należy najpierw zbudować sieć bayesowską. Generalnie

utworzenie takiej sieci wymaga pomocy eksperta z dziedziny, której dotyczy tworzony model,

w celu określenia właściwych zależności przyczynowych i prawdopodobieństw warunkowych.

W tym celu możliwe jest również zastosowanie technik uczenia. Większość oprogramowania

komputerowego dotyczącego budowania sieci bayesowskich pozwala na podstawie danych tre-

nujących wyznaczyć odpowiednie parametry sieci (warunkowe rozkłady prawdopodobieństwa).

Istnieją również bardziej złożone programy komputerowe pozwalające wyznaczyć związki przy-

czynowe pomiędzy zmiennymi (strukturę sieci). Kolejne kroki tworzenia sieci bayesowskiej (bez

użycia danych trenujących) i jej stosowanie:

• zdefiniowanie zmiennych,
• zdefiniowanie połączeń pomiędzy zmiennymi,
• określenie prawdopodobieństw warunkowych i ”a priori”

1

,

1

”a priori” - (z łaciny - z założenia) - niezależne od doświadczenia, zdobyte na podstawie rozumowania,

intuicję itp.

MGM2002PN15-002

Gliwice 2006-05-04

- 2/15 -

Rys. 1: Przykładowa sieć bayesowska, zmodyfikowany przykład pokazany w [5]

• wprowadzenie do sieci danych,
• uaktualnienie sieci,
• wyznaczenie prawdopodobieństw ”a posteriori”

2

.

2.3. Przykład wnioskowania za pomocą sieci

Siec przedstawioną na rys.1 będziemy rozpatrywać dla trzech sytuacji :

1. nie wiemy nic tzn. nie wiemy czy wystąpiło zachmurzenie, czy padał deszcz, czy działał

zraszacz i czy trawa jest mokra,

2. wiemy, że trawa jest mokra,

3. wiemy, że występuje zachmurzenie oraz trawa jest mokra.

Rysunki 2,3,4 przedstawiają odpowiednio rozkłady prawdopodobieństw (określone w procen-

tach) w każdym węźle.

Z porównania rysunku 3 i 2 wynika, że wiadomość o tym iż trawa jest mokra pozwala

zwiększyć nasze przekonanie o tym, że padał deszcz (z 50% do 70%) oraz o tym, że działał

zraszacz (z 30% do 43%).

Z porównania rysunków 4 i 3 wynika, że dodatkowa wiadomość o tym iż występuje za-

chmurzenie pozwala zwiększyć przekonanie, że padał deszcz (z 70% do 97,6%) oraz znacznie

zmniejszyć przekonanie o tym, że działał zraszacz (z 42% do 13%). Gdybyśmy ponadto w

2

”a posteriori” (z łaciny - z następstwa) - uzyskane na podstawie doświadczenia

MGM2002PN15-002

Gliwice 2006-05-04

- 3/15 -

Rys. 2: Rozkłady prawdopodobieństwa dla sytuacji 1 (”nie wiemy nic”).

Rys. 3: Rozkłady prawdopodobieństwa dla sytuacji 2 (”wiemy, że trawa jest mokra”).

Rys. 4: Rozkłady prawdopodobieństwa dla sytuacji 3 (”wiemy, że występuje zachmurzenie i
trawa jest mokra”).

MGM2002PN15-002

Gliwice 2006-05-04

- 4/15 -

kolejnym kroku stwierdzili, że zraszacz nie działa to nasze przekonanie o tym, że padał deszcz

wzrasta do 100%.

2.4. Zastosowanie programu NETICA do tworzenia sieci bayesowskiej

2.4.1. Stosowanie sieci

Omawiany wyżej przykład, zapisany w programie NETICA przedstawiono na rysunku 5. Obli-

czone prawdopodobieństwa pokazano graficznie. Wskazując prawym klawiszem myszy odpo-

wiedni węzeł uzyskuje się dostęp do menu kontekstowego węzła, w którym możemy nadać

węzłowi wartość (w przypadku, gdy jest ona znana np. TAK lub NIE). Domyślnie przyjmowana

jest wartość Unknown, oznaczająca nieznaną wartość danego węzła Przypisanie wartości wę-

złowi powoduje zmiany rozkładów prawdopodobieństw pozostałych węzłów, których wartości

nie zostały ustalone.

Rys. 5: Okno główne programu NETICA).

2.4.2. Zapisywanie sieci

Zapisywanie modelu należy rozpocząć od wstawienia węzłów poleceniem Add Nature Node

(menu górne-Modify lub ikona

). Po stworzeniu węzła i nadaniu mu odpowiedniej nazwy

(nie wolno używać polskich znaków diakrytycznych oraz spacji, w tytule węzła można używać

spacji) należy określić możliwe wartości (stany) węzła (lub pozostawić domyślne stany True i

False) w oknie (rys.6), które otwiera się podwójnym kliknięciem na węźle.

Aby wprowadzić gałąź łączącą dwa węzły (wprowadzić relację przyczynową) należy:

1. z menu górnego Modify wybrać polecenie Add Link lub wybrać ikonę

,

MGM2002PN15-002

Gliwice 2006-05-04

- 5/15 -

Rys. 6: Okno właściwości węzła).

2. połączyć węzły w odpowiedniej kolejności.

Połączenie można usunąć poprzez zaznaczenie połączenia i wybrania z menu górnego Edit

polecenia Delete (lub naciśniecie klawisza Delete).

W kolejnym kroku należy określić tablice prawdopodobieństw warunkowych. W tym celu należy,

w oknie otwartym przez podwójne kliknięcie na danym węźle nacisnąć przycisk Table. Pojawia

się wówczas okno umożliwiające przypisanie węzłowi tablicy prawdopodobieństw warunkowych

(rys.7). Prawdopodobieństwa warunkowe wprowadzamy w procentach. Ich suma musi być

równa 100 w każdym wierszu tablicy.

Ostatnim krokiem jest skompilowanie sieci. W tym celu należy wybrać z górnego menu Network

polecenie Compile lub kliknąć na ikonę

.

2.5. Twierdzenie Bayesa

Prawdopodobieństwa warunkowe służą do wyrażania zależności między zdarzeniami. Prawdo-

podobieństwo zajścia zdarzenia

A wtedy gdy zaszło zdarzenie B, definiuje się dla dowolnych

zdarzeń

A, B ⊆ Σ (gdzie Σ - zbiór zdarzeń elementarnych), przy założeniu, że P (B) > 0,

jako prawdopodobieństwo warunkowe

P (A|B) =

P (A, B)

P (B)

(1)

gdzie

P (A, B) oznacza prawdopodobieństwo łącznego zajścia zdarzeń A i B.

MGM2002PN15-002

Gliwice 2006-05-04

- 6/15 -

Rys. 7: Okno tablicy prawdopodobieństw warunkowych).

Z prawdopodobieństwem warunkowym wiąże się wzór Bayesa:

P (A|B) =

P (B|A) · P (A)

P (B)

(2)

2.5.1. Obliczanie prawdopodobieństw ”a posteriori”

W sieci bayesowskiej węzły reprezentują zmienne i przyjmują wartości dyskretne - stany. Dla

zmiennej

A, której wartości dyskretne (stany) przyjmują wartości a

1

, . . . , a

n

, rozkład prawdo-

podobieństwa wartości dyskretnych stanów jest oznaczany jako

P (A):

P (A) = (x

1

, . . . , x

n

)

x

i

 0

n

i=1

x

i

= 1,

(3)

gdzie:

x

i

jest prawdopodobieństwem tego, że

A przyjmuje wartość a

i

i jest oznaczane

P (A = a

i

).

Dla zmiennej

B przyjmującej wartości b

1

, . . . , a

m

,

P (A|B) jest n × m tablicą zawierającą

prawdopodobieństwa warunkowe

P (a

i

|b

j

)

Łączne prawdopodobieństwo

P (A, B) jest również tablicą n×m wymiarową i zawiera prawdo-

podobieństwa każdej konfiguracji

(a

i

, b

j

). W celu wyznaczenia łącznego prawdopodobieństwa

należy skorzystać ze wzoru (na podstawie wzoru 1):

MGM2002PN15-002

Gliwice 2006-05-04

- 7/15 -

P (a

i

, b

j

) = P (b

i

|a

j

) · P (a

j

)

(4)

Ogólna postać wzoru:

P (A, B) = P (B|A) · P (A)

(5)

Na podstawie łącznego prawdopodobieństwa

P (A, B) można wyznaczyć prawdopodobień-

stwo

P (B) wg wzoru 6. Zabieg ten nazywany jest marginalizacją zmiennej A.

P (b

j

) =

n

i=1

P (a

i

, b

j

)

(6)

Ogólna postać wzoru:

P (B) =

A

P (A, B)

(7)

Przykład 1:

Obliczyć prawdopodobieństwo

P (B) dla przypadku przedstawionego na rys.8 [2].

Rys. 8: Przykład 1

Rozwiązanie: Najpierw należy policzyć łączne prawdopodobieństwo

P (A, B) wg wzoru 5

(Tabela 1), a następnie dokonać marginalizacji zmiennej

A wg wzoru 7 (Tabela 2).

MGM2002PN15-002

Gliwice 2006-05-04

- 8/15 -

Tab. 1: Prawdopodobieństwo łączne

P (A, B)

b

1

b

2

b

3

a

1

0, 2 · 0, 4 = 0, 08

0, 3 · 0, 4 = 0, 12

0, 5 · 0, 4 = 0, 2

a

2

0, 6 · 0, 6 = 0, 36

0, 25 · 0, 6 = 0, 15

0, 15 · 0, 6 = 0, 09

Tab. 2: Prawdopodobieństwo

P (B)

b

1

b

2

b

3

a

1

0, 08

0, 12

0, 2

a

2

0, 36

0, 15

0, 09

P (B)

0, 08 + 0, 36 = 0, 44

0, 12 + 0, 15 = 0, 27

0, 2 + 0, 09 = 0, 29

Przykład 2: Obliczyć prawdopodobieństwo

P (W ) i P (H) dla przypadku przedstawionego na

rys. 9 oraz

P (H) dla przypadku, w którym węzeł W jest ustalony (rys. 10) [2].

Rys. 9: Przykład 2a

Rozwiązanie (przykład 2a): Aby obliczyć prawdopodobieństwo

P (W ) i P (H) należy naj-

pierw obliczyć łączne prawdopodobieństw

P (W, I) (tabela 3) i P (H, I) (tabela 4), a następnie

dokonać marginalizacji zmiennej

I (tabele 5 i 6).

MGM2002PN15-002

Gliwice 2006-05-04

- 9/15 -

Rys. 10: Przykład 2b

Tab. 3: Prawdopodobieństwo łączne

P (W, I)

W=y

W=n

I=t

0, 8 · 0, 7 = 0, 56

0, 7 · 0, 2 = 0, 14

I=n

0, 1 · 0, 3 = 0, 03

0, 9 · 0, 3 = 0, 27

Tab. 4: Prawdopodobieństwo łączne

P (H, I)

H=y

H=n

I=t

0, 8 · 0, 7 = 0, 56

0, 7 · 0, 2 = 0, 14

I=n

0, 1 · 0, 3 = 0, 03

0, 9 · 0, 3 = 0, 27

Tab. 5: Prawdopodobieństwo

P (W )

W = y

W = n

I = t

0, 56

0, 14

I = n

0, 03

0, 27

P (W )

0, 59

0, 41

MGM2002PN15-002

Gliwice 2006-05-04

- 10/15 -

Tab. 6: Prawdopodobieństwo

P (H)

W = y

W = n

I = t

0, 56

0, 14

I = n

0, 03

0, 27

P (W )

0, 56 + 0, 03 = 0, 59

0, 14 + 0, 27 = 0, 41

Rozwiązanie (przykład 2b): Aby obliczyć prawdopodobieństwo

P (H) należy najpierw ob-

liczyć łączne prawdopodobieństw

P (H, I) wg wzoru 8, a następnie dokonać marginalizacji

zmiennej

I. Aby obliczyć prawdopodobieństwo łączne P (H, I) (tabela 8) należy najpierw wy-

znaczyć prawdopodobieństwo warunkowe

P (I|W = y) (tabela 7) wykorzystując twierdzenie

Bayesa (wzór 9).

P (H, I) = P (H|I) · P (I|W = y)

(8)

P (I|W = y) =

P (W = y|I) · P (I)

P (W = y)

(9)

Tab. 7: Prawdopodobieństwo

P (I|W = y)

W = y

I = t

0,8·0,7

0,59

= 0, 95

I = n

0,1·0,3

0,59

= 0, 05

Tab. 8: Prawdopodobieństwo

P (H, I) i P (H)

H = y

H = n

I = t

0, 8 · 0, 95 = 0, 76

0, 2 · 0, 95 = 0, 19

I = n

0, 1 · 0, 05 = 0, 005

0, 9 · 0, 05 = 0, 045

P (H)

0, 76 + 0, 005 = 0, 765

0, 19 + 0, 045 = 0, 235

2.6. Warunkowa niezależność węzłów sieci bayesa

Rozważając sytuację przedstawioną na rysunku 11, gdzie nieznana jest wartość a priori węzła
C (Padał deszcz - unknown), możemy zauważyć, że węzły D (Trawa jest mokra) i E (Dach

MGM2002PN15-002

Gliwice 2006-05-04

- 11/15 -

jest mokry) są warunkowo zależne tzn. zmiana wartości a priori węzła

D wywołuje zmiany

wartości a posteriori węzła

E i odwrotnie.

Rys. 11: Fragment sieci dla przykładu przedstawionego na rys.1. Zmiana wartości a priori węzła

D (Trawa jest mokra) wywołuje zmiany wartości a posteriori węzła E (Dach jest mokry).

Natomiast dla sytuacji gdzie wartość a priori węzła

C jest znana (rys.12) węzeł D i E są

warunkowo niezależne tzn. zmiana wartości a priori węzła

D nie wywołuje zmiany wartości a

posteriori węzła

E i odwrotnie.

Rys. 12: Fragment sieci dla przykładu przedstawionego na rys.1. Zmiana wartości a priori węzła

D (Trawa jest mokra) nie wywołuje zmiany wartości a posteriori węzła E (Dach jest mokry)

Dwa (zbiory) węzły

Q i R są warunkowo niezależne jeżeli nie istnieje ani jedna ścieżka

bezpośrednio łącząca (d-connecting path)

Q i R. Ścieżka pomiędzy Q i R jest bezpośrednio

łączącą (d-connecting) jeśli każdy wewnętrzny węzeł

N ścieżki ma jedną z następujących

własności:

• jest liniowy lub rozchodzący się i nie znana jest jego wartość a priori,
• est zbiegający się i wartość a priori jego albo jednego z jego potomków jest znana.

Przykład 3: Określić węzły warunkowo niezależne od węzła

A dla sieci przedstawionej na

rysunku 14. Węzły

B i M są węzłami ustalonymi tzn. wartości a priori tych węzłów są znane

(węzły ciemniejsze) [2].

Rozwiązanie: Ścieżka bezpośrednio łącząca poszczególne węzły -

A − D − H − K − I − E −

C − F − J − L. Węzły należące do tej ścieżki są warunkowo zależne. Węzeł G nie należy do
tej ścieżki i nie istnieje żadna inna bezpośrednio łącząca ścieżka. Z tego wynika, że węzeł

G i

A są warunkowo niezależne.

MGM2002PN15-002

Gliwice 2006-05-04

- 12/15 -

Rys. 13: Rodzaje węzłów wewnętrznych: a)liniowy, b)zbiegający się, c)rozchodzący się.

Rys. 14: Przykład3

3. Zadania do samodzielnego wykonania

Zadania zamieszczone w tym punkcie zaczerpnięto lub opracowano na podstawie [2], [3].

Zadanie 1:

Oblicz prawdopodobieństwa

P (A), P (B), P (A|B), P (B|A) korzystając z prawdopodobień-

stwa łącznego

P (A, B) przedstawionego w tabeli 9.

Tab. 9: Prawdopodobieństwo

P (A, B)

b

1

b

2

b

3

a

1

0,05

0,10

0,05

a

2

0,15

0

0,25

a

3

0,10

0,20

0,10

MGM2002PN15-002

Gliwice 2006-05-04

- 13/15 -

Zadanie 2:

Oblicz prawdopodobieństwo

P (B) dla przypadku pokazanego na rys.15.

Rys. 15: Sieć bayesowska do zadania 2

Zadanie 3:

Określ węzły warunkowo niezależne od węzła

A dla sieci pokazanych na rysunku 16

Rys. 16: Sieci bayesowskie do zadania 3

Zadanie 4:

1. Uruchomić program NETICA.

2. Otworzyć nowy plik.

MGM2002PN15-002

Gliwice 2006-05-04

- 14/15 -

3. Zapisać sieć taką jak na rys.1.

4. Zmienić wartość węzła Występuje zachmurzenie na TAK. Zaobserwować zmiany obli-

czonych prawdopodobieństw.

5. Ustalić wartość węzła Trawa jest mokra na NIE i zaobserwować zmiany wartości praw-

dopodobieństw.

6. Ustalić wartość węzła Występuje zachmurzenie na Unknow, węzła Trawa jest mokra na

TAK i zaobserwować zmiany wartości prawdopodobieństw, zbadać warunkową niezależ-

ność węzłów Działał zraszacz i Padał deszcz.

7. Dla ustalonych wartości węzła Trawa jest mokra (TAK lub NIE) zmieniać wartości węzła

Padał deszcz i obserwować zmiany prawdopodobieństw, zbadać warunkową niezależność

węzłów Działał zraszacz i Padał deszcz.

8. Zmienić wartości prawdopodobieństw warunkowych w węźle Padał deszcz wg schematu:

Występuje zachmurzenie

TAK

NIE

TAK

10

90

NIE

90

10

i zaobserwować zmiany wartości prawdopodobieństw.

Zadanie 5: Zapisać sieć bayesowską dla zadania przygotowanego w domu.

1. opracować sieć w programie NETICA,

2. zbadać przekonania poszczególnych węzłów dla danych wskazanych przez prowadzącego,

3. określić warunkową niezależność węzłów wskazanych przez prowadzącego.

Literatura

[1] Charniak

E.:

Bayesian

Networks

without

Tears.

AI

Magazine,12(4)

1991.

http://www.aaai.org/Magazine/magazine.html

[2] Finn V. Jensen: An Introduction to Bayesian Networks. UCL Press and Springer Verlag,

1996.

[3] Finn V. Jensen: Bayesian Networks and Decision Graphs. Springer-Verlag, 2001.

[4] Murphy K.P: A Brief Introduction to Graphical Models and Bayesian Networks.

http://http.cs.berkeley.edu/ murphyk/Bayes/bayes.html

[5] Russell S., Norvig P.: Artificial Intelligence: A Modern Approach. Prentice Hall, Englewood

Cliffs, NI, 1995.

MGM2002PN15-002

Gliwice 2006-05-04

- 15/15 -