====== 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
===== - Reprezentacja wiedzy z użyciem Logik Deskrypcyjnych =====
==== - 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 ((Nazwy w nawiasach używane są zwykle w ontologiach zapisanych w języku OWL, opartym na formalizmie DL))).
* 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:
{{ :pl:dydaktyka:krr:dl-example-picture.png |}}
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
==== - 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]]
==== - 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
==== - 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:
- Ci którzy są w związku małżeńskim z doktorem i posiadający psa jako zwierzę domowe.
- 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.
- 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:
- Ci, którzy nie mają męskich przyjaciół, nie mają zwierząt domowych.
- Wszyscy mężczyźni są albo w związku małżeńskim albo mają nie-męskiego przyjaciela.
- Czy te aksjomaty są prawdziwe w danej interpretacji?
Odpowiedzi: [[lab_dl_answers#reprezentacja_-_zadanie]]
==== - 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.
- (Ax) gardener(x) => likes(x,Sun)
- Niektórych ludzi możesz nabrać zawsze. / You can fool some of the people all of the time.
- (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.
- (Ax) (person(x) => (Et) (time(t) ^ can-fool(x,t)))
- Wszystkie fioletowe grzyby są trujące. / All purple mushrooms are poisonous.
- (Ax) (mushroom(x) ^ purple(x)) => poisonous(x)
- Żadne fioletowe grzyby nie są trujące. / No purple mushroom is poisonous.
- ~(Ex) purple(x) ^ mushroom(x) ^ poisonous(x)
- (Ax) (mushroom(x) ^ purple(x)) => ~poisonous(x)
- Deb nie jest wysoka. / Deb is not tall.
- ~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. ≤1//hasMother//)
* \mathcal{N} ograniczenia liczbowe (np. ≥2//hasChild//, ≤//3hasChild//)
* \mathcal{Q} warunkowe ograniczenia liczbowe (np. ≥2//hasChild//.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 [[http://www.cs.man.ac.uk/~ezolin/dl/|przewodnik po językach DL]]
===== - 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
{{ :pl:dydaktyka:krr:dl_krs.png?500 |}}
==== - 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: [[lab_dl_answers#tbox]]
==== - 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: [[lab_dl_answers#abox]]
===== - 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ą [[http://en.wikipedia.org/wiki/Open_world_assumption|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 [[http://www.cs.man.ac.uk/~ezolin/dl/|przewodnik po językach DL]]
* Przykładowe wyniki dla zadania subsumcji:
{{ http://www.obitko.com/tutorials/ontologies-semantic-web/images/dl-complexity.gif |}}
==== - 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 ((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.)) (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:
- Jakiemu pojęciu jest równoważne pojęcie ''MadCow''?
- Wykorzystując bazę wiedzy z sekcji [[#terminologia_tbox]] odpowiedz na pytanie:
- Czy zdanie" "Każdy kto prowadzi przedmiot musi mieć tytuł inżyniera" jest logiczną konsekwencją tej bazy wiedzy? Odpowiedź uzasadnij.
==== - 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:
- Czy każda starsza pani musi mieć kota? Dlaczego?
- Do jakiej klasy należy obiekt Minnie?
- 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: [[lab_dl_answers#wnioskowanie]]
==== - 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**:
* [[http://www.cs.man.ac.uk/~horrocks/ISWC2003/Tutorial/examples.pdf|Więcej przykładów wnioskowania...]]
==== - 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: [[http://www.dcs.bbk.ac.uk/~michael/sw/slides/Sew11-8-tut.pdf|tutaj]].
==== - 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: [[http://www.cs.man.ac.uk/~sattler/reasoners.html|Prof. U. Sattler]].
Popularne narzędzia to m.in:
* [[http://clarkparsia.com/pellet/download|Pellet]]
* [[http://www.cs.man.ac.uk/~horrocks/FaCT/|FaCT]]
* [[http://www.sts.tu-harburg.de/%7Er.f.moeller/racer/|Racer]]
* [[http://www.sts.tu-harburg.de/%7Er.f.moeller/racer/Racer-1-9-2-beta-Release-Notes/release-notes-1-9-2se3.html#x4-70003.2|RacerPorter]] GUI
* [[http://blipkit.wordpress.com/2010/11/27/posh-the-prolog-owl-shell/|POSH: the prolog OWL shell]]
* [[http://code.google.com/p/dlmodel/|DL model]]
* [[http://db-tom.cs.uwaterloo.ca/AssertionRetrieval/pages/kbgen.jsp|CARE]] - online
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 [[http://clarkparsia.com/pellet/download|Pellet]].
- :!: 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 '' gdzie '''' jest bazą wiedzy ''people+pets.owl'' umieszczoną w katalogu ''examples/data''.
- Jakie są rezultaty?
- Uruchom ''pellet.sh classify '' dla powyższej ontologii ''peopl+pets.owl''
- Jakie są rezultaty?
===== Materiały =====
==== Wykłady, prezentacje ====
* [[http://www.inf.unibz.it/~franconi/dl/course/|DL Course]] by Enrico Franconi
* **[[http://www.inf.unibz.it/~franconi/dl/course/slides/prop-DL/propositional-dl.pdf|Propositional Description Logics]]** :!:
* [[http://www.inf.unibz.it/~franconi/dl/course/slides/kbs/kbs.pdf|Knowledge Bases in Description Logics]]
* [[http://www.inf.unibz.it/~franconi/dl/course/slides/logic/fol/fol-2.pdf|DL reasoning, FOL etc.]]
* [[http://www.cse.iitd.ac.in/~kkb/DL-1.pdf|DL Tutorial]]
* [[http://www.cs.man.ac.uk/~horrocks/Slides/IJCAR-tutorial/Print/p1-introduction.pdf|Description Logics—Basics, Applications, and More]]
* [[http://www.cs.put.poznan.pl/jjozefowska/wyklady/ai/Ontologie.pdf|Ontologie, Logiki deskrypcyjne]]
* [[http://www.cs.man.ac.uk/~horrocks/Slides/index.html|Horrock's Presentations]]
* [[http://www.inf.unibz.it/~franconi/dl/course/slides/db/db.pdf|DL and DB]]
* [[http://www.obitko.com/tutorials/ontologies-semantic-web/description-logics.html|DL]] by Obitko
* [[http://www.obitko.com/tutorials/ontologies-semantic-web/syntax-and-semantics.html|Syntax & Semantics]]
* [[http://www.obitko.com/tutorials/ontologies-semantic-web/translation-to-fopl.html|Translation to FOPL]]
* [[http://www.obitko.com/tutorials/ontologies-semantic-web/reasoning.html|Reasoning]]
* [[http://www.inf.unibz.it/~franconi/dl/course/dlhb/dlhb-01.pdf|Introduction to DL]] (handbook)
==== Kursy ====
* [[http://www.inf.unibz.it/~franconi/dl/course/|DL Course]] by Enrico Franconi
* [[http://www.cs.man.ac.uk/~horrocks/Teaching/cs646/|by I.Horrocks]]
* Lectures:
* {{http://www.cs.man.ac.uk/%7Ehorrocks/Teaching/cs646/Slides/pt2-dlintro.pdf|Intro to DL}}
* {{http://www.cs.man.ac.uk/%7Ehorrocks/Teaching/cs646/Slides/pt3-dlreasoning.pdf|DL reasoning}}
* Labs:
* DL reasoning: [[http://www.cs.man.ac.uk/~horrocks/Teaching/cs646/Labs/dlreasoning/|HTML]], {{http://www.cs.man.ac.uk/~horrocks/Teaching/cs646/Labs/dlreasoning.pdf|PDF}}
* [[http://www.cs.man.ac.uk/%7Ehorrocks/Teaching/cs646/Exams/dlreasoning2/|Exam]] - zadania z DL
* [[http://www.cs.man.ac.uk/~rector/modules/CS646/|Rector]]
* Lectures: [[http://www.cs.man.ac.uk/~rector/modules/CS646/Lecture-Handouts/|Handouts]]
* Lab: [[http://www.cs.man.ac.uk/~rector/modules/CS646/Lab-Handouts/|Handouts]]
* [[http://www.dcs.bbk.ac.uk/~michael/sw/sw.html|SemWeb course in London]], 2012
==== Narzędzia ====
* [[http://www.cs.man.ac.uk/~horrocks/FaCT/|FaCT]]
* [[http://www.sts.tu-harburg.de/%7Er.f.moeller/racer/|Racer]]
* [[http://www.sts.tu-harburg.de/%7Er.f.moeller/racer/Racer-1-9-2-beta-Release-Notes/release-notes-1-9-2se3.html#x4-70003.2|RacerPorter]] GUI
* [[http://blipkit.wordpress.com/2010/11/27/posh-the-prolog-owl-shell/|POSH: the prolog OWL shell]]
* [[http://code.google.com/p/dlmodel/|DL model]]
* [[http://db-tom.cs.uwaterloo.ca/AssertionRetrieval/pages/kbgen.jsp|CARE]] - online
* [[http://www.cs.man.ac.uk/~sattler/reasoners.html|More reasoners]]