Travaux pratiques : ranking

Cahier Jupyter

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

\[\Omega = \square \bigcirc \triangle \triangle \bigcirc \triangle \square \square \bigcirc ,\]

on doit donc pouvoir avoir au final un ordonnacement de la forme :

\[\underbrace{ q_j = \bigcirc}_{\text{requête}} | \underbrace{\bigcirc \bigcirc \bigcirc \triangle \square \square \triangle \square \triangle}_{\text{instances} \in \Omega} .\]

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

\[AP = \frac{1}{|\mathcal P|} \sum_{k\in \mathcal P} \text{Prec}(k) = \frac{1}{|\mathcal P|} \sum_{k\in \mathcal P} \frac{\text{rank}^+(k)}{\text{rank}(k)},\]

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 :

\[AP = \frac{1}{M} \sum_{i=1}^M AP_i.\]

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:

\[rank(k) = 1 + \sum_{j\in \mathcal P \setminus \{k\} } H (y(x_j,q_i) - y(x_k,q_i) ) = 1 + \sum_{j\in \mathcal P \setminus \{k\} } H (y_j - y_k ),\]

où \(H\) est la fonction de heaviside (en marche d’escalier) qui est définie de la façon suivante :

\[\begin{split}\forall x \in \mathbb R, H(x) = \begin{cases} 0 \text{ si } x < 0 \\ 1 \text{ si } x > 0 \end{cases}.\end{split}\]

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

\[\widehat{rank}(k) = 1 + \sum_{j\in \mathcal P \setminus \{k\} } \sigma (y_j - y_k ).\]

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	-8 7.4	-3 2.6	5 6.8	-7 8.9	`` 9.1``	- 3.5	-4 4.2	-5 5.6	- 9.9	-10 0.0
dog	2 2.8	-8 8.3	-9 9.9	- 2.2	-4 9.1	3 3.1	7 3.7	- 0.8	-9 0.6	8 8.8
car	-10 0.0	-5 4.8	-3 5.2	-9 9.9	-3 2.1	-9 8.9	-6 6.4	-5 6.6	4 9.2	-3 3.5

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

\[H(\Delta) = [1 , 3].\]

É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

\[\mathcal L = 1 - AP\]

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)