.. _chap-tpDeepLearning7: ############################################################################## Travaux pratiques - Ordonnancement Structuré ############################################################################## .. L'objectif de ce TME est d'utiliser les réseaux convolutifs profonds pour résoudre des taches de prédiction structurée, c'est à dire pour lesquelles les variables de sortie sont corrélées. On va ici considérer un problème **d'ordonnancement** (*ranking*), et on va utiliser une instanciation pour apprendre un modèle de prédiction structurée dont l'objectif sera de minimiser la **précision moyenne**, *Average Precision* (AP). .. Plus précisément, on considère un problème d'ordonnancement où les différents exemples (ici images de MNIST) présentent un **étiquetage binaire de pertinence** par rapport à une requête : typiquement la requête va correspondre à une classe (par exemple la classe des images de 8), et l'objectif de l'ordonnancement est de trier les images de sorte que les images pertinentes (label=1, *e.g.* les 8) soient classées devant les images non pertinentes (label=0, *e.g.* celles des autres classes que les 8). Plus précisément, on considère un problème d'ordonnancement où les différents exemples (ici images de la base VOC'07) présentent un **étiquetage binaire de pertinence** par rapport à une requête : typiquement la requête va correspondre à une classe (par exemple la classe des images de 'potted plant'), et l'objectif de l'ordonnancement est de trier les images de sorte que les images pertinentes (*i.e* :math:`\oplus`, label=1, *e.g.* les images de 'potted plant') soient classées devant les images non pertinentes (*i.e* :math:`\ominus`, label=0, *e.g.* celles des autres classes que la classe 'potted plant'). Exercice 0 : Modèle *baseline* et mesure d'\ *Average Precision* (AP) ***************************************************************************************** On va considérer les images de la base VOC'07, et télécharger les "Deep Features" calculées au TP5 : ``_) : .. code-block:: python outfile = 'DF_ResNet50_VOC2007.npz' npzfile = np.load(outfile) X_train = npzfile['X_train'] Y_train = npzfile['Y_train'] X_test = npzfile['X_test'] Y_test = npzfile['Y_test'] print "X_train=",X_train.shape, "Y_train=",Y_train.shape, " X_test=",X_test.shape, "Y_train=",Y_test.shape .. On va commencer par considérer une catégorie de la base MNIST comme la requête (*e.g.* les images de la classe 8). On se ramène donc à un problème de classification binaire, et le code suivant permet d'obtenir les données et labels binaire : .. .. code-block:: python .. from keras.datasets import mnist .. (X_train, y_train), (X_test, y_test) = mnist.load_data() .. X_train = X_train.reshape(60000, 784) .. X_test = X_test.reshape(10000, 784) .. X_train = X_train.astype('float32') .. X_test = X_test.astype('float32') .. X_train /= 255 .. X_test /= 255 .. # Class corresponding to the query .. c = 8 .. # Generate binary labels for class c .. y_trainb = np.zeros(60000) .. y_testb = np.zeros(10000) .. y_trainb[y_train==c] = 1 .. y_trainb[y_train!=c] = 0 .. y_testb[y_test==c] = 1 .. y_testb[y_test!=c] = 0 On va considérer une classe comme étant la requête, par exemple la classe 'potted plant' : l'objectif va alors être d'entraîner un modèle pour prédire les images pertinentes (*i.e* :math:`\oplus`, *e.g.* celles de la classe 'potted plant'), et les images non pertinentes. Pour cela nous allons mettre en place un modèle linéaire de classification binaire : on définiera un modèle simple de régression logistique binaire, *i.e.* un réseau de neurones avec un seul neurone de sortie et une fonction d'activation sigmoïde. On décrit d'abord l'architecture du modèle : .. code-block:: python from keras.models import Sequential from keras.layers import Dense, Activation from keras.optimizers import SGD model = Sequential() model.add(Dense(1, input_dim=2048, name='fc1')) model.add(Activation('sigmoid')) model.summary() Puis on le compile (on choisit ici le loss ``binary_crossentropy``) : .. code-block:: python from keras.optimizers import SGD learning_rate = 0.5/20 sgd = SGD(learning_rate) model.compile(loss='binary_crossentropy',optimizer=sgd,metrics=['binary_accuracy']) Et on l'entraîne sur les données d'apprentissage (ici les labels binaires de classe considérée, *e.g* 'potted plant') : .. code-block:: python c=15 # index of 'potted plant' class batch_size = 100 nb_epoch = 20 model.fit(X_train, Y_train[:,c],batch_size=batch_size, epochs=nb_epoch,verbose=1) On peut ensuite évaluer les performances de la métrique ``binary_accuracy`` en apprentissage et en test : .. code-block:: python scorestrain = model.evaluate(X_train, Y_train[:,c], verbose=0) scorestest = model.evaluate(X_test, Y_test[:,c], verbose=0) print("perfs train - %s: %.2f%%" % (model.metrics_names[1], scorestrain[1]*100)) print("perfrs test - %s: %.2f%%" % (model.metrics_names[1], scorestest[1]*100)) .. admonition:: Question : Expliquer pourquoi la métrique précédente n'est pas adpatée pour évaluer les performance d'un classifieur binaire avec un déséquilibre important entre la classe :math:`\oplus` et la classe :math:`\ominus`. **On va ici s'intéresser à mesurer l'Average Precision (AP)** du modèle précédemment appris. Intuitivement l'AP mesure l'ordonnancement correct des exemples, *i.e.* le fait que les exemples pertinents aient un score supérieur aux exemples non pertinents. On va pour cela tracer une courbe **Précision-Rappel (Precision-Recall)**, qui va calculer pour chaque valeur de score s : - Le rappel, *i.e.* le nombre d'éléments pertinents sur le nombre d’éléments total qui ont un score supérieur à s, - La précision, *i.e.* le nombre d'éléments pertinents qui ont un score supérieur à s sur le nombre total d’éléments pertinents. **L'Average Precision (AP)** correspond à **l'aire sous la courbe Précision-Rappel**. On peut tracer la courbe Précision-Rappel, la visualiser et calculer l'AP avec le code suivant (sur la base d'apprentissage, à adapter pour avoir le résultat sur la base de test) : .. code-block:: python from sklearn.metrics import average_precision_score from sklearn.metrics import precision_recall_curve import matplotlib.pyplot as plt LABELS = ['aeroplane', 'bicycle', 'bird', 'boat', 'bottle', 'bus', 'car', 'cat', 'chair', 'cow', 'diningtable', 'dog', 'horse', 'motorbike', 'person', 'pottedplant', 'sheep', 'sofa', 'train', 'tvmonitor'] # Computing prediction for the training set predtrain = model.predict(X_train) # Computing precision recall curve precision, recall, _ = precision_recall_curve(Y_train[:,c], predtrain) # Computing Average Precision AP_train = average_precision_score(Y_train[:,c], predtrain) print "Class ",c," - Average Precision TRAIN=", AP_train*100.0 plt.clf() plt.plot(recall, precision, lw=2, color='navy',label='Precision-Recall curve') plt.xlabel('Recall') plt.ylabel('Precision') plt.ylim([0.0, 1.05]) plt.xlim([0.0, 1.0]) plt.title('PR curve - CLASS '+LABELS[c]+': TRAIN AUC={0:0.2f}'.format(AP_train*100.0)) plt.legend(loc="lower left") plt.show() Voici un exemple de résultat obtenu sur la base d'apprentissage et de test : .. |logo3| image:: _images/AP_TRAIN_VOC_PP.png :height: 300px :width: 480px .. |logo4| image:: _images/AP_TEST_VOC_PP.png :height: 300px :width: 480px | |logo3| |logo4| .. admonition:: Question : Quelle est la propriété intéressante de la métrique AP, par exemple par rapport à d’autres métriques comme l’aire sous la courbe ROC (*Area Under Curve*, AUC)? Exercice 1 : Instanciation de prédiction structurée pour de l’ordonnancement ***************************************************************************************** On va maintenant s’intéresser à mettre en place une instanciation d’un modèle de prédiction structurée pour de l’ordonnancement (*ranking*) évalué avec une métrique d’Average Precision (AP). Formellement, dans cette instanciation : - L’entrée :math:`\mathbf{x} \in \mathcal{X} = \left\lbrace{ \mathbf{d_1},...,\mathbf{d_N} }\right\rbrace` est un ensemble de N documents (images), où chaque document :math:`\mathbf{d_i}` représenté par un vecteur :math:`\boldsymbol{\phi(d_i)} \in \mathbb{R}^d` (dans notre cas de taille 2048). On aura donc lors de l’entraînement un seul exemple constitué de l’ensemble des images. - La sortie structurée :math:`\mathbf{y} \in \mathcal{Y}` représente l'ordonnancement de pertinence de chacun des N documents par rapport à une requête : dans notre cas la requête correspond à une classe d’images (par exemple, ordonner toutes les images de la classe 'potted plant'). Cette sortie sera donc représentée par une liste ordonnée dans laquelle les indices des images apparaissent par ordre de pertinence décroissant par rapport à la requête. On pourra utiliser la classe ``RankingOutput`` pour représenter la sortie structurée : .. code-block:: python class RankingOutput(): ranking = [] nbPlus=0 def __init__(self,ranking,nbPlus): self.nbPlus = nbPlus self.ranking = ranking def labelsfromranking(self): labels = [0 for i in range(len(self.ranking))] for i in range(self.nbPlus): labels[self.ranking[i]]=1 return labels def __getitem__(self, key): return self **N.B.** : Soit :math:`N_+` le nombre d’images pertinentes (resp. :math:`N_-` le nombre d’images non pertinentes), on peut associer à une sortie donnée un étiquetage binaire des images : les images :math:`\oplus` sont celles :math:`\in \left\lbrace{O; N_+-1}\right\rbrace` (de la liste ordonnée), les images :math:`\ominus` celles :math:`\in \left\lbrace{N_+;N}\right\rbrace`, voir la fonction ``labelsfromranking``. .. admonition:: Question : Quelle est la sortie :math:`\mathbf{y}^* \in \mathcal{Y}` donnée par la supervision ? .. réponse : les images + placées devant les -, après n’importe quelle permutation des + ou - convient. De manière identique, la sortie structurée :math:`\mathbf{y} \in \mathcal{Y}` peut être représentée par une matrice de ranking :math:`\mathbf{Y}` de taille :math:`N\times N` tq : .. math:: y_{ij} = \begin{cases} +1 & \mbox{si } d_i \prec_{y} d_j \mbox{ ($d_i$ est classé avant $d_j$ dans la liste ordonnée)}\\ -1 & \mbox{si } d_i \succ_{y} d_j \mbox{ ($d_i$ est classé après $d_j$)} \end{cases} :label: rankigmatrice La fonction :math:`\Psi( \mathbf{x}, \mathbf{y})` d'ordonnancement entre l'entrée :math:`\mathbf{x}` et la sortie :math:`\mathbf{y}` est définie de la manière suivante : .. math:: \Psi( \mathbf{x}, \mathbf{y}) = \frac{1}{N_+ \cdot N_-}\sum\limits_{d_i \in \oplus} \sum\limits_{d_j \in \ominus} y_{ij} \left[ \boldsymbol{\phi(d_i)} - \boldsymbol{\phi(d_j)} \right] :label: jointfeatureranking .. admonition:: Question : Quelle est, en utilisant la représentation matricielle :math:`\mathbf{Y}` de la sortie structurée donnée à l’Eq. :eq:`rankigmatrice`, la sortie :math:`\mathbf{Y}^* = \left\lbrace{y_{ij}^{*}}\right\rbrace`, :math:`(i,j) \in \oplus \times \ominus`, donnée par la supervision à l’Eq. :eq:`jointfeatureranking` ? Inférence ############ On rappelle que la sortie prédite par le modèle consiste à résoudre le problème **d'inférence**, *i.e.* : .. math:: \hat{\mathbf{y}}(\mathbf{x},\mathbf{w}) = \underset{\mathbf{y} \in \mathcal{Y}} {arg\,max} \langle \mathbf{w} , \Psi(\mathbf{x} ,\mathbf{y} ) \rangle :label: predictionstruct2 .. admonition:: Question : Quelle est la taille :math:`|\mathcal{Y}|` de l’espace :math:`\mathcal{Y}` pour la sortie du ranking structuré ? Peut-on faire l’inférence en effectuant un parcours exhaustif de l’espace :math:`\mathcal{Y}` ? Montrer que la solution au problème d’inférence de l’Eq. :eq:`predictionstruct2` pour la fonction :math:`\Psi` de ranking de l’Eq. :eq:`jointfeatureranking` peut être obtenue en triant les exemples par ordre décroissant de :math:`\langle \mathbf{w} ,\boldsymbol{\phi(d_i)} \rangle`. Classe ``SRanking`` ##################### On s’appuiera sur la classe ``SRanking`` suivante : .. code-block:: python import numpy as np from keras.utils import np_utils from sklearn.metrics import average_precision_score from sklearn.metrics import precision_recall_curve class SRanking(SModel): def __init__(self, rankingoutput, d, size, learning_rate=0.1, epochs=2): SModel.__init__(self,learning_rate, epochs, size) # Ground Truth labels self.rankingoutput = rankingoutput self.d = d self.w = np.array([0 for i in range(d)]) print "w=",self.w.shape, "d=",d, "nb ex=",len(self.rankingoutput.ranking), " nbPlus=",self.rankingoutput.nbPlus def predict(self, X): # Inference: sorting elts wrt pred = -1.0*np.matmul(X,self.w) # When predicting, number of + unknown, setting it to default value 0 return RankingOutput(list(np.argsort(pred[:])),0) def delta(self, y1, y2): # y2 assumed to be ground truth, y1 predicted ranking labels = y2.labelsfromranking() pred = [0 for i in range(len(y1.ranking)) ] for i in range(len(y1.ranking)): pred[y1.ranking[i]] = -i return 1.0- average_precision_score(labels, pred) def psi(self, X, output): # COMPLETE WITH YOUR CODE def lai(self, X, Y): # COMPLETE WITH YOUR CODE où la fonction ``predict`` fait l’inférence de l’Eq. :eq:`predictionstruct2` en effectuant le tri des exemples précédemment indiqué, et la fonction ``delta`` s’appuie sur l’Average Precision (AP) pour calculer la dissimilarité entre y2 (supposée être la sortie donnée par la supervision) et y1 (la sortie prédite). Mise en place de la fonction ``psi`` ###################################### On demande ici d’implémenter la fonction ``psi`` de l’Eq. :eq:`jointfeatureranking`. **Bonus** : pour avoir un calcul efficace, on pourra remarquer que la double somme dans le calcul de l’Eq. :eq:`jointfeatureranking` revient à pondérer chaque exemple d’apprentissage par un facteur entier. Si on note par :math:`X` la matrice des tous les exemples (taille :math:`N \times 784`), on pourra donc calculer :math:`\alpha * X`, où :math:`\alpha` est un vecteur colonne (taille :math:`N \times 1`). On obtiendra :math:`\alpha` de la manière suivante : pour chaque exemple :math:`d_i \in \oplus` pertinent, on déterminera : - Le nombre d’exemples non pertinents :math:`N_-^b` qui ont un rang inférieur à :math:`d_i` (resp. :math:`N_-^a` qui ont un rang supérieur à :math:`d_i`). - Le poids de :math:`d_i` sera :math:`N_-^a-N_-^b`. - Le poids de chaque exemple non pertinent ayant un rang inférieur à :math:`d_i` sera incrémenté de 1. - Le poids de chaque exemple non pertinent ayant un rang supérieur à :math:`d_i` sera décrémenté de 1. Le vecteur final :math:`\Psi( \mathbf{x}, \mathbf{y})` de l’Eq. :eq:`jointfeatureranking` correspondra à sommer :math:`\alpha * X` sur les lignes, pour obtenir un vecteur de taille 784. Mise en place de la fonction ``lai`` ###################################### On rappelle que pour entraîner un modèle de prédiction structurée, il faut résoudre le problème du **"Loss-Augmented Inference" (LAI)**. Dans le cas de l’ordonnancement, on dispose d’un unique exemple d'apprentissage :math:`(\mathbf{\mathbf{x}},\mathbf{\mathbf{y^*}})` et le LAI consiste en la maximisation suivante : .. math:: \tilde{\mathbf{y}} = \underset{\mathbf{y} \in \mathcal{Y}} {arg\,max} \left[ \Delta(\mathbf{y}^*,\mathbf{y}) + \langle \mathbf{w} , \Psi(\mathbf{x} ,\mathbf{y} ) \rangle \right] :label: lai2 où :math:`\Psi(\mathbf{x}_i ,\mathbf{y} )` est la *feature map* de *ranking* définie à l’Eq. :eq:`jointfeatureranking`, et le *loss* :math:`\Delta(\mathbf{y}^*,\mathbf{y}) = 1-AP(\mathbf{y})`. La fonction ``lai`` prend en entrée la matrice :math:`X` des données (taille :math:`N \times 784`) et la sortie donnée par la supervision. On rappelle que le LAI peut être résolu dans ce cas de la manière suivante, en utilisant l’algorithme glouton optimal proposé dans :cite:`Yue:2007` : - On trie les exemples :math:`\oplus` et :math:`\ominus` par ordre de score décroissant. Pour cela on pourra utiliser le code suivant : .. code-block:: python # Computing for all examples pred = np.matmul(X,self.w) # Getting corresponding labels from ranking output Y labels = Y.labelsfromranking() # Dict structure dict = {i : pred[i] for i in range(len(labels))} iplus = np.where(np.array(labels[:])==1)[0] iminus = np.where(np.array(labels[:])==0)[0] nbPlus = len(iplus) nbMinus = len(iminus) nbTot = nbPlus+nbMinus dictplus = {i:dict[i] for i in iplus} dictminus = {i:dict[i] for i in iminus} # Sorting dict for + examples and - examples dictplus_s = sorted(dictplus.iteritems(), key=lambda (k,v): (v,k), reverse=True) dictminus_s = sorted(dictminus.iteritems(), key=lambda (k,v): (v,k), reverse=True) - On va trouver l’insertion optimale de chacun des exemples :math:`\ominus` dans la liste des :math:`\oplus` triés pour donner la solution optimale au problème LAI. On rappelle que le :math:`j^{\grave{e}me}` exemple :math:`\ominus` trié va être placé à la position :math:`i^{*}` des exemples :math:`\oplus` triés, avec :math:`i^{*} = \underset{i} {arg\,max} ~\delta_j(i)`: .. math:: \delta_j(i) = \frac{1}{N_+} \sum_{k=i}^{N_+} \left( \frac{j}{k+j} -\frac{j-1}{k+j-1} \right) - \frac{2 (s_k^p - s_j^n)}{N_-} :label: laidelta où :math:`s_k^p` est le score du :math:`k^{\grave{e}me}` exemple :math:`\oplus` trié, et :math:`s_j^n` est le score du :math:`j^{\grave{e}me}` exemple :math:`\ominus` trié. Le code suivant va permettre de calculer l'insertion optimale de l’Eq. :eq:`laidelta` : .. code-block:: python # Initializing list with + examples list_lai = [dictplus_s[i][0] for i in range(len(dictplus_s))] # Computing delta2 for each (+/-) pair in Eq 5 delta1 = 1.0/nbPlus* np.array( [[ ( float(j) / float(j+i) - (j-1.0)/(j+i-1.0)) - ( 2.0* (dictplus_s[i-1][1] - dictminus_s[j-1][1])/(nbMinus) ) for j in range(1,nbMinus+1) ] for i in range(1,nbPlus+1)]) delta2 = delta1 for i in range(nbPlus-2,-1,-1): delta2[i,:] = delta2[i,:] + delta2[i+1,:] # i* = argmax_i delta2 for all - examples res = np.argmax(delta2,axis=0) # If optimal value is <0, insert after the last + example a = [delta2[res[j],j] for j in range(nbMinus)] indexin = np.where(np.array(a[:])<0)[0] res[indexin] +=1 # Creating the final list for j in range(len(iminus)): list_final.insert(res[j]+j, dictminus_s[j][0]) # Returning it as a RankingOutput class return RankingOutput(list_lai,Y.nbPlus) .. bibliography:: refs7.bib :cited: