Optimisation de fonctions univariées en Python

Comment optimiser une fonction avec une variable ?

L'optimisation de fonction univariée consiste à trouver l'entrée d'une fonction qui aboutit à la sortie optimale d'une fonction objectif.

Il s'agit d'une procédure courante dans l'apprentissage automatique lors de l'ajustement d'un modèle avec un paramètre ou du réglage d'un modèle doté d'un seul hyperparamètre.

Un algorithme efficace est nécessaire pour résoudre des problèmes d'optimisation de ce type qui trouvera la meilleure solution avec le nombre minimum d'évaluations de la fonction objectif, étant donné que chaque évaluation de la fonction objectif pourrait être coûteuse en termes de calcul, comme l'ajustement et l'évaluation d'un modèle sur un ensemble de données.

Cela exclut les algorithmes coûteux de recherche sur grille et de recherche aléatoire et privilégie des algorithmes efficaces comme la méthode de Brent.

Dans ce didacticiel, vous découvrirez comment effectuer une optimisation de fonctions univariées en Python.

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

L'optimisation de fonction univariée implique de trouver une entrée optimale pour une fonction objectif qui prend un seul argument continu.
Comment effectuer une optimisation de fonction univariée pour une fonction convexe sans contrainte.
Comment effectuer une optimisation de fonction univariée pour une fonction non convexe sans contrainte.

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 trois parties : ils sont:

Optimisation des fonctions univariées
Optimisation de la fonction convexe univariée
Optimisation de fonctions univariées non convexes

Optimisation des fonctions univariées

Nous devrons peut-être trouver une valeur optimale d’une fonction qui prend un seul paramètre.

En apprentissage automatique, cela peut se produire dans de nombreuses situations, telles que :

Trouver le coefficient d'un modèle à adapter à un ensemble de données d'entraînement.
Trouver la valeur d'un seul hyperparamètre qui permet d'obtenir les meilleures performances du modèle.

C'est ce qu'on appelle l'optimisation de fonction univariée.

Nous pouvons être intéressés par le résultat minimum ou le résultat maximum de la fonction, bien que cela puisse être simplifié en minimisation car une fonction de maximisation peut être rendue minimisée en ajoutant un signe négatif à tous les résultats de la fonction.

Il peut y avoir ou non des limites sur les entrées de la fonction, ce qu'on appelle l'optimisation sans contrainte ou contrainte, et nous supposons que de petits changements dans l'entrée correspondent à de petits changements dans la sortie de la fonction, par ex. qu'il est lisse.

La fonction peut avoir ou non un seul optimal, même si nous préférons qu'elle ait un seul optimal et que la forme de la fonction ressemble à un grand bassin. Si tel est le cas, nous savons que nous pouvons échantillonner la fonction à un moment donné et trouver le chemin jusqu’aux minima de la fonction. Techniquement, on parle de fonction convexe pour la minimisation (concave pour la maximisation), et les fonctions qui n'ont pas cette forme de bassin sont appelées non convexes.

Fonction cible convexe : il existe un seul optimal et la forme de la fonction cible mène à cet optimal.

Néanmoins, la fonction cible est suffisamment complexe pour que nous ne connaissions pas la dérivée, ce qui signifie que nous ne pouvons pas simplement utiliser le calcul pour calculer analytiquement le minimum ou le maximum de la fonction où le gradient est nul. On parle alors de fonction non différentiable.

Même si nous pouvons échantillonner la fonction avec des valeurs candidates, nous ne connaissons pas l’entrée qui donnera le meilleur résultat. Cela peut être dû aux nombreuses raisons pour lesquelles il est coûteux d’évaluer les solutions candidates.

Par conséquent, nous avons besoin d’un algorithme qui échantillonne efficacement les valeurs d’entrée de la fonction.

Une approche pour résoudre les problèmes d’optimisation de fonctions univariées consiste à utiliser la méthode de Brent.

La méthode de Brent est un algorithme d'optimisation qui combine un algorithme de bissectrice (méthode de Dekker) et une interpolation quadratique inverse. Il peut être utilisé pour l’optimisation de fonctions univariées avec ou sans contrainte.

La méthode Brent-Dekker est une extension de la méthode de bissection. Il s'agit d'un algorithme de recherche de racine qui combine des éléments de la méthode sécante et de l'interpolation quadratique inverse. Il possède des propriétés de convergence fiables et rapides et constitue l'algorithme d'optimisation univariée de choix dans de nombreux packages d'optimisation numérique populaires.

— Pages 49-51, Algorithmes d'optimisation, 2019.

Les algorithmes de bissectrice utilisent une parenthèse (inférieure et supérieure) de valeurs d'entrée et divisent le domaine d'entrée, en le divisant en deux afin de localiser où se trouve l'optima dans le domaine, un peu comme une recherche binaire. La méthode de Dekker est un moyen d’y parvenir efficacement pour un domaine continu.

La méthode de Dekker reste bloquée sur des problèmes non convexes. La méthode de Brent modifie la méthode de Dekker pour éviter de rester coincé et se rapproche également de la dérivée seconde de la fonction objectif (appelée méthode sécante) dans le but d'accélérer la recherche.

En tant que telle, la méthode de Brent pour l’optimisation des fonctions univariées est généralement préférée à la plupart des autres algorithmes d’optimisation des fonctions univariées en raison de son efficacité.

La méthode de Brent est disponible en Python via la fonction SciPy minimise_scalar() qui prend le nom de la fonction à minimiser. Si votre fonction cible est contrainte à une plage, elle peut être spécifiée via l'argument « bounds ».

Il renvoie un objet OptimizeResult qui est un dictionnaire contenant la solution. Il est important de noter que la touche 'x' résume l'entrée pour l'optima, la touche 'fun' résume la sortie de la fonction pour l'optima et la touche 'nfev' résume le nombre d'évaluations de la fonction cible qui ont été effectuées.

...
# minimize the function
result = minimize_scalar(objective, method='brent')

Maintenant que nous savons comment effectuer une optimisation de fonctions univariées en Python, examinons quelques exemples.

Optimisation de la fonction convexe univariée

Dans cette section, nous explorerons comment résoudre un problème d’optimisation de fonction convexe univariée.

Tout d’abord, nous pouvons définir une fonction qui implémente notre fonction.

Dans ce cas, nous utiliserons une version offset simple de la fonction x^2, par exemple. une simple fonction de parabole (en forme de U). Il s'agit d'une fonction objectif de minimisation avec un optimal à -5,0.

# objective function
def objective(x):
	return (5.0 + x)**2.0

Nous pouvons tracer une grille grossière de cette fonction avec des valeurs d'entrée de -10 à 10 pour avoir une idée de la forme de la fonction cible.

L’exemple complet est répertorié ci-dessous.

# plot a convex target function
from numpy import arange
from matplotlib import pyplot

# objective function
def objective(x):
	return (5.0 + x)**2.0

# define range
r_min, r_max = -10.0, 10.0
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]
# plot inputs vs target
pyplot.plot(inputs, targets, '--')
pyplot.show()

L'exécution de l'exemple évalue les valeurs d'entrée dans notre plage spécifiée à l'aide de notre fonction cible et crée un tracé des entrées de fonction vers les sorties de fonction.

On voit la forme en U de la fonction et que l'objectif est à -5,0.

Remarque : dans un problème d'optimisation réel, nous ne serions pas en mesure d'effectuer aussi facilement autant d'évaluations de la fonction objectif. Cette fonction simple est utilisée à des fins de démonstration afin que nous puissions apprendre à utiliser l'algorithme d'optimisation.

Ensuite, nous pouvons utiliser l’algorithme d’optimisation pour trouver les optima.

...
# minimize the function
result = minimize_scalar(objective, method='brent')

Une fois optimisé, nous pouvons résumer le résultat, y compris la saisie et l'évaluation des optima et le nombre d'évaluations de fonctions nécessaires pour localiser les optima.

...
# summarize the result
opt_x, opt_y = result['x'], result['fun']
print('Optimal Input x: %.6f' % opt_x)
print('Optimal Output f(x): %.6f' % opt_y)
print('Total Evaluations n: %d' % result['nfev'])

Enfin, nous pouvons retracer la fonction et marquer l'optima pour confirmer qu'il se trouvait à l'endroit attendu pour cette fonction.

...
# define the range
r_min, r_max = -10.0, 10.0
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]
# plot inputs vs target
pyplot.plot(inputs, targets, '--')
# plot the optima
pyplot.plot([opt_x], [opt_y], 's', color='r')
# show the plot
pyplot.show()

L’exemple complet d’optimisation d’une fonction univariée convexe sans contrainte est répertorié ci-dessous.

# optimize convex objective function
from numpy import arange
from scipy.optimize import minimize_scalar
from matplotlib import pyplot

# objective function
def objective(x):
	return (5.0 + x)**2.0

# minimize the function
result = minimize_scalar(objective, method='brent')
# summarize the result
opt_x, opt_y = result['x'], result['fun']
print('Optimal Input x: %.6f' % opt_x)
print('Optimal Output f(x): %.6f' % opt_y)
print('Total Evaluations n: %d' % result['nfev'])
# define the range
r_min, r_max = -10.0, 10.0
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]
# plot inputs vs target
pyplot.plot(inputs, targets, '--')
# plot the optima
pyplot.plot([opt_x], [opt_y], 's', color='r')
# show the plot
pyplot.show()

L'exécution de l'exemple résout d'abord le problème d'optimisation et rapporte le résultat.

Remarque : Vos résultats peuvent varier en raison de la nature stochastique de l'algorithme ou de la procédure d'évaluation, ou des différences de précision numérique. Pensez à exécuter l’exemple plusieurs fois et comparez le résultat moyen.

Dans ce cas, nous pouvons voir que l'optima a été localisé après 10 évaluations de la fonction objectif avec une entrée de -5,0, atteignant une valeur de fonction objectif de 0,0.

Optimal Input x: -5.000000
Optimal Output f(x): 0.000000
Total Evaluations n: 10

Un tracé de la fonction est à nouveau créé et cette fois, les optima sont marqués par un carré rouge.

Optimisation de fonctions univariées non convexes

Une fonction convexe est une fonction qui ne ressemble pas à un bassin, ce qui signifie qu’elle peut avoir plus d’une colline ou d’une vallée.

Cela peut rendre plus difficile la localisation des optima globaux, car les multiples collines et vallées peuvent bloquer la recherche et signaler à la place un optima faux ou local.

Nous pouvons définir une fonction univariée non convexe comme suit.

# objective function
def objective(x):
	return (x - 2.0) * x * (x + 2.0)**2.0

Nous pouvons échantillonner cette fonction et créer un tracé linéaire des valeurs d'entrée par rapport aux valeurs objectives.

L’exemple complet est répertorié ci-dessous.

# plot a non-convex univariate function
from numpy import arange
from matplotlib import pyplot

# objective function
def objective(x):
	return (x - 2.0) * x * (x + 2.0)**2.0

# define range
r_min, r_max = -3.0, 2.5
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]
# plot inputs vs target
pyplot.plot(inputs, targets, '--')
pyplot.show()

L'exécution de l'exemple évalue les valeurs d'entrée dans notre plage spécifiée à l'aide de notre fonction cible et crée un tracé des entrées de fonction vers les sorties de fonction.

Nous pouvons voir une fonction avec un faux optimal autour de -2,0 et un optimal global autour de 1,2.

Ensuite, nous pouvons utiliser l’algorithme d’optimisation pour trouver les optima.

Comme auparavant, nous pouvons appeler la fonction minimise_scalar() pour optimiser la fonction, puis résumer le résultat et tracer les optima sur un tracé linéaire.

L’exemple complet d’optimisation d’une fonction univariée non convexe sans contrainte est répertorié ci-dessous.

# optimize non-convex objective function
from numpy import arange
from scipy.optimize import minimize_scalar
from matplotlib import pyplot

# objective function
def objective(x):
	return (x - 2.0) * x * (x + 2.0)**2.0

# minimize the function
result = minimize_scalar(objective, method='brent')
# summarize the result
opt_x, opt_y = result['x'], result['fun']
print('Optimal Input x: %.6f' % opt_x)
print('Optimal Output f(x): %.6f' % opt_y)
print('Total Evaluations n: %d' % result['nfev'])
# define the range
r_min, r_max = -3.0, 2.5
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]
# plot inputs vs target
pyplot.plot(inputs, targets, '--')
# plot the optima
pyplot.plot([opt_x], [opt_y], 's', color='r')
# show the plot
pyplot.show()

L'exécution de l'exemple résout d'abord le problème d'optimisation et rapporte le résultat.

Dans ce cas, nous pouvons voir que l'optima a été localisé après 15 évaluations de la fonction objectif avec une entrée d'environ 1,28, atteignant une valeur de fonction objectif d'environ -9,91.

Optimal Input x: 1.280776
Optimal Output f(x): -9.914950
Total Evaluations n: 15

Un tracé de la fonction est à nouveau créé, et cette fois, les optima sont marqués par un carré rouge.

Nous pouvons voir que l’optimisation n’a pas été trompée par les faux optima et a réussi à localiser les optima globaux.

Lectures complémentaires

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

Livres

Algorithmes d'optimisation, 2019.

Apis

Optimisation (scipy.optimize).
Optimisation et recherche de racine (scipy.optimize)
API scipy.optimize.minimize_scalar.

Articles

Méthode de Brent, Wikipédia.
Méthode sécante, Wikipédia.

Résumé

Dans ce didacticiel, vous avez découvert comment effectuer une optimisation de fonctions univariées en Python.

Concrètement, vous avez appris :

L'optimisation de fonction univariée implique de trouver une entrée optimale pour une fonction objectif qui prend un seul argument continu.
Comment effectuer une optimisation de fonction univariée pour une fonction convexe sans contrainte.
Comment effectuer une optimisation de fonction univariée pour une fonction non convexe sans contrainte.

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