###### tags: `S8` `Commun` `ScD : Analyse des données - introduction à l'IA et à la RDF`

<style>
.table-center th, .table-center td {
text-align: center;
}

.row-around {
display: flex;
justify-content: space-around;
width: 100%;
}
.mathjax {
font-size: 1.2em;
}
</style>

# Introduction à l'IA et à la Reconnaissance de Formes

## Maquette

<div class="row-around">
<table class="table-center">
<thead>
<tr>
<th colspan="3">Horaires (h)</th>
</tr>
<tr>
<th>CM</th>
<th>TD</th>
<th>TP</th>
</tr>
</thead>
<tbody>
<tr>
<td>12</td>
<td>4</td>
<td>6</td>
</tr>
</tbody>
</table>

<table class="table-center">
<thead>
<tr>
<th colspan="3">Poids (%)</th>
</tr>
<tr>
<th>UE</th>
<th>CC</th>
<th>ET</th>
</tr>
</thead>
<tbody>
<tr>
<td>35</td>
<td>/</td>
<td>100</td>
</tr>
</tbody>
</table>
</div>

Ragot : IA (4h)
Cardot : RDF

<ins>**Diapos sur teams**</ins>

## Introduction

### Matrice de confusion

**Lignes :** formes en entré (dont on connait déjà le type)
**Colonnes :** formes détectées. Il y a une colonne de rejet par l'algorithme.
**Contenu :** nb de fois que l'algo a reconnu un type pour une forme donnée. Un algo parfait a une matrice de confusion diagonale

### Taux de reconnaissance

somme diago / nb total d'exemple -> mauvaise formule car si les données d'entrée ne sont pas équitablement réparties entre les formes, faux

Bonne formule (fonctionne toujours !) : somme des pourcentage de bonne réponses de chaque type en entrée (lignes) / le nombre de types (lignes)

- Taux de fausse acceptation
- Taux de fausse erreur
- Taux d'égale erreur (biométrie) -> autant de fausse acceptation que de faux rejet

Coût d'une décision : poids de la conséquence d'une erreur (formule de mort -> $coût(d()) = intégrale...$)

### Décision Bayésienne

Thérorème Bayes probas :

$$
P_B(A) = \dfrac{P(A)\times P_A(B)}{P(B)}
$$

### Plus Proche Voisin (PPV)
CM1 diapo 27

$d(x) = d(x_i)$ avec $i = arg\quad min\quad dist(x, x_j)$

Taux d'erreur moyen < 2 * Bayes pour un grand échantillon
-> Moins bien que Bayes (Bayes = méthode optimale)

Zones graphes = zones de plus proche voisin

##### k-PPV

-> recherche les k PPV autours d'un point et on cherche la classe majoritaire.

##### La distance intraclasse :
*moyenne des distances des exemples d'une classe avec tous les autres exemples de la classe*
-> Vaut 2 fois la somme des variances sur chaque composante des formes

##### La distance interclasse :
*moyenne des distances des examples d'une classe avec tous les exemples d'une autre classe*

on cherche à maximiser:

-> $\dfrac{distInter}{distIntra}$

### K-Means ( centre mobiles, nuées dynamiques)


## Classification Ascendante Hiérarchique (CAH)

### Intro

Classifier = regrouper objets avec critères similaires

exemple:
*on prends une table individus/variables centrée reduite* :

### Indice de dissimilarité ou distance

(k = indice somme)

$$
d(l_i, l_j) = \sqrt{\sum{(x_{ik} - x_{jk})^2}}
$$


#### Dendogramme :

On cherche a partitionner aux endroits ou les sauts d'indices sont "intéressant".
-> *dans l'exemple on partitionne vers 1,5 pour se retrouver avec 4 regroupements(classes) .*

## CM2 : arbres de décision

**Arbre de décision :** <ins>classificateur</ins> pour des instances représentées dans un <ins>formalisme attribut/valeur</ins>
- Les **noeuds** testent les attributs ;
- Il y a une **branche** pour chaque valeur de l'attribut testé (noeud parent des branches);
- Les **feuilles** spécifient les catégories (deux ou plus).

exemple :

### Construction
Chaque instance est décrite par un vecteur d'attributs/valeurs

En entrée, un ensemble d'instances et leurs classes...

l'algorithme d'apprentissage doit contruire un arbre de décision.

On choisi le partitionnement s maximisant le gain d'inpureté (cf après) (calcul $\Delta i(s)$)

### Choix

Si langage adéquat, tjs possible constr un arbre décision classant correctement les exemples d'apprentissage

Il y a le + souvent de nombreux arbres de décisions possibles corrects

Valeur d'un arbre
-> Impossibilité de procéder par énumération / évaluation (NP-complet)

Utilisation d'une méthode constructive incrémentale :

$\prod_{i=1}^A {i^{V^{A-i}}}$

### Impureté

Arbre simple = minimise l'espérance du nb de tests pour classe un nv obj

Critère de choix de chaque noeud
...

on choisi un partitionnement qui maximise le gain d'impurté

$\Delta{i}(s) = i(t) -\sum_{m=1}^M P_m i(t_m)$

-> m = nb modalités (2 si binaire)
$p_m$ ou $p_k$ = proportion d'exemples de la modalité ou classe

Critères :

Taux de mal classé = forme : deux droites formant un angle
Entropie (critère le plus souvent utilisé) = forme : demi-cercle = gain d'information
Critère de Gini = forme : parabole

i(p) = impureté de l'objet p

#### Exemple calcul gain
/ -> séparation classe et non division

$i(t_2) = -\dfrac{5}{27 + 5}\times log_2\left(\dfrac{5}{27 + 5}\right) - \dfrac{27}{27 + 5}\times log_2\left(\dfrac{27}{27 + 5}\right)$
$i(t_2) = 0.625$

$\Delta(s) = i(t) - \dfrac{15 + 3}{20 + 30} \times i(t_1) - \dfrac{27 + 5}{20 + 30} \times i(t_2)$
$\Delta(s) = 0.971 - \dfrac{18}{50} \times 0.65- \dfrac{32}{50} \times 0.625$

### Arrêt et élagage
Pre-pruning :
*on s’arrête de développer l’arbre avant d’arriver à des feuilles pures*

Post-pruning :
*on enlève les branches qui sont les moins utiles*

### Random Forest

Méthode de classification

#### Principe de Random Forests

On va construire un grand nombre d’arbres de décision pour un même problème :
- On prend la décision finale par un vote majoritaire
- Le résultat final sera bon si les arbres sont différents (complémentaires) et efficaces

Choix de K : essais avec 1 ou √M ou log M +1
On peut prendre K aléatoire entre 1 et M pour
éviter un paramètre

### Méthodes structurelles

Description des formes à l'aide de primitives et de lien entre ces dernières

Outils utilisés : chaînes, graphes, et grammaires

#### Chaînes
- Longueur **fixe** : la position de la primitive dans la chaîne a une signification
- Longueur **variable** : chaîne d’un seul type de primitive

Exemple : code de Freeman
Numéro = sens du trait

#### Distance élastique

$d(A, B) = d(n, m)$, $A = x_1, ..., x_n\quad B = y_1, ..., y_m$
$d(2, 3) = d(x_1x_2, y_1y_2y_3)$

$d(x, y) = 1$ si $x \neq y$
$\quad\quad\quad= 0$ si $x = y$

$d(1,1)=d(x_1, y_1)$

$d(i, j) = min [ d(i-1, j), d(i, j-1), d(i-1, j-1) ] + d(x_i, y_j)$
pour 2 ≤ i ≤ n, 2 ≤ j ≤ m

*Exemple*:

#### Distance dédition

Prochain cours (à voir avant pour être bien)

coucou =)

Insertion : ε -> a. Coût $w_i$
Destruction : a -> ε. Coût $w_d$
Substitution : a -> b. Coût $w_s$

##### Algo :
- d(0, j) = j.$w_i$
- d(i, 0) = i.$w_d$
- d(i, j) =*min*[d(i-1,j)+$w_d$,d(i,j-1)+$w_i$, d(i-1, j-1)+$w_s$]

#### Graphes

En RF, nœuds : primitives et arcs : liens entre
primitives

#### Classification avec graphes

- Apprentissage : choisir des graphes prototypes (plusieurs graphes de formes représentatifs des classes)
- Reconnaissance : Quantifier la distance / ressemblance entre les graphes à reconnaître et les graphes prototypes. Puis kPPV avec cette distance.

#### Isomorphisme

Isomorphisme de graphe :
G1 et G2 sont isomorphes s’il existe une bijection f
entre X1 et X2 qui vérifie :
$$
\forall x_ 1 \in X_1 et \forall x_2 \in X_2,(x1, x2) \in U_1 \equiv (f(x_1), f(x_2)) \in U_2
$$
C’est un isomorphisme entre structures
G1 et G2 doivent avoir le même ordre (nb nœuds).
- Pour des graphes de formes, il faut en plus que
les valeurs des nœuds et des arcs se
correspondent.
- Cette notion est peu utilisable en RF

#### Distance entre 2 graphes

- Méthodes basées Noyau
- Apprenables
- Sensibles à de petites modifications
- GED : Graph Edit Distance
- Pas simple à calculer
- Résultats satisfaisants

**def :**
*Clique : Sous-graphes en relation complète*

#### Méthodes grammaticales

*rappel sur la Grammaire*:
- Alphabet (A)
- symboles Internes (I)
- symboles de départ ou Start (S)
- règles de Production (P)
- Le langage est généré par une grammaire. L ( G (A, I, S, P) ) est l’ensemble des chaînes générables par G.

#### Grammaires pour la RF

Apprentissage : inférence grammaticale

**¯\\\_(ツ)_/¯**

## CM3 : Sélection et extraction de caractéristiques

#### Curse of dimensionality

- Malédiction de la dimensionnalité. Bellman 1961.
- Dans un espace 100-D, combien faut-il d’exemples pour avoir la même densité de points que pour 100 données dans un espace 2-D ?

#### 2 approches

- Information redondante ou non significative
- Sélection de caractères : sous-ensemble de caract parmi celles disponibles
- Extraction de caractères : projection des données dans un espace de plus petite dimension

### Sélection de caractéristiques

#### Approches
- Filter (filtre)
La sélection se fait à partir de statistiques sur les caract.
- Wrapper (enveloppe) La sélection prend en compte le taux de reconnaissance (% reco).
- Integrated (intégrée) Intégrée dans l’algo de classif (ex. random forest)

Recherche optimale

- Nombre de sous-ensembles à explorer :

$$
q\binom{D}{d} = \frac{D!}{(D-d)!d!}
$$

Pour d=10 et D=100 : + de 1013 combinaisons
- Branch and bound (PSE)
Mais le critère (proba d’erreur minimum n’est pas vraiment monotone

## SVM