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.
Solution Manual for Artificial Intelligence A Modern Approach 3rd Edition / All Chapters Full Complete 2023 - 2024
All for this textbook (1)
Written for
Universiteit Leiden (UL)
Informatica
Kunstmatige Intelligentie
All documents for this subject (1)
3
reviews
By: timothyvanexel • 4 year ago
By: joycevredegoor • 5 year ago
By: bekirdemir10 • 6 year ago
Seller
Follow
Stuvian95
Reviews received
Content preview
Samenvatting
kunstmatige 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:
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).
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Stuvian95. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $6.96. You're not tied to anything after your purchase.
