Logika opisu - Description logic

Logiki opisu ( DL ) to rodzina języków formalnej reprezentacji wiedzy . Wiele DL jest bardziej wyrazistych niż logika zdań, ale mniej wyrazistych niż logika pierwszego rzędu . W przeciwieństwie do tego ostatniego, podstawowe problemy związane z rozumowaniem DL są (zwykle) rozstrzygalne , a dla tych problemów zaprojektowano i wdrożono wydajne procedury decyzyjne. Istnieją logiki opisu ogólna, przestrzenna, czasowa, czasoprzestrzenna i rozmyta, a każda logika opisu charakteryzuje się inną równowagą między mocą ekspresji a złożonością rozumowania , wspierając różne zestawy konstruktorów matematycznych.

DL są używane w sztucznej inteligencji do opisywania i uzasadniania odpowiednich koncepcji domeny aplikacji (znanych jako wiedza terminologiczna ). Ma to szczególne znaczenie w zapewnianiu logicznego formalizmu dla ontologii i sieci semantycznej : język ontologii sieci (OWL) i jego profile są oparte na DL. Najbardziej godnym uwagi zastosowaniem DL i OWL jest informatyka biomedyczna, gdzie DL pomaga w kodyfikacji wiedzy biomedycznej.

Wprowadzenie

Logika opisu (DL) modeluje pojęcia , role i osoby oraz ich relacje.

Podstawową koncepcją modelowania DL jest aksjomat - logiczne stwierdzenie odnoszące się do ról i / lub pojęć. Jest to kluczowa różnica w stosunku do paradygmatu ramek, w którym specyfikacja ramki deklaruje i całkowicie definiuje klasę.

Nomenklatura

Terminologia w porównaniu do FOL i OWL

Społeczność logiki opisu używa innej terminologii niż społeczność logiki pierwszego rzędu (FOL) dla pojęć równoważnych operacyjnie; kilka przykładów podano poniżej. Język Ontologii Sieciowej (OWL) wykorzystuje ponownie inną terminologię, również podane w tabeli poniżej.

Synonimy
FOL SOWA DL
stały indywidualny indywidualny
jednoargumentowy predykat klasa pojęcie
predykat binarny własność rola

Konwencja nazewnictwa

Istnieje wiele odmian logiki opisu i istnieje nieformalna konwencja nazewnictwa, która z grubsza opisuje dozwolone operatory. Expressivity jest kodowany na etykiecie dla logiki z użyciem jednego z następujących podstawowych logiki:

Język atrybutywny. To jest język bazowy, który umożliwia:
  • Negacja atomowa (negacja nazw pojęć, które nie pojawiają się po lewej stronie aksjomatów)
  • Koncepcja skrzyżowania
  • Uniwersalne ograniczenia
  • Ograniczona kwantyfikacja egzystencjalna
Język opisu oparty na ramkach, umożliwia:
  • Koncepcja skrzyżowania
  • Uniwersalne ograniczenia
  • Ograniczona kwantyfikacja egzystencjalna
  • Ograniczenie roli
Język egzystencjalny umożliwia:
  • Koncepcja skrzyżowania
  • Egzystencjalne ograniczenia (pełnej kwantyfikacji egzystencjalnej)

Po którym następuje dowolne z następujących rozszerzeń:

Właściwości funkcjonalne, szczególny przypadek kwantyfikacji niepowtarzalności .
Pełna kwalifikacja egzystencjalna (ograniczenia egzystencjalne, które mają wypełniacze inne niż ).
Pojęcie związku.
Złożona negacja koncepcji.
Hierarchia ról (właściwości podrzędne:) rdfs:subPropertyOf .
Ograniczone aksjomaty włączające złożone role; refleksyjność i nieodwracalność; rozłączność ról.
Nominały. (Numeracja klas ograniczeń wartość obiektu: owl:oneOf , owl:hasValue ).
Właściwości odwrotne.
Ograniczenia liczności ( owl:cardinality , owl:maxCardinality ), szczególny przypadek kwantyfikacji liczenia
Ograniczenia liczności kwalifikowanej (dostępne w OWL 2, ograniczenia liczności, które mają wypełnienia inne niż ).
Stosowanie właściwości typu danych, wartości danych lub typów danych.

Wyjątki

Niektóre kanoniczne DL, które nie pasują do tej konwencji, to:

Skrót od z rolami przechodnimi.
Język podrzędny , który uzyskuje się, uniemożliwiając ograniczenie roli. Jest to równoważne bez atomowej negacji.
Podjęzyk , który uzyskuje się przez niedopuszczenie do ograniczonej kwantyfikacji egzystencjalnej.
Alias ​​dla .

Przykłady

Przykładem jest logika opisu o centralnym znaczeniu, na podstawie której można dokonać porównań z innymi odmianami. jest po prostu uzupełnieniem dowolnego dozwolonego pojęcia, a nie tylko pojęć atomowych. jest używany zamiast odpowiednika .

Kolejny przykład, logika opisu to logika z ograniczeniami rozszerzonej liczności oraz rolami przechodnimi i odwrotnymi. Konwencje nazewnictwa nie są czysto systematyczne, więc logika może być określana jako, a inne skróty są również stosowane tam, gdzie to możliwe.

Obsługuje edytor ontologii Protégé . Trzy główne bazy terminologii informatyki biomedycznej, SNOMED CT , GALEN i GO, można wyrazić w (z dodatkowymi właściwościami roli).

OWL 2 zapewnia wyrazistość , na której opiera się OWL-DL , a dla OWL-Lite jest .

Historia

Logika opisu otrzymała swoją obecną nazwę w latach 80. Wcześniej nazywano go (chronologicznie): systemami terminologicznymi i językami pojęciowymi .

Reprezentacja wiedzy

Ramom i sieciom semantycznym brakuje formalnej (logicznej) semantyki. DL został po raz pierwszy wprowadzony do systemów reprezentacji wiedzy (KR), aby przezwyciężyć ten brak.

Pierwszym systemem KR opartym na DL był KL-ONE (autorstwa Ronalda J. Brachmana i Schmolze, 1985). W latach 80. opracowano inne systemy oparte na DL, wykorzystujące strukturalne algorytmy subsumcji, w tym KRYPTON (1983), LOOM (1987), BACK (1988), K-REP (1991) i CLASSIC (1991). Podejście to charakteryzowało się DL z ograniczoną wyrazistością, ale stosunkowo wydajnym (w czasie wielomianowym) rozumowaniem.

We wczesnych latach 90-tych wprowadzenie nowego paradygmatu algorytmu opartego na tableau umożliwiło efektywne wnioskowanie na bardziej wyrazistym DL. Systemy oparte na DL wykorzystujące te algorytmy - takie jak KRIS (1991) - wykazują akceptowalną wydajność wnioskowania w przypadku typowych problemów wnioskowania, mimo że złożoność najgorszego przypadku nie jest już wielomianem.

Od połowy lat 90. tworzone były rozsądki z dobrymi wynikami praktycznymi na bardzo wyrazistych DL o dużej złożoności najgorszych przypadków. Przykłady z tego okresu to FaCT, RACER (2001), CEL (2005) i KAON 2 (2005).

Osoby rozumujące DL, takie jak FaCT, FaCT ++, RACER, DLP i Pellet, wdrażają metodę analitycznych tabel . KAON2 jest implementowany przez algorytmy, które redukują bazę wiedzy SHIQ (D) do rozłącznego programu datalogu .

Sieć semantyczna

DARPA agencie Markup Language (DAML) i Ontologia Wnioskowanie Warstwa (OIL) ontologia języków dla Semantic Web może być postrzegana jako składniowych wariantów DL. W szczególności semantyka formalna i rozumowanie w OIL używają DL. Dokument DAML + OIL DL został opracowany jako przedłożenie - i stanowił punkt wyjścia - Grupy Roboczej ds. Ontologii Sieciowej World Wide Web Consortium (W3C). W 2004 roku Grupa Robocza Ontologii Sieci zakończyła swoje prace wydając rekomendację OWL . Konstrukcja OWL oparta jest na rodzinie DL z OWL DL i OWL Lite opartymi odpowiednio na i .

Grupa Robocza W3C OWL rozpoczęła w 2007 roku prace nad udoskonaleniem - i rozszerzeniem - OWL. W 2009 roku zakończyło się to wydaniem rekomendacji OWL2 . OWL2 opiera się na logice opisu . Praktyczne doświadczenie pokazało, że OWL DL brakowało kilku kluczowych cech niezbędnych do modelowania złożonych dziedzin.

Modelowanie

W DL rozróżnia się tak zwany TBox (pudełko terminologiczne) i ABox (pudełko asercyjne ). Ogólnie rzecz biorąc, TBox zawiera zdania opisujące hierarchie pojęć (tj. Relacje między pojęciami ), podczas gdy ABox zawiera zdania podstawowe określające, gdzie w hierarchii przynależą jednostki (tj. Relacje między jednostkami i pojęciami). Na przykład stwierdzenie:

Każdy pracownik to osoba

 

 

 

 

( 1 )

należy do TBox, natomiast oświadczenie:

Bob jest pracownikiem

 

 

 

 

( 2 )

należy do ABox.

Należy zauważyć, że rozróżnienie TBox / ABox nie jest znaczące, w tym samym sensie, że te dwa „rodzaje” zdań nie są traktowane inaczej w logice pierwszego rzędu (która obejmuje większość DL). Po przełożeniu na logikę pierwszego rzędu, aksjomat podporządkowania, taki jak ( 1 ), jest po prostu warunkowym ograniczeniem do jednoargumentowych predykatów (pojęć), w których występują tylko zmienne. Oczywiście zdanie w tej formie nie jest uprzywilejowane ani specjalne w stosunku do zdań, w których występują tylko stałe (wartości „ugruntowane”), takie jak ( 2 ).

Dlaczego więc wprowadzono to rozróżnienie? Głównym powodem jest to, że separacja może być przydatna przy opisywaniu i formułowaniu procedur decyzyjnych dla różnych DL. Na przykład osoba rozumująca może oddzielnie przetwarzać TBox i ABox, po części dlatego, że pewne kluczowe problemy związane z wnioskami są powiązane z jednym, ale nie z drugim („klasyfikacja” jest związana z TBox, „sprawdzanie instancji” z ABox). Innym przykładem jest to, że złożoność TBox może znacznie wpłynąć na wykonanie danej procedury decyzyjnej dla określonego DL, niezależnie od ABox. Dlatego warto mieć sposób, aby porozmawiać o tej konkretnej części bazy wiedzy .

Drugim powodem jest to, że rozróżnienie to może mieć sens z perspektywy osoby modelującej bazę wiedzy. Możliwe jest rozróżnienie między naszą koncepcją terminów / pojęć w świecie (aksjomaty klasowe w TBox) a poszczególnymi przejawami tych terminów / pojęć (stwierdzenia instancji w ABox). W powyższym przykładzie: gdy hierarchia w firmie jest taka sama w każdym oddziale, ale przypisanie do pracowników jest inne w każdym dziale (ponieważ pracują tam inne osoby), sensowne jest ponowne wykorzystanie TBox dla różnych oddziałów, które tego nie robią. użyj tego samego ABox.

Istnieją dwie cechy logiki opisu, które nie są wspólne dla większości innych formalizmów opisu danych: DL nie przyjmuje założenia o unikalnej nazwie (UNA) lub założeniu o zamkniętym świecie (CWA). Brak UNA oznacza, że ​​na podstawie pewnego wniosku można wykazać równoważność dwóch pojęć o różnych nazwach. Brak CWA, a raczej założenie otwartego świata (OWA) oznacza, że ​​nieznajomość faktu nie oznacza od razu znajomości zaprzeczenia faktu.

Opis formalny

Podobnie jak logika pierwszego rzędu (FOL), składnia określa, które zbiory symboli są wyrażeniami prawnymi w logice opisu, a semantyka określa znaczenie. W przeciwieństwie do FOL, DL może mieć kilka dobrze znanych wariantów składniowych.

Składnia

Składnia członka rodziny logiki opisu charakteryzuje się jego rekurencyjną definicją, w której podane są konstruktory, które mogą służyć do tworzenia terminów pojęciowych. Niektóre konstruktory są powiązane z konstruktorami logicznymi w logice pierwszego rzędu (FOL), takimi jak przecięcie lub połączenie pojęć, połączenie lub dysjunkcja pojęć, zaprzeczenie lub uzupełnienie pojęć, ograniczenie uniwersalne i ograniczenie egzystencjalne . Inni konstruktorzy nie mają odpowiedniej konstrukcji w FOL, w tym ograniczeń ról, na przykład odwrotności, przechodniości i funkcjonalności.

Notacja

Niech C i D będą pojęciami, a i b będą indywidualnościami, a R będzie rolą.

Jeśli a jest R związane z b, to b jest nazywany R-następcą a.

Notacja konwencjonalna
Symbol Opis Przykład Czytać
⊤ to specjalna koncepcja, w której każda osoba jest przykładem Top
pusta koncepcja Dolny
przecięcie lub połączenie pojęć C i D.
związek lub dysjunkcja pojęć C lub D.
negacja lub uzupełnienie pojęć nie c
powszechne ograniczenie wszyscy następcy R są w C.
egzystencjalne ograniczenie następca R istnieje w C
Włączenie koncepcji wszyscy C są D.
Równoważność pojęć C jest odpowiednikiem D.
Definicja pojęcia C jest zdefiniowane jako równe D.
Twierdzenie koncepcji a jest C
Potwierdzenie roli a jest związane z R z b

Logika opisu ALC

Prototypowy język pojęć atrybutywnych DL z uzupełnieniami ( ) został wprowadzony przez Manfreda Schmidta-Schaußa i Gerta Smolkę w 1991 roku i jest podstawą wielu bardziej wyrazistych DL. Poniższe definicje są zgodne z leczeniem opisanym w Baader i wsp.

Pozwól , i być (odpowiednio) zestawy z nazwami koncepcyjnych (znany również jako koncepcji atomowych ), nazw ról oraz indywidualnych nazw (znany również jako osoby fizyczne , nominałach lub obiektów ). Potem zamówiłem potrójne ( , , ) jest podpis .

Koncepcje

Zbiór pojęć jest najmniejszym zbiorem takim, że:

  • Oto pojęcia :
    • ( góra to koncepcja )
    • (na dole jest koncepcja )
    • Każdy (wszystkie pojęcia atomowepojęciami )
  • Jeśli i są pojęciami, a następnie są pojęciami :
    • (skrzyżowanie dwóch pojęć jest pojęciem )
    • (połączenie dwóch pojęć jest pojęciem )
    • (dopełnieniem pojęcia jest pojęcie )
    • (uniwersalnym ograniczeniem pojęcia przez rolę jest pojęcie )
    • (egzystencjalne ograniczenie pojęcia przez rolę jest pojęciem )
Aksjomaty terminologiczne

Ogólny włączenie koncepcji (GCI) ma postać gdzie i są koncepcje . Napisz kiedy i . TBox jest dowolny skończony zbiór GCIs.

Aksjomaty asercyjne

  • Pojęcie twierdzenie jest zestawienie postaci gdzie i C to pojęcie .
  • Rola twierdzenie jest zestawienie postaci gdzie R jest rola .

ABox jest skończonym zbiorem assertional aksjomatów.

Baza wiedzy

Bazę wiedzy (MB) są uporządkowane pary do TBox i ABox .

Semantyka

W semantyka opisu logiki są zdefiniowane jak koncepcje interpretacji zestawów jednostek i role zbiorów uporządkowanych par jednostek. Te osoby są zwykle zakładane z danej domeny. Semantyka pojęć i ról nieatomowych jest następnie definiowana w kategoriach pojęć i ról atomowych. Odbywa się to za pomocą definicji rekurencyjnej podobnej do składni.

Logika opisu ALC

Poniższe definicje są zgodne z leczeniem opisanym w Baader i wsp.

Terminologiczna interpretacja na podpis składa się z

  • niepusty zestaw zwany domeną
  • funkcja interpretacja , że mapy:
    • każda jednostka do elementu
    • każdą koncepcję do podzbioru
    • każdą nazwę roli do podzbioru

takie że

  • ( związek oznacza rozłączenie )
  • ( przecięcie oznacza koniunkcję )
  • ( dopełnienie oznacza zaprzeczenie )

Zdefiniuj (czytaj w I trzyma ) w następujący sposób

TBox
  • wtedy i tylko wtedy gdy
  • wtedy i tylko wtedy, gdy dla każdego
Pudełko
  • wtedy i tylko wtedy gdy
  • wtedy i tylko wtedy gdy
  • wtedy i tylko wtedy, gdy dla każdego
Baza wiedzy

Niech będzie bazą wiedzy.

  • wtedy i tylko wtedy, gdy i

Wnioskowanie

Problemy decyzyjne

Oprócz umiejętności formalnego opisu pojęć chciałoby się również zastosować opis zbioru pojęć do zadawania pytań o opisane pojęcia i przypadki. Najczęstszymi problemami decyzyjnymi są podstawowe pytania podobne do zapytań bazodanowych, takie jak sprawdzanie instancji (czy konkretna instancja (członek ABox) jest członkiem danej koncepcji) i sprawdzanie relacji (czy relacja / rola zachowuje się między dwoma instancjami, w innych słowa robi mają własność b ), a tym bardziej globalne-database-pytania typu subsumcji (to pojęcie podzbiorem innego pojęcia), a spójność koncepcji (czy nie ma sprzeczności między definicjami lub łańcucha definicji). Im więcej operatorów zawiera logika i im bardziej skomplikowany jest TBox (mający cykle, pozwalające na wzajemne uwzględnienie pojęć nieatomowych), zwykle tym większa jest złożoność obliczeniowa dla każdego z tych problemów (przykłady można znaleźć w opisie Logic Complexity Navigator ) .

Związek z innymi logikami

Logika pierwszego rzędu

Wiele DLS są rozstrzygalne fragmenty z logiką pierwszego rzędu (FOL) i zwykle są fragmenty dwóch zmiennych logiki lub strzeżonym logiki . Ponadto niektóre DL mają funkcje, które nie są objęte FOL; obejmuje to konkretne domeny (takie jak liczby całkowite lub ciągi znaków, które mogą być używane jako zakresy dla ról, takich jak hasAge lub hasName ) lub operator ról do przechodniego zamknięcia tej roli.

Logika opisu rozmytego

Logika opisu rozmytego łączy logikę rozmytą z logiką DL. Ponieważ wielu pojęciom, które są potrzebne inteligentnym systemom, brakuje dobrze zdefiniowanych granic lub precyzyjnie określonych kryteriów przynależności, potrzebna jest logika rozmyta, aby poradzić sobie z pojęciami niejasności i nieprecyzyjności. Stwarza to motywację do uogólnienia logiki opisu w kierunku zajmowania się nieprecyzyjnymi i niejasnymi pojęciami.

Logika modalna

Logika opisu jest związana z logiką modalną (ML), ale jest od niej rozwijana niezależnie . Wiele - ale nie wszystkie - DL to syntaktyczne warianty ML.

Ogólnie rzecz biorąc, obiekt odpowiada możliwemu światu , pojęcie odpowiada twierdzeniu modalnemu, a kwantyfikator ograniczony rolami operatorowi modalnemu, którego rolą jest relacja dostępności.

Operacje na rolach (takie jak kompozycja, inwersja itp.) Odpowiadają operacjom modalnym używanym w logice dynamicznej .

Przykłady

Warianty syntaktyczne
DL ML
K.
PDL
DPDL (deterministyczny PDL)
Converse- PDL
Converse - DPDL (deterministyczny PDL)

Logika opisu czasu

Logika opisu czasowego reprezentuje - i pozwala na rozumowanie - pojęcia zależne od czasu i istnieje wiele różnych podejść do tego problemu. Na przykład logika opisu może być połączona z modalną logiką temporalną, taką jak liniowa logika temporalna .

Zobacz też

Bibliografia

Dalsza lektura

Linki zewnętrzne

Rozumenci

Istnieje kilka argumentów semantycznych, które dotyczą OWL i DL. Oto niektóre z najpopularniejszych:

  • CEL to oparty na LISPu program rozumujący typu open source (licencja Apache 2.0).
  • Cerebra Engine był komercyjnym narzędziem do rozumowania opartym na C ++, zakupionym w 2006 roku przez webMethods.
  • FaCT ++ to darmowy program do rozumowania oparty na C ++ o otwartym kodzie źródłowym.
  • KAON2 to darmowy (do użytku niekomercyjnego) program do rozumowania oparty na Javie, oferujący szybkie wsparcie dla ontologii OWL.
  • MSPASS to darmowy program do rozumowania języka C o otwartym kodzie źródłowym dla wielu modeli DL.
  • Pellet to komercyjny, oparty na języku Java programista, posiadający podwójną licencję (AGPL i własna).
  • RacerPro z Racer Systems był komercyjnym (dostępne są bezpłatne wersje próbne i licencje badawcze) opartym na lisp, dziś zarówno wersja open source RACER istnieje od oryginalnych programistów z Uniwersytetu w Lubece korzystających z licencji BSD 3, jak i wersja komercyjna, nadal nazwany RacerPro przez Franz Inc.
  • Sim-DL to darmowy, oparty na Javie, program do rozumowania języka ALCHQ. Zapewnia również funkcjonalność pomiaru podobieństwa między koncepcjami. Aby uzyskać dostęp do tej funkcji, można użyć wtyczki Protégé.
  • HermiT jest otwartym wnioskiem opartym na rachunku „hipertableau”. Został opracowany przez University of Oxford .
  • Owlready2 to pakiet do programowania zorientowanego na ontologię w Pythonie . Może ładować ontologie OWL 2.0 jako obiekty Pythona, modyfikować je, zapisywać i przeprowadzać rozumowanie za pośrednictwem HermiT (w zestawie). Owlready2 umożliwia przejrzysty dostęp do ontologii OWL (w przeciwieństwie do zwykłego API opartego na Javie).

Redaktorzy

Interfejsy