Over Machines die Leren Luc De Raedt Dept. Computerwetenschappen
De Kunstmatige Intelligentie 1956: de eerste meeting rond kunstmatige intelligentie in Dartmouth de kernvraag:
• Kunnen we intelligente machines bouwen?
John McCarthy
Intelligentie Heeft veel aspecten en facetten Het onderzoek richt zich meestal op deelproblemen Wij : machinaal leren
• Kunnen machines leren ? • Kunnen we lerende machines bouwen ?
Overzicht A. Wat is machinaal leren ? B. Waarom is het interessant ? C. Hoe werkt het ? D. Waar leidt dit alles toe ? Toekomstverwachtingen
A. Wat is Machinaal Leren ?
Machinaal Leren Een machine leert wanneer
• zijn performantie (zijn prestaties) • op een bepaalde taak • verbetert met ervaring
Dammen
Arthur Samuel
Dammen
http://www.cs.ualberta.ca/~chinook/project/legacy.html
Dammen Machine = computerprogramma Taak = dammen Performantie = percentage gewonnen partijen Ervaring = gespeelde partijen
Spam
Spam Machine = e-mail programma, spamfilter Taak = e-mails classificeren Performantie = nauwkeurigheid van classificaties Ervaring = voorbeelden van spam en niet-spam
Recommender Systeem
Recommender Systeem Machine = website (en programma) Taak = boeken aanbevelen Performantie = behaalde omzet Ervaring = voorbeelden van voorbije aankopen
Machinaal Leren Een machine leert wanneer
• zijn performantie (zijn prestaties) • op een bepaalde taak • verbetert met ervaring
B. Waarom Machinaal Leren ?
Waarom ? Kunstmatige intelligentie Machinaal leren is gewoon erg praktisch
•
sommige programma’s (software) kunnen niet met de hand geprogrammeerd worden
•
analyse van data (data mining)
Inzicht in de aard van het leren en het verwerven van kennis
• •
welke wetten gelden voor lerende systemen ? cognitieve wetenschappen en wetenschapsfilosofie
Data Mining Machinaal leren analyseert gegevens/ervaring Nauw verwant met data mining
•
zoekt naar nieuwe nuttige kennis in mogelijk complexe datasets
Data mining is erg populair
•
Het is makkelijk om data te genereren maar moeilijk om ze te interpreteren
•
We are drowning in data but starving for knowledge
C. Hoe werkt het ?
Principes van Leren Een functie wordt geleerd
•
• •
Dammen
• • •
f(
) = 9-13
P(
,9-13) = kans dat zet gespeeld wordt
Q(
,9-13) = verwachte beloning
Spam
•
f(e-mail) = spam of geen spam
Recommender systeem
•
f(boek) = (geordende) verzameling boeken
De Ervaring Dammen
• • •
leren uit voorbeelden
•
goede/slechte zetten uit tekstboeken of van damleraar ?
leren uit imitatie (Eng. behavioral cloning)
•
imiteer de wereldkampioen
leren uit beloningen
• •
speel het spel, beloning = gewonnen stukken/partijen het AI probleem in het klein
Drie Leertechnieken 1. Het leren uit beloningen 2. Het leren van associaties 3. Het leren van beslissingsbomen + toepassingen en inzichten
C. Hoe werkt het ?
1. Leren uit beloningen
Donald Michie’s Menace
Donald Michie (2007)
Menace (1961)
Machine Educable Noughts And Crosses Engine
X aan Zet
O X O X Kies doosje op basis van huidige positie
Menace 287 luciferdoosjes
O X O X X Voer de zet uit
Kies at random een parel uit het doosje
Slide naar Johannes Fuernkranz
Menace Machine = 287 luciferdoosjes + parels Codeert probabilistische functie
• P(doosje, kleur) geeft kans weer op zet Leren van functie
Q (s, a) = R(s, a) + γ ∗
!
P (s" |s, a) max Q∗ (s" , a" ) ! a
• bij verlies: bewaar alle gebruikte parels • bij winst: stop gebruikt parels terug en voeg extra parel s!
van zelfde kleur toe
Richard Belmann
Q (s, a) = R(s, a) + γ ∗
! s!
∗ " " P (s" |s, a) max Q (s , a ) ! a
Exploratie versus Exploitatie Exploratie :
• de ruimte van mogelijke strategieën voldoende doorzoeken
Exploitatie :
• de geleerde kennis zoveel mogelijk gebruiken “Two armed-bandit” probleem
Leren uit Beloningen
Toepassingen in Games
AI en Games AI is meer dan Spelletjes Die worden vooral gebruikt omdat ze makkelijk te controleren omgevingen opleveren Tal van andere toepassingen
• robotica, controle, internet, ... Robocup
C. Hoe werkt het ?
2. Leren van associaties
Spam-filter
Associaties Welke producten worden frequent samen gekocht ?
4/5=80% 4/5=80% 4/5=60%
Associaties 4/5=80% 3/5=60%
ALS
DAN
met KANS
60% = 75% 80%
Toepassingen Dit zijn lokale patronen, ze zeggen iets over sommige gegevens Marketing, o.a. supermarkt, bank, ... Data mining in wetenschappelijke domeinen Analyse van (sociale) netwerken
Structuur-Activiteits-Relaties
Figuur: Siegfried Nijssen
Interpreteerbare kennis/patronen
C. Hoe werkt het ? 3. Leren van beslissingsbomen
Classificatie en Regressieproblemen Classificatie •
voorspel de klasse
•
bvb. spam of niet spam bij e-mail
Regressie
•
voorspel een numerieke waarde
•
bvb. de temperatuur morgen
Belangrijkste probleem in machinaal leren en data mining Tal van technieken; wij: beslissingbomen
Illustratie fortis dexia nee nee nee nee ja nee nee ja ja ja nee ja nee ja ja nee nee nee
kbc nee ja nee ja nee nee nee nee ja
... ... ... ... ... ... ... ... ... ...
Bel20 stijgt daalt stijgt daalt daalt stijgt stijgt stijgt daalt
Kan ik voorspellen of de BEL 20 morgen stijgt of daalt ? performantie = nauwkeurigheid
Een Beslissingsboom nee
dexia
ja
kbc stijgt
fortis daalt
stijgt
daalt
Een Illustratie Gegeven de vorm
Voorspel de kleur
rond nee nee ja nee ja nee nee ja nee
hol nee nee nee ja ja ja ja nee nee
driehoek nee ja nee ja nee nee nee nee ja
klasse groen rood groen rood rood groen groen groen rood
nee
?
ja
ronde ?
?
driehoek
holle
groen
rood
groen
rood
Beslissingsbomen Essentieel :
•
nauwkeurigheid geleerde boom (schatten a.d.h.v. “test-data” -- hangt ook af van kenmerken)
• •
criterium selectie kenmerken is essentieel (entropie) interpreteerbaarheid geleerde boom
Heel wat alternatieve methodes (o.a. probabilistische modellen) Toepassingen in allerlei domeinen:
•
medisch, financieel, wetenschappelijk, marketing, engineering, controle, ...
D. Toekomstverwachtingen
Verschillende Domeinen Wetenschap
•
Robot Scientist
Engineering & Control
• •
Darpa Grand Challenge Activiteitsherkenning
Sociale Netwerken
•
analyse
Wetenschap In heel wat domeinen :
• machinaal leren, data mining, essentieel • bvb. bioinformatics & computerlinguïstiek De toekomst ?
• The Robot Scientist (King et al. Nature 2004)
De Robot Scientist Kunstmatige intelligentie toegepast op de wetenschap zelf
• Kunnen machines wetenschappelijke werk verrichten ?
Robot Scientist (2004) Domein van microbiologie
•
pathway rond gist (Saccharomyces cerevisiae);
Experimenten opzetten om hypothesen te testen, te verfijnen, te bevestigen Werd geautomatiseerd Vergelijking met doctoraatstudenten
Nature 2004
Discussie Geen gevaar voor jobverlies in de wetenschap
• •
Het gaat om minder creatieve taken Wel ? Meer tijd vrij voor creatieve kant wetenschap
Nieuwe vragen en antwoorden voor wetenschapsfilosofie ?
•
Donald Gillies, AI and Scientific Method, 1996
Darpa Grand Challenge
Stanley -- Stanford Team o.l.v. Sebastian Thrun
Leren door Imitatie Voor sommige taken kan men geen controle programma’s schrijven met de hand De DARPA Grand Challenge
• sommige controle programma’s geleerd • o.a. classificatie terrein en snelheid bepalen.
Zie YOUTUBE: Sebastian Thrun -- Google Talks -- Grand Challenge
Leren door Imitatie
Snelheid Sebastian Slide Sebastian Thrun
Leren door Imitatie Sebastian
Stanley
Snelheid Sebastian en Stanley Slide Sebastian Thrun
Bestuur de wagen een tijdje Registreer waarden sensoren & snelheid Leer een functie die sensorwaardes afbeeldt op acties
Leren Terrein
Slide en video Sebastian Thrun
However, this profusion of options has not translated into an activity inferencing system capable of recognizing large numbers of day-to-day activities in natural environments. A key underlying problem is that no existing combination of sensors and feature selector has been shown to detect robustly the features necessary to distinguish between thousands of activities. For instance, objects used during activities have long been thought to be a crucial discriminator. However, existing object recognition and tracking systems [6] tend not to work very well when applied to a large variety of objects in unstructured environments. Activity recognition systems based on tracking objects therefore tend to be customized for particular environments and objects, and restricted in their utility as general purpose day-to-day activity recognizers. Given that producing each customized detector is itself a research task, the goal of general-purpose recognition has not surprisingly remained unattained.
Activiteitsherkenning
A new class of small, wireless sensors to individual objects seems likely to provide a practical means of detecting objects used in many day-to-day activities [3, 4]. Given this stream of objects, recent work has shown that even simple symbolic inference techniques are sufficient for tracking the progress of these activities.
Electronica sensoren
Detecting Object Use with RFID-Based Sensing
GPS, GSM, Smart Phone, video, PDA, RFID, ...
bevatten informatie over gebruik en gebruikers 1 cm
Intel Research
Figure 3 Radio Frequency Identification tags (left). A tagged toothbrush and toothpaste (right).
• Kan die gebruikt worden om
A passive Radio Frequency Identification (RFID [1]) tag is a postage-stamp-sized wireless, battery free transponder that, when interrogated (via radio) by an ambient reader, returns a unique identifier (see Figure 2). Each tag consists of an antenna, some protocol logic and optional non-volatile memory. Tags use the energy of the interrogating signal to return a 64 to 128-bit identifier unique to each tag, and when applicable, data stored in on-tag memory. Short-range tags, which are inductively coupled, have a 2 to 30 cm range, whereas long-range backscatter based tags have a 1 to 10 m range. Tags are available off the shelf for less than 50 cents a tag. Short range readers are priced in the
de gebruiker te assisteren ?
Francois Bremond
Mogelijke Toepassingen Ondersteuning gebruikers
• • • • • • •
Calo Project -- automatische office assistent ? Smart phones -- automatisch instellen Shopping -- niets vergeten, juiste prijs ? Transport -- juiste bus ? Intelligent huis -- fornuis uitgezet ? Surveillatie allerhande -- assistentie ouderen Ondersteuning bij job -- bvb. hulp rapportering agent of verpleegster
Netwerken P2 P1 P3 I1 A1
P4
Internet Sociaal Bibliografisch Wetenschappelijk Communicatie ...
Sociale Netwerken Heel wat informatie over personen en hun relaties beschikbaar
•
informeel:
• •
vandaag de dag:
• •
kring van kennissen, vrienden, collega’s en familie.
websites zoals Facebook, LinkedIn, Netlog, ...
het grote verschil
•
Men beschikt over informatie over IEDEREEN in het netwerk
Data kan geanalyseerd worden en gebruikt voor o.a. aanbevelingen, marketing
Analyse van Netwerken Voor bvb. aanbevelingen / marketing
•
Facebook: nieuwe kennissen; LinkedIn: jobs; Commercieel: nieuwe producten
Interessante problemen
• • • •
Wie een product eerst aanbevelen? Verspreiding ? Koopt iemand het product ? Classificatie. Welke relaties bestaan er tussen personen ? Wie zijn de autoriteiten, de hubs ?
Data Mining en Privacy Analyse activiteiten en sociale netwerken
• •
gevaar voor privacy, misbruiken, fouten, ... combinatie informatie op verschillende sociale netwerken
Het data mining onderzoekt ook
•
privacy preserving technieken
Het grote probleem is natuurlijk de beschikbaarheid van bepaalde informatie
Besluit Machines kunnen leren en hebben interessante toepassingen; veelbelovend ook in de toekomst
Referenties Youtube: Winning the Darpa Grand Challenge, Google Talks, Sebastian Thrun
•
ook artikels in o.a. Scientific American,
Robot Scientist (Aberystwyth), Ross D. King
•
artikels in Wired, Nat. Geographic, etc.
Dammen en andere spelletjes --
•
http://www.cs.ualberta.ca/~games/
Activiteitsleren
•
bvb. via Wikipedia -- Activity Recognition
Basiswerken Stuart Russel en Peter Norvig. Artificial Intelligence: A Modern Approach, 2de uitgave, Prentice Hall, 2002. Tom Mitchell, Machine Learning, McGraw-Hill, 1997. Ian Witten en Eibe Frank. Data Mining. Morgan Kaufmann: Practical Machine Learning Algorithms and Tools, 2de uitgave, Morgan Kaufmann, 2005.
