AI_14_1

14.1. Sieci Bayesa

Sie

Bayesa jest to graf acykliczny skierowany, który

umo

liwia zapis graficzny zale

ci warunkowej zdarze

Sie

Bayesa umo

liwia intuicyjne uj

cie zale

przyczynowych pomi

dzy zmiennymi.

Sieci Bayesa pozwalaj

przedstawi

zwi

ęź

le rozkład ł

czny

prawdopodobie

stwa.

Składnia sieci Bayesa:

– zbiór w

złów, po jednym dla ka

dej zmiennej

losowej (w

zły grafu),

mienna

P(Z

)=0.12

© F.A. Dul 2007

losowej (w

zły grafu),

Rozkład warunkowy jest przedstawiany najcz

ęś

ciej w postaci

tablic prawdopodobie

stwa warunkowego

(conditional proba-

bility table, CPT), które podaj

rozkład prawdopodobie

stwa

warunkowego dla X

dla ka

dej kombinacji warto

ci rodziców.

mienna

– poł

czenia odpowiadaj

ce zale

ciom

pomi

dzy zmiennymi (kraw

dzie grafu),

– rozkład prawdopodobie

stwa warunkowego

dego w

zła przy znanych warto

ciach

rozkładu prawdopodobie

stwa rodziców,

P(X

| Rodzice(X

))

)

0.80
0.20

P(Z

)

0.45
0.06

14.1. Sieci Bayesa

Przykład sieci Bayesa

Sie

Bayesa dla modelu opisuj

cego zale

ci pomi

dzy

bólem z

ba, ubytkiem, wykryciem ubytku oraz pogod

• Zmienne losowe zadania :BólZ

ba, Ubytek, Wykrycie

oraz Pogoda.

Pogoda

Ubytek

© F.A. Dul 2007

BólZ

Wykrycie

Topologia sieci Bayesa pozwala opisa

niezale

ść

absolutn

lub warunkow

zmiennych.

• BólZ

ba i Wykrycie s

niezale

ne warunkowo przy danej

warto

ci zmiennej Ubytek.

• Pogoda jest niezale

na od pozostałych zmiennych

(i vice versa).

14.1. Sieci Bayesa

Bardziej zło

ony przykład sieci Bayesa

• Opis problemu

Jestem w pracy. Dzwoni do mnie s

siad Jan z informacj

e uruchomił si

alarm w moim domu. Druga s

siadka, Maria,

nie dzwoni. Alarm jest czasami wł

czany przez ró

ne wstrz

sy.

Czy to jest włamanie?

• Zmienne losowe (w nawiasach nazwy skrócone):

Włamanie (W), Wstrz

sy (S), Alarm (A),

MariaDzwoni (M), JanDzwoni (J).

© F.A. Dul 2007

MariaDzwoni (M), JanDzwoni (J).

• Wiedza o zadaniu:

– Alarm mo

e uruchomi

włamywacz.

– Alarm mog

uruchomi

wstrz

sy, np. od przelatuj

cego

samolotu.

– Wł

czony alarm mo

e skłoni

Mari

lub Jana do zadzwonienia

do mnie.

• Topologia sieci Bayesa powinna odzwierciedla

powy

wiedz

przyczynow

14.1. Sieci Bayesa

Sie

Bayesa dla problemu włamania

P(S)

0.002

P(W)

0.001

W S

P(A|W,S)

0.95

łamanie

trz

© F.A. Dul 2007

0.95

0.94

0.29

0.01

an Dzwoni

aria Dzwoni

larm

A P(J|A)
T

0.90

0.05

P(M|A)

0.70

0.01

14.1. Sieci Bayesa

Zwarto

ść

reprezentacji za pomoc

sieci Bayesa

• Tablica CPT dla zmiennej losowej boolowskiej X

maj

cej k boolowskich rodziców ma 2

wierszy

dla wszystkich kombinacji warto

ci zmiennych

rodziców.

• Ka

dy wiersz zawiera prawdopodobie

stwo

p dla X

= prawda,

1-p dla X

= fałsz.

• Je

eli jest n zmiennych i ka

da zmienna

© F.A. Dul 2007

• Je

eli jest n zmiennych i ka

da zmienna

ma nie wi

cej ni

k rodziców to cała sie

opisana jest za pomoc

O(n

)

liczb.

• Rozmiar ro

nie wi

c liniowo wzgl

dem n, w przeciwie

stwie

do wzrostu wykładniczego

O(2

)

dla pełnego rozkładu

cznego.

• Dla problemu włamania jest to 1 + 1 + 4 + 2 + 2 = 10 liczb

(w porównaniu z 2

-1 = 31 w przypadku ogólnym).

14.2. Semantyka sieci Bayesa

Rozkład ł

czny prawdopodobie

stwa jest iloczynem

rozkładów w

złowych

Wnioskowanie na podstawie sieci Bayesa jest analogiczne
do wnioskowania z rozkładu ł

cznego.

Przykład

W problemie włamania rozkład prawdopodobie

stwa dla zdarzenia

„Jan dzwoni, Maria dzwoni, alarm działa, nie ma włamania i nie ma

∏

Rodzice

)

(

)

,...,

(

© F.A. Dul 2007

„Jan dzwoni, Maria dzwoni, alarm działa, nie ma włamania i nie ma
wstrz

sów” (j

∧

e ) wynosi

P( j

∧

e ) =

= P(j | a)

P(m | a)

P(a |

= 0.90

0.70

0.001

0.999

0.998

= 0.00062

B E

P(A|B,E)

0.95

0.94

0.29

0.01

Jan Dzwoni

Włamanie

Maria Dzwoni

Alarm

Wstrz

A P(J|A)
T

0.90

0.05

P(M|A)

0.70

0.01

P(B)

0.001

P(E)

0.002

14.2. Semantyka sieci Bayesa

Budowanie sieci Bayesa

1. Wybra

porz

dek zmiennych losowych X

, … ,X

;

2. Dla i = 1, … , n :

–

doda

do sieci;

–

wybra

spo

ród X

, … ,X

i-1

takich rodziców, dla których

P(X

| Rodzice(X

)) = P(X

| X

, ... X

i-1

)

© F.A. Dul 2007

Taki wybór rodziców gwarantuje wła

ciwe reprezentowanie

rozkładu ł

cznego:

P(X

, … ,X

)

∏

i =1

P(X

| X

, … , X

i-1

) (reguła ła

cuchowa)

∏

i =1

P(X

| Rodzice(X

))

(z konstrukcji)

Topologia sieci oraz jej zwarto

ść

zale

Ŝą

od pocz

tkowego

wyboru porz

dku zmiennych.

14.2. Semantyka sieci Bayesa

Przykład budowania sieci Bayesa

P(J | M) = P(J)?

Załó

my,

e wybrali

my porz

dek zmiennych: M, J, A, W, S;

an Dzwoni

aria Dzwoni

larm

P(A | J, M) = P(A | J)?

P(A | J, M) = P(A)?

P(W | A, J, M) = P(W | A)?

P(W | A, J, M) = P(W)?

Nie

Tak

© F.A. Dul 2007

• Inny porz

dek zmiennych wprowadził dwie nowe kraw

dzie.

• Sie

jest mniej zwarta ni

poprzednio: trzeba zapami

1 + 2 + 4 + 2 + 4 = 13 liczb.

• Okre

lanie niezale

ci warunkowej jest trudne

w kierunkach nieprzyczynowych (noncausal).

• Wydaje si

e modele przyczynowe i niezale

ść

warunkowa s

“wbudowane” w natur

ludzk

łamanie

trz

P(W | A, J, M) = P(W | A)?

P(S | W, A, J, M) = P(S | A, W)?

P(S | W, A ,J, M) = P(S | A)?

Nie

Tak

14.4. Wnioskowanie

cisłe w sieci Bayesa

∑

)

(

)

(

)

(

Prawdopodobie

stwo zmiennej

przy danych warto

ciach

zmiennych

E =

e jest równe

Wyznaczmy w zagadnieniu włamania prawdopodobie

stwo

zdarzenia

P(Wlamanie|JanDzwoni=prawda,MariaDzwoni=prawda)

∑∑

)

(

)

(

)

(

© F.A. Dul 2007

Dla przypadku w = (Włamanie=prawda) otrzymujemy

∑∑

)

(

)

(

)

(

)

(

)

(

)

(

gdzie: j = (JanDzwoni=prawda), m = (MariaDzwoni=prawda)

Po przegrupowaniu składników otrzymujemy

∑

)

(

)

(

)

(

)

(

)

(

)

(

14.4. Wnioskowanie

cisłe w sieci Bayesa

Wyznaczenie prawdopodobie

stwa dla

w = (Włamanie=prawda)

P(s)
0.002

0.998

P(w)

0.001

0.01197

0.592238

P(w|j,m) =

αααα ××××

0.000592238

∑

)

(

)

(

)

(

)

(

)

(

)

(

B E

P(A|B,E)

0.95

0.94

0.29

0.01

Jan Dzwoni

Włamanie

Maria Dzwoni

Alarm

Wstrz

A P(J|A)
T

0.90

0.05

P(M|A)

0.70

0.01

P(B)

0.001

P(E)

0.002

© F.A. Dul 2007

P(m|a)
0.70

P(j|a)
0.90

P(m|

0.01

P(j|

0.05

P(a|w,s)

0.95

a|w,s)

0.05

P(m|a)
0.70

P(j|a)
0.90

P(m|

0.01

P(j|

0.05

P(a|w,

0.94

a|w,

)

0.06

0.70

0.63

0.70

0.63

0.01

0.0005

0.01

0.0005

0.59223

0.5985

0.000025

0.598525

0.01197

0.5922

0.00003

0.591041

14.4. Wnioskowanie

cisłe w sieci Bayesa

Wyznaczenie prawdopodobie

stwa dla

w = (Włamanie=fałsz)

P(s)
0.002

0.998

0.999

0.000366

0.001493

w|j,m) =

αααα ××××

0.001492

∑

)

(

)

(

)

(

)

(

)

(

)

(

B E

P(A|B,E)

0.95

0.94

0.29

0.01

Jan Dzwoni

Włamanie

Maria Dzwoni

Alarm

Wstrz

A P(J|A)
T

0.90

0.05

P(M|A)

0.70

0.01

P(B)

0.001

P(E)

0.002

© F.A. Dul 2007

P(m|a)
0.70

P(j|a)
0.90

P(m|

0.01

P(j|

0.05

P(a|

w,s)

0.29

w,s)

0.71

P(m|a)
0.70

P(j|a)
0.90

P(m|

0.01

P(j|

0.05

P(a|

0.001

0.999

0.70

0.63

0.70

0.63

0.01

0.0005

0.01

0.0005

0.00113

0.1827

0.000355

0.183055

0.000366

0.00063

0.0005

0.001127

14.4. Wnioskowanie

cisłe w sieci Bayesa

Prawdopodobie

stwo zdarzenia

P(W | j,m)

jest wi

c równe

)

(

)

(

)

(

479.8245

0.001492)

0.000592

)

(

)

(

0.001492

0.000592

479.8245

)

0.716

0.284

(

Oznacza to,

e prawdopodobie

stwo włamania gdy dzwoni

)

0.001492

0.000592

(

© F.A. Dul 2007

Oznacza to,

e prawdopodobie

stwo włamania gdy dzwoni

oboje s

siedzi wynosi ok. 28%

Wady wnioskowania

cisłego w sieciach Bayesa:

• Składniki wyra

enia dla prawdopodobie

stwa s

obliczane

wielokrotnie, np. P(j|a)P(m|a) czy P(j|

a)P(m|

a).

• Zło

ono

ść

obliczeniowa dla sieci z n zmiennymi boolowskimi

jest wykładnicza -

O(2

)

ale jest ni

sza ni

w przypadku

ogólnym, w którym

O(n

)

14.5. Wnioskowanie przybli

one w sieci Bayesa

Ze wzgl

du na wielk

zło

ono

ść

obliczeniow

wyznaczania

prawdopodobie

stwa na podstawie sieci Bayesa w praktyce

stosuje si

najcz

ęś

ciej wnioskowania przybli

one.

Algorytm Monte Carlo próbkowania zmiennych losowych
Idea: przy du

ej liczbie próbkowa

prawdopodobie

stwo okre-

lone jako liczba próbek danej warto

ci zmiennej w stosunku

do liczby wszystkich próbkowa

ąŜ

y do warto

ci dokładnej,

)

(

∑

© F.A. Dul 2007

Przykład: rzut monet

, Moneta =

〈〈〈〈

orzeł , reszka

〉〉〉〉

, prawdopo-

dobie

stwo

cisłe P(Moneta) =

〈〈〈〈

0.5 , 0.5

〉〉〉〉

, za

przybli

one

)

(

lim

)

(

∑

∞

→

orzeł

)

(

)

(

∑

≈

...}

{

)

(

reszka

)

(

)

(

∑

≈

Przykład: kolejne rzuty monet

prowadz

do oszacowa

14.5. Wnioskowanie przybli

one w sieci Bayesa

Próbkowanie losowe w sieci Bayesa.

Chmury

P(C)=0.5

Zasada: próbkowanie ka

dej zmiennej w kolejno

ci okre

lonej

przez sie

Przykład: sie

Bayesa dla problemu mokrej trawy, uporz

dko-

wana nast

puj

co: [ Chmury, Zraszacz, Deszcz, MokraTrawa ]

© F.A. Dul 2007

Zraszacz

MokraTrawa

Deszcz

C P(Z)

0.10

0.50

C P(D)

0.80
0.20

Z D P(D)

t t
t

0.99
0.90
0.90
0.00

14.5. Wnioskowanie przybli

one w sieci Bayesa

Próbkowanie przykładowe w sieci:

1. Próbkowanie P(Chmury) =

〈〈〈〈

0.5, 0.5

〉〉〉〉

wynik:

prawda

;

2. Próbkowanie P(Zraszacz|Chmury=

prawda

) =

〈〈〈〈

0.1, 0.9

〉〉〉〉

wynik:

fałsz

;

3. Próbkowanie P(Deszcz|Chmury=

prawda

) =

〈〈〈〈

0.8, 0.2

〉〉〉〉

wynik:

prawda

;

4. Próbkowanie P(MokraTrawa|Zraszacz=

fałsz

,Deszcz=

prawda

) =

〈〈〈〈

0.9,0.1

〉〉〉〉

wynik:

prawda

;

Próbkowanie zwróciło wi

c zdarzenie zgodne z sieci

= [

prawda

fałsz

prawda

Kolejne próbkowanie mo

e zwróci

inne zdarzenie, np.

© F.A. Dul 2007

Kolejne próbkowanie mo

e zwróci

inne zdarzenie, np.

= [

prawda

fałsz

prawda

∏

rodzice

))

(

)

,...,

(

Ze sposobu próbkowania wynika, ze prawdopodobie

stwo

,...,x

) wybranej próbki [x

,...,x

] wynosi

i jest równe prawdopodobie

stwu zdarzenia reprezentowanym

przez sie

Bayesa

)

,...,

(

)

,...,

(

14.5. Wnioskowanie przybli

one w sieci Bayesa

eli N

,...,x

) jest liczb

wylosowa

próbki [x

,...,x

], to

W przykładzie mokrej trawy prawdopodobie

stwa zdarze

wylosowanych z sieci Bayesa wynosz

)

,...,

(

)

,...,

(

)

,...,

(

lim

∞

→

) = 0.5

××××

0.9

××××

0.8

××××

0.9 = 0.324,

) = 0.5

××××

0.1

××××

0.2

××××

0.9 = 0.009.

) = 0.5

××××

0.1

××××

0.2

××××

0.9 = 0.009.

Przy du

ej liczbie próbkowa

N zdarzenie Z

dzie wybrane

w 32.4%, za

zdarzenie Z

- tylko w 0.9% przypadków.

Koszt C wnioskowania przybli

onego w sieciach Bayesa jest

zazwyczaj du

o ni

szy ni

koszt wnioskowania

cisłego,

C << O(2

)

Istniej

równie

inne metody wnioskowania przybli

onego

w sieciach Bayesa, np. metoda

Monte Carlo dla ła

cucha

Markowa

(Markov chain Monte Carlo).

yteczno

ść

sieci Bayesa

Sieci Bayesa stanowi

wygodn

form

reprezentacji

zale

ci zdarze

Pozwalaj

znacznie zredukowa

rozmiar

reprezentacji a tak

e koszt wnioskowania

stochastycznego.

Wnioskowanie przybli

one w sieciach Bayesa

cechuje si

niskim kosztem przy zadowalaj

cych

F.A. Dul 2007

cechuje si

niskim kosztem przy zadowalaj

cych

dokładno

ciach uzyskiwanych rozkładów

prawdopodobie

stw.

Sieci Bayesa s

równie

wykorzystywane do opisu

dynamicznych zjawisk stochastycznych stanowi

podstaw

filtru Kalmana

14.7. Inne metody wnioskowania probabilistycznego

Podej

cie stochastyczne jest szeroko stosowane w wielu

dziedzinach wiedzy i praktyki: w fizyce, genetyce, ekonomii,
ubezpieczeniach, bankowo

ci...

W sztucznej inteligencji podej

cie probabilistyczne jest

ywane dopiero od lat 70. XX wieku, głównie w systemach

ekspertowych.

Powodem był wykładniczy koszt wnioskowania – wcze

niej

nie znano algorytmów dla sieci Bayesa.

Dlatego do wnioskowania w warunkach niepewno

stosowano podej

cia alternatywne, takie jak:

• Wnioskowanie

domy

lne

• Reprezentacja niepewno

ci za pomoc

reguł

• Reprezentacja ignorancji (teoria

Dempstera-Shafera

• Reprezentacja nieprecyzyjno

ci za pomoc

logiki rozmytej

Panuje przekonanie,

e wnioskowanie stochastyczne jest

bardziej uniwersalne ni

powy

sze wnioskowania alternatywne.

14.7. Inne metody wnioskowania probabilistycznego

Metody wnioskowania oparte na regułach
Metody wnioskowania wykorzystuj

ce reguły s

podobne

do metod logiki zda

lub pierwszego rz

du.

Wnioskowanie logiczne jest uzupełnione czynnikiem
okre

laj

cym stopie

wiarygodno

(fudge factor)

, np.

→

0.3

zapewni dojazd na czas;

Uwzgl

dnienie stopnia wiarygodno

ci umo

liwia „sterowanie”

wnioskowaniem logicznym.
Jednak z podej

ciem takim wi

ąŜą

trudno

ci.

Jednak z podej

ciem takim wi

ąŜą

trudno

ci.

Przykład
Czy mokra trawa jest wynikiem deszczu,
czy te

wł

czenia zraszacza?

Zraszacz

MokraTrawa

Deszcz

Mimo takich problemów wnioskowanie z

czynnikiem pewno

jest stosowane z powodzeniem w wielu systemach
ekspertowych (np. MYCIN).

– Zraszacz |

→

0.99

MokraTrawa;

– MokraTrawa |

→

0.7

Deszcz;

Problem: czy zraszacz powoduje deszcz?

14.7. Inne metody wnioskowania probabilistycznego

Teoria Dempstera-Shafera reprezentacji ignorancji

Teoria Dempstera-Shafera opisuje ró

nice pomi

dzy

niepewno

ignorancj

Funkcja wiarygodno

Bel(X)

opisuje prawdopodobie

stwo

tego,

e obserwacje potwierdzaj

twierdzenie

Przykład
Dla zdarzenia „Reszka” przy rzucie niepewn

monet

i przy

braku obserwacji zarówno

Bel(Reszka)=0

jak i

Bel(

Reszka)=0

eli stwierdzi si

z 90% pewno

e moneta jest dobra,

eli stwierdzi si

z 90% pewno

e moneta jest dobra,

(

P(Reszka)=0.5

), to

Bel(Reszka) = 0.9

0.5 = 0.45

; podobnie

Bel(

Reszka) = 0.45

Istniej

ca 10% luka wyra

a niepewno

ść

co do jako

ci monety.

Reguła Dempstera

okre

la sposób wyznaczania warto

funkcji

Bel

na podstawie obserwacji.

Teoria Dempstera-Shafera definiuje przedziały prawdopodo-
bie

stwa, np. dla wyrzucenia reszki przedział prawdopodo-

bie

stwa wynosi [0,1] przed weryfikacj

monety, za

po jej

weryfikacji [0.45,0.55].

14.7. Inne metody wnioskowania probabilistycznego

Logika rozmyta i reprezentacja nieprecyzyjno

Teoria zbiorów rozmytych okre

nieprecyzyjno

ść

twierdze

Przykład
Czy zdanie „Jan jest wysoki” (wzrost 175cm) jest prawdziwe?
Najcz

stsza odpowied

: Jan jest wysoki

„w pewnym stopniu”

UWAGA!

Nieprecyzyjno

ść

nie jest niepewno

(wzrost Jana

jest znany).
Teoria zbiorów rozmytych okre

la stopie

prawdziwo

twierdze

, np. Wysoki(Jan)

∈

[0,1] zamiast Wysoki(Jan)=fałsz.

twierdze

, np. Wysoki(Jan)

∈

[0,1] zamiast Wysoki(Jan)=fałsz.

Stopie

prawdziwo

ci opisuje zazwyczaj rozkład typu

probit

1.0 1.5 2.0 m 2.5

1.0

Wysoki

0.0

14.7. Inne metody wnioskowania probabilistycznego

Logika rozmyta i reprezentacja nieprecyzyjno

Logika rozmyta

umo

liwia wnioskowanie z wyra

eniami

logicznymi okre

lonymi w zbiorach rozmytych.

Miara prawdziwo

ci T okre

lona jest regułami:

Problemy: T(Wysoki(Jan)) = 0.6, T(Ci

ęŜ

ki(Jan)) = 0.4.

T(Wysoki(Jan)

∧

ęŜ

ki(Jan)) = 0.4

→

OK.

• T(A

∧

B) = min ( T(A) , T(B) ),

• T(A

∨

B) = max ( T(A) , T(B) ),

• T(

A) = 1 – T(A).

Sterowanie rozmyte

słu

y do syntezy sterowania przy u

yciu

reguł rozmytych.
Sterowanie rozmyte jest szeroko stosowane w wielu
urz

dzeniach, np.: pralkach, kamerach wideo, sprz

cie AGD.

T(Wysoki(Jan)

∧

ęŜ

ki(Jan)) = 0.4

→

OK.

T(Wysoki(Jan)

∧

Wysoki(Jan)) = 0.4

???

Podsumowanie

• Sieci Bayesa stanowi

naturaln

reprezentacj

niezale

ci warunkowej (indukowanej przyczynowo).

• Topologia sieci i tablice prawdopodobie

stwa warunkowego

(CPT) pozwalaj

na zwart

reprezentacj

rozkładu ł

cznego

prawdopodobie

stwa.

• Sieci Bayesa s

szczególnie przydane i łatwe do zastosowa-

nia w systemach ekspertowych.

• Wnioskowanie

cisłe z u

yciem sieci Bayesa jest kosztowne

• Wnioskowanie

cisłe z u

yciem sieci Bayesa jest kosztowne

~O(2

• Wnioskowanie przybli

one za pomoc

próbkowania zdarze

pozwala obni

koszt oblicze

przy zachowaniu akcepto-

walnej dokładno

ci wyznaczonych prawdopodobie

stw.

• Zwykłe sieci Bayesa maj

cechy logiki zda

, co ogranicza

zakres ich zastosowania.

• Istniej

inne sposoby uwzgl

dniania niepewno

ci: reguły

niepewno

ci, reprezentacja ignorancji, logika rozmyta.