[[
✎ pl:dydaktyka:krr:lab_dl
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== 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> (Fred, 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 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** | <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 </latex> * <latex> R \sqsubseteq S </latex> * <latex> C \equiv D </latex> * <latex> R \equiv S </latex> * Definicje to równości, które po lewej 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 </latex> jeżeli: <latex> C^{\mathcal{I}} \subseteq D^{\mathcal{I}} </latex>; analogicznie w przypadku relacji <latex> R \sqsubseteq S </latex> * interpretacja //I// spełnia definicję <latex> C \equiv D </latex> jeżeli: <latex> C^{\mathcal{I}} = D^{\mathcal{I}} </latex>; analogicznie w przypadku relacji <latex> R \equiv S </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]]. - :!: 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 ==== * [[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]]
pl/dydaktyka/krr/lab_dl.txt
· ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry