Sieci Bayesa
Jacek Kluska
Politechnika Rzeszowska
2011
J. Kluska (Politechnika Rzeszowska)
2011
1 / 25
Sieci Bayesa
Jacek Kluska
Politechnika Rzeszowska
2011
J. Kluska (Politechnika Rzeszowska)
2011
1 / 25
Prawdopodobie´nstwa ÷¾
aczne, a’posteriori i regu÷
a Bayesa
Za÷
ó·
zmy, ·
ze zmienne losowe A i B przyjmuj ¾
a warto´sci dyskretne:
A
2 f
a
1
, . . . , a
n
g
, B
2 f
b
1
, . . . , b
m
g
. De…niujemy tablic ¾
e
prawdopodobie´nstwa ÷¾
acznego (Joint Probability Distribution)
P
(
A
=
a
i
, B
=
b
j
)
jako macierz
f
P
(
a
i
, b
j
)g
n m
.
Example
Za÷
o·
zenie: A
2 f
a
1
, a
2
, a
3
g
, B
2 f
b
1
, b
2
g
.
f
P
(
a
i
, b
j
)g =
JPD
b
1
b
2
∑
a
1
P
(
a
1
, b
1
)
P
(
a
1
, b
2
)
P
(
a
1
)
a
2
P
(
a
2
, b
1
)
P
(
a
2
, b
2
)
P
(
a
2
)
a
3
P
(
a
3
, b
1
)
P
(
a
3
, b
2
)
P
(
a
3
)
∑
P
(
b
1
)
P
(
b
2
)
1
∑
i
P
(
a
i
, b
j
) =
P
(
b
j
)
,
∑
j
P
(
a
i
, b
j
) =
P
(
a
i
)
,
∑
i ,j
P
(
a
i
, b
j
) =
1
J. Kluska (Politechnika Rzeszowska)
2011
2 / 25
JPD umo·
zliwia obliczenie prawdopodobie´nstwa
warunkowego
P
(
b
j
j
a
i
) =
P
(
a
i
, b
j
)
P
(
a
i
)
Np.
P
(
b
2
j
a
3
) =
P
(
a
3
, b
2
)
P
(
a
3
)
=
P
(
a
3
, b
2
)
P
(
a
3
, b
1
) +
P
(
a
3
, b
2
)
Przypu´s´cmy, ·
ze wyst ¾
api A a potem B. Tablica prawdopodobie´nstwa
warunkowego, ·
ze wyst ¾
api b
j
pod warunkiem wyst ¾
apienia a
i
(Conditional
Probability Table). Np. dla A
2 f
a
1
, a
2
, a
3
g
, B
2 f
b
1
, b
2
g
:
CPT
b
1
b
2
∑
a
1
P
(
b
1
j
a
1
)
P
(
b
2
j
a
1
)
1
a
2
P
(
b
1
j
a
2
)
P
(
b
2
j
a
2
)
1
a
3
P
(
b
1
j
a
3
)
P
(
b
2
j
a
3
)
1
J. Kluska (Politechnika Rzeszowska)
2011
3 / 25
Przyk÷
ad obliczenia JPD
Za÷
o·
zenia: A
2 f
a
1
, a
2
, a
3
g
, B
2 f
b
1
, b
2
g
, po zdarzeniu A mo·
ze wyst ¾
api´c
B, znamy P
(
A
)
, znamy CPT tzn. P
(
B
j
A
)
.
Nale·
zy wyznaczy´c P
(
B
)
i JPD:
[
P
(
b
1
)
, P
(
b
2
)] = [
P
(
a
1
)
, P
(
a
2
)
, P
(
a
3
)]
2
4
P
(
b
1
j
a
1
)
P
(
b
2
j
a
1
)
P
(
b
1
j
a
2
)
P
(
b
2
j
a
2
)
P
(
b
1
j
a
3
)
P
(
b
2
j
a
3
)
3
5
f
P
(
a
i
, b
j
)g =
2
4
P
(
a
1
)
0
0
0
P
(
a
2
)
0
0
0
P
(
a
3
)
3
5
2
4
P
(
b
1
j
a
1
)
P
(
b
2
j
a
1
)
P
(
b
1
j
a
2
)
P
(
b
2
j
a
2
)
P
(
b
1
j
a
3
)
P
(
b
2
j
a
3
)
3
5
=
2
4
P
(
b
1
j
a
1
)
P
(
a
1
)
P
(
b
2
j
a
1
)
P
(
a
1
)
P
(
b
1
j
a
2
)
P
(
a
2
)
P
(
b
2
j
a
2
)
P
(
a
2
)
P
(
b
1
j
a
3
)
P
(
a
3
)
P
(
b
2
j
a
3
)
P
(
a
3
)
3
5
J. Kluska (Politechnika Rzeszowska)
2011
4 / 25
Przyk÷
ad zastosowania regu÷
y Bayesa do wnioskowania
Podstawa wnioskowania probabilistycznego:
P
(
B
j
A
) =
P
(
B
)
P
(
A
)
P
(
A
j
B
)
Przyk÷
ad. U pacjenta przeprowadzono test na obecno´s´c wirusa. Test
wypad÷pozytywnie. Czy pacjenta nale·
zy koniecznie hospitalizowa´c i
rozpocz ¾
a´c leczenie?
Testy nigdy nie s ¾
a ca÷
kowicie niezawodne. Dobry test zapewnia wysokie
prawdopodobie´nstwo:
wyniku pozytywnego (potwierdzaj ¾
acego obecno´s´c wirusa W ), o ile
wirus W jest rzeczywi´scie obecny: P
(
T
j
W
)
,
wyniku negatywnego – w przypadku braku wirusa: P T
j
W .
Lekarza i pacjenta najbardziej interesuj ¾
a szanse:
P
(
W
j
T
)
albo P W
j
T .
J. Kluska (Politechnika Rzeszowska)
2011
5 / 25
Przyk÷
ad zastosowania regu÷
y Bayesa do wnioskowania -
c.d.
Aby na podstawie przeprowadzonego testu wnioskowa´c o
prawdopodobie´nstwie zainfekowania wirusem, konieczne jest skorzystanie z
regu÷
y Bayesa.
Za÷
o·
zenia wynikaj ¾
ace z danych historycznych:
1
Wirus wyst ¾
epuje przeci ¾
etnie u 20 ludzi na 100 000:
P
(
W
) =
p
=
0.0002
2
Je·
zeli wirus rzeczywi´scie wyst ¾
epuje, to test daje wynik pozytywny w
90 przypadkach na 100: P
(
T
j
W
) =
a
=
0.90.
3
Je·
zeli wirus nie wyst ¾
epuje, to test daje wynik negatywny w 75
przypadkach na 100: P T
j
W
=
b
=
0.75.
Rozwa·
zmy pacjenta, dla którego test da÷wynik pozytywny. Jakie jest
prawdopodobie´nstwo, ·
ze pacjent zosta÷zainfekowany wirusem:
P
(
W
j
T
) =
?
J. Kluska (Politechnika Rzeszowska)
2011
6 / 25
Przyk÷
ad zastosowania regu÷
y Bayesa do wnioskowania -
c.d.
P
(
W
j
T
) =
P
(
W
)
P
(
T
)
P
(
T
j
W
)
=
P
(
W
)
P
(
T
j
W
)
P
(
W
) +
P T
j
W P W
P
(
T
j
W
)
=
ap
ap
+ (
1
b
) (
1
p
)
=
0.00071963
Czy w przypadku P
(
W
j
T
) <
0.1% warto podejmowa´c terapi ¾
e (by´c mo·
ze
nieoboj ¾
etn ¾
a dla zdrowia) ?
J. Kluska (Politechnika Rzeszowska)
2011
7 / 25
Przyk÷
ad zastosowania regu÷
y Bayesa do wnioskowania -
c.d.
Co si ¾
e zmieni, gdy b ¾
ed ¾
a wykonywane 2 niezale·
zne od siebie testy? Wyniki
testów zale·
z ¾
a tylko od wyst ¾
epowania wirusa. Zk÷
adamy, ·
ze znane s ¾
a:
P
(
W
) =
p
=
0.0001, P
(
T 1
j
W
) =
a
1
=
0.95, P
(
T 2
j
W
) =
a
2
=
0.95,
P T 1
j
W
=
b
1
=
0.90, P T 2
j
W
=
b
2
=
0.90.
P
(
W
j
T 1
^
T 2
) =
P
(
W
)
P
(
T 1
^
T 2
)
P
(
T 1
^
T 2
j
W
)
=
P
(
W
)
P
(
T 1
)
P
(
T 2
)
P
(
T 1
j
W
)
P
(
T 2
j
W
)
=
p
a
1
a
2
(
a
1
p
+ (
1
b
1
) (
1
p
)) (
a
2
p
+ (
1
b
2
) (
1
p
))
gdzie
P
(
Ti
) =
P
(
Ti
j
W
)
P
(
W
) +
P Ti
j
W P W
=
P
(
Ti
j
W
)
P
(
W
) +
1
P Ti
j
W
(
1
P
(
W
))
J. Kluska (Politechnika Rzeszowska)
2011
8 / 25
Przyk÷
ad zastosowania regu÷
y Bayesa do wnioskowania -
c.d.
Ile razy wzros÷
o prawdopodobie´nstwo poprzez wykonanie dwóch testów
zamiast jednego ?
P
(
W
j
T 1
^
T 2
)
P
(
W
j
T 1
)
=
P
(
W
)
P
(
T 1
j
W
)
P
(
T 2
j
W
)
P
(
T 1
)
P
(
T 2
)
P
(
W
)
P
(
T 1
j
W
)
P
(
T 1
)
=
P
(
T 2
j
W
)
P
(
T 2
)
=
a
2
a
2
p
+ (
1
b
2
) (
1
p
)
=
9.4919
J. Kluska (Politechnika Rzeszowska)
2011
9 / 25
Sie´c Bayesa (Bayes network, sie´c przekona´n, belief
network)
Graf skierowany bez cykli, którego wierzcho÷
kami s ¾
a zmienne losowe.
×uk X
!
Y ma intuicyjne znaczenie: “zmienna X ma bezpo´sredni
wp÷
yw na Y”.
Ka·
zdy wierzcho÷
ek X ma zwi ¾
azan ¾
a z nim tablic ¾
e
prawdopodobie´nstw warunkowych (CPT — Conditional
Probability Table) okre´slaj ¾
acych wp÷
yw wywierany na X przez jego
poprzedników w gra…e (rodziców).
Musimy okre´sli´c prawdopodobie´nstwa warunkowe dla ka·
zdej warto´sci
zmiennej losowej X dla wszystkich kombinacji warto´sci zmiennych
losowych, od których zale·
zy X.
Dla zmiennych, które nie zale·
z ¾
a od niczego, musimy okre´sli´c
prawdopodobie´nstwa a’priori.
J. Kluska (Politechnika Rzeszowska)
2011
10 / 25
Oszacowanie liczby prawdopodobie´nstw w sieci Bayesa
Na podstawie ÷¾
acznego rozk÷
adu prawdopodobie´nstwa (JPD, Joint
Probability Distribution) mo·
zna wyznaczy´c praktycznie wszystko.
Gdyby sie´c Bayesa mia÷
a N
=
20 wierzcho÷
ków, to tablica JPD
mia÷
aby 2
N
=
2
20
=
1 048 576 elementów. Za÷
ó·
zmy, ·
ze ka·
zdy
wierzcho÷
ek w sieci zale·
zy od K
=
6 zmiennych binarnych. Liczba
prawdopodobie´nstw warunkowych w CPT w jednym wierzcho÷
ku
wynosi 2
K
=
2
6
=
64, a we wszystkich N wierzcho÷
kach:
N
2
K
=
20
2
6
=
1 280.
Dzi ¾
eki sieci Bayesa mo·
zemy uzyska´c du·
z ¾
a oszcz ¾
edno´s´c, która jest
mo·
zliwa tylko wtedy, gdy zmienne bezpo´srednio zale·
z ¾
a tylko od
pewnej (ma÷
ej) liczby innych zmiennych. Gdyby zmienne w sieci
zale·
za÷
y od wszystkich innych zmiennych, to reprezentacja tych
zale·
zno´sci w postaci sieci Bayesa mia÷
aby niewielki sens.
J. Kluska (Politechnika Rzeszowska)
2011
11 / 25
Przyk÷
ad: Sie´c Bayesa budowana na podstawie statystyk
dla pewnej kliniki p÷
uc
Lauritzen S.L., Spiegelhalter D. J. (1988), Local computations with
probabilities on graphical structures and their application to expert
systems, Journal of the Royal Statistical Society, Series B
(Methodological), 50(2), 157-224:
50% pacjentów tej kliniki to palacze,
1% choruje na gru´zlic ¾
e,
5.5% ma raka p÷
uc,
45% ma jak ¾
a´s form ¾
e z ÷
agodnego lub przewlek÷
ego zapalenia oskrzeli,
Duszno´sci wykryte s ¾
a ´srednio u 10% ludzi - wi ¾
ekszo´s´c z powodu
astmy i powodów innych, ni·
z gru´zlica, rak p÷
uc lub zapalenie oskrzeli.
J. Kluska (Politechnika Rzeszowska)
2011
12 / 25
Przyk÷
ad: Sie´c Bayesa - klinika gru´zlicy i chorób p÷
uc
Za÷
o·
zenia ogólne - 3 typy danych:
1
Czynniki maj ¾
ace wp÷
yw na powstawanie chorób p÷
uc
{odwiedzenie Azji, palenie papierosów},
2
Rodzaje chorób p÷
uc:
{gru´zlica, zapalenie p÷
uc, zapalenie oskrzeli},
3
Objawy chorobowe:
{wyniki Rtg, duszno´sci}.
Uwaga: Przyk÷
ad nie nadaje si ¾
e do zastosowa´n wprost, ze wzgl ¾
edu na
ma÷¾
a liczb ¾
e danych.
J. Kluska (Politechnika Rzeszowska)
2011
13 / 25
Przyk÷
ad - Bezwarunkowe prawdopodobie´nstwa a’priori
dotycz ¾
ace czynników maj ¾
acych wp÷
yw na powstawanie
chorób p÷
uc
A: Pacjent odwiedzi÷Azj ¾
e:
B: Pacjent jest palaczem:
P(A=tak)=0.01,
P(B=tak)=0.50,
P(A=nie)=0.99;
P(B=nie)=0.50
J. Kluska (Politechnika Rzeszowska)
2011
14 / 25
Przyk÷
ad - Warunkowe prawdopodobie´nstwa a’priori
wyst ¾
epowania chorób: {gru´zlica, rak p÷
uc, zapalenie
oskrzeli}
C: Wyst ¾
epuje gru´zlica pod warunkiem, ·
ze pacjent odwiedzi÷Azj ¾
e: P(C
j
A)
P(C
j
A=tak)
P(C
j
A=nie)
A=tak
0.05
0.95
A=nie
0.01
0.99
D: Wyst ¾
epuje rak p÷
uc pod warunkiem, ·
ze pacjent jest palaczem: P(D
j
B)
P(D
j
B=tak)
P(D
j
B=nie)
B=tak
0.10
0.90
B=nie
0.01
0.99
E: Wyst ¾
epuje zapalenie oskrzeli pod warunkiem, ·
ze pacjent jest palaczem:
P(E
j
B)
P(E
j
B=tak)
P(E
j
B=nie)
B=tak
0.60
0.40
B=nie
0.30
0.70
J. Kluska (Politechnika Rzeszowska)
2011
15 / 25
Przyk÷
ad - okre´slenie funkcji deterministycznej dla w ¾
ez÷
a
sieci Bayesa “gru´zlica lub rak p÷
uc”
Funkcja potrzebna do obliczenia pr. wyst ¾
apienia gru´zlicy lub rak p÷
uc:
P(F
j
C lub D)
F: Funkcja deterministyczna:
(C, D)=(tak,tak)
)
(C lub D)=tak
(C, D)=(tak,nie)
)
(C lub D)=tak
(C, D)=(nie,tak)
)
(C lub D)=tak
(C, D)=(nie,nie)
)
(C lub D)=nie
J. Kluska (Politechnika Rzeszowska)
2011
16 / 25
Przyk÷
ad - warunkowe prawdopodobie´nstwa a’priori
objawów choroby: “Wynik Rtg wskazuje chorob ¾
e” oraz
“Wyst ¾
epuj ¾
a duszno´sci”
G: Wynik badania Rtg jest pozytywny pod warunkiem istnienia “gru´zlicy
lub raka p÷
uc”:
P(G
j
F)=tak
P(G
j
F)=nie
F=tak
0.02
0.98
F=nie
0.95
0.05
H: Wyst ¾
epuj ¾
a duszno´sci pod warunkiem F (gru´zlica lub rak p÷
uc) i E
(zapalenie oskrzeli): P(H
j
F
^
E)=tak, P(H
j
F
^
E)=nie
(F, E)=(tak,tak)
0.90
0.10
(F, E)=(tak,nie)
0.70
0.30
(F, E)=(nie,tak)
0.80
0.20
(F, E)=(nie,nie)
0.10
0.90
J. Kluska (Politechnika Rzeszowska)
2011
17 / 25
Pierwotna sie´c Bayesa i wnioskowanie
Sie´c pierwotna (tu·
z po wprowadzeniu wiedzy a’priori) przedstawia
sytuacj ¾
e zupe÷
nego braku wiedzy o konkretnym pacjencie (wiedza
wynika tylko z danych statystycznych).
Praktyczna korzy´s´c z wnioskowania bayesowskiego:
Wprowadzanie nowej informacji powoduje korygowanie
prawdopodobie´nstw w sieci, a to odbywa si ¾
e automatycznie.
J. Kluska (Politechnika Rzeszowska)
2011
18 / 25
Przyk÷
ad - “Pacjent ma duszno´sci”, P(H) = 1
1
P(E): 45%
%
83.4%. E jest cz ¾
e´sciej spotykane ni·
z F.
2
P(B): 50%
%
63.4%. Wzros÷
a szansa, ·
ze pacjent jest palaczem (B) ...
3
P(A): 1%
%
1.03%. Szansa na A jest prawie taka sama.
4
P(G): 11%
%
16%. Szanse Rtg “poza norm ¾
a” (G).
J. Kluska (Politechnika Rzeszowska)
2011
19 / 25
Przyk÷
ad - pierwsze wnioski, gdy: “Pacjent ma duszno´sci”
Co dolega pacjentowi?
Gro´zba fatalnego rozpoznania:
P(E)=0.834 - cierpi na zapalenie oskrzeli? Je´sli zatrzymujemy si ¾
e w
tym miejscu i diagnozujemy pacjenta jako chorego na zapalenie
oskrzeli, podczas, gdy by÷
by chory na raka, to by÷
oby fatalne
rozpoznanie.
Potrzebujemy wi ¾
ecej informacji.
J. Kluska (Politechnika Rzeszowska)
2011
20 / 25
Przyk÷
ad - wprowadzenie nowej informacji: “Pacjent
odwiedzi÷Azj ¾
e”
“Usprawiedliwianie” w sieci Bayesa:
Je·zeli istniej ¾
a rywalizuj ¾
ace ze sob ¾
a mo·zliwe powody zaistnienia
jakiego´s zdarzenia i szanse jednego z nich wzros÷
y, to inne szanse
zmniejszaj ¾
a si ¾
e i s ¾
a “usprawiedliwione”.
P(C): 2%
%
9%. H jest lepiej wyja´snione. P(D), P(E), P(B):
&
.
J. Kluska (Politechnika Rzeszowska)
2011
21 / 25
Przyk÷
ad - wprowadzenie nowej informacji: “Pacjent pali”
Nadal najlepsz ¾
a hipotez ¾
a jest E, nie C czy D.
Jednak trzeba si ¾
e upewni´c wykonuj ¾
ac prze´swietlenie Rtg.
J. Kluska (Politechnika Rzeszowska)
2011
22 / 25
Przyk÷
ad - wprowadzenie nowej informacji: “Wyniki bada´n
Rtg s ¾
a w normie”
Mocne potwierdzenie E i nik÷
e szanse D.
J. Kluska (Politechnika Rzeszowska)
2011
23 / 25
Przyk÷
ad - wprowadzenie nowej informacji: “Wyniki bada´n
Rtg nie s ¾
a w normie”
Teraz C i D
%
. E jest wci ¾
a·
z najbardziej prawdopodobne w zbiorze {C,D,E}
ale jest mniejsze, ni·
z hipoteza F=D
[
C.
Trzeba wykona´c dalsze testy, badania krwi, biopsje tkanki p÷
ucnej itp.
Mocna strona sieci Bayesa:
Obecna sie´c Bayesa nie relacjonuje tych testów ale mo·
zna j ¾
a poszerza´c
dodaj ¾
ac nowe w ¾
ez÷
y - bez wyrzucania cz ¾
e´sci poprzedniej sieci.
J. Kluska (Politechnika Rzeszowska)
2011
24 / 25
Podsumowanie
Sie´c Bayesa pozwala na intuicyjn ¾
a, gra…czn ¾
a wizualizacj ¾
e wiedzy
zawieraj ¾
ac ¾
a wzajemne oddzia÷
ywania pomi ¾
edzy ró·
znymi ´zród÷
ami
niepewno´sci.
Mechanizm wnioskowania wykorzystuje twierdzenie Bayesa:
P(A
j
B)P(B)=P(B
j
A)P(A) i polega na obliczaniu prawdopodobie´nstwa
ka·
zdego mo·
zliwego wyniku, gdy znany jest konkretny przypadek.
Sieci Bayesa mog ¾
a by´c stosowane m.in. w diagnostyce (systemy
doradcze), w rozumowaniu przebiegaj ¾
acym od objawów do przyczyn i
odwrotnie.
Wady:
wymaga si ¾
e dok÷
adnych znajomo´sci warto´sci prawdopodobie´nstw,
nie zawsze jest spe÷
nione podstawowe za÷
o·
zenie: “A i B s ¾
a warunkowo
niezale·
zne przy znajomo´sci C
,
P(A
j
B,C)=P(A
j
C)”,
czasami wymaga si ¾
e nierealistycznych za÷
o·
ze´n, np. wymagane wyniki
rozpoznania musz ¾
a si ¾
e wzajemnie wyklucza´c, tymczasem pacjent mo·
ze
mie´c wiele chorób jednocze´snie.
J. Kluska (Politechnika Rzeszowska)
2011
25 / 25