Bizonytalanságok melletti következtetés Mesterséges Intelligencia I.
Valószínűségi alapfogalmak (ismétlés) A, B,C események esetén a priori valószínűség:
P A
feltételes (a posteiori) valószínűség:
P A∣B =
P A∩B P B
Bayes-formula1
P A∣B =
P B∣A⋅P A P B
A és B függetlenek
P A∩B = P A⋅P B
A és B függetlenek
P A∣B = P A
A és B feltételesen függetlenek
P A∩B∣C = P A∣C ⋅P B∣C
A és B feltételesen függetlenek
P A∣B∩C = P A∣C
Naiv Bayes módszer Adottak:
A={A1, A2, ... , An }
attribútumok halmaza
V ={C 1, C 2, ... ,C m }
osztály-címkék halmaza
E ⊆{ A1× A2 ×× A n ×V }
példahalmaz
Kérdés, hogy egy X = x 1, x 2, ... , x n tulajdonság-vektorral leírt objektum, ahol (valószínűleg) melyik C ' osztályba tartozik?
x i ∈Ai , 1≤i≤n ,
Módszer: n
C ' =argmaxC ∈{V } P V =C ⋅∏ P Ai = x i∣V =C i =1
A módszer feltételezi, hogy az egyes attribútum-párok feltételesen függetlenek, innen a naiv elnevezés. 1
Nem tévesztendő össze a Bayes-tétellel, ahol a P(B) valószínűséget a teljes valószínűség tétele adja meg
Példa
A={A1, A2, A3, A4 } A1
= {S,O,R }:
időjárás (S: napos, O: felhős, R: esős)
A2
= {H,M,C }:
hőmérséklet (H: magas, M: közepes, C: hűvös)
A3
= {H, N }:
páratartalom (H: magas, N: normális)
A4
= {T, F }:
szél (T: szél van, F: nincs szél)
C
= {Y, N }:
érdemes-e a teniszpályára menni (Y: igen, N: nem)
Kérdés:
X =S , C , H , S mellett érdemes-e kimenni teniszezni?
Adatbázis
A1
A2
A3
A4
C
1
S
H
H
F
N
2
S
H
H
T
N
3
O
H
H
F
Y
4
R
M
H
F
Y
5
R
C
N
F
Y
6
R
C
N
T
Y
7
O
C
N
T
N
8
S
M
H
F
Y
9
S
C
N
F
N
10
R
M
N
F
Y
11
S
M
N
T
Y
12
O
M
H
T
Y
13
O
H
N
F
Y
14
R
M
H
T
N
Számítások
P Y =
9 14
P S∣Y =
5 14
2 9
P S∣N =
3 9
P C∣N =
3 9
P H∣N =
3 9
P T∣N =
P C∣Y =
P H∣Y =
P T∣Y =
P N =
3 5
1 5 4 5
3 5
Végül,
P Y ⋅P S∣Y ⋅P C∣Y ⋅P H∣Y ⋅P T∣Y =
9 2 3 3 3 1 ⋅ ⋅ ⋅ ⋅ = =0.005 14 9 9 9 9 189
P N ⋅P S∣N ⋅P C∣N ⋅P H∣N ⋅P T∣N =
azaz
5 3 1 4 3 18 ⋅ ⋅⋅ ⋅ = =0.02 14 5 5 5 5 875
C ' =N , hiszen ahhoz tartozik a nagyobb valószínűség, így nem érdemes kimenni teniszezni.
m-estimate of probability Előfordulhatnak 0 értékek a feltételes valószínűségekben, amely torzítja az eredményt:
P Ai = x i∣Y =v=0 Ha tudjuk, hogy az előbbi értéknek közelítőleg mennyinek kellene lennie, akkor a következő becslés adódhat:
P Ai = x i∣Y =v ≈
∣{ X , y ∈ E : Ai= x i , Y =v }∣ p i ,m⋅m ∣{ X , y∈ E : Y =v }∣m
ahol pi , m a közelítő érték, m egy megfelelően nagy konstans. Ha nincs ilyen közelítő érték, akkor a becslés:
P Ai = x i∣Y =v ≈
∣{ X , y∈ E : Ai =x i , Y = v}∣1 ∣{ X , y∈ E : Y =v }∣{X i lehetséges értékeinek száma Y =v}
Valószínűségi háló •
a gráf csomópontjai (csúcsai) valószínűségi változók
•
a csomópontokat irányított, élekkel kötjük össze
•
feltételes valószínűségeket rendelünk a csúcsokhoz – valószínűségi tábla („szülők hatása”)
•
körmentes a gráf
Pearl példája •
riasztó beszerelése – jelzi a földrengést is
•
két szomszéd: Mária és János, akik telefonálnak, ha szól a riasztó
•
de ◦ a riasztó nem tökéletes ◦ János nem mindig tudja a riasztót a telefontól megkülönböztetni ◦ Mária fülhallgatóval hallgat zenét
A fennálló függőségeket feltételes valószínűségi táblával adjuk meg •
János és Mária nem érzékelik a földrengést és a betörőt, csak a riasztást (egymást sem!)
•
így bizonyos kapcsolatok elhanyagolhatók, azaz csak a tényleges függőségben levők számítanak!
Hálózat
Betörés
Földrengés
Riasztás
János telefonál
Mária telefonál
FVT Betörés Földrengés P(Riasztás | Betörés, Földrengés) Igaz Igaz
Igaz
0.95
Igaz
Hamis
0.95
Hamis
Igaz
0.29
Hamis
Hamis
0.001
•
a táblákat minden csomóponthoz meg kell adni
•
a szülő nélküli csomópontokra ez csak az a priori valószínűségeket jelenti ◦ P(Betörés)=P(B)=0.001 ◦ P(Földrengés)=P(F)=0.002 ◦ P(Riasztás)=P(R) (fenti táblázat)
R Igaz
P(János telefonál)=P(J)
P(Mária telefonál)=P(M)
R
Igaz 0.9
Igaz
Igaz
Hamis 0.05
0.7
Hamis 0.01
Kiszámítás módja
Együttes valószínűségi eloszlásfüggvény n
P x 1, x 2, , x n =
∏ P x ∣Szülők X i
i
i=1
Konkrét példára: P J , M , R , ¬B , ¬F = P J∣R⋅P M ∣R ⋅P R∣¬B , ¬F ⋅P ¬B⋅P ¬F =0.9⋅0.7⋅0.001⋅0.999⋅0.998=0.000628
Nagyon kicsi a valószínűsége tehát annak, hogy János is és Mária is telefonált, volt is riasztás, de nem volt sem földrengés, sem betörés.
Hálók építése •
befolyásoló tényezők, vagyis a változók meghatározása
•
sorrend kijelölése
•
amíg van érintetlen változó ◦ vegyünk egy ilyet, adjuk a csúcsokhoz ◦ határozzuk meg a szüleit ◦ adjuk meg a feltételes valószínűségek tábláját
Hálók tulajdonságai
Mária telefonál János telefonál Riasztás
Betörés
Földrengés
Más struktúra esetén más hatásmechanizmusok munkálnak
•
determinisztikus csomópontok (nincs zaj) ◦ Példa: vagy USA, vagy Kanada, vagy Mexikó - Észak-Amerika
•
nemdeterminisztikus csomópontok (zajos) ◦ Példa: megfázás, influenza, malária – láz ◦ ahol csak egy igaz van, ott nincs zaj, ahol több igaz van, ott már van zaj
Következtetés valószínűségi hálókban Milyen jellegű lekérdezések lehetnek? •
diagnosztikai következtetés ◦ hatásról okra következtetünk ◦ riasztásos példa esetében P (B|J) ◦ azaz, ha adott, hogy János telefonált, akkor kiszámítható, hogy betörés volt-e
•
okozati következtetés ◦ okról hatásra következtetünk ◦ riasztásos példa esetében P(J|B )
•
okok közötti összefüggés
•
kevert
Következtetés többszörösen összekötött hálókban A hálók kezelésére alkalmas algoritmusok •
összevonó eljárás ◦ átalakítják a hálót egy gráffá a nem megfelelő csomópontokat összevonva
•
feltételezéses eljárás ◦ átalakításnál a változók értékét rögzítik, majd kiértékelik a gráfot minden lehetséges értékkombinációra. (szétbontjuk és csinálunk 2 hálót)
•
szimulációs eljárás (sztohasztikus) ◦ tárgytartomány nagyon nagy számú, konkrét modelljét generálják le
Felhős
Felhős
Locsolás + Esik Locsolás
Esik
Vizes pázsit
Összevonó eljárás
Vizes pázsit
