Emotionele voetbalrobot. Creativity -some unromantic thoughts. About finding needles in haystacks

me it o s e w op a r 14 december g n i t r voo ko ia.nl stellen s be s.sV tiCket naar Congre rf snel su

Creativity -some unromantic thoughts

Emotionele voetbalrobot

About finding needles in haystacks

Harvesting the knowledge of the public

Kennisrepresentaties en machineleren

Classifying websites

Inhoud Harvesting the knowledge of the public

6

Colofon Hoofdredactie Mina Zangi Eindredactie Frido Emans, Joris de Ruiter, Jasper van Turnhout Penningmeester Jasper van Turnhout Vormgeving Ayesha van der Woensel Coverbeeld Fabien Tesselaar

16

Redactieleden VU Joris de Ruiter UvA Jasper van Turnhout UU Rosaline de Boer, Magda Kowalczuk RUG Theije Visser, Jaap Oosterbroek

4 6

News Emotionele voetbalrobot

9

Voor de totstandkoming van dit nummer danken wij: Alexander van der Mey, Frank Smit, Kees-Jan Droog, Arnoud Visser, Ben Kröse, Thomas van den Berg, Jaap Oosterbroek, Sicco van Sas, Ork de Rooij, Kaspar de Geus & Frank Nack


Content voor de volgende Connectie dient voor 1 februari gemaild te zijn naar: [email protected]

Alexander van der Mey, Frank Smit, Kees-Jan Droog & Arnoud Visser

Ben Kröse

12

Classifying Websites using Visual Features Thomas van den Berg

14 15 16

Agenda Column Harvesting the knowledge of the public

Sicco van Sas

22 27

19 22

About finding needles in haystacks

De Connectie is een landelijk AI blad voor studenten en andere geïnteresseerden. De Connectie wil AI-studenten laten zien wat AI is in de breedste zin van het woord door het publiceren van artikelen over AI-onderzoek, AI-nieuws en een agenda met activiteiten. Wilt u adverteren in De Connectie? Mail voor meer informatie en prijzen naar [email protected] Oplage 950 Dit nummer is tot stand gekomen dankzij de opleidingen AI aan de RuG, UvA, UM, UU, RU en de VU. KvK Utrecht 30211962 ISSN 1871-3807

How Mobile Assisted Language Learning

Redactieadres Stichting AI-blad De Connectie Europaplein 908 3526WT Utrecht

Creativity- Some Unromantic Thoughts

Frank Nack

27

Kijk ook eens op onze website http://www.deconnectie.com

Ork de Rooij

Kaspar de Geus

24

Vragen, opmerkingen en suggesties kunnen te allen tijde gemaild worden naar: [email protected]

Prijsvraag

5

Marketing/advertenties Mina Zangi 06 81 61 7069 [email protected] Abonnementen Jaarabonnement (4 nummers): 10,00 euro Losse nummers: 2,50 euro (prijswijzigingen voorbehouden) Voor aanvraag [email protected] http://www.deconnectie.com

Mina Zangi, Hoofdredacteur De Connectie

column redactioneel

De Connectie

beste lezer Er is veel veranderd sinds de vorige editie. We hebben nu een veel professionelere layout dankzij Ayesha van der Woensel, en ik ben de nieuwe hoofdredactrice voor de komende jaargang. Als eerstejaars student CKI aan de UU is dit een grote stap voor mij geweest, maar dankzij de steun van de redactieleden, en in het bijzonder van Joris die mij wegwijs heeft gemaakt in het hoofdredacteurschap, kan er weer een nieuw nummer bij jullie op de deurmat verschijnen. Voor dit nummer hebben we samengewerkt met het team van AWESOME IT. Dit is een symposium over de steeds grotere invloed van de ontwikkelingen in de IT op het dagelijkse leven van de mens en vice versa. Zo wordt kennis over cognitieve processen toegepast bij robots, krijgt de mensgerichte aanpak een steeds grotere invloed in software innovatie, en wordt er gewerkt aan een intelligente versie van Powerpoint die creativiteit bij mensen begrijpt en ondersteunt. Ook werkt IBM in hun Smarter Planet project aan het verbeteren en slimmer maken van infrastructuur,energie en educatie. Deze en andere onderwerpen worden behandeld door de acht sprekers op het symposium, dus kijk snel op de website bij de line-up! Het symposium zal in februari plaats gaan vinden. Dat duurt nog even, maar om jullie alvast warm te maken vind je in deze Connectie artikelen over Mens&IT. Je maakt kennis met een robot die emoties vertoont bij het kijken naar een voetbalwedstrijd, de mogelijkheid om snel de juiste video te vinden, en creativiteit in verschillende soorten. Mocht dit je interesseren, neem dan een kijkje op de website van het symposium. Wij van de Connectie zullen ook aanwezig zijn met onze eigen stand. Bestel je je tickets vóór 14 december dan profiteer je van de vroege vogel korting van 1,00 euro! VIA- leden ontvangen 2,50 euro korting. De standaard ticketprijs is 7,50 euro. Voor de puzzelaars onder jullie: achterin staat een sudokupuzzel. Ik moet je er wel voor waarschuwen dat het om een breinbreker gaat. Is het je gelukt om de puzzel op te lossen? Stuur dan een mailtje naar ons, en wie weet wordt jij de winnaar van het meest epische AI-boek aller tijden!

Veel leesplezier! Mina Zangi

nummer 2, december 2010

3

news Designing An EthicAl Robot ScienceInTheSanctuary (Nov. 09, 2010) — In the article “Robot Be Good“, found in the Oct. 2010 issue of Scientific American, the question is brought up about what it would mean to create a robot that behaved “ethically.” Currently, Nao (the robot pictured on the cover), is one attempt at such a feat. Nao was designed to give medication to patients at nursing homes in such a way that would preserve the patients ability to say “no” to the medication while still notifying a doctor if the patient goes too long without their needed meds. This may not seem like a revolutionary step but the authors of the article, Drs. Michael and Susan Anderson, hint that it is the first step toward developing Artificial Intelligence that learns how to behave in various ethical situations. By constructing a set of priorities for the robot, such as “Do Good,” “Prevent Harm,” and “Be Fair,” a robot would be able to take various information and come to a decision based on maximizing those factors. The authors go on to say that robotic ethics is particularly interesting since robots do

Babies Treat Social Robots as Sentient Beings

Andrew Meltzoff, co-director of the University of Washington’s Institute for Learning and Brain Sciences, and Rajesh Rao, University of Washington associate professor of computer science and engineering, with the humanoid robot used to demonstrate “social” interactions to babies.

4 nummer 2, december 2010

not have to deal with emotions, something that we humans have in spades and that often make us “less than ideal ethical decision makers.” In the end, the authors come to this conclusion: …Properly trained machines might even behave more ethically than many human beings would, because they would be capable of making impartial decisions, something humans are not always very good at. Perharps interacting with an ethical robot might someday even inspire us to behave more ethically ourselves.

ScienceDaily (Oct. 14, 2010) — At 18 months old, babies are intensely curious about what makes humans tick. A team of University of Washington researchers is studying how infants tell which are “psychological agents” that can think and feel. Research provides a clue as to how babies decide whether a new object, such as a robot, is sentient or an inanimate object. Four times as many babies who watched a robot interact socially with people were willing to learn from the robot than babies who did not see the interactions. “Babies learn best through social interactions, but what makes something ‘social’ for a baby?” said Andrew Meltzoff, lead author of the paper and co-director of the UW’s Institute for Learning and Brain Sciences. “It is not just what something looks like, but how it moves and interacts with others that gives it special meaning to the baby.”

Why Should you Care?: If scientists are going to be developing an ethical robot, it may be worth considering what set of ethics they are using. In the article, one of the hypothetical robot’s directives is to “Be Fair.” While fairness is definitely something we want to see in society, there is arguably a difference between “fairness” and “justice.” Fairness, for instance, doesn’t always necessitate showing mercy or compassion. It may be fair that a person caught stealing to feed their family go to prison, but it might not be just. Since robots will undoubtedly play an increasingly important role in our society, its important for Christians and other people of faith to insist on including a set of ethics into Artificial Intelligence that encompasses justice for the poor and marginalized, compassion for the least, and the inherent value of all humanity. http://scienceinthesanctuary.org/?p=63

The UW researchers hypothesized that babies would be more likely to view the robot as a psychological being if they saw other friendly human beings socially interacting with it. “Babies look to us for guidance in how to interpret things, and if we treat something as a psychological agent, they will, too,” Meltzoff said. “Even more remarkably, they will learn from it, because social interaction unlocks the key to early learning.” The study has implications for humanoid robots, said co-author Rajesh Rao, UW associate professor of computer science and engineering and head of UW’s neural systems laboratory. Rao’s team helped design the computer programs that made Morphy appear social. “The study suggests that if you want to build a companion robot, it is not sufficient to make it look human,” said Rao. “The robot must also be able to interact socially with humans, an interesting challenge for robotics.”

news

De Connectie

Tiny Brained Bees Solve a Complex Mathematical Problem ScienceDaily (Oct. 25, 2010) — Bumblebees can find the solution to a complex mathematical problem which keeps computers busy for days. Scientists at Royal Holloway, University of London and Queen Mary, University of London have discovered that bees learn to fly the shortest possible route between flowers even if they discover the flowers in a different order. Bees are effectively solving the ‘Traveling Salesman Problem’, and these are the first animals found to do this. The Traveling Salesman must find the shortest route that allows him to visit all

locations on his route. Computers solve it by comparing the length of all possible routes and choosing the shortest. However, bees solve it without computer assistance using a brain the size of grass seed. Dr Nigel Raine, from the School of Biological Sciences at Royal Holloway explains: “Foraging bees solve traveling salesman problems every day. They visit flowers at multiple locations and, because bees use lots of energy to fly, they find a route which keeps flying to a minimum.” The team used computer controlled artificial flowers to test whether bees would follow a route defined by the order in which they discovered the flowers or if

they would find the shortest route. After exploring the location of the flowers, bees quickly learned to fly the shortest route. Dr Raine adds: “Despite their tiny brains bees are capable of extraordinary feats of behavior. We need to understand how they can solve the Traveling Salesman Problem without a computer. What shortcuts do they use?’’ New research shows that bumblebees can find the solution to a complex mathematical problem which keeps computers busy for days. http://www.sciencedaily.com/releases/2010/ 10/101025090020.htm

Doctors Conduct First-Ever All-Robotic Surgery and Anesthesia ScienceDaily (Oct. 20, 2010) — In a world first, a completely robotic surgery and anesthesia has been performed at the McGill University Health Centre (MUHC). The DaVinci surgical robot, which lets surgeons work from remote locations, was put to work this summer, whereas the anesthesia robot, nicknamed McSleepy, has been providing automated anesthesia since 2008. The two combined to perform the first all-robotic surgery on a prostatectomy patient at the Montreal General Hospital. “Collaboration between DaVinci, a surgical robot, and anesthetic robot McSleepy seemed an obvious fit; robots in medicine can provide health care of higher safety and precision, thus ultimately improving outcomes,” said Dr. TM Hemmerling of McGill University and MUHC’s Department of Anesthesia. “The DaVinci allows us to work from a workstation operating surgical instruments with delicate movements of our fingers with a precision that cannot be provided by humans alone,” said Dr. A. Aprikian, MUHC urologist in chief and Director of the MUHC Cancer Care Mission. He and his team of surgeons operate the robotic arms from a dedicated workstation via video control with unsurpassed 3D HD image quality.

“Providing anesthesia for robotic prostatectomy can be challenging because of the specific patient positioning and the high degree of muscle relaxation necessary to maintain perfect conditions for the surgical team,” added Dr. Hemmerling. “Automated anesthesia delivery via McSleepy guarantees the same high quality of care every time it is used, independent from the subjective level of expertise. It can be configured exactly to the specific needs of different surgeries, such as robotic surgery.” “Obviously, there is still some work needed to perfect the all robotic approach – from technical aspects to space requirements for the robots,” added Dr. Hemmerling. “Whereas robots have been used in surgery for quite some time, anesthe-

sia has finally caught up. Robots will not replace doctors but help them to perform to the highest standards.” Combining both robots, the specialists at the MUHC can deliver the most modern and accurate patient care. The researchers will use the results of this project to test all robotic surgery and anesthesia in a larger scale of patients and various types of surgery. ”This should allow for faster, safer and more precise surgery for our patients” concluded Dr. Aprikian. nummer 2, december 2010

5

Alexander van der Mey, Frank Smit, Kees-Jan Droog & Arnoud Visser

Emotionele voetbAlrobot De emoties die mensen ervaren tijdens het bekijken van een voetbalwedstrijd zijn vaak groot en meeslepend. Een robot heeft van nature geen emoties; zijn emotioneel systeem moet expliciet worden ontworpen. Het bekijken van een voetbalwedstrijd is voor zo’n emotioneel systeem een ideaal testscenario; de context is duidelijk en men verwacht grootse expressies. Voor dit onderzoek is de humanoid robot Nao uitgebreid met een dergelijk emotioneel systeem. Het emotionele systeem wordt gevoed door gebeurtenissen in de voetbalwedstrijd.

D Alexander van der Mey heeft de koppeling van stimuli naar emotione le lichaamshoudingen gecreëerd. Student KI, UvA, A.J.vanderMeij@ student.uva.nl

Frank Smit heeft de in terpretatie van de infor matie op het internet tot stimuli voor het emotio nele systeem gecreëerd. Student KI, UvA, Frank. [email protected]

e correspondentie tussen gebeurtenissen in de wereld en veranderingen in emotionele toestand van de robot zijn gemodelleerd aan de hand van een standaard psychologisch model, en gevalideerd door middel van een kleine enquête. Veranderingen in de emotionele toestand van de robot zijn gekoppeld aan de lichaamstaal van de robot. Als eindresultaat hebben we een robot met een dynamisch emotioneel systeem gemaakt, die zich duidelijk laat meeslepen door de gebeurtenissen tijdens een voetbalwedstrijd. De meeste Nederlanders zullen zich nog het afgelopen WK-voetbal herinneren. Met z’n allen hebben we die zenuwslopende laatste 10 minuten tegen Brazilië beleefd, de blijdschap toen Gio hem keihard in de Uruguayaanse kruising schoot, en de teleurstelling en woede toen Iniesta ons WK-avontuur beëindigde. We kunnen terugkijken op veel mooie en emotionele momenten, die misschien juist zo mooi zijn vanwege het feit dat we ze samen gedeeld hebben. De emoties die mensen ervaren zijn dan ook vanuit onze natuur ingebakken. Een robot is echter vanuit zichzelf niet in staat om deze emoties te ervaren of uit te beelden. Wetenschappers hebben al op vele manieren geprobeerd om robots met een emotioneel systeemte maken, omdat dit de samenwerking met mensen vergemakkelijkt. Er is echter nog geen robot die tijdens een voetbalwedstrijd emoties kan laten zien, terwijl dit een geschikt testscenario is. In het kader van deze studie hebben we een emotionele voetbalrobot ontwikkeld, die dit probleem op moet lossen. De Nao is een humanoid robot ontwikkeld door het Franse bedrijf Aldebaran Robotics. De robot is


zowel populair in het onderwijs als in het onderzoek en prijkt bijvoorbeeld op de voorkant van dit nummer van de Connectie. De robot is uitgerust met een scala aan sensoren en actuatoren die aan te spreken zijn door middel van verschillende interfaces (C++, Python & Urbi). In deze studie is er gebruik gemaakt van de Python interface. Tijdens een voetbalwedstrijd spelen zich allerlei gebeurtenissen af op het veld. De meest prominente gebeurtenissen vinden plaats rond de goals van de twee teams, zoals een schot op doel en een doelpunt. Zes van deze prominente gebeurtenissen zijn gekoppeld aan een bepaalde emotionele lading, waarbij het sterk uitmaakt voor welk team de robot is. Elke gebeurtenis veroorzaakt een verandering van de emotionele toestand in een bepaalde richting.

“Mensen kunnen emoties met hoge waarschijnlijkheid uit lichaamstaal halen” Een ‘gemiste kans van het eigen team’ is bijvoorbeeld geassocieerd met verandering richting ‘ergeren’ en een ‘doelpunt van het andere team’ met de ‘boosheid’-richting. De sterkte van een emotieverandering bleek moeilijk in te schatten, gedeeltelijk omdat het voor sommige gebeurtenissen afhankelijk is van het eerdere verloop van de wedstrijd. Om de sterkte van de veranderingen in te kunnen schatten is er een enquête ontworpen, waarin 22 deelnemers een hypothetische wedstrijd van Nederland werd voorgehouden. In de enquête passeerden verschillende scenario’s de revue, waarbij van de deel-

emotionele voetbalrobot

De Connectie

nemer werd verlangd zijn of haar emotionele reactie op denkbeeldige spelsituaties aan te geven. Sommige vragen gingen over de richting van de emotionele reactie, andere over de sterkte van de verandering. Uit de resultaten bleek bijvoorbeeld dat het verschil in doelpuntenratio tussen beiden teams van invloed is op de sterkte van de vreugde die een doelpunt van het favoriete team teweeg brengt. Met behulp van het psychologische model van Mehrabian[3] zijn deze emotionele veranderingen uitgedrukt als vectoren in een 3D-ruimte met de factoren: arousal, valence en stance. Deze keuze is geïnspireerd door het werk van Breazeal & Brooks[1]. Combinaties van deze drie factoren maakt het mogelijk een wijd scala aan emoties te vertegenwoordigen (zie figuur 2). Arousal geeft de mate van opwinding aan.; Valence heeft te doen met of een gebeurtenis positief of negatief is, terwijl Stance de houding ten opzichte van de omgeving vertegenwoordigt. Een emotie als angst kan bijvoorbeeld geplaatst worden als resultaat van hoge arousal, slechte valence en een teruggetrokken stance. De Kismet-robot, ontwikkelt door Breazeal & Brooks, is speciaal ontworpen voor het tonen van emotie door middel van gezichtsuitdrukkingen. Het gezicht van de Nao heeft minder vrijheidsgraden en kan daardoor slechts beperkt gebruikt worden voor het uitdrukken van emoties. In plaats daarvan is er gebruik gemaakt van de lichaamstaal van de Nao. Mensen kunnen emoties met hoge waarschijnlijkheid uit lichaamstaal halen, vooral emoties als boosheid, blijheid en verdriet. Gebruik is gemaakt van emotionele lichaamstaal ontwikkeld door Aldebaran Robotics. De taal bestaat uit in totaal vijftig lichaamsuitdrukkingen, waarvan veel emoties in meerdere gradaties, zoals blij, heel blij en ontzettend blij. Wanneer een nieuwe gebeurtenis zich voordoet in de wedstrijd wordt er een nieuwe emotievector gecreëerd op basis van het type gebeurtenis en het eerdere spelverloop. Elke vector is ook voorzien van een levensduur, die naarmate de wedstrijd vordert geleidelijk aan intensiteit verliest en uiteindelijk verwaarloosbaar wordt. Door alle op dat moment actieve, en misschien tegenstrijdige, vectoren samen te voegen in één resulte-

rende vector, ontstaat er een emotionele toestand (stemming) gebaseerd op de gebeurtenissen die op dat moment “het gemoed”van de Nao beïnvloeden. Los van het type gebeurtenis wordt de robot ook beïnvloed door het aantal gebeurtenissen. Uit de enquête bleek dat de arousal en stance vooral beïnvloed worden door het spelverloop. De arousal-waarde daalt op het moment dat het spel saai is (geen gebeurtenissen), terwijl er een stijging optreedt wanneer er voldoende gebeurtenissen binnenkomen. De stance-waarde zal negatief uitslaan wanneer het slecht gaat met het favoriete team, waardoor de Nao een meer stoïcijnse houding zal aannemen. De valance-waarde stijgt/daalt ook als het goed/slecht gaat met het favoriete team. De reactie is heftiger, maar ook korter dan van de stance-factor. Het verloop van de drie emotionele factoren tijdens een voetbalwedstrijd is te zien in figuur 4. Het verloop van deze emotionele toestand is daarna gekoppeld aan de lichaamstaal van de Nao. Hierbij is gebruik gemaakt van een subset van de beschikbare lichaamshoudingen om de emotionele toestand tijdens de wedstrijd te tonen. Een voorbeeld van twee uitingen met een groot verschil in arousal en valence is te zien in figuur 5. De non-verbale uitingen van emotie worden hierbij ook ondersteund met een verbale component, om de boodschap nog duidelijker te maken. Voor de verbale component is er gebruik

Kees-Jan Droog heeft onderzoek gedaan naar het volgen van de bal op het veld. Student KI, UvA, Kees-Jan.Droog@ student.uva.nl

Arnoud Visser heeft de wetenschappelijke ondersteuning van dit ond erzoek verzorgd. Docent KI, UvA, [email protected]

Figuur 2. De 3D ruimte met de emoties van de robot Kismet


7

Figuur 4. Emotionele dynamiek tijdens de wedstrijd Nederland – Ghana

gemaakt van een kleine database met relevante uitspraken, die de Nao door middel van zijn Text-toSpeech module kan uitspreken.

vorm van deze verslagen maakt het mogelijk naar bepaalde woorden en patronen te zoeken en de Nao te laten begrijpen wat er in de wedstrijd gebeurt.

Het emotionele systeem heeft natuurlijk stimuli nodig. Idealiter zou een robot naar een voetbalwedstrijd kijken en begrijpen wat er gebeurt. Het aantal gebeurtenissen in deze studie is beperkt, dus begrip betekent in dit geval dat de robot getraind moeten worden om de gekozen gebeurtenissen (doelpunt, schot naast, schot gehouden) te onderscheiden. Een deelproject van het totale onderzoek was om hier een eerste aanzet aan te geven. Als eerste stap is hiervoor het volgen van de bal genomen, omdat die in alle drie de gebeurtenissen een rol speelt. Het resultaat van dit deelonderzoek was dat de robot een felgekleurde bal op een echt veld kon volgen. Het volgen van een officiële FIFA-bal op het televisiescherm was nog te ambitieus.

De conclusie is dat de voetbalwereld er een supporter bij heeft gekregen. De emotionele toestand van de Nao verandert duidelijk naar aanleiding van de gebeurtenissen die plaatsvinden, en de robot is ook in staat om deze emotionele toestand uit te beelden met de corresponderende lichaamshoudingen. Het emotionele systeem van deze artificiële supporter wordt gedemonstreerd op het Human Factors Event. De levenswetenschappers op deze conferentie kunnen dan beoordelen hoe realistisch men de dynamiek van de emotionele toestand van deze robot vindt. ø

Om deze gebeurtenissen toch te kunnen genereren, is als alternatief een ander deelproject opgestart. Dit haalt de informatie van internet met een simpele vorm van ‘information retrieval’. Tijdens een voetbalwedstrijd zijn er verschillende fora te vinden waar live verslag van de wedstrijd wordt gedaan. Voor dit project is gebruik gemaakt van een ‘live commentary’ van het Entertainment and Sports Programming Network (ESPN). Het commentaar wordt op deze website in telegramstijl gegeven. Normaliter is de interpretatie van vrij geschreven tekst complex, maar de vaste

Figuur 5. De Nao tijdens een spannend en saai moment in de wedstrijd


Bibliografie: [1] C. Breazeal and R. Brooks, Who Needs Emotions?: The Brain Meets the Robot, chapter 10. Robot emotions; a functional perspective, pp. 271–310, Oxford University Press, 2005. [2] M. Coulson, “Attributing emotion to static body postu res; recognition accuracy, confusions and viewpoint de pendence”, Journal of Nonverbal Behavior, volume 28(2), 2004. [3] A. Mehrabian and J. Russell, An approach to environ mental psychology, MIT Press, 1974. [4] A. van der Mey, F. Smit, K.-J. Droog and A. Visser, “Emo tion Expression of an Affective State Space; a humanoid robot displaying a dynamic emotional state during a soc cer game”, in “Proceedings of the 3rd D-CIS Human Fac tors Event”, D-CIS Lab, Delft, November 2010. [5] J. Monceaux, J. Becker, C. Boudier and A. Mazel, “De monstration: First Steps in Emotional Expression of the Humanoid Robot Nao”, in “ICMI-MLMI ’09: Proc. of the 2009 International Conference on Multimodal Interfaces”, pp. 235–236, ACM, 2009. [6 E. soccernet, “ESPN livefeed van de WK-wedstrijd Neder land – Ghana”, http://es.pn/eMDulp

Ben Kröse, Universiteit van Amsterdam en Hogeschool van Amsterdam, [email protected]


voor robots in een menselijke omgeving Zestig jaar geleden introduceerde Alan Turing zijn voorstel voor een benchmark voor intelligente machines. Alhoewel er sindsdien enorme vooruitgang is geboekt op methoden voor natuurlijke taalverwerking, kennisrepresentatie en machineleren, is er nog geen computer voor de test geslaagd. Het nabootsen van menselijke intelligentie vereist blijkbaar een andere aanpak.

N

De auteur is universitair hoofd docent aan de UvA, waar hij al twintig jaar onderzoek verricht op het gebied van kunstmatige intelligentie en robotica. Sinds vijf jaar heeft hij ook een aan stelling als lector aan de HvA, waar hij een onderzoeksgroep leidt op het gebied van ‘Digi tal Life’. Hier wordt samen met bedrijven praktijkgericht onder zoek uitgevoerd op het gebied van informatietechnologie in de woonomgeving.

u intelligente machines steeds meer werkzaam zijn in een door mensen bewoonde wereld wordt intelligente interactie steeds belangrijker. Voor een succesvol samenleven moeten mens en machine op een natuurlijke manier communiceren over doelen, concepten en intenties. In het verleden werden voornamelijk optimale planningsmethoden ontwikkeld voor assemblage van producten. Robots opereerden in industriële omgevingen, waarbij interactie met mensen zoveel mogelijk werd vermeden. Omgevingen waren gestructureerd en voorzien van markers. Er is echter een ontwikkeling gaande waarbij de intelligente robots de fabriek verlaat en operereert in onze woonomgeving, bijvoorbeeld als intelligent vervoermiddel, of als autonome stofzuiger. Ook in deze omgevingen moet de robot kunnen functioneren, en dat is een stuk uitdagender. COGNIRON: The Cognitive Robot Companion Deze thematiek stond centraal in het project ‘Cogniron’, waarin een tiental vooraanstaande Europese onderzoeksgroepen op het gebied van robotica – waaronder de UvA – van 2004 tot 2008 samenwerkten. Het thema van het project was: ‘Developing robots interacting with humans, able to perceive, decide, communicate and learn in an open-ended way’.

Om het project te structureren werden er een aantal werkpakketten gedefinieerd. Behalve de standaard werkpakketten als management en integratie werden er werkpakketten gevormd die zich richten op typische onderzoeksthema’s uit de kunstmatige intelligentie, zoals multimodale dialoogvoering, herkenning en detectie van menselijke activiteiten, leren, planning en beslissen. Andere werkpakketten waren gericht op nieuwe thema’s zoals sociaal gedrag en context bepaling. Omgevingsmodellen Een bruikbare robot heeft een interne representatie van de omgeving nodig. Enerzijds om te kunnen navigeren en objecten te kunnen manipuleren, anderzijds om te kunnen communiceren met menselijke gebruikers. Traditioneel hebben robots geometrische representaties van de wereld: door middel van geometrische primitieven (bijvoorbeeld lijnen, of een raster met bezettingsindex) wordt een model van de omgeving gemaakt waarin doelen, obstakels en vrij toegankelijke ruimte kan worden aangegeven. Methoden uit de kunstmatige intelligentie worden vervolgens gebruikt om een pad te plannen. Voor robots die in een menselijke omgeving komt hier nog wat bij: We willen de robot de opdracht geven ‘ga naar de keuken’ en niet: ‘ga naar positie 239, 3974’. Aan de UvA hebben we een methonummer 2, december 2010

9

Figuur 3. G

den ld wor e b a raafclustering vor mt ca l e g n e s n tegorieën die door me

de ontwikkeld voor een omgevingsrepresentatie die op twee manieren afwijkt van de gangbare representatie. Op de eerste plaats maken we niet een geometrisch model van de omgeving maar een sensorische representatie. Op de tweede plaats leren we een relatie tussen de sensorische representatie en de concepten nodig voor mens-robot interactie. In het sensorische domein bestaat de ‘kaart’ niet uit geometrische elementen maar uit sensorische gegevens, in ons geval beelden van een (omnidirectionele) camera die verkregen zijn door de robot willekeurig rond te laten rijden. Uit de beeldinformatie kunnen we afleiden of twee beelden in de dataset

Figuur 2. Appearance representatie voor omgevingsmodellen


een relatie hebben. We definiëren hiertoe een afstandsmaat gebaseerd op lokale kenmerken en geometrische beperkingen. Twee beelden krijgen een een relatie als we voldoende bewijs hebben dat de beelden dezelfde omgeving voorstellen maar vanuit een ander camerastandpunt zijn genomen (zie Booij et al 2010). Op deze manier ontstaat er een graaf (figuur 2) waarin de knopen de opgeslagen beelden zijn en de zijden aangeven of de beelden op elkaar lijken. We hebben experimenten uitgevoerd waarbij deze graaf gebruikt is om op basis van visuele informatie van de huidige positie (beeld) naar een gewenste positie (beeld) te navigeren. De graafrepresentatie kan echter ook goed worden gebruikt om een conceptuele representatie van de omgeving te maken. Deze representatie kan gebruikt worden voor communicatie met de gebruiker. Het uitgangspunt hierbij is dat beelden die overeenkomstige spatiële concepten beschrijven (keuken, woonkamer, etc.), ook in de graaf dicht bij elkaar liggen.

kennisrepresentaties en machineleren

De Connectie

Met dit als uitgangpunt hebben we een graaf-clusteringsmethode gebruikt om categorieën (groepen) in de graaf te vinden. Figuur 3 geeft een voorbeeld van een graaf die is gemaakt terwijl de robot in het Informatica Instituut van de UvA rondreed, waarbij diverse kamers bezocht werden. In een interactiefase met menselijke gebruikers zijn er een beperkt aantal beelden gelabeld. De labels van deze beelden werden vervolgens toegekend aan alle beelden in de groep. Omdat er gedurende de interactie nieuwe labels werden toegevoegd en omdat er continu nieuwe beelden werden gemaakt, werden de graaf en de clusters continu aangepast. Een pruningsmechanisme werdt gebruikt om de grootte van de beeldenset beperkt te houden. Sociaal intelligente robots Behalve dat de interne representaties afgestemd moeten zijn op de interactie met mensen moeten ook de controle- en planningsmethoden zijn afgestemd op de menselijke wereld. Een onderwerp

dat we in Cogniron hebben uitgewerkt is proxemics: de studie naar afstanden die mensen innemen als ze onderling communiceren, en de invloed die dit heeft op de robotpadplanning. In de groep van Kerstin Dautenhahn aan de Universiteit van Hertfordshire is onderzoek gedaan naar afstanden die mensen innemen ten opzichte van robots. Door middel van een indicatorsysteem is bestudeerd bij welke afstanden en relatieve oriëntatie (richting van kijken) mensen zich nog prettig voelen. Ook werd er gekeken naar de invloed van muren en obstakels. Zo werd geconstateerd dat men het niet prettig vond als een robot ineens van achter een obstakel verscheen. Met dergelijke kennis kan nu een kostenfunctie worden opgesteld voor een omgeving die bestaat uit een configuratie van mensen en obstakels. Als de robot een bepaalde taak heeft, bijvoorbeeld een object uit de kast pakken en aan een van de aanwezigen overhandigen, zal een planningsmethode gebruikt worden om bij het object te komen. Onze proxemics kostenfunctie kan hierbij zorgen dat de robot geen mensen in de weg loopt. Een voorbeeld van deze slimme planning is gegeven in figuur 4, waarbij de robot zich moet positioneren vóór de twee personen. Als een standaard kostenfunctie – gebaseerd op de kortste afgelegde afstand – zou zijn gebruikt, dan zou de robot tussen de twee personen door zijn gereden. Het nu geplande traject voldoet aan de ‘sociale’ regels die gelden voor afstanden tussen mensen. Alomtegenwoordige robots Voorlopig zijn robots zijn nog niet wijdverbreid zichtbaar in onze woningen. Wat wel een grote vlucht neemt zijn verbor-

Figuur 4. Een optimaal gepland pad om de robot vóór de twee personen te plaatsen waarbij een kostenmodel is gebruikt dat rekening houdt met de sociaal gewenste afstand tussen mensen.

gen intelligente systemen in onze woonomgeving die bestaan uit een netwerk van intelligente apparaten voor communicatie, entertainment en comfort. Deze ‘Ambient Intelligence’ of ‘domotica’-sytemen zullen behalve ‘kunstmatige’ intelligentie ook een grote mate van ‘sociale’ intelligentie moeten bezitten. Hier zijn veel toepassingsmogelijkheden voor de onderzoeksresultaten uit de mens-robotinteractie. Zo is er in de gezondheidszorg een grote vraag naar systemen die met sensoren de activiteiten van ouderen monitoren en de juiste feedback geven, en hebben de intelligente winkelcentra van morgen informatiedisplays die de inhoud afstemmen op de mensen die voor het display staan. Een nieuwe vorm van robotica; de ‘ambient’ robotica heeft een grote toekomst. ø

meer informatie: [1] www.cogniron.org [2] Booij, O., Zivkovic, Z. & Kröse, B.J.A (2010). Efficient probabilistic planar robot motion estimation given pairs of images. Robotics: Science and Systems VI, Zaragoza, Spain, June 2010


11

Thomas van den Berg, [email protected]

Classifying Websites using Visual F In a time when the amount of information available to us is expanding fast due to the accessibility and size of the internet, there is an increasing demand for the ability to automatically filter all this data, presenting to us only information that is relevant and of high quality. Specifically in the domain of websites and online searching, there is room for improvement by rating pages not only based on their content, but also on their visual presentation.

W

ell-designed pages make it easier for people to find useful information, while very poorly designed pages usually do not contain a lot of information at all. Aside from quality of design, there are other dimensions we can extract from the visual presentation of a page, such as informativeness or topic. Graphic designers use a different Look and Feel for advertisements than for informative pages, and humans can pick up on this quite easily. In this research, the goal was to find features that would enable a machine learning algorithm to find these differences and classify pages based on their visuals. Feature Extraction Extracting features is essentially a pre-processing step for any machine learning algorithm. By quantifying aspects of the webpage such as the number of photos and the general colorfulness, we make it easier for the machine learning to find the `right' values of these parameters. It allows us to incorporate our prior knowledge of the domain into the system. These feature extracted should describe some higher level phenomenon in the data, while being relatively easy to compute. If the features are too complex, computing them might be a separate machine learning problem, which is not what we want. Features are chosen if they are suspected to have some correlation to the attempted classification. “Suspected” is enough, because the machine learning algorithm will discern the features that are informative. The features used in this research are at the level of color and composition. These features are more informative than separate image pixels, and can still be computed in a relatively straightforward way using statistical measures. Obviously, we suspect that these kinds of features are related to visual qualities (e.g. aesthetics). Four feature extractors were developed for this research: (1) The number and size of photos, (2) The size and position of columns, (3) The color palette that was used, and (4) An analysis of this color palette.


Finding Photos An important factor when people make up their minds about a web page is whether it has photos. A few photos can make a page more salient, while a lot of photos make it look cheap or confusing. Web pages are usually designed using mostly flat colors or subtle textures, so photos are much “noisier” than most parts of a webpage. Even though text also adds noise to the page, text does not form connected areas. Therefore images and photos will stand out as large, connected noisy areas. A problem is that not each photo is noisy everywhere (e.g. a blue sky might cause smooth parts in a photo). When checking pixels, it is difficult for an algorithms to find the images on a page. As a solution, it is possible to exploit the fact that images on web pages are usually rectangular and aligned to the page. If we assume that each noisy area is contained in a rectangular image region, we'll discover that some of these rectangular areas overlap, making them part of the same image. By repeatedly merging image areas whose bounding-boxes overlap, we end up with a very precise estimation of which pixels belong to images or photographs on the page. This algorithm is illustrated in Figure 1. The photo finding algorithm was evaluated in a small experiment, in which 93 out of 101 photos were detected, and 18 pieces of text were wrongly classified as photos. This map of which pixels belong to photos can then be used to generate multiple features such as the total photo area, number of photos, and average area per photo. Extracting Palettes When designing a website or other publication, a designer is aiming for a certain Look and Feel, trying to appeal to a specific audience or trying to evoke a specific response from a viewer. Color is the most important tool for this, so the intended purpose of a website can manifest in its use of color. Besides just extracting the colors used in the image, it is useful to analyze the combination of colors or palette. Whether a palette is bold, subdued, loud, etc. is determined by the relation between the colors, not the values of single colors.

classifying websites using visual features

De Connectie

al Features Thomas van den Berg: I am a Master student in Artificial Intelligence at the University of Amsterdam. I am also freelance web designer. At the moment my studies focus on computer vision and gaming. In my little spare time I work on different web apps and indie computer games. site: www.noio.nl

A color palette usually consists of three main colors. The most used color is the base color, this is usually a neutral tint, used as the background color on most web pages. The most notable color, though, is the dominant color; this is often the color of graphical elements such as menus and page headers. Then there is a highlight color, this color can either be a stronger tint of the dominant color or a contrasting color, and is used as an accent. The highlight color is used for elements that require the user's attention, such as navigation buttons and section headers. In web design, a fourth color is employed for practical reasons: the color of the text is picked so that it has a high contrast with the background. The text color usually has a low saturation, regardless of the other colors in the palette. The algorithm used to extract a color palette is a clustering algorithm that groups similar colors. In order for this to work, the pixels of a page are represented as vectors in a color space. The R,G,B color space is not very suitable, because it doesn't correspond very well to the way humans perceive color. A better way to represent colors is in the L*,a*,b* space. This

Figure 1: A local entropy map is created (a), small areas are removed (b). Then the bounding-box of each area is filled in until the image no longer changes as shown in (c) and (d).

color space has three dimensions: L* is the perceived lightness of a color, a* indicates whether the color is green or red, and b* indicates whether it is blue or yellow. In order to classify images based on the color palettes, we have to extract features. In this research we used features such as average saturation, average lightness, contrast, the number of different hues, etc. THe MÜller ForMUlA One of the color palette features is based on a bit of color theory by A. Müller. This theory states that humans prefer colors to be in a natural order of brightness. Colors have a natural perceptual brightness that is actually reflected in the L*a*b* color space by the L* component. Blues and purples have a lower perceptual brightness, yellows and reds have a higher brightness, even if they have the same intensity in the RGB color space (intensity defined as R+G+B). Humans prefer combinations of colors that are ordered according to their natural brightness. For example, most people prefer a combination of dark blue and light orange over a combination of dark orange and light blue. To operationalize this rule, we find the natural brightness of each of the six hues in a color palette, and see if the intensities of these six colors are in the same order. If these orderings are more similar, the Müllerness feature will be higher (as computed by the Spearman correlation). exPerIMeNT To evaluate the effectiveness of these new feature extractors, a classification experiment was set up. For the main experiment, a dataset was created by asking five participants to categorize a set of about 350 web pages on 3 different attributes. These attributes were selected so that there was some relation to visual features, namely: aesthetics, whether the site looks modern, and whether the website is informative. The average of each of the participants' scores was used to create two classes for each attribute, so looks good vs. looks bad, modern vs. old and commercial vs. informative. A Naive Bayes classifier was then trained and tested using 10-fold cross-validation. Performance was best on the aesthetics task, with 73% accuracy, and worst on the informativeness task, with 61% accuracy. This makes sense when you consider that, whether websites look informative or commercial, might involve more semantics that are harder to detect in simple visual features. nummer 2, december 2010

13

Agenda Workshop: An empirically-informed philosophy of logic » 7 and 8 december 2010, Amsterdam

Among the most predictive features for the aesthetics experiment were those that characterize the number of colors on the page and the number of photos used. Pages with many colors were usually considered to be bad looking, and a higher number of photos indicated a good looking page. In the modern vs. old experiment, the most important features were the size of the page and the average area covered by each photo. This is explained by technical limitations that were considered when the older websites were built. The older pages tend to be less wide, because they were designed for smaller monitors. They also have less and smaller pictures because of the limited bandwidth that was available. When distinguishing between commercial and informative pages, the number of photos was once again important, as photos are often used to display products and “happy customers” on commercial websites. Conclusion These experiments have shown that it is effective to extract high level design-related features from web pages in order to classify them. The method can be used to distinguish between different design-related qualities, and works well for classes that are closely related to the appearance of the website. High accuracy on aesthetics tasks indicate that the features are well suited for characterizing beauty in web design. This new method performed better than an earlier attempt at visual classification, and it has the added benefit of producing a human-readable feature space, allowing for easy examination of classification results and insight into what constitutes good web design. A practical application of the described methods could be a web design evaluation tool. If a classifier was trained on a larger dataset with good and bad design, it could be used to grade new pages. The tool could then return an overview of which features contributed to the grade, and how the page should be changed to get a higher grade. However, it remains to be seen if this method is by itself practically useful. Although the results for each experiment were significantly better than random , a real-world application might need more than 8 out of 10 correct predictions. In order for performance to improve, the feature extractors have to be fine-tuned and new feature extractors might be necessary. ø

Topics: Logical form in cognitive processes, Animal logic, an evolutionary perspective on deductive reasoning, Towards a cognitive science of proof, Reasoning with generic information, Formal languages and the extended mind. http://www.illc.uva.nl/peipl/

fMRI: From Neurophysiology to Cognitive Neuroscience » 10-12 december 2010, Maastricht Physical Basis of fMRI, Alternative fMRI methods, FMRI data analysis, clinical & cognitive applications. Lectures, exercises, and practical demonstrations. http://www.esmrmb.org/

CSCA lecture by Kees Stam » 15 december 2010 Plantage Muidergracht 22-24, Amsterdam, room P2.27 Both segregation and integration of information have to be dealt with in a single architecture of brain networks. There is strong evidence that synchronization of neural activity, both locally and between distant regions is a crucial code for functional interactions. A short pathlength, which implies that from any area in the brain any other area can be reached in a small number of steps, is strongly correlated with IQ. http://www.cognitie.nl/events/csca-lecture-by-kees-stam/

Symposium: New perspectives on face processing » 20 december 2010, Tilburg University How faces and facial expressions are perceived and processed in the brain. http://bit.ly/bPuzVz

AWESOME IT » 11 februari 2011, Amsterdam Een symposium over mens en IT. Zeer geschikt voor studenten, 7,50 euro. congres.svia.nl

IK 2011 » 25 March - 1 April 2011, Germany, near Dortmund The Interdisciplinary College (IK) is an annual, intense one-week spring school which offers a dense state-of-theart course program in neurobiology, neural computation, cognitive science/psychology, artificial intelligence, robotics and philosophy. The IK is also a unique social event. In the evenings participants may enjoy the very special atmosphere: minds meet, music is played, and friends are made in long evening and night sessions.

Prevention of noise-induced hearing loss » 14 january 2011 from 14:00-15:00 Groningen, Onderwijscentrum UMCG, Lokaal 4

Does music make you smarter? » 19 january from 16:00 - 17:00, Plantage Muidergracht 22-24 Amsterdam, room P2.27


CSCA lecture by Glenn Schellenberg

Jaap Oosterbroek, [email protected]

column

De Connectie

Wetenschap is niet mijn ding De meeste van mijn docenten zijn erg enthousiast over wetenschap. De meeste van mijn docenten zijn er ook erg teleurgesteld over dat er zo weinig studenten enthousiast zijn over wetenschap. Zo bleek maar weet eens uit het bedrukte gezicht van een docent toen hij de zaal vroeg hoeveel van hen onderzoeker wilden worden. Twee mensen staken twijfelachtig hun hand op maar besloten deze na een haastige inspectie van de modus in de zaal weer te laten zakken. De universiteit gaat er vaak ten onrechte van uit dat studenten zich inschrijven omdat zij in wetenschap zijn geïnteresseerd. Studenten gaan echter naar de universiteit omdat dit de opleiding is die het best aansluit bij hun capaciteiten. Voor de meeste van hun zou een gelijksoortig opleiding op het HBO lijden tot verveling, stagnatie, drugsverslaving en uiteindelijk suïcide. Het overgrote deel van de studenten vindt het fantastisch om dingen te leren, en neemt het wetenschappelijk gedoe dan wel op de koop toe. Bij docenten geeft dit helaas ergenis, stagnatie, een alcohol probleem en uiteindelijk totale desinteresse in de belevingswereld van studenten. In een recente enquête onder studenten in mijn eigen natuurwetenschappen faculteit is gebleken dat meer dan de helft van deze studenten een gebrekkige informatievoorziening over de aansluiting op de arbeidsmarkt ziet als het grootste manko van hun studie. Velen hebben blijkbaar het gevoel dat ze onvoldoende worden voorbereid op dat fatale moment waarop ze kiezen voor een comfortabele positie met een boven-modaal salaris in het bedrijfsleven in plaats van een wetenschappelijke carrière vol uitdagingen en creatieve energie. Voor mij is dit probleem acuut geworden nu ik recentelijk toch echt ben begonnen aan mijn afstudeerfase. Een angstaanjagend moment dat zal moeten worden afgesloten met een scriptie, daarop volgende een diploma en tenslotte, als het even tegen zit, een baan. Tijdens deze kwartalen van onzekerheid en wanhoop over de vraag waar ik nu weer terecht ga komen probeer ik mij te troosten met de gedachte dat ik een min-of meer competent ICT-er ben en ik toch-wel goed terecht kom. Maar wat als dat nou niet het geval zal zijn? Wat als alle baantjes die met computers te maken hebben straks naar India verhuizen. Wat als op het aanstaande moment dat al die babyboomers met pensioen gaan er ineens geen behoefte meer is aan

hoogopgeleide mensen in het bedrijfsleven. Wat als de Kwisatz Haderach op aarde komt en predikt dat alle privé-computers verbannen moeten worden zoals in de oranje bijbel geschreven staat? Zou ik mijn geest dan toch laten prostitueren aan een promotiepositie? Als het schrijven van een bachelorthesis mij één ding heeft geleerd is het dat ‘het’ academische echt niet mijn ding is. En zelfs als ik me er overheen kan zetten om van dat prachtige ambtenaren pensioen te kunnen genieten ik af en toe iets afgrijselijks zou moeten insturen naar een stoffige periodiek in de hoop dat iemand het voldoende passend in zijn eigen ideeënwereld acht, zou ik mezelf met moeite kunnen overtuigen om een wetenschappelijke carrière na te jagen. Natuurlijk lijkt het me fantastisch om na mijn studie nog over dezelfde creative ruimte en uitdagende omgeving te beschikken. Maar voor mij betekent wetenschap ook een bestaan in het verschikkelijke bureaucratische apparaat dat de universiteit heet. Voor mij is wetenschap ook omgaan met een pertinent tekort aan middelen. Een voortdurende strategische terugtocht tegen de oprukkenden budgettaire belangen van de hypotheekrente aftrek. Het hozen op een zinkend schip dat de kenniseconomie moet heten met een steeds kleinere emmer. Wetenschap is ook het omgaan met de agaïsche instituties en paradigma's die de vorige generatie wetenschappers heeft achtergelaten en vergeten op te ruimen toen ze besloten zich verder toe te leggen op het vergaren van beurzen en het runnen van een vakgroep in plaats van het doen van daadwerkelijk onderzoek. Ik kan natuurlijk al die nadelen de grond in kan relativeren. Ik kan de voordelen doen opzwellen tot heroische proporties. Ik kan dit alles op een valse weegschaal leggen en extra bijblazen op het moment dat ik het oordeel aflees. Dan, zelfs dan kan ik helaas niet erg enthousiast worden over wetenschap.


15

Sicco van Sas, [email protected]

Harvesting the knowledge of the public Vast technological improvements in the past two decades have made it possible to easily log our every-day experiences in digital format. We make photos and videos with our mobile phones and use GPS to track where we are. Access to high speed internet, whether via a cable or wireless, allow people to share this information via websites. Some of these websites have gathered enormous amounts of publicly available data. This data can be used for many purposes. After finishing his bachelor Artificial Intelligence, Sicco van Sas is currently studying the master of Artificial In telligence at the University of Amsterdam. This article is based on his bachelor thesis. He is further developing these ideas together with Abdo el Ali, a PhD student in Mobile Human-Computer Interaction at the UvA as part of the ILPS (Information & Language Processing Sys tems) group.

EXPERIENCING THE CITY Geotagged photos1 from Flickr can be used to create route recommendations, which allows for better navigation through a city. Tourists often find themselves lost in a new city. They'd like to know how to get from their current location to their destination via a nice and interesting route. To do this, they currently have to resort to city maps, tourist guides or by asking locals. While these methods work, they don’t offer a precise solution to the specific needs of different tourists. Our method makes use of hundreds of tourists and 1


Photo’s with GPS coordinates

locals who have shared their interpretation of the city in the form of geotagged photos and tags. This data can be used to discover how the public actually experiences the city. LOCALISATION Modern mobile devices can be used as ‘geographical information systems’ as they are capable of tracking their location, using location-aware technologies like GPS or cellular localization techniques. These geographical information systems have the ability to track the spatial behavior of people. This development has brought renewed interest to the time geography field. Time geography analyzes the patterns of human activity using space-time paths and has been praised for its representational capabilities, but has also been criticized for not being able to take the (social) context of human actions into perspective. A simple demonstration of this critique is as follows: A GPS tracker has logged the activity of a person. This person has walked through the streets of a city only to stop for 15 minutes at a certain location. It would be interesting to know why the person has stopped at that specific location, but this information is hard to infer from the pure GPS data. The person could have stayed there because of a nice view, which would mean that this place is interesting and thus a good recommendation to others. But the person could have also stopped because he coincidentally walked into a friend and decided to have a little chat, which would mean that this location is not particularly interesting. Luckily, GPS data is often coupled with other data like tweets, tags and photos. This geotagged data can be used to

harvesting the knowledge of the public

De Connectie

Figuur1. A route through Artis (the zoo of Amsterdam), inferred from geotagged photos.

make assumptions about the meaning of the spatial-temporal activities. We assume that photos convey a certain experience which the photographer went through and made him decide to take a photo. This experience could have been a nice building or some other thing of interest. In Flickr, these experiences can be partially inferred from the photo tags and the objects in the photo. This way, we can infer the social context of a certain location. HARVESTING THE EXPERIENCES Flickr hosts a few billion images and more

than 100 million of these are geotagged photos. Many photographers take several geotagged photos a day and publish these on Flickr. The geotag information together with the time and date of the photo can be used to easily infer the route made by the photographer during that day, as seen in Figure 1. This route consists of a sequence of locations where the photos were taken. Assuming that photos contain interesting experiences for the photographer, such a route can be interpreted as the highlights of the photographer’s experiences during that day. In the context of a tourist walking through a city, the route can be seen as the places that appealed to the tourist. Each of the locations of this route are semantically enriched with the tags that were added to the photos by the photographer. The social context of the route can therefore be described using a tag cloud and some sample photos. The goal of all this is to create route recommendations. It is quite arbitrary to give a recommendation based on just one route, so we constructed a database of nearly 500 routes taken by different pho-

tographers in Amsterdam. These routes were inferred from more than 65.000 geotagged photos from Flickr which were taken in Amsterdam during 2009. The routes in this database were compared to each other to find matching (parts of) routes. We assumed that if multiple routes took a similar path through the city, then this path must be popular and is therefore suited for recommendation. FROM EXPERIENCE TO RECOMMENDATION The specific sequence of each route had to be taken into account when comparing it to other routes. The task of comparing sequences is well studied in the bioinformatics field. They have been comparing sequences of protein and DNA for decades and developed various sequence alignment methods to do so. Back in the 90s, Clarke Wilson noticed that the comparison of sequences could be of great use to analyze social space-time activities2,3. He extended a bioinformatics program (ClustalW) to work with more types of data, in order to represent social spacetime activities. This program, ClustalG,

Figure 2. Several aligned sequences. Sequences with matching words are highlighted.


17

advertentie:

ing words together. The more matching words in a vertical sequence, the more popular the route. Figure 3 shows a small selection of these popular routes.

Figuur 3. A few popular routes, obtained via multiple sequence alignment.

performs multiple sequence alignment by comparing sequences of words via several iterations of pairwise alignment and the construction of similarity trees. The location coordinates of the data had to be discretized in order to be represented as words. We divided Amsterdam in a grid with 50 by 50 meter cells (as seen in Figure 1), where each cell was represented with a unique four character word (for example ‘Gewq’). A single route consisting of 8 locations (the first letter of a location’s word is capitalized) would then be: "GewqGcnjGcndGevtGjneGkrwGkrpGoew" Figure 2 shows a part of the result of multiple sequence alignment. The horizontal lines are individual routes taken by tourists. ‘Popular routes’ are parts of such routes with many matching words (highlighted). ClustalG has added gaps (denoted by ‘----’) in between several of the route sequences in order to group match-


Our research is currently at this stage. Further developments will allow users to submit their current location and a desired destination. A search algorithm will then find several routes by connecting popular route segments. The user will get a visualization of the routes to choose from. A problem however, is that the user, most likely a tourist, will not be able to choose between the routes. That is where the tags come in to play. A tagcloud for every route recommendation should give the user a clue of what to expect for each route. Besides the tags, a few sample photos for each route will give the user an impression of what can be seen on that particular route. These semantic clues help the user to select a preferable route. Future user studies based on this program will have to determine whether this method can become an alternative for traditional ways to navigate through a city. This method shows how digital breadcrumbs of peoples activities can be used to gain intricate social knowledge of areas, which can be used to enhance peoples experiences. ø

Bibliografie: [1] Hägerstrand T. - What about people in regional science? Papers in Regional Science, 24(1):6-21, 1970. [2] Wilson C. - Activity pattern analysis by means of sequence-alignment methods. Environment and Planning A, 30(6): 1017-1038, 1998. [3] Wilson C. - Reliability of sequence-align ment analysis of social processes: Mon te carlo tests of clustalg software. Environ ment and Planning A, 38(1):187-204, 2006.

korting op awesome it Tickets bestellen voor 14 december

surf snel naar: www.congres.svia.nl

awesome it

> IBM > Guerilla Games > Cognitieve Robotica > Computerkunst

Ork de Rooij, PhD in Computer Science, UvA, [email protected]

about finding needles in haystacks

De Connectie

About finding needles in haystacks Ork de Rooij is a PhD student in comput er science at the Uni versity of Amsterdam, where he works on ad vanced visualization systems for large vid eo collections. His main research interests cov er multimedia informa tion visualization, user computer interaction and large scale con tent based multimedia retrieval systems. Con tact him at [email protected]

Nowadays, there are many online multimedia collections available such as YouTube, Google Video and uitzendinggemist.nl. Although users are frequently able to add descriptions or tags to these videos, many videos still remain largely descriptionless, or unannotated. This poses a problem: what if we want to retrieve something specific later on? How do we find it? Without further aid, this is not much different than looking for a needle in a haystack.

T

he problem becomes even bigger if we include offline collections such as personal home video, surveillance videos and digital broadcast archives. In these collections the lack of annotation is even greater, and because the content is not online you cannot hope for hundreds of users tagging everything for you. Finding something specific then becomes next to impossible without resorting to just watching everything. In this article we give a bird’s-eye view of the research area of content-based video retrieval. We highlight a couple of solutions to this problem, and showcase the approaches we are investigating at the Intelligent Systems Laboratory Amsterdam of the University of Amsterdam. Content-based video analysis A video with no annotation or other metadata cannot be found without further aid. But, that what you are looking for is represented in the video itself. So, to search for something, we need to look at the content itself. For a human, this is easy. For a computer, not so much. Generally, in content-based image retrieval, a series of content analysis algorithms study images or videos and extract information from them. This can be something simple, like “This image contains 50% blue stuff ”, though nowadays we’re more at the levels of “This image probably contains an airplane”. The number of available techniques to do this has grown rapidly in the last decades, varying between methods which analyse images globally, per region, by extracting shapes, by color or texture, or by looking at interesting keypoints. For example, one of the more popular and heavily researched methods used nowadays in video retrieval is the Scale-Invari-

Figuur 1. A screenshot of the ForkBrowser, part of the MediaMill Semantic Video Search

ant Feature Tranform (SIFT) method by David Lowe [6]. SIFT finds interesting points and describes these invariant to intensity, color, scale and rotation [8, 9, 2]. In the early years content-based video retrieval was based on low-level feature comparisons. However, this posed a problem for users. How do you translate that you are looking for “an airplane taking off ” into statements such as “25% blue present, horizontal line visible, ...”. This problem is known as the semantic gap [8]. To solve this, many existing systems tried to translate the query to the low-level feature space itself, requiring specialized forms of input from the user. Examples include drawing sketches or providing example images. This isn’t always possible or practical, so alternative methods are needed. nummer 2, december 2010

19

In more recent literature several solutions have been proposed and examined to try to solve the gap between user intent and low-level visual feature querying. One of these methods is generic concept detection [9] which allows automatic labeling of people, objects, settings or events within video content, albeit with varying performance.

“Each shot is now also automatically annotated with presence scores for a variety of concepts” Concept detection globally works as follows. First, video is segmented into individual shots: fragments of video from a single camera capture. These shots are then analyzed individually and low level visual features are extracted. Next, for each definable concept we first need to “learn” this concept. This is done by manually tagging (large) sets of shots with labels, indicating that for example “this shot contains an airplane”. These sets of labels are then used in supervised machine learning algorithms, such as Support Vector Machines [1]. These

algorithms create an internal representation of that concept based on the set of given examples. This internal representation, or model, of a concept is then stored and used later on to determine that concepts presence on new video fragments. This yields a score between 0 and 1 indicating the system’s view on the presence or absence of visual concepts for each shot in the collection. These scores can be seen as a new form of metadata that can be used to characterize individual shots. Each shot is now also automatically annotated with presence scores for a variety of concepts. The quality of automated detection varies however, so to be sure, results must still be visually inspected. A combination of automated analysis and visual inspection does however give us a means to do content-based video retrieval. Finding Needles Interactively A set of detected semantic concepts, together with other computed sources of information, such as speech recognition results and similarity between shots, gives us several ways to search through video. Worldwide, several institutes, companies and universities are working on both content based analysis and accompanying interactive interfaces for video retrie-

Engine. Right: figuur 2. A screenshot of the UvA MediaTable system. Here you see part of a collection of 200 hours of video visualized as a table, with a part expanded through a lens effect.


about finding needles in haystacks

De Connectie

val, which use these methods for search. International research benchmarks such as TRECVID[7] and competitions such as VideOlympics[10] aid this by providing a common base of comparison between systems. The most successful interactive video retrieval interfaces allow users to navigate through hundreds of results at extremely high speeds. For example, the Extreme Video Retrieval system[5] uses rapid serial visual presentation which shows results extremely fast and users only have to press a button when they think they saw something relevant fly by. At the University of Amsterdam, we designed the ForkBrowser[4]. See figure 1 for a screenshot. The ForkBrowser combines both rapid viewing of query results with browsing through time and visual similarity at the same time. It does this by presenting search results in the shape of a fork. Each direction presents a different type of results, and users quickly browse through these by using hotkeys on the keyboard. Each image represents a video shot, and the center image is also played at high speed to allow the user to see its contents. This browser is shown to be highly effective at interactive video retrieval at the TRECVID conference [7, 4], and as such helps users in finding those specific fragments of videos based on their visual content alone. Navigating at extreme speeds allow us to find some needles (rapidly) in the collection, but what if we want to find all of them, and know for sure that we did find them? Search engines such as the ones in the above paragraph you’d then need to exhaustively browse through results – through the entire haystack – and only when reaching the very last page you’d

“ForkBrowser combines both rapid viewing of query results with browsing through time and visual similarity at the same time” know for sure that you found everything. This kind of problem requires a different type of interface. The UvA MediaTable[3] system, see figure 2, was designed with this problem in mind. This system uses existing easy-to-understand visualizations, such as a table, grid or scatterplot. It depicts the entire collection, with rows or items showing a video shot, which on mouse over will be enlarged and played. Metadata, including semantic concepts calculated by content based analysis techniques, are also visualized in the table, in such a way that users can quickly spot correlations and patterns between various forms of metadata. Users can search through the collection by sorting on any kind of concept, selecting results, and placing these in so called buckets.

The MediaTable software allows users to work in a different way than the ForkBrowser: instead of starting out finding what you are looking for, you first categorize your collection into smaller chunks of which you know the contents, and you do this really fast. This makes the collection smaller, and you end up with having to look through less and less hay to find your needles. ø

References [1] C. chung Chang and C.-J. Lin. Libsvm: a library for support vector machines, 2001. [2] R. Datta, D. Joshi, J. Li, and J. Z. Wang. Image retrieval: Ideas, influences, and trends of the new age. ACM Comput. Surv., 40(2): 1–60, 2008. [3] O. de Rooij, , M. Worring, and J. van Wijk. Mediatable: Interactive categorization of multimedia collections. IEEE Computer Graphics and Applications, 30(5):42–51, Sept. 2010. [4] O. de Rooij, C. G. M. Snoek, and M. Worring. Balancing thread based navigation for targeted video search. In Proceedings of the ACM International Conference on Image and Video Retrieval, pages 485–494, Niagara Falls, Canada, July 2008. [5] A. G. Hauptmann, W.-H. Lin, R. Yan, J. Yang, and M.-Y. Chen. Extreme video retrieval: joint maximization of human and computer performance. In Proceedings of the 14th annual ACM international conference on Multimedia, pages 385–394, New York, NY, USA, 2006. ACM Press. [6] D. G. Lowe. Distinctive image features from scale-invariant keypo ints. Int. J. Comput. Vision, 60(2):91–110, 2004. [7] A. F. Smeaton, P. Over, and W. Kraaij. Evaluation campaigns and trecvid. In Proceedings of the 8th ACM International Workshop on Multimedia Information Retrieval, pages 321–330, New York, NY, USA, 2006. ACM Press. [8] A. W. M. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain. Content based image retrieval at the end of the early years. In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 22, pages 1349–1380, December 2000. [9] C. G. M. Snoek and M. Worring. Concept-based video retrieval. Foundations and Trends in Information Retrieval, 4(2): 215–322, 2009. [10] C. G. M. Snoek, M. Worring, O. de Rooij, K. E. van de Sande, R. Yan, and A. G. Hauptmann. VideOlympics: Real-time evaluati on of multimedia retrieval systems. IEEE MultiMedia, 15(1):86–91, 2008.

Kaspar de Geus, Human Centered Multimedia, UvA, [email protected]

How Mobile Assisted Language Learning Can Support Learning English as a Second Language in Primary School Learning is an important part of life and it takes place at many different times, places and in diverse situations. Society has brought forth schools to stimulate and regulate learning. This has the advantage that the learning process is highly structured, which facilitates linking to and building on previous knowledge. In addition, learning is made explicit, making it easier to remember and reproduce the lessons learned. With the growing amount of digital information, the availability of study material that is being distributed digitally to students has also grown. Although some of this content is now also available through educational websites after school, most of it is only presented to the students during lessons, which means a lot of potential learning moments are now ignored.

B

Kaspar de Geus is a latecomer to the ac ademic world, as he started out getting a HAVO degree (similar to senior general sec ondary education) and only after some years of travel abroad and work he started his bachelor in Artificial Intelligence at the University of Am sterdam (UvA) at age 23. After this bachelor he continued with the master Information Sci ences also at the UvA and wrote this article about his graduation research/thesis.

esides lessons becoming more digitally inclined, the amount and the capabilities of mobile phones are increasing rapidly. New generation phones (smartphones) have an increasing amount of functions like GPS navigation (Global Positioning System), wireless Internet and digital cameras. Furthermore, the amount of wireless-network coverage is increasing while the cost of use is decreasing, which enhances the possibility to use the information available on the Internet and on other networks whenever, wherever and for as long as people want. Making use of these two trends, we investigated the advantages of using a mobile device to increase the freedom to learn, using digital lessons and serious games. Specifically, we taught primary school students English as a second language using a mobile learning application as an addition to the normal lessons already given at schools using the Early Bird method1. The goal was to see if their motivation to learn and ability to use English would increase. We presented the possibility to learn at their own pace, at a time of their choosing and in more diverse settings than just the classroom. Students had 24 hours a day access to a smartphone with a serious game designed for the purpose of learning English. The teaching application, in the form of a serious game (the MEL game), is built around 25 animals with 5 different game types. There is a multiple choice quiz, a spellings quiz, a memory game, a “Yes or No” 1

game and a jigsaw puzzle. The games could be played during their visit to Diergaarde Blijdorp (a zoo in the center of Rotterdam), and at home. All questions and answers are read out loud because the children’s ability to read English was still limited. To make sure the pronunciation was clear, we used high quality audio files. Before each game a movie clip about the animal in question was played (which can also be replayed). This clip contains all the information needed to answer the questions. All audio files, as well as the spoken text in the movies are sound recordings made using a native speaker that read out loud. Research The experiment consisted of a pretest, a learning phase and a posttest. Each student was subjected to an oral pre- and posttest of English language skills concerning zoo animals. In between, tests groups 1 and 2 got three weeks of English lessons about zoo animals. The lessons were specifically created for this experiment, and consisted of a teacher presenting stories and songs, giving out handouts and completing oral and written assignments. Group 3 started its lessons with a trip to Diergaarde Blijdorp were they where issued a smartphone with the MEL game. Following this trip, these students had similar lessons as conditions 1 and 2 for three weeks (four hours worth of lessons). Besides

The earlybird program starts English lessons at an earlier age and uses mainly native English speakers as teachers. http://www.earlybirdie.nl


mobile assisted language learning

De Connectie

these lessons they also got to take the smartphones home after the visit to the zoo. The logs created by the MEL game indicate that on average the game was played for approximately 4.1 hours by each phone. Results/Conclusion In the pretest we found no significant difference between the groups in language skill. In the posttest there were significant differences, which we explain by the difference in time spent learning. Students did use their free time to learn when they had access to a smartphone with a serious game on it, so the game was motivational enough to keep learning. When asked, 41.86% of the students replied they would play a similar game every day of the week given the chance. Although some parents had their initial doubts about letting their child use the smartphone,

their attitudes changed when they noticed their children learning new words with the game. One parent even said: “My first reaction was; not another mobile [device] to play games on! My son is only allowed to play one hour each day with his consoles. I do not, or more accurately did not, want to stimulate this. Now, after two weeks, he has picked up quite a few English words! Great!”. After a thorough analysis of the obtained data we can conclude that the application that we created was just as effective in teaching English to primary school students as additional lessons with a regular teacher. Spending extra time learning using the MEL game results in acquiring the same amount of target words as when learning in class with a teacher. ø The thesis can be downloaded from: http://student.science.uva. nl/~kgeus/MEL-MScThesis-0426849.pdf

Snapshots from the MEL game. A multiple choice question (Owl); a jigsaw puzzle (Ele phant), a spelling game (Boa constrictor), and a “Yes or No” question (Hyena).


23

Frank Nack, UvA ISLA, [email protected], http://fnack.wordpress.com

CreAtivity – Some UnromAntic Thoughts For a lot of people human creativity is a mystery, impossible to be understood or modelled and yet so simple that it virtually enters into every aspect of life. Every human being has the ability to come up with new, surprising and important ideas or artefacts; we all are creative every day – but astonishingly most people believe that only a small group is attributed to be truly creative, namely artists and scientists. Dr. Frank Nack is tenure as sistant professor at the Infor mation and Language Pro cessing Systems group (ILPS) of the Informatics Institute of the University of Amster dam (UvA). The main thrust of his research is on represen tation, retrieval and reuse of media in hypermedia systems; context and process aware media knowledge spaces; representation and adaptation of experiences; hypermedia systems that enhance human communication and creativ ity; interactive storytelling; computational applications of media theory & semiotics; AI and film (semantics, semi otics, perception); and com putational humour theory. He has published more than 100 papers on these topics.


A

nalysing what creativity is made of [1, 2] often focuses on the aspect of ‘newness’. Yet, a clear categorisation of ‘new’ in the context of creativity is hard and so it seems more appropriate to distinguish between two levels of creativity instead, namely psychological creativity (P-creativity) and historic creativity (H-creativity). The former describes ideas that are new, surprising or valuable to the individual and here it does not matter how many other people also had have this idea before. For the historic creativity it is important that the idea is truly new in the realm of human history. As H-creativity is a specialisation of P-creativity it is suitable to look at the P side of the

phenomenon, as the individualisation of the process allows us to comprehend how people come up with new ideas. Looking at the process of being creative in more detail it becomes apparent that the element of surprise is very important. Creativity is like a good joke, it presents us with an insight established by combining the un-combinable, resulting in pleasure – and both humour and creativity turn out not to be magic but indeed processes that can be described [1, 3]. Taking the element of surprise as the driving force behind creativity we can see different ways how creativity works. In the first and shortest way to creativity humans make unfamiliar combinations of familiar ideas and appreciate the novelty of this combination. Both steps require knowledge the person has access to and a set of mechanisms to navigate within this space. These sources can be little, as already young children are creative, but the larger the knowledge and set of navigation means the higher the chances of being able to apply combinatorial creativity. The second way of being creative operates in a conceptual knowledge space – mainly absorbed from one’s own culture or taken from other cultures. These types of conceptual spaces already exist and provide, for example, rules on how to write poems or style descriptions of paintings – thus ways of acting and thinking valuable to a certain social group. Being creative in such a conceptual space means to apply exploratory creativity, as the aim is to establish the possibilities and limits of general types in this space. The third and hardest way of being creative is concerned with the transfor-

creativity-some unromantic thoughts

De Connectie

Premeditate

mation of such a given space. Here, creativity is an opportunity to change the structures of the space, alter its mind-set, the style of thinking (the rules) that rendered certain thought impossible. How did Braque and Picasso invented Cubism – because they left the path of thinking of a painting as depicting objects from one viewpoint but rather thought of a painting as the result presentation of breaking up objects, analyse and then re-assemble them in an abstract form to present the object from a multitude of viewpoints in a greater context [4, pp. 573 574]. In AI research we have seen a long tradition of attempts to create computer creativity where H-creativity in an explorative context (the second way) plays a dominant role [3, 5]. In both references, systems are described that automatically generate humorous statements in different forms of media, i.e. text, speech and video. The problem with those approaches is that they never reached the level to establish rule sets that allow the breaking of rules, which is essential for transformational creativity (the third way). Though they enhanced our understanding of creativity it seems to be more plausible to not make the machine creative but to provide it with a notion of what it means to be creative. In this view P-creativity in a personalised (first way) and explorative (second way) context becomes the relevant item of investigation (where a transformation step can be the result, only that the machine does not have to produce it but has to be able to recognize it). The three essential aspects to be studied are the conceptual space of a domain, e.g. new media, the processes applicable in this domain and how they are applied and

Create

Annotate

Annotate Package

Construct Message

Organize

Query Publish

Distribute Figure 1: Canonical processes of media production

performed by humans. Take for example a production tool like PowerPoint. This application provides the means to establish multimedia presentations but it cannot support the user with insights if the current production makes sense nor can it assist if the user gets stuck with a communication problem. Trying to enhance PowerPoint, we first have to know something about the various processes that are applicable in multimedia production and communication. The essential processes for media production, exploitation, adaptation and

distribution (see Figure 1) are described in [6]. We then have to understand which of these processes requires personalised as well as explorative P-Creativity. This can be achieved by observing people while they produce PowerPoint presentations. For example, what do people do to construct the messages they try to communicate towards the audience? Is their strategy first to think about the presentation structure and then collect the material to be presented (top down approach) or do they first collect all the material and nummer 2, december 2010

25

only then start thinking about how to present it (bottom up approach). Understanding these mechanisms will help to build a system that can support users in their P-creativity in an informed (i.e. intelligent) manner. The result might be a system as described in [7], see also Figure 2, which portrays two of the three essential parts of support through the system, namely structure building and content collection. What the system essentially does is to harvest the domain knowledge (art) for the production of particular presentation

styles (e.g. article, biography, comparison, essay, lecture, etc.) where the system helps to identify the appropriate structure and material. Essential is that the system evaluates the steps taken by the user based on the history of the user’s personalised and explorative P-creativity (the history is part of the adaptive user model), facilitating in this way to open doors for new creative endeavours by stimulating yet unrecognised ways of working. How does it achieve that? As the system not only monitors the creative steps of the user but also has access to presentation cases produced by other users, it can provide new insights (not yet investigated structures) that stimulate the explorative creativity of the user. Cases where the user generates a transformation can then be identified due to the non-existence of similarity matches within the case-base of presentations. The interplay of process understanding, action identification and the contextualisation of generated content is key for that type of creativity understanding. What makes this type of approach interesting (see a different example making use of common sense knowledge for a camera that helps filming events with suggestions of what is important and needs to be captured [8]), and fun to research, is the combination of knowledge representation Figure 2. IPP interfaces for Topic (top and center) and content techniques (understand(above) identification.


ing a domain), the modelling of processes (understanding human action), as well as the modelling of human action (creativity) based on the analysis of individual behaviour. Over time it can be expected that an individual is facilitated with means to improve his or her creative potentials. At the same time accumulated data will allow us to get an even better understanding of what creativity really is. The talk at the AWESOME IT conference aims at sharing with you the research insights as well as fun aspects of creativity in an AI context. ø

References [1] Boden, M. A. (2004). The creative mind – myth and mechanisms (2nd edition). [2] Boden, M. A. – editor (1994). Dimensions of Creativity. A Bradford Book – MIT Press, Cambridge, Massachusetts [3] Binsted, K.; Nijholt, A.; Stock, O.; Strappa rava, (2006). Computational humor, IEEE Intelligent Systems Volume 21, Issue 2, 2006, pp. 59 - 69 [4] Grombrich, Ernst H. (1999). The Story of Art (16th edition). Phaidon Press [5] Nack, F. (1996) The Application of Video Semantics and Theme Representation for Automated Film Editing Ph.D. Thesis, Lancaster University. [6] Hardman, L., Obrenovic, Z., Nack, F., Kerherve, B., and Piersol, K. (2008). Canonical Processes of Semantically Annotated Media Production. [7] Falkovych, K. & Nack, F. (2006) Context Aware Guidance for Multimedia Authoring: Harmonizing domain and discourse know ledge. [8] Williams, R., Barry, B. and Singh, P. (2005). ComicKit: Acquiring Story Scripts Using Commonsense Feedback.

Jaap Oosterbroek

los de puZZel op en win een...

De Connectie

AI Killer Menig student kunstmatige intelligentie heeft een voorliefde voor logische puzzels. Dergelijke puzzels zoals sudoku, japanse beeldzoeker, zeeslag en andere regelmatig terugkerenden gasten in de logivaria, worden doorgaans als uit-dagend en plezierig ervaren. Dit is echter een grote misvatting. Logische puzzels zijn naar, vervelend en gotsgruwlijk moeilijk. In deze nieuwe puzzel rebriek zullen wij trachten dit aan te tonen. Uitraard zal de gemiddelde Connectie lezer hier in recalcitrante wijze op reageren door ons te laten zien hoe leuk en gemakkelijk het eigenlijk is om dergelijke puzzeltjes met de computer op te lossen. In de stijl van reversed psycology zullen wij trachten deze figuren verder te ontmoedigen door de mooiste inzending te bestraffen met het boek Gödel, Escher, Bach: An Eternal Golden Braid “ van Douglas Hofstadter*, in hardcover editie.

Voor deze eerste keer zijn we een lijst van meest moeilijkste sudokus op het spoor gekomen**. Bij deze de nummer 2 op de lijst welke de naam ‘AI killer’ draagt. Alhoewel er mensen zijn die claimen hem op te kunnen lossen zonder computer, is dit uiteraard niet de bedoeling. Ook is voor een dergelijk legendarische sudoku natuurlijk het antwoord op internet te vinden. Ook dat is nogal laf. Wil je echt laten zien dat jij de onbetwiste puzzelbreker bent en dat NP-compleet slechts een mythe om eerstejaars bang te maken, schrijf dan een programma*** dat deze en andere Sudoku’s zo snel mogenlijk kan oplossen naar:

*echte helden hebben dit prachtige werk natuurlijk al in hardcover in de kast staan. In dat geval kun je ook het boek “I am a strange loop” van Douglas Hofstadter ontvangen.

**Zoals verzameld door dr. Arto Inakala (http://www.aisudoku.com/ en/AIsudoku_Top10s1_en.pdf)

***gelieve een korte begeleidende uitleg van de code en zonodig compiler instructies mee te sturen. Inzendingen in Whitespace, brainfuck, lolCoDe en andere onleesbare of occulte programeertalen zullen uiteraard niet geëvalueerd worden. Als je zeker van je zaak wil zijn kun je ons altijd mailen.

redactie@ deconnectie.com


27

Emotionele voetbalrobot. Creativity -some unromantic thoughts. About finding needles in haystacks

Recommend Documents