Cette troisième série d'exercices est conçue pour les étudiants du Département d'Informatique de l'Université M'hamed Bougara de Boumerdès. Elle vise à consolider les compétences fondamentales en optimisation et en apprentissage automatique.
Le document couvre les notions clés suivantes :
- Algorithme de descente de gradient et minimisation de fonction de coût.
- Régression linéaire simple et multiple.
- Méthode des moindres carrés (analytique et itérative).
- Critères de convergence et implémentation pratique (Python).
Exercices TD Optimisation Fonction Coût Data mining
Télécharger PDFCette série d'exercices, proposée par le Département d’Informatique de la Faculté des Sciences de l'Université M’hamed Bougara de Boumerdès, couvre des concepts fondamentaux en machine learning, notamment l'optimisation par descente de gradient et la régression linéaire.
Exercice 01 : Optimisation par descente de gradient pour une fonction quadratique
Soit la fonction de coût F(x) = x2 - 1.2 * (x - 2) + 3.2.
1. Analyse de la fonction et tracé
Tracez la courbe de cette fonction. Déterminez la valeur de x qui minimise la fonction F et la valeur correspondante de F. La fonction F est-elle convexe ?
Une fonction est convexe si le segment de droite entre deux points quelconques de sa courbe se trouve au-dessus ou sur la courbe. Pour une fonction quadratique comme celle-ci, la convexité est essentielle car elle garantit l'existence d'un unique minimum global, rendant les algorithmes d'optimisation comme la descente de gradient efficaces pour le trouver.
2. Algorithme de la descente de gradient
L'algorithme de la descente de gradient est donné par la règle de mise à jour suivante :
xnouveau = xancien - α * dF(x)/dx
Répétez jusqu'à convergence.
a) Critères de convergence
Proposez deux critères de convergence (d'arrêt) pour cet algorithme.
Deux critères couramment utilisés pour arrêter l'algorithme de descente de gradient sont :
- Convergence de la valeur de la fonction de coût : Arrêter lorsque la variation de la fonction de coût F(x) entre deux itérations consécutives devient inférieure à un seuil très petit (ε). Cela signifie que le modèle ne s'améliore plus significativement.
- Convergence des paramètres : Arrêter lorsque la variation de la valeur de x (le paramètre ici) entre deux itérations consécutives devient inférieure à un seuil très petit (ε). Cela indique que x a atteint une valeur stable.
- Nombre maximal d'itérations : Fixer un nombre maximum d'itérations pour éviter que l'algorithme ne s'exécute indéfiniment, surtout si la convergence est lente ou si la fonction n'est pas idéalement convexe.
b) Application de l'algorithme
Appliquez l'algorithme du gradient pour trouver le minimum de cette fonction, avec un taux d'apprentissage (α) = 0.6 et une valeur initiale de x = 0.1. Affichez les résultats après quelques itérations et commentez le comportement de l'algorithme.
Le taux d'apprentissage (α) est un hyperparamètre crucial qui détermine la taille du pas à chaque itération. Un α trop grand peut empêcher la convergence (sauter le minimum), tandis qu'un α trop petit peut ralentir considérablement le processus. La valeur initiale de x est le point de départ de la recherche. Pour les fonctions convexes, le choix de la valeur initiale a moins d'impact sur le minimum final, mais peut influencer le nombre d'itérations nécessaires.
Exercice 02 : Régression linéaire simple par descente de gradient
Cet exercice est idéalement traité sous forme de Travaux Pratiques (TP) avec un langage de programmation tel que Python, afin d'étudier de manière interactive le comportement de la fonction de coût et des paramètres du modèle.
Un représentant commercial a visité 56 entreprises réparties dans 7 départements sur un mois. Les données de visites et de commandes sont les suivantes :
| Département | Nombre de visites | Volume de commandes |
|---|---|---|
| 1 | 2 | 23 |
| 2 | 3 | 27 |
| 3 | 5 | 28 |
| 4 | 9 | 39 |
| 5 | 10 | 39 |
| 6 | 12 | 45 |
| 7 | 15 | 51 |
1. Représentation graphique et relation
Représentez sur un graphique le volume des commandes (en ordonnée) et le nombre de visites (en abscisse) pour les départements enquêtés. Analysez s'il existe une relation entre ces deux grandeurs.
L'observation d'un nuage de points permet de visualiser rapidement s'il existe une corrélation linéaire positive, négative, ou aucune relation apparente entre les variables. Une relation linéaire positive signifierait qu'un plus grand nombre de visites est associé à un volume de commandes plus élevé.
2. Modèle de régression linéaire par descente de gradient
Soit le modèle d'hypothèse de régression linéaire simple : h(x) = θ0 + θ1 * x.
En utilisant la méthode de la descente de gradient, trouvez les valeurs optimales (ou proches de l'optimum) des paramètres θ0 et θ1. Vous devrez définir un nombre d'itérations et un taux d'apprentissage appropriés.
Tracez la fonction de coût correspondante (par exemple, l'erreur quadratique moyenne - MSE). Commentez l'évolution de la fonction de coût et la convergence des paramètres.
Dans la régression linéaire, θ0 représente l'ordonnée à l'origine (la valeur de h(x) quand x est égal à zéro), et θ1 représente la pente de la droite de régression (l'impact de x sur h(x)). La descente de gradient ajuste ces paramètres itérativement pour minimiser la fonction de coût, qui mesure l'erreur entre les prédictions du modèle et les valeurs réelles.
Exercice 03 : Estimateurs analytiques des Moindres Carrés Ordinaires (MCO)
Reprenons la fonction hypothèse de l'exercice 02 : h(x) = θ0 + θ1 * x.
1. Détermination analytique des estimateurs
Déterminez les estimateurs de θ0 et θ1 de façon analytique, en utilisant la méthode des Moindres Carrés Ordinaires (MCO). Calculez leurs valeurs estimées pour les données fournies dans l'exercice 02.
La méthode des Moindres Carrés Ordinaires (MCO) permet de trouver directement les valeurs optimales des paramètres θ0 et θ1 qui minimisent la somme des carrés des résidus, sans avoir recours à un processus itératif. Les formules analytiques pour une régression linéaire simple sont :
θ1 = Σ[(xi - &bar;x)(yi - &bar;y)] / Σ[(xi - &bar;x)2]
θ0 = &bar;y - θ1 * &bar;x
où &bar;x et &bar;y sont les moyennes respectives des variables x (nombre de visites) et y (volume de commandes).
2. Prédiction et qualité de l'ajustement
Effectuez une prédiction du volume des commandes pour un nombre de visites égal à 7.
Évaluez la qualité de l'ajustement des données par le modèle de régression linéaire proposé.
La qualité de l'ajustement d'un modèle de régression est souvent mesurée par le coefficient de détermination, R-carré (R2). Un R2 proche de 1 indique que le modèle explique une grande partie de la variance de la variable dépendante (volume de commandes) à partir de la variable indépendante (nombre de visites).
Exercice 04 : Régression linéaire multiple et forme matricielle des MCO
En régression linéaire multiple, lorsque nous disposons de m exemples d'apprentissage : (yi, xi1, xi2, ..., xin) pour i ∈ {1, ..., m}, qui sont des réalisations des variables aléatoires correspondantes, l'équation de régression s'écrit :
yi = θ0 + θ1 * xi1 + θ2 * xi2 + ... + θn * xin + εi, pour i = 1, ..., m.
où εi est l'erreur du modèle, représentant l'information non capturée par l'explication linéaire des valeurs de yi à partir de xi1, xi2, ..., xin.
À partir du modèle complet :
yi = θ0 + θ1 * xi1 + θ2 * xi2 + ... + θn * xin + εi, pour i = 1, ..., m.
Nous cherchons à estimer les paramètres pour obtenir le modèle de prédiction :
&hat;yi = &hat;θ0 + &hat;θ1 * xi1 + &hat;θ2 * xi2 + ... + &hat;θn * xin, pour i = 1, ..., m.
Les résidus estimés sont définis comme : &hat;εi = yi - &hat;yi.
Démontrez que l'estimateur des Moindres Carrés Ordinaires des paramètres θ sous forme matricielle est donné par l'équation normale :
&hat;θ = (XTX)-1XTY
où Y est un vecteur de dimension (m, 1), X est la matrice de design de dimension (m, n+1), θ est un vecteur de paramètres de dimension (n+1, 1), et ε est un vecteur d'erreurs de dimension (m, 1).
La forme matricielle est particulièrement utile en régression linéaire multiple car elle permet de gérer efficacement un grand nombre de variables explicatives. La matrice X inclut une colonne de 1 pour le terme d'interception (θ0), et n colonnes pour les n caractéristiques (x1 à xn).
Rappel : Formules utiles pour le calcul matriciel des MCO
Voici quelques formules de dérivées matricielles qui peuvent être utiles pour la démonstration de l'équation normale :
- Dérivée de
xTxpar rapport àx:∇x(xTx) = 2x - Dérivée de
A xpar rapport àx:∇x(A x) = AT(pour un vecteurxet une matriceA) - Dérivée de
xT A xpar rapport àx:∇x(xT A x) = (A + AT)x - Si
Aest une matrice symétrique, alors∇x(xT A x) = 2Ax
Foire aux Questions (FAQ) sur la régression et la descente de gradient
Qu'est-ce que la descente de gradient et à quoi sert-elle ?
La descente de gradient est un algorithme d'optimisation itératif utilisé pour trouver le minimum local (ou global pour les fonctions convexes) d'une fonction. Elle fonctionne en ajustant les paramètres du modèle dans la direction opposée au gradient de la fonction de coût, c'est-à-dire dans la direction de la pente la plus raide en descente. Elle est fondamentale dans l'apprentissage automatique pour l'entraînement de nombreux modèles, y compris la régression linéaire et les réseaux de neurones.
Quelle est la différence entre la régression linéaire simple et multiple ?
La régression linéaire simple modélise la relation entre une variable dépendante et une seule variable indépendante. Par exemple, prédire le prix d'une maison en fonction de sa taille. La régression linéaire multiple, quant à elle, utilise deux ou plusieurs variables indépendantes pour prédire la variable dépendante. Par exemple, prédire le prix d'une maison en fonction de sa taille, du nombre de chambres et de son emplacement.
Pourquoi utilise-t-on la méthode des Moindres Carrés Ordinaires (MCO) ?
La méthode des Moindres Carrés Ordinaires (MCO) est une technique statistique qui permet d'estimer les paramètres d'un modèle de régression linéaire en minimisant la somme des carrés des différences entre les valeurs observées (réelles) et les valeurs prédites par le modèle. Elle est largement utilisée car elle est facile à comprendre, à mettre en œuvre et fournit des estimateurs efficaces sous certaines conditions (hypothèses de Gauss-Markov).