2. Concepts généraux
Les briques communes à tout modèle supervisé : comment une perte mesure une prédiction isolée puis s'agrège en un coût, comment l'optimisation itérative minimise ce coût, et comment le point de vue probabiliste (la vraisemblance) retrouve les mêmes objectifs. On termine par l'algorithme de Newton, une alternative du second ordre à la descente de gradient.
Objectifs
- Définir une fonction de perte et agréger les pertes par exemple en un unique coût à minimiser.
- Énoncer la règle de mise à jour de la descente de gradient et opposer ses variantes par lots et stochastique.
- Définir la vraisemblance et l'objectif du maximum de vraisemblance, et le relier à la minimisation d'un coût.
- Énoncer la mise à jour de Newton en une et plusieurs dimensions et la comparer à la descente de gradient.
2.1 Fonctions de perte et coût
2.1.1 Fonction de perte
Une fonction de perte \(L(z, y)\) est définie comme une pénalité scalaire comparant un score brut \(z\) du modèle (ou une probabilité prédite \(\phi\)) à la cible \(y\). Plus elle est petite, mieux c'est. Chaque famille de modèles se caractérise par sa perte.
| Perte | Formule \(L(z,y)\) | Utilisée par |
|---|---|---|
| Erreur quadratique | \(\tfrac{1}{2}(y-z)^2\) | Régression linéaire |
| Logistique | \(\log\!\left(1+\exp(-yz)\right)\) | Régression logistique |
| Charnière | \(\max(0,\,1-yz)\) | SVM |
| Entropie croisée | \(-\left[\,y\log\phi+(1-y)\log(1-\phi)\,\right]\) | Réseaux de neurones |
Remarque : \(z\) désigne un score brut tel que \(\theta^T x\), tandis que \(\phi \in (0,1)\) désigne une probabilité prédite. La ligne d'entropie croisée prend une probabilité \(\phi\), non un score brut.
2.1.2 Fonction de coût
Le coût \(J(\theta)\) est défini comme la somme des pertes par exemple sur tout l'ensemble d'entraînement de \(m\) exemples :
\[\boxed{\,J(\theta)=\sum_{i=1}^{m} L\!\left(h_\theta(x^{(i)}),\,y^{(i)}\right)\,}\]Entraîner un modèle, c'est choisir \(\theta\) qui minimise \(J(\theta)\). La leçon suivante montre comment.
Remarque : le facteur \(\tfrac{1}{2}\) de l'erreur quadratique est une convention qui s'annule avec l'exposant lors de la dérivation, laissant un gradient propre.
Pertes basées sur la marge, chacune un substitut convexe de la perte 0-1 qui pénalise les marges faibles ou négatives.
2.2 Descente de gradient
2.2.1 Règle de mise à jour
La descente de gradient déplace itérativement les paramètres \(\theta\) à l'opposé du gradient du coût, mis à l'échelle par un taux d'apprentissage \(\alpha > 0\) :
\[\boxed{\,\theta \leftarrow \theta - \alpha\,\nabla_\theta J(\theta)\,}\]Le gradient pointe dans la direction de plus forte croissance, donc avancer à son opposé fait décroître \(J\). Le pas \(\alpha\) contrôle l'ampleur de chaque mise à jour.
Remarque : si \(\alpha\) est trop grand les itérés peuvent diverger, s'il est trop petit la convergence est lente.
2.2.2 Par lots ou stochastique
Les deux variantes diffèrent par le nombre d'exemples contribuant à une mise à jour.
| Variante | Exemples par mise à jour | Mise à jour |
|---|---|---|
| Par lots | Tous les \(m\) | \(\theta \leftarrow \theta - \alpha\,\nabla_\theta J(\theta)\) |
| Stochastique (SGD) | Un seul \((x^{(i)}, y^{(i)})\) | \(\theta \leftarrow \theta - \alpha\,\nabla_\theta L\!\left(h_\theta(x^{(i)}), y^{(i)}\right)\) |
Le mode par lots donne une descente lisse mais lit tout l'ensemble à chaque pas. SGD met à jour après chaque exemple, donc peu coûteux par pas et bruité.
2.2.3 Mise à jour LMS (Widrow-Hoff)
Pour l'erreur quadratique, la mise à jour stochastique par coordonnée est définie comme :
\[\boxed{\,\theta_j \leftarrow \theta_j + \alpha\left(y^{(i)} - h_\theta(x^{(i)})\right)x_j^{(i)}\,}\]La correction est proportionnelle au résidu \(y^{(i)} - h_\theta(x^{(i)})\) multiplié par la composante \(x_j^{(i)}\).
Remarque : un grand résidu produit un grand pas, une prédiction correcte ne produit aucune mise à jour.
La descente de gradient descend la pente vers le minimum (étoile).
2.3 Vraisemblance et estimation du maximum de vraisemblance
2.3.1 Vraisemblance
La vraisemblance \(L(\theta)\) est définie comme la probabilité des cibles observées sous le modèle, vue comme une fonction des paramètres \(\theta\). En supposant les exemples indépendants, elle se factorise :
\[\boxed{\,L(\theta)=\prod_{i=1}^{m} p\!\left(y^{(i)} \mid x^{(i)}; \theta\right)\,}\]2.3.2 Log-vraisemblance
Les produits sont malcommodes à optimiser, on prend donc le logarithme. La log-vraisemblance \(\ell(\theta)\) est définie comme :
\[\boxed{\,\ell(\theta)=\sum_{i=1}^{m} \log p\!\left(y^{(i)} \mid x^{(i)}; \theta\right)\,}\]Le \(\log\) est monotone, il a donc le même maximiseur que \(L(\theta)\) tout en transformant le produit en somme.
2.3.3 Estimation du maximum de vraisemblance
Le maximum de vraisemblance est défini comme la valeur des paramètres qui rend les données les plus probables :
\[\boxed{\,\theta_{\mathrm{MLE}}=\arg\max_\theta\,\ell(\theta)\,}\]Remarque : maximiser la log-vraisemblance équivaut à minimiser le coût \(J(\theta) = -\ell(\theta)\). C'est exactement la vue par minimisation du coût des leçons précédentes, vraisemblance et coût sont donc deux faces d'un même objectif.
2.4 Algorithme de Newton
2.4.1 Mise à jour unidimensionnelle
Pour trouver un point stationnaire de la log-vraisemblance, l'algorithme de Newton suit l'approximation quadratique locale. La mise à jour scalaire est définie comme :
\[\boxed{\,\theta \leftarrow \theta - \frac{\ell'(\theta)}{\ell''(\theta)}\,}\]Elle divise la dérivée première par la dérivée seconde, donc le pas s'adapte automatiquement à la courbure.
2.4.2 Mise à jour multivariée
Avec un vecteur de paramètres \(\theta \in \mathbb{R}^{n+1}\), la dérivée seconde devient la matrice hessienne \(H\), avec \(H_{jk}=\dfrac{\partial^2 \ell}{\partial\theta_j\,\partial\theta_k}\). La mise à jour est définie comme :
\[\boxed{\,\theta \leftarrow \theta - H^{-1}\,\nabla_\theta \ell(\theta)\,}\]Remarque : chaque pas résout un système linéaire en \(H\), une opération en \(O(n^3)\), donc l'algorithme de Newton est coûteux quand le nombre de variables \(n\) est grand.
2.4.3 Newton ou descente de gradient
| Propriété | Algorithme de Newton | Descente de gradient |
|---|---|---|
| Ordre | Second (utilise la courbure \(H\)) | Premier (utilise le gradient seul) |
| Coût par pas | Élevé (\(O(n^3)\), inverse \(H\)) | Faible (\(O(n)\) par exemple) |
| Convergence | Quadratique près de l'optimum, peu de pas | Linéaire, beaucoup de pas |
| Réglage | Aucun taux d'apprentissage | Nécessite un taux \(\alpha\) |
Remarque : l'algorithme de Newton converge en très peu d'itérations mais paie un coût élevé par pas, donc la descente de gradient est préférée quand \(n\) est grand.
Ces outils sont indépendants du modèle. La partie suivante les applique à la classe d'hypothèses la plus simple, où la prédiction est une fonction linéaire des variables : les modèles linéaires.
Suivant : Modèles linéaires · Vue d'ensemble du cours