Avancerad

Beskrivningslogik

Logiska system för kunskapsrepresentation och ontologier.

beskrivningslogik ontologi koncept roll subsumption

Föreställ dig att du organiserar ett enormt bibliotek. Du behöver ett system för att beskriva böcker: 'Denna bok är en roman som är skriven av en svensk författare och handlar om kriminalfall'. Beskrivningslogik fungerar på liknande sätt - det är ett språk för att precisionsorganisera och resonera om kunskap. Istället för böcker kan vi beskriva allt från medicinska diagnoser ('en sjukdom som påverkar hjärtat och orsakas av virus') till biologisk taxonomi ('ett däggdjur som lever i vatten och har fenor'). Beskrivningslogik är grunden för moderna kunskapsrepresentationssystem och semantiska webben.

Fördjupning

Beskrivningslogik (Description Logic, DL) är en familj av kunskapsrepresentationsspråk för att uttrycka kunskap om domäner på ett strukturerat sätt. DL kombinerar logisk precision med beräkningsmässig hanterbarhet. Huvudkomponenterna är koncept (klasser av objekt), roller (relationer mellan objekt) och individer (specifika objekt). DL ligger till grund för Web Ontology Language (OWL) och används för ontologier, expertSystem och semantisk webbteknik. Olika DL-logiker balanserar uttryckskraft mot algoritisk komplexitet.

Grundläggande komponenter

Beskrivningslogik organiserar kunskap genom tre huvudtyper av entiteter: koncept (beskriver klasser), roller (beskriver relationer) och individer (specifika objekt).

Atomära komponenter

Koncept: Person, Bil, Sjukdom (klasser av objekt)

Roller: äger, kör, orsakar (relationer mellan objekt)

Individer: Anna, bil-123, influensa-2023 (specifika objekt)

Påståenden: Anna är en Person, Anna äger bil-123

Enkla beskrivningar

Grundläggande syntax:

· Person: Anna tillhör konceptet Person

· äger(Anna, bil-123): Anna äger bil-123

· Bil ⊓ Röd: 'röda bilar' (intersection av koncept)

· ∃äger.Bil: 'saker som äger en bil'

· ∀kör.Bil: 'saker som bara kör bilar'

Konceptkonstruktorer

Komplexa koncept byggs från atomära koncept genom logiska operatorer och kvantifikatorer.

Booleska operatorer

C ⊓ D: intersection (både C och D)

C ⊔ D: union (C eller D)

¬C: negation (inte C)

⊤: universella konceptet (allt)

⊥: tomma konceptet (ingenting)

Existentiella och universella restriktioner

∃r.C (existential restriction):

'Objekt som har minst en r-relation till något i C'

Exempel: ∃barn.Student = 'föräldrar till studenter'

∀r.C (universal restriction):

'Objekt där alla r-relationer går till objekt i C'

Exempel: ∀äger.Bil = 'som bara äger bilar'

Talrestriktioner

≥n r.C: 'minst n r-relationer till C-objekt'

≤n r.C: 'högst n r-relationer till C-objekt'

=n r.C: 'exakt n r-relationer till C-objekt'

Exempel: ≥2 barn.Person = 'föräldrar med minst 2 barn'

Visuell representation av beskrivningslogiska konstruktorer

Kunskapsbaser och axiom

En kunskapsbas består av TBox (terminologiska axiom om koncept) och ABox (påståenden om individer).

TBox - terminologiska axiom

Definition: Förälder ≡ Person ⊓ ∃barn.Person

Subsumption: Student ⊑ Person (alla studenter är personer)

Disjunktion: Bil ⊓ Cykel ⊑ ⊥ (bilar och cyklar är disjunkta)

Komplex: SportBil ⊑ Bil ⊓ ∃motor.StarkMotor

ABox - assertionella axiom

Konceptmedlemskap:

· Person(Anna), Student(Erik), Bil(volvo-240)

Rollassertioner:

· äger(Anna, volvo-240), barn(Anna, Erik)

· kör(Erik, volvo-240)

Negativa assertioner:

· ¬Student(Anna), ¬äger(Erik, volvo-240)

Struktur av beskrivningslogisk kunskapsbas

Resonering och slutledning

Beskrivningslogik möjliggör automatisk slutledning för att härleda ny kunskap från befintlig kunskap.

Grundläggande resoneringsuppgifter

Satisfierbarhet: Kan konceptet C ha instanser?

Subsumption: Gäller C ⊑ D (är C mer specifikt än D)?

Ekvivalens: Gäller C ≡ D (har C och D samma instanser)?

Instanscheck: Tillhör individ a konceptet C?

Subsumptionsexempel

Givet:

· Förälder ≡ Person ⊓ ∃barn.Person

· Mor ≡ Kvinna ⊓ Förälder

· Kvinna ⊑ Person

Slutledning:

Mor ⊑ Förälder (trivialt från definition)

Mor ⊑ Person (från Kvinna ⊑ Person och Förälder ⊑ Person)

Automatisk klassificering

1. Definiera SportBilÄgare ≡ Person ⊓ ∃äger.SportBil

2. Assertera SportBil(ferrari-488), äger(Anna, ferrari-488)

3. System härleder automatiskt: SportBilÄgare(Anna)

4. Anna klassificeras som sportbilägare

DL-familjen och komplexitet

Olika beskrivningslogiker har olika uttryckskraft och beräkningskomplexitet. Vanliga logiker namnges efter tillgängliga konstruktorer.

Vanliga DL-logiker

ALC: Attributive Language with Complements (grundläggande)

SHIQ: S + hierarkier, inverser, kvalificerade talrestriktioner

SROIQ: SHIQ + Self, nominaler, komplex rollaxiom

EL++: Existentiell logik med konjunktion (mycket effektiv)

Konstruktor-namnsystemet

Varje bokstav representerar en konstruktor:

· S: ALC plus transitivitet

· H: rollhierarkier (r ⊑ s)

· I: inversroller (r⁻)

· N: talrestriktioner (≥n r.C)

· Q: kvalificerade talrestriktioner

· O: nominaler ({a})

· R: komplex rollaxiom

Komplexitetslager

EL: PTIME (mycket effektiv, används i stora ontologier)

ALC: EXPTIME-complete

SHIQ: EXPTIME-complete

SROIQ: 2-NEXPTIME-complete (används i OWL 2)

Tillämpningar och ontologier

Beskrivningslogik används praktiskt för att bygga ontologier - formella beskrivningar av domänkunskap.

Medicinsk ontologi (SNOMED CT)

Sjukdomsklassificering:

· Diabetes ⊑ Sjukdom ⊓ ∃påverkar.Metabolism

· Typ1Diabetes ⊑ Diabetes ⊓ ∃orsakas.AutoimmunReaktion

· Typ2Diabetes ⊑ Diabetes ⊓ ∃relateratTill.Övervikt

Automatisk klassificering hjälper läkare med diagnoser.

E-handelsontologi

Produkt ⊑ ⊤

Elektronik ⊑ Produkt

Smartphone ⊑ Elektronik ⊓ ∃har.Pekskärm

PremiumPhone ⊑ Smartphone ⊓ ∃kostar.HögtPris

Exempel på ontologisk hierarki i beskrivningslogik

Vanliga misstag

❌ Förväxla ∃ och ∀ restriktioner

∃äger.Bil betyder 'äger minst en bil', ∀äger.Bil betyder 'äger bara bilar'

Exempel: Fel: använda ∀äger.Bil för 'bilägare' - detta utesluter att äga andra saker

❌ Glömma stängda världens antagande

I beskrivningslogik är okänd information inte falsk, bara okänd

Exempel: Om vi inte vet att Anna äger en bil betyder det inte att ¬äger(Anna, bil) är sant

❌ Överkomplicera enkla relationer

Använd enkla konstruktorer när möjligt för bättre prestanda

Exempel: Bil ⊓ ¬Cykel kan ofta ersättas med enklare disjunkta klasser

Tillämpningar

Semantiska webben

OWL (Web Ontology Language) baseras på beskrivningslogik

Exempel: Schema.org, DBpedia, Wikidata använder DL-baserade teknologier

Biomedicin och hälsa

Stora medicinska ontologier för automatiserad diagnos och forskning

Exempel: SNOMED CT, Gene Ontology, Human Phenotype Ontology

Industri 4.0

Ontologier för smarta fabriker och IoT-system

Exempel: Produktkonfiguration, underhållsplanering, supply chain management

Kunskapsgrafer

Stora kunskapsgrafer använder DL för strukturering och slutledning

Exempel: Google Knowledge Graph, Microsoft Satori, Amazon Product Graph

Övningar

1 Lätt

Uttryck 'personer som äger minst 2 bilar' i beskrivningslogik

Tips

Använd talrestriktioner med ≥ operatorn

Visa facit

Person: grundkonceptet för personer
≥2 äger.Bil: äger minst 2 objekt som är bilar
⊓: intersection (både Person och talrestriktionen)
Resultat: Person ⊓ ≥2 äger.Bil

Svar: Person ⊓ ≥2 äger.Bil

2 Medel

Definiera 'Farförälder' rekursivt och visa att Erik är farförälder till Lisa

Tips

Använd existentiell restriktion med två nivåer av barn-relationen

Visa facit

∃barn.Person: har barn som är personer (= är förälder)
∃barn.(∃barn.Person): har barn som har barn (= är farförälder)
Definition: Farförälder ≡ Person ⊓ ∃barn.(∃barn.Person)
För att visa Erik är farförälder till Lisa: barn(Erik, Anna) ∧ barn(Anna, Lisa)

Svar: Farförälder ≡ Person ⊓ ∃barn.(∃barn.Person)

3 Svår

Analysera: Vad händer om vi definierar Person ≡ ∃förälder.Person?

Tips

Tänk på cirkulära definitioner och vad som händer med Adam och Eva

Visa facit

Definitionen säger: för att vara person måste man ha föräldrar som är personer
Detta skapar oändlig regress - inga 'första personer' kan existera
Första generationen (t.ex. Adam/Eva) kan inte vara personer
Lösning: Person ⊑ ∃förälder.Person ⊔ FörstaPerson
Eller: undvik cirkulära definitioner

Svar: Cirkulär definition som leder till logiska problem

Sammanfattning

Beskrivningslogik är en familj av kunskapsrepresentationsspråk som kombinerar logisk precision med beräkningsmässig hanterbarhet. Huvudkomponenterna är koncept (klasser), roller (relationer) och individer (objekt). Komplexa koncept byggs från atomära komponenter genom booleska operatorer, existentiella/universella restriktioner och talrestriktioner. Kunskapsbaser består av TBox (terminologiska axiom) och ABox (assertionella axiom). Olika DL-logiker balanserar uttryckskraft mot komplexitet. Beskrivningslogik ligger till grund för ontologier, semantiska webben och moderna kunskapshanteringssystem.