diff options
Diffstat (limited to 'background/opti.tex')
| -rw-r--r-- | background/opti.tex | 30 |
1 files changed, 15 insertions, 15 deletions
diff --git a/background/opti.tex b/background/opti.tex index bb2ec17..1043861 100644 --- a/background/opti.tex +++ b/background/opti.tex @@ -1,18 +1,18 @@ L'optimisation est une branche des mathématiques appliquées qui cherche à trouver les points pour lesquels une fonction réalise un certain nombre d'exigences. Le lecteur pourra se référer par exemple au livre 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 intéresserons qu'a deux type de problèmes liées à l'apprentissage automatique et surtout au réseaux de neurones. +Dans ce manuscrit nous ne nous intéresserons qu'a deux types de problèmes liés à l'apprentissage automatique et surtout aux réseaux de neurones. Le premier de ces problèmes est la minimisation sans contrainte d'une fonctionnelle convexe. Cela permet l'entraînement de modèles d'apprentissage automatique à l'aide de fonctions de coûts. 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 ? +C'est-à-dire, comment minimise-t'on le coût tout en garantissant certaines conditions ? -\subsubsection{Optimisation sans contrainte : Descente de gradient} +\subsubsection{Optimisation sans contrainte : descente de gradient} \label{sec:background-opti-sgd} Nous appelons fonctionnelles les fonctions de $\mathbb{R}^n$ dans $\mathbb{R}$. Soit $J$ une fonctionnelle convexe, nous cherchons à trouver $x\in\mathbb{R}^n$ tel que $J(x) = \text{inf}\{J(t)\mid t\in\mathbb{R}^n\}$. -Pour simplifier cette rapide présentation, nous supposerons que $J$ à toujours les conditions de régularité (différentiabilité) 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 à chaque étape la direction de descente soit optimale. +Pour simplifier cette rapide présentation, nous supposerons que $J$ a toujours les conditions de régularité (différentiabilité) suffisantes pour les opérations que nous appliquerons. +Pour trouver $x$ qui minimise $J$ une des méthodes les plus utilisées en apprentissage automatique est la descente de gradient. +Il s'agit de construire une suite $(x_k)_{k\in\mathbb{N}}$ telle qu'à chaque étape la direction de descente soit optimale. L'idée pour arriver à cela est de considérer une approximation de l'accroissement de $J$ en utilisant la définition du gradient. On cherche $h$ tel que $||h||=1$ et $J(x_k+h)$ soit minimal. @@ -32,11 +32,11 @@ Et aussi \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 descente de gradient est définit par la suite +Ainsi la méthode de descente de gradient est définie 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 livre de Ciarlet qu'il existe de multiple manières de trouver un pas optimale ou approprié à la fonctionnelle $J$. -Cependant, en apprentissage automatique les hypothèses nécessaires pour obtenir l'optimale sont souvent absentes, en pratique le pas est souvent choisit constant $\exists c\forall k~l_k=c$. +En théorie, nous pouvons lire dans le livre de Ciarlet qu'il existe de multiples manières de trouver un pas optimal ou approprié à la fonctionnelle $J$. +Cependant, en apprentissage automatique les hypothèses nécessaires pour obtenir l'optimale sont souvent absentes, en pratique le pas est souvent choisi constant $\exists c\forall k~l_k=c$. Nous montrons dans la Figure~\ref{fig:background-opti-gd} le fonctionnement de la méthode de gradient à pas fixe en dimension un pour une fonctionnelle convexe avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum. @@ -45,13 +45,13 @@ avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum \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$.} + \caption{La suite $u$ approche un minimum local 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.} + \caption{Convergence de 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} @@ -62,14 +62,14 @@ avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum \subsubsection{Optimisation sous contraintes : multiplicateurs de Lagrange} \label{sec:background-opti-sous} Pour expliquer ce qu'est l'optimisation sous contraintes, reprenons les mots de Philipe G. Ciarlet : -\textquote{On s'intéresse 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". [...] +\textquote{On s'intéresse 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 grand". [...] 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: +On introduit le lagrangien de ce problème par la formule suivante: \begin{equation*} L:\left\{ \begin{matrix} @@ -79,7 +79,7 @@ On introduit le lagrangien de ce problèmes par la formule suivante: \right. \end{equation*} -Pour respecter les contrainte du problèmes, la méthode consiste à chercher un point selle de $L$, +Pour respecter les contraintes du problème, 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) @@ -88,7 +88,7 @@ c'est-à-dire, un point $(u,\lambda)\in V\times \mathbb{R}^m_+$ tel que $u$ est alors solution du problème. Il est donc suffisant de connaître $\lambda$ appelé \emph{multiplicateurs de Lagrange} pour pouvoir trouver $u$ en se ramenant au cas sans contraintes de la section précédente. Trouver $\lambda$ s'appelle le \emph{problème dual} en contrepartie de la recherche de $u$ qui est le \emph{problème primal}. -Le problème dual bénéficie du fait que les contraintes sont plus simples car il s'agit uniquement de la positivité des multiplicateur de Lagrange. +Le problème dual bénéficie du fait que les contraintes sont plus simples car il s'agit uniquement de la positivité des multiplicateurs 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} |