Classification d'images

La classification d'image consiste à assigner un label (une catégorie) à une image. C'est l'un des problèmes fondamentaux en vision par ordinateur. La principale difficulté provient du fossé sémantique, c'est-à-dire la difficulté de passer de données brutes (une matrice de nombres) en une interprétation du sens de l'image par l'ordinateur. Les changements de points de vue, les conditions d'illumination, la variabilité intra-classe et les occlusions sont des facteurs qui influencent la classification et la rendent difficilement automatique.

Cette tâche est aisée pour nous, car notre perception et nos raisonnements sont le fruit d'un apprentissage ; l'apprentissage statistique vise à reproduire ces mécanismes.

Différents types d'apprentissages

• Apprentissage supervisé : on dispose d'une vérité terrain contenant la bonne réponse, et cette information peut être utilisée pour apprendre
• Apprentissage non supervisé : on ne dispose pas d'une vérité terrain, et on ne peut pas utiliser cette information pour apprendre, la méthode doit découvrir elle-même la structure des données
• Apprentissage semi-supervisé : méthodes hybrides, où l'on a par exemple une vérité de terrain partielle

Différents types de modèles

• Modèles discriminants : définition d'une frontière entre les différentes classes ; modèles souvent puissants pour la classification supervisée
• Modèles génératifs : définition d'un prototype (modèle de distribution) pour les différentes classes ; permet potentiellement de générer de nouvelles données

Évaluation d'un système d'apprentissage

• Séparation des données en train et test (ne jamais utiliser les données de test pour apprendre)
• Pour une classe donnée, deux types d'erreurs sont possibles :
  • Faux positifs : éléments d'une autre classe assignés à cette classe
  • Faux négatifs : éléments de la classe assignés à une autre classe
  • En fonction de l'application, on peut souhaiter minimiser plutôt l'un ou l'autre
• Évaluation quantitative des prédictions d'un modèle
  • Matrice de confusion, taux de réussite, précision, rappel, F1-score, etc.
  • Précision : proportion des éléments prédits dans une classe qui lui appartiennent réellement
  • Rappel : proportion des éléments de la classe effectivement retrouvés

On considère les résultats d'une classification de $N$ éléments en $K$ classes ; pour chaque classe $i$, on a : $P_i = \dfrac{VP_i}{VP_i + FP_i}$ et $R_i = \dfrac{VP_i}{VP_i + FN_i}$. On peut ensuite calculer les scores de précision et de rappel globaux (moyennes par classe, dites macro) $P = \dfrac{\sum_{i=1}^K P_i}{K}$ et $R = \dfrac{\sum_{i=1}^K R_i}{K}$.

Capacité de généralisation

On souhaite que le système apprenne à partir des données de l'ensemble d'apprentissage, c'est-à-dire qu'il en capture les régularités (sans apprendre le bruit par cœur : surapprentissage). On souhaite également que le système soit capable de généraliser face à des données de test non observées auparavant.

Classifieur bayésien "naïf"

C'est un modèle probabiliste génératif (définition d'un prototype pour chaque classe, puis prédiction en fonction de celui-ci) ; il repose sur les probabilités conditionnelles et le théorème de Bayes.

Soient deux événements $x$ et $y$, on a : $P(x \cap y) = P(x | y)P(y) = P(y|x)P(x)$

D'où le théorème de Bayes : $P(y | x) = \dfrac{P(x | y)P(y)}{P(x)}$

$x$ est un vecteur de caractéristiques correspondant à l'observation pour un échantillon, $y_i$ correspond à la classe de l'échantillon $x_i$.

La formule précédente permet de calculer la probabilité d'appartenir à une classe $y$ à partir d'une observation $x$. La probabilité a priori $P(y_i)$ est choisie en fonction des connaissances que l'on a sur le problème et les données : souvent, on l'estime par la fréquence d'apparition de la classe dans l'ensemble d'apprentissage ; si l'information n'existe pas, on suppose les classes équiprobables (loi uniforme). Le calcul de la vraisemblance $P(x | y_i)$ est une estimation d'une fonction de densité à partir des données d'apprentissage. Les modèles paramétriques définissent les caractéristiques suivant une loi de probabilité connue dont on va estimer les paramètres à partir des données.

Rappel sur la loi normale

On suppose que les caractéristiques pour une classe suivent une loi normale, dans le cas unidimensionnel, on a : $P(x | y_i) = \dfrac{1}{\sqrt{2\pi\sigma_i^2}}e^{-\frac{(x - \mu_i)^2}{2\sigma_i^2}}$. On estime de manière empirique les paramètres de la loi à partir des échantillons de l'ensemble d'apprentissage. Pour la classe $i$, d'ensemble d'apprentissage $E_i$ de taille $N_i$, la moyenne est $\mu_i = \dfrac{\sum_{x \in E_i} x}{N_i}$ et la variance $\sigma_i^2 = \dfrac{\sum_{x \in E_i} (x - \mu_i)^2}{N_i}$.

Hypothèse "naïve"

L'hypothèse « naïve » consiste à supposer que les caractéristiques sont indépendantes entre elles (conditionnellement à la classe), ce qui se traduit par :

• la matrice de covariance est diagonale $\Sigma = \begin{pmatrix} \sigma_1^2 & 0 & 0 \\ 0 & \sigma_2^2 & 0 \\ 0 & 0 & \sigma_3^2 \end{pmatrix}$ et donc $|\Sigma| = \prod_{i=1}^3 \sigma_i^2$.
• les surfaces d'équiprobabilité sont des ellipsoïdes alignés sur les axes (des hypersphères si toutes les variances sont égales) ; les calculs sont plus simples et le risque de surapprentissage diminue.

Résumé

• Modèle génératif : on crée un prototype pour chaque classe ; on peut cependant ensuite en déduire une frontière entre les classes
• Différentes modélisations sont possibles en utilisant différentes lois, en fonction de notre connaissance du problème
• Sert souvent de classifieur de référence pour sa simplicité.

Support Vector Machines

C'est un classifieur binaire : pour chaque point $x_i$, on a $y_i = 1$ ou $y_i = -1$ selon la classe de $x_i$. Le modèle est discriminant : il cherche la meilleure frontière entre les classes. L'objectif est de trouver un hyperplan qui maximise la marge $\dfrac{2}{\|w\|}$, c'est-à-dire de minimiser $\|w\|$ sous les contraintes $w^T x_i + b \geq 1$ si $y_i = +1$ et $w^T x_i + b \leq -1$ si $y_i = -1$. Cela peut être résumé par $\min \limits_{w,b} \|w\|$ sous les contraintes $y_i (w^T x_i + b) \geq 1$ pour tout $i$.

Lorsque les données ne sont pas linéairement séparables nous pouvons avoir la définition d'une marge "molle" qui autorise les échantillons mal classés, c'est un compromis entre marge et erreurs régulé par un hyperparamètre $C$.

Si cela ne suffit pas, l'idée est de renoncer à une frontière linéaire dans l'espace initial en utilisant un noyau (kernel trick) : on projette implicitement les données dans un espace de plus grande dimension, dans lequel une frontière linéaire peut exister.