====== 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]]