Travaux pratiques - Prédiction Structurée

Dans ce TP, on va mettre en place un modèle de prédiction structuré de type SVM structuré [TJHA05]. On rappelle tout d’abord la formulation générale du problème de prédiction structurée.

Modèle de prédiction. L’objectif est d’estimer une sortie y appartenant à un espace \(\mathbf{\mathcal{Y}}\) structuré discret à partir d’une entrée \(\mathbf{x}\) appartenant à un espace \(\mathbf{\mathcal{X}}\) quelconque. On suppose que la relation entre l’entrée \(\mathbf{x}\) et la sortie \(\mathbf{y}\) est modélisée une joint feature map \(\Psi( \mathbf{x},\mathbf{y}) \in \mathbb{R}^d\). On considère un modèle de prédiction linéaire qui assigne le score \(\langle \mathbf{w} , \Psi( \mathbf{x},\mathbf{y}) \rangle\) à chaque paire \((\mathbf{x},\mathbf{y}) \in (\mathbf{\mathcal{X}} \times \mathbf{\mathcal{Y}})\). La sortie prédite par le modèle consiste à résoudre le problème d’inférence, i.e. :

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

Apprentissage du modèle. La dissimilarité entre deux sorties \(\mathbf{y_1}\) et \(\mathbf{y_2}\) est modélisée par une fonction de coût \(\Delta(\mathbf{y_1},\mathbf{y_2})\). Dans un contexte d’apprentissage supervisé, on dispose d’un ensemble de N paires \((\mathbf{\mathbf{x_i}},\mathbf{\mathbf{y_i^*}})\) annotées et on cherche à déterminer les paramètres \(\mathbf{w}\) minimisant la dissimilarité \(\Delta\left( \hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w}) ,\mathbf{y_i^*}\right)\) entre la sortie prédite par le modèle \(\hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w})\) et la sortie donnée par la supervision \(\mathbf{y_i^*}\). La fonction \(\Delta\left( \hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w}\right) ,\mathbf{y_i})\) étant difficile à optimiser par rapport à \(\mathbf{w}\), la méthode dite de margin rescaling permet d’en dériver une borne supérieure convexe \(\ell(\mathbf{x}_i,\mathbf{y}_i^*;\mathbf{w}) \geq \Delta\left( \hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w}\right) ,\mathbf{y_i})\) :

\[\ell(\mathbf{x}_i,\mathbf{y}_i^*;\mathbf{w}) = \underset{\mathbf{y} \in \mathcal{Y}} \max \left[ \Delta\left(\mathbf{y},\mathbf{y_i^*}\right) + \langle \mathbf{w} , \Psi(\mathbf{x_i}, \mathbf{y}) \rangle \right] - \langle \mathbf{w} , \Psi(\mathbf{x_i},\mathbf{y_i^*}) \rangle\]

A partir de la borne supérieure convexe \(\ell(\mathbf{x}_i,\mathbf{y}_i^*;\mathbf{w})\) dérivée de \(\Delta\left( \hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w})\right)\) pour chaque exemple d’apprentissage, la fonction objectif régularisée \(\mathcal{P}(\mathbf{w})\) à minimiser pour entraîner le modèle est la suivante :

(11)\[\mathcal{P}(\mathbf{w}) = \frac{\lambda}{2} \|\mathbf{w}\|^2 + \frac{1}{N} \sum_{i=1}^N \left[ \underset{\mathbf{y} \in \mathcal{Y}}{\text{max }} \left[\Delta(\mathbf{y}_i^*,\mathbf{y}) + \langle \mathbf{w} , \Psi(\mathbf{x}_i,\mathbf{y})\rangle \right] - \langle \mathbf{w} , \Psi(\mathbf{x}_i,\mathbf{y}_i^*) \rangle \right]\]

La minimisation de la fonction objectif de l’Eq. (11) va nécessiter la résolution du problème de « Loss-Augmented Inference » (LAI) pour chaque exemple d’apprentissage \((\mathbf{\mathbf{x_i}},\mathbf{\mathbf{y_i^*}})\), i.e. :

(12)\[\tilde{\mathbf{y}_i} = \underset{\mathbf{y} \in \mathcal{Y}} {arg\,max} \left[ \Delta(\mathbf{y}_i^*,\mathbf{y}) + \langle \mathbf{w} , \Psi(\mathbf{x}_i ,\mathbf{y} ) \rangle \right]\]

Exercice 0 : Modèle générique de prédiction structurée

La fonction de prédiction de l’Eq. (10) et la formulation d’apprentissage de l’Eq. (11) sont génériques. On va s’appuyer sur la classe SModel pour utiliser et entraîner un modèle de prédiction structuré générique :

from abc import ABCMeta, abstractmethod
import numpy as np

class SModel:
  _metaclass__ = ABCMeta
  w=[]
  # Batch size
  tbatch = 10
  nbatch=0
  epochs = 10
  # Gradient step
  eta = 0.1
  # Regularization parameter
  llambda = 1e-6

  # Joint feature map Psi(x,y) in R^d
  @abstractmethod
  def psi(self, X, Y):
      pass

  # Loss-Augmented Inference (LAI):  arg max_y [<w, Psi(x,y)> + Delta(y,y*)]
  @abstractmethod
  def lai(self, X, Y):
     pass

  # Inference: arg max_y [<w, Psi(x,y)>]
  @abstractmethod
  def predict(self, X):
      pass

  @abstractmethod
  # Loss between two outputs
  def delta(self, Y1, Y2):
      pass

  def __init__(self, learning_rate=0.1, epochs=2, tbatch=100):
      self.eta=learning_rate
      self.epochs = epochs
      self.tbatch = tbatch


  def fit(self, X, Y):

      self.nbatch = X.shape[0]  / self.tbatch

      for i in range(self.epochs):
          for b in range(self.nbatch):
              # Computing joint feature map psi for groud truth output
              psi2 = self.psi(X[b*self.tbatch:(b+1)*self.tbatch,:], Y[b*self.tbatch:(b+1)*self.tbatch])
              # Computing most violated constraint => LAI
              yhat = self.lai(X[b*self.tbatch:(b+1)*self.tbatch,:], Y[b*self.tbatch:(b+1)*self.tbatch])
               # Computing joint feature map psi for LAI output
              psi1 = self.psi(X[b*self.tbatch:(b+1)*self.tbatch,:], yhat)
              # Computing gradient
              grad = self.llambda*self.w + (psi1-psi2)

              self.w = self.w - 1.0*self.eta * (grad)

          pred = self.predict(X)
          print "epoch ",i, " perf train=",(1.0-self.delta(pred, Y))*100.0, " norm W=",np.sum(self.w*self.w)

La classe SModel est abstraite, en particulier car les méthodes psi, predict, lai, et delta le sont. Ces méthodes seront définies dans les classes dérivés de SModel, qui correspondront à une instanciation particulière du modèle de prédiction structuré.

En dépit du caractère non défini des méthodes précédentes, on pourra utiliser le code fourni dans la méthode fit pour entraîner le modèle, i.e. minimiser l’Eq. (11). La fonction objectif définie à l’Eq. (11) étant convexe par rapport aux paramètres \(\mathbf{w}\) du modèle, une descente de gradient permettra de trouver le minimum global de la fonction.

La fonction fit consiste donc à effectuer, pour chaque sous-ensemble des données d’apprentissage (batch), les opérations suivantes :

  • Calcul de la fonction psi qui prend en paramètre un batch d’exemple \(\mathbf{X}\) et un batch de labels donné par la supervision \(\mathbf{Y^*}\), et renvoie la fonction renvoie la joint feature map \(\Psi\) moyennée sur l’ensemble du batch , i.e. \(\Psi_2 = \frac{1}{t_b} \sum\limits_{i=1}^{t_b} \Psi(\mathbf{x_i},\mathbf{y_i^*})\).

  • Calcul du problème de Loss-Augmented Inference (LAI), cf Eq. (12), pour l’ensemble des exemples du batch, i.e. \(\tilde{\mathbf{y}_i} = \underset{\mathbf{y} \in \mathcal{Y}} {arg\,max} \left[ \Delta(\mathbf{y}_i^*,\mathbf{y}) + \langle \mathbf{w} , \Psi(\mathbf{x}_i ,\mathbf{y} ) \rangle \right]\), \(\forall i \in \left\lbrace 1 ; t_b\right\rbrace\). La fonction lai revoie donc une matrice de taille \(t_b \times 1\).

  • Calcul de la fonction psi qui prend en paramètre un batch d’exemple \(\mathbf{X}\) et un batch de labels correspondant au résultat du LAI précédemment calculé \(\mathbf{\hat{Y}}\), et renvoie la fonction renvoie la « joint feature map » \(\Psi\) moyennée sur l’ensemble du batch , i.e. \(\Psi_1 = \frac{1}{t_b} \sum\limits_{i=1}^{t_b} \Psi(\mathbf{x_i},\mathbf{\tilde{y_i}})\).

  • Calcul du gradient de la fonction objectif de l’équation (11) par rapport à \(\mathbf{w}\) : \(\frac{\partial \mathcal{P}}{\partial \mathbf{w}} = \lambda \mathbf{w} + (\Psi_1-\Psi_2)\), et mise à jour des paramètres : \(\mathbf{w}^{(t+1)} = \mathbf{w}^{(t)} - \eta \frac{\partial \mathcal{P}}{\partial \mathbf{w}}\).

Exercice 1 : Instanciation en classification multi-classes

On demande dans cet exercice d’instancier le modèle de prédiction générique donné dans l’exercice 0 pour résoudre un problème de classification multi-classes, qu’on appliquera à la reconnaissance de chiffres manuscrits sur MNIST. On rappelle que le chargement des données et étiquettes (labels) peut être obtenu de la manière suivante :

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

On demande de compléter le code de la classe SXclass qui hérite de SModel pour instancier un modèle de classification multi-classes. Dans notre cas de classification multi-classes :

  • L’entrée \(\mathbf{x}\) correspond à l’image, i.e. \(\mathbf{x} \in \mathbb{R}^d\), avec \(d=784\).

  • La sortie \(\mathbf{y} \in \mathcal{Y}\) correspond à la classe de l’image, avec \(\mathcal{Y} = \left\lbrace 1; K \right\rbrace\), où \(K\) est le nombre de classes (\(K=10\)).

  • La joint feature map pour \(\mathbf{y}=k\) s’écrit \(\Psi(\mathbf{x},k) = \left( \overbrace{0^d... 0^d}^{(k-1)\cdot d}, \overbrace{\mathbf{x}}^{d}, \overbrace{0^d... 0^d}^{(K-k)\cdot d} \right)\), ce qui consiste à avoir un vecteur de taille \(d \cdot K = 7840\).

  • Le vecteur \(\Psi( \mathbf{x},\mathbf{y})\) consiste à recopier le vecteur d’entrée \(\mathbf{x}\) pour la dimension correspondant à la sortie (classe) \(\mathbf{y}=k\), et à compléter par des 0 ailleurs.

  • Les paramètres du modèle linéaire dans cet espace de dimension \(d \cdot K\) seront représentés par une matrice de taille \(d \times K\) (plutôt que par un vecteur de taille \(d \cdot K=7840\)), simplement pour une meilleure efficacité du code.

  • La fonction de dissimilarité est la fonction de coût 0/1 :

\[\begin{split}\Delta(\mathbf{y},\mathbf{y’}) = \begin{cases} 1 \mbox{ si } \mathbf{y} \neq \mathbf{y’} \\ 0 \mbox{ sinon} \end{cases}\end{split}\]
  • La résolution des problèmes d’inférence à l’Eq. (10) et de Loss-Augmented Inference (LAI) à l’Eq. (12) sera ici réalisée en effectuant un parcours exhaustif de l’espace \(\mathcal{Y}\), ce qui est possible dans ce cas simple car \(|\mathcal{Y}|\) est petit (\(|\mathcal{Y}|=10\)).

class SXclass(SModel):
  d =0
  k=0

  def __init__(self, d, K, learning_rate=0.1, epochs=2, tbatch=100):
      SModel.__init__(self,learning_rate, epochs, tbatch)
      self.d = d
      self.K = K
      self.w = np.zeros((d, K))

  def __str__(self):
      return "SXclass - size w="+str(self.w.shape)+ " eta="+str(self.eta)+" epochs="+ str(self.epochs)+ " tbatch="+str(self.tbatch)

  def psi(self, X, Y):
      #COMPLETE WITH YOUR CODE

  def delta(self, y1, y2):
      #COMPLETE WITH YOUR CODE

  def predict(self, X):
      #COMPLETE WITH YOUR CODE

  def lai(self, X, Y):
      #COMPLETE WITH YOUR CODE

Les fonctions à implémenter dans la classe SXclass sont les suivantes :

  • psi(self, X, Y) renverra une matrice de taille \(d \times K\) et correspondra à moyenner les features map de chacun des exemples du batch - comme expliqué ci-dessus.

  • delta(self, y1, y2) calculera la fonction de coût (ici 0-1 loss) entre deux vecteurs de classes : on pourra simplement calculer le vecteur de différence que l’on binarisera à 0/1 suivant que les valeurs soient ou non différentes de 0.

  • predict(self, X) calculera le résultat de l’inférence à l’Eq. (10) pour la classification multi-classes. On pourra calculer le produit matriciel \(X W\) sur un batch de taille \(t_b\) (résultat matrice de taille \(t_b \times K\)), et d’utiliser la méthode argmax pour récupérer la classe prédite pour chaque exemple.

  • lai(self, X, Y) calculera le résultat du problème de Loss-Augmented Inference (LAI) à l’Eq. (12) pour la classification multi-classes. On pourra utiliser la la fonction np_utils.to_categorical afin de convertir les labels de classes vers un encoding one-hot, ce qui permettra d’ajouter le terme \(\Delta(\mathbf{y}_i^*,\mathbf{y})\) dans la matrice de prédiction de la fonction précédente avant d’effectuer la maximisation.

Exercice 2 : Performances du modèle sur la base MNIST

On va maintenant évaluer les performances du modèle sur la base de test de MNIST. On utilisera la fonction predict de la classe SXclass en lui passant les données de test, puis on évaluera les performances avec la méthode delta. Vous devez obtenir un score de l’ordre de 92-93% dans ce cas.

Question :

Comparer les performances à celles obtenues avec la régression logistique (TP d’introduction au deep learning). Quelles sont les différences entre les deux modèles ?

TJHA05

I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research (JMLR), 6:1453–1484, September 2005.