Monday, January 31, 2011

Wie is de beste quizspeler: computer of mens?

De computer schaakt al beter dan de mens. Nu is zelfs ’s werelds moeilijkste kennisquiz Jeopardy! niet meer veilig voor de brute kracht van de denkende machine. 

Dit artikel is gepubliceerd in NRC Handelsblad van 29 januari 2011 (onder de titel 'Watson - de quizzende computer')

                                           IBM Watson Supercomputer. Credit: IBM

In 1997 versloeg IBM’s supercomputer Deep Blue wereldkampioen schaken Garry Kasparov in een match over zes partijen met 3½ - 2½. Een mijlpaal in de intellectuele strijd tussen computer en mens. “Ik heb op mijn emoties verloren van een niet-emotionele tegenstander”, zou Kasparov zes jaar later zeggen in de documentaire Game Over. Hij kon de nederlaag maar moeilijk verkroppen.

IBM heeft zich inmiddels een nieuw doel gesteld, dat veel moeilijker is en veel meer praktische toepassingen belooft. Van 14 tot en met 16 februari 2011 strijdt de nieuwe IBM-supercomputer Watson tegen de twee beste menselijke spelers uit de historie van Amerika’s succesvolste tv-kennisquiz Jeopardy! Nederland kende deze quiz in de jaren negentig onder de naam Waagstuk! destijds uitgezonden door SBS6 en gepresenteerd door Albert Verlinde.

Jeopardy! is niet zomaar een kennisquiz met vragen van het type ‘Wat is de langste rivier?’ Jeopardy-vragen zijn vaak cryptisch geformuleerd. De quizpresentator zegt bijvoorbeeld ‘Neem in Polen een kalafior als je houdt van deze broccolivariant’ of: ‘Nadat Duitsland Nederland binnenviel, vluchtte deze koningin, haar familie en haar regering naar Londen.’ De vragen kunnen metaforen, ironie, raadsels of dubbelzinnigheden bevatten. Om zich te onderscheiden van andere kennisquizzen moeten de Jeopardy!-kandidaten hun antwoorden juist als een vraag formuleren. ‘Wat is bloemkool?’ is dan het antwoord op de eerste vraag (het Poolse woord ‘kalafior’ betekent bloemkool) en ‘Wie is Wilhelmina?’ op de tweede.

Elke vraag staat voor een bepaald geldbedrag; sommige vragen leveren de kandidaat meer op dan andere. De kandidaten moeten zo snel mogelijk op een knop drukken. Bij een goed antwoord verdient de kandidaat het geldbedrag. Bij een verkeerd antwoord gaat hetzelfde bedrag van zijn totale verdiensten af. De Amerikaanse topspeler Ken Jennings won in het seizoen 2004-2005 74 maal achter elkaar − een record − en verdiende daarmee 2,52 miljoen dollar. De best verdienende speler is Brad Rutter met een prijzenbedrag van ruim 3,2 miljoen dollar. Het is precies tegen deze twee Kasparovs van Jeopardy! dat IBM-supercomputer Watson in februari gaat spelen. 

                         Het decor van de Jeopardy-quiz

Oneindig aantal vragen 
Tot enkele jaren geleden leek het voor een computer onmogelijk om de beste menselijke Jeopardy-spelers serieus partij te bieden. De computer staat namelijk voor vier levensgrote uitdagingen. Allereerst is Jeopardy! een quiz met een open domein. De kennisvragen kunnen overal over gaan − van geschiedenis tot popmuziek, van wetenschap tot sport − en het aantal mogelijke vragen is eindeloos. De beste menselijke spelers drukken bij ongeveer de helft van de vragen op de knop, en van hun antwoorden is zo’n 85% correct. Dat moet de computer zien te evenaren.

Dit open-domeinkarakter is het grote verschil met bordspelen als dammen of schaken. Bij deze bordspelen liggen de regels precies vast en is het aantal mogelijke stellingen weliswaar akelig groot, maar toch eindig. Dan kan een computer ideaal gebruik maken van zijn rekensnelheid, precisie en onvermoeibaarheid.

De tweede grote uitdaging voor Watson ligt in het begrijpen van de vraag in gecompliceerde, natuurlijke taal. Een computer is goed in het volgen van exacte regels. Maar bij taal liggen de regels niet precies vast, hebben woorden vaak meerdere betekenissen, hangt de betekenis van de context af en is een zin vaak onnauwkeurig geformuleerd. Zo kan de zin ‘Ik heb nooit gezegd dat zij mijn geld heeft gestolen’ zeven verschillende betekenissen hebben, afhankelijk van op welk woord de nadruk ligt. En in de zin ‘Hoe lang is de Rijn?’ gaat ‘lang’ over een lengte, maar in de zin ‘Hoe lang duurt het concert van Madonna?’ slaat ‘lang’ op een tijdsduur.

De rijkdom van natuurlijke taal maakt het voor een computer veel moeilijker om Ken Jennings te verslaan met Jeopardy! dan Garry Kasparov met schaken. Specialisten zeggen unaniem dat het begrijpen van de bedoeling achter de vraag het grootste struikelblok voor Watson gaat vormen. “Hoe ambiguer de Jeopardy-vraag, hoe meer kans de mens heeft en hoe eenduidiger de vraag, hoe beter de computer het zal doen”, verwacht de Canadese informaticus Jonathan Schaeffer. Schaeffer ontwikkelde als eerste een computerprogramma dat een wereldkampioen versloeg in een serieus bordspel: checkers − een variant van dammen op een 8-bij-8-bord in plaats van een 10-bij-10.

De derde grote uitdaging voor de computer is dat hij moet inschatten hoe betrouwbaar een antwoord is. Een fout antwoord kost immers geld. Om te kunnen concurreren met Jennings en Rutter moet ten minstens 85 procent van Watsons antwoorden correct zijn. Als vierde en laatste grote uitdaging moet Watson het antwoord ook nog binnen een handvol seconden geven.

Nieuw ijkpunt 
In 2007 besloot computergigant IBM al deze uitdagingen aan te gaan en Jeopardy! als nieuw ijkpunt te nemen voor de kunstmatige intelligentie, zoals schaken dat decennialang is geweest. “Een briljante zet”, vindt Schaeffer, “want wie maalt er, behalve schaakliefhebbers, om een superieure schaakcomputer? Maar iedereen kan het praktische belang inzien van een computer die vragen kan beantwoorden.”

IBM begon met een team van een man of vijftien, onder leiding van dr. David Ferrucci, een specialist in kunstmatige intelligentie. De eerste Jeopardy!-resultaten van de supercomputer stelden teleur. Begin 2007 gaf de computer zo’n 15 procent correcte antwoorden, veel minder dan de 85 procent van de beste menselijke spelers. Werk aan de winkel dus.

Ferrucci breidde het aantal medewerkers geleidelijk uit tot meer dan vijftig in 2009. Bovendien ging het bedrijf samenwerken met wetenschappers van Carnegie Mellon University en University of Massachusetts Amherst. Aparte teams specialiseerden zich in het ontrafelen van de betekenis van de vraag, het zoeken naar het antwoord, het optimaliseren van de computerhardware en zelfs op de spraaksoftware die Watson gebruikt om het antwoord correct uit te spreken.

In april 2010 speelde Watson voor het eerst goed genoeg om te concurreren met Jeopardy-winnaars. Wel bleef hij nog steeds achter bij topspeler Ken Jennings. In het laatste kwartaal van 2010 kwalificeerde Watson zich officieel voor Jeopardy! en speelde hij vijftig testwedstrijden tegen de betere menselijke spelers. Afgelopen december achtte IBM Watson in staat om ook de twee beste menselijke spelers serieus partij te bieden. Samen met de Jeopardy!-organisatoren kondigden ze een nieuwe grensverleggende match tussen mens en computer aan.

Het geheim van Watson 
Supercomputer Watson meet ongeveer acht koelkasten van het Amerikaanse king-size-formaat en is vernoemd naar IBM’s oprichter Thomas J. Watson. Hij is niet verbonden met het internet. Alle kennis die hij nodig heeft om de quizvragen te beantwoorden, moet uit zijn eigen geheugen komen. Sinds 2007 is Watson daarom gevoed met tientallen miljoenen documenten, variërend van encyclopedieën, woordenboeken en thesauri tot romans, toneelstukken en websites. Toch ligt het geheim van Watson niet in deze enorme hoeveelheid gegevens. Het geheim ligt in de manier waarop hij in dat geheugen naar antwoorden zoekt.

Laten we als voorbeeld de volgende Jeopardy-vraag nemen: ‘In mei 1898 vierde Portugal de vierhonderdste verjaardag van de aankomst van deze ontdekkingsreiziger in India.’ Als goede antwoord zou de computer ‘Wie is Vasco da Gama?’ moeten geven. Maar hoe vindt hij het antwoord in al die tientallen miljoenen documenten die hij in zijn geheugen heeft?
Grofweg kunnen we drie stappen onderscheiden, volgens Johan Bos, hoogleraar computationale semantiek bij de afdeling informatiekunde aan de Rijksuniversiteit Groningen. “De eerste stap is een diepe taalkundige analyse van de vraag. De tweede stap is het zoeken naar een antwoord op elke mogelijke interpretatie van de vraag. De derde en laatste stap is de controlestap.” Stel dat Watson het antwoord ‘Vasco da Gama’ heeft gevonden. Hij weet ook dat het om een persoon gaat. Dan formuleert hij het antwoord ten slotte eenvoudig als een vraag die voldoet aan de Jeopardy-eisen: “Wie is Vasco da Gama?” In deze vraag zit impliciet het antwoord.

In de eerste stap op weg naar het antwoord wordt de vraag eerst grammaticaal ontleed in zelfstandige naamwoorden, werkwoorden, bezittelijk voornaamwoorden, plaatsnamen, tijdsaanduidingen enzovoort. Daarna wordt gekeken hoe deze bij elkaar horen. In de voorbeeldzin is ‘Portugal’ het onderwerp van ‘vierde’ en hoort ‘aankomst’ bij ‘deze ontdekkingsreiziger’. Een goede grammaticale analyse is essentieel, omdat de grammaticale zin waarin het antwoord verstopt kan zitten er anders kan uitzien. Zo kan bijvoorbeeld de zin ‘Op 27 mei 1498 landde Vasco da Gama op Kappad Beach’ ergens in de miljoenen opgeslagen teksten staan. Wanneer de computer uit de voorbeeldvraag niet zou halen dat ‘ontdekkingsreiziger’ bij ‘aankomst’ hoort, dan zal hij ook niet kunnen achterhalen ‘landde Vasco da Gama’ op dezelfde gebeurtenis slaat.

Na de grammaticale analyse volgt de betekenisanalyse. Elke mogelijke interpretatie van de vraag wordt in een logische formule uitgedrukt die op een abstracte manier de betekenisrol van een woord in de zin uitdrukt. Zo is in het voorbeeld ‘Portugal’ het onderwerp van ‘vierde’. Elke tekst in Watsons geheugen is in hetzelfde logische taaltje vertaald. Als ergens in een tekst staat “...werd door Portugal gevierd...” dan is de logische vertaling daarvan gelijk aan die van ‘Portugal vierde’, omdat ‘Portugal’ het onderwerp is van het predicaat ‘vieren’.

In de tweede stap gaat de computer voor elke interpretatie van de Jeopardy-aanwijzing op zoek naar mogelijke antwoorden. Dat doet hij door te zoeken naar teksten waarin dezelfde logische formule te vinden is als die van de aanwijzing. In deze tweede stap gebruikt Watson op statistiek gebaseerde zoekmachines à la Google, die niks van betekenis begrijpen maar wel razendsnel zoeken op identieke tekens. Bos: “Je hoopt dat het antwoord in de enorme hoeveelheid documenten talloze malen voorkomt. Als het in de ene tekst niet lukt het antwoord te vinden, dan wellicht in het andere wel.”

Betrouwbaarheid 
Net zoals de vraag in een logische formule wordt voorgesteld, zo zijn alle teksten in het geheugen van Watson automatisch ook al op betekenis geanalyseerd en vertaald in logische formules. Zo kan Watson al weten dat Vasco da Gama een ontdekkingsreiziger is en dat Kappad Beach in India ligt. Bos: “Bij het zoeken naar een antwoord zoekt de computer naar een match tussen de logische representatie van de vraag en die van alle teksten.”

Volgens IBM-projectleider David Ferrucci vindt Watson gemiddeld honderden mogelijke antwoorden op één enkele interpretatie van een vraag. Alle antwoorden worden gerangschikt naar betrouwbaarheid, uitgedrukt als een getal tussen 0 en 100. Hoe vaker hetzelfde antwoord opduikt, hoe hoger de betrouwbaarheid van het antwoord. Ook de betrouwbaarheid van de bron weegt mee. De Encyclopedia Britannica geldt als betrouwbaarder dan een willekeurige webtekst. IBM kan aangeven welke betrouwbaarheid een antwoord minimaal moet hebben voordat Watson op de zoemer drukt, ten teken dat hij de Jeopardy!-vraag wil beantwoorden.

Tijdens de derde en laatste stap vult de computer mogelijke antwoorden in de vraag in en gaat dan opnieuw zoeken in zijn geheugen om de betrouwbaarheid van een antwoord te vergroten. In het voorbeeld zoekt de computer of de zin ‘In mei 1898 vierde Portugal de vierhonderdste verjaardag van de aankomst van Vasco da Gama in India’ inderdaad wel genoeg betrouwbare treffers oplevert.

Volgens projectleider David Ferrucci kost het beantwoorden van een enkele vraag op een standaard desktopcomputer met een processorsnelheid van 2,6 gigahertz twee uur rekenen. Door het zoekproces efficiënt te verdelen over drieduizend van zulke processoren, brengt de supercomputer de rekentijd terug tot tussen de twee en zes seconden.

Vraag het aan Watson 
De schaakmatch tussen Kasparov en Deep Blue leverde IBM weliswaar veel publiciteit op maar nauwelijks commerciële toepassingen. Dat moet anders met worden met het Watson-project. Het bedrijf denkt binnen een paar jaar een groot aantal commerciële vraag-antwoordsystemen te ontwikkelen voor overheden, bedrijven, gezondheidsinstellingen en helpdesks. “Voor IBM staat er veel op het spel”, zegt Johan Bos. “Ze hebben er al heel veel geld in gepompt. Het is hun kracht dat ze veel mankracht kunnen inzetten op alle onderdelen, ook op de hele saaie.”

Dezelfde vraag-antwoord-methode die Watson voor Jeopardy! gebruikt, kan bijvoorbeeld ook toegepast worden om een arts te helpen bij het stellen van een medische diagnose. Laat Watson zoeken door een lijst met symptomen van een patiënt, zijn persoonlijke en familiegeschiedenis, medische handboeken en wetenschappelijke artikelen, en hij kan mogelijke diagnoses naar betrouwbaarheid rangschikken, precies zoals hij antwoorden op Jeopardy!-vragen rangschikt.

Steeds meer informatie zal de komende decennia gedigitaliseerd worden. Daarmee groeit het belang om snel een antwoord te vinden op specifieke kennisvragen. Als Watson Jeopardy! weet te winnen, of ten minste goed partij weet te bieden, dan gaat Google er een grote concurrent bij krijgen. Eentje die antwoorden geeft in plaats van je op te schepen met een lange lijst van documenten waarin je het antwoord zelf moet zoeken.

[Kader 1:]
Wij doen het anders 

Wat is het verschil tussen de manier waarop supercomputer Watson een Jeopardy!-vraag oplost en de manier waarop de mens dat doet?

Hoogleraar theoretische neuropsychologie Jaap Murre van de Universiteit van Amsterdam heeft met een interdisciplinair team van psychologen, wiskundigen en taalkundigen onderzoek gedaan naar de manier waarop mensen kennisvragen beantwoorden. Murre: “Hersenscans hebben laten zien dat processen als het horen of lezen van de zin, het begrijpen van de zin, het zoeken naar het antwoord en het formuleren van het antwoord niet na elkaar plaatsvinden, zoals men vroeger dacht, maar tegelijkertijd. Bovendien wisselen deze processen voortdurend informatie uit. Uiteindelijk komt daar een samenhangend antwoord uit. Dat antwoord is gradueel: je hebt een gevoel over hoe betrouwbaar het is. Dit gevoel bepaalt op welk moment je begint met het uitspreken van je antwoord. Al deze processen gebeuren grotendeels onbewust via grote, associatieve netwerken van hersencellen die verspreid over het brein liggen. Alleen die aspecten die duidelijk uitgekristalliseerd zijn, bereiken het bewustzijn en stellen de mens in staat een antwoord te formuleren.”

Veel details over hoe mensen een antwoord vinden, zijn echter nog onbekend. Wel is duidelijk dat het essentiële verschil tussen de mens en de computer ligt in het unieke karakter van netwerken van hersencellen om patronen te herkennen, gecombineerd met het vermogen van die netwerken om tegelijkertijd actief te zijn. Deze capaciteiten geven het brein de multifunctionaliteit die ontbreekt bij Watson. Watson is geoptimaliseerd voor het spelen van Jeopardy! Hij kan niet schaken, geen gezichten herkennen, laat staan een alledaags gesprek voeren. De computer benut zijn eigen sterke punten: razendsnel rekenen, een enorm geheugen en nooit vermoeid raken. De mens doet waar hij goed in is: leren en patroonherkenning. Eigenlijk vullen het menselijk brein en de computer elkaar aan: waarin de een goed is, is de ander slecht en omgekeerd.

[kader 2:]
Computer tegen mens - Enkele historische hoogtepunten 

1948 Alan Turing schrijft het eerste computerschaakprogramma.

1952 Een van de eerste elektronische computers, de EDSAC, wordt geprogrammeerd om boter-kaas-en-eieren te spelen.

1959 Voor het eerst wint een checkers-computerprogramma, ontworpen bij IBM, van enkele goede menselijke spelers.

1962 Schaakprogramma van MIT-onderzoekers verslaat sommige amateurs.

1988 Schaakprogramma HiTech is het eerste dat op grootmeesterniveau schaakt. Vier-op-een-rij wordt volledig opgelost.

1994 Computerprogramma Chinook verslaat de wereldkampioen checkers, Marion Tinsley. Voor het eerst heeft een computer een wereldkampioen verslagen.

1996 Wereldkampioen schaken Garry Kasparov wint zijn eerste match over zes partijen tegen IBM-schaakcomputer Deep Blue met 4 - 2.

1997 Een verbeterde versie van Deep Blue (tweemaal zo snel en met betere algoritmen) verslaat Kasparov in een revanchematch met 3½ - 2½. Deep Blue rekent gemiddeld tweehonderd miljoen zetten per seconde door en kan veertien zetten vooruit denken.

2002 John Romein en Henri Bal van de VU Amsterdam hebben het Afrikaanse bordspel Awari opgelost (ongeveer 10^12 geldige stellingen: een 1 gevolgd door 12 nullen).

2007 Checkers wordt volledig opgelost door computerprogramma Chinook. Een computerbewijs laat zien dat Chinook nooit kan verliezen. Checkers heeft ongeveer 10^20 geldige stellingen.

2007 Quackle wint als eerste computerprogramma een scrabble-toernooi.

2008 Computerprogramma MoGo, deels in Nederland ontworpen en draaiend op de Nederlandse nationale IBM-supercomputer Huygens, verslaat een internationale topspeler bij het bordspel go. De topspeler begon wel met een handicap van negen stenen. Go heeft ongeveer 10^170 geldige stellingen, tegenover 10^47 bij schaken.

2011 IBM-supercomputer Watson neemt het op tegen de twee beste menselijke spelers in Amerika’s populairste kennisquiz Jeopardy!

Internet
www.ibmwatson.com Informatie over IBM’s supercomputer Watson
www.jeopardy.com/ Over de Jeopardy!-quiz
www.nytimes.com/interactive/2010/06/16/magazine/watson-trivia-game.html Speel hier een mini-Jeopardy!-variant.

Sunday, January 30, 2011

Laat dat robotkind maar schuiven







iCub is een robotkind van een jaar of drie. Net zoals een echt kind leert hij van zijn omgeving door te zien, te horen en te voelen. iCub moet ons de weg wijzen naar een beter begrip van het menselijk brein en naar betere robots. In december bracht ik een bezoek aan iCub in Barcelona, waar de Nederlandse psycholoog Paul Verschure de leiding heeft over het roboticalab.

Lees mijn artikel over iCub in KIJK 3-2011.

Hier alvast de intro van KIJK:

Inzicht in het menselijk brein krijg je door hersenscans te maken of proefpersonen te onderzoeken. Of: door een robot te bestuderen. Een kleuterrobot van een jaar of drie, om precies te zijn. KIJK-journalist Bennie Mols maakt in Spanje kennis met de iCub.

Vandaag heeft hij even vakantie. Bewegingloos staat hij in zijn metalen beugel. In Spanje is 6 december een vrije dag en de Spaanse onderzoekers die hem normaal zijn kunstjes laten vertonen, hebben allemaal vrij. Hij heet iCub en hij is een robot.

Hij is bewust gemodelleerd naar een kind dat tussen de drie en drieënhalf jaar oud is”, vertelt de Nederlander Paul Verschure die het roboticalab runt en mij zojuist aan de ‘kleuter’ heeft voorgesteld. Net zoals een echt kind leert de iCub van zijn omgeving door te zien, te horen en te voelen. Door een wit masker kijken zijn grote, zwarte robotpupillen me aan. Zijn metalen skelet zit vol elektronica en maakt van hem het meest geavanceerde robotkind ter wereld. Vooral zijn handen zien er zeer verfijnd uit. Perfecte grijphanden met vingerkootjes omhuld door een stevige plastic huid.

Verschure laat me een filmpje zien, waarin de iCub met zijn ogen een bewegend balletje volgt, er met één hand naartoe beweegt en het balletje vastgrijpt. “De makers van de iCub zijn gespecialiseerd in de coördinatie tussen ogen en handen”, legt hij uit. “En de rest van de robot is daar eigenlijk omheen gebouwd.”

Dit is een gedeelte van een artikel uit KIJK 3/2011, in de winkel van 11 februari tot en met 10 maart. 

Internet
www.robotcub.org/
www.icub.org/
www.youtube.com/watch?v=VKPkqneze6k Een filmpje van iCub in actie, met uitleg van Verschure
www.youtube.com/results?search_query=iCub&search_type=&aq=f Meer iCub-filmpjes op YouTube
http://specs.upf.edu/people/331 Meer informatie over het onderzoek van Paul Verschure