---
# System prepended metadata

title: Cour 10 -- Introduction a l'Intelligence Artificielle et à la Theorie des Jeux
tags: [M1 S1, IA, cour]

---

# 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)\
![](https://i.imgur.com/K00wXd3m.png)

- Si S n'est pas linéairement séparable\
![](https://i.imgur.com/EDLWjvum.png)


## Apprentissage par décente de gradient
![](https://i.imgur.com/tG69mMe.png)

### 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
:::
![](https://i.imgur.com/q0oV1za.png)


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:\
![](https://i.imgur.com/7C8I9KFl.png)

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
![](https://i.imgur.com/YpzxiN4l.png)

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

![](https://i.imgur.com/s66Peoxl.png)


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}
$$

![](https://i.imgur.com/50gqVkjl.png)

### 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}$