.. _chap-tpDeepLearning6: ############################################################################## 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é :cite:`Tsochantaridis/etal/05a`. 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 :math:`\mathbf{\mathcal{Y}}` structuré discret à partir d'une entrée :math:`\mathbf{x}` appartenant à un espace :math:`\mathbf{\mathcal{X}}` quelconque. On suppose que la relation entre l'entrée :math:`\mathbf{x}` et la sortie :math:`\mathbf{y}` est modélisée une *joint feature map* :math:`\Psi( \mathbf{x},\mathbf{y}) \in \mathbb{R}^d`. On considère un modèle de prédiction linéaire qui assigne le score :math:`\langle \mathbf{w} , \Psi( \mathbf{x},\mathbf{y}) \rangle` à chaque paire :math:`(\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.* : .. 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: predictionstruct **Apprentissage du modèle.** La dissimilarité entre deux sorties :math:`\mathbf{y_1}` et :math:`\mathbf{y_2}` est modélisée par une fonction de coût :math:`\Delta(\mathbf{y_1},\mathbf{y_2})`. Dans un contexte d'apprentissage supervisé, on dispose d'un ensemble de N paires :math:`(\mathbf{\mathbf{x_i}},\mathbf{\mathbf{y_i^*}})` annotées et on cherche à déterminer les paramètres :math:`\mathbf{w}` minimisant la dissimilarité :math:`\Delta\left( \hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w}) ,\mathbf{y_i^*}\right)` entre la sortie prédite par le modèle :math:`\hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w})` et la sortie donnée par la supervision :math:`\mathbf{y_i^*}`. La fonction :math:`\Delta\left( \hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w}\right) ,\mathbf{y_i})` étant difficile à optimiser par rapport à :math:`\mathbf{w}`, la méthode dite de *margin rescaling* permet d'en dériver une borne supérieure convexe :math:`\ell(\mathbf{x}_i,\mathbf{y}_i^*;\mathbf{w}) \geq \Delta\left( \hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w}\right) ,\mathbf{y_i})` : .. math:: \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 :math:`\ell(\mathbf{x}_i,\mathbf{y}_i^*;\mathbf{w})` dérivée de :math:`\Delta\left( \hat{\mathbf{y}}(\mathbf{x_i},\mathbf{w})\right)` pour chaque exemple d'apprentissage, la fonction objectif régularisée :math:`\mathcal{P}(\mathbf{w})` à minimiser pour entraîner le modèle est la suivante : .. math:: \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] :label: primalstruct La minimisation de la fonction objectif de l'Eq. :eq:`primalstruct` va nécessiter la résolution du problème de **"Loss-Augmented Inference" (LAI)** pour chaque exemple d'apprentissage :math:`(\mathbf{\mathbf{x_i}},\mathbf{\mathbf{y_i^*}})`, *i.e.* : .. math:: \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] :label: lai Exercice 0 : Modèle générique de prédiction structurée ********************************************************** La fonction de prédiction de l'Eq. :eq:`predictionstruct` et la formulation d'apprentissage de l'Eq. :eq:`primalstruct` 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 : .. code-block:: python 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 [ + Delta(y,y*)] @abstractmethod def lai(self, X, Y): pass # Inference: arg max_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. :eq:`primalstruct`. La fonction objectif définie à l'Eq. :eq:`primalstruct` étant convexe par rapport aux paramètres :math:`\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 :math:`\mathbf{X}` et un batch de labels donné par la supervision :math:`\mathbf{Y^*}`, et renvoie la fonction renvoie la *joint feature map* :math:`\Psi` moyennée sur l'ensemble du batch , *i.e.* :math:`\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. :eq:`lai`, pour l'ensemble des exemples du batch, *i.e.* :math:`\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]`, :math:`\forall i \in \left\lbrace 1 ; t_b\right\rbrace`. La fonction ``lai`` revoie donc une matrice de taille :math:`t_b \times 1`. - Calcul de la fonction ``psi`` qui prend en paramètre un batch d'exemple :math:`\mathbf{X}` et un batch de labels correspondant au résultat du LAI précédemment calculé :math:`\mathbf{\hat{Y}}`, et renvoie la fonction renvoie la "joint feature map" :math:`\Psi` moyennée sur l'ensemble du batch , *i.e.* :math:`\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 :eq:`primalstruct` par rapport à :math:`\mathbf{w}` : :math:`\frac{\partial \mathcal{P}}{\partial \mathbf{w}} = \lambda \mathbf{w} + (\Psi_1-\Psi_2)`, et mise à jour des paramètres : :math:`\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 : .. 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 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 :math:`\mathbf{x}` correspond à l’image, *i.e.* :math:`\mathbf{x} \in \mathbb{R}^d`, avec :math:`d=784`. - La sortie :math:`\mathbf{y} \in \mathcal{Y}` correspond à la classe de l’image, avec :math:`\mathcal{Y} = \left\lbrace 1; K \right\rbrace`, où :math:`K` est le nombre de classes (:math:`K=10`). - La *joint feature map* pour :math:`\mathbf{y}=k` s’écrit :math:`\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 :math:`d \cdot K = 7840`. - Le vecteur :math:`\Psi( \mathbf{x},\mathbf{y})` consiste à recopier le vecteur d’entrée :math:`\mathbf{x}` pour la dimension correspondant à la sortie (classe) :math:`\mathbf{y}=k`, et à compléter par des 0 ailleurs. - Les paramètres du modèle linéaire dans cet espace de dimension :math:`d \cdot K` seront représentés par une matrice de taille :math:`d \times K` (plutôt que par un vecteur de taille :math:`d \cdot K=7840`), simplement pour une meilleure efficacité du code. - La fonction de dissimilarité est la fonction de coût 0/1 : .. math:: \Delta(\mathbf{y},\mathbf{y’}) = \begin{cases} 1 \mbox{ si } \mathbf{y} \neq \mathbf{y’} \\ 0 \mbox{ sinon} \end{cases} - La résolution des problèmes d’inférence à l’Eq. :eq:`predictionstruct` et de *Loss-Augmented Inference* (LAI) à l’Eq. :eq:`lai` sera ici réalisée en effectuant un parcours exhaustif de l’espace :math:`\mathcal{Y}`, ce qui est possible dans ce cas simple car :math:`|\mathcal{Y}|` est petit (:math:`|\mathcal{Y}|=10`). .. code-block:: python 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 :math:`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. :eq:`predictionstruct` pour la classification multi-classes. On pourra calculer le produit matriciel :math:`X W` sur un batch de taille :math:`t_b` (résultat matrice de taille :math:`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. :eq:`lai` 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 :math:`\Delta(\mathbf{y}_i^*,\mathbf{y})` dans la matrice de prédiction de la fonction précédente avant d’effectuer la maximisation. .. Solution de la classe ``SXclass`` : ``_. 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**. .. admonition:: 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 ? .. Solution du script de test : ``_. .. bibliography:: refs6.bib :cited: