729G10 Artificiell intelligens I

Laboration 4: Kunskapsrepresentation

Sammanfattning

Er uppgift är att skriva funktioner för att representera och manipulera kunskap i ett frames-system. Några utmärkande (men inte unika) egenskaper för strukturerade representationsformer är egenskapsärvning, skönsvärde (defaults) och procedural attachments (ungefär associerade procedurer, Russel & Norvig s. 456, 466). Kursboken, avsnitt 12.5, innehåller en del information.

Syfte

Syftet med denna laboration är att ge en inblick i hur man kan lagra kunskap om objekt, objektens egenskaper och relationer mellan objekt i ett s.k. frames-system, samt hur ett sådant kan implementeras.

Förberedelser

För att kunna utföra laborationen så snabbt och enkelt som möjligt, förbered er väl:

Läs igenom laborationsinstruktionerna.
Fundera på vilken domän ni vill representera i ert frames-system. Välj en av domänerna från listan och brodera ut lagom mycket, eller kom på er egen domän:
- Klassificera djurarter enligt vetenskaplig taxonomi (i stil med typ, art, individ).
- Kategorisera böcker i genre och delgenre.
- Växter och blommor, klassificera enligt vetenskaplig taxonomi eller hur de kan användas i landskapsplanering.
- Mat och dryck, lagra t.ex. information om pris, när det ätes (huvudrätt/efterätt), typ av mat (kött/fisk/vegetariskt).
- Fortskaffningsmedel kan sorteras enligt hur de tar sig fram, om man behöver licens, antal passagerare, maxhastighet.
- Geografisk information kan lagras, t.ex. politisk uppdelning, klimat, demografiska och ekonomiska fakta.
Om ni väljer en egen domän ska denna godkännas av assistenten innan ni går vidare, för att domänen på ett naturligt sätt ska kunna beskrivas i ett frames-system. Tänk på att det måste gå att representera hierarkiskt.

Er hierarki ska innehålla minst 10 instanser och ha ett djup på minst tre nivåer. Inför denna laboration kan ni kan utgå från kodskalet i kurskatalogen: ~729G10/Kursbibliotek/Lab4/.

Lite Framesteori

I ett frames-system lagras kunskapen inte som logiska satser utan i strukturer där egenskaper och begrepp som är relaterade till varandra på något sätt samlats på ett ställe. Teoretiskt kan alla frames-system (och semantiska nät) uttryckas i FOPL, men praktiskt kan det vara lämpligt att organisera kunskapen som den används och som de flesta av oss konceptualiserar den. Mer om detta kan läsas i Elaine Rich och Kevin Knights bok Artificial Intelligence 2:nd ed.

I frames-system brukar man tala om ramar (frames) och attribut som de grundläggande datastrukturerna. En ram kan ses som en beskrivning av ett objekt eller av en klass av objekt. En ram består av ett ram-namn och en mängd av attribut. Attributen i sin tur består av ett attributnamn och ett värde.

Något som gör frames-system intressanta är hanteringen av värden för attribut. Ett frames-system kan bland annat innehålla skönsvärden (default). Om ett objekt saknar ett värde för ett attribut kan man utgå ifrån att det har samma värde som objektets kategori. Om en struts vikt är okänd, kan man anta att den väger 70 kg eftersom det är den normala vikten för en struts. Procedural attachments och ärvning är värda en närmare förklaring:

Procedural attachments

Procedural attachments är en allmän term för kategorispecifika metoder för att hämta och sätta värden, infogade utan att andra delar av systemet egentligen behöver bry sig om att de är procedurer - de är "transparenta". Om vi till exempel har en ram som hanterar trianglar, så behöver man inte uttryckligen lägga in både bas, höjd och area. Arean kan istället beräknas automatiskt när det värdet efterfrågas, utifrån basen och höjden i triangeln. Det här kallar vi en ask-association.

Ärvning

Ofta kan vi strukturera de objekt vi vill beskriva i en hierarki, till exempel Fordon - Bil - Saab - bilen HXC 123. Det är därför naturligt att vi kan göra samma sak med de ramar som vi skapar. En hierarki kan beskrivas med hjälp av ISA-relationer, där Saab ISA Bil betyder att alla objekt i klassen Saab också är objekt av typen Bil. En ram som lagras på en högre nivå i hierarkin tolkas därmed som mer generell än underliggande ramar. Detta medför att ramar som representerar objekt endast förekommer längst ned i hierarkin - dessa kallas instanser. Tanken är att de attribut och värden som är gemensamma eller typiska för en klass lagras i klass-ramen, medan de särskiljande attributen och värden lagras i underliggande ramar. Sedan låter vi de senare ärva egenskaper från ovanstående ram. Att organisera kunskapen på detta sätt, i en så kallad ärvningshierarki, är en vanlig metod som används i bland annat expertsystem.

För att vara noga finns det olika sorters relationer som kan representeras av hierarkier i frames-system. Även om vi i labben benämner relationen ISA så kan domäner med relationen "PARTOF" lagras och behandlas på samma sätt utan problem. PARTOF innebär att det aktuella objektet är en del av ett annat objekt och därmed kan dela vissa egenskaper. I en domän med länder och städer, gäller till exempel att varje stad är PARTOF ett land of har samma värde för attributet statsskick som landet. (Man måste ändå se upp - attributet invånarantal är förstås inte samma.)

Utförande

Labben utförs genom att implementera en arkitektur för att hantera frame-system. Ni ska sedan använda er av den implementerade arkitekturen för att lagra information om en vald domän. Dessutom ingår en reflektion kring kunskapsrepresentation och frame-system.

Arkitektur

Implementationen av frame-systemet kräver tre klasser, vilka visas i diagramet nedan.

Klassen Frame innehåller information om en enskild ram. Den kommer att finnas i en instans för varje enskild ram i er hierarki. Kunskapsbasen innehåller alla frames i systemet. FrameSystem är huvudklassen i systemet. Här finns de metoder som anropas av användaren av frame-systemet. Klasserna och deras innehåll beskrivs mer i detalj nedan.

Frame

Den här klassen utgör en generell struktur för ramar samt metoder för att skapa och uppdatera sådana. (Notera att även om man konceptuellt kan dela upp ramar i kategorier och instanser, så lyder de samma mekanismer. Det är därför onödigt att ha två uppsättningar kod.)

Ramar innehåller exempelvis namn, isa och en mängd attribut, samt metoder för att sätta och hämta värden på attribut.

KnowledgeBase

Om ni ska kunna manipulera information i era ramar måste ni lagra dem på något sätt. Skapa därför en klass som utgör denna kunskapsbas. Kunskapsbasen innehåller en mängd ramar.

Ni kan använda en "dictionary" i kunskapsbasen. En enkel kunskapsbas KB skulle då kunna se ut på följande sätt.

Nyckel

Ram

top

namn	ISA	attribut
top	nil	{}

djur

namn	ISA	attribut
djur	top	{levande: ja}

människa

namn	ISA	attribut
människa	djur	{använder: [hjärna, redskap], antal_ben: 2}

Kunskapsbasen behöver metoder för att skapa och hämta en ram med ett givet namn.

FrameSystem

Den här klassen utgör huvudstrukturen för frames-systemet. Den innehåller en kunskapsbas samt de metoder som behövs för att ställa frågor (ask) och lagra information (tell) i kunskapsbasen. Den innehåller även metoder för att lagra ramar, samt information om attributens get- och put-metoder.

store_frame

Denna metod används för att lägga in en ny ram i frame-systemet. Den tar namnet på den nya ramen samt namnet på den ram som den nya ramen ärver ifrån som argument.

store_attribute

Denna metod används för att lagra information om vilken typ ett visst attribut har. Den måste anropas för varje attribut innan det används i tell.

Attribut kan ha olika get- och put-metoder. Get-metod innebär på vilket sätt information om attributet ska hämtas. Put-metod innebär på vilket sätt information om attributet ska lagras. Följande fall förekommer:

Put-metoder:
- Ersätt: Det nya värdet för attributet ersätter det gamla värdet.
- Lägg till: Attributet kan ha multipla värden, det nya värdet ska läggas till de värden som redan finns.
Get-metoder:
- Ärvning: om det finns ett värde för det efterfrågade attributet i ramen returneras detta, i annat fall söker frames-systemet efter ett värde som kan ärvas
- Lokalt värde: om det finns ett värde för det efterfrågade attributet i ramen returneras detta, i annat fall genereras ett felmeddelande som talar om att värdet saknas, d v s ingen ärvning sker (ärvning är m.a.o. förbjuden för det givna attributet)

I store_attribute ska ni lagra vilken put- och get-metod som ett attribut använder. Denna information lagras lämpligen i FrameSystem-klassen.

TIPS:

Ett sätt att lagra attribut-infon på är att ha två dictionary, en som kopplar ihop attribut och get-metod och en som kopplar attribut och set-metod. Dessa kan då användas i ask respektive tell för att avgöra på vilket sätt attributet ska hämtas eller lagras.

En smidig lösning är att ha fyra undermetoder i FrameSystem. Två som utför lagring på de två olika sätten beskrivet ovan, och två som utför hämtning av värden. Attributen kan då lagras i en dictionary direkt kopplade till den undermetod som utför hämtning/lagring på rätt sätt. Om man gör på detta sätt kan man i ask respektive tell direkt anropa den undermetod som utför hämtning/lagring på det sätt som passar det efterfrågade attributet genom att slå upp rätt metod i denna dictionary.

tell

Denna metod används för att lagra information i kunskapsbasen. Metoden ska ta namnet på en kategori eller instans, ett attributnamn samt ett värde som argument. Er metod ska kunna hantera de två olika set-metoder som beskrivs ovan. Dessutom kan det vara så att det angivna attributet än så länge saknas i kategorin eller instansen och därför måste skapas och läggas till.

Om tell används för ett attribut som inte är känt av systemet ska ett felmeddelande ges.

Värdet för attribut kan vara av två typer, antingen kan det vara ett enkelt värde, till exempel ett tal eller en sträng eller så kan det vara en procedural attachment. För att inkludera procedural attachments är den bästa lösningen att låta varje ram innehålla kopplingar från attributnamn till motsvarande attachment för de attribut som ska kopplas till attachments. Attachments lagras då i form av namnet på en metod. Mindre flexibla lösningar godkänns också, men då ska skillnaderna pekas ut i diskussionen.

ask

Denna metod används för att ta fram lagrad information ur kunskapsbasen. Metoden ska ta namnet på en ram och ett attributnamn som argument och returnera värdet för attributet om det finns något. Annars ska ett felmeddelande ges. Er metod ska kunna hantera attribut som har de put-metoder som beskrivs ovan. Den ska även kunna hantera värden både av enkel typ, och som utgörs av procedural attachment.

Om ask används för en ram eller ett attribut som inte är känt av systemet ska ett felmeddelande ges.

Det är också mycket lämpligt att använda hjälpmetoder som dessa fyra huvudmetoder använder.

Lagra information

Lägg in information om er domän i frames-systemet. Informationen om er domän ska vara skild från koden för frames-systemet. Detta är en vanlig tumregel, som gör systemet lättare att förstå och domänen lättare att utöka i efterhand, eller till och med att ersätta helt och hållet.

Er hierarki ska innehålla minst tio instanser och ha ett djup på minst tre nivåer. Det ska finnas minst ett attribut av varje typ med avseende på get- och put-metod. Det ska finnas minst en procedural attachment. Informationen ni lagrar ska ha en rimlig struktur som speglar hur er domän ser ut i verkligheten. Era frames ska utgöra en rimlig hierarki, och era attribut ska vara av lämpliga typer, och ha rimliga värden.

Skriv in och spara de metodanrop som behövs för att skapa kunskapsbasen i slutet av filen så att ni inte behöver bygga upp den varje gång ni startar om idle.

Er lösning ska vara tillräckligt generell för att exemplet nedan ska kunna köras och ge liknande utskrifter när ni är färdiga med labben: # Skapa en tom kunskapsbas animalKB = KnowledgeBase() # Skapa Frame-systemet och lägg till kunskapsbasen FS = FrameSystem(animalKB) ##STORE_FRAME # Skapa en ram (Frame) för varje djurart/grupp FS.store_frame('Djur', None) FS.store_frame('Däggdjur', 'Djur') FS.store_frame('Kräldjur','Djur') FS.store_frame('Katt','Däggdjur') FS.store_frame('Pelle','Katt') ##STORE_ATTRIBUTE # Skapa attributen som ska kunna användas databasen FS.store_attribute('varmblodig', FS.inherit, FS.replace) FS.store_attribute('barn', FS.local, FS.add) FS.store_attribute('födelseår', FS.local, FS.replace) FS.store_attribute('namn', FS.local, FS.replace) FS.store_attribute('har_svans', FS.inherit, FS.replace) FS.store_attribute('ålder', FS.local, FS.replace) ##TELL # Lägg till attributvärden för ramarna FS.tell('Djur','varmblodig',False) FS.tell('Däggdjur', 'varmblodig', True) FS.tell('Katt', 'har_svans', True) FS.tell('Pelle', 'födelseår', 2008) FS.tell('Pelle', 'har_svans', False) FS.tell('Pelle', 'namn', 'Pelle Svanslös') # Lägg till flera värden till samma attribut FS.tell('Pelle', 'barn', 'Maj') FS.tell('Pelle', 'barn', 'Muff') FS.tell('Pelle', 'barn', 'Murre') # Ersätt ett tidigare satt värde FS.tell('Pelle', 'födelseår', 1939) # Värdet på 'ålder' är i det här fallet en 'procedural attachment'. Ni behöver inte # implementera just denna utan kan skapa en/flera som är specifik(a) för just er domän. FS.tell('Pelle', 'ålder', calculate_age) ##ASK print FS.ask('Pelle', 'varmblodig') >> True print FS.ask('Pelle','barn') >> ['Maj','Muff','Murre'] print FS.ask('Katt','har_svans') >> True print FS.ask('Pelle','har_svans') >> False print FS.ask('Pelle','ålder') >> 73 # Även fel ska hanteras FS.tell('Kräldjur','kan_simma',True) >> Attributet 'kan_simma' finns inte tillagt i databasen FS.tell('Krokodil','ålder',calculate_age) >> Ramen 'Krokodil' finns inte i databasen print FS.ask('Katt','ålder') >> Attributet 'ålder' finns inte för 'Katt' None print FS.ask('Peeeeeelle', 'barn') >> Ramen 'Peeeeeelle' finns inte tillagd databasen None print FS.ask('Pelle','bbaarn') >> Attributet 'bbaarn' finns inte tillagt i databasen None

Felhantering

Ert frame system ska vara robust, och inte krascha vid felaktig indata. Om man till exempel anger ett felaktigt attribut- eller framenamn till tell eller ask så ska ett rimligt felmeddelande ges, och det ska gå att fortsätta köra programmet. Ert program ska minst klara av följande fel:

Felaktiga frame-namn till ask och tell, d.v.s felstavade namn, eller namn på frames som inte lagrats genom ett anrop till store_frame
Felaktiga attributnamn till ask och tell, d.v.s felstavade namn, eller namn på attribut som inte lagrats genom ett anrop till store_attribute
Anrop till store_frame med en ISA som ej finns

Diskussion

Skriv en diskussion om hur ni implementerat ert frames-system, samt vilka fördelarna och nackdelarna är med er implementation.
Fundera på och diskutera hur kunskapsrepresentation i frames skiljer sig från predikatlogik.
Fundera på och diskutera vilka de största fördelarna och nackdelarna med frames respektive predikatlogik är.

Redovisning och bedömning

Den här laborationen redovisas genom att lämna in följande:

Skicka in koden för det färdiga frames-systemet till Labbass.AI@gmail.com samt lämna in en utskrift av densamma i Jody Foos fack.
Lämna in er diskussion skriftligen.

Stilkrav på koden

Det är av vikt att er lösning inte bara fungerar, utan också är läsbar. Assistenten ska kunna läsa koden och se att den löser labbuppgiften. För att göra det här möjligt, behöver er kod:

ha beskrivande namn för variabler och procedurer,
innehålla kommentarer som kortfattat beskriver syftet med åtminstone varje procedur och för variabler och kod där det ej är uppenbart hur koden fungerar,
vara abstraherad genom att använda egna små procedurer för att hantera de datastrukturer ni själva skapat, och
vara robust för felaktig indata. Programmet ska inte krascha om man till exempel använder ett attribut som inte lagrats än, utan ge ett rimligt felmeddelande.

Krav för godkänt

För godkänt krävs att ni skapar ett system i vilket man kan lagra och söka efter data på så sätt som beskrivis ovan. Systemet ska innehålla åtminstone en procedural attachment som kan köras när ett värde till ett attribut efterfrågas. Koden ska vara läsbar. Diskussionen ska även visa på att ni kan koppla ihop teori med praktik.

Krav för väl godkänt

För väl godkänt ställs samma krav som för godkänt, utöver det läggs extra vikt på följande punkter:

Koden är så väl abstraherad att kunskapsbasen är helt separerad från metoderna för att manipulera den att det går att koppla in en helt ny kunskapsbas utan att ändra i dessa metoder.
Koden är lättläst, enligt stilkraven ovan.
Diskussionen visar på att ni kan sätta in laborationen i ett större perspektiv.
Laborationen är inlämnad i tid.

Sidansvarig: Arne Jönsson

Institutionen för datavetenskap