Pokaż źródło strony

Ostatnie zmiany Indeks

AIwiki

Strona Główna

Dla Studentów

Zima / Winter 2021:

Computer Science: Introduction to AI
ISI: Podstawy Sztucznej Inteligencji

Old specialized AI courses

SMaDA/SMaIDA/AIDA

1. semester:

2. semester:

WSHOP -- Development Workshop

Informatyka (EAIiIB)

1. rok:

2. i 3. rok:

4. rok:

Systemy i technologie wirtualizacji

Studia Dr

HeKatE

Public

The KESE workshop (EN only)
Mindstorms (archive)

KRR: Logiki Deskrypcyjne

Tematem laboratorium są logiki deskrypcyjne (ang. Description Logics). W zakres ćwiczeń wchodzą następujące tematy:

DL jako formalizm reprezentacji wiedzy
Struktura bazy wiedzy w DL
Zadania wnioskowania dla DL
Wsparcie narzędziowe

1 Reprezentacja wiedzy z użyciem Logik Deskrypcyjnych

1.1 Wprowadzenie

Logiki deskrypcyjne (opisowe) (ang. Description Logics, DL) są rodziną formalizmów reprezentacji wiedzy.
Elementami reprezentacji są pojęcia (klasy), role (relacje) i instancje (obiekty ¹⁾).
Logiki opisowe są koncepcyjnie powiązane z sieciami semantycznymi (ang. semantic networks) i ramami (ang. frames), jednak w przeciwieństwie do nich, przez swoje powiązanie z logiką pierwszego rzędu, posiadaję formalnie zdefiniowaną semantykę i zapewniają możliwość automatycznego wnioskowania.
Intuicyjnie można powiedzieć, że logiki opisowe łączą paradygmat obiektowy (ramy, sieci semantyczne) z logiką (rachunek predykatów, logika 1. rzędu).

Przykład 1: graf obrazujący zbiór obiektów powiązanych relacjami i należących do pewnych klas:

Wybrane fragmenty ww. grafu zapisane w logice opisowej:

$Fred : person$ , $Tibbs: cat$ , $(Fred, Tibbs) : has\_pet$
$man \equiv person \sqcap adult \sqcap male$ , $cat\_liker \equiv person \sqcap \exists likes.cat$
$(cat\_liker, cat) : likes$ , $(sheep, grass) : eats\_only$
$cat \sqsubseteq animal$ , $sheep \sqsubseteq animal \sqcap \forall eats.grass$

1.2 Co możemy zapisać z użyciem Logik Deskrypcyjnych

W logikach opisowych możemy konstruować zdania o pojęciach i instancjach. Poniżej przedstawiono podstawowe rodzaje wyrażeń w logice opisowej i ich intuicyjne wytłumaczenia:

Instancje (obiekty):

przynależność obiektu do klasy (ang. concept assertions), np:
- $Fred : person$ - Fred jest osobą
- $Tibbs : cat$ - Tibbs jest kotem
relacja między dwoma obiektami
- $(Fred, Tibbs) : has\_pet$ - Fred ma zwierzę, którym jest Tibbs

Pojęcia

definicje pojęć (warunki konieczne i wystarczające), np.
- $man \equiv person \sqcap adult \sqcap male$ - Mężczyzna to dorosła osoba rodzaju męskiego
- $cat\_liker \equiv person \sqcap \exists likes.cat$ - Miłośnik kotów to osoba, która lubi (jakiegoś) kota
relacje między pojęciami (klasami)
- $(cat\_liker, cat) : likes$ - (każdy) miłośnik kotów lubi (jakiegoś) kota
- $(sheep, grass) : eats\_only$ - (każda) owca je tylko trawę
aksjomaty
- $cat \sqsubseteq animal$ (każdy) kot jest zwierzęciem (hierarchia pojęć)
- $sheep \sqsubseteq animal \sqcap \forall eats.grass$ owce to zwierzęta, które jedzą tylko trawę (warunek konieczny, ale nie wystarczający)

Ćwiczenie 1: Wypisz z grafu z przykładu 1 wszystkie:

pojęcia (klasy),
role (relacje),
instancje (obiekty).

Odpowiedzi: lab_dl_answers

1.3 Podstawowy język DL

W języku logiki opisowej tworzymy opisy.
Podstawowe elementy języka to: atomicze pojęcia i atomiczne role.
Złożone opisy tworzy się indukcyjnie za pomocą konstruktorów.
Poszczególne języki DL różnią się między sobą zbiorem dopuszczalnych konstruktorów
Najprostszy język to AL (ang. Attributive Language)

Składnia AL

atomiczne pojęcia ( $A, B, ...$ )
atomiczne role ( $R, S, ...$ )
opisy ( $C, D, ...$ ); mogą nimi być:
- $A$ - pojęcie atomiczne
- $\top$ - top concept, pojęcie uniwersalne oznaczające „wszystko”
- $\bot$ - bottom concept, pojęcie puste, oznaczające „nic”
- $\neg A$ - negacja
- $C \sqcap D$ - koniunkcja
- $\forall R.C$ - kwantyfikator uniwersalny: „dla każdego”
- $\exists R.\top$ - kwantyfikator egzystencjalny/szczegółowy: „istnieje”

Semantyka AL

Semantyka zdefiniowana jest poprzez interpretację składającą się z:

dziedziny intepretacji: $\Delta^{\mathcal{I}}$ - niepustego zbioru, na który mapowane są symbole i relacje
funkcji interpretacji, która przypisuje:
- każdemu atomicznemu pojęciu zbiór: $A \rightarrow A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}$
- każdej atomicznej roli relację binarną: $R^{\mathcal{I}} \rightarrow \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}$

Konstruktor	Składnia	Semantyka
pojęcie atomiczne (atomic concept)	$A$	$A^{\mathcal{I}} = A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}$
atomiczna rola (atomic role)	$R$	$R^{\mathcal{I}} = R^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}$
pojęcie uniwersalne (universal concept)	$\top$	$\top^{\mathcal{I}} = \Delta^{\mathcal{I}}$
pojęcie puste (bottom concept)	$\bot$	$\bot^{\mathcal{I}} = \emptyset$
(atomic negation)	$\neg A$	$(\neg A)^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus A^{\mathcal{I}}$
koniunkcja/przecięcie (intersection)	$C \sqcap D$	$(C \sqcap D)^{\mathcal{I}} = C^{\mathcal{I}} \cap D^{\mathcal{I}}$
ograniczenie wartości (value restriction)	$\forall R.C$	$(\forall R.C)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \forall b, (a,b) \in R^\mathcal{I} \rightarrow b \in C^{\mathcal{I}} \rbrace$
ograniczony kwantyfikator egzystencjalny (limited existential quantification)	$\exists R.\top$	$(\exists R.\top)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \exists b, (a,b) \in R^\mathcal{I} } \rbrace$

Przykład 2:

pojęcia atomiczne: Person, Female, Elephant uwaga: dopóki nie zapisze się tego explicite, pomiędzy pojęciami nie występują żadne relacje. Są to po prostu oznaczenia jakichś zbiorów
- osoba rodzaju żeńskiego: $Person \sqcap Female$
- słonica: $Elephant \sqcap Female$
- osoba, które nie jest rodzaju żeńskiego: $Person \sqcap \neg Female$
atomiczna rola: hasChild
- osoba, która ma (jakieś) dziecko/dzieci: $Person \sqcap \exists hasChild. \top$
- osoba, której wszystkie dzieci są rodzaju zeńskiego $Person \sqcap \forall hasChild.Female$
- osoba bezdzietna $Person \sqcap \forall hasChild. \bot$

1.4 Rodzina języków DL

Poszczególne języki DL rozróżniamy poprzez konstruktory, które dopuszczają. Przykładowe konkstruktory:

$\mathcal{U}$ - suma : $(C \sqcup D)^\mathcal{I} = C^\mathcal{I} \cup D^\mathcal{I}$
$\mathcal{E}$ - pełny kwantyfikator egzystencjalny : $(\exists R.C)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \exists b, (a,b) \in R^\mathcal{I} \land b \in C^{\mathcal{I}} \rbrace$
$\mathcal{N}$ - ograniczenia liczbowe:
- $(\geq n R)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \arrowvert { \mid\lbrace b \mid (a,b) \in R^\mathcal{I} \rbrace \mid \geq n } \rbrace$
- $(\leq n R)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \arrowvert { \mid\lbrace b \mid (a,b) \in R^\mathcal{I} \rbrace \mid \leq n } \rbrace$
$\mathcal{C}$ - negacja : $( \neg C)^\mathcal{I} = \Delta^\mathcal{I} \setminus C^\mathcal{I}$

Używające powyższych konstruktorów języki nazywają się odpowiednio:

$\mathcal{ALU}$
$\mathcal{ALE}$
$\mathcal{ALN}$
$\mathcal{ALC}$ → odpowiada podzbiorowi logiki pierwszego rzędu ograniczonemu do formuł z dwoma zmiennymi

Ćwiczenie 2

Rozważmy interpretację: I = (∆, ·I ), gdzie

$\Delta I = \{John,Suzan,Max,Helen,Natalie,Nick\}$ ,
$Human^I = \{John,Suzan,Helen,Natalie,Nick\}$ ,
$Male^I = \{John, Max, Nick\}$ ,
$Dog^I = \{Max\}$ ,
$Doctor^I = \{John, Helen\}$ ,
$areFriends^I = \{(Suzan,Helen),(Helen,Suzan),(Natalie,Helen),(Helen,Natalie),$ $(Suzan, Natalie), (Natalie, Suzan), (Natalie, Nick), (Nick, Natalie) \}$ ,
$areMarried^I = \{(Suzan, John), (John, Suzan)\}$ ,
$hasPet^I = \{(Suzan, Max), (John, Max)\}$ .

Przedstaw powyższą interpretację w postaci grafu.
Zapisz następujące opisy w logice deskrypcyjnej:
1. Ci którzy są w związku małżeńskim z doktorem i posiadający psa jako zwierzę domowe.
2. Ci którzy nie są w związku małżeńskim, a wszyscy ich przyjaciele są albo kobietami albo mężczyznami w związkach małżeńskich.
3. Wyznacz rozszerzenie powyższych pojęć w interpretacji I (sprawdź czy/kto w podanej interpretacji zalicza się do tych grup).
Zapisz następujące pojęcia w postaci aksjomatów (postaci $A \sqsubseteq B$ ) języka $ALC$ :
1. Ci, którzy nie mają męskich przyjaciół, nie mają zwierząt domowych.
2. Wszyscy mężczyźni są albo w związku małżeńskim albo mają nie-męskiego przyjaciela.
3. Czy te aksjomaty są prawdziwe w danej interpretacji?

Odpowiedzi: reprezentacja_-_zadanie

1.5 Powiązanie z innymi rachunkami (logicznymi)

Większość logik opisowych jest podzbiorem logiki pierwszego rzędu
- nazwy pojęć ⇔ predykaty unarne
- relacje (atomiczne) ⇔ predykaty binarne
- pojęcia ⇔ formuły z jedną wolną zmienną
Formuły logiki opisowej można intuicyjnie interpretować poprzez analogię do algebry zbiorów

Przykład użycia	Składnia DL	Składnia FOL	Algebra zbiorów
Mężczyzna to dorosły i osoba i rodzaju męskiego	$C_{1} \sqcap ... \sqcap C_{n}$	$C_{1}(x) \land ... \land C_{n}(x)$	$C_{1} \cap ... \cap C_{n}$
Gazeta to dziennik lub czasopismo	$C_{1} \sqcup ... \sqcup C_{n}$	$C_{1}(x) \lor ... \lor C_{n}(x)$	$C_{1} \cup ... \cup C_{n}$
Wszystko, co jedzą wegetarianie to nie mięso	$\neg C$	$\neg C(x)$	$C^c$ (dopełnienie zbioru)
Kraje UE to: Niemcy, Francje, …, Polska	$\lbrace x_{1} \rbrace \sqcup ... \sqcup \lbrace x_{n} \rbrace$	$x=x_{1} \lor ... \lor x=x_{n}$	$\lbrace x_{1} \rbrace \cup ... \cup \lbrace x_{n} \rbrace$
Każde zwierzę, które ma starsza pani to kot	$\forall P.C$	$\forall y.P(x,y) \rightarrow C(y)$	$\pi_Y(P) \subseteq C$
Właściciel psa ma jakiegoś psa	$\exists P.C$	$\exists y.P(x,y) \land C(y)$	$\pi_Y(P) \cap C \neq \emptyset$ (Π - projekcja)
Rozsądny mężczyzna spotyka się z maksymalnie 1 kobietą równocześnie	$\leq nP$	$\exists^{\leq n}y.P(x,y)$	$card(P)\leq n$ (card - liczność zbioru)
Miłośnik zwierzą ma minimum 3 ziwerzaki	$\geq nP$	$\exists^{\geq n}y.P(x,y)$	$card(P) \geq n$
Dziecko to to samo co młoda osoba	$C \equiv D$	$\forall x.C(x) \leftrightarrow D(x)$	$C \equiv D$
Każda foka jest zwierzęciem	$C \sqsubseteq D$	$\forall x.C(x) \rightarrow D(x)$	$C \subseteq D$

Ćwiczenie 3 (na podstawie http://pages.cs.wisc.edu/~dyer/cs540/notes/fopc.html Poniższe zdania przełożono z języka naturalnego na formuły rachunku pierwszego rzędu. Dopisz odpowiadające im zdania w logice deskrypcyjnej tam gdzie jest to możliwe.

Każdy ogrodnik lubi słońce. / Every gardener likes the sun.
1. (Ax) gardener(x) ⇒ likes(x,Sun)
Niektórych ludzi możesz nabrać zawsze. / You can fool some of the people all of the time.
1. (Ex) (person(x) ^ (At)(time(t) ⇒ can-fool(x,t)))
Czasami możesz nabrać wszystkich ludzi. / You can fool all of the people some of the time.
1. (Ax) (person(x) ⇒ (Et) (time(t) ^ can-fool(x,t)))
Wszystkie fioletowe grzyby są trujące. / All purple mushrooms are poisonous.
1. (Ax) (mushroom(x) ^ purple(x)) ⇒ poisonous(x)
Żadne fioletowe grzyby nie są trujące. / No purple mushroom is poisonous.
1. ~(Ex) purple(x) ^ mushroom(x) ^ poisonous(x)
2. (Ax) (mushroom(x) ^ purple(x)) ⇒ ~poisonous(x)
Deb nie jest wysoka. / Deb is not tall.
1. ~tall(Deb)

Odpowiedzi: lab_dl_answers

* Rozszerzenia języków DL

Podstawowym językiem jest ALC (≈ALUE). Dodatkowe litery oznaczają następujące rozszerzenia:

dotyczące konstruktorów pojęć:
- $\mathcal{F}$ ograniczenia funkcyjne (np. ≤1hasMother)
- $\mathcal{N}$ ograniczenia liczbowe (np. ≥2hasChild, ≤3hasChild)
- $\mathcal{Q}$ warunkowe ograniczenia liczbowe (np. ≥2hasChild.Doctor))
- $\mathcal{O}$ z użyciem instancji (e.g., {Italy})
dotyczące konstruktorów ról:
- koniunkcja ról: R∩S, suma ról: R∪S, role dopełniające: ¬R, łańcuchy (kompozycja) ról: R o S
- $\mathcal{I}$ role odwrotne (np. $isChildOf \equiv hasChild^{–}$ )
dodatkowe aksjomaty dot. ról:
- $\mathcal{S}$ przechodniość relacji
- $\mathcal{H}$ hierarchia relacji (e.g., $hasDaughter \sqsubseteq hasChild$ )
- $\mathcal{R}$ zawieranie się relacji: RoS ⊆ R, RoS ⊆
inne:
- $^{(\mathcal{D})}$ użycie typów danych w obrębie języka

Przykłady: Język ontologii

OWL DL jest równoważny SHOIN(D) przechodniość (S) + hierarhia ról (H) + instancje (O) + odwrotność (I) + ograniczenia liczbowe (N) + typy danych (D) = SHOIN(D)
OWL Lite jest uproszczonym podzbiorem OWL DL i odpowiada SHIF(D) przechodniość (S) + hierarchia (H) + odwrotność (I) + funkcyjność (F) + typy danych (D)= SHIF(D)
OWL2 - ekspresywny język ontologii równoważny SROIQ(D) R - zawieranie się relacji (RoS ⊆ R, RoS ⊆ S)

BONUS:

Złożoność obliczeniowa wnioskowania w poszczególnych językach DL zależy od ich siły ekspresji: zobacz przewodnik po językach DL

2 Struktura bazy wiedzy opartej na logice opisowej

Baza wiedzy w logice opisowej składa się z:

Terminologii, tzw. TBox (ang. terminology box), zawierającej aksjomaty dot. pojęć, w tym definicje
Zbioru twierdzeń , tzw. ABox (ang. assertion box) - zawierającego twierdzenia o pojedynczych obiektach

2.1 Terminologia (TBox)

Składnia:

TBox to skończony zbiór aksjomatów terminologicznych postaci:
- $C \sqsubseteq D$
- $R \sqsubseteq S$
- $C \equiv D$
- $R \equiv S$
Definicje to równości, które po lewej stronie mają pojęcie atomiczne

Semantyka:

funkcja interpretacji $\mathcal{I}$ mapuje każde pojecie na podzbiór dziedziny
interpretacja spełnia aksjomat $C \sqsubseteq D$ jeżeli: $C^{\mathcal{I}} \subseteq D^{\mathcal{I}}$ ; analogicznie w przypadku relacji $R \sqsubseteq S$
interpretacja I spełnia definicję $C \equiv D$ jeżeli: $C^{\mathcal{I}} = D^{\mathcal{I}}$ ; analogicznie w przypadku relacji $R \equiv S$
interpretacja spełnia terminologię (TBox) jeżeli spełnia wszystkie jej aksjomaty. Mówimy wtedy, że I jest modelem T.

Ćwiczenie 4: Używając pojęć: „Przedmiot”, „Wykładowca”, „Mgr” i „Inż” oraz ról „prowadzi” i „maTytuł” przedstaw poniższą wiedzą w postaci TBoxa:

Każdy kto prowadzi przedmiot musi mieć albo stopień magistra albo być wykładową.
Każdy wykładowca ma tytuł inżyniera.
Każdy wykładowca prowadzi jakiś przedmiot.
Każdy posiadający tytuł magistra ma też tytuł inżyniera.

Odpowiedzi: tbox

2.2 Opis świata (ABox)

Składnia: ABox zawiera wiedzę o instancjach (obiektach występujących w opisywanym świecie), w tym:

stwierdzenia o przynależności do klasy tzw. concept assertions np. a : C
stwierdzenia o relacjach między obiektami tzw. role assertions np. (b,c) : R

Semantyka:

funkcja interpretacji mapuje każdą nazwę na element dziedziny.
interpretacja spełnia (względem terminologii T):
- a : C wtw gdy $a^{\mathcal{I}} \in C^{\mathcal{I}}$
- (b,c) : R wtw gdy $(b^{\mathcal{I}}, c^{\mathcal{I}}) \in R^{\mathcal{I}}$
- ABox wtw gdy spełnia wszystkie jego stwierdzenia. Mówimy wtedy, że I jest modelem A.

Ćwiczenie 5 Dany jest następujący opis świata (ABox):

(john,susan): friend
(john,andrea): friend
(susan,andrea): loves
(andrea,bill): loves
susan: Female
bill: ¬Female

Wypisz relacje, klasy i obiekty.
Przedstaw ww. ABox w postaci grafu.
Zapisz następujące stwierdzenie: „John ma przyjaciółkę (przyjaciela rodzaju żeńskiego), które jest zakochana w mężczyźnie (osobie niebędącej rodzaju żeńskiego)” w postaci john : X, gdzie X jest odpowiednim opisem.

Odpowiedzi: abox

3 Wnioskowanie w logikach deskrypcyjnych

Logiki opisowe, dzięki formalnemu ugruntowaniu w logice, umożliwiają automatyczne wnioskowanie.
Osobne zadania wnioskowania definiuje się dla TBoxa i ABoxa.
W logikach opisowych stosuje sią Założenie o otwartości świata.
Podstawowymi algorytmami dla DL są:
- algorytmy strukturalne (Structural subsumption algorithms)
- algorytmy tableau (Tableau algorithms)
Złożoność obliczeniona poszczególnyc zadań wnioskowania zależy od siły ekspresji języka DL
- zobacz przewodnik po językach DL
- Przykładowe wyniki dla zadania subsumcji:

3.1 Zadania wnioskowania dla TBoxa

Spełnialność (ang. satisfiability)
- Pojęcie C jest spełnialne względem terminologii T jeżeli istnieje model (interpretacja) I taki że $C^{\mathcal{I}}$ jest niepusty.
Subsumcja ²⁾ (ang. subsumption)
- Pojęcie C jest włączone w pojęcie D wzg. T jeżeli $C^{\mathcal{I}} \subseteq D^{\mathcal{I}}$ dla każdego modelu I terminologii T.
Równoważność (ang. equivalence)
- Dwa pojęcia C i D są sobie równoważne wzg. T jeżeli $C^{\mathcal{I}} = D^{\mathcal{I}}$ dla każdego modelu I terminologii T.
Rozłączność (ang. disjointness)
- Dwa pojęcia C i D są rozłączne wzg. T. jeżeli $C^{\mathcal{I}} \cap D^{\mathcal{I}} = \emptyset$ dla każdego modelu I terminologii T.

Ćwiczenie 6

Wiedząc, że:
- $Vegetarian \equiv (\forall eats.(\neg (\exists partOf.Animal))) \sqcap (\forall eats.(\neg Animal)) \sqcap Animal$
- $Cow \sqsubseteq Vegetarian$
- $MadCow \equiv \exists eats.(\exists partOf.Sheep \sqcap Brain) \sqcap Cow$
  Odpowiedz na pytanie:
1. Jakiemu pojęciu jest równoważne pojęcie MadCow?
Wykorzystując bazę wiedzy z sekcji terminologia_tbox odpowiedz na pytanie:
1. Czy zdanie„ „Każdy kto prowadzi przedmiot musi mieć tytuł inżyniera” jest logiczną konsekwencją tej bazy wiedzy? Odpowiedź uzasadnij.

3.2 Zadania wnioskowania dla ABoxa

Sprawdzenie spójności (ang. consistency checking)
- ABox A jest spójny wzg. terminologii T, jeżeli istnieje nterpretacja I będąca jednocześnie modelem A i T.
Sprawdzanie instancji (ang. instance checking)
- $A \models \alpha$ iff każda interpretacja spełniająca A spełnia również α.
Poszukiwanie najbardziej szegółowego pojęcia dla danej instancji (ang. realization).
Poszukiwanie instancji danego pojęcia (ang. retrieval).

Uwaga:

wszystkie zadania TBox mogą być zredukowane do zadania subsumcji lub spełnialności
- C i D są rozłączne ⇔ $C \sqcap D$ zawiera się w ⊥
- np. C zawiera się D ⇔ $C \sqcap \neg D$ nie jest spełnialne (na tej obserwacji opierają się algorytmy tableau)
wszystkie zadania wnioskowania mogą być sprowadzone do sprawdzenia spójności bazy wiedzy.

Ćwiczenie 7:

Wiedząc, że:
- $OldLady \equiv Elderly \sqcap Female \sqcap Person$
- $OldLady \sqsubseteq \exists hasPet.Animal$ $\sqcap$ $\forall hasPet. Cat$
- $hasPet(Minnie,Tom)$ , $Elderly(Minnie)$ , $Female(Minnie)$
  Odpowiedz na pytania:
1. Czy każda starsza pani musi mieć kota? Dlaczego?
2. Do jakiej klasy należy obiekt Minnie?
3. Do jakiej klasy należy obiekt Tom?
Rozważ opis świata z sekcji abox i odpowiedz na pytanie:
- Czy John należy do klasy: ∃friend.(Female ⊓ ∃loves.¬Female)?
- Podpowiedź:
  - Zwizualizuj w postaci grafu ten ABox, zaobserwuj, do jakich klas należą poszczególne obiekty.
  - Rozważ dwa przypadki: andrea : Female i andrea : ¬Female

Odpowiedzi: wnioskowanie

3.3 Założenie o otwartości świata

Analogia bazy wiedzy DL i relacyjnej bazy danych:
- schemat bazy danych ↔ TBox
- instancje danych ↔ ABox
W przeciwieństwie do relacyjnych baz danych, brak w ABox oznacza brak wiedzy, nie zaś negatywnąinformację
ABox reprezentuje potencjalnie nieskończenie wiele interpretacji.
Semantyka otwartego świata wymaga nietrywialnych mechanizmów wnioskowania, a realizaja zapytań jest bardziej skomplikowana.

BONUS:

Więcej przykładów wnioskowania...

3.4 Algorytmy wnioskowania

Strukturalne

Porównują strukturę składniową pojęć. Są efektywne, ale odpowiednie tylko do prostych języków, np. nie działają dla języków z negacją i dysjunkcją

Tableau

Opierają swoje działanie na obserwacji, że: $C \sqsubseteq D$ wtw. gdy wyrażenie $C \sqcap \neg D$ jest niespełnialne. Schemat działania:

Start od faktów (aksjomatów ABox)
Dekompozycja składniowa z użyciem odpowiednich reguł tzw. tableaux expansion rules
- reguły odpowiadają poszczególnymkonstruktorom ( $\sqcap, \sqcup, ...$ )
- niektóre reguły są niedeterministyczne (np. $\sqcup, \leq$ ) (w praktyce prowadzi to do przeszukiwania)
Wnioskowanie o ograniczeniach na elementach modelu
Stop, kiedy nie można zastosować więcej reguł lub wystąpiła sprzeczność

Ćwiczenie 8 (dla chętnych):

Sprawdź czy poniższe pojęcia są spełnialne:

A ⊓ ∃R.C ⊓ ∀R.D
∃R.C ⊓ ∀R.¬(C ⊓ D)
A⊓∃R.C⊓∀R.D⊓∀R.¬(C⊓D)
∃R.(A ⊓ ∃R.C) ⊓ ∀R.¬C
∃R.(A ⊓ ∃R.C) ⊓ ∀R.∀R.¬C
¬C ⊓ ∃R.C ⊓ ∀R.(¬C ⊔ ∃R.C)
A ⊓ ∀R.A ⊓ ∀R.¬∃P.A ⊓ ∃R.∃P.A

Przykładowe rozwiązania z użyciem algorytmu tableau: tutaj.

3.5 Wsparcie narzędziowe

Istnieje wiele implementacji silników wnioskujących dla logik deskrypcyjnych. Niektóre z nich są zoptymalizowane pod kątem konkretnych języków DL (np. takich na których opierają się warianty języka ontologii OWL ).

Lista dostępnych silników wnioskujących dostępna jest na stronie: Prof. U. Sattler. Popularne narzędzia to m.in:

Najczęściej silniki wnioskujące zintegrowane są z innymi narzędziami, np. edytorami ontologii (pełnią one wówczas rolę pomocniczą, np. do sprawdzania spójności ontologii itp.).

Ćwiczenie 9:

Pobierz silnik wnioskujący Pellet.
1. Na borgu powinien być w /usr/local/pellet.
Uruchom go wpisując w konsoli pellet.sh help i zapoznaj się z dostępnymi opcjami. (/usr/local/pellet/pellet.sh)
Uruchom pellet.sh consistency <ontology> gdzie <ontology> jest bazą wiedzy people+pets.owl umieszczoną w katalogu examples/data.
Jakie są rezultaty?
Uruchom pellet.sh classify <ontology> dla powyższej ontologii peopl+pets.owl
Jakie są rezultaty?

Materiały

Wykłady, prezentacje

DL Course by Enrico Franconi

DL Tutorial

Description Logics—Basics, Applications, and More

DL by Obitko

Introduction to DL (handbook)

Kursy

DL Course by Enrico Franconi
by I.Horrocks
- Lectures:
  - Intro to DL
  - DL reasoning
- Labs:
  - DL reasoning: HTML, PDF
  - Exam - zadania z DL
Rector
- Lectures: Handouts
- Lab: Handouts
SemWeb course in London, 2012

Narzędzia

¹⁾

Nazwy w nawiasach używane są zwykle w ontologiach zapisanych w języku OWL, opartym na formalizmie DL

²⁾

subsumcja (sub- + sumere ‘brać’) log. proces wynajdowania dla danego pojęcia innego pojęcia, bardziej ogólnego. Wg. „Słownik Wyrazów Obcych” Wydawnictwa Europa, pod redakcją naukową prof. Ireny Kamińskiej-Szmaj, autorzy: Mirosław Jarosz i zespół. ISBN 83-87977-08-X. Rok wydania 2001.

pl/dydaktyka/krr/lab_dl.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)

Pokaż źródło strony Poprzednie wersje

Menadżer multimediów Do góry