Cours

Apprentissage de paramètres par max de vraisemblance

Partie obligatoire


Dans ce TME, l'objectif est d'apprendre grâce à l'estimateur de maximum de vraisemblance les paramètres de lois normales à partir d'un ensemble de données. Ces lois normales seront ensuite exploitées pour faire de la classification (comme nous l'avions vu en cours avec les images de désert, forêt, mer et paysages enneigés).

Ici, notre base de données d'apprentissage est la base USPS. Celle-ci contient les images réelles de chiffres provenant de codes postaux écrits manuellement et scannés par le service des postes américain. Ces données scannées ont été normalisées de manière à ce qu'elles soient toutes des images de 16x16 pixels en teintes de gris, cf. Le Cun et al., 1990:

Y. LeCun, O. Matan, B. Boser, J. S. Denker, et al. (1990) "Handwritten zip code recognition with multilayer networks". In ICPR, volume II, pages 35–40.

Voici quelques exemples d'images de cette base :

1. Préparation / visualisation

Vous allez tout d'abord copier-coller le code ci-dessous dans votre éditeur de python. Ne perdez pas de temps à essayer de comprendre les instructions de ces fonctions. Leur utilité est décrite en dessous du code.

# -*- coding: utf-8 -*-

import numpy as np
import matplotlib.pyplot as plt

def read_file ( filename ):
    """
    Lit un fichier USPS et renvoie un tableau de tableaux d'images.
    Chaque image est un tableau de nombres réels.
    Chaque tableau d'images contient des images de la même classe.
    Ainsi, T = read_file ( "fichier" ) est tel que T[0] est le tableau
    des images de la classe 0, T[1] contient celui des images de la classe 1,
    et ainsi de suite.
    """

    # lecture de l'en-tête
    infile = open ( filename, "r" )    
    nb_classes, nb_features = [ int( x ) for x in infile.readline().split() ]

    # creation de la structure de données pour sauver les images :
    # c'est un tableau de listes (1 par classe)
    data = np.empty ( 10, dtype=object )  
    filler = np.frompyfunc(lambda x: list(), 1, 1)
    filler( data, data )

    # lecture des images du fichier et tri, classe par classe
    for ligne in infile:
        champs = ligne.split ()
        if len ( champs ) == nb_features + 1:
            classe = int ( champs.pop ( 0 ) )
            data[classe].append ( list ( map ( lambda x: float(x), champs ) ) )
    infile.close ()

    # transformation des list en array
    output  = np.empty ( 10, dtype=object )
    filler2 = np.frompyfunc(lambda x: np.asarray (x), 1, 1)
    filler2 ( data, output )

    return output

def display_image ( X ):
    """
    Etant donné un tableau X de 256 flotants représentant une image de 16x16
    pixels, la fonction affiche cette image dans une fenêtre.
    """

    # on teste que le tableau contient bien 256 valeurs
    if X.size != 256:
        raise ValueError ( "Les images doivent être de 16x16 pixels" )

    # on crée une image pour imshow: chaque pixel est un tableau à 3 valeurs
    # (1 pour chaque canal R,G,B). Ces valeurs sont entre 0 et 1
    Y = X / X.max ()
    img = np.zeros ( ( Y.size, 3 ) )
    for i in range ( 3 ):
        img[:,i] = X

    # on indique que toutes les images sont de 16x16 pixels
    img.shape = (16,16,3)

    # affichage de l'image
    plt.imshow( img )
    plt.show ()

La base qui va vous servir pour votre apprentissage de paramètres s'appelle 2015_tme3_usps_train.txt. Téléchargez-la. La fonction read_file : string -> float np.array n.array np.array contenue dans le code python ci-dessus permet de lire ce fichier. Cette fonction renvoie un tableau de tableaux d'images:

  • Chaque image a une taille de 16x16 pixels et représente un chiffre entre 0 et 9. Par exemple :
  • Chaque image est modélisée par un tableau numpy de 256 nombres réels compris entre 0 et 2, qui caractérisent l'intensité des pixels dans l'image (16x16 = 256 pixels).
  • Les images correspondant au même chiffre manuscript (0,...,9) sont placées dans un même tableau. Le fichier usps indique en effet pour chaque image à quel chiffre celle-ci correspond. Dans le jargon de l'apprentissage, les chiffres sont appelés classes et, lorsque nous aurons de nouvelles images dont nous essayerons de déterminer, grâce à nos lois normales, à quel chiffre elles correspondent, nous dirons que nous faisons de la classification. Enfin, apprendre les paramètres de nos lois normales à partir d'un fichier qui contient pour chaque image sa classe s'appelle de l'apprentissage supervisé.
  • Pour terminer la description de l'objet retourné par la fonction read_file, les tableaux d'images correspondant à chaque chiffre sont eux-mêmes stockés dans un tableau et c'est ce dernier qui est renvoyé. Chaque élément de ce tableau correspond donc à l'ensemble des images d'une classe. Le premier élément contient ainsi toutes les images du chiffre 0, le 2ème toutes celles du chiffre 1, et ainsi de suite. Par exemple, si read_file("fichier") retourne un objet training_data, alors training_data[2] est le tableau de toutes les images du chiffre 2, et training_data[2][3] correspond à la 4ème image du chiffre 2 (les indices des tableaux débutant à 0), autrement dit à un tableau de 256 nombres réels représentant cette image.


La fonction display_image, quant à elle, permet de visualiser les images que vous allez manipuler. Celle-ci prend donc en argument une image (c'est-à-dire un tableau de 256 nombres réels) et l'affiche dans une fenêtre. Exécutez cette fonction sur quelques images de votre base d'apprentissage afin de visualiser les données que vous allez manipuler par la suite. Par exemple, vous pouvez tester:

training_data = read_file ( "2015_tme3_usps_train.txt" )

# affichage du 1er chiffre "2" de la base:
display_image ( training_data[2][0] )

# affichage du 5ème chiffre "3" de la base:
display_image ( training_data[3][4] )

2. Maximum de vraisemblance pour une classe

Dans ce TME, nous allons étudier la distribution de probabilité des teintes de gris des images (en fait, nous allons étudier sa fonction de densité car on travaille sur des variables aléatoires continues) . Nous allons faire l'hypothèse (certes un peu forte mais tellement pratique) que, dans chaque classe, les teintes des pixels sont mutuellement indépendantes. Autrement dit, si {$X_i$}, {$i=$}0,...,255, représente la variable aléatoire "intensité de gris du ième pixel", alors {$p(X_0,\ldots,X_{255})$} représente la fonction de densité des teintes de gris des images de la classe et:

{$$p(X_0,\ldots,X_{255}) = \prod_{i=0}^{255} p(X_i).$$}

Ainsi, en choisissant au hasard une image dans l'ensemble de toutes les images possibles de la classe, si celle-ci correspond au tableau np.array([x_0,...,x_255]), où les x_i sont des nombres réels compris entre 0 et 2, alors la valeur de la fonction de densité de l'image est égale à {$p$}(x_0,...,x_255) = {$\prod_{i=0}^{255} p$}(x_i).

Nous allons de plus supposer que chaque {$X_i$} suit une distribution normale de paramètres {$(\mu_i,\sigma^2_i)$} (autrement dit, {$p$}(X_i) = {$\cal{N}(\mu_i,\sigma^2_i)$}). Par maximum de vraisemblance, estimez, pour une classe donnée, l'ensemble des paramètres {$(\mu_0,\ldots,\mu_{255})$} et {$(\sigma_0^2,\ldots,\sigma_{255}^2)$}. Pour cela, écrivez une fonction learnML_class_parameters : float np.array np.array -> float np.array x float np.array qui, étant donné le tableau d'images d'une classe tel que retourné par la fonction read_file (autrement dit un tableau de tableaux de 256 nombres réels), renvoie un couple de tableaux, le premier élément du couple correspondant à l'ensemble des {$\mu_i$} et le 2ème à l'ensemble des {$\sigma_i^2$}, {$i=$}0,...,255. C'est-à-dire que learnML_class_parameters ( classe ) renverra un objet similaire à :

( array ( [{$\mu_0,\ldots,\mu_{255}$}] ), array ( [{$\sigma_0^2,\ldots,\sigma_{255}^2$}] ) )

Grâce à votre fonction learnML_class_parameters, vous pouvez verifier que:

learnML_class_parameters ( training_data[0] )
 (array([ 1.37185930e-03,   4.60217755e-03,   1.50770519e-02,
          5.87487437e-02,   1.66657454e-01,   4.28577052e-01,
          8.68415410e-01,   1.15260804e+00,   1.04628392e+00,
          6.46298995e-01,   2.58751256e-01,   7.90837521e-02,
          ...............................
          1.28302848e+00,   1.52802513e+00,   1.43905193e+00,
          1.04248827e+00,   5.32985762e-01,   1.74494137e-01,
          3.24891122e-02,   3.47487437e-03,   6.36515913e-05,
          0.00000000e+00]), 
  array([ 2.24522353e-03,   6.60664324e-03,   1.95906222e-02,
          6.29011999e-02,   1.80366523e-01,   3.72113773e-01,
          5.31683397e-01,   5.38201451e-01,   5.62586277e-01,
          4.57620803e-01,   2.35928060e-01,   8.26775407e-02,
          ...............................
          4.46902042e-01,   3.40271867e-01,   1.30177809e-01,
          2.49171310e-02,   1.77752743e-03,   4.23882955e-06,
          0.00000000e+00] ) )
learnML_class_parameters ( training_data[1] )
 
 (array([ 0.00000000e+00,   0.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   3.98009950e-06,   1.27223881e-02,
          3.64843781e-01,   1.47724776e+00,   9.99703483e-01,
          1.18331343e-01,   4.97313433e-03,   0.00000000e+00,
          ...............................
          4.32477612e-01,   3.99064677e-02,   3.73731343e-03,
          6.62686567e-04,   4.67661692e-04,   0.00000000e+00,
          0.00000000e+00]), 
  array([ 0.00000000e+00,   0.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   1.59045568e-08,   7.47939656e-03,
          2.52206480e-01,   2.13186449e-01,   3.40351753e-01,
          7.76266554e-02,   3.64318435e-03,   0.00000000e+00,
          ...............................
          3.20651061e-01,   4.13332529e-02,   4.10675488e-03,
          4.40910100e-04,   2.19582288e-04,   0.00000000e+00,
          0.00000000e+00] ) )


3. Maximum de vraisemblance pour toutes les classes

En utilisant la fonction de la question précédente, écrivez une fonction learnML_all_parameters : float np.array np.array np.array -> (float np.array x float np.array) list qui, étant donné le tableau training_data retourné par la fonction read_file (donc contenant toutes les images de toutes les classes), renvoie une liste de couples ( array ( [{$\mu_0,\ldots,\mu_{255}$}] ), array ( [{$\sigma_0^2,\ldots,\sigma_{255}^2$}] ) ). Vous exécuterez cette fonction sur vos données d'apprentissage et sauvegarderez le résultat dans une variable parameters.

4. Log-vraisemblance d'une image

Nous allons maintenant tester si, étant donné de nouvelles images, on peut classer celles-ci correctement, c'est-à-dire si on peut retrouver les chiffres auxquelles elles correspondent. Pour cela, nous allons utiliser de nouvelles images se trouvant dans le fichier 2015_tme3_usps_test.txt. Ce fichier a exactement le même format que celui d'apprentissage et peut donc être lu grâce à la fonction read_file. En particulier, pour chaque image, nous avons le chiffre auquel elle correspond, ce qui nous permettra de vérifier que notre classifieur fonctionne correctement. Téléchargez le fichier et lisez-le en utilisant read_file.

Ecrivez une fonction log_likelihood : float np.array x (float np.array,np.array) -> float qui, étant donné une image (donc un tableau de 256 nombres réels) et un couple ( array ( [{$\mu_0,\ldots,\mu_{255}$}] ), array ( [{$\sigma_0^2,\ldots,\sigma_{255}^2$}] ) ), renvoie la log-vraisemblance qu'aurait l'image selon cet ensemble de {$\mu_i$} et {$\sigma_i$}. Rappelez-vous que:

{$$\log p(x_0,\ldots,x_{255}) = \sum_{i=0}^{255} \log p(x_i) = \sum_{i=0}^{255} \left[- \frac{1}{2} \log(2 \pi \sigma_i^2) - \frac{1}{2} \frac{(x_i - \mu_i)^2}{\sigma_i^2}\right]$$}

Notez que le module math contient une constante math.pi. Attention: dans la liste parameters calculée dans la question précédente, pour certains pixels de certaines classes, la valeur de {$\sigma^2$} est égale à 0 (toutes les images de la base d'apprentissage avaient exactement la même valeur sur ce pixel). Dans ce cas, la vraisemblance de toute image sur ce pixel doit être de 1 (et donc sa log-vraisemblance doit être égale à 0).

Vous pourrez vérifier que vous obtenez les mêmes résultats que ci-dessous:

parameters = learnML_all_parameters ( training_data )
test_data = read_file ( "2015_tme3_usps_test.txt" )
log_likelihood ( test_data[2][3], parameters[1] )
 -36631213.400524415
[ log_likelihood ( test_data[0][0], parameters[i] ) for i in range ( 10 ) ]
 [-80.594309481001218, -2030714328.0707991, -339.70961551873495, -373.97785273732529,
  -678.16479308314922, -364.62227994586954, -715.4508284953547,  -344286.66839952325,
  -499.88159107145611, -35419.208662902507]


5. Log-vraisemblance d'une image (bis)

Ecrivez une fonction log_likelihoods : float np.array x (float np.array,np.array) list -> float np.array qui, étant donné une image (donc un tableau de 256 nombres réels) et la liste de paramètres déterminés dans la question 3, renvoie un tableau contenant, pour chaque chiffre possible entre 0 et 9, la log-vraisemblance qu'aurait l'image si celle-ci correspondait à ce chiffre. Ainsi, si tab = log_likelihoods ( image, parameters ), tab est un tableau de 10 éléments (les 10 chiffres possibles) et tab[3] est égal à la log-vraisemblance de l'image dans la classe "chiffre = 3".

Vous pourrez vérifier que vous obtenez les mêmes résultats que ci-dessous:

log_likelihoods ( test_data[1][5], parameters )
 array([-889.22508387,  184.03163176, -185.29589129, -265.13424326,
        -149.54804688, -215.85994204,  -94.86965712, -255.60771575,
        -118.95170104,  -71.5970028 ])


6. Classification d'une image

Ecrivez une fonction classify_image : float np.array x (float np.array,np.array) list -> int qui, étant donné une image et l'ensemble de paramètres déterminés dans la question 3, renvoie la classe la plus probable de l'image, c'est-à-dire celle dont la log-vraisemblance est la plus grande.

Vous pourrez vérifier que vous obtenez les mêmes résultats que ci-dessous:

classify_image( test_data[1][5], parameters )
 1
classify_image( test_data[4][1], parameters )
 9



Partie optionnelle


7. Classification de toutes les images

Ecrivez maintenant une fonction classify_all_images : float np.array np.array np.array x (np.array,np.array) list -> float np.2D-array qui, étant donné le tableau test_data des images du fichiers 2015_tme3_usps_test.txt tel que retourné par la fonction read_file et l'ensemble de paramètres déterminés dans la question 3, renvoie un tableau numpy bi-dimensionnel T de taille 10x10 tel que T[i,j] représente le pourcentage d'images correspondant dans la réalité au chiffre i que votre classifieur a classées dans la classe j (pour tout i, {$\sum_{j=0}^{9}$} T[i,{$j$}] = 100%).

Vous pourrez vérifier que:

  • T[0,0] = 0.84958217
  • T[2,3] = 0.040404040404040407
  • T[5,3] = 0.050000000000000003


8. Affichage du résultat des classifications

Afin de visualiser les résultats obtenus par votre classifieur, exécutez la fonction suivante, qui prend en paramètres le tableau obtenu à la question précédente. Si votre classifieur est performant, vous devriez observer des pics sur la diagonale.

from mpl_toolkits.mplot3d import Axes3D

def dessine ( classified_matrix ):
    fig = plt.figure()
    ax = fig.add_subplot(111, projection='3d')
    x = y = np.linspace ( 0, 9, 10 )
    X, Y = np.meshgrid(x, y)
    ax.plot_surface(X, Y, classified_matrix, rstride = 1, cstride=1 )