Une introduction douce à l’optimisation des fonctions

L'optimisation des fonctions est un domaine d'étude fondamental et les techniques sont utilisées dans presque tous les domaines quantitatifs.

Il est important de noter que l’optimisation des fonctions est au cœur de presque tous les algorithmes d’apprentissage automatique et des projets de modélisation prédictive. En tant que tel, il est essentiel de comprendre ce qu’est l’optimisation des fonctions, la terminologie utilisée dans le domaine et les éléments qui constituent un problème d’optimisation des fonctions.

Dans ce tutoriel, vous découvrirez une introduction douce à l'optimisation des fonctions.

Après avoir terminé ce tutoriel, vous saurez :

• Les trois éléments de l’optimisation des fonctions : solutions candidates, fonctions objectives et coût.
• La conceptualisation de l'optimisation des fonctions en tant que navigation dans un espace de recherche et une surface de réponse.
• La différence entre les optima globaux et les optima locaux lors de la résolution d'un problème d'optimisation de fonction.

Démarrez votre projet avec mon nouveau livre Optimization for Machine Learning, comprenant des tutoriels pas à pas et les fichiers code source Python pour tous exemples.

Présentation du didacticiel

Ce didacticiel est divisé en quatre parties ; ils sont:

1. Optimisation des fonctions
2. Solutions pour les candidats
3. Fonctions objectives
4. Coûts d'évaluation

Optimisation des fonctions

L'optimisation des fonctions est un sous-domaine des mathématiques et, de nos jours, elle est abordée à l'aide de méthodes de calcul numérique.

L'Optimisation de fonctions continues (« optimisation de fonctions » ici en abrégé) appartient à un domaine d'étude plus large appelé optimisation mathématique.

Elle se distingue des autres types d'optimisation car elle implique de trouver des solutions candidates optimales composées de variables d'entrée numériques, par opposition aux solutions candidates composées de séquences ou de combinaisons (par exemple, l'optimisation combinatoire).

L’optimisation des fonctions est un ensemble de techniques largement utilisées dans pratiquement toutes les disciplines scientifiques et techniques.

Les gens optimisent. Les investisseurs cherchent à créer des portefeuilles qui évitent les risques excessifs tout en obtenant un taux de rendement élevé. […] L'optimisation est un outil important en science de la décision et dans l'analyse des systèmes physiques.

— Page 2, Optimisation numérique, 2006.

Il joue un rôle central dans l'apprentissage automatique, car presque tous les algorithmes d'apprentissage automatique utilisent l'optimisation des fonctions pour adapter un modèle à un ensemble de données d'entraînement.

Par exemple, ajuster une ligne à un ensemble de points nécessite de résoudre un problème d’optimisation. Tout comme l'ajustement d'une régression linéaire ou d'un modèle de réseau neuronal sur un ensemble de données d'entraînement.

De cette manière, l’optimisation fournit un outil permettant d’adapter un modèle général à une situation spécifique. L'apprentissage est traité comme un problème d'optimisation ou de recherche.

En pratique, l'optimisation de fonction décrit une classe de problèmes permettant de trouver l'entrée d'une fonction donnée qui aboutit à la sortie minimale ou maximale de la fonction.

L'objectif dépend de certaines caractéristiques du système, appelées variables ou inconnues. Notre objectif est de trouver les valeurs des variables qui optimisent l'objectif.

— Page 2, Optimisation numérique, 2006.

L'optimisation de fonction implique trois éléments : l'entrée de la fonction (par exemple x), la fonction objectif elle-même (par exemple f()) et la sortie de la fonction (par exemple >coût).

• Entrée (x) : l'entrée de la fonction à évaluer, par ex. une solution candidate.
• Fonction (f()) : fonction objectif ou fonction cible qui évalue les entrées.
• Coût : résultat de l'évaluation d'une solution candidate avec la fonction objectif, minimisée ou maximisée.

Examinons de plus près chaque élément tour à tour.

Solutions pour les candidats

Une solution candidate est une entrée unique pour la fonction objectif.

La forme d'une solution candidate dépend des spécificités de la fonction objectif. Il peut s'agir d'un nombre à virgule flottante unique, d'un vecteur de nombres, d'une matrice de nombres ou aussi complexe que nécessaire pour le domaine spécifique du problème.

Le plus souvent, des vecteurs de nombres. Pour un problème de test, le vecteur représente les valeurs spécifiques de chaque variable d'entrée de la fonction (x=x1, x2, x3, …, xn). Pour un modèle d'apprentissage automatique, le vecteur peut représenter des coefficients ou des poids du modèle.

Mathématiquement parlant, l'optimisation est la minimisation ou la maximisation d'une fonction soumise à des contraintes sur ses variables.

— Page 2, Optimisation numérique, 2006.

Il peut y avoir des contraintes imposées par le domaine du problème ou la fonction objectif sur les solutions candidates. Cela peut inclure des aspects tels que :

• Le nombre de variables (1, 20, 1 000 000, etc.)
• Le type de données des variables (entier, binaire, à valeur réelle, etc.)
• La plage de valeurs acceptées (entre 0 et 1, etc.)

Il est important de noter que les solutions candidates sont discrètes et nombreuses.

L’univers des solutions possibles est peut-être vaste, trop vaste pour être énuméré. Au lieu de cela, le mieux que nous puissions faire est d’échantillonner les solutions candidates dans l’espace de recherche. En tant que praticien, nous recherchons un algorithme d'optimisation qui utilise au mieux les informations disponibles sur le problème pour échantillonner efficacement l'espace de recherche et localiser une bonne ou la meilleure solution candidate.

• Espace de recherche : univers de solutions candidates défini par le nombre, le type et la plage d'entrées acceptées dans la fonction objectif.

Enfin, les solutions candidates peuvent être classées en fonction de leur évaluation par la fonction objectif, ce qui signifie que certaines sont meilleures que d'autres.

Fonctions objectives

La fonction objectif est spécifique au domaine du problème.

Il peut s'agir d'une fonction de test, par ex. une équation bien connue avec un nombre spécifique de variables d'entrée, dont le calcul renvoie le coût de l'entrée. Les optima des fonctions de test sont connus, permettant de comparer les algorithmes en fonction de leur capacité à naviguer efficacement dans l'espace de recherche.

Dans l'apprentissage automatique, la fonction objective peut impliquer de connecter la solution candidate à un modèle et de l'évaluer par rapport à une partie de l'ensemble de données d'entraînement, et le coût peut être un score d'erreur, souvent appelé perte du modèle.

La fonction objectif est facile à définir, bien que coûteuse à évaluer. L'efficacité de l'optimisation des fonctions fait référence à la minimisation du nombre total d'évaluations de fonctions.

Même si la fonction objectif est facile à définir, elle peut être difficile à optimiser. La difficulté d'une fonction objective peut aller de la capacité à résoudre analytiquement la fonction directement en utilisant le calcul ou l'algèbre linéaire (facile), à l'utilisation d'un algorithme de recherche local (modéré) et à l'utilisation d'un algorithme de recherche global (difficile).

La difficulté d’une fonction objective dépend de ce que l’on sait sur la fonction. Souvent, cela ne peut pas être déterminé en examinant simplement l’équation ou le code permettant d’évaluer les solutions candidates. Il fait plutôt référence à la structure de la surface de réponse.

La surface de réponse (ou paysage de recherche) est la structure géométrique du coût par rapport à l'espace de recherche des solutions candidates. Par exemple, une surface de réponse lisse suggère que de petits changements dans l’entrée (solutions candidates) entraînent de petits changements dans le résultat (coût) de la fonction objectif.

• Surface de réponse : propriétés géométriques du coût de la fonction objectif en réponse aux modifications apportées aux solutions candidates.

La surface de réponse peut être visualisée en faibles dimensions, par ex. pour les solutions candidates avec une ou deux variables d’entrée. Une entrée unidimensionnelle peut être tracée sous forme de nuage de points 2D avec les valeurs d'entrée sur l'axe des x et le coût sur l'axe des y. Une entrée bidimensionnelle peut être tracée sous forme de tracé de surface 3D avec des variables d'entrée sur les axes x et y, et la hauteur de la surface représentant le coût.

Dans un problème de minimisation, les mauvaises solutions seraient représentées par des collines dans la surface de réponse et les bonnes solutions seraient représentées par des vallées. Ceci serait inversé pour maximiser les problèmes.

La structure et la forme de cette surface de réponse déterminent la difficulté qu’un algorithme aura à naviguer dans l’espace de recherche jusqu’à une solution.

La complexité des fonctions objectives réelles signifie que nous ne pouvons pas analyser la surface de manière analytique, et la dimensionnalité élevée des entrées et le coût de calcul des évaluations de fonctions rendent difficile la cartographie et le tracé des fonctions objectives réelles.

Coûts d'évaluation

Le coût d’une solution candidate est presque toujours un seul nombre réel.

L'échelle des valeurs de coût variera en fonction des spécificités de la fonction objectif. En général, la seule comparaison significative des valeurs de coût est celle avec d'autres valeurs de coût calculées par la même fonction objectif.

Le résultat minimum ou maximum de la fonction est appelé l'optima de la fonction, généralement simplifié au simple minimum. Toute fonction que nous souhaitons maximiser peut être convertie en minimisation en ajoutant un signe négatif devant le coût renvoyé par la fonction.

Dans l'optimisation globale, la véritable solution globale du problème d'optimisation est trouvée ; le compromis est l’efficacité. Dans le pire des cas, la complexité des méthodes d’optimisation globale croît de façon exponentielle avec la taille des problèmes…

— Page 10, Optimisation convexe, 2004.

Une fonction objectif peut avoir une seule meilleure solution, appelée optimal global de la fonction objectif. Alternativement, la fonction objectif peut avoir de nombreux optima globaux, auquel cas nous pouvons être intéressés à en localiser un ou tous.

De nombreuses méthodes d'optimisation numérique recherchent des minima locaux. Les minimums locaux sont localement optimaux, mais on ne sait généralement pas si un minimum local est un minimum global.

— Page 8, Algorithmes d'optimisation, 2019.

En plus des optima globaux, une fonction peut avoir des optima locaux, qui sont de bonnes solutions candidates qui peuvent être relativement faciles à localiser, mais pas aussi bonnes que les optima globaux. Les optima locaux peuvent apparaître comme des optima globaux pour un algorithme de recherche, par ex. peuvent se trouver dans une vallée de la surface de réponse, auquel cas nous pourrions les qualifier de trompeurs car l'algorithme les localisera facilement et restera bloqué, échouant à localiser les optima globaux.

• Global Optima : la solution candidate avec le meilleur coût par rapport à la fonction objectif.
• Optimums locaux. Les solutions candidates sont bonnes mais pas aussi bonnes que les optima globaux.

La nature relative des valeurs de coût signifie qu'une référence de performance sur des problèmes difficiles peut être établie à l'aide d'un algorithme de recherche naïf (par exemple aléatoire) et que la « qualité » des solutions optimales trouvées par des algorithmes de recherche plus sophistiqués peut être comparée par rapport à la référence.

Les solutions candidates sont souvent très simples à décrire et très faciles à construire. La partie difficile de l’optimisation des fonctions consiste à évaluer les solutions candidates.

Résoudre un problème d'optimisation de fonction ou une fonction objectif fait référence à la recherche des optima. L'objectif général du projet est de localiser une solution candidate spécifique avec un bon ou le meilleur coût, en tenant compte du temps et des ressources disponibles. Dans des problèmes simples et modérés, nous pouvons être en mesure de localiser exactement la solution candidate optimale et avoir une certaine certitude que nous l'avons fait.

De nombreux algorithmes pour les problèmes d'optimisation non linéaire recherchent uniquement une solution locale, un point auquel la fonction objectif est plus petite qu'en tout autre point proche réalisable. Ils ne trouvent pas toujours la solution globale, qui est le point ayant la valeur de fonction la plus faible parmi tous les points réalisables. Des solutions globales sont nécessaires dans certaines applications, mais pour de nombreux problèmes, elles sont difficiles à reconnaître et encore plus difficiles à localiser.

— Page 6, Optimisation numérique, 2006.

Sur des problèmes plus difficiles, nous pouvons nous contenter d'une solution candidate relativement bonne (par exemple assez bonne) compte tenu du temps disponible pour le projet.

Lectures complémentaires

Cette section fournit plus de ressources sur le sujet si vous souhaitez approfondir.

Livres

• Algorithmes d'optimisation, 2019.
• Optimisation convexe, 2004.
• Optimisation numérique, 2006.

Articles

• Optimisation mathématique, Wikipédia.

Résumé

Dans ce didacticiel, vous avez découvert une introduction douce à l'optimisation des fonctions.

Concrètement, vous avez appris :

• Les trois éléments de l’optimisation des fonctions : solutions candidates, fonctions objectives et coût.
• La conceptualisation de l'optimisation des fonctions en tant que navigation dans un espace de recherche et une surface de réponse.
• La différence entre les optima globaux et les optima locaux lors de la résolution d'un problème d'optimisation de fonction.

Avez-vous des questions ?
Posez vos questions dans les commentaires ci-dessous et je ferai de mon mieux pour y répondre.