Metody sztucznej inteligencji

 wykªad 3

(dla studentów Wydziaªu MT Politechniki ‘laskiej

- na prawach rekopisu)

23 Marca 2006

Rozumowanie w rachunku
predykatów 1. rzedu

1

Reguªy wnioskowania z u»yciem kwantykatorów

(1)

SUBST(θ, α)

 zastosowanie podstawienia (lub listy wia»acej) θ

do zdania α

Przykªad: SUBST({x/Sam, y/P am}, Likes(x, y)) = Likes(Sam, P am)

•

Uniwersalna eliminacja: dla ka»dego zdania α, zmiennej ν
i termu elementarnego g:

∀ν α

SUBST(

{ν/g}, α)

Np. dla ∀x Likes(x, IceCream) podstawienie {x/Ben} daje
Likes(Ben, IceCream)

2

Reguªy wnioskowania z u»yciem kwantykatorów

(2)

•

Egzystencjalna eliminacja: dla ka»dego zdania α, zmiennej
ν

i staªego symbolu k nie wystepujacego w bazie wiedzy:

∃ν α

SUBST(

{ν/k}, α)

Np. ze zdania ∃x Kill(x, V ictim) mo»na wyprowadzi¢
Kill(M urderer, V ictim)

dopóki tylko staªa Murderer nie wystepuje

w bazie wiedzy.

Uwaga: podstawiana staªa nie mo»e wystepowa¢ w rozpa-

trywanej bazie wiedzy! Inaczej powstaja nonsensowne zda-

nia, np. je±li w zdaniu ∃x F ather(x, John) podstawimy {x/John},

otrzymamy F ather(John, John)

3

Reguªy wnioskowania z u»yciem kwantykatorów

(3)

•

Egzystencjalna introdukcja: dla ka»dego zdania α, zmien-
nej ν nie wystepujacej w zdaniu α i staªego symbolu g nie
wystepujacego w zdaniu α:

α

∃ν SUBST({g/ν}, α)

Np. ze zdania Likes(Ian, IceCream) mo»na wyprowadzi¢
∃x Likes(x, IceCream)

.

4

Uogólnione Modus ponens

•

Uogólnione Modus ponens: dla zda« atomowych
p

i

, p

0

i

, i = 1, . . . , n

, q, dla których istnieje podstawienie θ takie,

»e ∀i SUBST(θ, p

0

i

) = SUBST(θ, p

i

)

:

p

0

1

, p

0

2

, . . . , p

0

n

, (p

1

∧ p

2

∧ . . . ∧ p

n

⇒ q)

SUBST(θ, q)

Wydajna reguªa wnioskowania:

•

Šaczy wiele maªych kroków wnioskowania w jeden krok;

•

Kroki te sa rozsadne  ze wzgledu na u»ycie podstawienia;

•

Poprzez prekompilacje umo»liwia przeksztaªcenie wielu zda«
wystepujacych w bazie wiedzy do ich postaci kanonicznej.

5

Posta¢ kanoniczna

•

Mo»na zbudowa¢ mechanizm wnioskowania bazujacy jedynie
na uogólnionym Modus Ponens;

•

Wszystkie zdania zawarte w KB winny by¢ wówczas w postaci,
która odpowiada jednej z przesªanek reguªy Modus Ponens,
tj. zdanie musi by¢:

 albo zdaniem atomowym,
 albo implikacja, której przesªanka jest koniunkcja zda«

atomowych, a konkluzja jest pojedynczy atom;

•

Zdania takie nazywa sie zdaniami Horna (klauzulami Horna).
O KB zawierajacej jedynie klauzule Horna mówi sie, »e jest
postaci normalnej Horna.

•

Zdania sa przeksztaªcane w zdania Horna z zastosowaniem
reguª: eliminacji egzystencjalnej i eliminacji koniunkcji.

6

Unikacja (1)

•

Procedura unikacji UNIFY dla dwóch zda« atomowych p, q
zwraca podstawienie θ, które spowodowaªoby, »e p, q wygladaªyby
identycznie

UNIFY(p, q) = θ

, gdzie SUBST(θ, p) = SUBST(θ, q)

θ

nazywa sie unikacja dwóch zda«

•

Je±li takie podstawienie nie istnieje, UNIFY zwraca staªa fail

7

Unikacja (2)  Przykªad

•

reguªa Knows(John, x) ⇒ Hates(John, x), chcemy wywnioskowa¢

na podstawie danej KB, kogo to dotyczy

•

w KB sa nastepujace zdania:

Knows(J ohn, J ane)
Knows(y, Leon)
Knows(y, M other(y))
Knows(x, Ellen)

•

Zastosowanie unikacji do poprzednika reguªy i ka»dego zda-

nia daje:

UNIFY(Knows(J ohn, x), Knows(J ohn, J ane)) = {x/J ane}
UNIFY(Knows(J ohn, x), Knows(y, Leon)) = {x/Leon, y/J ohn}
UNIFY(Knows(J ohn, x), Knows(y, M other(y))) =

{y/J ohn, x/M other(John)}

UNIFY(Knows(J ohn, x), Knows(x, Ellen)) = f ail

bo x nie mo»e jednocze±nie przyja¢ warto±ci John i Ellen

8

Rodzaje rozumowania

Rozumowanie w przód (forward chaining): rozpoczyna sie od

zda« zawartych w KB i generuje sie nowe konkluzje za po-
moca reguªy uogólnionegoModus Ponens, które moga by¢
nastepnie zastosowane jako przesªanki w kolejnym kroku rozu-
mowania.

Rozumowanie wstecz (backward chaining): zaczyna sie od zda-

nia, które nale»y dowie±¢, poszukuje sie zdaniaimplikacji,
którego konkluzja jest udowadniane zdanie, a nastepnie próbuje
sie potwierdzi¢ sªuszno±¢ wszystkich zda« tworzacych przesªanke
tej implikacji.

9

Rozumowanie w przód (1)

•

Uruchamiane poprzez dodanie nowego faktu p do bazy KB

•

Poszukiwane sa wszystkie implikacje, w przesªankach których
wystepuje fakt p

•

Je±li dla danej implikacji p ∧ r ∧ . . . ∧ s ⇒ q wiadomo, »e po-
zostaªe zdania r, s, . . . wystepujace w jej przesªance sa prawdziwe,
konkluzja q tej implikacji jest dodawana do KB.

Dodanie tej konkluzji mo»e wywoªa¢ dalsze kroki wnioskowa-
nia.

10

Rozumowanie w przód (2)

Przemianowanie (renaming): zdanie jest przemianowaniem in-

nego zdania, je±li sa one identyczne z wyjatkiem nazw
zmiennych.

Przykªady: ka»de ze zda« Likes(x, IceCream), Likes(y, IceCream)
jest przemianowaniem drugiego z nich; Likes(x, x), Likes(x, y)
nie sa przemianowaniami.

Zªo»enie podstawie« (composition of substitutions):

COMPOSE(θ

1

, θ

2

)

jest podstawieniem, którego skutek jest

identyczny ze skutkiem uzyskanym po kolejnym zastosowaniu
obu podstawie«:

SUBST(COMPOSE(θ

1

, θ

2

), p) = SUBST(θ

2

, SUBST(θ

1

, p))

11

Rozumowanie w przód  algorytm (1)

procedure

FORWARD-CHAIN(KB, p)

if

there is a sentence in KB that is a renaming of p

then return

Add p to KB

for each

(p

1

∧ . . . ∧ p

n

⇒ q)

in

KB

such that for some i, UNIFY(p

i

, p) = θ

succeeds

do

FIND-AND-INFER(KB, [p

1

, . . . , p

i−1

, p

i+1

, . . . , p

n

], q, θ)

end

12

Rozumowanie w przód  algorytm (2)

procedure

FIND-AND-INFER(KB, premises, conclusion, θ)

if

premises = [ ]

then

FORWARD-CHAIN(KB, SUBST(θ, conclusion))

else for each

p

0

in

KB

such that UNIFY(p

0

, SUBST(θ, FIRST(premises))) = θ

2

do

FIND-AND-INFER(

KB, REST(premises), conclusion, COMPOSE(θ, θ

2

))

end

13

Rozumowanie wstecz (1)

•

Stosowane w celu wyszukania wszystkich odpowiedzi na za-

pytanie skierowane do KB (odpowiada funkcji ASK)

•

Wpierw sprawdza sie, czy nie mo»na dostarczy¢ odpowiedzi

bezpo±rednio na podstawie zda« zawartych w KB

•

Nastepnie wyszukuje sie wszystkie implikacje, których kon-

kluzje unikuja sie z zapytaniem skierowanym do KB, i próbuje

sie ustali¢ przesªanki tych implikacji (tak»e za pomoca rozu-

mowania wstecz)

Je±li przesªanka jest koniunkcja, analizuje sie ka»de zdanie

tworzace te koniunkcje, budujac unikator kompletnej przesªanki.

14

Rozumowanie wstecz  algorytm

function

BACK-CHAIN(KB, q)

returns

a set of substitutions

BACK-CHAIN-LIST(KB, [q], { })

function

BACK-CHAIN-LIST(KB, qlist, θ)

returns

a set of substitutions

inputs

: KB, knowledge base

qlist

, a list of conjuncts forming a query (θ already applied)

θ

, the current substitution

local variables

: answers, a set of substitutions, initially empty

if

qlist

is empty

then return

{θ}

q ← FIRST(qlist)

for each

q

0

i

in

KB

such that θ

i

← UNIFY(q, q

0

i

)

succeeds

do

Add COMPOSE(θ, θ

i

)

to answers

end
for each

sentence (p

1

∧ . . . ∧ p

n

⇒ q

0

i

)

in

KB

such that θ

i

← UNIFY(q, q

0

i

)

succeeds

do

answers ←

BACK-CHAIN-LIST(

KB, SUBST(θ

i

, [p

1

. . . p

n

]), COMPOSE(θ, θ

i

))

∪ answers

end

return

S

θ∈answers

BACK-CHAIN-LIST(KB, REST(qlist), θ)

15

Zupeªno±¢ (1)

Rozwa»my baze wiedzy:

∀x P (x)

⇒ Q(x)

∀x ¬P (x) ⇒ R(x)
∀x Q(x)

⇒ S(x)

∀x R(x)

⇒ S(x)

(1)

Z bazy tej mo»na wyprowadzi¢ S(A), gdzie {x/A} jest dowol-
nym podstawieniem. Nie mo»na tego jednak zrobi¢ za pomoca
reguªy Modus Ponens, poniewa» zdania ∀x ¬P (x) ⇒ R(x) nie da
sie przeksztaªci¢ w klauzule Horna. Taka procedura dowodzenia
bazujaca jedynie na Modus Ponens jest wiec niezupeªna.

16

Zupeªno±¢ (2)

Z twierdzenia Gödla o zupeªno±ci wiadomo, »e dla rachunku
predykatów 1. rzedu ka»de zdanie pociagane przez zbiór zda«
mo»e by¢ udowodnione dla tego zbioru, tj. mo»na znale¹¢ reguªy
rozumowania, które umo»liwia utworzenie zupeªnej procedury
dowodzenia R:

if

KB |= α

then

KB `

R

α

17

Reguªa rozumowania  rezolucja

Uogólniona rezolucja (dysjunkcje) CNF: dla zda« p

i

, q

i

, gdzie

UNIFY(p

j

, ¬q

k

) = θ

:

p

1

∨ . . . p

j

. . . ∨ p

m

,

q

1

∨ . . . q

k

. . . ∨ q

n

SUBST(θ, (p

1

∨ . . . p

j−1

∨ p

j+1

. . . ∨ p

m

∨ q

1

∨ . . . q

k−1

∨ q

k+1

. . . ∨ q

n

))

Uogólniona rezolucja (implikacje) INF: dla atomów p

i

, q

i

, r

i

, s

i

,

gdzie UNIFY(p

j

, q

k

) = θ

:

p

1

∧...p

j

...∧p

n1

⇒r

1

∨...∨r

n2

,

s

1

∧...∧s

n3

⇒q

1

∨...q

k

...∨q

n4

SUBST(θ,(p

1

∧...p

j−1

∧p

j+1

...∧p

n1

∧s

1

∧...∧s

n3

⇒r

1

∨...∨r

n2

∨q

1

∨...q

k−1

∨q

k+1

...∨q

n4

))

18

Kanoniczne formy rezolucji

KB z (1) mo»e by¢ przedstawiona jako:

Conjunctive Normal Form
(CNF)

Implicative Normal Form
(INF)

¬P (w) ∨ Q(w)

P (w) ⇒ Q(w)

P (x) ∨ R(x)

T rue ⇒ P (x) ∨ R(x)

¬Q(y) ∨ S(y)

Q(y) ⇒ S(y)

¬R(z) ∨ S(z)

R(z) ⇒ S(z)

Uwaga: Modus Ponens jest szczególnym przypadkiem rezolucji,
bo:

α, α ⇒ β

β

jest równowa»ne

T rue ⇒ α, α ⇒ β

T rue ⇒ β

19

Dowód »e S(A) wynika z KB

P (w) ⇒ Q(w)

Q(y) ⇒ S(y)

{y/w}

b

b

b

b

b

b

b

b

b

b

"

"

"

"

"

"

"

"

"

"

P (w) ⇒ S(w)

T rue ⇒ P (x) ∨ R(x)

{w/x}

b

b

b

b

b

b

b

b

b

b

"

"

"

"

"

"

"

"

"

"

T rue ⇒ S(x) ∨ R(x)

R(z) ⇒ S(z)

{x/A, z/A}

b

b

b

b

b

b

b

b

b

b

"

"

"

"

"

"

"

"

"

"

T rue ⇒ S(A)

Uwaga: prawidªowy wynik jest

T rue ⇒ S(A) ∨ S(A)

,

ale S(A) ∨ S(A) = S(A)

[wg S. Russel, P. Norvig, Articial Intelligence. A modern approach. Prentice Hall, 1995]

20

Dowód nie wprost, »e S(A) wynika z KB

Schemat dowodu nie wprost:

(KB ∧ ¬P ⇒ F alse) ⇔ (KB ⇒ P )

P (w) ⇒ Q(w)

Q(y) ⇒ S(y)

{y/w}

a

a

a

a

a

a

a

a

a

a

!

!

!

!

!

!

!

!

!

!

P (w) ⇒ S(w)

T rue ⇒ P (x) ∨ R(x)

{w/x}

a

a

a

a

a

a

a

a

a

a

!

!

!

!

!

!

!

!

!

!

T rue ⇒ S(x) ∨ R(x)

R(z) ⇒ S(z)

{z/x}

a

a

a

a

a

a

a

a

a

a

!

!

!

!

!

!

!

!

!

!

T rue ⇒ S(x)

S(A) ⇒ F alse

a

a

a

a

a

a

a

a

a

a

!

!

!

!

!

!

!

!

!

!

T rue ⇒ F alse

[wg S. Russel, P. Norvig, Articial Intelligence. A modern approach. Prentice Hall, 1995]

21

Konwersja do postaci normalnej (1)

1. Eliminuj implikacje:
p ⇒ q ≡ ¬p ∨ q

3. Standardyzuj zmienne: dla
zda« typu (∀x P (x)) ∨ (∃x Q(x))
w których ta sama zmienna jest
u»yta dwukrotnie, zmie« nazwe
jednej ze zmiennych

2.

Przemie±¢ negacje do

wewnatrz:
¬(p ∨ q) ≡ ¬p ∧ ¬q
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬∀x p ≡ ∃x ¬p
¬∃x p ≡ ∀x ¬p
¬¬p ≡ p

4. Przemie±¢ kwantykatory
w lewo: np. je±li p nie zawiera
zmiennej x, przeksztaª¢ p ∨ ∀x q
w ∀x p ∨ q

22

Konwersja do postaci normalnej (2)

5. Skolemizuj: wyeliminuj kwanty-
katory ∃, np. zastap ∃x P (x) przez
P (A)

(A  staªa nie wystepujaca

dotychczas w KB) lub wprowad¹
funkcje skolemizujaca, np. zdanie
∀x

P erson(x)

⇒

∃y

Heart(y) ∧

Has(x, y)

(ka»dy

ma

serce)

przeksztaª¢ na ∀x P erson(x) ⇒
Heart(F (x)) ∧ Has(x, F (x))

7. Usu« zagnie»d»one ko-
niunkcje i dysjunkcje: np.
(a ∨ b) ∨ c

staje sie (a ∨ b ∨ c),

(a ∧ b) ∧ c

staje sie (a ∧ b ∧ c)

6. Rozdziel ∧ wzgledem ∨: np.
(a ∧ b) ∨ c

staje sie

(a ∨ c) ∧ (b ∨ c)

8. Przeksztaª¢ dysjunkcje
na implikacje:

zgromad¹

wpierw wszystkie zanegowane
literaªy obok siebie, np. (¬a ∨
¬b∨c∨d)

staje sie (a∧b ⇒ c∨d)

23

Przykªadowy dowód (1)

Jack owns a dog.

Every dog owner is an animal lover.

No animal lover kills an animal.

Either Jack or Curiosity killed the cat, who is named Tuna.

Did Curiosity kill the cat?
Oryginalna KB

KB w postaci INF

A. ∃x Dog(x) ∧ Owns(Jack, x)

A1. Dog(D)

A2. Owns(Jack, D)

B. ∀x (∃y Dog(y) ∧ Owns(x, y)) ⇒

AnimalLover(x)

B. Dog(y) ∧ Owns(x, y)

⇒

AnimalLover(x)

C. ∀x

AnimalLover(x)

⇒

(

∀y Animal(y) ⇒ ¬Kills(x, y))

C. AnimalLover(x) ∧ Animal(y) ∧

Kills(x, y) ⇒ F alse

D. Kills(Jack, T una)

∨

Kills(Curiosity, T una)

D. Kills(Jack, T una)

∨

Kills(Curiosity, T una)

E. Cat(T una)

E. Cat(T una)

F. ∀x Cat(x) ⇒ Animal(x)

F. Cat(x) ⇒ Animal(x)

24

Przykªadowy dowód Who killed the cat? (2)

Dog(D) Dog(y) ∧ Owns(x, y) ⇒ AnimalLower(x) AnimalLower(x) ∧ Animal(y) ∧ Kills(x, y) ⇒ F alse

{y/D}

a

a

a

a

a

a

a

a

!

!

!

!

!

!

!

!

L

L

L

L

L

L

L

L

L

L

L

L

L

L

L

Owns(x, D) ⇒ AnimalLower(x)

Owns(J ack, D)

{x/J ack}

a

a

a

a

a

a

a

a

!

!

!

!

!

!

!

!

Cat(T una)

Cat(x) ⇒ Animal(x)

{x/T una}

a

a

a

a

a

a

a

a

!

!

!

!

!

!

!

!

AnimalLower(J ack)

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

Animal(T una)

!

!

!

!

!

!

!

!

{y/T una}

Kills(J ack, T una) ∨ Kills(Curiosity, T una)

L

L

L

L

L

L

L

L

L

AnimalLower(x) ∧ Kills(x, T una) ⇒ F alse

!

!

!

!

!

!

!

!

{x/J ack}

Kills(Curiosity, T una) ⇒ F alse

a

a

a

a

a

a

a

a

{ }

Kills(J ack, T una) ⇒ F alse

Kills(J ack, T una)

a

a

a

a

a

a

a

a

{ }

F alse

[wg S. Russel, P. Norvig,

Articial Intelligence.

A modern approach.

Prentice Hall, 1995]

Pytanie do KB: ∃w Kills(w, T una).

Do KB dodaje sie podstawienia negacji

tego zdania: Kills(w, T una) ⇒ F alse

25

Rozumowanie w rach. predykatów  podsumowanie

(1)

•

Rachunek ten umo»liwia konstruowanie dowodów prawdzi-
wo±ci zda« zawartych w danej KB.

•

Unikacja w celu identykacji odpowiednich podstawie« umo»li-
wia bardziej efektywne dowodzenie.

•

Uogólnione Modus Ponens stosuje unikacje; jest ono
naturalna i mocna reguªa rozumowania zarówno w przód, jak
i wstecz.

26

Rozumowanie w rach. predykatów  podsumowanie

(2)

•

Forma kanoniczna dla Modus Ponens jest formuªa Horna. Nie
da sie za jej pomoca reprezentowa¢ wszystkich zda«, dlatego
Modus Ponens nie jest zupeªnym systemem dowodzenia.

•

Uogólniona rezolucja jest reguªa rozumowania, tworzaca zu-
peªny system dowodu nie wprost. Wymaga to zapisu zda«
w postaci normalnej, do której ka»de zdanie daje sie przek-
sztaªci¢.

•

Rezolucja mo»e by¢ stosowana albo w formie CNF (ka»de
zdanie jest dysjunkcja literaªów), albo w formie INF (ka»de
zdanie jest w formie implikacji, której poprzednik jest
koniunkcja atomów, a nastepnik jest dysjunkcja atomów).

27

Niepewno±¢.

Probabilistyczne systemy

wnioskowania

28

Problemy ze stosowaniem logiki 1. rzedu

•

Agent prawie nigdy nie ma dostepu do peªnej prawdy o jego
±rodowisku

•

Niektóre zdania sa wprost wynikiem percepcji agenta, pod-
czas gdy inne moga by¢ wyprowadzone na podstawie wiedzy
o ±rodowisku agenta oraz obecnych i poprzednich wyników
jego percepcji

•

Dziaªanie agenta jest obarczone niepewno±cia

29

Przyczyny niepewno±ci

•

Niekompletno±¢ reguª w KB

•

Niepoprawno±¢ procesu wnioskowania agenta

•

Zbyt du»a liczba przesªanek, warunków (ogranicze«)

30

Przykªady konkluzji

•

Nierealizowalna:
Plan90 pozwala na dotarcie samochodem na lotnisko na czas

•

Sªabsza (realizowalna):
Plan90 pozwala na dotarcie na lotnisko na czas, pod warun-
kiem, »e samochód bedzie zatankowany, nie wydarzy sie wypa-
dek, nie bedzie wypadków na mo±cie, samolot nie odleci
wcze±niej, nie bedzie trzesienia ziemi . . .

31

Wiedza niepewna

Przykªadem dziedziny zwiazanej z dziaªaniami na wiedzy niepewnej

jest diagnostyka

Niesko«czony zbiór reguª:

∀pSymptom(p, T oothache) ⇒ Disease(p, Cavity)

∀pSymptom(p, T oothache) ⇒

Disease(p, GumDisease) ∨ Disease(p, ImpactedW isdom)

Reguªa przyczynowa:

∀pDisease(p, Cavity) ⇒ Symptom(p, T oothache)

32

Dlaczego logika 1. rzedu nie wystarcza?

Lenistwo  skompletowanie peªnej listy mo»liwych reguª wymaga

za du»o pracy i za du»o czasu

Nieznajomo±¢ teorii  np. medycyna nie zna wytªumaczenia

powodów wszystkich schorze«

Nieznajomo±¢ praktyki  nawet je»eli znamy wszystkie reguªy,

nie mo»emy by¢ pewni czy w przypadku konkretnego pa-
cjenta okre±lone reguªy sa poprawne

33

Wiedza agenta zawarta w KB

•

Jest niepewna

•

Charakteryzuje sie stopniem przekonania (w okre±lonych re-
guªach)

•

Mo»na na niej dziaªa¢ stosujac np. aparat teorii prawdopo-
dobie«stwa

34

Teoria prawdopodobie«stwa w reprezentacji

wiedzy

•

Pozwala na sumowanie niepewno±ci wynikajacej z wielu przy-
czyn

•

Prawdopodobie«stwo 0.8 oznacza 80% przekonania o prawdzi-
wo±ci zdania (stwierdzenia)

•

Prawdopodobie«stwo nie oznacza stopnia prawdziwo±ci zda-
nia (stwierdzenia)

35

Niepewne i racjonalne decyzje

Plany agenta

Plan90 Plan120

Plan1440

Który jest najbardziej racjonalny?

Agent w tej sytuacji:

•

wybiera

•

posªuguje sie teoria u»yteczno±ci

Teoria decyzji = Teoria prawdopodobie«stwa + Teoria u»ytecznosci

36

Podstawowe rodzaje prawdopodobie«stwa

•

Prawdopodobie«stwo bezwarunkowe (a priori)

•

Prawdopodobie«stwo warunkowe (a posteriori)

37

Prawdopodobie«stwo a priori (1)

Prawdopodobie«stwo a priori P (A) zdarzenia A

P (Cavity) = 0.1

oznacza, »e w przypadku braku innych informacji zostanie posta-
wiona diagnoza, »e z prawdopodobie«stwem 10 % pacjent ma
ubytek.

Prawdopodobie«stwo P(A) mo»e by¢ stosowane wyªacznie w
przypadku, gdy nie ma dodatkowych informacji.

38

Prawdopodobie«stwo a priori (2)

•

W zdaniu okre±lajacym prawdopodobie«stwo P (A) zdarzenie
mo»e reprezentowa¢ symbol

•

Zdarzenia mo»na zapisywa¢ z zastosowaniem zmiennych loso-
wych:

P (W eather = sunny) = 0.7

P (W eather = rain) = 0.2

P (W eather = cloudy) = 0.08

P (W eather = snow) = 0.02

39

Prawdopodobie«stwo a posteriori (1)

Prawdopodobie«stwo warunkowe

P (Cavity|T oothache) = 0.8

Je»eli u pacjenta zaobserwowano ból zeba i nie ma innych infor-
macji to na 80% pacjent ma ubytek.

P (A|B)

mo»e by¢ stosowane wyªacznie wtedy, gdy znane jest

tylko B. Gdy znamy C, trzeba obliczy¢ P (A|B ∧ C).

40

Prawdopodobie«stwo a posteriori (2)

P (A|B) =

P (A ∧ B)

P (B)

(2)

Posta¢ iloczynowa:

P (A ∧ B) = P (A|B)P (B)

(3)

P (A ∧ B) = P (B|A)P (A)

(4)

41

Aksjomaty prawdopodobie«stwa

1. Warto±ci prawdopodobie«stwa zawieraja sie w granicach < 0, 1 >:

0

≤ P (A) ≤ 1

(5)

2. Prawdopodobie«stwo zdarzenia pewnego i caªkowicie niepewnego:

P (T rue) = 1 P (F alse) = 0

(6)

3. Prawdopodobie«stwo dysjunkcji (alternatywy):

P (A ∨ B) = P (A) + P (B) − P (A ∧ B)

(7)

42

Prawdopodobie«stwo ªaczne (1)

Niech X

1

, . . . , X

n

 zdania atomowe

P(X

1

, . . . , X

n

)

 prawdopodobie«stwo ªaczne

Oznacza rozkªad prawdopodobie«stwa zdarzenia wszystkich zda«
atomowych

43

Prawdopodobie«stwo ªaczne (2)

T oothache

¬T oothache

Cavity

0.04

0.06

¬Cavity

0.01

0.89

P(Cavity) = 0.06 + 0.04 = 0.10

P(Cavity ∨ T oothache) = 0.04 + 0.01 + 0.06 = 0.11

P(Cavity|T oothache) =

P(Cavity ∧ T oothache)

P(T oothache)

=

0.04

0.04 + 0.01

= 0.80

44

Twierdzenie Bayesa

P(A ∧ B) = P(A|B)P(B)

(8)

P(A ∧ B) = P(B|A)P(A)

(9)

P(B|A) =

P(A|B)P(B)

P(A)

(10)

45

Zastosowanie twierdzenia Bayesa

P(S|M ) = 0.5
P(M ) = 1/50000

Zapalenie opon mózgowych

P(S) = 1/20

Sztywno±¢ karku

P(M |S) =

P(S|M )P(M )

P(S)

=

0.5×1/50000

1/20

= 0.0002

46

Normalizacja

P(M |S) =

P(S|M )P(M )

P(S)

P(W |S) =

P(S|W )P(W )

P(S)

P(S|W ) = 0.8

P(W ) = 1/1000

P(S|M ) = 0.5

P(M ) = 1/50000

Wzgledna wiarygodno±¢:

P(M |S)

P(W |S)

=

P(S|M )P(M )

P(S|W )P(W )

=

0.5×1/50000

0.8×1/1000

=

1

80

47

Šaczenie dowodów (1)

Dane:

P(Z|X) , P(Z|Y )

Oblicz:

P(Z|X ∧ Y )

Z twierdzenia Bayesa:

P(Z|X ∧ Y ) =

P(X ∧ Y |Z)P(Z)

P(X ∧ Y )

Gdy Z jest bezpo±rednia przyczyna X, Y , to:

P(Y |Z ∧ X) = P(Y |Z); P(X|Z ∧ Y ) = P (X|Z)

czyli warunkowa niezale»no±¢ X, Y je±li dane Z

Wada: Trzeba zna¢ prawdopodobie«stwa dla n

2

par zmiennych

48

Šaczenie dowodów (2)

P(Z|X ∧ Y ) = P(Z|Y )

P(Y |X ∧ Z)

P(Y |X)

= P(Z)

P(X|Z)

P(X)

P(Y |Z)

P(Y |X)

= αP(X|Z)P(Y |Z)

49

Skad wzia¢ warto±ci prawdopodobie«stw?

Podej±cie czesto±ciowe: na podstawie eksperymentu

Podej±cie obiektywistyczne: okre±lone dla uniwersum

Podej±cie subiektywistyczne: reprezentuja przekonania eksper-

ta/agenta: Moim zdaniem, spodziewam sie »e prawdopodo-
bie«stwo awarii bedzie 10%

50

Podsumowanie (1)

•

Rzeczywiste ±wiaty charakteryzuje niepewno±¢

•

Prawdopodobie«stwo wyra»a niemo»liwo±¢ podjecia przez agenta
jednoznacznej decyzji dotyczacej prawdziwo±ci zdania, oraz
sumuje jego przekonania

•

Podstawowe zdania zawieraja prawdopodobie«stwa a priori i
a posteriori

51

Podsumowanie (2)

•

Aksjomaty prawdopodobie«stwa stanowia ograniczenia w sto-
sunku do przypisywania prawdopodobie«stwa do zdarze«

•

Šaczny rozkªad prawdopodobie«stwa okre±la prawdopodo-
bie«stwo ka»dej kombinacji warto±ci zmiennych losowych.
Wielo±¢ kombinacji powoduje, »e nie stosuje sie go w prak-
tyce.

52

Podsumowanie (3)

•

Reguªa Bayesa umo»liwia obliczenie nieznanych prawdopodo-
bie«stw na podstawie znanych prawdopodobie«stw

•

Warunkowa niezale»no±¢ zdarze« uªatwia ªaczenie ró»nych
niezale»nych dowodów

53

Probabilistyczne systemy

wnioskowania

54

Sie¢ przekona« (Belief network)

•

Zbiór zmiennych losowych (wezªy sieci)

•

Zbiór zorientowanych krawedzi (podaja, która zmienna ma
bezpo±redni wpªyw na inna)

•

Tablica prawdopodobie«stw warunkowych (okre±la wpªyw ro-
dziców na wezeª)

•

Graf skierowany, acykliczny

55

Przykªad (1)

•

W domu zainstalowano alarm przeciwwªamaniowy:

 dziaªa prawie niezawodnie przy wªamaniach

 reaguje na sªabe wstrzasy tektoniczne

•

Sasiedzi dzwonia do pracy, gdy usªysza alarm:

 John dzwoni zawsze, lecz czasem myli alarm z d¹wiekiem

telefonu i dzwoni niepotrzebnie

 Mary sªucha gªo±nej muzyki i czasem nie sªyszy alarmu

56

Przykªad (2)

Burglary

Earthquake

Alarm

JohnCalls

MaryCalls

Burglary

Burglary

Earthquake

Earthquake

Alarm

JohnCalls

JohnCalls

MaryCalls

MaryCalls

Jakie jest prawdopodobie«-
stwo wªamania, je±li wiado-
mo:

•

kto zadzwoniª?

•

»e dana osoba nie za-
dzwoniªa?

57

Wªasno±ci sieci przekona«

•

Topologia sieci reprezentuje generalna strukture zwi¡zków
przyczynowych w danej dziedzinie

•

Sie¢ przekona« mo»e by¢ interpretowana jako abstrakcyjna
baza wiedzy

•

Brak w niej nieistotnych zwiazków; zwiazki nieistotne
sa uwzglednione w warto±ciach prawdopodobie«stw warun-
kowych podanych dla ka»dego wezªa

58

Tabela prawdopodobie«stw warunkowych

(przykªad)

Burglary

Earthquake

P (Alarm|Burglary, Earthquake)
True

False

True

True

0.950

0.050

True

False

0.940

0.060

False

True

0.290

0.710

False

False

0.001

0.999

Tabela dla wezªa Alarm, wiersze sumuja sie do 1.0

59

Semantyka sieci przekona«

Sie¢ mo»e by¢ rozpatrywana jako reprezentacja ªacznego rozkªadu
prawdopodobie«stwa,

lub

Sie¢ mo»e by¢ zastosowana do zakodowania prawdopodobie«stw
warunkowych

60

Sie¢ z prawdopodobie«stwami warunkowymi

Burglary

Earthquake

Alarm

JohnCalls

MaryCalls

P(B)

0.001

P(E)

0.002

P(M)

0.70
0.01

A

T
F

P(J)

0.90
0.05

A

T
F

P(A)

0.95
0.94
0.29
0.001

B E
T T
T F
F T
F F

Burglary

Earthquake

Alarm

JohnCalls

MaryCalls

Burglary

Burglary

Earthquake

Earthquake

Alarm

JohnCalls

JohnCalls

MaryCalls

MaryCalls

P(B)

0.001

P(B)

P(B)

0.001

0.001

P(E)

0.002

P(E)

P(E)

0.002

0.002

P(M)

0.70
0.01

A

T
F

P(M)

P(M)

0.70
0.01

0.70
0.01

A

T
F

A

A

T
F

T
F

P(J)

0.90
0.05

A

T
F

P(J)

P(J)

0.90
0.05

0.90
0.05

A

T
F

A

A

T
F

T
F

P(A)

0.95
0.94
0.29
0.001

B E
T T
T F
F T
F F

P(A)

0.95
0.94
0.29
0.001

P(A)

P(A)

0.95
0.94
0.29
0.001

0.95
0.94
0.29
0.001

B E
T T
T F
F T
F F

B E

B E
T T
T F
F T
F F

T T
T F
F T
F F

61