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

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

[TOC]

## Classification supervisé
$$
\left.
\begin{array}{l}
&D = D_1 \times D_2 \times \cdots D_n\\
&\varphi = \{1, \cdots, c\}
\end{array}
\right \}=\text{fixé}
$$

- Loi de Probabilité P sur D fixée (inconnue).
- on dispose d'un éxhantillon S.\
un ensemble de m exemples
$(\vec{x}, c(\vec{x})), \vec{x} \in D$
Livrés aléatoirement selon P(., .) défini par $P(\vec{x}), y) = P(\vec{x}) . P(y | \vec{x})$

On cherche à inférer une fonction de classemnt qui minimise l'erreur.

### Erreur apparente

$E_{app}(C) = \frac{err}{|S|}$ avec err égal au nombre d'exemple de S mal classée par C. ($|s|$ = cardinal de s)

Attention:\
On veut aussi avoid des fonctions qui ont un bon pouvoir prédictif.

$$
\lim\limits_{|s| \to \infty}{}E_{app}(C) = E(C)
$$

### Classificateur naïf de Bayes
$$
\DeclareMathOperator*{\argmax}{arg\,max}
$$

$$
C_{Bayes}(d) = \argmax_{k \in \{1 \cdots c\}} P(k | \vec{d})
= \argmax_{k \in \{1 \cdots c\}} P(\vec{d} | k) . P(k)
$$

$$
D = D_1 \times D_2 \times \cdots D_n\\
\vec{d} = (d_1, \cdots, d_n)\\
C_{Bayes}(d) = \argmax_{k \in \{1 \cdots c\}} P(\vec{d} | k) . P(k)
$$

$P(\vec{d} | k)$ : estrimation en utilisant S ?

$\widehat{P}(k)=$ la proportion des éléments de k dans S
$\frac{\text{nombre des élément de k dans s}}{|s|}$

Hypothèse de simplificatrice:\
On suppose que les attributs sont indépendants:
$$
P(d_1 \cdots d_n | k) = \prod_{i=1}^{n} P(d_i | k)
$$

$\widehat{P}(d_i|k)=$ la proportion d'éléments de la classe k qui ont $d_i$ comme descriptions

$$
C_{NaifBayes}(\vec{d}) =
\argmax_{k} \prod_{i=1}^{n} \widehat{P}(d_i | k) \widehat{P}(k)
$$

### Estimation de l'erreur réelle
- ensemble de test

On va donc répartir les exemple tirés aléatoirement dans 2 ensemble S et T
- S: échantillons d'apprentissage
- T: ens de test

$$
\widehat{E}(C) = \frac{\text{nombre d'éléments de T mal classés}}{|T|}
$$

### Rééchantillonage
Validation croisée:
Soit $k$ un param\
Partistionner S aléatoirement en k sous ens. $S_1 \cdots S_k$\
pour i = 1 à k\
- Apprendre sur l'échantillons $S \backslash S_i$ pour générer $C_i$
- Calculer $\widehat{e_{i}}$ erreur apparrente de $c_i$ sur $S_i$

$$
\widehat{E}(C) = \frac{\sum_{i=1}^{k} \widehat{e_i}}{|T|}
$$

### Bootstrap:

## Arbre de décision
Le principe est d'utiliser un test sur notre population $\Pi$

On ajoute un critere pour avoir les feuilles qui peut etre:
- avoir tous l'ensemble avec la classe C
- avoir quasiment tout le monde dans la classe C

Cela va donc dépendre de notre échantillon.

Rappelle erreur apparente:\
erreur faite sur l'échantillon meme

### Exemple personne malade
Les critère:
- température <37.5
- gorge irritée

Digraph g
{
    n0 [label="T<37.5"]
    n01 [label="gorge irritée"]
    n02 [label="malade", color="orange"]
    n11 [label="bien portant", color="orange"]
    n12 [label="malade", color="orange"]
    
    n0 -> n01 [label="oui"]
    n0 -> n02 [label="non"]
    n01 -> n12 [label="oui"]
    n01 -> n11 [label="non"]
}

:::success
Arbre de décision:
- noueud: position\
Soit $\alpha$ l'arité maximal des noeuds qui est ele nombre de successeurs a chaque noeud
- position: mot de $\{1 \cdots \alpha\}^*$\
$\epsilon$: position de la racine
:::

Pour $p \in \{1 \cdots \alpha\}^*$ une position dans l'arbre:
- $N(p)$ = le cardinal de l'esemble des exemples associé à p
- $N(k | p)$ = le cardinal de l'ensemble des exemple associés à p qui sont de classe k. (pour $k \in \{1 \cdots \alpha\}^*$)
- $P(k|p) = \frac{N(k | p)}{N(p)}$: la propostion des éléments de la classe k à la position p

$$
\begin{array}{|c|c|}
\hline
client & M & A & R & E & I \\
&\text{(montant complexe)} & \text{(age)} &
\text{(résidence)} & \text{(education)} & \text{Classe (internet)}\\
\hline
1 & moyen & moyen & village & oui & oui \\
\hline
2 & élevé & moyen & bourg & non & non \\
\hline
3 & faible & agé & bourg & non & non \\
\hline
4 & faible & moyen & bourg & oui & oui \\
\hline
5 & moyen & jeune & ville & oui & oui \\
\hline
6 & élevé & agé & ville & oui & non \\
\hline
7 & moyen & agé & ville & oui & non \\
\hline
8 & faible & moyen & village & non & non \\
\hline
\end{array}
$$
On a: $3I$ et $5\overline{I}$

Digraph M
{
    M [label="M (3, 5)"]
    f [label="(1, 2)"]
    m [label="(2, 1)"]
    e [label="(0, 2)"]
    
    M -> f [label="f"]
    M -> m [label="m"]
    M -> e [label="e"]
}

Digraph A
{
    A [label="A (3, 5)"]
    j [label="(1, 0)"]
    m [label="(2, 2)"]
    a [label="(0, 3)"]
    
    A -> j [label="j"]
    A -> m [label="m"]
    A -> a [label="a"]
}

Digraph R
{
    R       [label="R (3, 5)"]
    village [label="(1, 1)"]
    bourg   [label="(1, 2)"]
    ville   [label="(1, 2)"]
    
    R -> village [label="village"]
    R -> bourg   [label="bourg"]
    R -> ville   [label="ville"]
}

Digraph E
{
    E [label="A (3, 5)"]
    o [label="(3, 2)"]
    n [label="(0, 3)"]
    
    E -> o [label="o"]
    E -> n [label="n"]
}

### mesuré le degré de mélange?
Comment mesurer le degré de mélange entre les classes dans un ensemble d'éxemple ?

La fonction qui prend:
- soit min quand pas de mélange.
- soit max quand plus de mélange

#### Entropie

Pour une position dans l'arbre $(\{1 \cdots \alpha\}^*)$
:::success
$$
Entropie(p) = - \sum_{k = 1}^{c} P(k | p) \times \log(P(k | p))
$$
:::

#### Gini
:::success
$$
\begin{align}
Gini(p) &= 1 - \sum_{k = 1}^{c} P(k | p) ^2\\
&= 2 \sum_{k<k'} P(k | p) \times P(k' | p)
\end{align}
$$
:::

Exemple: Cas ou on prend 2 classes\
Soit x = la proportion d'éléments de classe 1 à p.
$$
E(p) = - x \log(x) - (1 - x) \log(1 - x)
$$
Donc:
- min: 0, 1 -> 0
- max: 1/2 -> 1

$$
Gini(p) = 2 x (1 - x)
$$
Pareil:
- min: 0, 1 -> 0
- max: 1/2 -> 1

---

Sur notre exemple:

Pour le test E:
$$
Ent(\epsilon) = - \frac{3}{8} \times \log(\frac{3}{8})
- \frac{5}{8} \times \log(\frac{5}{8}) \simeq 0.954\\
Ent(1) = - \frac{3}{5} \times \log(\frac{3}{5})
- \frac{2}{5} \times \log(\frac{0}{5}) \simeq 0.97\\
Ent(2) = - \frac{0}{3} \times \log(\frac{0}{3})
- \frac{3}{3} \times \log(\frac{3}{3}) = 0
$$

$$
Gini(\epsilon) = 2 \times \frac{3}{8} \times \frac{5}{8} \simeq 0.469\\
Gini(1) = 2 \times \frac{3}{5} \times \frac{3}{5} \simeq 0.48\\
Gini(2) = 2 \times \frac{0}{3} \times \frac{3}{3} = 0
$$

### Gain
Pour un test t, pour une position p.
$$
Gain(p, t) = f(p) - \sum_{j=1}^{\alpha} P_j \times f(p_j)
$$
- f peut etre:
- entropie
- ginie
- $P_j$ = la proportion des éléments de S à la position p qui se retrouvent à la postion pj après le test t


Choix du test à la position, c'est donc maximiser choisir t pour lequel Gain(p, t) est maximal.

$$
\begin{align}
G(\epsilon, M) &= E(\epsilon) -
\left(
\frac{3}{8} Ent(1) +
\frac{3}{8} Ent(2) +
\frac{2}{8} Ent(2)
\right)\\
&= Ent(\epsilon) - 0.62\\
G(\epsilon, A) &= Ent(\epsilon) - 0.5\\
G(\epsilon, R) &= Ent(\epsilon) - 0.87\\
G(\epsilon, E) &= Ent(\epsilon) - 0.607\\
\end{align}
$$
1. A
2. E
3. M
4. R

On applique donc un algorithme récursif

### Algorithme d'apprentissage générique

# attention ici on a du tres gros pseudo code
def decision_tree(lang):
    """
    entré:
        language de description, échantillon S
    """
    # initialisation à l'arbre vide
    # la eacine est le noeud courant
    t = Tree() 
    
    while(true):
        # décidé si le noeud est terminal
        if terminal(lang):
            t = lang.classe() # affecté une classe
            break;
        else:
            # selectioné un test et crée les sous arbre
            # créer les sous arbres
            t = test_and_create_sub_tree()
        # passer au noeud suivant
        t.next() 
    return t

### Arbre parfait
Erreur apparentte faible

Un arbre est parfait si:\
il ne se trompe pas sur les exmples de l'échantillon d'apprentissage.

On peut avoir de l'overfeating (erreur réel > erreur apparente)

### Elagage
On peut décider de faire un élaguage pour baiser l'erreur réel.
Il faut donc mesurée le gain en s'arrétant a l'endroit de l'élaguage

On va donc construire l'arbre puis essayer l'allégé, avec l'erreur réel.

On a donc 2 phase:
- phase d'expansion (construit l'arbre)
- phase d'élaguage (minimiser l'erreur réelle)

Exemple d'algo: CART
- phase d'expansion
- décider si un noeud est terminal: \
$N(p) \leq Borne_1 \lor Gini(p) \leq Borne_2$
- affecter la classe: \
classe majoritaire
- choix du test: \
Gain max avec gini
- phase d'élaguage:\
On construit une séquence d'arb re


$t_i \rightarrow t_{i+1}$\
p une position dans $t_i$


$$
g(p) = \frac{\Delta_{app}(p)}{|u_p| - 1}\\
\text{avec } \Delta_{app}(p) = \frac{MC(p) - MC(up)}{N(p)} \\
$$
avec:
- $MC(p)=$ le nombre d'éléments de $s$ mal classés à $p$ lorsqu'on élague $t_i$ à la position $p$
- $MC(up)=$ le nobre d'éléments de $s$ associés à $p$ qui sont mal classés par $up$

on calcule l'erreur apparante sur un ensemble de test T.\
Estimation de l'erreur réel
Puis on prentd le $t_i$ qui minimise l'erreur