Lògica de descripció

Les lògiques de descripció també anomenades lògiques descriptives (DL per description logics) són una família de llenguatges de representació del coneixement que poden ser usats per a representar coneixement terminològic d'un domini d'aplicació d'una forma estructurada i formalment ben compresa. El nom lògica de descripció es refereix, d'una banda, a descripcions de conceptes usades per descriure un domini i, d'altra banda, a la semàntica que estableix una equivalència entre les fórmules de lògiques de descripció i expressions en lògica de predicats de primer ordre. DL es va dissenyar com una extensió de frames (marcs) i xarxes semàntiques, els quals no estaven equipats amb semàntica basada en la lògica. A diferència dels altres sistemes de representació (xarxes semàntiques i frames), aquestes lògiques estan dotades amb una semàntica formal basada en lògica i tenen característiques molt importants com són:

Un formalisme descriptiu: conceptes, rols, individus i constructors.
Un formalisme terminològic: axiomes terminològics que introdueixen descripcions complexes i propietats de la terminologia descriptiva .
Un formalisme assertiu: que introdueix propietats d'individus.
Són capaços d'inferir nou coneixement a partir de coneixement donat; tenen per tant, algoritmes de raonament que són decidibles.

Els elements centrals de l'alfabet del llenguatge de les lògiques de descripció són:

Noms de concepte (concept name): assignen un nom a un grup d'objectes.
Noms de rol (role name): assigna un nom a una relació entre objectes.
Noms d'individus (o objectes): els individus són instàncies dels conceptes i també es poden relacionar per mitjà d'un rol.
Constructors (constructor): relaciona noms de conceptes i noms de rols, i també crea conceptes complexos a partir dels atòmics (complex concepts).
Definicions de conceptes complexos: usa els símbols $\doteq$ $\sqsubseteq$ per declarar conjunt d'igualtats i conjunts d'inclusions.

El nom de lògica de descripció és dels anys 1980. Abans d'això es deia (cronològicament): sistemes terminològics , i llenguatges de conceptes . Les lògiques de descripció d'avui en dia s'han convertit en una pedra fonamental de la web semàntica per al seu ús en el disseny d'ontologies.

El primer sistema basat en DL va ser KL-ONE (per Brachman and Schmolze, 1985). Després van venir d'altres terminals de DL. Estan Loom (1987), BACK (1988), Kris (1991), CLASSIC (1991), FACT (1998), RACER (2001), CEL (2005) i kaon 2 (2005).

El desenvolupament d'OIL va ser inspirat en DL.

Modelant amb lògiques de descripció

A DLS, hi ha una distinció entre l'anomenada TBox (caixa terminològica) i la ABOX (caixa d'assercions). En general, la TBox conté sentències descrivint conceptes jeràrquics (ie, relacions entre conceptes) mentre la ABOX conté sentències "ground" indicant a on pertanyen els individus en la jerarquia (és a dir, relacions entre individus i conceptes). Per exemple, la frase:

(1) Cada empleat és una persona

part del TBox, mentre que la frase:

(2) Bob és un empleat

part de l'ABOX. Noteu que la distinció entre TBox i ABOX no és significant en el mateix sentit que en la lògica de primer ordre (la qual subsumeix la majoria de les DL). Les dues "classes" de sentències es tracten de la mateixa manera. Quan es tradueix a lògica de primer ordre, un axioma de subsumición com (1) és simplement un condicional restringit a predicats unaris (conceptes) on només apareixen variables. Una sentència d'aquesta manera no té un tractament diferent de les sentències on només apareixen constants (valors "ground") com en (2).

Llavors, per què fer aquesta distinció? La principal raó és que aquesta separació pot ser útil per descriure i formular procediments de decisió per a diverses DL. Per exemple, un raonador podria processar la TBox i la ABOX per separat. Certs problemes claus d'inferència estan lligats a una però no a l'altra ('classificació' està relacionat amb la TBox, 'revisió d'instància' a la ABOX). A més la complexitat de la TBox pot afectar considerablement la performance d'un procediment de decisió per a certa DL, independentment de la ABOX. Així resulta útil una manera de parlar d'una part específica d'una base de coneixement (KB). Un altre motiu d'aquesta distinció és que tingui sentit des del punt de vista del que modela la base de coneixement. És convenient poder distingir entre els conceptes en el món (axiomes de classe a la TBox) i les manifestacions particulars d'aquests conceptes (assercions d'instància en la ABOX)

Diferències amb OWL

Terminologia

Un concepte en l'argot de DL es refereix a una classe en OWL. Un rol en l'argot de DL és una propietat en OWL.

Noms

OWL no necessita la suposició de noms únics (UNA per unique name assumption).

Raonats per lògiques de descripció

A continuació es detallen els més populars raonats per manejar-se amb OWL i amb DL:

CEL és un raonador basat en LISP, gratuït per a ús no comercial.
Cerca^{[Enllaç no actiu]} és un raonador comercial basat en C++.
FACT++ és un raonador basat en C++, gratuït open-source.
KAON2 Arxivat 2006-01-06 a Wayback Machine. és un raonador basat en Java, gratuït per a ús no comercial.
Schmidt/mspass/ MSPASS és un raonador basat en C, gratuït i open-source.
Pellet és un raonador basat en Java, gratuït open-source.
RacerPro és un raonador basat en LISP comercial, però amb trials gratuïts i llicències de recerca.

Altres eines relacionades a DLS inclouen els següents:

Protégé és un editor d'ontologies i frameworks de bases de coneixement, gratuït open-source. Podeu usar raonats de DL que ofereixen una interfície DIG per revisions de consistència.

La lògica ${\mathcal {ALC}}$

Les lògiques ${\mathcal {AL}}$ (AL per attributive language) constitueixen una família de lògica populars. Cadascuna afegeix lletres al seu nom per indicar el seu poder expressiu. Una lògica popular és la lògica ${\mathcal {ALC}}$ , la qual utilitza una notació estàndard, comunament coneguda com a sintaxi alemanya a causa de la nacionalitat dels seus creadors, que s'ha adoptat àmpliament per a la discussió teòrica sobre DL. Aquesta notació usa els símbols:

" $\sqcap$ " i " $\sqcup$ " per a operadors de conjunció i disjunció, reflectint la seva interpretació del model teòric com el conjunt d'intersecció i unió.
" $\forall$ " i " $\exists$ " quantificadors lògics estàndard, símbols per restricció de valor i restricció existencial.
" $\lnot$ " per al complement.

Varietat d'altres símbols també poden usar-se per representar operadors addicionals, que seran descrits més endavant.

Els símbols de relació " $\doteq$ " i " $\sqsubseteq$ " s'usen en axiomes i reflecteixen la seva interpretació en el model teòric com a conjunt d'igualtat i conjunt d'inclusió.

Sintaxi de ${\mathcal {ALC}}$

La sintaxi d'aquestes lògiques suporten la descripció lògica de conceptes, rols (relacions) i individus, on els conceptes i rols poden ser combinats, utilitzant una varietat d'operadors, per formar expressions més complexes. Els operadors suportats per les lògiques de descripció, normalment inclouen algunes o totes les connectives lògiques estàndards juntament amb un o dos operadors relacionals (quantificadors universals i existencials anomenats restriccions de valor i restriccions existencials).

Formalment una terminologia en ${\mathcal {ALC}}$ està definida per la següent formació de regles:

Els axiomes són de la forma:

C\doteq D\mid C\sqsubseteq D

on C i D són les expressions de concepte.

Les expressions de concepte de la forma:

$CN\mid \top \mid \bot \mid \lnot C\mid C\sqcap D\mid C\sqcup D\mid \exists R.C\mid \forall R.C$

CN és un nom de concepte (conceptes atòmics) R és una expressió de rol.

El nom de concepte $\top$ (top) representa el concepte més general. El nom de concepte $\bot$ (bottom) representa el concepte menys general.

Semàntica de ${\mathcal {ALC}}$

La Semàntica busca explicar la relació que existeix entre la sintaxi del llenguatge i els models previstos del domini, donant significat a les expressions, el qual és donat pel model teòric semàntic. Aquest model teòric va ser proposat per Tarski, on els conceptes i rols es refereixen a conjunts d'objectes en el domini d'interès i les relacions entre ells.

Formalment el model teòric es dona per: ${\mathcal {I}}=(\Delta ^{\mathcal {I}},\cdot ^{\mathcal {I}})$ el qual consta d'un conjunt no buit $\Delta ^{\mathcal {I}}$ anomenat el domini de ${\mathcal {I}}$ i una funció $\cdot ^{\mathcal {I}}$ (la funció d'interpretació de ${\mathcal {I}}$ ) que assigna a cada concepte un subconjunt de $\Delta ^{\mathcal {I}}$ , cada rol a un subconjunt de $\Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}$ ia cada individu un element de $\Delta ^{\mathcal {I}}$ , de tal manera que:

\top ^{\mathcal {I}}=\Delta ^{\mathcal {I}}

\bot ^{\mathcal {I}}=\emptyset

(\lnot C)^{\mathcal {I}}=\Delta ^{\mathcal {I}}\backslash C^{\mathcal {I}}

(C\sqcap D)^{\mathcal {I}}=C^{\mathcal {I}}\cap D^{\mathcal {I}}

(C\sqcup D)^{\mathcal {I}}=C^{\mathcal {I}}\cup D^{\mathcal {I}}

(\exists R.C)^{\mathcal {I}}=\{d\in \Delta ^{\mathcal {I}}\mid \exists i\in \Delta ^{\mathcal {I}}:(d,e)\in R^{\mathcal {I}}\land i\in C^{\mathcal {I}}\}

(\forall R.C)^{\mathcal {I}}=\{d\in \Delta ^{\mathcal {I}}\mid \forall i\in \Delta ^{\mathcal {I}}:(d,e)\in R^{\mathcal {I}}\to i\in C^{\mathcal {I}}\}

És a dir:

Un concepte és interpretat com un conjunt d'individus
Els rols són interpretats com a conjunts de parells d'individus.
Els conceptes atòmics s'interpreten com subconjunts del domini de la interpretació.

Mentre que la Semàntica dels constructors són llavors especificats per definicions de conjunt d'individus denotats per cada constructor. Per exemple:

$C\sqcap D$ és el conjunt d'individus obtinguts per la intersecció de conjunts d'individus denotats per C i D , respectivament.
$\forall R.C$ és el conjunt d'individus que estan en la relació R amb els individus que pertanyen al conjunt denotat pel concepte C .

Extensions de ${\mathcal {ALC}}$

El poder expressiu d'una lògica de descripció és la capacitat per representar "coneixement" sobre el domini i depèn de la riquesa del seu llenguatge.

El llenguatge de la lògica ${\mathcal {ALC}}$ no és molt expressiu. Per comprovar-només cal veure aquests exemples de "informació" bàsica sobre un domini senzill no expressable en ${\mathcal {ALC}}$ :

"Una dona que té exactament dos fills" (no és possible expressar restriccions numèriques).
"Tot home és fill d'una dona" (no és possible expressar l'invers d'un rol).
"La mare del pare és l'àvia" (no és possible expressar composició de rols).

Cal estendre el llenguatge de ${\mathcal {ALC}}$ , però afegint els elements necessaris de manera que la complexitat computacional no sigui intractable, ja que volem poder raonar amb aquesta lògica i, en particular, disposar dels algorismes mínims de satisfactibilidad, subsumición i consistència. Vegem els constructors més importants utilitzats per estendre el llenguatge ${\mathcal {ALC}}$ i també alguns dels sistemes obtinguts estenent.

Restriccions numèriques $({\mathcal {N}})$ : $\geq n\ R\mid \leq n\ R$
Restriccions numèriques qualificades $({\mathcal {Q}})$ : $\geq n\ R.C\mid \leq n\ R.C$
Restriccions funcionals $({\mathcal {F}})$ : $\leq 1\ R$
Nominals $({\mathcal {O}})$ : $a_{1},\ldots ,a_{n}$
Dominis concrets: Un domini concret D és un conjunt $\Delta ^{(D)}$ (el domini) més un conjunt pred ( D ) dels noms de predicat de D . Cada nom de predicat P de D s'associa amb una àrida n i un predicat n -usuari d $\Delta ^{(D)}$ .

Exemple: el domini concret $\mathbb {N}$ , té com a domini el conjunt $\mathbb {N}$ dels nombres naturals i pred ( $\mathbb {N}$ ) el conjunt dels predicats binaris <≤> ≥.

Les lògiques de descripció molt més expressives també fan servir constructors de rols, ja que els rols s'interpreten com relacions binàries, això implica definir constructors la Semàntica és la de les operacions sobre relacions. On: si R i S són descripcions de rol (atòmic) també ho són:

Unió de rols: $R\sqcup S$
Intersecció de rols: $R\sqcap S$
Complement de rol: $\lnot R$
Composició de rols: $R\circ S$
Rol invers $({\mathcal {I}})$ : $R^{-}$
Rol transitiu: $R^{+}$

La terminologia també permet incloure jerarquia de rols $({\mathcal {H}})$ on els axiomes són de la forma:

$R\doteq S\mid R\sqsubseteq S$

La semàntica per a les expressives lògiques de descripció exposades anteriorment es dona, de la següent manera:

Axiomes	Semàntica	Exemple
$\geq n\ R$	$\{x\mid \#\{i\mid R^{\mathcal {I}}(x,y)\}\geq n\}$	$\geq 2\ tieneHijo$
$\leq n\ R$	$\{x\mid \#\{i\mid R^{\mathcal {I}}(x,y)\}\leq n\}$	$\leq 2\ tieneHijo$
$\geq n\ R.C$	$\{x\mid \#\{i\mid R^{\mathcal {I}}(x,y)\land C^{\mathcal {I}}(i)\}\geq n\}$	$\geq 3\ tieneHijo.Hombre$
$\leq n\ R.C$	$\{x\mid \#\{i\mid R^{\mathcal {I}}(x,y)\land C^{\mathcal {I}}(i)\}\leq n\}$	$\leq 3\ tieneHijo.Mujer$
$A_{1}\ldots a_{n}$	$\{a_{1}^{\mathcal {I}},\ldots ,a_{num}^{\mathcal {I}}\}$	$\{Maria,John\}$
$R\sqcup S$	$R^{\mathcal {I}}\cup S^{\mathcal {I}}$	$tieneHijo\sqcup tieneHija$
$R\sqcap S$	$R^{\mathcal {I}}\cap S^{\mathcal {I}}$	$tieneHijo\sqcap tieneHija$
$\lnot R$	$(\Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}})\mid R^{\mathcal {I}}$	$\lnot tieneAmigo$

Axiomes	Semàntica	Exemple
$R\circ S$	$\{(a,c)\in \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}\mid \exists b.(A,b)\in R^{\mathcal {I}}\land (b,c)\in S^{\mathcal {I}}\}$	$tieneHijo\circ tieneAmigo$
$R^{-}$	$\{(b,a)\in \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}\mid (a,b)\in R^{\mathcal {I}}\}$	$tienePadre^{-}$
$R^{+}$	$\bigcup _{i\geq 1}(R^{\mathcal {I}})^{i}$	$avantpassat^{+}$
$R\doteq S$	$R^{\mathcal {I}}=S^{\mathcal {I}}$	$tieneHijo\doteq tienePadre^{-}$
$R\sqsubseteq S$	$R^{\mathcal {I}}\subseteq S^{\mathcal {I}}$	$avantpassat^{+}\sqsubseteq avantpassat$

Inferències

Les lògiques de descripció són alguna cosa més que llenguatges per a formalitzar conceptes, han de representar l'ontologia d'un domini d'aplicació i permetre raonar sobre ell. Per a això s'introdueixen nous elements en el llenguatge i la semàntica necessària per a formalitzar les propietats dels individus del domini i de les relacions entre conceptes i rols, són les anomenades bases de coneixement.

Base de coneixement

La base de coneixement està formada per dues parts: la TBox i el ABOX .

L' TBox contempla tota la terminologia, és a dir, el vocabulari d'un domini d'aplicació en funció de:

Conceptes: denoten classes o conjunt d'individus.
Rols: denoten relacions binàries entre els individus.
Un conjunt de descripcions complexes sobre aquest vocabulari (restringits, per descomptat, pel llenguatge de descripció).

L' ABOX conté assercions sobre individus nomenats en termes de vocabulari.

Una base de coneixement ( TBox i ABOX ) és equivalent a un conjunt d'axiomes de la LPO (Lògica de primer ordre), i per tant es pot definir un càlcul o sistema d'inferència que permet derivar "coneixement" implícit a partir del "explícit" de la base de coneixement.

Raonament amb conceptes ( TBox )

Suposem que tenim un llenguatge descriptiu per a un domini, per exemple ${\mathcal {ALC}}$ , i que s'ha definit una TBox (axiomes terminològics) per modelar un domini. Si es defineix un nou concepte és important saber si és consistent o contradictori amb el TBox . Aquesta propietat es coneix com el concepte satisfer (o respectivament insatisfacció) pel que fa al TBox . Potser caldrà saber si un concepte és més general que un altre, si són equivalents o si són disjunts. La formalització d'aquestes propietats és la següent:

Suposem que ${\mathcal {T}}$ és un TBox , C i D conceptes:

C és satisfactori pel que fa a ${\mathcal {T}}$ si hi ha un model ${\mathcal {I}}$ tal que ${\mathcal {T}}(C)^{\mathcal {I}}\neq \emptyset$ .
C és subsumit per D pel que fa a ${\mathcal {T}}$ si per tot model ${\mathcal {I}}$ de ${\mathcal {T}}$ , hem de $(C)^{\mathcal {I}}\subseteq (D)^{\mathcal {I}}$ . Això s'escriu ${\mathcal {T}}\models C\sqsubseteq D$ .

Raonant amb individus ( ABOX )

Un cop definida una TBox , en definir l' ABOX , les propietats més importants que caldrà comprovar les de la consistència del ABOX i el TBox , i la derivació d'una instanciació a partir del ABOX. Vegem formalment aquests conceptes:

Suposem que ${\mathcal {T}}$ és un TBox , A és un ABOX, C un concepte i o un nom d'individu:

A és consistent pel que fa a ${\mathcal {T}}$ si hi ha una interpretació que és model de ${\mathcal {T}}$ i de A .
o : C es deriva de ${\mathcal {T}}$ i A si tot model ${\mathcal {I}}$ de ${\mathcal {T}}$ compleix $(o)^{\mathcal {I}}\in (C)^{\mathcal {I}}$ . això és $({\mathcal {T}},A\models o:C)$ .

Sistema ${\mathcal {SH}}$

Aquesta és una altra notació molt utilitzada per alguns sistemes de lògiques de descripció. La importància d'aquesta lògica, és que és la que actualment s'està implementant per les ontologies depenent de les necessitats del programador. El sistema ${\mathcal {SH}}$ es dona de la següent manera:

${\mathcal {SHIQ}}$ és ${\mathcal {ALCQI}}$ +rols transitius+inclusió rols. ${\mathcal {SHOIQ}}$ és ${\mathcal {SHIQ}}$ +nominals. Es demostra també que ${\mathcal {SHOIQ}}$ és ${\mathcal {SHOIN}}$ estesa amb restriccions qualificades. ${\mathcal {SHOIN(D)}}$ és ${\mathcal {MARINIS}}$ +nominals+dominis concrets ( ${\mathcal {D}}$ ).

Encara que estendre una lògica amb dominis concrets la dotació d'una expressivitat molt valorada per representar ontologies, fàcilment pot portar a la indecidibilitat. Veurem, però, que ${\mathcal {SHOIN(D)}}$ és decidible i és base per al llenguatge d'ontologia actualment més acceptat.

Complexitat computacional del sistema ${\mathcal {SH}}$

Les lògiques de descripció van ser pensades com sistemes formals per a representar coneixement, i això significa anar més enllà d'emmagatzemar terminologies i descripcions. En particular, significa poder derivar fets implícits a partir dels daus. Per aquest motiu la implementació de processos d'inferència ha de tenir en compte la possibilitat d'utilitzar algorismes d'inferència òptims. En l'estudi d'aquests algorismes el punt de partida és conèixer la seva complexitat computacional (per exemple la complexitat EXPTIME i PSPACE).

Trobar algoritmes de decisió per als problemes d'inferència com satisfactibilidad, subsumición i consistència en ABOX per lògiques de descripció expressives i amb la menor complexitat possible, de manera que la implementació computacional sigui afrontar-la, la qual és tot un repte.

La recerca d'aquests procediments de decisió ha estat un dels objectius fonamentals en el desenvolupament de les lògiques de descripció. Una de les maneres d'obtenir-los és estudiant la connexió de les lògiques de descripció amb altres lògiques conegudes. És el cas de la decidibilitat en ${\mathcal {ALC}}$ i en totes les seves extensions que s'obtenen afegint constructors que a la LPO es poden expressar amb dues variables. Tanmateix, la complexitat del procediment de decisió obtingut d'aquesta manera és normalment més gran del que realment es necessita, per exemple el problema de satisfactibilidad per a la LPO amb dues variables és NEXPTIME (que és una complexitat molt gran, tot i que encara és decidible) mentre que en ${\mathcal {ALC}}$ és PSPACE-hard (és una complexitat menor). Una altra manera d'estudiar la complexitat és fent servir la connexió amb les lògiques modals proposicionals.

En la següent taula es presentés les principals extensions de ${\mathcal {ALC}}$ , especificant les noves propietats expressables en l'extensió i els límits per a la complexitat computacional.

DL	Propietat expressable en la lògica	Complexitat
${\mathcal {ALC}}$	lògica de descripció bàsica	PSPACE
${\mathcal {ALCN}}$	+restriccions numèriques no qualificades $({\mathcal {N}})$	PSPACE
${\mathcal {ALC}}$ reg	+expressions regulars sobre rols (reg)	EXPTIME
${\mathcal {ALCI}}$ reg	+invers de rols $({\mathcal {I}})$	EXPTIME
${\mathcal {ALCFI}}$ reg	+restriccions funcionals sobre rols atòmics $({\mathcal {F}})$	EXPTIME
${\mathcal {ALCQI}}$ reg	+restriccions numèriques qualificades $({\mathcal {Q}})$	EXPTIME
${\mathcal {ALCQO}}$ reg	+un alfabet per als objectes del domini $({\mathcal {O}})$	EXPTIME
${\mathcal {SHIQ}}$	${\mathcal {ALCQI}}$ +rols transitius+inclusió rols	EXPTIME
${\mathcal {SHOIN}}$	+restriccions numèriques no qualificades $({\mathcal {N}})$	EXPTIME
${\mathcal {SHOIQ}}$	${\mathcal {SHIQ}}$ +nominals	NEXPTIME
${\mathcal {SHOIN(D)}}$	${\mathcal {SHOIN}}$ +dominis concrets	EXPTIME

http://www.trafford.com/07-1729 Arxivat 2008-09-27 a Wayback Machine. Aquest un llibre relaciona 16 classes de complexitat algorísmica respecte a espai i temps. I resol algunes igualtats.

Bibliografia

F. Baader, D. Calvanese, D. L. McGuiness, D. Nardi, P. F. Patel-Schneider: The Description Logic Handbook: Theory, Implementation, Applications . Cambridge University Press, Cambridge, UK, 2003. ISBN 0-521-78176-0

Enllaços externs