Kunstmatige intelligentie

Het vak Kunstmatige intelligentie, ook wel AI (van Artificial Intelligence) genoemd, wordt verzorgd door dr. W.A. (Walter) Kosters, geassisteerd door drs. J. (Jeroen) Eggermont, en wordt in het voorjaar van 2001 verzorgd.

Collegetijden: woensdagen, van 11.15 tot 13.00 uur, in zaal 405 van het gebouw van Wiskunde en Informatica, Niels Bohrweg 1, Leiden. Data: 17 januari tot en met 11 april, en 25 april 2001.

De tentamendata in 2001 waren:

vrijdag 1 juni 2001, 14.00 - 17.00 uur, zaal 174; en dit was het tentamen (in PostScript) met uitwerking (in PostScript);
vragenuur: woensdag 30 mei 2001, 14.00 uur, zaal 401;
hertentamen: maandag 13 augustus 2001, 14.00 - 17.00 uur, zaal 402; en dit was het tentamen (in PostScript) met uitwerking (in PostScript).

Het vak levert 4 studiepunten op. Naast het voldoende maken van het tentamen is het hiervoor ook nodig het practicum voldoende te hebben. Het eindcijfer wordt namelijk als volgt berekend: (2 keer het tentamencijfer plus 1 keer het cijfer voor het practicum) gedeeld door 3, mits tentamencijfer en practicumcijfer beide voldoende zijn. Bij nader inzien is dit geworden (wat overigens meestal op hetzelfde neerkomt :-): het eindcijfer wordt bepaald door het tentamencijfer, afgerond in de richting van het practicum. Het practicumcijfer is het gewone gemiddelde van de vier opgaven; deze moeten ieder voor zich minstens met een 5 beoordeeld zijn, en het gemiddelde zelf dus minstens een 6.
Het college is in eerste instantie bedoeld voor derde- en hogerejaars studenten Informatica, maar is ook interessant voor andere belangstellenden; voorkennis van de programmeertaal C++ is sterk aan te raden.

Gebruik wordt gemaakt van het boek Artificial intelligence, A modern approach van Stuart Russell en Peter Norvig, Prentice Hall, 1995. De paperback-uitgave is soms overigens aanzienlijk goedkoper dan de gebonden versie, maar andere keren zijn ze weer even duur. De vaak aangekondigde en lang verwachte nieuwe druk van dit boek is helaas niet op tijd klaar voor het college. Hij staat nu aangekondigd voor eind 2001 :-(.
In het bijzonder worden uit dit boek de volgende hoofdstukken behandeld: 1 (lezen), 2 (lezen), 3 (uitgebreid), 4 (uitgebreid), 5 (uitgebreid), 6 (lezen, met name Wumpus), 7 (lezen, met name Wumpus), 15 (uitgebreid; niet p. 448/452, 15.5, 15.6), 18 (uitgebreid, met name ID3: 18.3 en 18.4), 19 (uitgebreid, met name Neurale netwerken), 20 (uitgebreid, met name Genetische algoritmen) en 25 (+ Lego-robots; lezen), niet noodzakelijk in deze volgorde.
Daarnaast wordt nog speciaal aandacht besteed aan het onderwerp Data mining. Een algemene, goed leesbare, introductie hiervoor is te vinden in het boek Data mining van Pieter Adriaans en Dolf Zantinge, Addison-Wesley, 1996.
Een ander aan te raden boek is trouwens Machine learning van Tom M. Mitchell, McGraw-Hill, 1997.

Er is meer informatie te vinden over het college de afgelopen jaren; hier zijn onder andere oude tentamens (gefabriceerd door andere docenten!) te bekijken, zoals het redelijk representatieve tentamen van 8 juni 1998 [NIET Opgave 4] met uitwerking [beide gezipt PostScript].

Het practicum

Voor iedere practicumopgave moeten worden ingeleverd: een drie pagina's tellend verslag in LaTeX, en een werkend programma (digitaal en uitgeprint). Het verslag moet een duidelijke opbouw hebben, bijvoorbeeld:

Inleiding ("dit is de tweede opdracht van het college ...")
Uitleg probleem ("de spelregels zijn ...", gebruikte definities)
Aanpak ("een drielaags neuraal netwerk ...")
Implementatie ("een dubbel array")
Conclusie ("ging fout als de testopstelling niet verlicht was")
Referenties ("handleiding Lego-robots")
Appendix: het programma

De deadlines zijn redelijk strikt, overleg eventueel met de docenten. Voor alle opdrachten geldt dat ze nog voorlopig zijn, aanvullingen tijdens het semester zullen zeker voorkomen. Eigen initiatief wordt -na overleg- op prijs gesteld.
De opgaven worden per stuk als volgt beoordeeld: er wordt gekeken naar het verslag en het programma (met name werking en leesbaarheid); originaliteit beinvloedt de eind-afronding. De cijfers zijn hier te vinden.
Het practicum bestaat zoals gezegd uit vier opgaven:

Spel(l)en
Bekijk het bekende spelletje Mijnenvegen. Geef regels om het aanklikken van zeker veilige of eventuele bijna veilige velden te ondersteunen. Zeer interessante situaties ontstaan bijvoorbeeld tijdens het eindspel, wanneer zelfs kennis over het aantal nog aanwezige maar onontdekte mijnen kan helpen!
Meer concreet:
- Schrijf een eenvoudig (*) niet-grafisch C++-programma dat het spel Mijnenvegen speelt: als een speler een coordinatenpaar geeft krijgt hij/zij te horen hoeveel van de (maximaal 8) onmiddellijke buren een mijn bevatten. Steeds wordt het hele speelveld afgedrukt.
  (*) Gebruik alleen iostream.h.
- Geef minstens een drietal eenvoudige regels (en implementeer deze) die veilig te vragen vakjes opleveren. De meest eenvoudige is (en die telt niet mee :-): als ergens 0 buurmijnen zijn, kun je alle buren vragen. Bedenk een geschikte representatie, en formuleer de regels als "conditie-actie-regels".
- Bedenk en implementeer een heuristische functie die alle nog ongevraagde vakjes waardeert. Als een vakje 0 buurmijnen heeft, hebben de buren alle de hoogste (of als je het andersom doet: de laagste) waarde; vakjes waar je niks van weet hebben de laagste waarde - als er nog mijnen over zijn tenminste. Eventueel kun je gebruiken: als er nog m onbekende buren zijn van een vakje met waarde n (bekende mijnen reeds verdisconteerd) is de kans op een mijn per buurvakje n/m.
- Opmerkingen:
  - Je kunt het spelen beperken tot het kiezen van een vakje, waarna voor dit vakje het aantal buurmijnen wordt opgeleverd (en ook voor alle al eerder gekozen vakjes).
  - Als regels aanslaan, kunnen deze als suggestie worden gepresenteerd. Een flauw voorbeeld:
    REGEL "ALS buurmijngetal = 0 DAN vraag onbekende buur" slaat aan op vakje (4,5).
In te leveren: geprint verslag plus code. Deadline: woensdag 14 februari 2001.
Robotica
Er moeten Lego-robots geprogrammeerd worden in een soort C-variant (handleiding (288 kB, PDF; geschreven door Mark Overmars)), dit om uit een doolhof te geraken. Lees ter inspiratie maar eens het verhaal over de Wumpus world (zie ook http://www.liacs.nl/home/jeggermo/Wumpus/ voor een C++-versie) in Russell/Norvig, Hoofdstuk 6.
In het media lab (achter de gebogen muur bij de ingang van het gebouw) staan te zijner tijd Lego-robotjes klaar. In eerste instantie hoeven ze niet "verbouwd" te worden. Ieder tweetal kan na reservering twee keer een halve dag werken met de speciale computer die hiervoor nodig is; handleidingen zijn ter plekke aanwezig. Toegangscodes en paswoorden zijn verkrijgbaar bij de docent.
Meer concreet:
- Er is een doolhof, waarbij de muren uit bakstenen bestaan. De robot (agent) moet de ene uitgang zien te vinden. Schrijf allereerst een redelijk random manier van lopen.
- Zorg ervoor dat de robot uit een hoek kan komen.
- Nu zijn op diverse plekken CD's en munten en gekleurde papiertjes (of andere platte voorwerpen) gelegd. Laat de robot deze zien te vinden - gebruik geluidssignalen.
- Laat de agent ook nog een eenvoudig geheugen gebruiken, en bij de uitgang met geluidsignalen of via de "Datalog" het aantal gevonden soorten voorwerpen aangeven. De uitgang wordt gemarkeerd met een tweetal verlichte CD's.
In te leveren: geprint verslag plus code; en eventueel demonstratie. Deadline: woensdag 7 maart 2001 (eventueel een week later :-).
Data mining
Bekijk de weblogfiles van een webserver, op die van Informatica is dat /var/log/httpd/access_log (alleen te benaderen vanuit een CGI-script, een Perl-programma, in je eigen public_html-directory). Probeer een agent te maken die hier intelligent (in ons geval met ID3) naar kijkt, bijvoorbeeld de webzoekmachines in herkent - zonder in eerste instantie bekende ip-adressen of nog meer spiders (en gesorteerd in een file, nog zonder de Nederlandse; de eerste twee of drie getallen uit het adres zijn meestal voldoende; met dank aan John) te gebruiken. En voor de liefhebbers: wordt er door de week vaker op "serieuze" adressen geklikt?
Meer concreet:
- Schrijf een eenvoudig Perl-programma om de invoer in het juiste formaat te brengen, oftewel om de weblogfile van de server te halen. (Deze stap mag eventueel overgeslagen worden.)
- Schrijf een C++- of liever nog Perl-programma dat de zoekmachines herkent in de weblogfile. Er mag ook gecombineerde informatie gebruikt worden, bijvoorbeeld de tijden tussen opeenvolgende hits.
- Maak nu met behulp van ID3 een kleine zoekboom (diepte: TWEE) voor de classificatie; gebruik eventueel de eerder gevonden resultaten of een lijst met bekende ip-adressen, zie boven. Leg dit overigens duidelijk uit in het verslag. Mogelijke attributen zijn: protocol, dag, tijd (bijvoorbeeld met attribuutwaarden nacht, ochtend, middag, avond), aantal hits vanaf zelfde ip-adres binnen x seconden, soort file, servercode (200, 404, ...), eerste getal ip-adres, ...
In te leveren: geprint verslag plus code. Deadline: woensdag 4 april 2001 (was woensdag 28 maart 2001).
Neurale netwerken en Genetische algoritmen
Deze opgave bestaat uit twee onafhankelijke delen:
- Schrijf in C++ een neuraal netwerk met één verborgen laag dat een redelijk ingewikkelde functie, bijvoorbeeld ( 10*sin((x*x)/3) + cos(x) + x*x ) / 47 op het interval [0,6], benadert. Beoogde lengte van het programma: ruim honderd regels.
  Het netwerk heeft één invoerknoop en één uitvoerknoop, en een tussen 1 en 40 in te stellen aantal verborgen knopen. Gebruik BackPropagation als leermethode; redelijke waarden zijn: leersnelheid 0.9, aantal verborgen knopen 3 en 100000 epochs. Gebruik gnuplot om voor het verslag enkele grafieken te plotten, bijvoorbeeld met verschillende aantallen verborgen knopen, leersnelheden en stopcriteria. Als je aan het eind van je programma alle duos (x,y) afdrukt in een file (zeg net.uit; één duo per regel), waarbij x met kleine stapjes door het interval [0,6] loopt terwijl y de bijbehorende uitvoer van het getrainde netwerk is, dan kun je in gnuplot eenvoudig een grafiekje van netuitvoer en beoogde functie maken met behulp van: gnuplot> plot "net.uit", (10*sin(x*x/3)+cos(x)+x*x)/47 Hierbij kun je eenvoudig PostScript-uitvoer genereren door gnuplot> set terminal postscript eps
  gnuplot> set output "file.ps" vlak voor het plot-commando te geven. Kijk verder in de LaTeX-handleiding (Hoofdstuk 4.1) hoe je PostScipt-files in LaTeX kunt importeren.
  Aan neurale netwerken wordt overigens ook een speciaal college gewijd.
- Schrijf in C++ een genetisch algoritme om Japanse puzzels mee op te lossen. Zie ook de voorbeeldfile voor meer uitleg. Beoogde lengte van het programma: ruim tweehonderd regels.
  Neem aan dat we een klein vierkant, zeg een 5-bij-5 array hebben, waarvoor een "Japanse puzzel" gespecificeerd is. Oplossingen zijn strings met 25 bits die aan de eisen voldoen - leg de rijen van het array maar achter elkaar; de oplossingen hoeven overigens niet altijd uniek te zijn. De fitness-functie is bijvoorbeeld het aantal kolommen en rijen dat precies klopt met de specificatie, of iets beters. Gebruik mutatie en crossover; je kunt bijvoorbeeld crossover doen met de twee "fitste" strings uit de populatie, of met de twee "fitste" van een tiental random getrokken strings uit de populatie, of met twee willekeurige strings. Redelijke waarden zijn: mutatiekans (per bit) 0.01, populatiegrootte 100, 5000 generaties. Neem bijvoorbeeld de 5 beste steeds mee naar de volgende generatie (elitair).
  Aan genetische, of algemener evolutionaire, algoritmen wordt overigens ook een speciaal college gewijd.
In te leveren: geprint verslag plus code. Deadline: woensdag 25 april 2001.

De colleges

Tijdens de colleges wordt het volgende behandeld. Let op: enkele hier beneden te vinden sheets zijn niet aan de orde geweest.

woensdag 17 januari 2001
Algemene introductie; het practicum, met name de eerste opgave.
Hoofdstuk 1 (Introductie) in vogelvlucht. Voor een korte samenvatting: zie de sheets die Ida Sprinkhuizen-Kuyper ooit fabriceerde aan de hand van voorbeelden van Russell en Norvig:
Hoofdstuk 1 (4 op een pagina) of Hoofdstuk 1 (groot) [allemaal in gezipt PostScipt]
woensdag 24 januari 2001
Hoofdstuk 2 (Intelligente agenten) in vogelvlucht, zie de sheets:
Hoofdstuk 2 (4 op een pagina) of Hoofdstuk 2 (groot) [allemaal in gezipt PostScipt]
Hoofdstuk 3 (Probleem oplossen met zoeken) uitgebreid, tot Uniform cost search, zie de sheets:
Hoofdstuk 3 (4 op een pagina) of Hoofdstuk 3 (groot) [allemaal in gezipt PostScipt]
woensdag 31 januari 2001
Hoofdstuk 3 uitgebreid, vervolg. Sheets: zie vorig college.
Hoofdstuk 4 ("Informed" zoekmethoden) uitgebreid, tot en met het A*-algoritme, zie de sheets:
Hoofdstuk 4 (4 op een pagina) of Hoofdstuk 4 (groot) [allemaal in gezipt PostScipt]
woensdag 7 februari 2001
Hoofdstuk 4 uitgebreid, vervolg. Sheets: zie vorig college.
woensdag 14 februari 2001
Robotica, onder meer Lego-robots, zie de handleiding (288 kB, PDF; geschreven door Mark Overmars); lees ook Hoofdstuk 25 (Robotica) van Russell en Norvig. Dit alles ten behoeve van de tweede practicum-opgave.
Restanten van Hoofdstuk 4, zie vorige colleges.
woensdag 21 februari 2001
Hoofdstuk 5 (Spel(l)en) uitgebreid, zie de sheets:
Hoofdstuk 5 (4 op een pagina) of Hoofdstuk 5 (groot) [allemaal in gezipt PostScipt]
woensdag 28 februari 2001
Hoofdstukken 6 (Logisch redenerende agenten) en 7 (Eerste orde logica), zie de sheets:
Hoofdstukken 6 en 7 (4 op een pagina) of Hoofdstukken 6 en 7 (groot) [allemaal in gezipt PostScipt]
woensdag 7 maart 2001
Algemene informatie over de derde practicum-opgave; Perl.
Hoofdstuk 18 (Leren van/uit observaties) uitgebreid, met name ID3, zie de sheets:
Hoofdstuk 18 (4 op een pagina) of Hoofdstuk 18 (groot) [allemaal in gezipt PostScipt]
woensdag 14 maart 2001
Hoofdstuk 18, vervolg. Sheets: zie vorig college.
woensdag 21 maart 2001
Hoofdstuk 15 (Belief networks) uitgebreid, NIET het algoritme op p. 448/452, NIET 15.5 en 15.6, zie de sheets (die van Hoofdstuk 14 over Kansrekening staan er ter lering ook bij):
Hoofdstukken 14 en 15 (4 op een pagina) of Hoofdstukken 14 en 15 (groot) [allemaal in gezipt PostScipt]
woensdag 28 maart 2001
Hoofdstuk 15, vervolg. Sheets: zie vorig college.
woensdag 4 april 2001
Algemene informatie over de vierde practicum-opgave.
Hoofdstuk 19 (Neurale netwerken) uitgebreid, zie de sheets:
Hoofdstuk 19 (4 op een pagina) of Hoofdstuk 19 (groot) [allemaal in gezipt PostScipt]
woensdag 11 april 2001
Hoofdstuk 20 (met name Genetische algoritmen) uitgebreid, zie de sheets (die van Hoofdstuk 21 over onder meer Inductive logic progamming staan er ter vermaak ook bij):
Hoofdstukken 20 en 21 (4 op een pagina) of Hoofdstukken 20 en 21 (groot) [allemaal in gezipt PostScipt]
woensdag 25 april 2001
Data mining. Restanten. Discussie.

Genoemde hoofdstukken komen steeds uit het boek van Russell en Norvig.

Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.

13 augustus 2001 - http://www.liacs.nl/home/kosters/AI/jaar2001.html