|
|
pl:dydaktyka:krr:lab_dl [2013/05/31 23:03] ikaf [Literatura, materiały] |
pl:dydaktyka:krr:lab_dl [2019/06/27 15:50] |
====== 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: | |
* <latex> Fred : person </latex>, <latex> Tibbs: cat</latex>, <latex> (Tred, Tibbs) : has\_pet</latex> | |
* <latex> man \equiv person \sqcap adult \sqcap male</latex>, <latex> cat\_liker \equiv person \sqcap \exists likes.cat</latex> | |
* <latex>(cat\_liker, cat) : likes </latex>, <latex> (sheep, grass) : eats\_only</latex> | |
* <latex> cat \sqsubseteq animal</latex>, <latex> sheep \sqsubseteq animal \sqcap \forall eats.grass</latex> | |
| |
| |
==== - 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: | |
* <latex>Fred : person </latex> - Fred jest osobą | |
* <latex>Tibbs : cat</latex> - Tibbs jest kotem | |
- relacja między dwoma obiektami | |
* <latex> (Fred, Tibbs) : has\_pet</latex> - Fred ma zwierzę, którym jest Tibbs | |
| |
__Pojęcia__ | |
- definicje pojęć (warunki konieczne i wystarczające), np. | |
* <latex> man \equiv person \sqcap adult \sqcap male</latex> - Mężczyzna to dorosła osoba rodzaju męskiego | |
* <latex> cat\_liker \equiv person \sqcap \exists likes.cat</latex> - Miłośnik kotów to osoba, która lubi (jakiegoś) kota | |
- relacje między pojęciami (klasami) | |
* <latex> (cat\_liker, cat) : likes</latex> - (każdy) miłośnik kotów lubi (jakiegoś) kota | |
* <latex> (sheep, grass) : eats\_only</latex> - (każda) owca je tylko trawę | |
- aksjomaty | |
* <latex> cat \sqsubseteq animal</latex> (każdy) kot jest zwierzęciem (hierarchia pojęć) | |
* <latex> sheep \sqsubseteq animal \sqcap \forall eats.grass</latex> 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 (<latex>A, B, ... </latex>) | |
* atomiczne role (<latex>R, S, ... </latex>) | |
* opisy (<latex>C, D, ... </latex>); mogą nimi być: | |
* <latex> A </latex> - pojęcie atomiczne | |
* <latex>\top </latex> - //top concept//, pojęcie uniwersalne oznaczające "wszystko" | |
* <latex>\bot </latex> - //bottom concept//, pojęcie puste, oznaczające "nic" | |
* <latex>\neg A </latex> - negacja | |
* <latex>C \sqcap D </latex> - koniunkcja | |
* <latex>\forall R.C </latex> - kwantyfikator uniwersalny: "dla każdego" | |
* <latex>\exists R.\top </latex> - kwantyfikator egzystencjalny/szczegółowy: "istnieje" | |
| |
=== Semantyka AL === | |
Semantyka zdefiniowana jest poprzez //interpretację// składającą się z: | |
- dziedziny intepretacji: <latex> \Delta^{\mathcal{I}}</latex> - niepustego zbioru, na który mapowane są symbole i relacje | |
- funkcji interpretacji, która przypisuje: | |
* każdemu atomicznemu pojęciu zbiór: <latex> A \rightarrow A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}</latex> | |
* każdej atomicznej roli relację binarną: <latex> R^{\mathcal{I}} \rightarrow \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}</latex> | |
| |
| |
\\ | |
^ Konstruktor ^ Składnia ^ Semantyka ^ | |
| pojęcie atomiczne (atomic concept) | <latex> A </latex> | <latex> A^{\mathcal{I}} = A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}</latex> | | |
| atomiczna rola (atomic role) | <latex> R </latex> | <latex> R^{\mathcal{I}} = R^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}</latex> | | |
| pojęcie uniwersalne (universal concept) | <latex> \top </latex> | <latex> \top^{\mathcal{I}} = \Delta^{\mathcal{I}}</latex> | | |
| pojęcie puste (bottom concept) | <latex> \bot </latex> | <latex> \bot^{\mathcal{I}} = \emptyset</latex> | | |
| (__**atomic**__ negation) | <latex> \neg A </latex> | <latex> (\neg A)^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus A^{\mathcal{I}} </latex> | | |
| koniunkcja/przecięcie (intersection) | <latex> C \sqcap D </latex> | <latex> (C \sqcap D)^{\mathcal{I}} = C^{\mathcal{I}} \cap D^{\mathcal{I}}</latex> | | |
| ograniczenie wartości (value restriction) | <latex> \forall R.C </latex> | <latex> (\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</latex> | | |
| ograniczony kwantyfikator egzystencjalny (limited existential quantification) | <latex> \exists R.\top</latex> |<latex> (\exists R.\top)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \exists b, (a,b) \in R^\mathcal{I} } \rbrace</latex> | | |
| |
__**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: <latex> Person \sqcap Female</latex> | |
* słonica: <latex> Elephant \sqcap Female</latex> | |
* osoba, które nie jest rodzaju żeńskiego: <latex> Person \sqcap \neg Female</latex> | |
* atomiczna rola: //hasChild// | |
* osoba, która ma (jakieś) dziecko/dzieci: <latex> Person \sqcap \exists hasChild. \top </latex> | |
* osoba, której wszystkie dzieci są rodzaju zeńskiego <latex> Person \sqcap \forall hasChild.Female </latex> | |
* osoba bezdzietna <latex> Person \sqcap \forall hasChild. \bot </latex> | |
| |
==== - Rodzina języków DL ==== | |
Poszczególne języki DL rozróżniamy poprzez konstruktory, które dopuszczają. | |
Przykładowe konkstruktory: | |
* <latex> \mathcal{U}</latex> - suma : <latex> (C \sqcup D)^\mathcal{I} = C^\mathcal{I} \cup D^\mathcal{I}</latex> | |
* <latex> \mathcal{E}</latex> - pełny kwantyfikator egzystencjalny : <latex> (\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 </latex> | |
* <latex> \mathcal{N}</latex> - ograniczenia liczbowe: | |
* <latex> (\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 </latex> | |
* <latex> (\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 </latex> | |
* <latex> \mathcal{C}</latex> - negacja : <latex> ( \neg C)^\mathcal{I} = \Delta^\mathcal{I} \setminus C^\mathcal{I}</latex> | |
| |
Używające powyższych konstruktorów języki nazywają się odpowiednio: | |
* <latex> \mathcal{ALU} </latex> | |
* <latex> \mathcal{ALE} </latex> | |
* <latex> \mathcal{ALN} </latex> | |
* <latex> \mathcal{ALC} </latex> -> odpowiada podzbiorowi logiki pierwszego rzędu ograniczonemu do formuł z dwoma zmiennymi | |
| |
__**Ćwiczenie 2**__ | |
| |
Rozważmy interpretację: I = (∆, ·I ), gdzie | |
* <latex>\Delta I = \{John,Suzan,Max,Helen,Natalie,Nick\}</latex>, | |
* <latex>Human^I = \{John,Suzan,Helen,Natalie,Nick\}</latex>, | |
* <latex>Male^I = \{John, Max, Nick\}</latex>, | |
* <latex>Dog^I = \{Max\}</latex>, | |
* <latex>Doctor^I = \{John, Helen\}</latex>, | |
* <latex>areFriends^I = \{(Suzan,Helen),(Helen,Suzan),(Natalie,Helen),(Helen,Natalie),</latex> <latex> (Suzan, Natalie), (Natalie, Suzan), (Natalie, Nick), (Nick, Natalie) \} </latex>, | |
* <latex>areMarried^I = \{(Suzan, John), (John, Suzan)\}</latex>, | |
* <latex>hasPet^I = \{(Suzan, Max), (John, Max)\}</latex>. | |
| |
- 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 <latex>A \sqsubseteq B</latex>) języka <latex>ALC</latex>: | |
- Ci, którzy nie mają męskich przyjaciół, nie mają zwierząt domoych. | |
- 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 algabry 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** | <latex> C_{1} \sqcap ... \sqcap C_{n}</latex> | <latex> C_{1}(x) \land ... \land C_{n}(x)</latex> |<latex> C_{1} \cap ... \cap C_{n}</latex> | | |
|Gazeta to **dziennik lub czasopismo** | <latex> C_{1} \sqcup ... \sqcup C_{n}</latex> | <latex> C_{1}(x) \lor ... \lor C_{n}(x)</latex> |<latex> C_{1} \cup ... \cup C_{n}</latex> | | |
|Wszystko, co jedzą wegetarianie to **nie mięso** | <latex> \neg C</latex> | <latex> \neg C(x)</latex> | <latex> C^c</latex> (dopełnienie zbioru)| | |
|Kraje UE to: **Niemcy, Francje, ..., Polska** | <latex> \lbrace x_{1} \rbrace \sqcup ... \sqcup \lbrace x_{n} \rbrace </latex> | <latex> x=x_{1} \lor ... \lor x=x_{n}</latex> | <latex> \lbrace x_{1} \rbrace \cup ... \cup \lbrace x_{n} \rbrace </latex> | | |
|**Każde zwierzę, które ma** starsza pani **to kot** | <latex> \forall P.C </latex> | <latex> \forall y.P(x,y) \rightarrow C(y)</latex> | <latex> \pi_Y(P) \subseteq C</latex> | | |
|Właściciel psa **ma jakiegoś psa**| <latex> \exists P.C </latex> | <latex> \exists y.P(x,y) \land C(y)</latex> | <latex>\pi_Y(P) \cap C \neq \emptyset</latex> (Π - projekcja)| | |
|Rozsądny mężczyzna spotyka się z **maksymalnie 1 kobietą równocześnie** ;-) | <latex> \leq nP </latex> | <latex> \exists^{\leq n}y.P(x,y)</latex> | <latex> card(P)\leq n </latex> (card - liczność zbioru)| | |
|Miłośnik zwierzą **ma minimum 3 ziwerzaki** | <latex> \geq nP </latex> | <latex> \exists^{\geq n}y.P(x,y)</latex> | <latex> card(P) \geq n </latex> | | |
|Dziecko **to to samo co** młoda osoba |<latex> C \equiv D </latex> | <latex> \forall x.C(x) \leftrightarrow D(x) </latex> | <latex> C \equiv D </latex> | | |
|**Każda foka jest zwierzęciem** | <latex> C \sqsubseteq D </latex> | <latex> \forall x.C(x) \rightarrow D(x) </latex> | <latex> C \subseteq D </latex> | | |
| |
__**Ć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ęć: | |
* <latex> \mathcal{F}</latex> ograniczenia funkcyjne (np. ≤1//hasMother//) | |
* <latex> \mathcal{N}</latex> ograniczenia liczbowe (np. ≥2//hasChild//, ≤//3hasChild//) | |
* <latex> \mathcal{Q}</latex> warunkowe ograniczenia liczbowe (np. ≥2//hasChild//.Doctor)) | |
* <latex> \mathcal{O}</latex> 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 | |
* <latex> \mathcal{I}</latex> role odwrotne (np. <latex> isChildOf \equiv hasChild^{–}</latex>) | |
* dodatkowe aksjomaty dot. ról: | |
* <latex> \mathcal{S}</latex> przechodniość relacji | |
* <latex> \mathcal{H}</latex> hierarchia relacji (e.g., <latex> hasDaughter \sqsubseteq hasChild</latex>) | |
* <latex> \mathcal{R}</latex> zawieranie się relacji: RoS ⊆ R, RoS ⊆ | |
* inne: | |
* <latex> ^{(\mathcal{D})}</latex> 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: | |
* <latex> C \sqsubseteq D (R \sqsubseteq S) </latex> | |
* lub <latex> C \equiv D (R \equiv S) </latex> | |
* Definicje to równości, które po leweje stronie mają pojęcie atomiczne | |
| |
Semantyka: | |
* funkcja interpretacji <latex> \mathcal{I} </latex> mapuje każde pojecie na podzbiór dziedziny | |
* interpretacja //spełnia// aksjomat <latex> C \sqsubseteq D (R \sqsubseteq S) </latex> jeżeli: <latex> C^{\mathcal{I}} \subseteq D^{\mathcal{I}} </latex> lub <latex> R^{\mathcal{I}} \subseteq S^{\mathcal{I}} </latex> | |
* interpretacja //I// spełnia definicję <latex> C \equiv D (R \equiv S) </latex> jeżeli: <latex> C^{\mathcal{I}} = D^{\mathcal{I}} </latex> lub <latex> R^{\mathcal{I}} = S^{\mathcal{I}} </latex> | |
* 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 <latex> a^{\mathcal{I}} \in C^{\mathcal{I}}</latex> | |
* (b,c) : R wtw gdy <latex> (b^{\mathcal{I}}, c^{\mathcal{I}}) \in R^{\mathcal{I}}</latex> | |
* 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 <latex> C^{\mathcal{I}}</latex> 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 <latex> C^{\mathcal{I}} \subseteq D^{\mathcal{I}}</latex> 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 <latex> C^{\mathcal{I}} = D^{\mathcal{I}}</latex> dla każdego modelu I terminologii T. | |
- Rozłączność (ang. //disjointness//) | |
* Dwa pojęcia C i D są //rozłączne// wzg. T. jeżeli <latex> C^{\mathcal{I}} \cap D^{\mathcal{I}} = \emptyset</latex> dla każdego modelu I terminologii T. | |
| |
__**Ćwiczenie 6**__ | |
- Wiedząc, że: | |
* <latex>Vegetarian \equiv (\forall eats.(\neg (\exists partOf.Animal))) \sqcap (\forall eats.(\neg Animal)) \sqcap Animal</latex> | |
* <latex>Cow \sqsubseteq Vegetarian</latex> | |
* <latex>MadCow \equiv \exists eats.(\exists partOf.Sheep \sqcap Brain) \sqcap Cow </latex> \\ 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//) | |
* <latex> A \models \alpha</latex> 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 ⇔ <latex> C \sqcap D</latex> zawiera się w ⊥ | |
* np. C zawiera się D ⇔ <latex> C \sqcap \neg D </latex> 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: | |
* <latex> OldLady \equiv Elderly \sqcap Female \sqcap Person</latex> | |
* <latex> OldLady \sqsubseteq \exists hasPet.Animal </latex><latex> \sqcap </latex><latex> \forall hasPet. Cat </latex> | |
* <latex> hasPet(Minnie,Tom)</latex>,<latex> Elderly(Minnie)</latex>,<latex> Female(Minnie)</latex> \\ 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: <latex>C \sqsubseteq D</latex> wtw. gdy wyrażenie <latex>C \sqcap \neg D </latex> 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 (<latex> \sqcap, \sqcup, ...</latex>) | |
* niektóre reguły są niedeterministyczne (np. <latex> \sqcup, \leq </latex>) (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]]. | |
- Uruchom go wpisując w konsoli ''pellet.sh help'' i zapoznaj się z dostępnymi opcjami. | |
- Uruchom ''pellet.sh consistency <ontology>'' gdzie ''<ontology>'' jest bazą wiedzy ''people+pets.owl'' umieszczoną w katalogu ''examples''. | |
- Jakie są rezultaty? | |
- Uruchom ''pellet.sh classify <ontology>'' dla powyższej ontologii ''peopl+pets.owl'' | |
- Jakie są rezultaty? | |
- Go to the [[http://pellet.owldl.com/owlsight/|OwlSight]] ontology browser integrated with the Pellet reasoner. | |
| |
| |
__**Ćwiczenie 10**__: | |
- Przejdź na stronę: [[http://db-tom.cs.uwaterloo.ca/AssertionRetrieval/|narzędzia CARE]]. | |
- Zapoznaj się ze [[http://db-tom.cs.uwaterloo.ca/AssertionRetrieval/SyntaxGuide.html|składnią]] narzędzia. | |
- Wygeneruj bazę wiedzy dla 50 studentów i 20 profesorów, niech 5% studentów ma dwóch promotorów.. | |
- Obejrzyj wygenerowaną bazę wiedzy. | |
- Przejdź na [[http://db-tom.cs.uwaterloo.ca/AssertionRetrieval/|tę stronę]] i postaw następujące pytania | |
FIXME | |
| |
| |
| |