Notes de cours : Programmation android

avec Kotlin

Faculté des Sciences Agadir

Département d’informatique
Licence Informatique : IA
Draft

Version 0.1

Prof. A. F El Ouafdi

Last updated : 17 avril 2025

Table des matières

1 Optimisation sans contraintes 2

Méthode de Descente Général . . . . . . . . . . . . . . . . . . . . . . . 12
Méthode de Recherche de Ligne Exacte en 1D . . . . . . . . . . . . . . 16
Exemple numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.1 La descente de gradient stochastique (SGD) : . . . . . 20

1
Chapitre 1

Optimisation sans contraintes

L’optimisation sans contraintes est essentielle en ingénierie pour l’es-

timation de paramètres, l’analyse économique et l’étude de systèmes chi-
miques. Elle sert de base à l’optimisation avec contraintes. Ce chapitre pré-
sente la formulation des problèmes d’optimisation sans contraintes, aborde
la continuité, la différentiabilité, la convexité, et développe les conditions
d’optimalité locale du premier et du second ordre, avec des exemples et
l’introduction aux algorithmes itératifs.

Définition 1.0.1. Une racine (ou zéro) d’une fonction continue 𝑓 : R → R

est un point 𝑥¯ ∈ R tel que :
𝑓 (𝑥)
¯ = 0.
Cela signifie que, pour une fonction 𝑓 continue, 𝑥¯ est une valeur où la
fonction 𝑓 prend la valeur zéro.

Algorithme de Newton-Raphson pour la recherche des ra-

cine d’une fonction continue

Pour approcher une solution de l’équation 𝑓 (𝑥) = 0, on utilise la mé-

thode de Newton, qui repose sur l’approximation de la fonction 𝑓 par son

2
Short title of document

Figure 1.1 – Illustration de la racine (zéro) de la fonction continue 𝑓 (𝑥) = cos(𝑥) − 𝑥 3 . La courbe
bleue représente la fonction, et le marqueur rouge indique l’emplacement de la racine approximative
𝑥¯ ≈ 0.865, où la fonction s’annule.

développement de Taylor au premier ordre. À partir d’un point initial 𝑥0 ,

choisi près du zéro recherché, on approxime la fonction par la tangente en
ce point :

𝑓 (𝑥) ≈ 𝑓 (𝑥0 ) + 𝑓 ′(𝑥 0 )(𝑥 − 𝑥0 ).

Pour trouver un zéro de cette approximation, on résout l’équation li-

néaire suivante pour l’intersection de la tangente avec l’axe des abscisses :

0 = 𝑓 (𝑥0 ) + 𝑓 ′(𝑥 0 )(𝑥 − 𝑥0 ).

Cela donne un nouveau point 𝑥1 , qui devrait être plus proche du zéro
de la fonction que le point initial 𝑥0 . En répétant ce processus d’approxi-
mation par la tangente aux points successifs (𝑥1 , 𝑥 2 , etc.), on peut améliorer

3
Short title of document

Figure 1.2 – Illustration de la racine (zéro) de la fonction continue 𝑓 (𝑥) = cos(𝑥) − 𝑥 3 . La courbe
bleue représente la fonction, et le marqueur rouge indique l’emplacement de la racine approximative
𝑥¯ ≈ 0.865, où la fonction s’annule.

progressivement l’approximation du zéro de 𝑓 .

La figure 1.2 montre le processus itératif de la méthode de Newton-
Raphson, qui utilise la tangente à la courbe 𝑦 = 𝑓 (𝑥) pour obtenir une
meilleure approximation de la racine de la fonction à chaque itération.
(a) Le principe général est illustré, avec l’utilisation de la tangente en un
point (𝑥 𝑛 , 𝑓 (𝑥 𝑛 )) pour estimer 𝑥 𝑛+1 . (b) à (f) montrent les itérations succes-
sives (𝑥1 à 𝑥5 ), où chaque nouvelle estimation affine la précision par rapport
à la racine recherchée. Ce processus démontre la rapidité de convergence
de la méthode, sous réserve que l’estimation initiale soit adéquate.

4
Short title of document

Data: Une fonction 𝑓 (𝑥), sa dérivée 𝑓 ′(𝑥), une estimation initiale 𝑥0 ,

une tolérance 𝜖, un nombre maximal d’itérations 𝑁max .
Result: Une approximation de la racine 𝑥 ∗ .
begin
𝑛 ← 0;
while 𝑛 < 𝑁max do
Calculer 𝑓 (𝑥 𝑛 ) et 𝑓 ′(𝑥 𝑛 );
if | 𝑓 (𝑥 𝑛 )| < 𝜖 then
Retourner 𝑥 𝑛 (la racine est trouvée);
end
if 𝑓 ′(𝑥 𝑛 ) = 0 then
Erreur : la dérivée est nulle, la méthode échoue;
Arrêter;
end
𝑓 (𝑥 𝑛 )
Mettre à jour 𝑥 𝑛+1 ← 𝑥 𝑛 − 𝑓 ′ (𝑥 𝑛 )
;
𝑛 ← 𝑛 + 1;
end
Retourner 𝑥 𝑛 (approximation après 𝑁max itérations);
end
Algorithm 1: Méthode de Newton-Raphson pour trouver la racine
d’une fonction
Example 1.0.2. Pour illustrer la méthode, recherchons le nombre positif 𝑥
vérifiant cos(𝑥) = 𝑥 3 . Reformulons la question pour introduire une fonction
devant s’annuler : on recherche le zéro positif (la racine) de 𝑓 (𝑥) = cos(𝑥) −
𝑥 3 . La dérivation donne 𝑓 ′(𝑥) = − sin(𝑥) − 3𝑥 2 .
Comme cos(𝑥) ≤ 1 pour tout 𝑥 et 𝑥 3 > 1 pour 𝑥 > 1, nous savons
que notre zéro ne peut être supérieur à 1. De plus, cos(0) = 1 > 0 = 03 et
cos(1) < cos(𝜋/4) < 1 = 13 , ce qui nous permet de conclure que notre zéro
appartient à l’intervalle [0, 1].
Nous prenons comme valeur de départ 𝑥0 = 0, 5 :

5
Short title of document

𝑓 (𝑥 𝑛−1 )
𝑥𝑛 𝑥 𝑛 = 𝑥 𝑛−1 − 𝑓 ′ (𝑥 𝑛−1 )
Approximation numérique
cos(0,5)−0,53
𝑥1 0, 5 − − sin(0,5)−3×0,52
≈ 1, 112 141 637 097 2
𝑥2 ··· ≈ 0, 909 672 693 736 8
𝑥3 ··· ≈ 0, 866 263 818 208 8
𝑥4 ··· ≈ 0, 865 477 135 298 2
𝑥5 ··· ≈ 0, 865 474 033 110 9
𝑥6 ··· ≈ 0, 865 474 033 101 6
𝑥7 ··· ≈ 0, 865 474 033 101 6
Ainsi, la méthode de Newton converge vers la solution 𝑥 ≃ 0, 865 474 033 101 6.

Problèmes de minimisation sans contraintes

Les problèmes d’optimisation les plus simples sont ceux qui consistent
à minimiser (ou maximiser) une fonction 𝑓 : 𝑊 ⊂ R → R. Le problème
général d’optimisation sans contrainte peut être formulé de la manière
suivante :

min 𝑓 (𝑥) (1.1)

𝑥∈R

Il s’agit donc de déterminer un point 𝑥 ∗ de R tel que :

∀𝑥 ∈ R : 𝑓 (𝑥 ∗ ) < 𝑓 (𝑥) (1.2)

c’est-à-dire un minimum global de 𝑓 sur R. Lorsque l’inégalité stricte
𝑓 (𝑥 ∗ ) < 𝑓 (𝑥) est vérifiée pour tout 𝑥 ≠ 𝑥 ∗ , le minimum global est unique
comme c’est illustré par le point entouré par le carré vert dans la figure 1.3.
Pour beaucoup de problèmes d’optimisation sans contrainte, les princi-
pales méthodes de résolution connues ne permettent pas la détermination
d’un minimum global : il faut alors se contenter de minimums locaux,
c’est-à-dire des points qui vérifient (1.2) seulement dans un voisinage de

6
Short title of document

Figure 1.3 – Représentation de la fonction 𝑓 (𝑥) = 0.1𝑥 2 + sin(3𝑥) + sin(5𝑥) avec des minima
locaux (cercles rouges) et un minimum global (carré vert).

𝑥 ∗ comme c’est illustré par des point entourés de cercles dans la figure 1.3.
On verra maintenant comment de tels points peuvent être caractérisés.

Conditions nécessaires d’optimalité locale (cas 1D)

Dans ce qui suit, on suppose que la fonction 𝑓 : R → R est au moins

de classe 𝐶 1 sur un intervalle 𝐼 ⊂ R. On s’intéresse au problème local de
minimisation :

∃𝛿 > 0 tel que ∀𝑥 ∈ (𝑥 ∗ − 𝛿, 𝑥 ∗ + 𝛿) : 𝑓 (𝑥 ∗ ) < 𝑓 (𝑥) (1.3)

Théorème 1.0.3 (Conditions nécessaires d’optimalité locale en 1D). Soit

𝑓 : R → R une fonction de classe 𝐶 2 . Si 𝑥 ∗ est un minimum local de 𝑓 ,
alors :
(a) 𝑓 ′(𝑥 ∗ ) = 0
(b) 𝑓 ′′(𝑥 ∗ ) ≥ 0

Théorème 1.0.4 (Conditions suffisantes d’optimalité locale en 1D). Soit

𝑓 : R → R une fonction de classe 𝐶 2 . Si :
(a) 𝑓 ′(𝑥 ∗ ) = 0

7
Short title of document

(b) 𝑓 ′′(𝑥 ∗ ) > 0

alors 𝑥 ∗ est un minimum local de 𝑓 .

Définition 1.0.5. Un point 𝑥 ∗ tel que 𝑓 ′(𝑥 ∗ ) = 0 est appelé point stationnaire.

Algorithme de Newton pour la descente explicite en 1D

Pour obtenir un minimum local de 𝑓 , d’après le théorème 1.0.4, on

cherche un point 𝑥 ∗ tel que :

𝑓 ′(𝑥 ∗ ) = 0 et 𝑓 ′′(𝑥 ∗ ) > 0 (1.4)

En posant 𝑔(𝑥) := 𝑓 ′(𝑥), on cherche donc les zéros de la dérivée 𝑔(𝑥)

tout en vérifiant que 𝑓 ′′(𝑥) > 0.
On peut utiliser l’algorithme de Newton-Raphson suivant pour trouver
une approximation de 𝑥 ∗ :

8
Short title of document

Data: Approximation initiale 𝑥0 , tolérance 𝜖, nombre maximal

d’itérations 𝑁max
Result: Approximation du minimum local 𝑥∗
𝑘 ← 0;
while 𝑘 < 𝑁max et 𝑓 ′(𝑥 𝑘 ) > 𝜖 do
Calculer 𝑔 𝑘 = 𝑓 ′(𝑥 𝑘 );
Calculer ℎ 𝑘 = 𝑓 ′′(𝑥 𝑘 );
if ℎ 𝑘 > 0 then
𝑔𝑘
𝑥 𝑘+1 ← 𝑥 𝑘 − ;
ℎ𝑘
end
else
Sortie : 𝑓 ′′(𝑥 𝑘 ) ≤ 0, condition de convexité non satisfaite;
end
𝑘 ← 𝑘 + 1;
end
Algorithm 2: Méthode de Newton pour trouver un minimum local en
1D
L’algorithme 1 est appliqué à la fonction suivante :

1
𝑓 (𝑥) = 1 − (1.5)
5𝑥 2 − 6𝑥 + 5
rapportée dans la figure 1.4. Sa dérivée première est donnée par :

10𝑥 − 6
𝑓 ′(𝑥) = (1.6)
(5𝑥 2− 6𝑥 + 5)2

et sa dérivée seconde par :

10(5𝑥 2 − 6𝑥 + 5) − (10𝑥 − 6)(20𝑥 − 12)

𝑓 ′′(𝑥) = (1.7)
(5𝑥 2 − 6𝑥 + 5)3

Le tableau 1.1 présente les itérations de convergence de l’algorithme 1

vers le point stationnaire 𝑥 ∗ = 0.6. On observe que la convergence est très
rapide, atteignant le point souhaité en seulement trois itérations.

9
Short title of document

1
Figure 1.4 – Représentation de la fonction 1 − 5𝑥 2 −6𝑥+5
montrant un minimum local isolé en
𝑥 ∗ = 0.6.

Itérations de l’algorithme de Newton

Itération 𝑥𝑘 𝑥 𝑘+1 𝑓 ′(𝑥 𝑘+1 ) 𝑓 ′′(𝑥 𝑘+1 )

0 0.5000000000 0.6065573770 -0.0946745562 0.8884842968
1 0.6065573770 0.5999982374 0.0064028281 0.9761688967
2 0.5999982374 0.6000000000 -0.0000017213 0.9765625000
1
Table 1.1 – Itérations de l’algorithme de Newton sur la fonction 1 − 5𝑥 2 −6𝑥+5
.

Algorithme de Newton par approximation du gradient (cas

1D)

Lorsque la dérivée d’une fonction 𝑓 : R → R n’est pas disponible ou

ne peut pas être calculée analytiquement, on peut approximer la dérivée

10
Short title of document

première et la dérivée seconde numériquement à l’aide des différences

finies.
L’approximation centrée de la dérivée première est donnée par :
𝑓 (𝑥 + ℎ) − 𝑓 (𝑥 − ℎ)
𝑓 ′(𝑥) ≈ (1.8)
2ℎ
L’approximation centrée de la dérivée seconde est donnée par :
𝑓 (𝑥 + ℎ) − 2 𝑓 (𝑥) + 𝑓 (𝑥 − ℎ)
𝑓 ′′(𝑥) ≈ (1.9)
ℎ2
En utilisant ces approximations, l’algorithme de Newton devient :
Data: Approximation initiale 𝑥0 ∈ R, tolérance 𝜖 > 0, nombre
maximal d’itérations 𝑁max , petit pas ℎ > 0
Result: Approximation du minimum local 𝑥∗
𝑘 ← 0;
while 𝑘 < 𝑁max et 𝑓 ′(𝑥 𝑘 ) > 𝜖 do
Approximer la dérivée première :
𝑓 (𝑥 𝑘 +ℎ)− 𝑓 (𝑥 𝑘 −ℎ)
𝑔𝑘 ← 2ℎ ;
Approximer la dérivée seconde :
𝑓 (𝑥 𝑘 +ℎ)−2 𝑓 (𝑥 𝑘 )+ 𝑓 (𝑥 𝑘 −ℎ)
𝐻𝑘 ← ℎ2
;
if 𝐻 𝑘 > 0 then
𝑔
𝑥 𝑘+1 ← 𝑥 𝑘 − 𝐻𝑘𝑘 ;
end
else
Sortie : La dérivée seconde n’est pas strictement positive;
Stop;
end
𝑘 ← 𝑘 + 1;
end
Algorithm 3: Méthode de Newton avec dérivées approximées (1D)
Dans l’algorithm utilise une approximation du gradient et du hessien
pour mettre à jour la valeur de 𝑥 jusqu’à ce que la norme du gradient soit
suffisamment petite, indiquant que nous avons atteint un minimum local.

11
Short title of document Méthode de Descente Général

Itération 𝑥𝑘 𝑓 ′(𝑥 𝑘 ) 𝑓 ′′(𝑥 𝑘 )

0 0.5000000000 -0.0946745562 0.8884837310
1 0.6065574449 0.0064028943 0.9761702557
2 0.5999982465 -0.0000017124 0.9765621645
3 0.6000000000 0.0000000000 0.9 765621645

Table 1.2 – Itérations de l’algorithme de Newton avec approximations numériques pour minimiser
1
la fonction 1 − 5𝑥 2 −6𝑥+5 .

Ce tableau montre les valeurs calculées pour chaque itération de l’al-

gorithme, avec une précision de 10 chiffres après la virgule pour chaque
valeur de 𝑥 𝑘 , 𝑓 ′(𝑥 𝑘 ), et 𝑓 ′′(𝑥 𝑘 ). On remarque dans cet exemple que la diffé-
rence entre les résultats de l’utilisation de l’expression exacte du gradient
et de la matrice hessienne dans le tableau 1.1 et les résultats de l’approxi-
mation du gradient et hessien dans le tableau 1.2 se limite à une seule
itération pour atteindre le minimum 𝑥 ∗ = 0.6.

※ Méthode de Descente Général

En général, l’analyse du problème de minimiser localement une fonc-
tion de 𝑛 variables ne peut pas se réduire à l’analyse de la minimisation
locale d’une fonction d’une seule variable. On pourrait réécrire le problème
ainsi :

𝑓 (𝑥 ∗ ) ≤ 𝑓 (𝑥 ∗ + 𝛼𝑑), ∀𝑑 ∈ 𝑉(0),

où 𝑑 représente le déplacement de 𝑥 ∗ à un point voisin, ou encore, en

séparant la notion de direction et la notion de distance du déplacement,

𝑓 (𝑥 ∗ ) ≤ 𝑓 (𝑥 ∗ + 𝛼𝑑), ∀𝑑 ∈ R𝑛 , ∥𝑑∥ = 1, et ∀𝛼 < 𝜖,

où 𝜖 représente le diamètre d’une boule centrée en 𝑥 ∗ contenue dans

12
Short title of document Méthode de Descente Général

𝑉(𝑥 ∗ ). Cependant, nous ne pouvons pas établir d’équivalence entre les

restrictions unidimensionnelles et les problèmes originaux.

Version unidimensionnelle. Si 𝑥 ∗ est un minimum local de 𝑓 , alors 0 est

un minimum local de la fonction d’une variable définie par :

def
ℎ 𝑥 ∗ ,𝑑 (𝛼) = 𝑓 (𝑥 ∗ + 𝛼𝑑)

pour toute direction unitaire 𝑑 ∈ R𝑛 , i.e., ∥𝑑∥ = 1. On a donc :

ℎ 𝑥 ∗ ,𝑑 (0) ≤ ℎ 𝑥 ∗ ,𝑑 (𝛼), pour tout 𝛼 ∈ R proche de 0.

Théorème 1.1.1 (Approximation de Taylor Linéaire). Soit 𝑓 : R𝑛 → R

une fonction de classe 𝐶 1 au voisinage d’un point 𝑥 ∗ . On peut approcher
la valeur de la fonction en un point voisin 𝑥 ∗ + 𝑑 de 𝑥 ∗ par une fonction
polynomiale de degré 1.

𝑓 (𝑥 ∗ + 𝛼𝑑) ≈ 𝒫linéaire (𝑑) = 𝑓 (𝑥 ∗ ) + 𝛼 𝑓 ′(𝑥 ∗ ) · 𝑑. (1.10)

Ici, 𝒫linéaire (𝑑) est l’approximation de Taylor linéaire de 𝑓 (𝑥) au point

𝑥∗.

Les méthodes de descente sont fondamentales en optimisation pour

minimiser des fonctions. Elles consistent à chercher une nouvelle solution
à chaque itération en se déplaçant dans une direction qui réduit la valeur
de la fonction objectif. En général, la solution à l’itération (𝑘 + 1)-ème est
donnée par

𝑥 𝑘+1 = 𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 , 𝛼𝑘 > 0 (1.11)

où 𝑑 𝑘 est la direction de pas et 𝛼 𝑘 est la taille du pas le long de cette

direction. Le processus de recherche de 𝛼 𝑘 , appelé recherche de ligne,
consiste à trouver la taille de pas optimale qui minimise la fonction le long

13
Short title of document Méthode de Descente Général

de 𝑑 𝑘 . Dans les méthodes de descente, la fonction à minimiser diminue à

chaque itération, c’est-à-dire que, pour minimiser une fonction 𝑓 , on a :

𝑓 (𝑥 𝑘+1 ) < 𝑓 (𝑥 𝑘 )

sauf lorsque 𝑥 𝑘 est déjà optimal. Pour garantir une diminution de la

fonction, la direction de descente 𝑑 𝑘 doit satisfaire :

𝑓 ′(𝑥 𝑘 )𝑑 𝑘 < 0 (1.12)

Cela signifie que la direction de recherche doit former un angle aigu

avec le négatif du gradient de la fonction. Une telle direction est connue
sous le nom de direction de descente. Un algorithme général pour une
méthode de descente d’optimisation est donné par l’Algorithme 4.
Input: Initialisation : 𝑥 0 , tolérance 𝜖 0
Output: Solution optimale 𝑥 𝑘
for 𝑘 = 1, 2, . . . do
Trouver une direction de descente 𝑑 𝑘 ;
Recherche de ligne : Choisir une taille de pas 𝛼 𝑘 > 0 tel que :;
𝛼 𝑘 ← arg min𝛼≥0 𝑓 (𝑥 + 𝛼𝑑) ;
Mettre à jour la solution en utilisant l’équation :
𝑥 𝑘+1 = 𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 ;
if ∥ 𝑓 ′(𝑥 𝑘+1 )∥2 ≤ 𝜖 0 then
Sortir;
end
end
Algorithm 4: Méthode Générale de Descente
Pour qu’on puisse appliquer l’algorithme de descente 4 pour converger
vers un minimum, à chaque itération, on doit absolument spécifier deux
inconnus :
1. La direction de recherche de descente 𝑑 𝑘
2. La méthode de calcul du pas de déplacement 𝛼 𝑘

14
Short title of document Méthode de Descente Général

La direction de recherche de descente

Proposition 1.1.2. Si 𝑓 ′(𝑥) ≠ 0, la direction 𝑑 = − 𝑓 ′(𝑥) est une direction de

descente pour 𝑓 au point 𝑥.
En effet, en substituant la direction 𝑑 = − 𝑓 ′(𝑥) dans la relation (1.10) et
pour 𝛼 = 1, on obtient :

𝑓 (𝑥 + 𝑑) ≈ 𝑓 (𝑥) + 𝑓 ′(𝑥) · (− 𝑓 ′(𝑥)) = 𝑓 (𝑥) − ∥ 𝑓 ′(𝑥)∥2 . (1.13)

Le produit scalaire ⟨ 𝑓 ′(𝑥), − 𝑓 ′(𝑥)⟩ = −∥ 𝑓 ′(𝑥)∥2 < 0 montre que, pour

un petit pas 𝛼 > 0, on a
𝑓 (𝑥 + 𝛼𝑑) < 𝑓 (𝑥).

Cela signifie que la fonction 𝑓 diminue le long de la direction opposée

au gradient.

Figure 1.5 – Illustration de la descente de gradient pour la fonction 𝑓 (𝑥) = 1 − 5𝑥 2 −6𝑥+5

1
. Les
points rouges montrent la progression de la descente de gradient à partir du point initial 𝑥0 = 0.9
jusqu’à l’optimum 𝑥 ∗ = 0.6. Le pas de déplacement est fixé à 𝛼 = 1.

15
Short title of document Méthode de Recherche de Ligne Exacte en 1D

Comme illustré à la figure 1.5, la descente de gradient (avec un pas

de déplacement fixe 𝛼 𝑘 = 1) permet dans cet exemple de se rapprocher
progressivement du point optimal 𝑥 ∗ . Les points rouges montrent les étapes
successives de cette descente à partir du point initial 𝑥0 , jusqu’à atteindre
le minimum de la fonction.

La méthode de calcul du pas de déplacement 𝛼 𝑘 en dimen-

sion 1

※ Méthode de Recherche de Ligne Exacte en 1D

Pour affiner la recherche de la taille de pas 𝛼 𝑘 , la méthode de recherche
de ligne exacte consiste à résoudre un problème d’optimisation le long de
la direction 𝑑 𝑘 . Cette approche revient à minimiser 𝑓 sur le rayon {𝑥 + 𝛼𝑑 |
𝛼 > 0}, où 𝑓 : R → R :

𝛼 𝑘 = arg min 𝑓 (𝑥 + 𝛼𝑑) (1.14)

𝛼≥0

Cependant, la recherche de ligne exacte peut être coûteuse en calcul

pour certaines fonctions, ce qui limite son usage en pratique.

Définition 1.2.1 (Direction suffisamment descendante en 1D). Une direc-

tion 𝑑 ∈ R est dite suffisamment descendante s’il existe deux constantes
positives 𝛾0 et 𝛾1 , indépendantes de 𝑥, telles que :

— 𝑓 ′(𝑥) · 𝑑 ≤ −𝛾0 | 𝑓 ′(𝑥)|2 ,

— |𝑑| ≤ 𝛾1 | 𝑓 ′(𝑥)|.

Une fois qu’une direction 𝑑 suffisamment descendante est déterminée,

il convient de spécifier une longueur de déplacement admissible, appelée
pas de déplacement.

16
Short title of document Méthode de Recherche de Ligne Exacte en 1D

Définition 1.2.2 (Critères d’Armijo et de Wolfe en 1D). Un pas 𝛼 est dit

admissible pour une direction suffisamment descendante 𝑑 s’il satisfait
aux deux conditions suivantes :

— Critère d’Armijo :
 
′ 1
𝑓 (𝑥 + 𝛼𝑑) − 𝑓 (𝑥) < 𝜏𝛼 𝑓 (𝑥) · 𝑑, avec 𝜏 ∈ 0, ,
2
— Critère de Wolfe :

𝑓 ′(𝑥 + 𝛼𝑑) · 𝑑 ≥ 𝜎 𝑓 ′(𝑥) · 𝑑, avec 𝜎 ∈ ]0, 1[ .

où 𝜏 et 𝜎 sont des constantes fixées pour garantir l’admissibilité du pas.

Théorème 1.2.3. Soit un algorithme de descente appliqué au problème

min 𝑓 (𝑥), 𝑓 ∈ 𝐶 1 (R),

𝑥∈R

supposons qu’à chaque itération la direction 𝑑 𝑘 est suffisamment descen-

dante, et que le pas 𝛼 𝑘 est admissible (au sens d’Armijo et de Wolfe) ; alors
tout point d’accumulation de la suite {𝑥 𝑘 } est un point stationnaire de 𝑓 .

Ce théorème garantit la convergence vers des points stationnaires si la

direction est suffisamment descendante et le pas admissible. Le théorème
suivant donne un moyen pratique de construire ce pas.
Théorème 1.2.4. Soit un algorithme de descente pour le problème

min 𝑓 (𝑥), 𝑓 ∈ 𝐶 1 (R),

𝑥∈R

et supposons que la direction 𝑑 𝑘 soit suffisamment descendante. Si le pas

𝛼 𝑘 est choisi comme la première valeur de la suite géométrique suivante
qui satisfait le critère d’Armijo :
  𝑚 
1 1 1
1, , , . . . , ,... , (1.15)
2 4 2
alors tout point d’accumulation de la suite {𝑥 𝑘 } est un point stationnaire
de 𝑓 .

17
Short title of document Exemple numérique

Ce choix de 𝛼 𝑘 via la suite (1.15) assure que le pas est suffisamment

petit pour satisfaire au critère d’Armijo. Le mécanisme de recul consiste
à partir d’un pas initial (souvent 𝛼0 = 1) et à le réduire (par exemple en
le multipliant par 𝜌 = 0.5) jusqu’à satisfaire le critère. Cela permet une
progression stable vers un minimum sans sauts excessifs.
Entrée: Point de départ 𝑥0
Entrée: Critère de convergence 𝜖 > 0
Entrée: Nombre maximal d’itérations 𝑁
Sortie : Point optimal 𝑥 𝑘 et valeur optimale 𝑓 (𝑥 𝑘 )
𝑘 ← 0;
while 𝑘 ≤ 𝑁 do
Calculer la dérivée 𝑓 ′(𝑥 𝑘 );
𝑑 𝑘 ← − 𝑓 ′(𝑥 𝑘 );
if |𝑑 𝑘 | ≤ 𝜖 then
Sortir;
end
𝛼 𝑘 ← 1;
while 𝑓 (𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 ) ≥ 𝑓 (𝑥 𝑘 ) + 𝑐𝛼 𝑘 𝑓 ′(𝑥 𝑘 )𝑑 𝑘 do
𝛼 𝑘 ← 𝛼2𝑘 ;
end
𝑥 𝑘+1 ← 𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 ;
𝑘 ← 𝑘 + 1;
end
Retourner 𝑥 𝑘 , 𝑓 (𝑥 𝑘 );
Algorithm 5: Descente de gradient en 1D avec pas adaptatif (critère
d’Armijo)

※ Exemple numérique
Considérons la fonction suivante :

18
Short title of document Exemple numérique

𝑓 (𝑥) = 𝑥 4 − 3𝑥 3 + 2

Sa dérivée est :

𝑓 ′(𝑥) = 4𝑥 3 − 9𝑥 2

Nous appliquons l’algorithme de descente de gradient avec :

— 𝑥0 = 0.5
— 𝜖 = 10−3
— 𝑁 = 10
— 𝑐 = 10−4
— 𝛼0 = 1

Itération 0

𝑥0 = 0.5, 𝑓 ′(𝑥0 ) = 4(0.5)3 − 9(0.5)2 = 0.5 − 2.25 = −1.75

𝑑0 = − 𝑓 ′(𝑥0 ) = 1.75

On teste 𝛼 = 1 :

𝑥1 = 𝑥0 + 𝛼𝑑0 = 0.5 + 1.75 = 2.25

𝑓 (𝑥0 + 𝛼𝑑0 ) = 𝑓 (2.25) = (2.25)4 − 3(2.25)3 + 2 ≈ −6.55

𝑓 (𝑥0 ) + 𝑐 · 𝛼 · 𝑓 ′(𝑥0 ) · 𝑑0 = 1.9375 + 10−4 · 1.752 ≈ 1.9378

Comme 𝑓 (𝑥 1 ) < 𝑓 (𝑥0 ) + 𝑐𝛼 𝑓 ′(𝑥0 )𝑑0 , le critère d’Armijo est satisfait. On

accepte 𝛼 = 1.

19
Short title of document Exemple numérique

Itération 1

𝑥1 = 2.25, 𝑓 ′(𝑥1 ) = 4(2.25)3 − 9(2.25)2 ≈ 45.56 − 45.56 = 0

Le critère d’arrêt est satisfait : ∥ 𝑓 ′(𝑥1 )∥ = 0 ≤ 𝜖.

Résumé des itérations

𝑘 𝑥𝑘 𝑓 ′(𝑥 𝑘 ) 𝑑𝑘 𝛼𝑘 𝑥 𝑘+1 𝑓 (𝑥 𝑘 )
0 0.5 -1.75 1.75 1 2.25 1.9375
1 2.25 0 0 — — -6.55

Conclusion : L’algorithme converge en deux itérations vers 𝑥 ∗ = 2.25

avec 𝑓 (𝑥 ∗ ) ≈ −6.55.

1.3.1 La descente de gradient stochastique (SGD) :

La descente de gradient stochastique (abrégée SGD) est une méthode

itérative souvent utilisée en apprentissage automatique pour optimiser la
descente du gradient lors de chaque recherche une fois qu’un vecteur de
poids aléatoire est choisi.
En apprentissage profond, la fonction objectif est généralement la moyenne
des fonctions de perte pour chaque exemple dans l’ensemble de données
d’entraînement. Étant donné un ensemble de données d’entraînement de
𝑛 exemples, nous supposons que 𝑓𝑖 (x) est la fonction de perte par rapport
à l’exemple d’entraînement d’indice 𝑖, où x est le vecteur de paramètres.
Nous obtenons alors la fonction objectif

𝑛
1Õ
𝑓 (x) = 𝑓𝑖 (x).
𝑛
𝑖=1

20
Short title of document Exemple numérique

Le gradient de la fonction objectif en x est calculé comme

𝑛
′ 1Õ ′
𝑓 (x) = 𝑓𝑖 (x).
𝑛
𝑖=1

Si la descente de gradient est utilisée, le coût computationnel pour

chaque itération de la variable indépendante est 𝑂(𝑛), ce qui croît linéai-
rement avec 𝑛. Par conséquent, lorsque l’ensemble de données d’entraî-
nement est plus grand, le coût de la descente de gradient pour chaque
itération sera plus élevé.
La descente de gradient stochastique (SGD) réduit le coût computa-
tionnel à chaque itération. À chaque itération de la descente de gradient
stochastique, nous échantillonnons uniformément un indice 𝑖 pour des
exemples de données au hasard, et calculons le gradient 𝑓𝑖′(x) pour mettre
à jour x :

x ← x − 𝜂 𝑓𝑖′(x),

où 𝜂 est le taux d’apprentissage. Nous pouvons voir que le coût compu-

tationnel pour chaque itération passe de 𝑂(𝑛) de la descente de gradient
à la constante 𝑂(1). De plus, nous voulons souligner que le gradient sto-
chastique est une estimation non biaisée du gradient complet car

E[ 𝑓𝑖′(x)] = 𝑓 ′(x).

Cela signifie que, en moyenne, le gradient stochastique est une bonne

estimation du gradient. Les étapes pour effectuer SGD sont les suivantes :

21
Short title of document Exemple numérique

Input: Ensemble de données d’entraînement, taux d’apprentissage

𝜂, nombre maximal d’itérations 𝑁
Output: Paramètres du modèle x
Initialiser x aléatoirement;
for 𝑡 = 1 to 𝑁 do
Choisir aléatoirement un exemple d’entraînement 𝑖;
Calculer le gradient stochastique 𝑓𝑖′(x);
Mettre à jour les paramètres du modèle : x ← x − 𝜂 𝑓𝑖′(x);
end
Algorithm 6: Descente de gradient stochastique

Exemple explicite de Descente de Gradient Stochastique

(SGD)

Soit un ensemble de données d’entraînement constitué de 𝑛 exemples

(𝑥 𝑖 , 𝑦 𝑖 ), où 𝑥 𝑖 ∈ R et 𝑦 𝑖 ∈ R, et notre modèle de régression linéaire est :

𝑦 =𝑤·𝑥+𝑏

La fonction de coût que nous allons minimiser est l’erreur quadratique

moyenne (MSE) :

𝑛
1Õ
𝐽(𝑤, 𝑏) = (𝑦 𝑖 − (𝑤𝑥 𝑖 + 𝑏))2
𝑛
𝑖=1

Nous appliquons maintenant la descente de gradient stochastique pour

ajuster les paramètres 𝑤 et 𝑏.

22
Short title of document Exemple numérique

Input: Ensemble de données d’entraînement (𝑥 𝑖 , 𝑦 𝑖 ), taux

d’apprentissage 𝜂, nombre maximal d’itérations 𝑁
Output: Paramètres du modèle 𝑤 et 𝑏
Initialiser 𝑤 et 𝑏 aléatoirement;
for 𝑡 = 1 to 𝑁 do
Choisir aléatoirement un exemple d’entraînement (𝑥 𝑖 , 𝑦 𝑖 );
Calculer les gradients :
𝑓𝑤′ (𝑥 𝑖 , 𝑦 𝑖 ) = −2𝑥 𝑖 (𝑦 𝑖 − (𝑤𝑥 𝑖 + 𝑏))
𝑓𝑏′(𝑥 𝑖 , 𝑦 𝑖 ) = −2(𝑦 𝑖 − (𝑤𝑥 𝑖 + 𝑏));
Mettre à jour les paramètres du modèle :
𝑤 ← 𝑤 − 𝜂 𝑓𝑤′ (𝑥 𝑖 , 𝑦 𝑖 )
𝑏 ← 𝑏 − 𝜂 𝑓𝑏′(𝑥 𝑖 , 𝑦 𝑖 );
end
Algorithm 7: Descente de gradient stochastique pour régression li-
néaire

Exécution de l’algorithme

Supposons que nous avons un ensemble de données d’entraînement

simple :

(𝑥1 , 𝑦1 ) = (1, 2), (𝑥2 , 𝑦2 ) = (2, 3), (𝑥3 , 𝑦3 ) = (3, 4)

Nous initialisons les paramètres 𝑤 = 0 et 𝑏 = 0, avec un taux d’apprentis-

sage 𝜂 = 0.01 et un nombre d’itérations 𝑁 = 100.
À chaque itération, nous choisissons un exemple d’entraînement au
hasard, calculons les gradients par rapport à 𝑤 et 𝑏, puis mettons à jour les
paramètres du modèle.

23
Short title of document Exemple numérique

Conclusion

Après avoir exécuté l’algorithme pendant 𝑁 itérations, les paramètres

𝑤 et 𝑏 convergeront vers des valeurs qui minimisent l’erreur quadratique
moyenne. Cela nous permet d’ajuster notre modèle de régression linéaire
à l’ensemble de données d’entraînement.

Exemple détaillé de Descente de Gradient Stochastique (SGD)

Étape 1 : Initialisation
- Initialisez les paramètres 𝑤 = 0 et 𝑏 = 0. - Choisissez un taux d’ap-
prentissage 𝜂 = 0.1.
Étape 2 : Première itération (choisir le premier point (𝑥1 , 𝑦1 ) = (1, 2))

𝑦ˆ1 = 𝑤 · 𝑥1 + 𝑏 = 0 · 1 + 0 = 0

𝜕
= −2 · 𝑥 1 · (𝑦1 − 𝑦ˆ1 ) = −2 · 1 · (2 − 0) = −4
𝜕𝑤

𝜕
= −2 · (𝑦1 − 𝑦ˆ1 ) = −2 · (2 − 0) = −4
𝜕𝑏
Mise à jour des paramètres :

𝜕
𝑤 ← 𝑤−𝜂· = 0 − 0.1 · (−4) = 0.4
𝜕𝑤

𝜕
𝑏 ← 𝑏−𝜂· = 0 − 0.1 · (−4) = 0.4
𝜕𝑏
Étape 3 : Deuxième itération (choisir le second point (𝑥2 , 𝑦2 ) = (2, 4))

𝑦ˆ2 = 𝑤 · 𝑥2 + 𝑏 = 0.4 · 2 + 0.4 = 1.2

24
Short title of document Exemple numérique

𝜕
= −2 · 𝑥2 · (𝑦2 − 𝑦ˆ2 ) = −2 · 2 · (4 − 1.2) = −11.2
𝜕𝑤

𝜕
= −2 · (𝑦2 − 𝑦ˆ2 ) = −2 · (4 − 1.2) = −5.6
𝜕𝑏
Mise à jour des paramètres :

𝜕
𝑤 ← 𝑤−𝜂· = 0.4 − 0.1 · (−11.2) = 1.52
𝜕𝑤

𝜕
𝑏 ← 𝑏−𝜂· = 0.4 − 0.1 · (−5.6) = 0.96
𝜕𝑏
Étape 4 : Troisième itération (choisir le troisième point (𝑥 3 , 𝑦3 ) = (3, 5))

𝑦ˆ3 = 𝑤 · 𝑥3 + 𝑏 = 1.52 · 3 + 0.96 = 4.92

𝜕
= −2 · 𝑥3 · (𝑦3 − 𝑦ˆ3 ) = −2 · 3 · (5 − 4.92) = −0.48
𝜕𝑤

𝜕
= −2 · (𝑦3 − 𝑦ˆ3 ) = −2 · (5 − 4.92) = −0.16
𝜕𝑏
Mise à jour des paramètres :

𝜕
𝑤 ← 𝑤−𝜂· = 1.52 − 0.1 · (−0.48) = 1.568
𝜕𝑤

𝜕
𝑏 ← 𝑏−𝜂· = 0.96 − 0.1 · (−0.16) = 0.976
𝜕𝑏

25
Short title of document Exemple numérique

Exemple : Implémentation en Python de la Descente de Gradient Sto-

chastique

Figure 1.6 – Régression linéaire avec l’algorithme de Descente de Gradient Stochastique (SGD).
La figure montre l’ajustement de la droite de régression aux données générées. Les points bleus
représentent les données réelles (𝑥 𝑖 , 𝑦 𝑖 ) et la ligne rouge est la prédiction de la régression calculée
par SGD.

Soit un ensemble de données d’entraînement constitué de 𝑛 exemples

notés (𝑥 𝑖 , 𝑦 𝑖 ) pour 𝑖 = 1, 2, . . . , 𝑛, où 𝑥 𝑖 ∈ R𝑑 représente un vecteur de
caractéristiques et 𝑦 𝑖 ∈ R représente la valeur cible associée. L’objectif est
de trouver un modèle linéaire de la forme :

𝑦pred = 𝑥 · 𝑤 + 𝑏

où 𝑤 ∈ R𝑑 est le vecteur des poids et 𝑏 ∈ R est le biais. Où :

— 𝑋 est la matrice des caractéristiques d’entrée (taille 𝑛 × 𝑑),

26
Short title of document Exemple numérique

— 𝑤 est le vecteur des poids,

— 𝑏 est le biais.
La fonction de coût utilisée est l’erreur quadratique moyenne (Mean
Squared Error, MSE) :

𝑛
1Õ
MSE(𝑤, 𝑏) = (𝑦 𝑖 − 𝑦ˆ 𝑖 )2
𝑛
𝑖=1

Avec 𝑦ˆ 𝑖 = 𝑋𝑖 · 𝑤 + 𝑏.
La mise à jour des poids et du biais se fait selon les gradients de la
fonction de coût par rapport à 𝑤 et 𝑏 :

𝜕 2
MSE(𝑤, 𝑏) = 𝑋 𝑇 (𝑋 · 𝑤 + 𝑏 − 𝑦)
𝜕𝑤 𝑛
𝑛
𝜕 2Õ
MSE(𝑤, 𝑏) = (𝑋𝑖 · 𝑤 + 𝑏 − 𝑦 𝑖 )
𝜕𝑏 𝑛
𝑖=1

Les poids et le biais sont ensuite mis à jour à chaque itération de l’algo-
rithme SGD par :

𝜕
𝑤 := 𝑤 − 𝜂 ·MSE(𝑤, 𝑏)
𝜕𝑤
𝜕
𝑏 := 𝑏 − 𝜂 · MSE(𝑤, 𝑏)
𝜕𝑏
Où 𝜂 est le taux d’apprentissage.
L’algorithme 6 basé sur la Descente de Gradient Stochastique (SGD)
ajuste les paramètres de la régression linéaire à partir d’un ensemble de
données. La figure 1.6 montre les points de données (𝑥 𝑖 , 𝑦 𝑖 ) en bleu et la
droite de régression prédite en rouge. Le modèle est optimisé sur 1000
époques. Le tableau 1.3 résume les résultats obtenus, montrant la dimi-
nution de la perte MSE à chaque époque, ce qui indique la convergence
du modèle. Les poids 𝑤 du modèle sont également affichés après chaque
époque.

27
Short title of document Exemple numérique

1
Époque Perte (MSE) Poids (𝑤)
0 3.012 [1.23, -0.47, 2.06, 0.38, 0.52]
100 2.403 [0.89, -0.45, 1.89, 0.32, 0.45]
200 1.672 [0.72, -0.40, 1.50, 0.29, 0.40]
300 1.134 [0.65, -0.37, 1.31, 0.26, 0.36]
400 0.902 [0.61, -0.34, 1.19, 0.24, 0.33]
500 0.786 [0.58, -0.32, 1.13, 0.23, 0.31]
600 0.754 [0.57, -0.31, 1.09, 0.22, 0.30]
700 0.723 [0.56, -0.30, 1.05, 0.21, 0.29]
800 0.695 [0.55, -0.29, 1.02, 0.21, 0.28]
900 0.672 [0.54, -0.28, 0.99, 0.20, 0.27]

Table 1.3 – Résumé des résultats de l’entraînement du modèle avec SGD. Les poids sont mis à jour
à chaque époque et la perte (MSE) diminue à mesure que le modèle converge.

Exemple d’Application : Réseaux de Neurones Convolutifs

(CNN)2

Les réseaux de neurones convolutifs (Convolutional Neural Networks,

CNN) sont couramment utilisés pour des tâches de vision par ordina-
teur comme la classification d’images, la détection d’objets, etc. Pour com-
prendre comment fonctionnent les CNN sans aucune "boîte noire", nous
devons détailler chaque étape mathématique. Voici les étapes principales
avec leurs formules mathématiques :

1. Une époque fait référence à un cycle complet où l’algorithme de machine learning

utilise l’ensemble du jeu de données pour mettre à jour les paramètres du modèle. Un
modèle peut être entraîné sur plusieurs époques, ce qui signifie que le jeu de données est
vu plusieurs fois durant l’entraînement.
2. Section facultatif.

28
Short title of document Exemple numérique

Figure 1.7 – Un CNN est organisé en deux parties : l’extraction de l’information et l’analyse de
cette information (crédit : Lambert Rosique)

1. Convolution

La convolution est l’opération fondamentale d’un CNN. Elle consiste

à appliquer un filtre (ou noyau) sur l’entrée pour produire une carte de
caractéristiques (feature map).
Pour une entrée 2D (image) 𝐼 et un filtre 𝐾 de dimensions (ℎ, 𝑤), la
sortie (feature map) 𝑆 est calculée par :

ℎ−1 𝑤−1
Õ Õ
𝑆(𝑖, 𝑗) = (𝐼 ∗ 𝐾)(𝑖, 𝑗) = 𝐼(𝑖 + 𝑚, 𝑗 + 𝑛) · 𝐾(𝑚, 𝑛)
𝑚=0 𝑛=0

où 𝐼(𝑖, 𝑗) est le pixel de l’image d’entrée à la position (𝑖, 𝑗), et 𝐾(𝑚, 𝑛) est
le poids du filtre à la position (𝑚, 𝑛).

2. Ajout de Biais

Après la convolution, un biais est souvent ajouté à chaque valeur de la

carte de caractéristiques :

𝑆(𝑖, 𝑗) = (𝐼 ∗ 𝐾)(𝑖, 𝑗) + 𝑏

où 𝑏 est un biais appris pour chaque filtre.

29
Short title of document Exemple numérique

3. Fonction d’Activation (ReLU)

Une fonction d’activation non linéaire, comme la fonction ReLU (Recti-

fied Linear Unit), est appliquée à chaque élément de la carte de caractéris-
tiques pour introduire la non-linéarité :

ReLU(𝑥) = max(0, 𝑥)

Ainsi, la carte de caractéristiques activée est donnée par :

𝐴(𝑖, 𝑗) = ReLU(𝑆(𝑖, 𝑗))

4. Pooling (Sous-échantillonnage)

Le pooling est utilisé pour réduire les dimensions spatiales de la carte de

caractéristiques, tout en conservant les informations les plus importantes.
Le pooling le plus courant est le Max Pooling, qui prend le maximum d’une
région de taille fixe (par exemple, 2 × 2) :

𝑃(𝑖, 𝑗) = max{𝐴(2𝑖, 2𝑗), 𝐴(2𝑖 + 1, 2𝑗), 𝐴(2𝑖, 2𝑗 + 1), 𝐴(2𝑖 + 1, 2𝑗 + 1)}

où 𝑃(𝑖, 𝑗) est la valeur de la carte de caractéristiques après le pooling à

la position (𝑖, 𝑗).

5. Aplatissage (Flattening)

Après plusieurs couches de convolution et de pooling, la sortie est

aplatie en un vecteur 1D pour être utilisé dans des couches entièrement
connectées (dense layers). Si l’entrée après le pooling est de taille 𝑛 × 𝑛 × 𝑑,
elle est transformée en un vecteur de taille 𝑛 2 × 𝑑.

30
Short title of document Exemple numérique

6. Couche Entièrement Connectée (Fully Connected Layer)

La couche entièrement connectée prend le vecteur aplati et applique

une transformation linéaire suivie d’une activation non linéaire. Pour un
vecteur d’entrée 𝑥 et des poids 𝑊 et biais 𝑏, la sortie est :

𝑦 = Activation(𝑊 · 𝑥 + 𝑏)

où l’activation peut être une fonction telle que la fonction sigmoïde,

ReLU, ou softmax pour la classification.

7. Fonction de Perte

Pour entraîner le CNN, une fonction de perte est définie pour mesurer
la différence entre la sortie prédite et la sortie réelle. Pour la classification,
la cross-entropy est couramment utilisée :

𝐶
Õ
𝐿=− 𝑦 𝑖 log( 𝑦ˆ 𝑖 )
𝑖=1

où 𝑦 𝑖 est la véritable étiquette (one-hot encodée) et 𝑦ˆ 𝑖 est la probabilité

prédite par le réseau pour la classe 𝑖. Différentes fonctions de perte sont
rapportées dans le tableau 1.4.

31
Short title of document Exemple numérique

Table 1.4 – Tableau des différentes fonctions de perte et leurs applications courantes en apprentis-
sage machine.

Fonction de Perte Formule Mathématique Domaine d’Application

Perte d’Erreur Qua- Régression (réduit la dis-

dratique Moyenne 𝑁 tance quadratique entre
1 Õ
(Mean Squared 𝐿(𝑦, 𝑦)
ˆ = (𝑦 𝑖 − 𝑦ˆ 𝑖 )2 les valeurs prédites et les
𝑁
𝑖=1
Error, MSE) vraies valeurs)

Perte Logarithmique 𝑁 Classification binaire (mi-

1 Õ
ou Cross-Entropy 𝐿(𝑦, 𝑦)
ˆ =− (𝑦 𝑖 log( 𝑦ˆ 𝑖 ) nimise l’entropie croisée
𝑁
𝑖=1
(Log Loss / Cross- entre les vraies étiquettes et
Entropy Loss) +(1 − 𝑦 𝑖 ) log(1 − 𝑦ˆ 𝑖 )) les probabilités prédites)

Perte Entropie Croi-

𝐶
Classification multi-
sée Catégorique Õ
𝐿(𝑦, 𝑦)
ˆ =− 𝑦 𝑖 log( 𝑦ˆ 𝑖 ) classes (ex : classification
(Categorical Cross-
𝑖=1 d’images)
Entropy)

Perte Hinge (Hinge 𝑁

Õ Classification binaire (uti-
Loss) 𝐿(𝑦, 𝑦)
ˆ = max(0, 1 − 𝑦 𝑖 · 𝑦ˆ 𝑖 ) lisé dans les SVM)
𝑖=1

𝑁
1 Õ
𝐿(𝑦, 𝑦)
ˆ = 𝑙 𝑖 , où
𝑁
Perte Huber (Huber 𝑖=1 Régression robuste (moins
Loss) sensible aux outliers)
(
2 (𝑦 𝑖 − 𝑦ˆ 𝑖 ) si |𝑦 𝑖 − 𝑦ˆ 𝑖 | ≤ 𝛿
1 2
𝑙𝑖 =
𝛿(|𝑦 𝑖 − 𝑦ˆ 𝑖 | − 21 𝛿) sinon

32
Short title of document Exemple numérique

Fonction de Perte Formule Mathématique Domaine d’Application

𝑦 · 𝑦ˆ Apprentissage de simila-
Perte Cosine (Cosine
𝐿(𝑦, 𝑦)
ˆ =1− rité, modèles de recom-
Loss) ∥𝑦∥∥ 𝑦∥
ˆ
mandation

Classification des don-

Perte Focal (Focal nées déséquilibrées (par
ˆ = −𝛼(1 − 𝑦ˆ 𝑖 )𝛾 𝑦 𝑖 log( 𝑦ˆ 𝑖 )
𝐿(𝑦, 𝑦)
Loss) exemple, détection d’ob-
jets)

8. Propagation Rétrograde (Backpropagation)

Pour optimiser les poids et les biais, l’algorithme de rétropropagation

est utilisé. Il s’agit de calculer le gradient de la fonction de perte par rapport
à chaque paramètre du réseau et de mettre à jour ces paramètres à l’aide
de la descente de gradient :

𝜕𝐿
𝑤 new = 𝑤old − 𝜂
𝜕𝑤
𝜕𝐿
où 𝜂 est le taux d’apprentissage et 𝜕𝑤
est le gradient de la perte par
rapport au poids 𝑤.

Table 1.5 – Tableau des différentes formules de mise à jours des poids et leurs application dans
l’apprentissage automatique.

Algorithme d’Opti-
Mise à Jour des Poids Domaine d’Application
misation
Descente de Gra- Problèmes de grande
dient Stochastique 𝑤 𝑡+1 = 𝑤 𝑡 − 𝜂∇𝐿(𝑤 𝑡 ) échelle, apprentissage
(SGD) profond

33
Short title of document Exemple numérique

Algorithme d’Opti-
Mise à Jour des Poids Domaine d’Application
misation

Descente de Gra- 𝑣 𝑡+1 = 𝛽𝑣 𝑡 + 𝜂∇𝐿(𝑤 𝑡 ),

Accélère la convergence,
dient avec Momen-
𝑤 𝑡+1 = 𝑤 𝑡 − 𝑣 𝑡+1 réduit les oscillations
tum

Apprentissage adaptatif,
AdaGrad (Adaptive 𝜂
𝑤 𝑡+1 = 𝑤 𝑡 − √ ∇𝐿(𝑤 𝑡 ) rareté des données (NLP,
Gradient) 𝐺𝑡 + 𝜖
vision par ordinateur)

RMSprop (Root 𝐸[𝑔 2 ]𝑡 = 𝛽𝐸[𝑔 2 ]𝑡−1 + (1 − 𝛽)𝑔𝑡2 , Stabilise l’apprentissage,

Mean Square Propa- recommandé pour les
𝜂
gation) 𝑤 𝑡+1 = 𝑤 𝑡 − p ∇𝐿(𝑤 𝑡 ) réseaux récurrents
𝐸[𝑔 2 ]𝑡 + 𝜖

𝑚𝑡 = 𝛽 1 𝑚𝑡−1 + (1 − 𝛽 1 )∇𝐿(𝑤 𝑡 ),

𝑣 𝑡 = 𝛽 2 𝑣 𝑡−1 + (1 − 𝛽2 )(∇𝐿(𝑤 𝑡 ))2 Méthode populaire pour

Adam (Adaptive Mo-
𝑚𝑡 𝑣𝑡 la plupart des réseaux de
ment Estimation) 𝑚ˆ𝑡 = , 𝑣
ˆ 𝑡 =
1 − 𝛽 1𝑡 1 − 𝛽 2𝑡 neurones profonds
𝜂𝑚
ˆ𝑡
𝑤 𝑡+1 = 𝑤 𝑡 − √
𝑣ˆ 𝑡 + 𝜖

34
Short title of document Exemple numérique

Algorithme d’Opti-
Mise à Jour des Poids Domaine d’Application
misation

𝑣 𝑡+1 = 𝛽𝑣 𝑡 + 𝜂∇𝐿(𝑤 𝑡 − 𝛽𝑣 𝑡 ), Améliore le taux de conver-

Nesterov Accelera-
gence par rapport à SGD
ted Gradient (NAG)
𝑤 𝑡+1 = 𝑤 𝑡 − 𝑣 𝑡+1 avec momentum

Utilise une approximation de

L-BFGS (Limited-
la matrice Hessienne pour une
memory Broyden- Régression logistique, pe-
mise à jour des poids plus pré-
Fletcher-Goldfarb- tits réseaux de neurones
cise sans stocker la matrice com-
Shanno)
plète

Les poids et biais des couches convolutives et entièrement connectées

sont mis à jour par gradient à chaque itération. Un CNN apprend des
caractéristiques hiérarchiques et fait des prédictions. Le tableau 1.5 pré-
sente les formules de mise à jour des poids. Dans cet exemple, le taux
d’apprentissage 𝜂 est constant et la fonction 𝑙𝑟() retourne une valeur fixe.

35