MSI 2006 w3

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

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)

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)

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)

Uogólnione Modus ponens

•

Uogólnione Modus ponens: dla zda« atomowych
p

, p

, i = 1, . . . , n

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

»e ∀i SUBST(θ, p

) = SUBST(θ, p

)

, p

, . . . , p

, (p

∧ p

∧ . . . ∧ p

⇒ 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.

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.

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

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

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.

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.

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(θ

, θ

)

jest podstawieniem, którego skutek jest

identyczny ze skutkiem uzyskanym po kolejnym zastosowaniu
obu podstawie«:

SUBST(COMPOSE(θ

, θ

), p) = SUBST(θ

, SUBST(θ

, p))

Rozumowanie w przód algorytm (1)

procedure

FORWARD-CHAIN(KB, p)

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

then return

Add p to KB

for each

∧ . . . ∧ p

⇒ q)

such that for some i, UNIFY(p

, p) = θ

succeeds

FIND-AND-INFER(KB, [p

, . . . , p

i−1

, p

i+1

, . . . , p

], q, θ)

end

Rozumowanie w przód algorytm (2)

procedure

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

premises = [ ]

then

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

else for each

such that UNIFY(p

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

FIND-AND-INFER(

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

))

end

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.

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

qlist

is empty

then return

{θ}

q ← FIRST(qlist)

for each

such that θ

← UNIFY(q, q

)

succeeds

Add COMPOSE(θ, θ

)

to answers

end
for each

sentence (p

∧ . . . ∧ p

⇒ q

)

such that θ

← UNIFY(q, q

)

succeeds

answers ←

BACK-CHAIN-LIST(

KB, SUBST(θ

, [p

. . . p

]), COMPOSE(θ, θ

))

∪ answers

end

return

θ∈answers

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

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.

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:

KB |= α

then

KB `

Reguªa rozumowania rezolucja

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

, q

, gdzie

UNIFY(p

, ¬q

) = θ

∨ . . . p

. . . ∨ p

∨ . . . q

. . . ∨ q

SUBST(θ, (p

∨ . . . p

j−1

∨ p

j+1

. . . ∨ p

∨ q

∨ . . . q

k−1

∨ q

k+1

. . . ∨ q

))

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

, q

, r

, s

gdzie UNIFY(p

, q

) = θ

∧...p

...∧p

⇒r

∨...∨r

∧...∧s

⇒q

∨...q

...∨q

SUBST(θ,(p

∧...p

j−1

∧p

j+1

...∧p

∧s

∧...∧s

⇒r

∨...∨r

∨q

∨...q

k−1

∨q

k+1

...∨q

))

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 ⇒ β

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

P (w) ⇒ Q(w)

Q(y) ⇒ S(y)

{y/w}

P (w) ⇒ S(w)

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

{w/x}

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

R(z) ⇒ S(z)

{x/A, z/A}

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]

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}

P (w) ⇒ S(w)

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

{w/x}

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

R(z) ⇒ S(z)

{z/x}

T rue ⇒ S(x)

S(A) ⇒ F alse

T rue ⇒ F alse

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

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

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

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

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)

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)

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

F. Cat(x) ⇒ Animal(x)

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}

Owns(x, D) ⇒ AnimalLower(x)

Owns(J ack, D)

{x/J ack}

Cat(T una)

Cat(x) ⇒ Animal(x)

{x/T una}

AnimalLower(J ack)

Animal(T una)

{y/T una}

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

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

{x/J ack}

Kills(Curiosity, T una) ⇒ F alse

{ }

Kills(J ack, T una) ⇒ F alse

Kills(J ack, T una)

{ }

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

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.

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).

Niepewno±¢.

Probabilistyczne systemy

wnioskowania

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

Przyczyny niepewno±ci

•

Niekompletno±¢ reguª w KB

•

Niepoprawno±¢ procesu wnioskowania agenta

•

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

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 . . .

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)

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

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

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)

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

Podstawowe rodzaje prawdopodobie«stwa

•

Prawdopodobie«stwo bezwarunkowe (a priori)

•

Prawdopodobie«stwo warunkowe (a posteriori)

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.

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

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).

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)

Aksjomaty prawdopodobie«stwa

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

≤ 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)

Prawdopodobie«stwo ªaczne (1)

Niech X

, . . . , X

zdania atomowe

P(X

, . . . , X

)

prawdopodobie«stwo ªaczne

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

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

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)

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

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

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

par zmiennych

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)

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%

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

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.

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

Probabilistyczne systemy

wnioskowania

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

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

Przykªad (2)

Burglary

Earthquake

Alarm

JohnCalls

MaryCalls

Burglary

Earthquake

Alarm

JohnCalls

MaryCalls

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

•

kto zadzwoniª?

•

»e dana osoba nie za-
dzwoniªa?

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

Tabela prawdopodobie«stw warunkowych

(przykªad)

Burglary

Earthquake

P (Alarm|Burglary, Earthquake)
True

False

True

0.950

0.050

True

False

0.940

0.060

False

True

0.290

0.710

False

0.001

0.999

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

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

Sie¢ z prawdopodobie«stwami warunkowymi

Burglary

Earthquake

Alarm

JohnCalls

MaryCalls

P(B)

0.001

P(E)

0.002

P(M)

0.70
0.01

T
F

P(J)

0.90
0.05

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

Earthquake

Alarm

JohnCalls

MaryCalls

P(B)

0.001

P(B)

0.001

P(E)

0.002

P(E)

0.002

P(M)

0.70
0.01

T
F

P(M)

0.70
0.01

T
F

P(J)

0.90
0.05

T
F

P(J)

0.90
0.05

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)

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

Wyszukiwarka

Podobne podstrony:
MSI 2006 w3
finanse międzynarodowe w3 (07 03 2006) NOWLRAH4S7UWZBVETF7P2IB2SNCKEWYVHH75G7A
MSI w6 2006 cz1
MSI-w3-konspekt-2010
MSI w3 konspekt 2010
systemy podatkowe w3 ! 03 2006 2UAYDMFEZHADC554EHW5L2VSVJMKFHNVA4WJFJQ
transport i handel morski w3 (08 03 2006) NTHIVERR54UWAZBGZRY3L32JGBIPNAR57Z2HXTI

więcej podobnych podstron