Travaux pratiques - Ordonnancement Structuré

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 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 \(\oplus\), label=1, e.g. les images de “potted plant”) soient classées devant les images non pertinentes (i.e \(\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 : http://cedric.cnam.fr/~thomen/cours/US330X/DF_ResNet50_VOC2007.npz) :

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 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 \(\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 :

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) :

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”) :

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 :

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))

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 \(\oplus\) et la classe \(\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) :

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 logo4

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 \(\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 \(\mathbf{d_i}\) représenté par un vecteur \(\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 \(\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 :

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 \(N_+\) le nombre d’images pertinentes (resp. \(N_-\) le nombre d’images non pertinentes), on peut associer à une sortie donnée un étiquetage binaire des images : les images \(\oplus\) sont celles \(\in \left\lbrace{O; N_+-1}\right\rbrace\) (de la liste ordonnée), les images \(\ominus\) celles \(\in \left\lbrace{N_+;N}\right\rbrace\), voir la fonction labelsfromranking.

Question :

Quelle est la sortie \(\mathbf{y}^* \in \mathcal{Y}\) donnée par la supervision ?

De manière identique, la sortie structurée \(\mathbf{y} \in \mathcal{Y}\) peut être représentée par une matrice de ranking \(\mathbf{Y}\) de taille \(N\times N\) tq :

(13)\[\begin{split}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}\end{split}\]

La fonction \(\Psi( \mathbf{x}, \mathbf{y})\) d’ordonnancement entre l’entrée \(\mathbf{x}\) et la sortie \(\mathbf{y}\) est définie de la manière suivante :

(14)\[\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]\]

Question :

Quelle est, en utilisant la représentation matricielle \(\mathbf{Y}\) de la sortie structurée donnée à l’Eq. (), la sortie \(\mathbf{Y}^* = \left\lbrace{y_{ij}^{*}}\right\rbrace\), \((i,j) \in \oplus \times \ominus\), donnée par la supervision à l’Eq. () ?

Inférence

On rappelle que la sortie prédite par le modèle consiste à résoudre le problème d’inférence, i.e. :

(15)\[\hat{\mathbf{y}}(\mathbf{x},\mathbf{w}) = \underset{\mathbf{y} \in \mathcal{Y}} {arg\,max} \langle \mathbf{w} , \Psi(\mathbf{x} ,\mathbf{y} ) \rangle\]

Question :

Quelle est la taille \(|\mathcal{Y}|\) de l’espace \(\mathcal{Y}\) pour la sortie du ranking structuré ? Peut-on faire l’inférence en effectuant un parcours exhaustif de l’espace \(\mathcal{Y}\) ? Montrer que la solution au problème d’inférence de l’Eq. () pour la fonction \(\Psi\) de ranking de l’Eq. () peut être obtenue en triant les exemples par ordre décroissant de \(\langle \mathbf{w} ,\boldsymbol{\phi(d_i)} \rangle\).

Classe SRanking

On s’appuiera sur la classe SRanking suivante :

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 <w,x>
        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. () 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. (). Bonus : pour avoir un calcul efficace, on pourra remarquer que la double somme dans le calcul de l’Eq. () revient à pondérer chaque exemple d’apprentissage par un facteur entier. Si on note par \(X\) la matrice des tous les exemples (taille \(N \times 784\)), on pourra donc calculer \(\alpha * X\), où \(\alpha\) est un vecteur colonne (taille \(N \times 1\)). On obtiendra \(\alpha\) de la manière suivante : pour chaque exemple \(d_i \in \oplus\) pertinent, on déterminera :

  • Le nombre d’exemples non pertinents \(N_-^b\) qui ont un rang inférieur à \(d_i\) (resp. \(N_-^a\) qui ont un rang supérieur à \(d_i\)).

  • Le poids de \(d_i\) sera \(N_-^a-N_-^b\).

  • Le poids de chaque exemple non pertinent ayant un rang inférieur à \(d_i\) sera incrémenté de 1.

  • Le poids de chaque exemple non pertinent ayant un rang supérieur à \(d_i\) sera décrémenté de 1.

Le vecteur final \(\Psi( \mathbf{x}, \mathbf{y})\) de l’Eq. () correspondra à sommer \(\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 \((\mathbf{\mathbf{x}},\mathbf{\mathbf{y^*}})\) et le LAI consiste en la maximisation suivante :

(16)\[\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]\]

\(\Psi(\mathbf{x}_i ,\mathbf{y} )\) est la feature map de ranking définie à l’Eq. (), et le loss \(\Delta(\mathbf{y}^*,\mathbf{y}) = 1-AP(\mathbf{y})\). La fonction lai prend en entrée la matrice \(X\) des données (taille \(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 [YFRJ07] :

  • On trie les exemples \(\oplus\) et \(\ominus\) par ordre de score décroissant. Pour cela on pourra utiliser le code suivant :

# Computing <w; x_i> 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 \(\ominus\) dans la liste des \(\oplus\) triés pour donner la solution optimale au problème LAI. On rappelle que le \(j^{\grave{e}me}\) exemple \(\ominus\) trié va être placé à la position \(i^{*}\) des exemples \(\oplus\) triés, avec \(i^{*} = \underset{i} {arg\,max} ~\delta_j(i)\):

(17)\[\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_-}\]

\(s_k^p\) est le score du \(k^{\grave{e}me}\) exemple \(\oplus\) trié, et \(s_j^n\) est le score du \(j^{\grave{e}me}\) exemple \(\ominus\) trié. Le code suivant va permettre de calculer l’insertion optimale de l’Eq. () :

# 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)

YFRJ07

Yisong Yue, Thomas Finley, Filip Radlinski, and Thorsten Joachims. A support vector method for optimizing average precision. In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR “07, 271–278. New York, NY, USA, 2007. ACM. doi:10.1145/1277741.1277790.