Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:krr:lab_dl [2013/05/31 23:00] ikaf [Spool] |
pl:dydaktyka:krr:lab_dl [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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 | ||
| - | |||
| - | |||
| - | ===== Literatura, materiały ===== | ||
| - | FIXME | ||
| - | - Description Logic Handbook: {{http://www.inf.unibz.it/~franconi/dl/course/dlhb/dlhb-01.pdf|Rozdział 1: "Introduction to Description Logics"}} | ||
| - | - Portal o logikach opisowych: | ||
| - | |||
| - | |||
| - | * Wikipedia: [[http://en.wikipedia.org/wiki/Description_logic|Description Logic]] | ||
| - | |||
| - | Materiały: | ||
| - | * http://www.dcs.bbk.ac.uk/~michael/sw/slides/solutions-11-7.pdf | ||
| - | |||
