Beskjeder undervisning
Uke 35
Læreboka er Peter Norvig: Paradigms of Artificial Intelligence Programming. På Norvigs hjemmeside finner dere mange nyttige pekere - blant annet til det jeg ellers anbefalte
I sammenlikningen mellom Scheme og Common Lisp er det et opplagt poeng at Scheme er et lite språk. Formålet med Scheme er å lage et pedagogisk vel egnet språk. Common Lisp er stort - og det er ment å brukes til store applikasjoner. Går en ned i språkene er kanskje den vesentlige forskjellen at
Se etter de 5 slots du har til hvert symbol i Common Lisp ved å bruke funksjonene
Du kan bruke setf til å endre på disse.
Du kan bruke funksjonene på andre argumentplass ved apply eller funcall. Da kan funksjonsverdier legger inn på symbolets verdiplass - og du kan (bortsett fra syntaksen) regne på det som om det var Scheme.
Lær deg hvordan du kan skifte mellom ting som legges inn på verdi-plass og funksjons-plass.
Så for å lære seg Common Lisp gå gjennom de to grammatikk-programmene i Kap 2. Først vises en grammatikk der grammatikken er bakt inn i koden. Deretter en der gramatikken er verdien til en parameter - og programmet er en interpret for slike grammatikker. Vi skal venne oss til å kode på den siste måten - og heller oppnå effektiviteten av det første programmet ved å kompilere det siste.
Som pensum i kurset har vi delene II, III, IV. Det vesentlige der er 10 store AI-program der vi ser nærmere på 8 av dem
Jeg vil at dere skal dele dere opp i grupper - hver på 2-3 stykker - og se nærmere på en av de 8 aktuelle programmene. Jeg kommer tilbake til hva hver av gruppene skal gjøre.
Uke 36
Vi ser på Newell og Simons General Problem Solver. De analyserte mange problemer til en søking i et tilstandsrom og så sin GPS som en realisering av Aristoteles mål-middel analyse. Det er altså gitt
og så skal en ved et søk komme fra start til mål ved å bruke operasjoner. Tradisjonelt har en flere former for søk
De to første forutsetter ikke noen vurdering av hvor gode tilstandene er - og kalles uinformerte. I informert søk inngår en vurdering av tilstandene - og dette brukes til enten å avskjære søket eller gi en strategi for hva som skal undersøkes først. I informert søk er det en avveining mellom hvor mye som skal huskes underveis og hvor effektiv søket skal være.
Det kan være fornuftig å se på programmet for å se om søkestrategien blir dybde eller bredde først. Dette avhenger av hvordan en behandler tilstander som er gjort klar for undersøking, men ennå ikke undersøkt.
Som regel er det et stort problem ved at tilstandsrommet blir for stort. I GPS blir hver tilstand tatt som en liste av - ferdig angitte symboler. Og så vil en operasjon være gitt ved tre lister
Dette er et opplegg som ble utarbeidet av N.Nilsson i programmene STRIPS og ABSTRIPS rundt 1970. Med dette blir arbeidet rundt tilstandene vesentlig forenklet.
Vi ser på to ulike varianter av GPS. I GPS-1 har vi gitt
Vi får problemer med GPS-1 pågrunn av måten tilstandene blir representert. Underveis husker vi ikke mer enn øyeblikksverdien til *state*. Det kan tenkes at vi måte å stryke et ønsket symbol for å oppnå et annet ønsket symbol osv.
Så til GPS-2. For det første er GPS-2 lagd ved at vi ikke bare holder orden på tilstanden vi er i, men også de tilstandene vi har vært innom. Dette gjøres ved å legge til et nytt argument i mange av funksjonene i GPS-1. For det andre ser vi hvordan vi kan lage programmer som endrer på programmene i GPS-1 og gir et innblikk i eksplorativ programmering.
Uke 37
Jeg har notert følgende grupper
Eliza er lagd av Joseph Weizenbaum. Det skulle imitere en psykiatrisk samtale. Da det kom i 1966 var det veldig vellykket. Weizenbaum forteller at han ble for alvor sjokkert da han så ansatte sette seg ved terminalene og hadde sin samtale - som de så tok veldig alvorlig.
For Weizenbaum ble dette en tankevekker. Han skrev boka "Computer power and human reasoning" etter det der han tok for seg en del av det moralske ved å programmere.
For oss er det viktig å se hvor lett programmet lurer folk. Det viktige er at en må se programmet og brukeren som en enhet - og at en kan få til kunstig intelligens ved å la intelligensen komme fra brukeren.
På toppnivå har vi en løkke
Altså lik vår read-eval-print.
Vi bruker et pattern-matching program:
Uke 38
Først to ting knyttet til verktøy
Deretter starter vi på Student. Det interessante med Student er hvordan vi kan bruke pattern-matching til å finne løsbare regnestykker i tekstoppgaver for skoleelever.
Eliza brukte de skjulte forventningene / forutsetningene i en psykiatrisk samtale. Her bruker vi det samme for tekstoppgaver. Det skal være skjulte regnestykker i dem - og programmet finner dem. Det er bare tilsynelatende samme oppgave å finne regnestykker i vilkårlig tekst.
Uke 39
Student er et program for å løse tekstoppgaver i matematikk for - la oss si - ungdomsskolen. Noen punkter
Løse likninger, søking, pattern matching er alle eksempler på assymmetriske problemstillinger. Det skal mye arbeid til for å finne løsninger, men lite til for å sjekke at løsningene er riktige. Det er god grunn til at vi skal være interessert i slike problemstillinger - og ikke de omvendte.
Uke 40
Vi ser på prolog. Jeg definerte eksekveringen av prolog ved å se på et OG-ELLER-tre som jeg kalte prologtreet. Ved eksekvering vil treet bli lagd og dekorert med info om bindinger av variable gitt ved unifikasjon
Uke 41
Jeg gjennomgikk hovedpunktene i CLOS. Hovedmekanismene var
Uke 42
Gjennomgikk Mycin med vekt på behandling av usikkerhet. Deretter Waltz' bruk av føringer for å tolke strektegninger.
Uke 43
Gjennomgår Othello og parsing i frase-struktur grammatikk.
Med Othello så ser vi på minmax med alfa-beta-avskjæring.
Parsing - vi ser på parsing av en kontekstfri grammatikk - bottom-up. Ved bruk av memoisering kan vi effektivisere parsingen voldsomt. Denne effektiviseringen bruker på en vesentlig måte at vi har en kontekstfri grammatikk. Vi memoiserer en funksjon som til en del av en setning gir forslag til hvilke delvise parsinger som finnes.
Uke 44
Gjennomgåelse av prosjekter: Student og Prolog
Uke 45
Gjennomgåelse av prosjekter: Mycin 1 og Mycin 2
Uke 46
Gjennomgåelse av prosjekter: Waltz algoritme og Othello.
Eksamen - høst 2001 - SLI 330
Utlevering: mandag 03.12 klokka 0900
Innlevering: mandag 10.12 klokka 1500 på mitt kontor (642) - eller en av SLI-lærerne
Generelt:
· oppgavene løses individuelt - samarbeid om oppgavene ikke
tillatt.
· til besvarelsene skal det gis kode og kjøringseksempler. Det
vil si at det skal leveres kode i kjørbar stand - som diskett eller som
vedlegg til mail. Videre skal det leveres kjøringseksempler slik at programmene
skal kunne vurderes uten at sensor trenger kjøre dem
· materialet er gitt ved 15 tekstfiler og et editeringsprogram som er
tilgjengelig under folk.uio.no/herman/folketelling . Det er ikke sikkert at
dere trenger alt her.
· om noen av spørsmålene er uklare, så gjør
dine egne presiseringer og redegjør for dem.
· er det ytterligere spørsmål, så vil jeg være
tilgjengelig på kontor eller via email
FOLKETELLING
Du har fått 15 tekstfiler som gir materiale fra kirkebøker / folketellinger fra distriktet rundt Fredrikstad på 1800-tallet. Materialet er i en slik form at noe må gjøres for å gjøre det tilgjengelig og nyttig. Tekstfilene finnes under
folk.uio.no/herman/folketelling
og er nummerert 1 til 15. Der ligger det også et editeringsprogram som du kan bruke - om du ikke foretrekker emacs eller noe annet. Men du må regne med at det aller meste av editeringen skal du selv gjøre med enkle common lisp programmer.
1.
Først må du bli kjent med filene. Da ser du at det kan være tull med skandinaviske bokstaver. Dette retter du opp.
Vi forutsetter at alle filene er fra tabeller der det er skilletegn for
· ny kolonne
· ny rad
Det kan godt være at noen av skilletegnene mangler i filene nå. Men vi forutsetter at det skal være samme type opplysning i hver kolonne. Typene kan være
· nummer på husstandmedlem
· navn på mann
· navn på kvinne
· yrke
· bosted
· fødselsdato
· registreringsdato
· slektskapsrelasjon
· .......
Det første programmet skal kjøre gjennom deler av en fil og så
gi forslag til hvor mange kolonner det er i den underliggende tabellen og hva
slags type informasjon det er i hver kolonne. En måte å gjøre
dette på vil være å lage en enkel statistikk over hva det
ser ut til å være i hver enkelt kolonne - navn, tall, yrke, sted
... - og så regne med at det som forekommer mest i en kolonne er det som
kolonnen burde inneholde. Du kan også først la programmet telle
hvor mange kolonner det er mellom hvert linjeskift i gjennomsnitt - for deretter
å bygge opp tabellen. Det er ikke nødvendig at programmet skal
kunne behandle alle de 15 filene, men du skal kunne si hvilke filer programmet
ditt virker bra for. Du kan anta at i hver fil er det en underliggende tabell,
men det er ingen grunn til å tro at de ulike filene har tilsvarende tabeller.
2.
Informasjonen fra filene du har valgt å behandle legges nå i en stor hash-tabell. Du er klar til videre bearbeiding. Det første problemet er å gjøre informasjonen sammenliknbar. La oss gjøre dette skrittvis
a.
Datoer må alle oversettes til en standardform. Du trenger å finne ut hvor mange måter datoer er skrevet på - for deretter å oversette.
b.
Lag en liste over yrker - og ta yrkenavn som starter på samme måte til å være like. Gjør dette slik at du ender opp med ikke alt for mange yrker.
c.
Et problem med folketellinger er ulik skrivemåte for samme navn. Det finnes en algoritme som langt på vei løser problemet. Den kalles SOUNDEX. Varianter av den finnes på web'en, og den er også beskrevet i Donald Knuths bok om algoritmer. Idéen er at vi oversetter ord til indekser slik at ord som uttales nesten likt blir oversatt på samme måte.
En beskrivelse av SOUNDEX finnes på
http://www.nara.gov/genealogy/soundex/soundex.html
3.
Med så mange registre vi har her må vi regne med at samme person kan være ført opp mange ganger. Dette prøver vi nå å unngå ved et program som prøver å identifisere slike multiple oppførsler. Her kan vi bruke sikkerhetsfaktorer for å veie de ulike kildene mot hverandre, men regner vel med at samme navn, samme fødselsår, samme navn på ektefelle er mer enn nok.
Lag så et program der vi får en ny tabell der informasjonen fra de multiple oppførslene er med.
Ta med eksempler dere har funnet som blir rettet opp.
4.
Nå ønske vi å koble sammen slektskapsrelasjoner. Da blir sikkerhetsfaktorer viktig. En dame kan for eksempel ha flere menn - men det bør ikke være samtidig og aldersforskjellen bør ikke være for stor. Legg inn informasjonene om slike slektskapsrelasjoner også i tabellen.
Ta med eksempler som dere har funnet som blir rettet opp.
5.
Et av målene med folketellingene må være å få fram slektstrær. Jeg vet ikke om det er nok informasjon i filene dere har fått utlevert til å lage slike trær, så derfor kan det tenkes at dere ikke finner gode eksempler i materialet på noe overraskende slektstre. Men lag program for generering av slektstrær.
6.
Så ønsker vi ulike statistikker fra materialet. Du kan selv gi forslag til hva du kan finne fra materialet - og vise hvordan det kan gjøres.
7.
Med de 15 filene er det jo et stort materiale dere har fått utlevert. Gi forslag til hva mer som burde gjøres med det, hvordan dette skulle kunne gjøres mer tilgjengelig og mer oversiktlig.
SLUTT PÅ OPPGAVESETTET