Metody sztucznej inteligencji

 wykªad 2

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

- na prawach rekopisu)

09 Marca 2006

Rozwiazywanie problemów przez

przeszukiwanie

1

Kroki konieczne przy rozwiazywaniu problemu

•

Sformuªowanie celu

•

Okre±lenie dziaªa« powodujacych przej±cie pomiedzy poszczegól-

nymi stanami

•

Sformuªowanie problemu

•

Poszukiwanie rozwiazania

•

Wykonanie sekwencji dziaªa« bedacej rozwiazaniem prob-

lemu

2

Problem dobrze okre±lony

•

Stan poczatkowy

•

Zbiór mo»liwych dziaªa«, które sa dostepne dla agenta

•

Test osiagniecia celu

•

Sposób wyboru rozwiaza« 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

zastapiono cyframi

Operatory: zastap wszystkie wystapienia

danej

litery

cyfra

jeszcze

nie

wystepujaca 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 rozwiaza«

•

Polega na przeszukiwaniu przestrzeni stanów

•

Idea polega na odnalezieniu i rozszerzeniu zbioru sek-
wencji rozwiaza« cze±ciowych

10

Generowanie sekwencji dziaªa«

•

Zbadaj, czy stan wyj±ciowy nie jest docelowy

•

Wygeneruj nowy zbiór stanów, stosujac operatory do bie»acego
stanu (rozwijanie stanu)

•

Wybierz stan, który nale»y rozwija¢ jako nastepny (okre±la
to STRATEGIA PRZESZUKIWANIA)

11

Drzewo przeszukiwania

•

wezeª przeszuki-

wania odpowiada

danemu stanowi

•

li±¢

drzewa

odpowiada

stanowi, który:

 albo

nie

zostaª

jeszcze

rozwiniety

 albo w wyniku

rozwiniecia

daje

pusty

zbiór stanów

12

Kryteria oceny strategii przeszukiwania

•

Kompletno±¢

•

Zªo»ono±¢ czasowa

•

Zªo»ono±¢ pamieciowa

•

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

Modykacja przeszukiwania w gªab (narzucenie ograniczenia na
max gªeboko±¢ ±cie»ki):

•

specjalny algorytm o ograniczonej gªeboko±ci szukania

•

zmodykowane operatory szukania

19

Przeszukiwanie z iteracyjnym pogªebianiem

20

Przeszukiwanie dwukierunkowe

21

Porównanie strategii przeszukiwania

b

- liczba gaªezi; d - gªeboko±¢ rozwiazania; m - max gªeboko±¢ drzewa; l -

ograniczenie gªeboko±ci

22

Podsumowanie

•

Do okre±lenia problemu potrzebne sa:

stan poczatkowy, operatory, cel, przestrze« stanów, ±cie»ki

przeszukiwania

•

Problem dobrze okre±lony

•

Poszukiwanie rozwiaza«

•

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 sa zdaniami

•

symbol zdaniowy P, Q, . . . jest zdaniem

•

zdanie otoczone nawiasami jest zdaniem, np. (P )

•

zdanie zanegowane jest zdaniem, np. ¬P

•

zdania mo»na budowa¢, ªaczac 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 sie ze znacze« jego
cze±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 pomiedzy
poprzednikiem i nastepnikiem implikacji zachodziªa przyczynowo±¢
lub co najmniej odpowiednio±¢ (relewantno±¢)

5 jest nieparzyste ⇒ Tokio jest stolica Japonii jest prawdziwe
w rachunku zda«!!!

29

Rachunek zda«: Walidacja (ocena prawdzi-

wo±ci)

Wyra»enie W jest tautologia 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 pomoca rachunku zda« (tj.

analizujac tabelki jak poprzednio) , mo»na stosowa¢ reguªy wnioskowa-

nia

Reguªy wnioskowania sa wzorcami sposobu wnioskowania

Notacja:

je»eli α mo»e by¢ wyprowadzone z β przez wnioskowanie, to

odpowiednie schematy wnioskowania zapisuje sie 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-
nalna baze wiedzy sa nadal implikowane przez uzupeªniona baze
wiedzy.

33

Rachunek predykatów: Zaªo»enia

•

±wiat tworza obiekty, posiadajace wªasno±ci odró»niajace je
od innych obiektów

•

pomiedzy obiektami zachodza relacje

•

niektóre relacje sa funkcjami (maja tylko jedna warto±¢ dla
danej zmiennej)

34

Rachunek predykatów: Przykªad

Jeden plus dwa równa sie trzy

•

obiekty: jeden, dwa, trzy, jeden plus dwa

•

relacja: równa sie

•

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 sie

do którego symbolu

predykaty: interpretacja okre±la, które symbole predykatów dotycza

specycznych relacji w modelu

term: wyra»enie logiczne, odnoszace sie 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)

kwantykatory: do wyra»ania wªasno±ci zbiorów obiektów

•

kwantykator ogólny

∀

∀ x Kot(x) ⇒ Ssak(x)

zdanie jest prawdziwe, je±li jest prawdziwe dla wszystkich
podstawie« zmiennej x

•

kwantykator szczególny (szczegóªowy)

∃

np. Burek ma siostre, 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 kwantykatory

∀ 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 kwantykatory

∀ 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 kwantykatoró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 dotycza 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 pojecia

In»ynieria wiedzy: proces konstruowania bazy wiedzy; szerzej

 nauka o metodach i ±rodkach stosowanych w tym celu.

In»ynier wiedzy: osoba, która bada dana dziedzine wiedzy, okre±la

które pojecia wystepujace w tej dziedzinie sa istotne, oraz

tworzy dla tej dziedziny formalna reprezentacje obiektów i

relacji wystepujacych pomiedzy tymi obiektami.

Uwaga: In»ynier wiedzy nie jest zwykle ekspertem w tej

dziedzinie, z której wiedze pozyskuje, winien mie¢ natomiast

co najmniej minimalna orientacje w problemach tej dziedziny

oraz by¢ specjalista 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 pomoca formalnych ±rodków reprezentacji.

44

In»ynieria wiedzy a programowanie

In»ynieria wiedzy

Programowanie

Wybór jezyka reprezentacji

Wybór jezyka 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 sie zrozumie¢

dziedzine na tyle dobrze, aby wiedzie¢ które obiekty i fakty

powinny by¢ uwzglednione, 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 poje¢ z dziedziny

zastosowa« na jezyk logiki (utworzenie ontologii dziedziny).

3. Zakoduj ogólna wiedze o tej dziedzinie. Zapisz zdania

logiczne wyra»ajace aksjomaty dotyczace termów wystepujacych

w ontologii.

4. Zakoduj opis przykªadowego problemu. Je±li ontologia

jest dobrze przemy±lana i kompletna, zapisuje sie zdania ato-

mowe o przypadkach poje¢ wystepujacych 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 specykacja tworzonych poj¦¢

•

Ontologia jest opisem (podobnym do formalnej specykacji
programu) poj¦¢ i relacji które mog¡ istnie¢ dla agenta
lub spoªeczno±ci agentów

•

Upraszczaj¡c, ontologia jest zbiorem denicji 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 specycznych

dla tej dziedziny);

•

W ka»dej nieco bardziej zªo»onej dziedzinie, ró»ne obszary

wiedzy musza by¢ zunikowane, poniewa» rozumowanie i

rozwiazywanie problemu mo»e wymaga¢ wiedzy pochodzacej

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, Articial Intelligence. A modern approach.
Prentice Hall, 1995]

50