Metody sztucznej inteligencji
wykªad 2
(dla studentów Wydziaªu MT Politechniki l askiej
- na prawach r ekopisu)
09 Marca 2006
Metody sztucznej inteligencji
wykªad 2
(dla studentów Wydziaªu MT Politechniki l askiej
- na prawach r ekopisu)
09 Marca 2006
Rozwi azywanie problemów przez
przeszukiwanie
1
Kroki konieczne przy rozwi azywaniu problemu
•
Sformuªowanie celu
•
Okre±lenie dziaªa« powoduj acych przej±cie pomi edzy poszczegól-
nymi stanami
•
Sformuªowanie problemu
•
Poszukiwanie rozwi azania
•
Wykonanie sekwencji dziaªa« b ed acej rozwi azaniem prob-
lemu
2
Problem dobrze okre±lony
•
Stan pocz atkowy
•
Zbiór mo»liwych dziaªa«, które s a dost epne dla agenta
•
Test osi agni ecia celu
•
Sposób wyboru rozwi aza« bardziej preferowanych
3
Przykªad - mapa Rumunii
4
Przykªad - ªamigªówka
5
Przykªad - wymiar problemu
6
Przykªad - kryptoarytmetyka
Stany: ukªadanka w której niektóre litery
zast apiono cyframi
Operatory: zast ap wszystkie wyst apienia
danej
litery
cyfr a
jeszcze
nie
wyst epuj ac a w ukªadance
Test celu: same cyfry, suma poprawna
Koszt ±cie»ki: 0
FORTY
+ TEN
+ TEN
-
SIXTY
7
Misjonarze i kanibale
•
Stany: trzech misjonarzy, trzech kanibali, ªódka (3,3,1)
•
Operatory: z jednego brzegu mo»na zabra¢ (zamiast 27 - 5):
dwóch misjonarzy
dwóch misjonarzy i jednego kanibala
dwóch kanibali
jednego kanibala i jednego misjonarza
jednego kanibala
jednego misjonarza
8
Problemy ±wiata rzeczywistego
•
Znajdowanie drogi
•
Problem komiwoja»era
•
Sterowanie robotem
•
. . .
9
Poszukiwanie rozwi aza«
•
Polega na przeszukiwaniu przestrzeni stanów
•
Idea polega na odnalezieniu i rozszerzeniu zbioru sek-
wencji rozwi aza« cz e±ciowych
10
Generowanie sekwencji dziaªa«
•
Zbadaj, czy stan wyj±ciowy nie jest docelowy
•
Wygeneruj nowy zbiór stanów, stosuj ac operatory do bie» acego
stanu (rozwijanie stanu)
•
Wybierz stan, który nale»y rozwija¢ jako nast epny (okre±la
to STRATEGIA PRZESZUKIWANIA)
11
Drzewo przeszukiwania
•
w ezeª przeszuki-
wania odpowiada
danemu stanowi
•
li±¢
drzewa
odpowiada
stanowi, który:
albo
nie
zostaª
jeszcze
rozwini ety
albo w wyniku
rozwini ecia
daje
pusty
zbiór stanów
12
Kryteria oceny strategii przeszukiwania
•
Kompletno±¢
•
Zªo»ono±¢ czasowa
•
Zªo»ono±¢ pami eciowa
•
Optymalno±¢
13
Ogólny podziaª strategii przeszukiwania
•
Przeszukiwanie ±lepe
•
Przeszukiwanie heurystyczne - z wykorzystaniem dodatkowej
informacji
14
Sposoby przeszukiwania ±lepego
•
Wszerz (breadth- rst search)
•
Z jednolitym kosztem (uniform cost search)
•
W gª ab (depth- rst search)
•
O ograniczonej gª eboko±ci (depth-limited search)
•
Z iteracyjnym pogª ebianiem (iterative deepening search)
•
Dwukierunkowe (bidirectional search)
15
Przeszukiwanie wszerz
16
Przeszukiwanie z jednolitym kosztem
17
Przeszukiwanie w gª ab
18
Przeszukiwanie o ograniczonej gª eboko±ci
Mody kacja przeszukiwania w gª ab (narzucenie ograniczenia na
max gª eboko±¢ ±cie»ki):
•
specjalny algorytm o ograniczonej gª eboko±ci szukania
•
zmody kowane operatory szukania
19
Przeszukiwanie z iteracyjnym pogª ebianiem
20
Przeszukiwanie dwukierunkowe
21
Porównanie strategii przeszukiwania
b
- liczba gaª ezi; d - gª eboko±¢ rozwi azania; m - max gª eboko±¢ drzewa; l -
ograniczenie gª eboko±ci
22
Podsumowanie
•
Do okre±lenia problemu potrzebne s a:
stan pocz atkowy, operatory, cel, przestrze« stanów, ±cie»ki
przeszukiwania
•
Problem dobrze okre±lony
•
Poszukiwanie rozwi aza«
•
Strategie przeszukiwania:
wszerz, wszerz z jednolitym kosztem, w gª ab, o ograniczonej
gª eboko±ci, z iteracyjnym pogª ebianiem, dwukierunkowe, ze
speªnianiem ogranicze«
23
Rozumowanie w rachunku zda«
i rachunku predykatów
24
Rachunek zda«: Skªadnia
1. Symbole:
•
staªe True, False
•
symbole zdaniowe P, Q, . . .
•
ª aczniki (spójniki) logiczne ∧, ∨, ⇔, ⇒ (operatory dwuargu-
mentowe)
•
operator jednoargumentowy ¬
•
nawiasy (, )
25
Rachunek zda«: Skªadnia
2. Reguªy tworzenia zda«:
•
staªe True, False s a zdaniami
•
symbol zdaniowy P, Q, . . . jest zdaniem
•
zdanie otoczone nawiasami jest zdaniem, np. (P )
•
zdanie zanegowane jest zdaniem, np. ¬P
•
zdania mo»na budowa¢, ª acz ac inne zdania
spójnikami logicznymi ∧, ∨, ⇔, ⇒
26
Rachunek zda«: Gramatyka BNF
Zdanie → ZdanieAtomowe | ZdanieZlozone
(1)
ZdanieAtomowe →
True
|
False
(2)
|
P | Q | R | . . .
(3)
ZdanieZlozone → ( Zdanie )
(4)
|
Zdanie Spojnik Zdanie
(5)
|
¬Zdanie
(6)
Spojnik → ∧ | ∨ | ⇔ | ⇒
(7)
Priorytet operatorów: ¬, ∧, ∨, ⇒, ⇔
27
Rachunek zda«: Semantyka
1. Znaczenie zda«:
•
Symbol zdaniowy mo»e oznacza¢ jakikolwiek fakt
•
Znaczenie zdania zªo»onego wyprowadza si e ze znacze« jego
cz e±ci skªadowych
28
Rachunek zda«: Semantyka
2. Warto±¢ logiczna zda« zªo»onych:
P
Q
¬P
P ∧ Q
P ∨ Q
P ⇒ Q
P ⇔ Q
F alse
F alse
T rue
F alse
F alse
T rue
T rue
F alse
T rue
T rue
F alse
T rue
T rue
F alse
T rue
F alse
F alse
F alse
T rue
F alse
F alse
T rue
T rue
F alse
T rue
T rue
T rue
T rue
Uwaga: klasyczny rachunek zda« nie wymaga aby pomi edzy
poprzednikiem i nast epnikiem implikacji zachodziªa przyczynowo±¢
lub co najmniej odpowiednio±¢ (relewantno±¢)
5 jest nieparzyste ⇒ Tokio jest stolic a Japonii jest prawdziwe
w rachunku zda«!!!
29
Rachunek zda«: Walidacja (ocena prawdzi-
wo±ci)
Wyra»enie W jest tautologi a rachunku zda« wtedy i tylko wtedy,
gdy przy ka»dym podstawieniu staªych za zmienne przechodzi w
zdanie prawdziwe
Czy zdanie ((P ∨ H) ∧ ¬H) ⇒ P jest zawsze prawdziwe?
P
H
P ∨ H
¬H
(P ∨ H) ∧ ¬H)
((P ∨ H) ∧ ¬H) ⇒ P
F alse
F alse
F alse
T rue
F alse
T rue
F alse
T rue
T rue
F alse
F alse
T rue
T rue
F alse
T rue
T rue
T rue
T rue
T rue
T rue
T rue
F alse
F alse
T rue
30
Reguªy wnioskowania w rachunku zda«:
Dlaczego warto je stosowa¢?
Zamiast wykazywa¢ sªuszno±¢ za pomoc a rachunku zda« (tj.
analizuj ac tabelki jak poprzednio) , mo»na stosowa¢ reguªy wnioskowa-
nia
Reguªy wnioskowania s a wzorcami sposobu wnioskowania
Notacja:
je»eli α mo»e by¢ wyprowadzone z β przez wnioskowanie, to
odpowiednie schematy wnioskowania zapisuje si e jako:
α ` β
lub
α
β
31
Reguªy wnioskowania w rachunku zda«
•
Eliminacja implikacji
(Modus ponens)
α ⇒ β, α
β
•
Eliminacja koniunkcji
α
1
∧ α
2
∧ ... ∧ α
n
α
i
•
Wprowadzenie koniunkcji
α
1
, α
2
, ... α
n
α
1
∧ α
2
∧ ... ∧ α
n
•
Wprowadzenie dysjunkcji
α
i
α
1
∨ α
2
∨ ... ∨ α
n
•
Eliminacja podwójnej ne-
gacji
¬ ¬ α
α
•
Jednostkowa rezolucja
α ∨ β, ¬β
α
•
Rezolucja
α ∨ β, ¬β ∨γ
α ∨ γ
lub
¬α ⇒ β, β ⇒ γ
¬α ⇒ γ
32
Monotoniczno±¢ rachunku zda«
Rachunek zda« jest monotoniczny:
Je±li KB
1
|= α
, to KB
1
∪ KB
2
|= α
Ogólnie, logika jest monotoniczna, je±li po dodaniu do bazy
wiedzy nowych zda« wszystkie zdania implikowane przez orygi-
naln a baz e wiedzy s a nadal implikowane przez uzupeªnion a baz e
wiedzy.
33
Rachunek predykatów: Zaªo»enia
•
±wiat tworz a obiekty, posiadaj ace wªasno±ci odró»niaj ace je
od innych obiektów
•
pomi edzy obiektami zachodz a relacje
•
niektóre relacje s a funkcjami (maj a tylko jedn a warto±¢ dla
danej zmiennej)
34
Rachunek predykatów: Przykªad
Jeden plus dwa równa si e trzy
•
obiekty: jeden, dwa, trzy, jeden plus dwa
•
relacja: równa si e
•
funkcja: plus
35
Rachunek predykatów: Skªadnia BNF
Zdanie
→
ZdanieAtomowe
(1)
|
Zdanie Spojnik Zdanie
(2)
|
Kwantyf ikator Zmienna, . . . Zdanie
(3)
|
¬Zdanie
(4)
|
( Zdanie )
(5)
ZdanieAtomowe
→
P redykat(T erm, . . .) | T erm = T erm
(6)
T erm
→
F unkcja(T erm, . . .)
(7)
|
Stala
(8)
|
Zmienna
(9)
Spojnik
→
⇒ | ∧ | ∨ | ⇔
(10)
Kwantyf ikator
→
∀ | ∃
(11)
Stala
→
A | X
1
| Jan | · · ·
(12)
P redykat
→
P rzed | M aKolor | · · ·
(13)
F unkcja
→
M atka | LewaN oga | · · ·
(14)
36
Rachunek predykatów: Semantyka (1)
staªe: interpretacja musi okre±li¢, który obiekt ±wiata odnosi si e
do którego symbolu
predykaty: interpretacja okre±la, które symbole predykatów dotycz a
specy cznych relacji w modelu
term: wyra»enie logiczne, odnosz ace si e do obiektu,
np. LewaNoga(Jan)
zdania atomowe: sªu» a do wyra»ania faktów;
konwencja: P (x, y) oznacza "x jest P y"
zdania zªo»one: zdania atomowe poª aczone spójnikami
np. Brat(P iotr, Jan) ∧ Brat(Jan, P iotr)
37
Rachunek predykatów: Semantyka (2)
kwanty katory: do wyra»ania wªasno±ci zbiorów obiektów
•
kwanty kator ogólny
∀
∀ x Kot(x) ⇒ Ssak(x)
zdanie jest prawdziwe, je±li jest prawdziwe dla wszystkich
podstawie« zmiennej x
•
kwanty kator szczególny (szczegóªowy)
∃
np. Burek ma siostr e, która jest psem
∃ x Siostra(x, Burek) ∧ P ies(x)
zdanie jest prawdziwe, je±li jest prawdziwe dla co najmniej
jednego podstawienia zmiennej x
38
Zagnie»d»one kwanty katory
∀ x ∃ y Kocha(x, y)
Everybody loves somebody
∃ y ∀ x Kocha(x, y)
There is someone who is loved by everyone
∃ x ∀ y Kocha(x, y)
There is someone who loves everyone
39
Zagnie»d»one kwanty katory
∀ x ∃ y Kocha(x, y)
Everybody loves somebody
∃ y ∀ x Kocha(x, y)
There is someone who is loved by everyone
∃ x ∀ y Kocha(x, y)
There is someone who loves everyone
40
Prawa De Morgana
Dla kwanty katorów:
∀ x ¬ P
≡ ¬ ∃ x P
¬ ∀ x P
≡ ∃ x ¬ P
∀ x P
≡ ¬ ∃ x ¬ P
∃ x P
≡ ¬ ∀ x ¬ P
Dla zda«:
¬ P ∧ ¬ Q ≡ ¬ (P ∨ Q)
¬ (P ∧ Q) ≡ ¬ P ∨ ¬ Q
P ∧ Q ≡ ¬ (¬ P ∨ ¬ Q)
P ∨ Q ≡ ¬ (¬ P ∧ ¬ Q)
41
Rachunek predykatów: Równo±¢
•
umo»liwia tworzenie zda« atomowych poprzez wskazanie, »e
dwa termy dotycz a tego samego obiektu
np. Ojciec(Jan) = P iotr
•
mo»e by¢ stosowana do opisania wªasno±ci funkcji, a tak»e
do rozró»niania obiektów
np. Zosia ma co najmniej dwie siostry
∃ x, y Siostra(Zosia, x) ∧ Siostra(Zosia, y) ∧ ¬(x = y)
42
Konstruowanie bazy wiedzy
43
Konstruowanie bazy wiedzy: Wa»niejsze poj ecia
In»ynieria wiedzy: proces konstruowania bazy wiedzy; szerzej
nauka o metodach i ±rodkach stosowanych w tym celu.
In»ynier wiedzy: osoba, która bada dan a dziedzin e wiedzy, okre±la
które poj ecia wyst epuj ace w tej dziedzinie s a istotne, oraz
tworzy dla tej dziedziny formaln a reprezentacj e obiektów i
relacji wyst epuj acych pomi edzy tymi obiektami.
Uwaga: In»ynier wiedzy nie jest zwykle ekspertem w tej
dziedzinie, z której wiedz e pozyskuje, winien mie¢ natomiast
co najmniej minimaln a orientacj e w problemach tej dziedziny
oraz by¢ specjalist a w zakresie in»ynierii wiedzy!!!
Pozyskiwanie wiedzy: proces (który mo»e w szczególno±ci by¢
realizowany przez in»yniera wiedzy), którego celem jest wydoby-
cie (lub ujawnienie) wiedzy (a tak»e do±wiadczenia) z danej
dziedziny w wymaganym zakresie oraz zapisanie jej w danej
bazie wiedzy za pomoc a formalnych ±rodków reprezentacji.
44
In»ynieria wiedzy a programowanie
In»ynieria wiedzy
Programowanie
Wybór j ezyka reprezentacji
Wybór j ezyka programowania
Budowa bazy wiedzy
Napisanie programu
Implementacja teorii
dowodzenia
Wybór lub napisanie
kompilatora
Wywiedzenie nowych stwierdze« Uruchamianie programu
45
Metodyka in»ynierii wiedzy
1. Zdecyduj o czym ma by¢ mowa. Staraj si e zrozumie¢
dziedzin e na tyle dobrze, aby wiedzie¢ które obiekty i fakty
powinny by¢ uwzgl ednione, a które nie (trudny problem!!!).
2. Okre±l zawarto±¢ sªowników predykatów, funkcji i staªych.
Oznacza to przetªumaczenie najwa»niejszych poj e¢ z dziedziny
zastosowa« na j ezyk logiki (utworzenie ontologii dziedziny).
3. Zakoduj ogóln a wiedz e o tej dziedzinie. Zapisz zdania
logiczne wyra»aj ace aksjomaty dotycz ace termów wyst epuj acych
w ontologii.
4. Zakoduj opis przykªadowego problemu. Je±li ontologia
jest dobrze przemy±lana i kompletna, zapisuje si e zdania ato-
mowe o przypadkach poj e¢ wyst epuj acych w ontologii.
5. Sformuªuj zapytania do procedury wnioskowania i od-
bierz odpowiedzi.
46
Poj¦cie ontologii
•
W dziedzinie sztucznej inteligencji cz¦sto stosowany jest ter-
min ontologia
•
Ontologia to specy kacja tworzonych poj¦¢
•
Ontologia jest opisem (podobnym do formalnej specy kacji
programu) poj¦¢ i relacji które mog¡ istnie¢ dla agenta
lub spoªeczno±ci agentów
•
Upraszczaj¡c, ontologia jest zbiorem de nicji poj¦¢
47
Ogólna ontologia (1)
Pytanie: Czy istnieje ogólna ontologia, wspólna dla ró»nych
dziedzin?
Je±li taka ontologia istnieje, to:
•
Powinno by¢ mo»liwe jej zastosowanie w ka»dej szczegóªowej
dziedzinie zastosowa« (po dodaniu aksjomatów specy cznych
dla tej dziedziny);
•
W ka»dej nieco bardziej zªo»onej dziedzinie, ró»ne obszary
wiedzy musz a by¢ zuni kowane, poniewa» rozumowanie i
rozwi azywanie problemu mo»e wymaga¢ wiedzy pochodz acej
jednocze±nie z wielu dziedzin.
48
Ogólna ontologia (2):
Co nale»y reprezentowa¢?
1. Kategorie
5. Wydarzenia i procesy
2. Miary
6. Fizyczne obiekty
3. Obiekty grupowe
(zªo»one)
7. Substancje
4. Czas, przestrze« i zmiana 8. Obiekty my±lowe
(abstrakcje) i przekonania
49
Ogólna ontologia ±wiata
[wg S. Russel, P. Norvig, Arti cial Intelligence. A modern approach.
Prentice Hall, 1995]
50