# Cour 9 -- Introduction a l'Intelligence Artificielle et à la Theorie des Jeux

###### tags `cour` `M1 S1` `IA`
[Somaire](/8Sa-Z4QBS1ep0xPwtzigJA)\
[Precedent](/SsELiBJQSIuFPBUHO90pYw)
> [time= 20 novembre 2020]

[TOC]

## Apprentissage basé sur les réseaux de neuronnes

Dans ce cours:\
apprentissage supervisé à partir d'une base d'exemple (online)

### perceptron (Franck rosemblate 1958)
:::success
On appelle perceptron linéaire à seuil:
- **n** entrée $x_1 \cdots x_n$
- **o** sortie

(peuvet etre des réel, booléen ...)

il faut y avoir:
- $n + 1$ coéficient synaptiques $w_1 \cdots w_n$
- seuil $\mathcal{o}$
$$
o =
\begin{cases}
1 & \text{si } \sum_{i=1}^{n} w_i . x_i >\mathcal{o}\\
0 & \text{sinon}
\end{cases}
$$
:::

On peut aussi définir:
- un potentiel synaptique: $\sum_{i=1}^{n} w_i . x_i$
- fonction d'activation f
- on utilise systématiquement une entrée de plus $x_0 = 1$

fonction de heaviside:
$$
f(x)=
\begin{cases}
1 & \text{si } x > 0\\
0 & \text{sinon}
\end{cases}
$$

Comparaison avec perception a seuil:
$w_0 = - \mathcal{o}$

### Or logique

### Limitation et interprétation géométrique
Soit $S \subseteq \mathbb{R}^N \times \{0, 1\}$ un ensemble d'exemples
$$
S_0 = \{ s \in \mathbb{R}^N (s, 0) \in S\}\\
S_1 = \{ s \in \mathbb{R}^N (s, 1) \in S\}
$$
S est linéairement séparable s'il existe un hyperplan de $\mathbb{R}^N$ qui sépare $S_0$ et $S_1$.

#### Théoreme
Un perceptron linéaire a sueil divise lespade des entré $\mathbb{R}^N$ en 2 sous espace délimités par un hyperplan.\

Et inversement:\
Tout ensemble linéairement séparable peut ètre discriminé par un perception

$$
f: \mathbb{R}^N \rightarrow \{0, 1\}
$$

### XOR
XOR ne peut pas être calculée par un perception linéaire à seuil

| x1 | x2 | x1 XOR x2 |
| --- |:---:|:---------:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | O | 1 |
| 1 | 1 | 0 |

Preuve:\
Supposons qu'il existe un perception pour XOR.
$$
\begin {cases}
w_0 &+& 0 . w_1 &+& 0 . w_2 &=& w_0 &\leq 0\\
w_0 &+& 0 . w_1 &+& 1 . w_2 &=& w_0 + w_2 &> 0\\
w_0 &+& 1 . w_1 &+& 0 . w_2 &=& w_0 + w_1 &> 0\\
w_0 &+& 1 . w_1 &+& 1 . w_2 &=& w_0 + w_1 + w_2 &\leq 0\\
\end {cases}
$$
si on fait equation 1 + 4: $2 w_0 + w_1 + w_2 \leq 0$\
si on fait equation 2 + 3: $2 w_0 + w_1 + w_2 > 0$\
On a donc contradiction

interprétation graphique:\

### Algorithme par correction d'erreur
Entrée:
- Un échantillon S de $\mathbb{R}^N \times \{0, 1\}$ ou $\{0, 1\}^N \times \{0, 1\}$

intialisation des poids $w_i$ pour $i=0 \cdots n$

Répété:
- Prendre un exemple $(\vec{x}, c)$ dans S
- Calculer la sortie $\mathcal{o}$ du percetion sur $\vec{x}$
- Pour i=0 à n: // on change les poids
- $w_i = w_i + (c - \mathcal{o}) . x_i$

Sortie:
- un perception défini par $(w_0, w_1, \cdots, w_n)$

Prendre tous les exemples dans un certain ordre fixé.\
S'arréter quand les poids n'ont pas changé quand on à fait un tour complet des exemples.

$$
\begin{array}{| c | c |}
\hline
étape & w_0 & w_1 & w_2 & Entrée &
\sum_{i=0}^{2} w_i x_i & \mathcal{o} & C &
w_0 & w_1 & w_2\\
\hline
init & & & & & & & & 0 & 1 & -1 \\
\hline
1 & 0 & 1 & -1 & 100 & 0 & 0 & 0 & 0 & 1 & -1 \\
\hline
2 & 0 & 1 & -1 & 101 & -1 & 0 & 1 & w_0 + (C - \mathcal{o}) \times{x_0} = & 1 & 0 \\
&&&&&&&&0 + 1 \times 1 = 1 &\\
\hline
3 & 1 & 1 & 0 & 110 & 2 & 1 & 1 & 1 & 1 & 0 \\
\hline
4 & 1 & 1 & 0 & 111 & 2 & 1 & 1 & 1 & 1 & 0 \\
\hline
5 & 1 & 1 & 0 & 100 & 1 & 1 & 0 & 1 + (-1) \times x_0 = 0 & 1 & 0 \\
\hline
6 & 0 & 1 & 0 & 101 & 0 & 0 & 1 & 1 & 1 & 1 \\
\hline
7 & 1 & 1 & 1 & 110 & 2 & 1 & 1 & 1 & 1 & 1 \\
\hline
8 & 1 & 1 & 1 & 111 & 3 & 1 & 1 & 1 & 1 & 1 \\
\hline
9 & 1 & 1 & 1 & 100 & 1 & 1 & 0 & 0 & 1 & 1 \\
\hline
10 & 0 & 1 & 1 & 101 & 1 & 1 & 1 & 0 & 1 & 1 \\
\hline
11 & 0 & 1 & 1 & 110 & 1 & 1 & 1 & 0 & 1 & 1 \\
\hline
12 & 0 & 1 & 1 & 111 & 2 & 1 & 1 & 0 & 1 & 1 \\
\hline
13 & 0 & 1 & 1 & 100 & 0 & 0 & 0 & 0 & 1 & 1 \\
\hline
\end{array}
$$

Cette algorithme converge que si l'ensemble est linéairement séparable

[suivant](/Y1TM7fS5Scuoy9lPTVluJA)