Travaux pratiques : ranking¶
Partie 0 : Préambule¶
Le but de ce TP est d’apprenre un modèle classant des instances par rapport à une requête des plus similaires au plus dissimilaires. Nous nous placerons dans un contexte de classification multi-labels tel que dans le TP Fine Tuning.
Partant d’un ensemble d’instances \(\Omega = \{x_j\}\) (des images, du texte, des vecteurs…) et un ensemble de requêtes \(\mathcal Q\), on souhaite trouver une représentation \(y(x_j, q_i)\) telle que pour une requête \(q_i\), l’ordonnancement de \(\{y(x_j, q_i)\}_{x_j \in \Omega}\) corresponde au classement des \(x_j\) des plus proches au moins proche de \(q_i\).
Plus concrêtement, supposons que \(\Omega\) est composé de \(N\) objets étant soit des triangles, des ronds ou des carrés : \(\Omega = \{\triangle, \bigcirc, \square\}^N\). Notre requête \(q_i \in \bigcirc\) est un rond. On souhaite alors que classer les valeurs de \(\{y(x_j, q_i)\}_{1\leq j \leq N}\) de la plus grande à la plus petite permette d’ordonner \(\Omega\) de façon à avoir tous les \(x_j \in \bigcirc\) en tête de classement. Si on représente l’ensemble des instances par
on doit donc pouvoir avoir au final un ordonnacement de la forme :
Cette opération est correspond à peu prêt au travail d’un moteur de recherche qui va classer les résultats les plus similaires à une requêtes parmi un très grand nombre d’instances. Grossièrement on souhaite donc à mettre les éléments positifs, c’est-à-dire partageant la même classe en tête de classement.
Partie 1 : Average Precision¶
Une métrique classiquement utilisée pour juger de la qualité d’un ordonnancement est l’Average Precision (AP). La précision est donnée par le ratio entre le nombre d’instances positives sur le nombre total d’instances dans une séquence. L’AP est donnée par la moyenne des valeurs de précision pour les sous-ensembles de taille croissante correspondant à un nombre croissant de positifs. Par exemple pour un ordonnancement entre positifs et négatifs (indépendamment de leur classe) donné par:
l’AP est donnée par la moyenne des précisions pour chacun des sous-ensembles suivants :
$ + \(\Rightarrow\) Prec = 1/1 = 1
$ + + \(\Rightarrow\) Prec = 2/2 = 1
$ + + - - + \(\Rightarrow\) Prec = 3/5
$ + + - - + - + \(\Rightarrow\) Prec = 4/7
$ + + - - + - + + \(\Rightarrow\) Prec = 5/8
AP = ( 1 + 1 + 3/5 + 4/7 + 5/8 ) / 5
Chaque sous-ensemble est donné par l’apparition d’une nouvelle instance positive. On voit bien que dans le cas d’un classement parfait avec tous les positif en tête de classement l’AP vaut 1, sa valaur maximale. Par ailleurs \(AP\rightarrow 0\) lorsque tous les éléments positifs sont en fin de classement. Formellement, dans un cas binaire avec une seule requête tel que ci-dessus, l’AP est donnée par
où \(\mathcal P\) est l’ensemble des instances positives, \(\text{rank}(k)\) est le rang du \(k\)-ieme élément et \(\text{rank}^+(k)\) est le rang du \(k\)-ieme élément parmi les éléments positif. Si, à présent on cherche à évaluer les classements obtenus pour plusieurs requêtes, l’AP totale est donnée par la moyenne des AP pour chacune des \(M\) requêtes :
Partie 2 : optimisation de l’AP¶
Le calcul du rang rend l’AP non différentiable qui ne peut donc pas être directement optimisée. On peut toutefois constater que le rang peut être calculé de la façon suivante:
où \(H\) est la fonction de heaviside (en marche d’escalier) qui est définie de la façon suivante :
Cette fonction indique donc si une variable est positive. Appliquée à une différence de deux variables réelles, \(x\) et \(y\), \(H(x-y)\) indique donc si \(x\) est supérieur ou non à \(y\). Dans le calcul du rang précédent, pour la \(k^{ieme}\) instance, on compte donc le nombre d’éléments ayant une représentation \(y(x_j,q_i)\) plus proche que \(y(x_k,q_i)\).
Une approximation possible du rang peut donc être obtenue en approchant \(H\) par une sigmoïde \(\sigma\) donnant
Le but de ce TP est d’utiliser cette approximation du rang pour contruire une AP différentiable et donc utilisable comme loss pour un réseau de neurones.
Partie 3 : Implémentation de la Loss AP¶
Dans ce TP nous allons apprendre à ordonner les images de PascalVOC par rapport à la présence ou non d’une classe dans l’image. Les instances sont donc les images et les requêtes les classes du dataset. PascalVOC compte un total de 20 classes. Le coeur de l’exercice est donc d’implémenter une loss permettant de claculer l’AP pour un batch en prenant les classes présentes comme requête.
Ici, on suppose qu’on a en entrée une image contenant plusieurs objets de différentes classes parmi un nombre total de \(N_c\) classes. On suppose qu’on dispose d’un modèle \(f\) pour résoudre cette tâche. Dans ce cas, \(f\) produit en sortie un vecteur \(y \in \mathbb R^{C}\) dont chaque élément \(y_c\) d’indice \(c\) s’interpête comme un score indiquant que l’objet de classe \(c\) est ou non présent. Plus \(y_c\) est grand plus la classe est présente pour le modèle. Pour interpréter cette grandeur comme une probabilité, un modèle entraîné pour une tâche de classification standard ferait passer ce score dans une fonction sigmoïde cf. TP Fine Tuning. Ces scores sont également appelé logits.
Supposons, que nous disposions d’un batch d’images \(\boldsymbol x \in \mathbb R^{B\times H\times W \times C}\) où \(B\) est la taille du batch, \(H\) et \(W\) sont les dimensions de l’image. Après traitement par \(f\), nous avons donc un batch de vecteurs \(\boldsymbol y \in \mathbb R^{B \times C}\) dont chaque composante est un logit indiquant la présence ou l’abscence d’une classe dans l’image. Dans ce cas, pour calculer l’AP totale sur le batch, nous devons moyenner les AP obtenues pour chaque requête i.e. ici pour chaque classe.
import tensorflow as tf
from tensorflow import keras
import numpy as np
import sys
from matplotlib import pyplot as plt
Voici l’implémentation des fonctions sigmoïde et heaviside:
def tau_sigmoid(tensor, tau):
exponent = -tensor / tau
# clamp the input tensor for stability
exponent = 1. + tf.math.exp(tf.clip_by_value(exponent,-50, 50))
return 1.0 / exponent
def heaviside(tensor, val=1., target=None, general=None):
return np.heaviside(tensor,val)
Approximation du rang avec Tensorflow¶
Commençons par calculer l’approximation du rang pour un exemple. Supposons que l’on ait à disposition un batch de 10 vecteurs \(\boldsymbol y \in \mathbb R^{B\times Nc}\) de logits pour un problème de classification multilabels avec 3 classes. On veut connaître l’AP pour chacune des classes et donc calculer le rang de chaque image dans le batch pour toutes les classes. Par exemple, supposons que notre batch ressemble à cette matrice :
Class Id |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
---|---|---|---|---|---|---|---|---|---|---|
cat |
|
|
|
|
`` 9.1`` |
|
|
|
|
|
dog |
|
|
|
|
|
|
|
|
|
|
car |
|
|
|
|
|
|
|
|
|
|
Les valeurs correspondent pour chacun des 10 vecteur à \(\boldsymbol y(x_j,q_i)\) le score de proximité entre l’image \(j\) et la classe \(i\). Regardons la ligne pour le label cat. Vu les valeurs, on obtient le classement suivant:
Class Id |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
---|---|---|---|---|---|---|---|---|---|---|
cat |
2 |
5 |
4 |
8 |
1 |
6 |
7 |
3 |
0 |
9 |
où les instances sont ordonnées de la plus grande à la plus petite valeur. Pour calculer le rang d’une image \(k\) par rapport à une classe \(c\) avec la fonction sigmoïde, il faut donc avoir la différence entre \(y_c^k\) et \(y_c^j\) pour \(j\neq k\). En faisant le calcul pour toute les images on obtient alors la matrice de différences suivante pour la classe cat :

Ceci peut être obtenu avec Tensorflow de la façon suivante:
Bs = 10 # Taille de batch
y = tf.constant([-87.4, -32.6, 56.8, -78.9, 9.1, -3.5, -44.2, -55.6, -9.9, -100.0], dtype=tf.float32)
Delta = tf.reshape(y,(1,Bs)) - tf.reshape(y,(Bs,1))
Les fonctions tf.reshape(x,size)
permettent de modifer la taille du
vecteur x
. Ici, on s’en sert pour transposer et avoir
tf.reshape(y,(1,Bs))
qui soit un vecteur ligne et
tf.reshape(y,(Bs,1))
un vecteur colonne. La soustraction d’un
vecteur de taille \((1\times Bs)\) par un vecteur de taille
\((Bs\times 1)\) peut sembler étrange. En réalite, Tensorflow
interpête cette opération comme un broadcasting et construit la
matrice \(\Delta\) de taille \((Bs\times Bs)\) dont chaque
coefficient est donné par \(\Delta_{ij} = y_i - y_j\).
En réalite, en regardant la formule du calcul du rang, on ne somme que les différences entre le score pour l’instance \(k\) et les instances positives, c’est-à-dire les images contenant réellement la classe. Pour avoir cette information, il faut donc se référer aux vrais labels pour chaque image. Mettons qu’on ait la vérité terrain suivante :
Class Id |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
---|---|---|---|---|---|---|---|---|---|---|
cat |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
dog |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
car |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
On s’intéresse donc plutôt à la matrice suivante calculant les différences entre logits pour la classe cat mais seulement pour les images pour lesquelles la classe est présente. On obtient alors la matrice de différence \(\Delta\) suivante :

Chaque coefficient positif dans une ligne indique qu’il y a un élément ayant un meilleur score que l’image 2 ou 5. Compter tous ces éléments positifs nous donne donc l’indication du nombre d’éléments classés avant les éléments positifs 2 ou 5 considérés. Cette opération est équivalente à appliquer la fonction de Heaviside à chaque élément de \(\Delta\) et sommer sur les colonnes. On obtient alors
Écrivons les étapes correspondantes avec Tensorflow :
# Taille de batch
Bs = 10
# Instanciation des vecteurs
y = tf.constant([-87.4, -32.6, 56.8, -78.9, 9.1, -3.5, -44.2, -55.6, -9.9, -100.0], dtype=tf.float32)
labels = tf.constant([0, 0, 1, 0, 0, 1, 0, 0, 0, 0],dtype=tf.int16)
# extraction des logits correspondant aux classes présentes
y_pos = tf.boolean_mask(y, labels)
# calcul du nombre de positifs = nombre de classes présentes
Pos = tf.reduce_sum(labels,0)
# Calcul de la matrice de différence
Delta = tf.reshape(y,(1,Bs)) - tf.reshape(y_pos,(Pos,1)) # calcul de la matrice de différence shape(Pos,Bs)
La fonction tf.boolean_mask(x,y)
extrait les éléments de x
correspondant aux éléments valant True
dans le vecteur de booléens
y
. tf.reduce_sum(x,dim)
permet de sommer les éléments d’un
tenseur selon la dimension dim
.
Pour l’instant nous n’avons pas traîté le fait que \(\sigma(0) = \frac{1}{2}\), ce qui revient à artificiellement monter le classement de chaque instance (on n’a aussi fait comme si \(H(0)=0\) mais c’est un détail). Pour éviter ce problème, nous allons mettre à 0 les élément de Delta après avoir appliqué la fonction sigmoïde dessus. Le problème lorsque nous voudrons construire notre loss est que Tensorflow ne nous laisse pas modifier les éléments d’un tenseur à notre guise en allant directement modifier les coefficients qui nous intéressent. Par sécurité avec Tensorflow les tenseurs sont immutable (immuables). Nous pouvons nous y prendre autrement en calculant un masque dont les éléments de chaque ligne correspondant à l’instance concernée (image id=2 ou 5 dans l’exemple) sont nuls :
# Application de la fonction heaviside
Delta = heaviside(Delta)
# Initialisation du masque
mask = tf.ones_like(Delta,dtype='float')
# Calcul des indices à mettre à 0
## On récupère les indices des instances positives
cond = tf.where(labels)
## On construit un tableau d'indices associant à chaque ligne la position de l'instance concernée.
## Dans notre exemple, on doit avoir indices = [[0,1][2,5]]
indices = tf.concat([tf.expand_dims(tf.range(len(cond),dtype='int64'),axis=1),cond],axis=1)
## On met à zeros les valeurs aux indices souhaités dans mask
updates = tf.zeros(len(indices))
mask = tf.tensor_scatter_nd_update(mask, indices, updates, name='mask')
# On applique le masque à Delta
Delta *= mask
Calcul de l’AP¶
Nous avons fait le plus gros du travail dans notre exemple. Reste à faire la somme des colonnes de \(\Delta\) pour avoir \(\boldsymbol r = \sum_{k\in \mathcal P} rank(k)\) pour chaque \(k=2 ou 5\). On peut faire de même en ne gardant que les instances positives pour avoir \(\boldsymbol r^+ = \sum_{k\in \mathcal P} rank^+(k)\). La division terme à terme des vecteurs obtenus et la somme des colonnes donne au final \(AP = \frac{1}{|\mathcal P|} \sum_{k\in \mathcal P} \frac{\text{rank}^+(k)}{\text{rank}(k)}\) :
# On somme toutes les colonnes pour obtenir le rang pour chaque ligne
r = 1 + tf.reduce_sum(Delta,axis=1) # shape (Pos,)
# On somme toutes les colonnes parmi les positifs pour avoir rank^+
l_mask = tf.cast(labels,'float')
r_plus = 1 + tf.reduce_sum(Delta * tf.reshape(l_mask,(1,Bs)),axis=1) # shape (Pos,)
# On calcule l'AP du batch en sommant la division terme à terme de r et r_plus normalisé par le nombre total de positif
ap = tf.reduce_sum(r_plus / r) / tf.reduce_sum(l_mask) # shape (1,)
print(f"Valeur de l'average precision du bacth pour la classe cat: AP = {ap}")
Valeur de l'average precision du bacth pour la classe cat: AP = 0.8333333730697632
Dans cet exemple la valeur de l’AP est plutôt bonne bien qu’imparfaite du au grand score accordé à l’image Id=4.
Coding Task¶
Nous allons à présent utiliser toutes les briques vu précédement pour
implémenter notre loss pénalisant des valeur d’AP différentes de 1. À
vous de compléter la fonction suivante donnant l’approximation de l’AP
pour un batch de logit et les vraies labels associés donnés par
target
. La loss finale sera donnée par
ATTENTION on prendra ici la fonction sigmoïde et non la fonction heaviside pour calculer le rang.
def smooth_ap(target,logits,tau=0.2,alpha=1e-1,Nc=10):
"""
logits: output of a linear classifier shape (BS, Nc)
target: one-hot encoding shape (BS, Nc)
"""
Bs = tf.shape(target)[0]
ap_score = []
logits=tf.transpose(logits)
target=tf.transpose(target)
a = tf.zeros((Nc,1),dtype='int32')
indices = tf.concat([tf.expand_dims(tf.range(len(a)),axis=1),a],axis=1)
updates = tf.ones(len(indices))
target = tf.tensor_scatter_nd_update(target, indices, updates, name='target_update')
# On parcourt toutes les classes
for idx in range(Nc):
_lgts = logits[idx] # shape (Nc,)
_tgt = target[idx] # shape (Nc,)
# Calcul de la matrice de différence
Delta = ...
# Calcul du rang
r = ...
# Calcul du rang parmi les positifs
r_plus = ...
# Calcule l'AP du batch
ap = ...
ap_score.append(ap)
ap_score = tf.stack(ap_score) # shape Nc
loss = 1-tf.reduce_mean(ap_score)
return loss
Ranking sur PascalVOC¶
Nous allons maintenant tester cette loss pour fine tuner un resnet50 sur PascalVOC
!wget http://host.robots.ox.ac.uk/pascal/VOC/voc2007/VOCtrainval_06-Nov-2007.tar
--2022-06-02 11:32:26-- http://host.robots.ox.ac.uk/pascal/VOC/voc2007/VOCtrainval_06-Nov-2007.tar
Resolving host.robots.ox.ac.uk (host.robots.ox.ac.uk)... 129.67.94.152
Connecting to host.robots.ox.ac.uk (host.robots.ox.ac.uk)|129.67.94.152|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 460032000 (439M) [application/x-tar]
Saving to: ‘VOCtrainval_06-Nov-2007.tar’
VOCtrainval_06-Nov- 100%[===================>] 438,72M 6,02MB/s in 82s
2022-06-02 11:33:48 (5,34 MB/s) - ‘VOCtrainval_06-Nov-2007.tar’ saved [460032000/460032000]
!tar -xvf VOCtrainval_06-Nov-2007.tar
!wget http://host.robots.ox.ac.uk/pascal/VOC/voc2007/VOCtest_06-Nov-2007.tar
--2022-06-02 11:33:50-- http://host.robots.ox.ac.uk/pascal/VOC/voc2007/VOCtest_06-Nov-2007.tar
Resolving host.robots.ox.ac.uk (host.robots.ox.ac.uk)... 129.67.94.152
Connecting to host.robots.ox.ac.uk (host.robots.ox.ac.uk)|129.67.94.152|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 451020800 (430M) [application/x-tar]
Saving to: ‘VOCtest_06-Nov-2007.tar’
VOCtest_06-Nov-2007 100%[===================>] 430,13M 6,36MB/s in 1m 57s
2022-06-02 11:35:47 (3,68 MB/s) - ‘VOCtest_06-Nov-2007.tar’ saved [451020800/451020800]
!tar -xvf VOCtest_06-Nov-2007.tar
!wget http://cedric.cnam.fr/~thomen/cours/US330X/data_gen.py
--2022-06-02 12:35:37-- http://cedric.cnam.fr/~thomen/cours/US330X/data_gen.py
Resolving cedric.cnam.fr (cedric.cnam.fr)... 163.173.128.10
Connecting to cedric.cnam.fr (cedric.cnam.fr)|163.173.128.10|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 5351 (5,2K) [text/x-python]
Saving to: ‘data_gen.py.1’
data_gen.py.1 100%[===================>] 5,23K --.-KB/s in 0s
2022-06-02 12:35:37 (572 MB/s) - ‘data_gen.py.1’ saved [5351/5351]
import importlib
import data_gen
importlib.reload(data_gen)
data_dir = 'VOCdevkit/VOC2007/' # A changer avec votre chemin
data_generator_train = data_gen.PascalVOCDataGenerator('train', data_dir)
Coding Task¶
Retirer la dernière couche du modèle et la remplacer par une couche dense donnant une sortie de taille 20
from tensorflow.keras.applications.resnet50 import ResNet50
from tensorflow.keras.models import Model
from tensorflow.keras.models import Sequential
from tensorflow.keras.layers import Dense, Conv2D, MaxPooling2D, Flatten
# Load ResNet50 architecture & its weights
model = ResNet50(include_top=True, weights='imagenet')
# YOUR CODE HERE #
model = Model(inputs=model.input,outputs=x)
À présent on compile le modèle et on procède à l’entraînement
lr = 0.1
opt = keras.optimizers.Adam(learning_rate=lr)
model.compile(loss=smooth_ap, optimizer=opt,metrics=['binary_accuracy'])
batch_size=40
nb_epochs=10
data_generator_train = data_gen.PascalVOCDataGenerator('trainval', data_dir)
nb_batch = int(len(data_generator_train.id_to_label) / batch_size) + 1
model.fit(data_generator_train.flow(batch_size=batch_size),
steps_per_epoch=nb_batch,
epochs=nb_epochs,
verbose=1)
model.save('VOC_smoothAP')
Calculons pour finir l’AP sur les ensemble de train et de test
generator = data_generator_train.flow(batch_size=batch_size)
# Initilisation des matrices contenant les Deep Features et les labels
y_pred_train = np.zeros((len(data_generator_train.images_ids_in_subset),20))
y_train = np.zeros((len(data_generator_train.images_ids_in_subset),20))
y_pred_test = np.zeros((len(data_generator_train.images_ids_in_subset),20))
y_test = np.zeros((len(data_generator_train.images_ids_in_subset),20))
# Calcul du nombre de batchs
nb_batches = int(len(data_generator_train.images_ids_in_subset) / batch_size) + 1
for i in range(nb_batches):
# Pour chaque batch, on extrait les images d'entrée X et les labels y
X, y = next(generator)
bs = X.shape[0]
# On récupère les Deep Feature par appel à predict
y_pred_train[i*bs:(i+1)*bs,:] = model.predict(X)
y_train[i*bs:(i+1)*bs,:] = y
data_generator_test = data_gen.PascalVOCDataGenerator('test', data_dir)
generator = data_generator_test.flow(batch_size=batch_size)
nb_batches = int(len(data_generator_test.images_ids_in_subset) / batch_size) + 1
for i in range(nb_batches):
# Pour chaque batch, on extrait les images d'entrée X et les labels y
X, y = next(generator)
bs = X.shape[0]
# On récupère les Deep Feature par appel à predict
y_pred_test[i*bs:(i+1)*bs,:] = model.predict(X)
y_test[i*bs:(i+1)*bs,:] = y
Coding Task:¶
Calculer l’AP avec la fonction average_precision_score
de scikit
learn
from sklearn.metrics import average_precision_score
AP_train = np.zeros(20)
AP_test = np.zeros(20)
for c in range(20):
AP_train[c] = ...
AP_test[c] = ...
print("MAP TRAIN =", AP_train.mean()*100)
print("MAP TEST =", AP_test.mean()*100)