1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
L'optimisation est une branche des mathématiques appliquées qui cherche à trouver les points pour lequels une fonctions réalise un certain nombre d'exigences.
Le lecteur pourra se reférer par exemple au libre de Phillipe G. Ciarlet \textit{Introduction à l'analyse numérique matricielle et à l'optimisation}~\cite{ciarlet} pour une présentation très complète d'un grand nombre de techniques.
Dans ce manuscrit nous ne nous interesseront qu'a deux type de problèmes liées à l'apprantissange automatique et surtout au réseaux de neuronnes.
Le premier de ces problèmes est la minimisation sans contrainte d'une fonctionelle convexe.
Cela permet l'entraînement de modèle d'apprantissage automatique à l'aide d'une fonction de coût.
Le second problème reprend le premier mais y ajoute des contraintes.
C'est à dire, comme minimise-t'on le coût tout en garantissant certaines conditions ?
\subsubsection{Optimisation sans contrainte : Descente de gradient}
\label{sec:background-opti-sgd}
Nous appellons fonctionelles les fonctions $\mathbb{R}^n$ dans $\mathbb{R}$.
Soit $J$ une fonctionelle convexe, nous cherchons à trouver $x\in\mathbb{R}$ tel que $J(x) = \text{inf}\{J(t)\mid t\in\mathbb{R}\}$.
Pour simplifier cette rapide présentation, nous supposerons que $J$ à toujours les conditions de régularité (diférentiabilié) suffisante pour les opérations que nous appliquerons.
Pour trouver $x$ qui minimise $J$ une des méthode les plus utilisé en apprentissage automatique est la descente de gradient.
Il s'agit de construire une suite $(x_k)_{k\in\mathbb{N}}$ telle que à chauqe étape la direction de descente soit optimale.
L'idée pour arriver à cela et de considérer une approximation de l'accroissement de $J$ en utiliant la définition du gradient.
On cherche $h$ tel que $||h||=1$ et $J(x_k+h)$ soit minimal.
D'après la définition du gradient
\begin{equation*}
J(x_k+h) = J(x_k) + \langle\nabla J(x_k),h\rangle + ||h||\epsilon(h)
\end{equation*}
On cherche alors à résoudre (*) : $min_{||h||=1}\langle\nabla J(x_k),h\rangle$.
D'après l'inégalite de Cauchy-Schwartz
\begin{equation*}
\forall h~||h||=1\implies~|\langle\nabla J(x_k),h\rangle |\leq ||\nabla J(x_k)||
\end{equation*}
Et aussi
\begin{equation*}
\forall h~||h||=1\implies~\left(|\langle\nabla J(x_k),h\rangle | =||\nabla J(x_k)||
\iff h = \pm \frac{\nabla J(x_k)}{||\nabla J(x_k)||}\right)
\end{equation*}
$h=-\frac{\nabla J(x_k)}{||\nabla J(x_k)||}$ est donc solution de (*) pour que $\langle\nabla J(x_k),h\rangle$ soit négatif.
Ainsi la méthode de déscente de gradient est définit par la suite
$x_{k+1}=x_k-l_k\nabla J(x_k)$.
$l_k$ est appelé le pas.
En théorie nous pouvons lire dans le libre de Ciarlet qu'il existe de multiple manière de trouver un pas optimale ou approprié à la fonctionelle $J$.
Cependant, en apprantissage automatique le hypothèse necessaire pour obtenir l'optimalité sont souvent absentes, en pratique le pas est souvant choisit constant $\exists c\forall k~l_k=c$.
Nous montrons dans la Figure~\ref{fig:background-opti-gd} le fonctionement de la méthode de gradient à pas fixe en dimension un pour une fonctionelle convexe.
Avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum.
\begin{figure}
\centering
\begin{subfigure}{0.45\linewidth}
\centering
\includegraphics[width=0.66\linewidth]{background/figure/opti/f.pdf}
\caption{La suite $u$ approche un minimum locale de la fonction $f$.}
\end{subfigure}
\hspace{1cm}
\begin{subfigure}{0.45\linewidth}
\centering
\includegraphics[width=0.66\linewidth]{background/figure/opti/conv.pdf}
\caption{Convergence des l'écart entre $u$ et le minimum vers $0$ en fonction des itérations.}
\end{subfigure}
\caption{Convergence de la méthode de gradient.}
\label{fig:background-opti-gd}
\end{figure}
\subsubsection{Optimisation sous contraintes : multiplicateurs de Lagrange}
\label{ref:background-opti-sous}
Pour expliquer ce qu'est l'optimisation sous contraintes, represnons les mots de Philipe G. Ciarlet :
\textquote{On s'interesse au problème suivant : trouver des conditions \emph{nécessaires}, et des conditions \emph{suffisantes}, pour qu'un point d'un ensemble $U$ soit un extremum relatif de la restriction à l'ensemble $U$ d'une fonction $J$ définie sur un ensemble "plus grands". [...]
Un premier exemple est celui des \emph{extremums relatifs liés}, où l'ensemble $U$ est de la forme
\begin{equation*}
U=\{v\in V \mid \forall i\in m-1~\varphi_i(v)\leq 0\}
\end{equation*}
}
On introduit le Lagrangien de ce problèmes par la formule suivante:
\begin{equation*}
L:\left\{
\begin{matrix}
V\times\mathbb{R}^m_+\\
(v,\mu)\mapsto J(v)+\sum_{i=0}^{m-1}\mu_i\varphi(v)
\end{matrix}
\right.
\end{equation*}
Pour respecter les contrainte du problèmes, la méthode consiste à chercher un point selle de $L$,
c'est-à-dire, un point $(u,\lambda)\in V\times \mathbb{R}^m_+$ tel que
\begin{equation*}
sup L(\square,\lambda)=L(u,\lambda)\wedge inf L(u,\square)=L(u,\lambda)
\end{equation*}
$u$ est alors solution du problème.
Il est donc suffisant de connaitre $\lambda$ appelé \emph{multiplicateurs de Lagrange} pour pouvoir trouver $u$ en se ramensant au cas sans contraintes de la section précédente.
Trouver $\lambda$ s'apelle le \emph{problème dual} en contrepartie de la recheche de $u$ qui est le \emph{problème primal}.
Le problème dual bénéficie du fait que ces contraintes sont plus simples car il sagi uniquement de la positivité des multiplicateur de Lagrange.
Le problème dual s'écrit donc $sup (inf_{v\in V}L(v,\square))$.
Pour une présentation plus complète des multiplicateurs de Lagrange et de la dualité voir les Sections 7.2 et 9.3 du Livre de Ciarlet~\cite{ciarlet}
|
