---
tags: HoGent, AI
---

# Artificiële Intelligentie

[](https://i.imgur.com/8q8amV5.png)

## Rationale Agenten
### Definities van Artificiële Intelligentie
/
### Rationale Agenten

`Agent`: entiteit die omgeving kan waarnemen adhv sensoren en invloed kan uitoefenen door actoren.
- krijgt per tijdseenheid een waarnameing met als gevolg een `waarnemingssequentie`
- `waarn.seq.` --- `agentfuntie` --- > acties
- heeft `performantiemaat`:
- NIET beloond voor acties maar voor gevolgen van de acties
- "score"

`Rationale agent`: maximaliseert de `performantiemaat`, rekening houdend met `waarn.seq.` en de evt. ingebouwde kennis van de agent.

:warning: rationaliteit $\neq$ helderziendheid.

### Eigenschappen van Omgevingen


- De meest eenvoudige omgevingen: steeds de bovenste eig,
- De meest realistische omgevingen vaak de onderste eig.

### Structuur van Agenten
4 types agenten gesorteerd op complexiteit:
1. `Eenvoudig reflex`
- GEEN geheugen: alles episodisch bepaald.
- kan dus niet rationaal zijn in een partieel observeerbare wereld
- IF-THEN
- Problemen bij sequentiele en partieel observeerbare omgevingen
1. `Modelgebaseerd reflex`
- maakt eerst een **inschatting** van de situatie.
- beschikt over een model van hoe de omgeving verandert of zal veranderen door acties
- daarna als-dan
- heeft geen voordeel over de eenvoudige reflex agent in compleet observeerbare omgeving!
3. `Doelgebaseerd`
- Naast een model is ook een beschrijving van het doel belangrijk.
5. `Utiliteitsgebaseerd`
- zoals doelgebaseerd maar gebruikt `utiliteitsfunctie` om aan te geven hoe geschikt een toestand is
- $\approx$ de performantiemaat

---

## Zoekalgoritmes

> samengevat
> 

### Inleiding

Een `zoekprobleem` heeft volgende elementen:
- `toestandsruimte` $S$
- de `initiële toestand` $s_0$
- verzameling acties $A$
- `transitiemodel` $T : (S,A) \rightarrow S : (s,a) \mapsto s'$
- $s'$ is de `opvolger` van $s$.
- $T$ vertelt wat het effect is van de actie op de toestand.
- er is een `kost` mee geassocieerd: kostfunctie $c(s,a,s')$
- Een `doeltest` die checkt of de `doeltoestand` is bereikt (booleaans)

De `toestandsruimtegraaf` (state space graph) kan worden opgesteld met $S$, $T$ en $c$.
- De knopen zijn de toestanden $s$
- De knopen zijn GERICHT verbonden $s\rightarrow s'$ (dmv $T$)
- De gewichten zijn bepaald door $c$

De oplossing van eeen zoekprobleem:
- is de sequentie van acties om de doeltoestand te bereiken

De kost van een zoekprobleem:
- is de som van de kosten van de acties

De `optimale oplossing` ve zoekprobleem:
- oplossing met minimale kost

### Algemene Zoekalgoritmen
#### Boomgebaseerd Zoeken

De `open lijst`:
- bevat de leafs van de zoekboom = partiele oplossingen = `plannen`
- bevat initieel enkel $s_0$

We expanderen steeds 1 van de plannen door er de mogelijke acties op uit te voeren. Elk plan slaat volgende data op:

Plan{
    - huidigeToestand : Toestand
    - laatstGekozenActie : Actie
    - voorganger : Plan
    - totaleKost : int
}

(De totale kost wordt met $g$ genoteerd)

- Met deze implementatie moeten we enkel de leafs opslaan en niet heel de boom.
- $g$ zou recursief berekend kunnen worden in $O(n)$, maar deze bijhouden is handiger.


#### Criteria voor Zoekalgoritmen

1. COMPLEET
- vindt altijd een oplossing
3. OPTIMAAL
- vindt altijd optimale oplossing
5. TIJDSCOMPLEXITEIT
- uitvoeringstijd
7. RUIMTECOMPLEXITEIT
- benodigd geheugen

maten:
- `vertakkingsfactor` $b$
- maximaal aantal opvolgers van een top
- diepte van de ondiepste top die ook doeltop is $d$
- = minimale diepte voor een oplossing
- maximale lengte van een pad $m$
- = maximale diepte voor een oplossing

Aantal toppen in een zoekboom met vertakkingsfactor $b$ en max.depth. $m$
$$
\text{#toppen} = 1+b+b^2 +\ldots + b^m = \sum_{i=0}^mb = \frac{b^{m+1}-1}{b-1}
$$

dit is dus van grootteorde $\mathcal{O}(b^m)$

:warning: het grote probleem is dat het algoritme niet onthoudt waar het al is geweest, dit is sub-optimaal en kan leiden tot infinite loops.

#### Graafgebaseerd Zoeken
Analoog aan boomgebaseerd, maar met `gesloten lijst`. Deze bevat nu geen plannen maar wel effectief de toestanden!!

Het algo checkt of een toestant al eerder werd geexpandeerd. Dit fixt de problemen met boomgebaseerd.


### Blinde Zoekmethoden
#### Breedte Eerst Zoeken
- met een FIFO: `queue`
- bouwt alle lagen van de zoekboom op
- kan stoppen bij meest ondiepe oplossing!
- dit is een **COMPLEET** algoritme
- geeft oplossing met min aantal acties
- Het is **niet optimaal**
- want kleinste aantal acties $\neq$ kleinste kost
- wel optimaal als alle kosten gelijk!

Tijdscomplexiteit: $\mathcal{O}(b^{d+1})$
Ruimtecomplexiteit: idem

#### Diepte Eerst Zoeken
- met een LIFO: `stack`
- niet ideaal want gaat eerst de langste oplossingen af
- kan in infinite loop gaan
- **niet compleet**
- **niet optimaal**

tijdscomplexiteit in worst case: $\mathcal{O}(b^m)$
ruimtecomplexiteit: $\mathcal{O}(b\cdot m)$ <-- dit is lineair! :thumbsup:

In graafgebaseerd uitvoeren tegen de infinite loops? Dan verliest men het voordeel van de lage ruimtecomplexiteit...

#### Iteratief Verdiepen
gebruikt **`DIEPTE GELIMITEERD ZOEKEN`**


- lus rond diepte gelimiteerd zoeken
- steeds diepte verhogen tot doeloplossing wordt gevonden
- combineert **diepte eerst** met een soort breedte-eerst-lagen
- algoritme moet steeds opnieuw beginnen
- maar dat maakt niet zoveel uit
- zie hieronder:

Als oplossing op diepte $d$, en we doen iteratief verdiepen, hoeveel werk hebben we dan teveel gedaan?
- we hebben moeten diepte gebaseerd zoeken op dieptes 1 tot d-1 zonder resultaat
- hoeveel toppen zijn dit?
- $1 + (1+b) + (1+b+b^2) + \ldots + (1+b+b^2+\ldots + b^{d-1})...$

Aantal toppen gegenereerd bij enkele iteratie met diepte $i$
$N(i) = 1+b+b^2+\ldots + b^i$ dus:

$$
N(i)= \frac{b^{i+1} -1}{b-1}
$$

Totale aantal toppen van elke iteratie zonder oplossing

$$
\sum_{i=0}^{d-1} N(i) = \ldots \approx \frac{1}{b-1} N(d)\quad \overset{!}{<} N(d)
$$

> 

#### Uniforme Kost Zoeken

= breedte eerst met prioriteits-queue gebaseerd op kost!
= *Cheapest First Search* of *Best First Search*
$\approx$ Dijkstra, maar dan met een doeltop!

kies altijd pad met kleinste **totale** kost om te expanderen.

{%youtube dRMvK76xQJI %}

Tijd en ruimtecomplexiteit is $\mathcal{O}(b^{1+\lfloor C^* /\varepsilon\rfloor})$ met elke kost $\geq \varepsilon$ en $C^*$ de kost van de optimale oplossing.

### Geïnformeerde Zoekmethoden
> $\leftrightarrow$ blinde zoekmethoden

#### Heuristieken
Indicator van de totale kost naar het doel.

$h(s) \in \mathbb{R}^+$ met $s$ een toestand.

- Een `toelaatbare` heuristiek overschat NOOIT; dus
$$h(s) \leq C^*(s)$$

met $C^*(s)$ optimale kost van $s$ naar doeltoestand.
Het is duidelijk dat de heuristiek van de doeltoestand dus nul is. $h(g) = 0$

- Een `consistente` heuristiek heeft deze eig ($h(g) = 0$) EN er geldt dat de heuristiek voor een rechtstreeks pad altijd kleiner is dan voor een "omweg", nl.
$$h(s) \leq c(s,a,s') + h(s')
$$
Waarbij de "omweg" node $s'$ is en de kost van de omweg $c(s,a,s')$

Hier is duidelijk te zien `consistent` $\Rightarrow$ `toelaatbaar`. Maar niet omgekeerd.
Bewijs ook te zien op p.42 vd cursus. :bookmark:

#### Gulzig Beste Eerst

- Evaluatiefunctie: $f(n)= h(n)$
- Expandeert steeds de node met de *laagste heuristiek*.
- Gebruikt geen effectieve kosten.
- Is **niet optimaal** en **niet compleet**
- $TC$ = $SC$ = in slechtste geval $\mathcal{O}(b^m)$ dus exponentieel :thumbsdown:

Geen goed algoritme imo.

#### A ∗ Zoekalgoritme

- Evaluatiefunctie: $f(n)= h(n) + g(n)$
- Expandeert steeds de node met de *laagste \[heuristiek + voorlopige totale kost*\].
- is **compleet** en **optimaal** bij volgende voorwaarden:
1. boomgebaseerd
- minstens toelaatbare heuristiek (zie bewijs p50) :bookmark:
- kosten > 0
2. graafgebaseerd
- minstens consistente heuristiek :warning:
- kosten > 0
- $TC$ = $SC$ = in slechtste geval nog steeds exponentieel, en gebruikt meer geheugen dan greedy BFS. :thumbsdown:

### Ontwerpen van Heuristieken
#### Gebruik van Vereenvoudigde Problemen
= restricties weghalen, vogelvlucht of manhattan distance gebruiken, ......

#### Patroon Databanken
dit kan een ondergrens bieden voor de heuristiek. Meerder patronen combineren en het maximum nemen geeft nog betere ondergrens.

---

## Zoeken met een Tegenstander
### Inleiding
we beschouwen omgeving:
- competitief multipersoons
- compleet observeerbaar
- discreet
- deterministisch

##### 2p-zero-sum-game
Veel zelfde elementen als een zoekprobleem:
- toestandsverzameling $S$
- actieverzameling $A$
- transitiemodel $T(s,a)$ met opvolger $s'$
- initiële toestand $s_0$
En ook nog deze:
- `EINDTEST`: booleanse test: spel gedaan of niet gedaan
- de toestanden waarvoor deze true is zijn `eindtoestanden`
- `opbrengstfunctie`$U$. Hierbij geldt dat de som van $U(s)$ voor alle spelers in de eindtoestand $s$ een constante is! (dus eigenlijk constant-sum-game): $U_{Min}(s) + U_{Max}(s) = C$

### Spelbomen en het Minimax Algoritme

"Max" vs "Min". We noemen de opbrengstfunctie voor Max ($U_{Max}$) gewoon $U$
Max wil $U$ voor zichzelf maximaliseren, Min wil deze minimaliseren.

De `minimax waarde` is recursief:

$$
\text{minimax}(s) = \begin{cases}
U(s) & \text{als } s \text{ een eindtoestand}\\
\max_{a\in A} \text{minimax}(s')&\text{als Max aan zet in toestand } s\\
\min_{a\in A} \text{minimax}(s')&\text{als Min aan zet in toestand } s
\end{cases}
$$

Dit steeds met $s'= T(s,a)$, de opvolger van $s$ via transitiemodel $T$.

**Diepte-eerst** algoritme.

- $SC = \mathcal{O}(b\cdot m) \rightarrow$ lineair:thumbsup:
- diepte eerst, maar dan waarde opgeslagen per diepe vertakking
- $TC = \mathcal{O}(b^ m) \rightarrow$ exponentieel :thumbsdown:
- want genereert wel alle toppen


### Snoeien van Spelbomen
{%youtube zp3VMe0Jpf8 %}

Snoeien: het niet evalueren van een tak ondat deze de eindoplossing niet beïnvloedt.
=> de kinderen van die tak snoeien.

[andere video](https://www.youtube.com/watch?v=hM2EAvMkhtk)
Interesting:
- waarom snoeien? Kost dit niet meer tijd dan gewoon minima en maxima berekenen?
- antwoord 1: een cijfer berekenen voor een eindtoestand betekent vaak veel berekenwerk ( bvb schaken: alle posities, alle mogelijke manieren van schaak, ...)
- er kunnen immens veel eindtoestanden zijn


##### Ordening
Kan groot effect hebben op efficiëntie van snoeien!
Maat voor hoe goed de ordening is: de `effectieve vertakkingsfactor` = $b_e$
- een boom met hetzelfde aantal toppen $N$ en zelfde diepte $m$ kan worden gemaakt, maar dan met constante vertakkingsfactor.

dus $N = ( b_e^{m+1} -1 ) / ( b_e -1)$
Een benadering wordt gegeven door:

$$
be\approx N^{1/m} = \sqrt[m]{N}
$$

### Praktische Uitwerking

Voor schaken, dammen, Go.... veeeel te veel toestanden.
- opslaan met minimax waarde in `transpositietabel` is onrealistisch

We hebben een `heuristische evaluatiefunctie` nodig!
- dieptelimiet voor minimax, wanneer diepte bereikt heuristiek gebruiken
- maximale diepte is $d$

$$
\text{h-minimax}(s, d) = \begin{cases}
\text{EVAL}(s) & \text{als } s \text{ een eindtoestand of }d=0\\
\max_{a\in A} \text{h-minimax}(s',d -1)&\text{als Max aan zet in toestand } s\\
\min_{a\in A} \text{h-minimax}(s',d-1)&\text{als Min aan zet in toestand } s
\end{cases}
$$

Dit steeds met $s'= T(s,a)$, de opvolger van $s$ via transitiemodel $T$.

De kwaliteit van de heuristische "EVAL" functie is belangrijk.
1. moet de eindtoestanden op zelfde manier ordenen als opbrengstftie $U$
2. moet snel kunen berekend worden
3. waarde moet sterk gecorreleerd zijn met effectieve winstkansen

De eval functie is een lineaire combinatie van spelfeatures.

## Lokaal Zoeken en Genetische Algoritmen

### Lokale Zoekmethoden

Lokaal zoeken
- houdt zich niet bezig met bijhouden van actiesequentie
- gebruikt beperkt geheugen
- goede oplossingen in grote S-ruimten
- wil gewoon de oplossing
- meestal `optimalisatieproblemen`
- doelfunctie max of minimaliseren (analoog aan LP)

#### Hill Climbing
- neem steeds de beste opvolger als deze beter is dan jezelf
- gulzig algoritme
- bekijkt in-the-moment wat het beste is
- kan vastlopen
- in lokaal maximum zonder globaal maximum te bereiken!
- in plateau
- we kunnen zijwaartste stappen toelaten met een aantal-beperking
- is **niet compleet**
- kan worden verbeterd door random herstarten
- theoretisch wordt het dan compleet
- in praktijk duurt dit te lang


#### Simulated Annealing

Hill climbing: wandelt enkel naar boven en raakt vast in lokaal max
Random walk: zou te lang duren

Combinatie:
- als oplossing beter is, aanvaard hem (zoals hill climb, `exploit`)
- als oplossing niet beter is, aanvaard hem misschien (zoals random walk, `explore`)
- gebaseerd op temperatuur ($T\propto 1/t$ met $t$ de verstreken tijd)
- gebaseerd op de kwaliteit van de opvolger ($\Delta E$, groot als goeie move, klein als slechte move )

Het al dan niet aanvaarde van een slechtere oplossing, hangt in het algo af van de waarschijnlijkheid:
$$p_{\text{aanvaarding}} = e^{\frac{\Delta E}{T}}
$$

vereenvoudigd algo (niet volledig, zi p 87 :bookmark:)

for dalende T: #of voor stijgende tijd en dan T berekenen
    if T == 0 return current               #stop als temp nul is
    next = current.getRandomSuccessor()
    delta_E = h(next) - h(current)         #hoe goed is de move?         
    if delta_E > 0:                        #beter dan wat we hadden
        current = next                     #aanvaard
    else if exp(delta_E / T) > rand(0,1) : #slechter, maar waarsch. beter dan random
        current = next                     #aanvaard

#### Gradient Descent

Toestandsruimte continu, afleidbaar en n-dimensionaal.

$$ \vec{x}' = \vec{x} - \alpha \nabla f(\vec x)
$$

En dus, als het om 2 variabelen $x_1$ en $x_2$ gaat:

$$ (x_1',\, x_2') = \left( \,
x_1 - \alpha\frac{\partial f}{\partial x_1}\quad,\quad
x_2 - \alpha\frac{\partial f}{\partial x_2}\,
\right)
$$

Met $\alpha$ de stapgrootte. Bij elke stap zal $x$ dus dichter bij een lokaal minimum geraken, door de sterkste daling te volgen.

De stapgrootte is belangrijk:
- niet te klein want dan te traag
- niet te groot want dan kans op inf. loop

### Genetische Algoritmen


- klassieke algo's houden hele open lijst bij
- lokale houden enkel huidige toestand bij
We zoeken een compromis => vast aantal toestanden bijhouden.

Genetische algoritmen:
- maximaliseert doelfunctie $h$
- $\leftrightarrow$ lokale: geen notie van opvolgers vereist.
- werken iteratief
- 
- wordt uitgevoerd tot voldoende tijd verstreken of voldoende goeie oplossing

#### Populatie en Encodering

Zoals eerder gezegd: houdt `populatie` bij van vast aantal individuen.
Elk individu `encodeert` een toestand: bij elke toestand een string assosiëren!

#### Fitnessfunctie en Selectiemechanisme
fitness functie $f$ bepaalt hoe goed een volgende generatie is (hoger is beter).
`selectiemechanisme`: de kans op selectie stijgt als fitness hoger is (logisch)

implementatievoorbeelden:
1. `roulette wiel selectie`
- stuk van "wiel" evenredig aan de fitness
- kans is dan $f_i / \sum f$ = `fitness ratio`
- probleem: superfit individu heeft té veel kans
- algo convergeert te snel
- blijft snel steken in "lokale maxima"
2. `ranggebaseerde selectie`
- individuen sorteren STIJGENDE fitness en rangnummer geven
- de eerste is de slechtste, de laatste de beste
- de kans op selectie is dan rangnummer / som van rangnummers
- $p= i / \sum j = \frac{2i}{n(n+1)}$
- enkel relatieve fitness doet ertoe, dus uitschieters domineren minder :thumbsup:

#### Recombinatie en Mutatie

recombinatie:
- genetisch materiaal van 2 individuen gebruiken voor 2 nieuwe afstammelingen
- #individuen blijft constant!
1. `éénpunts crossover`
- op een bepaalde plaats van de string een merge maken
- (bv bij 4letter string: eerste 2 van parent 1 en laatste 2 van parent 2)
- niet nuttig bij bvb trav.salesm.pr. wantdoor random crossoverpunt niet zeker dat alle steden erin staan
2. `geordende crossover`
- 2 random punten kiezen
- daartussen ongewijzigd
- daarbuiten:
- maak lijst van opties die nog niet aan bod komen
- in volgerde van ANDERE parent na 2e punt
- begin in te vullen na 2e punt
- vul verder aan na eerste punt
- bvb
||1|2|
|--|--|--|
| **parents** | `CAGDBEF` | `FBEADCG`|
| **crossoverpunten** | `CA\|GD\|BEF` | `FB\|EA\|DCG` |
| **kinderen** stap 1 | `xx\|GD\|xxx` | `xx\|EA\|xxx` |
|**nog niet gebruikt**|~~`D`~~,**`C`**,~~G~~,**`F`**,**`B`**,**`E`**,**`A`**| **`B`**,~~`E`~~,**`F`**,**`C`**,~~`A`~~,**`G`**,**`D`**|
| **kinderen** stap 2 | `xx\|GD\|CFB` | `xx\|EA\|BFC` |
| **kinderen** finaal | `EA\|GD\|CFB` | `GD\|EA\|BFC` |

---

Daarna kan nog `mutatie` optreden.
- dit moet met lage probabiliteit gebeuren
- Zorg wel dat de "regels" gerespecteerd blijven
(bvb bij tsp: wissel 2 steden om ipv random steden te veranderen.)

#### Een Eenvoudige Implementatie
vb
#### Besluit en Toepassingen
Genetische algoritmen:
- niet gegarandeerd optimaal
- kan wel goeie oplossing bekomen
- voorwaarde: goede encodering

---

## Machinaal Leren
### Inleiding
/
### Drie Types van Machinaal Lere
#### Gesuperviseerd Leren

= op basis van een **gelabelde `trainingsdataset`** een `hypothese` functie $h$ opbouwen zodat voor nieuwe invoer het label voorspeld kan worden
- label = getal : `regressie`
- label = klasse : `classificatie` (kan binair)


#### Ongesuperviseerd Leren
= structuur ontdekken in **ongelabelde dataset**
- clustering
- groeperen (maar niet interpreteren) van data
- anomaliedetectie
- abnormaliteiten vinden
- primaire componenten analyse
- data "uitdunnen" en reduceren tot belangrijkste components
#### Reinforcement Learning
$\approx$ Pavlov: belonen voor goeie acties, zo leert algo welk `beleid` leidt tot de grootste beloning (en dus het best is)

### Evaluatie van Hypothesen voor Gesuperviseerd Leren
#### Foutmaten
##### regressie
- `RMSD` (root mean square deviation $\approx$ gemiddelde kwadratische afwijking) $$RMSD^2 = \frac{1}{m} \sum_{i=1}^m \left( h(x^{(i)}) - y^{(i)}\right)$$
simpeler genoteerd: $\frac{1}{m} \sum_m (h(x)-y)$
##### classificatie
- `foutratio` (=percentage fout gelabelden)
$$FR = \frac{1}{m}\cdot \#\{ x^{(i)} \mid h(x^{(i)}) \neq y^{(i)} \}$$

###### Binaire classificatie:
- `precisie` (= correct positief gelabeld / totaal aantal gelabeld positief )
$$P= \frac{\#\text{correct}}{\#\text{correct} + \#\text{vals positief}}$$
- `rappel` = `recall` (= correct positief gelabeld / wat effectief positief is)
$$R= \frac{\#\text{correct}}{\#\text{correct} + \#\text{vals negatief}}$$

Beste classificatie heeft $P = R = 1$
Goede verhouding tussen deze maten: **`F-score`**

$$F = 2\frac{P\cdot R}{P+R} \qquad(\leq 1)
$$

Voor $P$ $R$ en $F$ geldt: hoe groter hoe beter!

#### Trainings-, Validatie- en Testdata

`Testdata` moet volledig los zijn van trainingsdata!
- een hypothese die goed scoort op training maar niet op test = OVERFITTING
- een hypothese is niet algemeen genoeg = ONDERFITTING

`Occams Razor` is van toepassing: when in doubt, choose the easiest model
(mag ook wel niet te eenvoudig zijn voor het probleem...)

`Validatie dataset`: aangezien testdata echt los moet blijven van het trainen:
- set data die gebruikt wordt om meta-parameters te tunen
- foutmaat daalt steeds, tot deze weer stijgt (dan begint overfitting)
- het moment van minimale foutmaat bepaalt de meta-parameters!
- dit is enkel indicatief voor de parameters
- dus dit is NIET de finale foutmaat! Hiervoor hebben we de testdataset!!!

---

## Gesuperviseerd Leren
### Lineaire Regressie
#### Probleemstelling

Hypothese van de vorm $$h_{w,b}(\vec x) \equiv h(\vec x) = \vec w \cdot \vec x + b$$
Dit is dus uitgeschreven $w_1x_1 + w_2x_2+ \ldots + w_nx_n + b$ of dus $\sum_i(w_ix_i )+b$

De kostfunctie die moet geminimaliseerd worden definieren we adhv de RMS:
$$J(w,b) = \frac{1}{2m}\sum_m(h(\vec x) - \vec y)^2
$$

Met $m$ het aantal elementen in de testdataset en de factor 1/2 random maar met een of andere reden.

#### Oplossingsmethode

De kostfunctie $J$ zal steeds maar 1 lokaal = globaal minimum hebben!
We kunnen er dus gradient descent op toepassen!

##### Algoritme voor lineaire regressie
1. kies startwaarden voor $b$ en voor alle $w_i$
2. Kies goede stapgrootte $\alpha$
3. $$w_j' = w_j - \alpha\frac{\partial J}{\partial w_j} \qquad \text{en}\qquad b'= b - \alpha\frac{\partial J}{\partial b}$$
met $$\frac{\partial J}{\partial w_j} = \frac{1}{m} \sum_m (h(x) - y) \cdot x_j \qquad \text{en}\qquad \frac{\partial J}{\partial b} = \frac{\alpha}{m} \sum_m (h(x) - y)
$$
de onderdelen van $\nabla J(w,b)$
4. herhaal stap 3 tot $|\Delta w| \leq \varepsilon$ en $|\Delta b| \leq \varepsilon$ (ze veranderen nog nauwelijks)
- dus $\alpha\frac{\partial J}{\partial b}$ en $\alpha\frac{\partial J}{\partial w_j}$ zeer klein

*--> dit is dus gradient descent op $J$*

##### Efficiënte bepaling van de gradiënt
zie cursus p125-127 :bookmark:

#### Polynomiale Attributen
- om evt polynomisch verband te onderzoeken
- cheat the system door gewoon een extra parameter toe te voegen
- bvb $x_2 := x_1^2$
- pas daarna lin reg toe en kijk of de kostfunctie lager ligt
- profit(?)

#### Regularisatie ter Preventie van Overfitting

extra term toevoegen om te grote waarden te bestraffen.

$$J(w,b) = \frac{1}{2m}\sum_m(h(\vec x) - \vec y)^2 + \color{orange}{\lambda \sum_n w_j^2}
$$

met $\lambda$ een meta parameter. Bepaald met de validatiedataset.

### Logistische Regressie
=> Voor CLASSIFICATIEPROBLEMEN

##### Binaire classificatie
Lineaire regressie met grens 1/2 is geen goed idee
- te gevoelig voor uitschieters
- lin reg kan waarden opleveren anders dan 0 en 1

De `stapfunctie`:
$$ H(z) = \begin{cases} 0&z<0\\1 &z\geq 0\end{cases}
$$

Deze functie is echter **niet continu**
- dus niet gepast voor gradient descent etc.

De `sigmoïde` of `logistische functie`:
$$g(z) = \frac{1}{1+e^{-z}}
$$
met voor de afgeleide geldt, met $g\equiv g(z)$
$$g' = g \cdot (1-g)
$$

Als de hypothese de sigmoïde volgt, dan geeft de hypothese steeds de kans terug dat een label correct is.

#### De Scheidingslijn
kan rechte, ellips, hyperbool, parabool..... zijn.

Door het toevoegen van attributen!

#### De Kostfunctie

De kost moet 0 zijn als juist, en maximaal voor fout.
- nadeel hiervan is dat de kost niet continu is
- niet goed voor gradient descent

We nemen voor de kost een continue functie met als voorwaarden als het label 1 moet zijn:
- $J(0) = 0$
- $J(>1/2)$ stijgt zeer snel, want hier echt wel fout geclassificeerd
- $J(1) = + \infty$

analoog voor als het label 0 moet zijn.

De $\ln(x)$ functie heeft deze karakteristiek. Dus gecombineerd voor $\color{red}{y=0}$ en $\color{green}{y=1}$:
$$ J(w,b) = - \frac{1}{m} \sum_m \ y\cdot \color{green}{ \ln(h(x))} \ + \ (1-y)\cdot \color{red}{\ln(1-h(x))}
$$

Binaire classificatie gebeurt dus als volgt:
1. minimaliseer $J$ met gradient descent en trainingsdata
- bekom zo alle parameters $w_i \in \vec w$ en ook de parameter $b$
3. voor testdata, bereken de hypothese $h_{w,b}(\vec x)$.
- $h \geq \frac{1}{2}$, label dan als 1
- $h < \frac{1}{2}$, label dan als 0

#### Niet-binaire Classificatie
##### 1-vs-allen

Zij $k \in \{1,2,\ldots,K\}$ een klasse; het aantal klassen is dus $K$

- stel $K$ hypothesen op: $h^{(1)} ... h^{(k)}$
- per hypothese geldt:
- klasse $k$ is positief voor hypothese $h^{(k)}$
- de rest van de klassen is negatief
- Kies dan de hypothese $h^{(k)}(x)$ die het meest kans geeft dat een $x$ tot een $k$ , die $k$ wordt het label $y$.

$$y = \arg \max_{k\in \scriptsize{\{1,2,\ldots,K\}}} h^{(k)} (x)
$$
waarbij de $\arg$ functie ervoor zorgt dat het een $k$ is die wordt toegewezen aan $y$ bij maximale $h^{(k)}(x)$

##### 1v1

Zij $k \in \{1,2,\ldots,K\}$ een klasse; het aantal klassen is dus $K$

- stel hypothesen $h^{(k,l)}$ op
- met $l\in \left]\, k,K\,\right]$
- er zijn dus $\frac{1}{2} K(K-1)$ hypothesen
- per hypothese geldt:
- klasse $k$ is positief voor hypothese $h^{(k,l)}$
- klasse $l$ is negatief voor hypothese $h^{(k,l)}$
- overloop alle hypothesen, en tel het aantal "stemmen"
- als $h^{(k,l)} \geq 1/2$ dan is dit stem voor positief dus $k$
- als $h^{(k,l)} \lt 1/2$ is er stem voor negatief dus $l$

### Artificiële Neurale Netwerken
#### Inleiding

- voorwaarts gericht = acyclisch!
- uitvoer is functie van de invoer
- recurrent bevat wel cykels
- feedback loops
- bereikt een van volgende toestanden
- stationair
- oscillatie
- chaos
- uitvoer is functie van invoer **en** vorige invoeren
- $\sim$ "kortetermijngeheugen"
- moeilijker te trainen dus buiten scope van de cursus.

#### Gelaagde Voorwaarts Gerichte Neurale Netwerken

flowchart LR
subgraph sub [verborgen lagen]
B(...) --> C(...)
end
A(Invoerlaag)--> B
C -->D(uitvoerlaag)

Meestal evenveel neuronen in de uitvoerlaag als er klassen zijn.

$$z_i = w_ix + b_i \quad \text{en} \quad a_1 = g(z_1)
$$
met $g$ de implementatie van een `activatiefunctie` (meestal de sigmoide $\frac{1}{1+e^{-z}}$)

Door eigenschappen van het matrixproduct (:bookmark: 150-151) kunnen we veralgemenen:

$$\vec z = \boldsymbol{W}\cdot \vec x + \vec b \quad \text{en} \quad \vec a = g(\vec z)
$$

**`voorwaartse propagatie`** is het laag per laag berekenen van de uiteindelijke uitvoerlaag $L$

$$z^{[l]} = \boldsymbol{W^{[l]}}\cdot \vec a^{[l-1]} + \vec b^{[l]} \quad \text{en} \quad \vec a^{[l]} = g(\vec z^{[l]})
$$
voor $l \in \{1,2 \ldots, L\}$ en $\vec a^{[0]} \equiv \vec x$

#### Vectorisatie

De vorige formule kan in een loop over alle voorbeelden worden uitgevoerd, of we maken een matrix $X$ van alle kolommen $\vec x_i$

Uiteindelijk komen we dan bij:

$$\boldsymbol{Z}^{[l]} = \boldsymbol{W^{[l]}}\cdot \boldsymbol{A}^{[l-1]} + \vec b^{[l]} \quad \text{en} \quad \boldsymbol{A}^{[l]} = g(\boldsymbol{Z}^{[l]})
$$
voor $l \in \{1,2 \ldots, L\}$ en $\vec A^{[0]} \equiv \boldsymbol{X} = (\vec x^{(1)}, \ldots , \vec x^{(m)})$

:warning: de eerste formule bevat wiskundig een "foute" notatie, aangezien je geen kolomvector kan optellen bij een n-dimensionaal matrixproduct. We gaan er echter van uit dat er `broadcasting` is; i.e. kolomgewijs optellen.

#### Trainen van een Neuraal Netwerk

Minimaliseren van een kostfunctie.
We volgen voorbeeld van logistische regressie.

> De labels $y^{(i)}$ zijn gedefinieerd adhv de `one-hot-encoding`: een vector vol nullen die op de $k^{de}$ plaats een 1 heeft als voorbeeld $i$ van de klasse $k$ is.

- de **`cross-entropy kostfunctie`**

Stel $K$ klassen en $m$ trainingsvoorbeelden.
waarbij $h(^{(i)})_k$ de k-de component is van de $h$ vector voor voorbeeld $x^{(i)}$

We kunnen aanpassingsmatrices en -vectoren opstellen:

$$\begin{cases}
dz^{[L]} = a^{[L]} - y & L \text{ is de eindlaag}\\
dz^{[l]} = (W^{[l+1]})^T \, dz^{[l+1]} \, \odot \, g'^{[l]} (z^{[l]}) & l \in \{L-1, \ldots, 1\}\\
dW^{[l]} = dz^{[l]}a^{[l-1]} & "\\
db^{[l]} = dz^{[l]}& "
\end{cases}
$$

met $\odot$ de puntsgewijze vermenigv; en zoals voorheen: $g' = g \cdot (1-g)$

Gradient descent geeft dan:
$$\begin{cases}
W'^{[l]} = W^{[l]} - \alpha dW^{[l]}\\
b'^{[l]} = b^{[l]} - \alpha db^{[l]}
\end{cases}
$$

- **`Stochastische gradient descent`**
- 1 enkel voorbeeld gebruiken om gewichten te tunen
- hoe?
0. initialiseer gewichten op random, kies een $\alpha$, shuffle voorbeelden
> for voorbeeld in voorbeelden
1. bereken actievaties $a^{[l]}$ en $z^{[l]}$ met voorwaartse propagatie ($l \in \{1,2,\ldots, L\}$)
2. Bereken aanpassingsmatrices $dW$ en -vectoren $db$ met achterwaartse propagatie ($l \in \{L, L-1, \ldots, 1\}$)
3. Pas de gewichten aan volgens gradient descent: $$
\begin{cases}
W'^{[l]} = W^{[l]} - \alpha dW^{[l]}\\
b'^{[l]} = b^{[l]} - \alpha db^{[l]}
\end{cases}$$

Stochastische GD voor klein aantal voorbeelden ipv maar 1: `mini-batch gradient descent` (kan door vectorisatie ongeveer even snel)

#### Uitbreidingen en Variatie

##### Andere activatiefuncties:
- `tangens hyperbolicus`
$$
\tanh(x) = \frac{e^z - e^{-z}}{e^z + e^{-z}}
$$

- `Rectified linear unit`
$$
\text{ReLU}(x) = \max(0,z)
$$
- **`Softmax functie`** (vaak gebruikt)
$$
\sigma(\vec z)_i = \frac{e^{z_i}}{\sum_{j=1}^L e^{z_j}}
$$

##### Convolutionele lagen
= CNN (conv. neur. net.)

`convolutie` is operatie die een filter over de invoer plaatst.
- geeft nieuw beeld met 1 kanaal
- gebruikt bvb bij veel voorkomende patronen

---

## Ongesuperviseerd Leren
### Clustering en het K-Gemiddelden Algoritme
**`het K-Gemiddelden Algoritme`**
- voor het vinden van clusters
- invoer is ongelabelde dataset en aantal clusters te vinden $K$
- cluster voorgesteld adhv `zwaartepunt`
- $\mu = \frac{1}{m} \sum_{i=1}^{m} \vec x_i$ aka zoals het "gemiddelde"

stappen:
0. random toewijzen van de $K$ zwaartepunten $\mu^{(k)}$ met $k \in \{1, \ldots ,K\}$
> for toestand $i$ in $m$ toestanden
1. toewijzing
- bereken $\forall x^{(i)}$ tot welke cluster $k$ het hoort
- dus welke afstand tot een zwaartepunt $\mu^{(k)}$ het dichtst is $||x^{(i)}-\mu^{(k)}|| = \sqrt{(\sum_j x^{(i)}_j - \mu^{(k)}_j)^2}$
2. update zwaartepunt
- nieuwe zwaartpunt berekenen door toevoegen van deze

blijf de for loop herhalen tot de toegewezen zwaartepunten niet meer veranderen
#### Het K-Gemiddelden Algoritme als Optimalisatie

- De kostfunctie is

$$
J = \frac{1}{m} \sum_{i=1}{m} ||x^{(i)} - \mu^{(c^{(i)})}||^2
$$

als $c^{(i)}$ de index is van de cluster van $x^{(i)}$

- het K-means algo kan vastgeraken in lokaal minimum. Random restart kan helpen.

#### Bepalen van het Aantal Clusters

Soms is het duidelijk, soms met de elleboogmethode:
- kostfunctie opstellen voor oplopende $K$
- knik in J(K) grafiek zoeken -> dit is het beste aantal

<!--
MARKMAP

# Zoekalgoritmen
##
### Boomgebaseerd
### Graafgebaseerd
##
### Blind
#### Diepte-eerst
#### Breedte-eerst
#### Iteratief verdiepen
#### Uniforme kost (= cheapest-first)
### Geïnformeerd
#### Gulzig beste-eerst
#### A*
## Competitief
### Minimax (evt. snoeien)
### Heuristische minimax
## Lokaal
### Hill climbing
### Gradient descent
### (Random walk)
### Simulated annealing
## Genetisch
### Selectie
#### Roulette wheel
#### Ranggebaseerd
### Recombinatie
#### Eénpunts crossover
#### Geordende crossover
### Mutatie

# Machine learning
## Gesuperviseerd
### Regressie
#### Lineaire regressie
#### Lineaire regressie met polynomiale attr.
### Classificatie
#### Logistische regressie
##### Binair
##### Niet-binair 1-vs-allen
##### Niet-binair 1v1
#### Neurale netwerken
##### Voorwaarts gericht
###### Stochastische gradient descent
###### Mini-batch gradient descent
##### (Recurrent)
## Ongesuperviseerd
### Clustering
#### K-means
### (Anomaliedetectie)
### (Primaire componenten analyse)
## (Reinforcement learning)

-->

<style>
body {
counter-reset: h2
}

h2 {
counter-reset: h3
}

h3 {
counter-reset: h4
}

h4 {
counter-reset: h5
}

h2:before {
counter-increment: h2;
content: counter(h2) ". "
}

h3:before {
counter-increment: h3;
content: counter(h2) "." counter(h3) ". "
}

h4:before {
counter-increment: h4;
content: counter(h2) "." counter(h3) "." counter(h4) ". "
}

h5:before {
counter-increment: h5;
content: "> ";
}
</style>