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ą 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

1 Zadania wnioskowania dla TBoxa

  1. 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.
  2. Subsumcja 1) (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.
  3. 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.
  4. 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

  1. 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:
    1. Jakiemu pojęciu jest równoważne pojęcie MadCow?
  2. Wykorzystując bazę wiedzy z sekcji terminologia_tbox odpowiedz na pytanie:
    1. Czy zdanie„ „Każdy kto prowadzi przedmiot musi mieć tytuł inżyniera” jest logiczną konsekwencją tej bazy wiedzy? Odpowiedź uzasadnij.

2 Zadania wnioskowania dla ABoxa

  1. 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.
  2. Sprawdzanie instancji (ang. instance checking)
    •  A \models \alpha iff każda interpretacja spełniająca A spełnia również α.
  3. Poszukiwanie najbardziej szegółowego pojęcia dla danej instancji (ang. realization).
  4. 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:

  1. 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:
    1. Czy każda starsza pani musi mieć kota? Dlaczego?
    2. Do jakiej klasy należy obiekt Minnie?
    3. Do jakiej klasy należy obiekt Tom?
  2. 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: wnioskowanie

3 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:

4 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:

  1. Start od faktów (aksjomatów ABox)
  2. Doprowadzenie do normalnej formy negacyjnej (NNF). Jest to forma, w której negacja występuje tylko przd nazwami klas.
  3. Dekompozycja składniowa z użyciem odpowiednich reguł tzw. tableaux expansion rules
  4. Wnioskowanie o ograniczeniach na elementach modelu
  5. Stop, kiedy nie można zastosować więcej reguł lub wystąpiła sprzeczność

Proszę zapoznać się szczegółowo z trzema przykładami z ze slajdów. Proszę przeczytać strony 22-30.

Ćwiczenie 8 (dla chętnych):

Sprawdź czy poniższe pojęcia są spełnialne:

  1. A ⊓ ∃R.C ⊓ ∀R.D
  2. ∃R.C ⊓ ∀R.¬(C ⊓ D)
  3. A⊓∃R.C⊓∀R.D⊓∀R.¬(C⊓D)
  4. ∃R.(A ⊓ ∃R.C) ⊓ ∀R.¬C
  5. ∃R.(A ⊓ ∃R.C) ⊓ ∀R.∀R.¬C
  6. ¬C ⊓ ∃R.C ⊓ ∀R.(¬C ⊔ ∃R.C)
  7. A ⊓ ∀R.A ⊓ ∀R.¬∃P.A ⊓ ∃R.∃P.A

5 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: Prof. U. Sattler. Popularne narzędzia to m.in:

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:

  1. Pobierz silnik wnioskujący Pellet.
    1. :!: Na borgu powinien być w /usr/local/pellet.
  2. Uruchom go wpisując w konsoli pellet.sh help i zapoznaj się z dostępnymi opcjami. (/usr/local/pellet/pellet.sh)
  3. Uruchom pellet.sh consistency <ontology> gdzie <ontology> jest bazą wiedzy people+pets.owl umieszczoną w katalogu examples/data.
  4. Jakie są rezultaty?
  5. Uruchom pellet.sh classify <ontology> dla powyższej ontologii peopl+pets.owl
  6. Jakie są rezultaty?

Materiały

Wykłady, prezentacje

Kursy

Narzędzia

1)
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.
pl/dydaktyka/krr/lab_dl_reasoning.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0