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

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

[TOC]

## Perceptron -- algorithme de correction d'erreur

#### Théoreme:
Si l'échantillon S est lionéairement séparable et si les exemples sont présenté équiablement (le choix des exemples n'en exclu aucun).
L'algorithme par correction d'erreur converge vers un perceptron à seuil qui calcul S.

### Probleme
- Le vitesse de convergence peut etre lente
- Donne parfois des solutions qui ne sont pas robuste (par rapport a l'ajout de nouveaux exemple)\

- Si S n'est pas linéairement séparable\

## Apprentissage par décente de gradient

### Perceptron linéaire:
n entrées $x_1 \cdots x_n \rightarrow \mathcal{o}$
défini par $w_1 \cdots w_n$
$$
\mathcal{o} = \vec{x} . \vec{w} = \sum_{i=1}^{n} w_i x_i
$$

Erreur d'un perception P défini par $\vec{w} = (w_i, \cdots, w_n)$

Considérer, S l'ensemble d'exemple:
$$
s = (\vec{x}, \vec{c})\\
E(\vec{w}) = \frac{1}{2} . \sum_{s = (\vec{x}, \vec{c}) \in S} (c^s - \mathcal{o}^s)^2
$$
Minimiser E est trouver $\vec{x}$ qui minimise E

### Méthode du gradient
f est dérivable

$$
x_{n+1} = x_{n} + \Delta x_n\\
\Delta x_n = - \epsilon f'(x_n) \text{ pour un $\epsilon$ "bien choisis"}\\
f(x_{n+1}) = f(x_n - \epsilon f'(x_n)) \approx f(x_n) - \epsilon (f'(x_n))^2
$$

$$
\begin{align}
\frac{\partial E(\vec{w})}{\partial w_i} &=
\frac{\partial }{\partial w_i} \frac{1}{2} \sum_{s = (\vec{x}, \vec{c}) \in S} (c^s - \mathcal{o}^s)^2\\
&= \frac{1}{2} \sum_{S} \frac{\partial }{\partial w_i} (c^s - \mathcal{o}^s)^2\\
&= \frac{1}{2} \sum_{S} 2 (c^s - \mathcal{o}^s) \frac{\partial }{\partial w_i} (c^s - \mathcal{o}^s)\\
&=\sum_{S} (c^s - \mathcal{o}^s) \frac{\partial }{\partial w_i}
(c^s - \vec{w} \vec{x}^s)\\
&= \sum_{S} (c^s - \mathcal{o}^s) (-x_i^s)
\end{align}
$$

$$
\Delta w_i = - \epsilon \frac{\partial E(\vec{w})}{\partial w_i}
= \epsilon \sum_{S} (c^s - \mathcal{o}^s) . x_i\\
w_i \leftarrow w_i + \Delta w_i
$$

### Algorithme de décente de gradient:
Entrée:
- un échantillon S de $\mathbb{R}^N \times \{0, 1\}$
- $\epsilon$

Initialiser aléatoirement $w_i$ pour $i = 1 \cdots n$

Répéter
- Pour tout i
- $\delta w_i \leftarrow 0$
- Pour tout exemple $(\vec{x}^s, c^s) \in S$
- calcudler la sortie $\mathcal{o}^s$
- Pour tout i
- $\Delta w_i \leftarrow \Delta w_i + \epsilon (c^s - \mathcal{o}^s) \vec{xi}$
- Pour tout i
- $w_i \leftarrow w_i + \Delta w_i$

Sortie:
$P_i \vec{w} = (w_1, \cdots, w_n)$

### Algo de Widow-Hoff
$$
\Delta w_i = \epsilon (c^s - \mathcal{o}^s) x_i^s
$$
Entrée:
- $S \subseteq \mathbb{R}^N \times \{0, 1\}$
- $\epsilon$

Initialisaion aléatoire des $w_i$
Répéter
- Prendre un exmple $(\vec{x}, c) \in S$
- calcudler la sortie $\mathcal{o}^s$ pour $\vec{x}$
- Pour tout i à n faire:
- $w_i \leftarrow w_i + \epsilon (c - \mathcal{o}) xi$
- Pour tout i
- $w_i \leftarrow w_i + \Delta w_i$

Sortie:
$P_i \vec{w} = (w_1, \cdots, w_n)$

---

choix des exemples:
- choisir de mannière équitable

Arret:
- modification des poids < seuil

## réseaux muticouche

Peut t'on définir la fonction xor avec un réseaux multicouche ?

:::success
++définition:++\
Un réseaux de neuronnes est définit par une architechture
qui vérifie les propriétés suivantes:
- les céllules sont réparties en couche $c_0, c_1, \cdots c_q$
$c_i \cap c_j = \emptyset$
- $c_0$ est la rétine = cellules d'entrée = n variables d'entrée
- $c_1 \cdots c_{q-1}$: couche cachées
- $c_q$ = la ou les cellusles de décision (sortie)
- les entrées d'une céllile de $c_i (i \geq 1)$ sont toutes les cellulles de $c_{i-1}$ et aucune autre
:::

Parametre:
- combien de couche ?
- combien de cellules dans une couche ?
- trouver les coefficient synaptique

Pour un pb données:
- il faut fixer l'architechture (on ne le verra pas ici)
- Apprendre à partir d'un échantillon les poids

xor:\

Théoreme:\
Tout fonction booléenne peut être définie par un perception multicouche (réseaux de neuronne)

Indication pour la preuve:
mettre les formules sous la forme CNF ou DNF.

## fonction sigmoïde

la fonction sigmoide est une aproximation de la fonctionne de Heavyside

$$
\sigma_k(x) = \frac{e^{kx}}{e^{kx} + 1} = \frac{1}{1 + e^{-kx}}\\
k = 1:\\
\sigma(x) = \frac{e^{x}}{e^{x} + 1} = \frac{1}{1 + e^{-x}}\\
\sigma(x)' = \frac{e^{x}}{(1 + e^{x})^2} = \sigma(x) . (1 - \sigma(x))
$$

### Percepton a couche
Une cellule élémentaire à n entrée $\vec{x} = (x_1, \cdots, x_n) \in \mathbb{R}^N$ est défini par $\vec{w} = (w_1, \cdots, w_n) \in \mathbb{R}^N$ et la sortie $\mathcal{o}$:

$$
\begin {align}
\mathcal{o}(\vec{x}) &= \frac{1}{1 + e^{-y}}
& \text{ avec } y = \vec{x} \vec{w} = \sum_{i=1}^{n} w_i x_i\\
&= \sigma\left(\sum_{i=1}^{n} w_i x_i\right)
\end{align}
$$
notre fonction d'activation est sigmoïde


L'erreur:
$$
E(\vec{w}) = \frac{1}{2}
\sum_{(\vec{x}^s, \vec{c}^s) \in S}
\sum_{k =1}^{p} (c_k^s - \mathcal{o}_k^s)^2
$$
On veut donc miniser cette erreur sur l'ensemble de l'échantillion

$$
E(\vec{w})= \frac{1}{2} \sum_{k =1}^{p} (c_k^s - \mathcal{o}_k^s)^2
$$
Pour un élément doné de S (à la widrow-Hoff)

$$
\Delta w_{ij} = - \epsilon \frac{\partial E(\vec{w})}{\partial w_{ij}}
$$
$$
\begin{align}
\frac{\partial E(\vec{w})}{\partial w_{ij}} =
\frac{\partial E}{\partial y_i}
\frac{\partial y_i}{\partial w_{ij}}\\
= \frac{\partial E(\vec{w})}{\partial y_i} x_{ij}
\end{align}
$$
notation:
$$
\delta_i = - \frac{\partial E}{\partial y_i}
$$

cellule i:
- sortie
- interne

sortie:
$$
\delta_i = \mathcal{o}_i (1 - \mathcal{o}_i) (c_i - \mathcal{o}_0)
$$

interne:
$$
\delta_i = \mathcal{o}_i (1 - \mathcal{o}_i) \times \sum_{k \in Success(i)} \delta_k w_{ki}
$$

$$
\Delta w_{ij} = \epsilon w_{ij} \times \delta{i}
$$


### Algorithme de rétropropagation du gradient
Entrée:
- un Perceptron muti-couche (pmc) $c_o c_1 \cdots c_{q-1} c_q$

pour chaque couche : n-cellules

Initialisation aléatoire des poids dans $[-0.5, 0.5]$

Répéter:
- Prendre $(\vec{x}^s, \vec{c}^s) \in S$ et calculer $\mathcal{o}^s$

% Calcul des $\delta_i$ par rétropropagation.
- pour toutes cellules de sortie i:
- $\delta_i \leftarrow \mathcal{o}_i (1 - \mathcal{o}_i) (c_i - \mathcal{o}_i)$
- pour chaque couche de q-1 à 1
- pour chaque cellule u de la couche courante:
- $\delta_i \leftarrow \mathcal{o}_i (1 - \mathcal{o}_i) \sum_{k \in succ(i)}(delta_k - w_{ki})$

% mise a jour des poids
- Pour tout poids
- $w_{ij} \leftarrow w_{ij} + \epsilon . \delta_i x_{ij}$

Sortie:
- les $w_{ij}$