Kunstmatige intelligentie

Het vak Kunstmatige intelligentie, ook wel AI (van Artificial Intelligence) genoemd, wordt verzorgd door dr. W.A. (Walter) Kosters, geassisteerd door drs. Edgar de Graaf, en wordt in het voorjaar van 2008 gegeven.

Eerstvolgende keer: najaar 2009. Data: dinsdagen 3 februari - 28 april 2009, 13.45-15.30 uur; werkcolleges: maandagen 23 februari, 16 maart, 6 april en 4 mei, 13.45-15.30 uur; tentamen: woensdag 24 juni 2009, vrijdag 21 augustus 2009, 14.00-17.00 uur.

Note that the course is in DUTCH.

Collegetijden: dinsdagen, van 13.45 tot 15.30 uur, in zaal 174 van het Snellius, het gebouw van Wiskunde en Informatica, Niels Bohrweg 1, Leiden. Data: 5 februari tot en met 22 april 2008. Let op: er is ook college op dinsdag 6 mei 2008, 11.15-13.00 uur, in zaal 174. Direct aansluitend aan de colleges is er uitgebreid gelegenheid vragen te stellen, met name over de programmeeropgaven, tijdens een vragenuur.
Er zijn vier werkcolleges gepland: maandag 25 februari, maandag 17 maart, maandag 7 april en dinsdag 6 mei 2008, steeds van 13.45 tot 15.30 uur, ook in zaal 174. Er wordt hier gewerkt aan kleine opgaven, aan oude tentamenopgaven en wellicht ook aan de verslagen van de programmeeropgaven. Onderwerpen voor deze werkcolleges:

maandag 25 februari 2008: Opgaven 1 (in PDF)
maandag 17 maart 2008: Opgaven 2 (in PDF)
maandag 7 april 2008: Opgaven 3 (in PDF)
dinsdag 6 mei 2008: Opgaven 4 (in PDF)

Het vak levert 6 (zes) ECTS punten op in het nieuwe systeem (vanaf 2002/2003; voorheen waren dit 4 (vier) "oude" studiepunten). Naast het voldoende maken van het tentamen is het hiervoor ook nodig het practicum voldoende te hebben. Het eindcijfer wordt voor 99% bepaald door het tentamencijfer, eventueel enigszins afgerond in de richting van het gemiddelde practicumresultaat, mits beide voldoende zijn. Ten einde het practicum voldoende te maken, moeten de vier opgaven alle met minstens een 6 of een "OK" beoordeeld zijn.
Het college is in eerste instantie bedoeld voor tweede- en hogerejaars studenten Informatica, maar is ook interessant voor andere belangstellenden; voorkennis van de programmeertaal C++ is sterk aan te raden.

Tentamendata

De tentamendata in 2008 zijn:

woensdag 25 juni 2008, 14.00 - 17.00 uur
vragenuur: maandag 23 juni 2008, 11.00 uur; zaal 174
hertentamen: vrijdag 15 augustus 2008, 14.00 - 17.00 uur

Alle cijfers (college voorjaar 2008) zijn te zijner tijd hier te vinden. Zie ook vroeger.

Materiaal

Gebruik wordt gemaakt van het boek Artificial intelligence, A modern approach van Stuart J. Russell en Peter Norvig, second edition, Prentice Hall, 2003. Het kost in de winkel circa 60 euro; soms is de versie met slappe kaft goedkoper.
In het bijzonder worden uit dit boek de volgende hoofdstukken behandeld: 1 (Introduction; lezen), 2 (Intelligent agents; lezen), 3 (Solving problems by searching; uitgebreid), 4 (Informed search and exploration; uitgebreid), 5 (Constraint satisfaction problems; uitgebreid), 6 (Adversarial search; uitgebreid), 7 (Logical agents; lezen, met name Wumpus), 8 (First order logic; lezen, met name Wumpus), 14 (Probabilistic reasoning; uitgebreid; lees ook 13, Uncertainty), 18 (Learning from observations; uitgebreid, met name beslissingsbomen), 19.1 (Knowledge in learning; lezen), 20.5 (Statistical learning methods; uitgebreid: neurale netwerken), 21.1,2,3 (Reinforcement learning, geillustreerd met 17.1,2; uitgebreid, aangevuld met 4.3 Genetische algoritmen) en 25 (Robotics; lezen, + concreet robot-programma), grotendeels in deze volgorde. Lees ook eens Hoofdstuk 26 (Philosophical foundations).
Daarnaast werd in voorgaande jaren nog speciaal aandacht besteed aan het onderwerp Data mining, maar aangezien er nu een apart derdejaars vak is met die titel ...

Overige literatuur (niet kopen — tenzij je erg veel geld hebt):

George F. Luger, Artificial intelligence, Structures and strategies for complex problem solving, Fifth edition, Addison-Wesley, 2005.
R. Callan, Artificial intelligence, Palgrave Macmillan, 2003.
Tom M. Mitchell, Machine learning, McGraw-Hill, 1997.
Michael Negnevitsky, Artificial intelligence, A guide to intelligent systems, Addison-Wesley, Second edition, 2004.
E. Alpaydin, Introduction to machine learning, The MIT Press, 2004.
Christopher M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.

Archief

tentamen 1 juni 2001 (in PostScript) met uitwerking (in PostScript)
tentamen 13 augustus 2001 (in PostScript) met uitwerking (in PostScript)
tentamen 5 juni 2002 (in PDF)
tentamen 12 augustus 2002 (in PDF)
tentamen 4 juni 2003 (in PDF)
tentamen 25 juni 2003 (in PDF)
tentamen 12 augustus 2003 (in PDF)
tentamen 4 juni 2004 (in PDF)
tentamen 3 juni 2005 (in PDF)
tentamen 20 juni 2006 (in PDF)
tentamen 21 augustus 2006 (in PDF)
tentamen 19 juni 2007 (in PDF)
tentamen 25 juni 2008 (in PDF)

Handiger: bekijk de Compilatie 2001-2007 (in PDF, 18 pagina's); enkele antwoorden (in PDF). Deze opgaven zijn ook verwerkt in de opgaven voor de werkcolleges.

Er is meer informatie te vinden over het college de afgelopen jaren.
Let op: vanaf voorjaar 2005 hoort het onderwerp Data mining niet meer bij de tentamenstof.

Het practicum

Voor iedere practicumopgave moeten worden ingeleverd: een minstens drie pagina's (laten we zeggen vijf pagina's, afgezien van de Appendix) tellend verslag in LaTeX (dit is een GROTE tekst in PDF; zie ook hier voor een zeer korte inleiding, en daar voor een langere; of een heel korte zichzelf uitleggende voorbeeldfile; of een leuke, uitgebreide, Vlaamse handleiding), en een werkend programma (digitaal (mailen aan de docent) en uitgeprint in de Appendix van het verslag; stuur geen LaTeX/PS/PDF-files en ook geen executables). Het verslag moet een duidelijke opbouw hebben, bijvoorbeeld:

Inleiding ("dit is de tweede opdracht van het college ...")
Uitleg probleem (plaatje; "de spelregels zijn ...", gebruikte definities)
Theorie ("stelling zegt dat ...")
Aanpak (plaatje; "een drielaags neuraal netwerk ...")
Implementatie ("een dubbel array"; kort)
Experimenten (tabel, grafiek)
Conclusie ("ging fout als de testopstelling niet verlicht was")
Referenties (genummerd; naar alle wordt verwezen; "handleiding Lego-robots ...", "Russell en Norvig ...")
Een fatsoenlijke referentie ziet er uit als:
[1] S.J. Russell en P. Norvig, Artificial intelligence, A modern approach, second edition, Prentice Hall, 2003
Appendix: het programma; tip: vervang tabs door spaties, kies kleiner lettertype, en zet het tussen \begin{verbatim} en \end{verbatim}; liefhebbers: gebruik package verbatim en het commando \verbatiminput{eigen.file}

Er is een klein skelet voor de verslagen: verslag.tex, dat deze PDF-versie op kan leveren. Zie ook diverse opmerkingen.

De deadlines zijn strikt, overleg eventueel met de docent(en). 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. Oude cijfers: bij de docent.
Het practicum bestaat zoals gezegd uit vier opgaven:

Bridge; deadline dinsdag 26 februari 2008
Schrijf in C++ een bridge-programma. Zie verder hier.
Robotica; deadline dinsdag 18 maart 2008
Schrijf een aantal bots voor RoboCom. Zie verder hier.
Neuraal netwerk; deadline dinsdag 8 april 2008
Schrijf in C++ een neuraal netwerk, dat een poker-hand classificeert. Meer informatie hier.
Genetisch algoritme; deadline dinsdag 6 mei 2008
Schrijf in C++ een Genetisch algoritme, dat een graaf zo mooi mogelijk tekent. Meer informatie hier.

De colleges

Tijdens de colleges wordt het volgende behandeld. Het programma is uiteraard voorlopig, zelfs als het semester voorbij is — op deze webpagina is steeds de meest actuele versie te vinden. Voor sheets van voorgaande jaren raadplege men de oude pagina's. Tijdens de colleges vinden ook discussies plaats over de genoemde hoofdstukken van Russell/Norvig. De sheets zijn voornamelijk gebaseerd op die van deze beide heren, en op sheets die vorige docenten fabriceerden.
En voor de liefhebbers: alle 337 sheets (in PDF, 2 MB; versie 2008).
Er wordt op het tentamen vanzelfsprekend nog wel eens iets gevraagd wat niet (letterlijk) op de sheets staat ...

dinsdag 5 februari 2008
Algemene introductie; het practicum, met name de eerste opgave.
Hoofdstuk 1 (Introductie) in vogelvlucht, zie de sheets:
    Introductie
leuk leesvoer:
    * Alan M. Turing, Computing machinery and intelligence
    Mind 59 (1950) 433-460
    doi:10.1093/mind/LIX.236.433; ophalen vanaf een PC binnen de universiteit
    * Jason Hutchens, How to pass the Turing test by cheating
    Technical report, 1997
dinsdag 12 februari 2008
Hoofdstuk 2 (Intelligente agenten), zie de sheets:
Intelligente agenten
dinsdag 19 februari 2008
Hoofdstuk 3 (Probleemoplossen en zoeken), zie de sheets:
Probleemoplossen en zoeken
Denk ook aan het werkcollege van maandag 25 februari 2008, Opgaven 1!
dinsdag 26 februari 2008
Robotica, in het bijzonder RoboCom. Lees ook Hoofdstuk 25 (Robotica) van Russell en Norvig.
Dit alles ten behoeve van de tweede practicum-opgave.
Zie ook de sheets:
     Robotica
Hoofdstuk 3, vervolg.
leuk leesvoer:
    * Rodney A. Brooks, Intelligence without representation
    Artificial Intelligence 47 (1991) 139-159
    doi:10.1016/0004-3702(91)90053-M; ophalen vanaf een PC binnen de universiteit
dinsdag 4 maart 2008
Hoofdstuk 4 (Gericht zoeken), zie de sheets:
Gericht zoeken
dinsdag 11 maart 2008
Hoofdstuk 4, vervolg.
Hoofdstuk 5 (Constraint Satisfaction Problemen), zie de sheets:
CSP's
Denk ook aan het werkcollege van maandag 17 maart, Opgaven 2!
dinsdag 18 maart 2008
Algemene informatie over de derde practicum-opgave; Perl.
Hoofdstuk 20.5 (Neurale netwerken), zie de sheets:
     Neurale netwerken
leuk leesvoer:
    * W.S. Noble, What is a support vector machine?
    Nature Biotechnology 24 (2006) 1565-1567
    doi:10.1038/nbt1206-1565; ophalen vanaf een PC binnen de universiteit
dinsdag 25 maart 2008
Hoofdstuk 6 (Spel(l)en), zie de sheets:
     Spel(l)en
leuk leesvoer:
    * H.J. van den Herik, J.W.H.M. Uiterwijk en J. van Rijswijck, Games solved: Now and in the future
    Artificial Intelligence 134 (2002) 277-311
    doi:10.1016/S0004-3702(01)00152-7; ophalen vanaf een PC binnen de universiteit
dinsdag 1 april 2008
Hoofdstukken 7 (Logisch redenerende agenten), 8 (Eerste orde logica) en 10.3, zie de sheets:
Logische agenten
Denk ook aan het werkcollege van maandag 7 april, Opgaven 3!
dinsdag 8 april 2008
Algemene informatie over de vierde practicum-opgave.
Hoofdstuk 4.3 (Genetische algoritmen), zie de sheets:
Genetische algoritmen
dinsdag 15 april 2008
Hoofdstuk 18 (Leren van/uit observaties), met name ID3, en Hoofdstuk 19.1, kort;
Hoofdstuk 21.1,2,3 (Reinforcement leren, geillustreerd met 17.1,2 (deels)); zie de sheets:
Leren
dinsdag 22 april 2008
Hoofdstuk 13 (Onzekerheid; kort) en Hoofdstuk 14 (Bayesiaanse netwerken), zie de sheets:
Bayesiaanse netwerken
dinsdag 6 mei 2008, 11.15-13.00 uur
Vervolg plus van alles.
Denk ook aan het werkcollege die zelfde middag, Opgaven 4!

Genoemde hoofdstukken komen steeds uit het boek van Russell en Norvig, tweede druk — met dank voor een flink gedeelte van de sheets en veel plaatjes.

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

25 juni 2008 — http://www.liacs.nl/home/kosters/AI/index.html