Kunnskapsrepresentasjon

Et hyttefelt skal få en kunnskapsbase. Den skal kunne svare på om hytte 7 er ledig i uke 28, om peisen hører til stua, og hva en helg koster. Før den første setningen skrives i førsteordens logikk, må vi bestemme hvilke begreper som finnes, og hvordan de henger sammen. Det valget er en ontologi (ontology): en formell beskrivelse av kategoriene, objektene og relasjonene i et domene. Arbeidet med å lage den kalles ontologisk ingeniørarbeid (ontological engineering).

En domene-ontologi dekker ett område, som hyttefeltet eller en musikkforretning. Over den ligger en øvre ontologi (upper ontology): det generelle rammeverket med fysiske objekter, hendelser, tid og abstrakte objekter som tall og mål. Domenebegrepene henges på under. Figuren viser en forenklet øvre ontologi vi har laget for kapitlet. Ekte øvre ontologier er langt større.

Hvorfor bry seg om toppen? To kunnskapsbaser som bygger på samme øvre ontologi, kan kobles sammen. Er både en booking og en konsert hendelser, gjelder reglene om hendelser og tid for begge, og de skrives bare én gang. Et generelt rammeverk skal derfor dekke mange domener, og det skal kunne utvides med spesialtilfeller uten at toppen må skrives om. Det er vanskeligere enn det høres ut: nesten hver generalisering har unntak, og en ontologi som skal brukes av mange, må tåle at domenene ser verden litt ulikt.

Ingen ontologi er fullstendig, og store ontologier blir til på ulike måter. Noen skrives av fageksperter aksiom for aksiom, andre hentes automatisk ut av oppslagsverk og databaser, og noen bygges av mange frivillige som legger inn ett faktum om gangen. Den første veien gir høy kvalitet og liten dekning, de andre stor dekning og mer støy.

En kunde spør om butikken har en fiolin. Det er kategorien som betyr noe, ikke hvilket eksemplar hun får. Mye av resonneringen skjer derfor på kategorinivå. En kategori (category) kan skrives som et predikat, $\text{Fiolin}(x)$, eller som et objekt, $\text{Fioliner}$. Det siste kalles reifisering (reification): kategorien blir en konstant vi kan si ting om. Da skrives medlemskap med ∈ og delmengde med ⊂:

Kategorier bundet sammen med ⊂ danner en taksonomi (taxonomy). Taksonomien organiserer kunnskapen gjennom arv (inheritance): det som gjelder alle strykeinstrumenter, gjelder også alle fioliner og hvert enkelt fiolinobjekt. Det er ƒarv gjennom delmengder:

Et objekt arver medlemskap oppover, og med det alle egenskapene som er knyttet til kategoriene over. En egenskap skrives én gang, på riktig nivå.

Tre begreper beskriver hvordan underkategorier deler opp en kategori. Har de ingen felles medlemmer, er de disjunkte kategorier (disjoint), slik ƒdefinisjonen av disjunkthet sier. En uttømmende dekomposisjon (exhaustive decomposition) dekker hele forelderen: hvert medlem er med i minst én av underkategoriene. En partisjon (partition) er begge deler, og det er ƒdefinisjonen av partisjon:

Tabellen under viser tre inndelinger fra en instrumenttaksonomi. Treblås og Messing er en partisjon av blåseinstrumentene. Strengeinstrumentene er delt inn etter hvordan strengen settes i sving, og den inndelingen er uttømmende uten å være disjunkt: en fiolin strykes, men den kan også klimpres. Fløyter og klarinetter er disjunkte, men dekker ikke alle treblåseinstrumenter.

Ikke alle hierarkier handler om kategorier. Peisen er en del av stua, og stua er en del av hytta. Relasjonen her er del-av-relasjonen (PartOf), som beskriver hvordan objekter er satt sammen av andre objekter:

Relasjonen er transitiv, som setningen viser, og refleksiv: alt er en del av seg selv. Den er ikke medlemskap. Peisen er en del av hytte 7, men den er ingen hytte og ikke medlem av kategorien Hytter. Sammensatte objekter beskrives ofte med strukturelle relasjoner i tillegg, for eksempel at hver hytte har nøyaktig én stue.

Med mål og enheter (measures, units) får objektene tallverdier. Et mål skrives som en enhetsfunksjon brukt på et tall, ikke som et nakent tall:

Enhetene kobles med aksiomer for omregning, som $\text{Centimeter}(100\cdot x)=\text{Meter}(x)$, og mål med samme dimensjon kan sammenlignes og legges sammen. Et mål trenger ikke ha tall. Utsikten fra en hytte har ingen enhet, men den kan ordnes: $\text{Utsikt}({\text{Hytte}}_7)>\text{Utsikt}({\text{Hytte}}_3)$. Det holder for å resonnere om hvilken hytte som har best utsikt.

Bookingene i hyttefeltet endrer hvilke hytter som er opptatt. Et faktum som er sant noen ganger og usant andre ganger, kalles en fluent, for eksempel $\text{Opptatt}({\text{Hytte}}_7)$. I en hendelseskalkyle (event calculus) er både fluenter og hendelser objekter, og predikater sier når ting skjer:

• •$T(f,t)$: fluenten $f$ er sann ved tidspunktet $t$.
• •$\text{Happens}(e,i)$: hendelsen $e$ skjer over intervallet $i=(t_1,t_2)$, fra $t_1$ til $t_2$.
• •$\text{Initiates}(e,f,t)$ og $\text{Terminates}(e,f,t)$: hendelsen $e$ gjør $f$ sann eller usann ved $t$.
• •$\text{Clipped}(f,i)$ og $\text{Restored}(f,i)$: $f$ blir usann eller sann et sted i intervallet $i$.

Hvert predikat har samme antall argumenter overalt: tidspunkter i $T$, $\text{Initiates}$ og $\text{Terminates}$, ett intervall i de tre andre. Kjernen er at en fluent forblir sann fra en hendelse starter den, til en annen hendelse avbryter den. Det er ƒfluent-aksiomet:

Innsjekken 3. juli starter $\text{Opptatt}({\text{Hytte}}_7)$. Skjer ingen utsjekk før 5. juli, er hytta opptatt 5. juli.

Hendelser varer, så hver hendelse har et tidsintervall (time interval) med start $\text{Begin}(i)$ og slutt $\text{End}(i)$. Hvordan to intervaller ligger i forhold til hverandre, beskrives av Allen-relasjonene. To av dem er ƒdefinisjonene av Meet og Before:

Tabellen viser sju relasjoner med bookinger av samme hytte. Med de omvendte blir det 13, og med de strenge definisjonene av Starts og Finishes i tabellen gjelder nøyaktig én av dem for to intervaller. Et øyeblikk er et intervall uten varighet, der start og slutt faller sammen.

Koden under finner relasjonen mellom to bookinger du stiller inn selv.

start_a = 2  # @param 0..10
slutt_a = 6  # @param 1..12
start_b = 4  # @param 0..10
slutt_b = 9  # @param 1..12

# To bookinger av samme hytte, i dager. Relasjonene sjekkes i fast rekkefølge.
def relasjon(sa, ea, sb, eb):
    if ea < sb: return "Before(A, B)"
    if eb < sa: return "Before(B, A)"
    if ea == sb: return "Meet(A, B)"
    if eb == sa: return "Meet(B, A)"
    if (sa, ea) == (sb, eb): return "Equals(A, B)"
    if sa == sb: return "Starts(A, B)" if ea < eb else "Starts(B, A)"
    if ea == eb: return "Finishes(A, B)" if sa > sb else "Finishes(B, A)"
    if sb < sa and ea < eb: return "During(A, B)"
    if sa < sb and eb < ea: return "During(B, A)"
    return "Overlap(A, B)" if sa < sb else "Overlap(B, A)"

def vis(s, e):
    return f"[{s}, {e}]" if s < e else "ugyldig (start etter eller lik slutt)"

print(f"Intervall A: {vis(start_a, slutt_a)}")
print(f"Intervall B: {vis(start_b, slutt_b)}")
if start_a < slutt_a and start_b < slutt_b:
    print(f"Relasjon: {relasjon(start_a, slutt_a, start_b, slutt_b)}")
else:
    print("Relasjon: ingen (et intervall er ugyldig)")

Logikk er ikke den eneste måten å skrive ned en ontologi på. Et semantisk nett (semantic network) tegner den som en graf: kategorier og objekter er noder, og kantene er relasjoner. DelmengdeAv binder en kategori til kategorien over, MedlemAv binder et objekt til kategorien sin, og egenskaper henger ved den kategorien de gjelder for. Arv blir da å følge kantene oppover til den første noden som har egenskapen.

Klarinetten K1 er MedlemAv Treblås. Nettet finner «lyd fra: luftsøyle» ved å gå fra K1 til Treblås og videre til Blåseinstrumenter. Å følge kanter er raskt, og det er en hovedgrunn til at semantiske nett har vært populære. Et objekt kan også ha en egen verdi som overstyrer den arvede. En saksofon regnes som et treblåseinstrument, men den er laget av messing. Den egne verdien vinner, fordi den står nærmest objektet. En slik standardverdi som kan overstyres, går ut over vanlig førsteordens logikk.

Semantiske nett har også grenser. En kant binder to noder, så relasjoner med tre eller flere argumenter må reifiseres som egne objekter. Nettet kan heller ikke uttrykke negasjon eller disjunksjon: «K1 er ikke stemt» og «K1 er en klarinett eller en obo» har ingen kant.

En beskrivelseslogikk (description logic) går en annen vei. Den er et logisk språk for å definere kategorier ut fra enklere kategorier og relasjoner:

De to viktigste oppgavene er subsumpsjon (subsumption), om én kategori er en delmengde av en annen ut fra definisjonene alene, og klassifisering (classification), om et objekt eller en ny kategori hører til en kategori. Definerer vi en ny kategori Trio som et ensemble med $\text{AtLeast}(3,\text{Musiker})$ og $\text{AtMost}(3,\text{Musiker})$, plasserer klassifiseringen den automatisk under alle kategorier den er subsumert av, for eksempel et kammerensemble definert som et ensemble med høyst ni musikere. Språket er så begrenset at begge oppgavene kan avgjøres raskt, i polynomisk tid for de enkleste variantene, mens det samme spørsmålet i full førsteordens logikk kan være uavgjørbart. Prisen er uttrykkskraft: mange beskrivelseslogikker mangler negasjon og disjunksjon.