Samenvatting
Samenvatting Kunstmatige Intelligentie Leiden
Samenvatting van het vak Kunstmatige Intelligentie deels aan de hand van het boek Artificial intelligence, A modern approach van Stuart J. Russell en Peter Norvig, 3e editie.
[Meer zien]Voorbeeld 10 van de 42 pagina's
Voorbeeld 10 van de 42 pagina's
In winkelwagengesponsord bericht van onze partner
Gekoppeld boek
Titel boek:
Auteur(s):
- Uitgave:
- ISBN:
- Druk:
3 beoordelingen
Door: timothyvanexel • 4 jaar geleden
Door: joycevredegoor • 5 jaar geleden
Door: bekirdemir10 • 6 jaar geleden
Voorbeeld van de inhoud
Samenvattingkunstmatige Intelligent
19 mei 2017
Inhoudsopgave
1 Introductie 1
2 Agenten 2
3 Logisch redenerende agenten 7
4 Probleemoplossen en Zoeken 10
5 Gericht zoeken 13
6 Spel(l)en 16
7 Constrained Satisfaction Problem 21
8 Robotica 24
9 Neurale Netwerken 25
10 Leren 31
11 Genetische algoritmen 35
12 Bayesiaanse netwerken 38
1 Introductie
Kunstmatige intelligentie is een verzamelnaam voor een breed vakgebied met onder andere:
• Robotica: hoe programmeer je een robot?
• Data mining: wat staat er in/op Wikileaks?
• Rechtspraak: wordt je volautomatisch be-/veroordeeld?
• Vertalen: bijvoorbeeld de fouten bij letterlijke vertalingen.
• Computer games: hoe speelt de computer Cod?
• Neurale netwerken: kun je beurskoersen voorspellen?
, Samenvatting
kunstmatige Intelligent
Er zijn twee invalshoeken:
1. Vanuit een meer filosofische of psychologische richting: wat is het verschil tussen een
mens en een computer? Kan een computer denken?
2. Vanuit een meer technische richting: Hoe werkt een schaakprogramma? Hoe werkt een
marsrobot?
KI laat computers zich zo gedragen dat het intelligent zou heten als mensen het op die manier
zouden doen.
We delen de definities voor KI op in vier categorieën:
succes afmeten aan de mens succes afmeten aan ideaal beeld
Redeneren Systemen die denken als mensen Systemen die redelijk denken
Gedrag Systemen die handelen als mensen Systemen die redelijk handelen
Links-onder valt onder de Turing-test: als een computer voor een menselijke ondervrager niet
te onderscheiden is van een mens. Hiervoor is het noodzakelijk dat die computer het volgende
kan:
• Verwerking van natuurlijk taal.
• Kennis-representatie: opslaan wat het weet of hoort.
• Geautomatiseerd redeneren: vragen beantworden aan de hand van opgeslagen informatie
en het trekken van conclusies.
• Machine learning.
2 Agenten
Een agent is iets wat zijn/haar omgeving waarneemt met behulp van sensoren en op deze
omgeving werkt met actuatoren. De waarnemingen die een agent gedaan heeft vormen zijn
percept sequence. De actie die een agent kiest kan afhangen van die gehele reeks, maar
niet van iets wat hij niet heeft waargenomen. Het gedrag van de agent wordt omgeschreven
door de agent function die waarnemingsreeksen aan acties koppelt. Deze agent functie wordt
geimplementeerd door een agent program.
Een rational agent is een agent die het juiste doet. Voor elke mogelijke waarnemingsreeks
selecteert ie de actie waarvan verwacht wordt dat deze de performance measure maximali-
seert op basis van die reeks en alle ingebouwde voorkennis die de agent bezit. De performance
maat definieert de mate van succes. De ideale koppeling van waarnemingsreeksen aan acties
specificeert welke actie de agent zou moeten nemen, gegeven een waarnemingsreeks. Dit levert
een ideale agent op.
Een agent is autonoom als zijn gedrag bepaald wordt door zijn eigen ervaring. Hij vertoont
dan doorgaans lerend gedrag om zo te compenseren voor ontbrekende of foutieve voorkennis.
, Samenvatting
kunstmatige Intelligent
Als er geen aandacht is voor waarnemingen is er geen sprake van autonomie.
Als we een rationele agent willen ontwerpen moeten we de task-environment specificeren.
We noemen deze ook wel PEAS:
• Performance maat
• Environment
• Actuatoren
• Sensoren
Er zijn verschillende dimensies waarlangs je omgevingen kunt leggen:
1. Fully Observable vs. partially observable
Een omgeving is volledig observeerbaar als de agent door middel van zijn sensoren op
elk moment de gehele toestand van de omgeving kan bekijken. Een omgeving is deels
observeerbaar als niet alle relevante aspecten uit de omgeving kunnen worden opgenomen.
Wanneer een agent helemaal geen sensoren heeft is de omgeving unobservable.
2. Single agent vs. multi agent
De definities spreken voor zichzelf, maar wanneer spreken we van een tweede agent in
plaats van een object in een multi-agent situatie. Dit hangt ervan af of die agent een
prestatie maatstaf maximaliseert wiens waarde afhankelijk is van de andere agent in de
situatie. We spreken van een competitive multi-agent omgeving als het maximaliseren
van de prestatie maatstaf van de ene agent leidt tot het minimaliseren van de maatstaf
van de andere agent. We spreken van een cooperative multi-agent omgeving als het
maximaliseren van de prestatie maatstaf van een agent leidt tot het maximaliseren van
de prestatie maatstaven van alle agenten.
3. Deterministic vs. Stochastic
Als de volgende toestand van de omgeving volledig bepaald wordt door de huidige toe-
stand en de actie die de agent uitvoert, dan is de omgeving deterministisch. In alle andere
gevallen is de omgeving stochastisch.
4. Episodic vs. sequential
In een episodische omgeving ontvangt de agent in elke episode een waarnemingsreeks en
voert vervolgens een actie uit. De volgende episode is onafhankelijk van deze actie. In
sequentiele omgevingen kan de huidige toestand of actie wel degelijk alle toekomstige
beslissingen beı̈nvloeden.
5. Static vs. dynamic
Als een omgeving kan veranderen terwijl een agent nadenkt over zijn actie dan zeggen
we dat de omgeving dynamisch is voor die agent. In alle andere gevallen is de omgeving
statisch. Als de omgeving zelf niet veranderd met het verstrijken van de tijd maar de
prestatie score van de agent wel, dan is de omgeving semidynamic.
6. Discrete vs. continuous
Deze onderscheiding slaat op de toestand van de omgeving. Als een omgeving continuous
is veranderen de eigenschappen van een toestand voortdurend van waarden binnen een
toestand. Als een omgeving discrete is zijn de waarden van de eigenschappen van die
toestand gedurende de hele toestand gelijk.
, Samenvatting
kunstmatige Intelligent
7. Known vs. unknown
Dit onderscheidt slaat op de kennis die een agent heeft over de fysica wetten van de
omgeving. In een known omgeving zijn de uitkomsten voor alle acties bekend. Als een
omgeving unknown is moet de agent eerst leren hoe die werkt om goede keuzes te maken.
We onderscheiden vier basis agentprogramma’s:
Simple reflex agent: dit is het eenvoudigste type agent. Deze agent selecteert acties
op basis van de huidige waarnemingsreeks. In sommige situaties triggert een conditie een
connectie in het agentprogramma met een bepaalde actie. We noemen zo’n connectie een
condition-action rule: if [condition] then [action].
Model-based reflex agents: De meest effectieve manier om met een partially obser-
vable omgeving om te gaan is de agent het deel van de omgeving dat ie niet kan zien
bij te laten houden. Oftewel, de agent moet een soort internal state bijhouden die
afhankelijk is van de waarnemingsgeschiedenis en daarmee ten minste een deel van de
onobserveerbare aspecten van de huidige toestand reflecteert. Een model van de omge-
ving bestaat uit twee soorten kennis, namelijk informatie over hoe de omgeving evolueert
onafhankelijk van de agent. En de informatie over hoe de acties van de agent de wereld
beı̈nvloeden. Een agent die gebruik maakt van zo’n model noemen we een model-based
agent.
Goal-based agents: Kennis over de huidige toestand van de omgeving is niet altijd
voldoende voor het maken van een keuze. Soms heeft een agent ook goal informatie
nodig die omschrijft welke situaties wenselijk zijn.
, Samenvatting
kunstmatige Intelligent
, Samenvatting
kunstmatige Intelligent
Utility-based agents: Goals alleen zijn vaak nog niet genoeg om gedrag van hoge
kwaliteit te genereren voor de meeste omgevingen. We gebruiken de term utility om aan
te duiden hoe wenselijk of onwenselijk bepaalde toestanden precies zijn. We noemen dit
ook wel nut-gebaseerd. Een agents utility function verwerkt de prestatie maatstaf in
het programma.
Learning agents: Een lerende agent kan opgedeeld worden in 4 conceptuele componen-
ten:
• Learning element: verantwoordelijk voor het maken van verbeteringen. Gebruikt
de feedback van de critic en bepaalt hoe de prestatie maatstaf moet worden aange-
past voor betere prestaties in de toekomst.
• Performance element: verantwoordelijk voor de selectie van externe acties.
• Critic: geeft feedback over hoe de agent het doet.
• Problem generator: verantwoordelijk voor het voorstellen van acties die leiden
tot nieuwe en informatieve ervaringen. Deze zorgt als het ware voor exploratie en
exploitatie.
Het Belief-Desire-Intention (BDI) model is een schema om praktisch redeneren te kunnen
begrijpen en analyseren. De software kant van het model bestuurt en programmeert agenten.
Het model probeert het selecteren van plannen te scheiden van het uitvoeren daarvan, maar
creëert zelf geen plannen. Een BDI-agent heeft:
, Samenvatting
kunstmatige Intelligent
• Beliefs: wat gelooft de agent over zichzelf en de wereld?
• Desires: wat wil de agent? Een doel(goal) is een verlangen(desire) dat de agent actief
najaagt, consistent met andere doelen.
• Intentions: wat heeft de agent gekozen? De agent besluit voor één of meer plannen/ac-
ties.
Je kunt op verschillende niveau’s naar componenten van agenten kijken:
• Atomair: geen interne structuur in de toestanden. Bijvoorbeeld bij zoeken in grafen of
spel(l)en.
• Opgedeeld = factored: toestanden worden bepaald door variabelen met hun waarden.
Bijvoorbeeld bij CSP’s, propositielogica en Bayesiaanse netwerken.
• Gestructureerd: zaken zijn met elkaar gerelateerd. Bijvoorbeeld eerste-orde logica en
natuurlijke taal.
3 Logisch redenerende agenten
Een knowledge base (KB) is een verzameling zinnen in een formele taal en is domein-
specifiek. Een inference engine gebruikt logisch goed-gefundeerde algoritmen om met be-
hulp van de KB vragen te beantwoorden. In de declaratieve aanpak vertel (”Tell”) je zinnen
aan de KB en vraag (”Ask”) je queries. Bij de procedurele aanpak vertaal je gewenst gedrag
rechtstreeks in programma-code.
Je kunt op verschillende niveau’s naar knowledge based agent kijken:
Knowledge(kennis) niveau
Logisch niveau
Implementatie niveau
Een eenvoudige kennis-gebaseerde agent zet als volgt een waarneming om in een actie met
knowledge base KB en tijd t(initieel 0).
function KBagent(percept){
Tell(KB, MakePerceptSequence(percept, t));
actie = Ask(KB, MakeActionQuery(t));
Tell(KB, MakeActionSequence(actie, t));
t = t + 1;
return actie;
}
De KB kan aan het begin achtergrondkennis bevatten. Een eenvoudige logica is de propositie-
logica:
, Samenvatting
kunstmatige Intelligent
Syntax
• Sentence → AtomicSentence|ComplexSentence
• AtomicSentence → T rue|F alse|P |Q|R|..
• ComplexSentence → (Sentence)|Sentence Connective Sentence|¬Sentence
• Connective → ∧| ∨ | =⇒ | ⇐⇒
Semantiek: de bekende waarheidstafels voor ¬P, P ∧ Q, P ∨ Q, P =⇒ Q en P ⇐⇒ Q
Inferentieregels: regels zoals
α =⇒ β, α
modus ponens
β
α ∨ β, ¬β
unit resolutie
α
en AND-eliminatie, AND-introductie, OR-introductie, dubbelle ontkenning en re-
solutie.
De stappen uit de inferentie vormen een bewijs. Als je ware beweringen afleidt is de inferentie
sound. Als je alle ware beweringen kunt afleiden is de inferentie compleet. Het gebruik van
eenvoudige propositie logica levert een aantal problemen op:
∗ Je krijgt veel te veel proposities.
∗ Er zijn problemen met het gebruik van tijd.
Om deze redenen gaan we nu naar eerste orde logica met objecten en relaties kijken:
Syntax
• Sentence → AtomicSentence|¬Sentence|Sentence Connective Sentence|(Sentence)
|Quantif ier variable, ...Sentence
• AtomicSentence → P redicate(T erm, ...)|T erm = T erm
• T erm → F unction(T erm, ...)|Constant|V ariable
• Quantif ier → ∀|∃
• Connective → ∧| ∨ | =⇒ | ⇐⇒
• Constant → A|X1 |John
• V ariable → a|x|s|...
• P redicate → Bef ore|HasColor|...
• F unction → M other|Lef tLegOf |...
Doorgaans gebruiken we eerste orde logica in een geschikt, beperkt domein. Je krijgt
dan regels als:
• Axioma: ∀m, c M other(m, c) ⇐⇒ F emale(m) ∧ P arent(m, c)
• Stelling: ∀x, y Sibbling(x, y) ⇐⇒ Sibbling(y, x)
Andere soorten regels:
, Samenvatting
kunstmatige Intelligent
• Synchrone regels: alles tot nu toe gezien.
• Diachrone regels: redeneren met tijd erbij.
∀x, y a, b Adjacent((x, y), (a, b)) ⇐⇒ (a, b) ∈ {(x+1, y), (x−1, y), (x, y +1), (x, y −
1)}
∀s, t At(agent, s, t) ∧ Breeze(t) =⇒ Breezy(s)
Met coördinaten x, y, a, b, vakje s en tijd t.
• Diagnostische regels: deze leiden van waargenomen effecten naar verborgen oor-
zaken.
∀sBreezy(s) =⇒ ∃rAdjacent(r, s) ∧ P it(r)
• Causale regels: leiden van oorzaken naar effecten.
∀rP it(r) =⇒ [∀sAdjacent(r, s) =⇒ Breezy(s)]
Systemen die redeneren met causale regels heten wel model-based reasoning
systemen.
Er zijn ook hogere orde logica’s waarin je bijvoorbeeld over functies kunt quantificeren/re-
deneren:
∀f, g(f = g) ⇐⇒ (∀x f (x) = g(x))
De speciale quantifier ∃!: ∃!xKing(x) is equivalent met ∃xKing(x) ∧ ∀y(King(y) =⇒ x = y).
En λ-calculus: een λ-expressie als λx, y, x2 − y 2 werkt als volgt: (x, y, x2 − y 2 )(25, 24) =
252 − 242 = 49
Prolog is, in tegenstelling tot een procedurele/imperatieve taal zoals C++, een declaratieve
taal:
koe(klara)
dier(X) :- koe(X)
Nu kun je vragen:
?- dier(klara).
true.
Het antwoord wordt gegeven door logische afleidingsregels los te laten op de database met
feiten en regels.
Situaties zijn de beginsituatie en dat wat je krijgt als je een actie op een situatie los laat.
De benadering die probeert veranderingen bij te houden heet situation calculus. Bepaalde
eigenschappen zijn niet afhankelijk van de tijd en zijn eeuwig of atemporeel.
Effect-axioma’s: beschrijven veranderingen ten gevolge van acties (met situatie s).
∀sAtGold(s) =⇒ Holding(Gold, Result(Grab, s))
Frame-axioma’s: beschrijven wat onveranderd blijft tijdens acties (met voorwerpen x en
acties a).
, Samenvatting
kunstmatige Intelligent
∀a x, sHolding(x, s) ∧ a 6= Release =⇒ Holding(x, Result(a, s))
Successor-state axioma’s: deze laat effect- en frame-axioma samen komen.
∀a, sHolding(Gold, Result(a, s)) ⇐⇒ ((a = Grab ∧ AtGold(s)) ∨ (Holding(Gold, s) ∧ a 6=
Release))
Dit lost het zogeheten representational frame problem (te veel dingen waar een actie
niets mee doet) op.
4 Probleemoplossen en Zoeken
Een probleemoplossende agent zoekt zijn weg naar een doel en gebruikt daarbij de toege-
stane acties. In dit hoofdstuk gaan we uit van een statische, volledig observeerbare, discrete,
deterministische, single-agent probleemomgeving. Een probleem heeft een toestand-actie-
ruimte. Daarnaast heeft elk goed geformuleerd probleem:
• één of meer begintoestanden(initial states).
• een goal test, een test of het doel bereikt is.
• de toegestane acties, per toestand x geeft de opvolger functie S(x) een verzameling paren
van het type < actie, opvolger >, waarbij actie van x naar opvolger leidt.
• een padkosten functie g die kosten aan paden toekent. We nemen aan dat de kosten van
een pad de som van de kosten van de individuele acties langs een pad zijn. De stapkosten
voor een actie a in toestand x die ons naar toestand y brengt worden dan gegeven door
c(x, a, y) ≥ 0.
Soorten problemen:
Single-state: de agent weet alles. De agent weet precies in welke toestand hij is en
de acties hebben eenduidige resultaten. De situatie is dan deterministisch en volledig
observeerbaar.
Multiple-state: de agent heeft beperkte kennis van de wereld. De situatie is wel de-
terministisch, maar niet volledig observeerbaar. We noemen dit ook wel sensorloos of
conformant. Je hebt dan tevens belief toestanden, dit zijn verzamelingen toestanden,
waarbij je alleen maar weet in welke verzameling je zit.
In beide bovenstaande gevallen zijn rijtjes de oplossing.
Contingency: er is sprake van onzekerheid, opletten bij executie. Het probleem is niet-
deterministisch en/of gedeeltelijk observeerbaar. Als deze onzekerheid wordt veroorzaakt
door de acties van een andere agent dan spreken we van adversarial.
Bij dit type probleem is de oplossing een boom of policy.
Exploration: dit zijn experimenten. In dit geval is de toestandsruimte onbekend.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper Stuvian95. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €6,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 52355 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen