POLITECHNIKA WARSZAWSKA
MEL
MEL
WYDZIAA
MECHANICZNY ENERGETYKI I LOTNICTWA
WPROWADZENIE
DO SZTUCZNEJ INTELIGENCJI
NS 586
Dr in\
. Franciszek Dul
© F.A. Dul 2007
10. REPREZENTACJA WIEDZY
O ÅšWIECIE
O ÅšWIECIE
© F.A. Dul 2007
Reprezentacja wiedzy
Poka\
emy, w jaki sposób reprezentuje
siÄ™ najwa\
niejsze aspekty świata:
przestrzeń, czas, działania, zdarzenia
w języku logiki pierwszego rzędu.
Omówimy systemy ekspertowe, które
wspomagają człowieka w korzystaniu
z wiedzy i przy podejmowaniu decyzji.
© F.A. Dul 2007
Jak opisać świat w języku FOL?
W języku logiki pierwszego rzędu mo\
na  z marszu
opisać prosty układ logiczny lub świat Wumpusa.
Jednak nawet wtedy sÄ… problemy, gdy\
logika
 niczego nie wie o świecie  nawet tego, \
e 1 `" 0.
Opis świata rzeczywistego jest nieporównanie
bardziej skomplikowany, gdy\
:
- istnieje niezliczone mnóstwo ró\
nych rzeczy,
- istnieje niezliczone mnóstwo ró\
nych rzeczy,
- między rzeczami zachodzą skomplikowane relacje,
- w świecie występują zdarzenia,
- świat się zmienia (ewoluuje).
Aby ująć całą zło\
oność świata w języku FOL nale\
y
posłu\
yć się ontologią wy\
szÄ…, pozwalajÄ…cÄ…
kategoryzować i systematyzować obiekty i zdarzenia.
Jest to zagadnienie reprezentacji wiedzy.
© F.A. Dul 2007
Jak opisać świat w języku FOL?
Zasadnicza trudność reprezentacji świata polega
na tym, \
e jego opis logiczny musi być zupełny.
Człowiek rozumuje przyjmując wiele faktów jako
domyślnych  model świata otwartego.
Logika nie ma wbudowanego zestawu faktów
domyślnych  model świata zamkniętego.
Pominięcie pewnych faktów mo\
e prowadzić
Pominięcie pewnych faktów mo\
e prowadzić
do błędnych wniosków.
Trzeba więc znalez
ć reprezentację faktów i reguł
domyślnych która jest zupełna a zarazem efektywna.
© F.A. Dul 2007
Plan rozdziału
" In\
ynieria ontologiczna
" Kategorie i obiekty
" Działania, sytuacje i zdarzenia
" Zdarzenia mentalne i obiekty mentalne
" Systemy wnioskowania dla kategorii; sieci semantyczne
" Wnioskowanie z informacją domyślną
" Systemy utrzymywania prawdy
" Systemy utrzymywania prawdy
" Systemy ekspertowe
© F.A. Dul 2007
10.1. In\
ynieria ontologiczna
Ontologia (metafizyka,  Nauka o wszystkim co istnieje )
jest działem filozofii odpowiadającym na pytania dotyczące
struktury rzeczywistości: przedmiotów, czasu, przestrzeni...
In\
ynieria ontologiczna (OE) zajmuje się problemem ogólnej
elastycznej reprezentacji świata.
" OE rozwa\
a takie pojęcia jak: działania, czas, obiekty
fizyczne czy wiarygodność.
" OE mo\
na uwa\
ać za uogólnienie In\
ynierii Wiedzy (KE)
Ka\
da reprezentacja logiczna świata ma ograniczenia.
Problemami reprezentacji są wyjątki i niepewność określeń.
Przykład: pomidor jest zwykle czerwony i okrągły, ale mo\
e
być te\
zielony, \
ółty, pomarańczowy; owoce mogą
znacznie ró\
nić się kształtami, wielkością, itp.
Ontologia wy\
sza (upper ontology) definiuje ogólne ramy
dla koncepcji dotyczących reprezentacji świata.
Ontologia wy\
sza definiuje i klasyfikuje w sposób
hierarchiczny obiekty i zdarzenia występujące w świecie.
© F.A. Dul 2007
10.1. In\
ynieria ontologiczna
Ontologia wy\
sza świata (niewielka część)
Wszystko
Zdarzenia uogólnione
Obiekty abstrakcyjne
Zbiory Obiekty Przedziały Miejsca
Liczby
Obiekty Procesy
reprezentowalne
fizyczne
Materia
Chwile
Miary Rzeczy
Kategorie Sentencje
Ciało
Gaz
Zwierzęta Agenci Ciecz
Masa
Czas
stałe
Ludzie
Ka\
da koncepcja poziomu ni\
szego jest specjalizacjÄ… koncepcji
poziomu wy\
szego.
© F.A. Dul 2007
10.1. In\
ynieria ontologiczna
Cechy i zadania ontologii wy\
szej
" Ontologia ogólna powinna dać się zastosować do ka\
dej
dziedziny szczegółowej.
Do dziedziny szczegółowej nale\
y dodać aksjomaty
słuszne dla tej dziedziny.
" W ka\
dej większej dziedzinie ró\
ne obszary wiedzy
powinny być ujednolicone.
Ró\
ne obszary wiedzy muszą zazwyczaj być łączone
w celu opisu dziedziny szczegółowej.
w celu opisu dziedziny szczegółowej.
Wymaga to komplementarności (przystawania) opisów
(np. opisów czasu i przestrzeni).
" Co nale\
y wyrazić w ramach ontologii wy\
szej?
Kategorie, Miary, Obiekty zło\
one,
Czas, Przestrzeń,
Zmiany, Zdarzenia, Procesy,
Obiekty fizyczne, Substancje, Obiekty mentalne,
PoglÄ…dy,...
© F.A. Dul 2007
10.2. Kategorie i obiekty
" Kategoria jest zbiorem (swoich) elementów.
" Reprezentacja wiedzy wymaga podzielenia obiektów
na kategorie.
 Oddziaływanie (interakcja) ma miejsce na poziomie
obiektów.
 Wnioskowanie zachodzi na poziomie kategorii.
" Kategorie pozwalają identyfikować obiekty na podstawie
postrzeganych własności, np.
postrzeganych własności, np.
OkrÄ…gÅ‚y '" Czerwony '" MiÄ™kki '" PoÅ‚yskujÄ…cy Ò! Pomidor
Ò!
Ò!
Ò!
" Kategorie mogą być reprezentowane w logice pierwszego
rzędu na dwa sposoby:
 jako predykaty:
Pomidor(x)
 poprzez sprowadzanie (reifying) kategorii do zbiorów
obiektów:
Pomidory
© F.A. Dul 2007
10.2. Kategorie i obiekty
Organizacja kategorii
" Kategorie zwiÄ…zane sÄ… relacjÄ… dziedziczenia
(por. z językiem C++), np.:
 ka\
dy egzemplarz \
ywności jest jadalny;
 owoc jest podklasÄ… \
ywności;
 jabłko jest podklasą owoców;
 zatem jabłko jest jadalne.
" Definiowanie systematyki poprzez relacje kategorii
Ka\
da kategoria bardziej
Ka\
da kategoria bardziej
Ssaki
szczegółowa dziedziczy
cechy kategorii ogólniejszej
Podzbiór
z której się wywodzi.
Osoby
Przykład
Podzbiór Podzbiór
Kobiety dziedziczÄ… cechy
osób, np. wzrost, wagę;
MÄ™\
czyz
ni
Kobiety
podobnie mÄ™\
czyz
ni.
Element
Element
Kobiety i mÄ™\
czyz
ni majÄ…
Maria Jan
te\
jednak pewne cechy
odmienne...
© F.A. Dul 2007
10.2. Kategorie i obiekty
Opis kategorii w logice pierwszego rzędu
" Obiekt jest elementem kategorii
Element( BB12 , PiłkaDoKoszykówki )
" Kategoria mo\
e być podklasą innej kategorii
Podzbiór( PiłkaDoKoszykówki , Piłki )
" Wszystkie elementy kategorii mają pewne własności
"x Element(x,PiÅ‚kaDoKoszykówki) Ò! OkrÄ…gÅ‚y(x)
" Wszystkie elementy kategorii mogą być rozpoznane
po pewnych własnościach
" x (Pomarańczowy(x) '" Okrągły(x) '" Średnica(x)=24.5 cm
'" Element(x,PiÅ‚ki) Ò! Element(x, PiÅ‚kaDoKoszykówki))
" Kategoria jako całość ma pewne własności
Element( Psy , GatunkiOswojone )
© F.A. Dul 2007
10.2. Kategorie i obiekty
Relacje pomiędzy kategoriami
" Dwie lub więcej kategorie są rozłączne je\
eli nie maja
wspólnych elementów:
RozÅ‚Ä…czne(s) Ô! (" c1,c2 c1"s '" c2" s '" c1 `" c2 Ò!
Przecięcie(c1,c2) = { } )
Przykład
Rozłączne( { zwierzęta, warzywa } )
" Zbiór kategorii s tworzy dekompozycję kompletną
" Zbiór kategorii s tworzy dekompozycję kompletną
kategorii c je\
eli wszystkie elementy zbioru c sÄ… pokryte
przez kategorie z s:
DekompozycjaKompletna(s,c) Ô! ("i i " c Ò! "c2 c2" s'" i"c2)
Przykład
DekompozycjaKompletna(
{Amerykanie, Kanadyjczycy, Meksykanie},
AmerykaniePółnocni ).
© F.A. Dul 2007
10.2. Kategorie i obiekty
Relacje pomiędzy kategoriami
" Podział jest to rozłączna dekompozycja kompletna:
PodziaÅ‚(s,c) Ô! RozÅ‚Ä…czny(s) '" DekompozycjaKompletna(s,c)
Ô!
Ô!
Ô!
Przykład
Podział( {Mę\
czyz
ni,Kobiety} ,Osoby).
Czy jest podziałem dekompozycja
({Amerykanie, Kanadyjczycy, Meksykanie}, AmerykaniePółnocni )
Nie, bo niektórzy AmerykaniePółnocni mają podwójne obywatelstwo.
Nie, bo niektórzy AmerykaniePółnocni mają podwójne obywatelstwo.
" Kategorie mogą być zdefiniowane przez podanie
warunków koniecznych i dostatecznych dla elementów
"x Kawaler(x) Ô! MÄ™\
czyzna(x) '" Dorosły(x) '" Nie\
onaty(x)
Ô!
Ô!
Ô!
© F.A. Dul 2007
10.2. Kategorie i obiekty
Struktura fizyczna kategorii
" Obiekt mo\
e być częścią innego obiektu:
Część(Bukareszt,Rumunia)
Część(Rumunia,EuropaWschodnia)
Część(EuropaWschodnia,Europa)
" Predykat Część jest przechodni (a tak\
e zwrotny),
zatem mo\
emy wnioskować, \
e
Część(Bukareszt,Europa)
" Definicja formalna predykatu Część:
"x Część(x,x)
"x,y,z Część(x,y) '" Część(y,z) Ò! Część(x,z)
Ò!
Ò!
Ò!
" Struktura fizyczna często jest określona przez zale\
ności
strukturalne pomiędzy częściami, np.
Dwunóg(a) Ò! ("l1 , l2 ,b) (Noga(l1) '" Noga(l2) '" CiaÅ‚o(b) '"
Ò!
Ò!
Ò!
Część(l1,a) '" Część(l2,a) '" Część(b,a) '"
Przyłączony(l1,b) '" Przyłączony(l2,b) '"
l1 `" l2 '" (" l3) (Noga(l3) Ò! ( l3 = l1 (" l3 = l2 ) ) )
Ò!
Ò!
Ò!
© F.A. Dul 2007
10.2. Kategorie i obiekty
Miary
" Obiekty mają wysokość, masę, cenę, ....
Wartości przypisane tym cechom to miary
" Funkcje liczbowe określające jednostki miar:
Długość(L1) = Cale(1.5) = Centymetry(3.81).
" Konwersje pomiędzy jednostkami:
"i Centymetry( 2.54 x i ) = Cale(i).
" Miary mogą posłu\
yć do opisu obiektów:
Średnica( PiłaDoKosza12 ) = Cale(9.5).
" Niektóre miary nie mają skali: Piękno, Trudność, etc.
 Najwa\
niejsza cecha miar: mogą być uporządkowane.
 Nie nale\
y przywiązywać zbytniej wagi do konkretnych
wartości.
Jabłko mo\
e mieć  wyśmienitość 0.9 lub 1.0.
© F.A. Dul 2007
10.2. Kategorie i obiekty
Substancje i obiekty
" Świat składa się z obiektów prostych i zło\
onych.
" Pewne obiekty są niepodzielne (np. krzesło), zaś inne
są podzielne (np. masło).
" Obiekty niepodzielne to rzeczy (things)
domy, koty, twierdzenia, ...
zaÅ› niepodzielne to materia (stuff),
woda, energia, masło, ....
" Reprezentacja materii w języku FOL.
" Reprezentacja materii w języku FOL.
 Ka\
da część masła jest masłem
x " MasÅ‚o '" Część(y,x) Ò! y " MasÅ‚o.
Ò!
Ò!
Ò!
" Niektóre własności są wewnętrzne (intrinsic) i niepodzielne
gęstość, kolor, zapach, temperatura topnienia, ...
zaś inne  zewnętrzne (extrinsic)
masa, długość, kształt, ...
" Materia ma tylko własności wewnętrzne.
" RzeczÄ… jest zaÅ› ka\
dy obiekt majÄ…cy chocia\
jednÄ…
własność zewnętrzną.
© F.A. Dul 2007
10.2. Reprezentacja wiedzy
Rodzaje naturalne
" Niektóre kategorie są zdefiniowane ściśle, np. trójkąty.
" Wiele kategorii nie ma jednak precyzyjnych definicji,
np. krzesło, krzak, ksią\
ka, ...
Pomidory mogą być czerwone, zielone, \
ółte, zazwyczaj są okrągłe.
Kategorie takie stanowiÄ… rodzaje naturalne.
" Rozwiązanie: kategoria Typowe określająca podstawowe
cechy elementów kategorii naturalnej c,
cechy elementów kategorii naturalnej c,
Typowe(c) Ä…" c.
Przykład
"x, x " Typowe(Pomidory) Ò! Czerwony(x) '" Kulisty(x).
Ò!
Ò!
Ò!
Za pomocÄ… kategorii Typowe mo\
na opisać wa\
ne fakty
dotyczące kategorii bez formułowania ścisłych definicji.
" U\
yteczność pojęcia ścisła definicja jest wątpliwa.
Stwierdzenie  Papie\
jest kawalerem , które wynika
z definicji ścisłej, jest niezbyt fortunne...
© F.A. Dul 2007
10.3. Działania, zdarzenia i sytuacje
" Wnioskowanie o wyniku
działania jest podstawą
działania agenta z bazą wiedzy.
" Jak mo\
na śledzić zmiany
świata w logice pierwszego
rzędu?
W logice zdań nale\
y określić
stan w ka\
dej chwili czasu.
stan w ka\
dej chwili czasu.
" Sytuacje sÄ… to zdarzenia zmieniajÄ…ce
siÄ™ dyskretnie w czasie.
" Sytuacje  przeskakujÄ… od zdarzenia
do zdarzenia  nie ma mo\
liwości
zmiany stanu pomiędzy zdarzeniami.
" Rachunek sytuacji opisuje zmiany
sytuacji w wyniku kolejnych działań.
© F.A. Dul 2007
10.3. Działania, zdarzenia i sytuacje
Zasady rachunku sytuacji
" Działania są termami logicznymi, np. Skręć(WPrawo).
" Sytuacje są termami logicznymi zło\
onymi z:
" sytuacji poczÄ…tkowej S0
" wszystkich sytuacji wynikających z działań a wykonanych
w sytuacjach s,
Wynik(a,s) [ lub Zrób(a,s) ]
" Potoki (fluent) są to funkcje i predykaty które zmieniają
siÄ™ z sytuacji na sytuacjÄ™, np.
ŹTrzymanie(G , S0)
ŹTrzymanie(G1, S )
" IstniejÄ… tak\
e predykaty wieczne (eternal), np.
ZÅ‚oto(Gi)
" Wynik ciągu działań jest określony (zdeterminowany)
przez poszczególne działania.
" Zadanie projektowania: wywnioskować wynik danego
ciągu działań.
" Zadanie planowania: znalez
ć ciąg działań który
zapewnia po\
Ä…dany wynik.
© F.A. Dul 2007
10.3. Działania, zdarzenia i sytuacje
W rachunku sytuacji ka\
da sytuacja (z wyjÄ…tkiem poczÄ…tkowej)
jest wynikiem pewnego działania.
© F.A. Dul 2007
10.3. Działania, zdarzenia i sytuacje
Opis działań w rachunku sytuacji
" Najprostszy rachunek sytuacji potrzebuje do opisu zmian
dwóch aksjomatów:
 Aksjomat mo\
liwości: przeprowadzić działanie je\
eli
jest to mo\
liwe
WarunkiWstÄ™pne Ò! Mo\
liwe(a,s)
Ò!
Ò!
Ò!
Przy(Agent,x,s) '" PrzylegÅ‚y(x,y) Ò! Mo\
liwe(Idz
(x,y),s)
Ò!
Ò!
Ò!
 Aksjomat wyniku: opisać zmiany wywołane działaniem
Mo\
liwe(a,s) Ò! Zmiany w wyniku dziaÅ‚ania a
Mo\
liwe(a,s) Ò! Zmiany w wyniku dziaÅ‚ania a
Mo\
liwy(Idz
(x,y),s) Ò! Przy(Agent,y,Wynik(Idz
(x,y),s))
Ò!
Ò!
Ò!
" Jak opisać to, co w świecie się nie zmienia?
 Problem kadru: reprezentacja wszystkich sytuacji które
nie zmieniajÄ… siÄ™.
 Aksjomat kadru: co się nie zmienia podczas działań
Przy(o,x,s) '" (o `" Agent) '" ŹTrzymać(o,s) Ò!
Ò!
Ò!
Ò!
Przy(o,x,Wynik(Idz
(y,z),s))
© F.A. Dul 2007
10.3. Działania, zdarzenia i sytuacje
Rachunek zdarzeń
Rachunek sytuacji opisuje zdarzenia dyskretne w czasie.
Rachunek zdarzeń opisuje stany zmieniające się w czasie
w sposób ciągły.
W rachunku zdarzeń istnieje mo\
liwość zaistnienia pewnego
zdarzenia w dowolnej chwili.
Aksjomat rachunku zdarzeń
T(f,t2) Ô! " e, t ZdarzaSiÄ™(e,t) '" Inicjalizuje(e,f,t) '" (t < t2)
T(f,t2) Ô! " e, t ZdarzaSiÄ™(e,t) '" Inicjalizuje(e,f,t) '" (t < t2)
Ô!
Ô!
Ô!
Ô!
Ô!
Ô!
'" ŹPrzerwanie(f,t,t2)
Przerwanie(f,t,t2) Ô! " e, t1 ZdarzaSiÄ™(e,t1) '" KoÅ„czy(e,f,t1)
Ô!
Ô!
Ô!
'" (t < t1) '" (t1 < t2)
Potok f jest inicjalizowany w pewnej chwili t, a kończy się
w chwili t1.
Potok f mo\
e być zakończony w chwili t2 < t1 przez pewne
zdarzenie e.
© F.A. Dul 2007
10.3. Działania, zdarzenia i sytuacje
Zdarzenia uogólnione
Zdarzenie uogólnione jest elementem
czasoprzestrzeni, zło\
onym ze zdarzeń
działań, miejsca, czasu, potoków oraz
obiektów.
Przykład  Druga wojna światowa
Podzdarzenia (subevents) sÄ…
elementami zdarzenia uogólnionego.
Element kategorii c jest podzdarzeniem zdarzenia
Element kategorii c jest podzdarzeniem zdarzenia
lub przedziału i
E(c,i) Ô! "e e " c '" Subevent(e,i)
Ô!
Ô!
Ô!
Przykład
Subevent( BitwaOAngliÄ™ , DrugaWojnaÅšwiatowa)
Procesy są to zdarzenia zmieniające się w czasie w sposób
ciągły.
Procesy ró\
nią się tym od zdarzeń, czym materia ró\
ni siÄ™
od rzeczy.
© F.A. Dul 2007
10.4. Obiekty i zdarzenia mentalne
" Agent mo\
e mieć poglądy i wyciągać wnioski prowadzące
do nowych poglądów.
" Agent powinien te\
przewidywać, co myślą inni agenci.
" Wymaga to modeli stanów myślowych w czyjejś głowie
oraz procesów zmieniających te stany.
" Obiekty mentalne to takie stany mentalne w czyjejś głowie
(lub w bazie wiedzy), jak: wiedza, przekonania, potrzeby.
" Zdarzenia mentalne to procesy wnioskowania w których
" Zdarzenia mentalne to procesy wnioskowania w których
uczestniczÄ… obiekty mentalne.
uczestniczÄ… obiekty mentalne.
" Wiedza i przekonanie agenta a na temat zdania p:
Wie(a,p), Wierzy(a,p).
" Relacja pomiędzy wiedzą a przekonaniem: je\
eli jest siÄ™
przekonanym o czymÅ› i je\
eli to jest prawda, to siÄ™ to wie,
Wierzy(a,p) '" p Ò! Wie(a,p).
Ò!
Ò!
Ò!
" Przekonanie zapisane za pomocÄ… aksjomatu rachunku
zdarzeń:
T( Wierzy(Jan , Superman(Leci) ) , Dzisiaj ).
© F.A. Dul 2007
10.6. Systemy wnioskowania dla kategorii
Kategorie stanowią podstawowe cegiełki dla reprezentacji
zło\
onych systemów wiedzy.
IstniejÄ… dwa rodzaje reprezentacji i wnioskowania dla
kategorii: sieci semantyczne i logika opisowa.
Sieci semantyczne:
" umo\
liwiajÄ… wizualizacjÄ™ bazy wiedzy;
" zawierają efektywne algorytmy wnioskowania o własnoś-
ciach elementów na podstawie ich przynale\
ności
ciach elementów na podstawie ich przynale\
ności
do kategorii.
Logika opisowa:
" u\
ywa języka formalnego do budowania i łączenia definicji
kategorii;
" dostarcza efektywnych algorytmów do wyznaczania relacji
zawierania pomiędzy kategoriami.
© F.A. Dul 2007
10.6. Systemy wnioskowania dla kategorii
Sieci semantyczne
Dziedziczenie:
Ssaki
liczba nóg = 2
Sieci semantyczne reprezentujÄ…
Podzbiór
graficznie obiekty, kategorie
Nogi
Ma matkÄ™
obiektów oraz relacje pomiędzy
Osoby
2
obiektami.
Podzbiór
Podzbiór
Sieci semantyczne stanowiÄ…
Jan:
MÄ™\
czyz
ni
Kobiety
liczba
alternatywÄ™ opisu logicznego.
nóg = 1
Element Element
Sieci semantyczne umo\
liwiajÄ…
Nogi
Siostra
Maria Jan
Maria Jan
1
1
wnioskowanie z dziedziczeniem.
wnioskowanie z dziedziczeniem.
(Porównaj z programowaniem
Kategoria Kobiety dziedziczy wszystkie
orientowanym obiektowo  np. C++).
własności kategorii Osoby.
PowiÄ…zania odwrotne, np. "p,s MaSiostrÄ™(p,s) Ô! Siostra(s,p)
Ô!
Ô!
Ô!
pozwalają znacznie zwiększyć efektywność wnioskowania.
Wady sieci semantycznych:
" Połączenie mo\
e reprezentować tylko relacje binarne.
Mo\
na temu zaradzić poprzez potraktowanie twierdzenia jako zdarzenia.
" Reprezentacja wartości domyślnych jest narzucona przez
mechanizm dziedziczenia.
© F.A. Dul 2007
10.6. Systemy wnioskowania dla kategorii
Logika opisowa
Logika opisowa (description logic) została opracowana
specjalnie do opisu definicji i własności kategorii.
Logika opisowa powstała jako formalizacja sieci
semantycznych.
Najwa\
niejszymi zadaniami logiki opisowej sÄ…:
" Subsumpcja: sprawdzanie czy dana kategoria jest
podzbiorem innej kategorii poprzez porównanie ich
definicji.
definicji.
" Klasyfikacja: sprawdzanie czy dany obiekt nale\
y
do kategorii.
" Zgodność: czy kryteria przynale\
ności do kategorii
są logiczne spełnialne (satisfiable).
Najwa\
niejszym aspektem logiki opisowej jest poło\
enie
nacisku na mo\
liwość przeprowadzenia wnioskowania.
Wadą logiki opisowej jest nieobsługiwanie przez nią negacji
i alternatywy.
Logika opisowa do zapisu zdań u\
ywa języka CLASSIC.
© F.A. Dul 2007
10.7. Wnioskowanie z informacją domyślną
Reprezentacja informacji domyślnej wymaga uwagi.
To, co dla człowieka jest domyślnie oczywiste, nie jest takie
dla logicznego systemu wnioskujÄ…cego.
Przykład Wykłady w semestrze letnim: NS101, NS102, NS106, TE101.
Ile wykładów będzie prowadzonych?
" Odpowiedz
bazy wiedzy: cztery przy zało\
eniach, \
e:
 informacja jest zupełna (wszystkie nie wyra\
one jawnie zdania sÄ…
fałszywe  zało\
enie świata zamkniętego);
 ró\
ne obiekty mają ró\
ne nazwy - zało\
enie nazw unikalnych.
" Odpowiedz
logiki: od jednego do nieskończenie wielu.
" Odpowiedz
logiki: od jednego do nieskończenie wielu.
 Logika nie czyni zało\
eń domyślnych.
Informacji domyślna wymaga zatem dopełnienia.
Umo\
liwiajÄ… to logiki niemonotoniczne.
Ograniczenie (circumscription) umo\
liwia zapis faktów
prawdziwych tylko dla wybranych obiektów.
Logika domyślna (default logic) u\
ywa reguł domyślnych
postaci P : J1, ..., J1 / C do zapisu faktów, np.
Ptak(x) : Leci(x) / Leci(x)
oznacza \
e je\
eli Ptak(x) jest prawdÄ… i je\
eli Leci(x) jest zgodne z bazÄ…
wiedzy, to Leci(x) mo\
e być przyjęte domyslnie.
© F.A. Dul 2007
10.8. Systemy utrzymywania prawdy
Wiele wnioskowań ma charakter przybli\
ony  ich wyniki
nie sÄ… absolutnie pewne.
Wywnioskowane przez nie fakty mogą być zatem fałszywe
i powinny być wycofane z bazy (weryfikacja poglądu).
Załó\
my \
e baza wiedzy KB zawiera zdanie P i chcemy
dodać do niej zdanie ŹP; TELL(KB, ŹP) sprzeczność.
Aby uniknąć sprzeczności nale\
y wycofać błędne zdanie
z bazy wiedzy; Wycofać(KB,P).
z bazy wiedzy; Wycofać(KB,P).
Pojawia siÄ™ jednak problem ze zdaniami wywnioskowanymi
wcześniej ze zdania P.
Do rozwiązywania takich problemów słu\
Ä… systemy
utrzymywania prawdy (truth maintenance systems).
Systemami takimi sÄ… np. JTMS, ATMS.
Systemy utrzymywania prawdy zawierajÄ… mechanizmy
wyjaśniające  pozwalające wyznaczyć zbiór wszystkich
zdań pociągających zdanie P.
© F.A. Dul 2007
10.9. Projekt powszechnej ontologii Å›wiata CYC®
Projekt CYC® (enCYClopedia) ma na celu stworzenie
obszernej ontologii oraz bazy danych dla ogólnej i potocznej
wiedzy o świecie.
Celem jest stworzenie ogólnej bazy wiedzy umo\
liwiajÄ…cej
wnioskowanie automatyczne na podobieństwo ludzkiego.
Stan aktualny: baza wiedzy zawiera ponad milion faktów,
reguł oraz pojęć potocznych, np.  Every tree is a plant .
Wiedza zapisana jest w języku CycL opartym na rachunku
Wiedza zapisana jest w języku CycL opartym na rachunku
predykatów, podobnym do języka LISP, np.
predykatów, podobnym do języka LISP, np.
USPresident(GeorgeWBush) #$isa #$GeorgeWBush #$USPresident



System wnioskowania umo\
liwia odpowiadanie na pytania
zadawane przez u\
ytkownika.
W zamierzeniu docelowym CYC ma umo\
liwiać komunikację
z u\
ytkownikiem w języku naturalnym oraz ma się uczyć.
Podzbiór OpenCYC jest bazą uproszczoną, dostępną
na zasadach licencji Open Source.
Ambitne zamierzenia programu CYC sÄ… jednak krytykowane.
© F.A. Dul 2007
Systemy ekspertowe
Wiedza na temat dziedziny jest bardzo cenna, gdy\

pozwala określić racjonalne działania.
Ogrom zgromadzonej wiedzy oraz subtelne nieraz
zale\
ności pomiędzy jej składnikami czynią jednak
korzystanie z niej procesem bardzo \
mudnym.
Efektywne wykorzystanie wiedzy wymaga więc
narzędzi wspomagających, które pozwolą ogarnąć
narzędzi wspomagających, które pozwolą ogarnąć
całość oraz wyciągać skomplikowane wnioski.
Narzędziami umo\
liwiajÄ…cymi kompleksowe
wykorzystywanie wiedzy sÄ… systemy ekspertowe.
Podstawę systemów ekspertowych stanowią: język
logiki oraz ontologia wy\
sza świata.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Systemy ekspertowe (eksperckie, z bazÄ… wiedzy)
sÄ… to programy wspomagajÄ…ce korzystanie z wiedzy
i ułatwiające podejmowanie decyzji.
System ekspertowy mo\
e być uwa\
any za model ekspertyzy
zło\
ony z bazy wiedzy i procedury wnioskowania logicznego.
Cechy systemy ekspertowych:
" sÄ… wÄ…sko wyspecjalizowane,
" mogą wspomagać lub nawet zastępować ekspertów
w danej dziedzinie,
w danej dziedzinie,
" mogą dostarczać rad, zaleceń i diagnoz dotyczących
problemów tej dziedziny.
Systemy ekspertowe sÄ… tworzone przez in\
ynierów wiedzy
w ramach metod in\
ynierii ontologicznej.
y
ródła informacji i dane dla systemów ekspertowych:
" wiedza ekspertów danej dziedziny,
" heurystyki (dla domysłów, przypuszczeń, itp. ),
" modele u\
ywane w dziedzinie,
" analiza wcześniejszych rozwiązań.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Struktura systemu ekspertowego
In\
ynier wiedzy
Ekspert
System dedykowany
Baza danych
Baza wiedzy
zmiennych
Mechanizm Mechanizm Edytor bazy
wyjaśniajacy wnioskowania wiedzy
Interfejs u\
ytkownika
Szkielet systemu ekspertowego
U\
ytkownik
© F.A. Dul 2007
10.10. Systemy ekspertowe
Elementy systemu ekspertowego:
" Szkielet systemu w skład którego wchodzą:
" Mechanizm wnioskowania (maszyna wnioskujÄ…ca)
Główny składnik systemu ekspertowego wykonujący cały
proces rozumowania w trakcie rozwiÄ…zywania problemu
postawionego przez u\
ytkownika;
" Interfejs u\
ytkownika
Umo\
liwia udzielanie informacji systemowi (TELL)
oraz zadawanie pytań, odbieranie od systemu
odpowiedzi i wyjaśnień (ASK);
odpowiedzi i wyjaśnień (ASK);
" Edytor bazy wiedzy
Pozwala modyfikować wiedzę zawartą w systemie,
umo\
liwiajÄ…c tym samym jego rozbudowÄ™;
" Mechanizm wyjaśniający
Element interfejsu u\
ytkownika, który umo\
liwia uzyskanie
informacji:
- dlaczego system udzielił takiej, a nie innej odpowiedzi,
- dlaczego system zadał u\
ytkownikowi określone pytanie.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Elementy systemu ekspertowego:
" Baza wiedzy
Deklaratywna postać wiedzy ekspertów z danej
dziedziny zapisana za pomocÄ… wybranego sposobu
reprezentacji wiedzy, najczęściej reguł lub ram.
" Baza danych zmiennych
Pamięć robocza przechowującą pewne fakty
wprowadzone w trakcie dialogu z u\
ytkownikiem;
Umo\
liwia odtworzenie sposobu wnioskowania
Umo\
liwia odtworzenie sposobu wnioskowania
systemu i przedstawienie go u\
ytkownikowi
za pomocą mechanizmu wyjaśniającego.
Pozyskiwaniem wiedzy od ekspertów zajmują się
in\
ynierowie wiedzy.
Pozyskiwanie wiedzy to zwykle długi i \
mudny proces, gdy\

wiedza stosowana przez ekspertów ma charakter intuicyjny
i praktyczny, często trudny do werbalizacji.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Klasyfikacja systemów ekspertowych:
" Rodzaj bazy wiedzy
" oparta na regułach (rule-based systems),
" oparta na modelu (model-based systems),
" oparta na wcześniejszych rozwiązaniach(case-based systems).
" Charakter przetwarzanej wiedzy:
" pewna (prawda/fałsz),
" niepewna;
" sposób reprezentacji niepewności:
 logika wielowartościowa,
 logika wielowartościowa,
 logika rozmyta,
 współczynniki stopnia pewności,
 metody statystyczne.
" Sposób działania:
" off-line,
" on-line - systemy czasu rzeczywistego.
" Uniwersalność:
" systemy dedykowane, tworzone dla konkretnego zastosowania,
" systemy szkieletowe.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Zadania realizowane przez systemy ekspertowe:
" Interpretacja  formułowanie wniosków lub opisów
na podstawie  surowych danych.
" Predykcja  przewidywanie skutków danego stanu.
" Diagnoza  określanie przyczyn złego funkcjonowania
na podstawie objawów.
" Projektowanie  znajdowanie konfiguracji elementów
systemu spełniających warunki projektu.
systemu spełniających warunki projektu.
" Planowanie  wyznaczanie ciągu działań które pozwolą
osiągnąć cel.
" Monitorowanie  porównywanie rzeczywistego zachowania
systemu z zało\
onym.
" Instruowanie  wykrywanie i poprawianie błędów uczniów.
" Sterowanie  sterowanie zło\
onymi systemami.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Zasady bazy wiedzy opartej na regułach
W skład regułowej bazy wiedzy wchodzą:
" Fakty (asercje)  uznane za prawdziwe informacje
dotyczÄ…ce opisywanej dziedziny.
" Reguły  związki zachodzące miedzy faktami w formie
JEśELI przesłanka TO wniosek
Przesłankami i wnioskami w regułach są fakty.
Wnioskowanie polega na realizacji ( odpaleniu ) reguły.
Wnioskowanie polega na realizacji ( odpaleniu ) reguły.
Odpalenie reguły następuje wtedy, gdy jej przesłanki
występują w bazie faktów i są prawdziwe.
W wyniku odpalenia reguły wynikający z niej wniosek
jest dodawany do bazy faktów.
Wniosek jednej reguły mo\
e stanowić przesłankę dla innej
 jest to wniosek pośredni.
Wniosek, który stanowi odpowiedz
na zadane pytanie
jest wnioskiem końcowym.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Reprezentacja reguł
Reguły mogą być reprezentowane:
- jako zbiór warunków JEśELI przesłanka TO wniosek,
- w postaci drzewa decyzyjnego.
Drzewo decyzyjne jest to graficzna postać reguł.
Drzewo decyzyjne obrazuje powiązania pomiędzy faktami.
Przykład Drzewo decyzyjne diagnozy rozruchu samochodu
Czy silnik zapala?
Czy silnik zapala?
Nie
Tak
Czy świecą się światła?
Tak
Nie
Czy rozrusznik pracuje? Akumulator
Tak
Nie
Czy w zbiorniku jest paliwo? Rozrusznik
Tak Nie
Czy paliwo dopływa do silnika?
Brak paliwa
Tak Nie
Zapłon Pompa
© F.A. Dul 2007
10.10. Systemy ekspertowe
Uwzględnianie niepewności faktów i reguł
Niepewność wiedzy mo\
e być reprezentowana na ró\
ne
sposoby: probabilistycznie, logiką wielowartościową lub
rozmytą oraz stopniem pewności.
Stopień pewności pozwala uwzględnić wiedzę heurystyczną,
intuicyjnÄ…, przybli\
onÄ….
KÄ…zdemu faktowi i ka\
dej regule przyporzÄ…dkowany jest
współczynnik pewności (certainity factor, CF) z przedziału
[-1,1], przy czym:
-1 oznacza, \
e fakt lub reguła jest nieprawdziwa,
-1 oznacza, \
e fakt lub reguła jest nieprawdziwa,
0 oznacza, \
e stopień prawdziwości faktu lub reguły jest nieokreślony,
+1 oznacza, \
e fakt lub reguła jest prawdziwa.
Przy wnioskowaniu reguły wybierane są w kolejności zale\
nej
od stopnia ich prawdziwości.
Współczynniki pewności faktów są określone a priori lub te\

sÄ… zdefiniowane przez u\
ytkownika.
Współczynniki pewności wniosków są wyznaczane na podsta-
wie współczynników pewności przesłanek oraz współczynnika
pewności reguły, z której wynikają.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Maszyna wnioskujÄ…ca
Maszyna wnioskujÄ…ca (kontroler wywodu, inference engine)
jest to program prowadzÄ…cy wnioskowanie.
Na podstawie faktów i reguł maszyna wnioskująca generuje
nowe fakty będące odpowiedziami na pytania u\
ytkownika.
Podstawową zasadą wnioskowania jest reguła modus
ponens,
( A Ò! B ) , A
      
      
B
Wnioskowanie mo\
e być prowadzone:
" bez hipotezy - generowanie nowych faktów tak długo,
a\
zostanÄ… odpalone wszystkie mo\
liwe reguły;
Pytanie  Co wynika z XXX ?
" z hipotezÄ… - weryfikacja (udowodnienie) konkretnej
hipotezy na podstawie faktów zawartych w bazie wiedzy;
Pytanie  Czy jest prawdÄ…, \
e XXX ?
© F.A. Dul 2007
10.10. Systemy ekspertowe
Podstawowe algorytmy wnioskowania:
" w przód;
 wnioskowania z hipotezÄ… lub bez.
" wstecz;
 tylko wnioskowania z hipotezÄ….
" mieszane;
 rodzaj wnioskowania przełączany w zale\
ności od reguły.
Algorytm wnioskowania
Algorytm wnioskowania
" Znalezienie kolejnej reguły mo\
liwej do odpalenia,
 kolejność wyboru reguł zale\
y od przyjętej strategii
" Odpalenie reguły,
" Dodanie uzyskanych wniosków do bazy wiedzy,
" Koniec gdy:
" znaleziono odpowiedz
(wnioskowanie z hipoteza),
" gdy wszystkie reguły zostały odpalone (bez hipotezy).
© F.A. Dul 2007
10.10. Systemy ekspertowe
Przykład wnioskowania
Baza reguł:
Baza faktów
R1: P '" Q Ò! S
'" Ò!
'" Ò!
'" Ò!
BF = { P, Q , R }
R2: S '" T Ò! U
'" Ò!
'" Ò!
'" Ò!
R3: R Ò! T
Ò!
Ò!
Ò!
R4: S '" R Ò! V
'" Ò!
'" Ò!
'" Ò!
Wnioskowanie w przód Wnioskowanie wstecz
Hipoteza: V
Mo\
na odpalić reguły R1 i R3.
Czy V " BF ? NIE
Odpalenie reguły R1;
Hipoteza jest wnioskiem R4
4
Wynik BF = { P , Q , R , S }
Wynik BF = { P , Q , R , S }
Nale\
y sprawdzić jej przesłanki:
Mo\
na odpalić reguły R3 i R4
Czy S " BF ? NIE
Odpalenie reguły R3;
Hipoteza robocza: S
Wynik BF = { P , Q , R , S , T } Hipoteza robocza jest wnioskiem R1
Nale\
y sprawdzić jej przesłanki:
Mo\
na odpalić reguły R2 i R4
Czy P " BF ? TAK
Odpalenie reguły R3;
Czy Q " BF ? TAK
Wynik BF = { P , Q , R , S , T , U }
Odpalić regułę R1
Mo\
na odpalić regułę R4
Hipoteza robocza S została
Odpalenie reguły R4;
udowodniona, BF = { P , Q , R , S }
Wynik BF = { P , Q , R , S , T , U , V }
Czy R " BF ? TAK
Odpalić regułę R4
Hipoteza V została udowodniona, BF = { P , Q , R , S , V }
© F.A. Dul 2007
10.10. Systemy ekspertowe
Szkielety systemów ekspertowych
Zamiast tworzyć systemy ekspertowe od podstaw, u\
ywa siÄ™
gotowych szkieletów systemów ekspertowych (expert system
shell).
Szkielet to system ekspertowy bez bazy wiedzy.
Popularnym systemem szkieletowym jest EMYCIN, który
powstał z pełnego systemu MYCIN.
Najpopularniejsze szkielety systemów ekspertowych:
- CLIPS,
- CLIPS,
- JESS,
- MANDRAX.
Języki systemów ekspertowych
Klasycznym językiem u\
ywanym przy tworzeniu systemów
ekspertowych są języki Prolog i LISP.
Języki te posiadają wbudowane mechanizmy wnioskowania
logicznego.
Niektóre języki, np. Sphinx mają wbudowane szkieletowe
systemy ekspertowe.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Zalety stosowania systemów ekspertowych:
" Naturalna reprezentacja wiedzy, Å‚atwa do zrozumienia
przez u\
ytkownika systemu;
" A
atwość modyfikacji i rozbudowy bazy wiedzy;
" Mo\
liwość przyrostowego tworzenia systemu;
" Porządkowanie i kodyfikowanie wiedzy ekspertów;
" Rozwiązywanie specjalistycznych problemów jakościowych
w których istotne jest doświadczenie;
" Zwiększenie dostępności fachowej ekspertyzy  dobra
" Zwiększenie dostępności fachowej ekspertyzy  dobra
rzadkiego i kosztownego.
" A
ączą wiedzę wielu ekspertów, mogą więc przewy\
szać
wiedzÄ… pojedynczego eksperta;
" Stabilność i powtarzalność ekspertyz;
" Niezale\
ność ekspertyz od czynników zewnętrznych;
© F.A. Dul 2007
10.10. Systemy ekspertowe
Niektóre zastosowania systemów ekspertowych:
" diagnozowanie chorób,
" poszukiwanie złó\
minerałów,
" identyfikacja struktur molekularnych,
" udzielanie porad prawnych,
" diagnozy problemów eksploatacyjnych (np.
nieprawidłowego działania urządzeń),
" dokonywanie wycen i kalkulacji kosztów przez firmy
ubezpieczeniowe,
ubezpieczeniowe,
" prognozowanie pogody,
" sterowanie robotami, pojazdami automatycznymi,
samolotami, statkami kosmicznymi,
" analiza notowań giełdowych,
" doradztwo personalne, ...
© F.A. Dul 2007
10.10. Systemy ekspertowe
Systemy ekspertowe w medycynie
" MYCIN (1972) Stanford University
System diagnozujÄ…cy zaka\
enia krwi i pomagający dobrać
właściwy antybiotyk.
" PUFF (1979)
System pomocy przy diagnozie niewydolności płuc.
" INTERNIST / CADUCEUS (1974 / 1984)
Wspomaganie diagnoz większości chorób wewnętrznych.
" BABY
" BABY
Monitorowanie intensywnej opieki medycznej noworodków
Monitorowanie intensywnej opieki medycznej noworodków
" QMR (1988) (Quick Medical Record)
Wspomaga diagnozy ponad 4000 chorób
© F.A. Dul 2007
10.10. Systemy ekspertowe
Systemy ekspertowe w chemii, biologii i rolnictwie
" DENDRAL (1964) Stanford University
System wspomagajÄ…cy wyznaczanie struktury molekularnej
czÄ…stek chemicznych na podstawie danych ze spektrometru
masowego.
" CRYSALIS (1979)
System wspomagający identyfikację struktury białek na podstawie
analizy widmowej i map gęstości elektronowej.
" CASD
System wspomagajÄ…cy analizÄ™ reakcji chemicznych.
System wspomagajÄ…cy analizÄ™ reakcji chemicznych.
" MOLGEN
Planowanie eksperymentów z DNA w genetyce molekularnej.
" PLANT/ds
Diagnozy chorób soi.
" PLANT/cd
Diagnozy strat w uprawach kukurydzy spowodowanych przez
gÄ…sienicÄ™ zbo\
ówkę.
© F.A. Dul 2007
10.10. Systemy ekspertowe
Systemy ekspertowe w innych dziedzinach
" PROSPECTOR (1978) Stanford University
System dla geologów; pomaga w znajdywaniu rud metali.
" DESIGN ADVISOR (1989)
Wspomaganie projektowania układów scalonych.
" TOP SECRET (1989)
Klasyfikacja tajnej dokumentacji dotyczÄ…cej broni jÄ…drowej.
" R1/XCON (1978) Carnegie-Mellon University
Wspomaganie projektowania komputerów VAX w firmie DEC.
Wspomaganie projektowania komputerów VAX w firmie DEC.
" MACSYMA (1968)
System algebry symbolicznej.
" GATES (1988)
System wspomagania kontroli ruchu lotniczego na lotnisku JFK.
Pomaga przydzielać bramki startującym i lądujący samolotom.
" INVEST (1985) Karlsruhe Universitat
System doradztwa inwestycyjnego dla banków.
" LENDING ADVISOR / UNDERWRITING ADVISOR (1987)
System konsultacyjny dla banków i firm ubezpieczeniowych;
Doradza przy szacowaniu ryzyka inwestycyjnego.
© F.A. Dul 2007
Systemy ekspertowe
Systemy ekspertowe znajdujÄ… szerokie zastosowanie
w wielu obszarach działalności człowieka: chemii,
medycynie, biologii, bankowości, wojsku, lotnictwie,
projektowaniu i innych.
Systemy ekspertowe sprawdzają się zwłaszcza
w takich dziedzinach jak np. medycyna, w których
brak modeli rekompensowany jest ogromnÄ… wiedzÄ…
brak modeli rekompensowany jest ogromnÄ… wiedzÄ…
praktyczną, opartą na statystyce i doświadczeniu
gromadzonym przez wielu specjalistów w długim
okresie czasu.
Zaawansowane systemy ekspertowe często górują
jakością formułowanych diagnoz nad ekspertami -
ludz
mi.
© F.A. Dul 2007
Podsumowanie
" Reprezentacja wiedzy wymaga ontologii ogólnej obejmującej
ró\
ne obszary wiedzy.
" Ontologia wy\
sza opiera siÄ™ na kategoriach oraz rachunku
zdarzeń.
" Działania, zdarzenia i czas mogą być reprezentowane
zarówno w rachunku sytuacji, jak i bardziej ekspresyjnym
rachunku zdarzeń lub procesów.
" Stany mentalne agenta mogą być reprezentowane
" Stany mentalne agenta mogą być reprezentowane
za pomocą łańcuchów przekonań.
" Sieci semantyczne oraz logika opisowa słu\
Ä… do reprezentacji
kategorii.
" Zało\
enie świata zamkniętego umo\
liwia pominięcie du\
ej
ilości informacji negatywnych.
" Do efektywnej aktualizacji wiedzy słu\
Ä… systemy
utrzymywania prawdy.
" Systemy ekspertowe wykorzystujÄ… szeroko ontologiÄ™ wy\
szÄ…
do reprezentacji wiedzy ogólnej i szczegółowej.
© F.A. Dul 2007