Optimisation lorsque la fonction de coût est lente à évaluer

59

La descente en gradient et de nombreuses autres méthodes sont utiles pour trouver des minima locaux dans les fonctions de coût. Ils peuvent être efficaces lorsque la fonction de coût peut être évaluée rapidement à chaque point, que ce soit numériquement ou analytiquement.

J'ai ce qui me semble être une situation inhabituelle. Chaque évaluation de ma fonction de coût coûte cher. J'essaie de trouver un ensemble de paramètres qui minimisent une surface 3D par rapport à des surfaces de vérité au sol. Chaque fois que je modifie un paramètre, je dois exécuter l'algorithme sur l'ensemble de la cohorte de l'échantillon afin de mesurer son effet. Afin de calculer un gradient, je dois modifier les 15 paramètres indépendamment, ce qui signifie que je dois régénérer toutes les surfaces et les comparer à la cohorte de l'échantillon trop de fois par gradient, et nettement trop au cours de l'optimisation.

J'ai développé une méthode pour contourner ce problème et je l'évalue actuellement, mais je suis surpris de ne pas avoir trouvé grand chose dans la littérature concernant les évaluations coûteuses de la fonction de coût. Cela me fait me demander si je ne complique pas le problème et s'il existe déjà une meilleure solution.

Mes questions sont donc essentiellement les suivantes: quelqu'un connaît-il des méthodes d'optimisation des fonctions de coût, convexes ou non, lorsque l'évaluation est lente? Ou, est-ce que je fais quelque chose de stupide en premier lieu en réexécutant l'algorithme et en le comparant si souvent avec la cohorte de l'échantillon?

Jared Becksfort
la source
5
Avez-vous entendu parler de la descente de gradient stochastique? Pour les réseaux de neurones profonds appliqués à de grands ensembles d’entraînement, vous avez un problème similaire (mais vous pouvez analyser le gradient d’Eval de manière analytique) et la solution standard consiste à effectuer une descente de gradient uniquement sur un seul échantillon (stochastique) par rapport à l’ensemble de la cohorte (batch)
seanv507
3
Je ne connais que vaguement la région, ce qui en fait un commentaire plutôt qu'une réponse. Mais ce que vous discutez ressemble beaucoup au sujet de la quantification de l'incertitude, souvent rencontré par les ingénieurs, où une seule évaluation de la fonction cible effectuée prend des semaines à être évaluée (du moins dans les problèmes rencontrés par mes collègues ingénieurs). Ma compréhension très limitée de la façon dont cela est géré consiste à faire une approximation de substitution beaucoup plus facile à évaluer sur la base d'évaluations antérieures et de modèles d'ingénierie plus simples, puis à utiliser ces modèles de substitution pour choisir l'évaluation suivante ...
Cliff AB
2
... de la fonction cible la plus chère. Je déteste le dire, mais je ne sais plus ce sujet pour le moment; On ne m'en a parlé que brièvement lors de discussions sur des sujets de recherche avec lesdits ingénieurs. Fait intéressant, cela semble être un domaine de recherche très difficile: je pense que de bons modèles exigent à la fois une bonne compréhension de la physique et des statistiques.
Cliff AB
1
@ seanv507 Oui, merci, mais je l'ai évité pour une raison similaire. Il faut environ 30 secondes à une minute pour analyser un échantillon. Si j’ai 15 paramètres, j’observe près de 8 minutes par calcul de gradient, même si je n’utilise qu’un seul échantillon. Si l'espace est grand, cela peut prendre beaucoup de temps. S'il vous plaît, corrigez-moi si vous aviez d'autres idées en tête.
Jared Becksfort
5
"Ce qui me semble être une situation inhabituelle. Chaque évaluation de ma fonction de coût coûte cher.". Ce n'est pas du tout une situation inhabituelle, en général. Il apparaît partout, par exemple, chaque fois que votre fonction de coût vient de l'exécution d'une simulation (par exemple, dans cet article: white.ucc.asn.au/publications/White2015PsoTransistorSizing.pdf, nous simulons un circuit dans SPICE en prenant 10 secondes ). Plus franchement, en science expérimentale, les évaluations peuvent prendre des siècles. Le projet Masters de l’un de mes amis est en train d’optimiser 5 paramètres pour trouver le meilleur moyen d’insérer de l’ADN. Chaque évaluation prend 24 heures.
Lyndon White

Réponses:

60

TL; DR

Je recommande d'utiliser LIPO. C’est tout à fait correct et bien meilleur que la recherche aléatoire pure (PRS). Il est également extrêmement simple à mettre en œuvre et n’a pas d’hyperparamètres. Je n'ai pas effectué d'analyse comparant LIPO à BO, mais je m'attends à ce que la simplicité et l'efficacité de LIPO impliquent qu'il sera plus performant que BO.

(Voir aussi: Quels sont les inconvénients de l'optimisation bayésienne à hyper-paramètres? )

Optimisation Bayésienne

Les méthodes de type optimisation bayésienne construisent des modèles de substitution de processus gaussiens pour explorer l'espace des paramètres. L'idée principale est que les nuplets de paramètres les plus proches auront des valeurs de fonction similaires, de sorte que l'hypothèse d'une structure de co-variance entre les points permet à l'algorithme de faire des suppositions éclairées sur le meilleur nuplet de paramètre qui mérite le plus d'être essayé. Cette stratégie aide à réduire le nombre d’évaluations de fonctions; En fait, les méthodes BO ont pour objectif de limiter le plus possible le nombre d'évaluations de fonctions tout en "utilisant le buffle entier" pour deviner avec précision le point à tester par la suite. Différents facteurs de mérite (amélioration attendue, amélioration attendue du quantile, probabilité d'amélioration, etc.) sont utilisés pour comparer les points à visiter ensuite.

Comparez cela à quelque chose comme une recherche sur grille, qui n'utilisera jamais les informations de ses évaluations de fonctions précédentes pour indiquer où aller ensuite.

Incidemment, il s’agit également d’une puissante technique d’optimisation globale qui, en tant que telle, ne fait aucune hypothèse sur la convexité de la surface. De plus, si la fonction est stochastique (par exemple, les évaluations ont un bruit aléatoire inhérent), cela peut être directement pris en compte dans le modèle GP.

D'autre part, vous devrez adapter au moins un généraliste à chaque itération (ou plusieurs, en choisissant le "meilleur", ou en calculant la moyenne des alternatives, ou des méthodes entièrement bayésiennes). Ensuite, le modèle est utilisé pour effectuer (probablement des milliers) de prédictions, généralement sous la forme d'une optimisation locale à plusieurs étapes, en observant qu'il est beaucoup moins coûteux d'évaluer la fonction de prédiction GP que la fonction sous optimisation. Mais même avec cette surcharge de calcul, il est généralement possible d'optimiser même les fonctions non-convexes avec un nombre relativement petit d'appels de fonction.

Jones et al. , "Optimisation globale efficace des fonctions coûteuses de la boîte noire", est un article largement cité sur le sujet . Mais il y a beaucoup de variations sur cette idée.

Recherche aléatoire

Même lorsque la fonction de coût est coûteuse à évaluer, la recherche aléatoire peut toujours être utile. La recherche aléatoire est extrêmement simple à mettre en œuvre. Pour un chercheur, le seul choix est de définir la probabilité p que vous souhaitez que vos résultats se situent dans un quantile q ; le reste procède automatiquement en utilisant les résultats de la probabilité de base.

Supposons que votre quantile est q=0.95 et que vous voulez une probabilité p=0.95 que les résultats du modèle se situent dans le top 100×(1-q)=5 % de tous les n-uplets de l'hyperparamètre. La probabilité que tous lesn tuples tentésnesoientpasdans cette fenêtre estqn=0.95n (car ils sont choisis indépendamment de manière aléatoire dans la même distribution), de sorte que la probabilité qu’aumoins untuple se trouve dans cette région est comprise entre1-0.95n. En réunissant tout, nous avons

1-qnpnbûche(1-p)bûche(q)

n59

n=60n=60

Puisque vous avez une caractérisation probabiliste de la qualité des résultats, ce résultat peut être un outil convaincant pour convaincre votre patron que la réalisation d'expériences supplémentaires générera des rendements marginaux décroissants.

LIPO et ses variantes

C'est une arrivée passionnante qui, si elle n'est pas nouvelle , l'est certainement pour moi. Elle procède en alternant entre le placement de bornes informées sur la fonction, l'échantillonnage à partir de la meilleure liaison et l'utilisation d'approximations quadratiques. Je travaille toujours sur tous les détails, mais je pense que c'est très prometteur. Ceci est une écriture-up blog agréable , et le papier est Cédric Nicolas Malherbe et Vayatis « Optimisation globale des fonctions Lipschitz . »

Rétablir Monica
la source
1
Cela semble être une variante moderne des méthodes de surface de réponse!
kjetil b halvorsen
1
En fait, la recherche aléatoire peut fonctionner remarquablement bien: argmin.net/2016/06/20/hypertuning
Tim
1
@ Tim Oui, votre point est bien pris. Je ne voulais pas "décider" de la question de savoir laquelle est la meilleure dans ce billet, car il y a essentiellement des permutations sans fin sur BO, chacun prétendant être "le meilleur" optimiseur de boîte noire - rendant impossible la définition définitive. Je conviens que la recherche aléatoire peut très bien fonctionner, mais je recommanderais en réalité le LIPO au-dessus de PRS. Le LIPO est manifestement correct et surpasse fortement le PRS (en moyenne) dans toutes mes expériences. Le coût d’estimation de LIPO est également minimal: si vous pouvez minimiser une QP, vous pouvez l’utiliser, et LIPO ne contient aucun hyperparamètre (contrairement à BO).
Rétablir Monica
Je suis content d'avoir vérifié cette question à nouveau. LIPO semble génial.
Jared Becksfort
LIPO est génial. Quand j'aurai un moment, j'élargirai ma réponse pour donner une meilleure comptabilité du LIPO.
Rétablir Monica le
40

F(X)X

Je dirais que l’étalon-or actuel pour l’évaluation de la fonction (très) coûteuse de la boîte noire est l’optimisation bayésienne (globale ). Sycorax a déjà décrit certaines fonctionnalités de BO. Je ne fais donc qu'ajouter quelques informations qui pourraient être utiles.

Pour commencer, vous voudrez peut-être lire ce document d’aperçu 1 . Il en existe aussi un plus récent [2].

L’optimisation bayésienne a connu une croissance constante au cours des dernières années, avec une série d’ateliers dédiés (par exemple, BayesOpt , et des vidéos de l’atelier de Sheffield sur BO), car elle a des applications très pratiques en apprentissage automatique, telles que pour optimiser les hyper-paramètres des algorithmes ML - voir par exemple cet article [3] et la boîte à outils associée, SpearMint . Il existe de nombreux autres packages dans différentes langues qui implémentent différents types d'algorithmes d'optimisation bayésienne.

Comme je l'ai mentionné, l'exigence sous-jacente est que l'évaluation de chaque fonction soit très coûteuse, de sorte que les calculs liés aux BO ajoutent un surcoût négligeable. Pour donner une idée approximative, BO peut être vraiment utile si votre fonction évalue dans un délai de l'ordre de quelques minutes ou plus. Vous pouvez également l'appliquer pour des calculs plus rapides (par exemple, des dizaines de secondes), mais en fonction de l'algorithme que vous utilisez, vous devrez peut-être adopter diverses approximations. Si votre fonction évalue en secondes , je pense que vous repoussez les limites de la recherche actuelle et que d'autres méthodes pourraient devenir plus utiles. De plus, je dois dire que BO est rarement vraiment une boîte noire et que vous devez souvent modifier les algorithmes, parfois énormément , pour le faire fonctionner à plein potentiel avec un problème spécifique du monde réel.

A part cela, pour un examen des méthodes d'optimisation générales sans dérivées, vous pouvez consulter cet article [4] et rechercher des algorithmes possédant de bonnes propriétés de convergence rapide. Par exemple, la recherche de coordonnées à plusieurs niveaux (MCS) converge généralement très rapidement vers un voisinage d'un minimum (pas toujours le minimum global, bien sûr). MCS est conçu pour une optimisation globale, mais vous pouvez le rendre local en définissant des contraintes liées appropriées.

Enfin, vous vous intéressez à BO pour les fonctions cibles à la fois coûteuses et bruyantes , voir ma réponse à cette question .


Références:

1 Brochu et al., "Tutoriel sur l'optimisation bayésienne de coûteuses fonctions, avec application à la modélisation utilisateur active et à l'apprentissage par renforcement hiérarchique" (2010).

[2] Shahriari et al., "Prendre l'humain de la boucle: un examen de l'optimisation bayésienne" (2015).

[3] Snoek et al., «Optimisation bayésienne pratique des algorithmes d'apprentissage automatique», NIPS (2012).

[4] Rios et Sahinidis, «Optimisation sans dérivés: examen des algorithmes et comparaison des implémentations logicielles», Journal of Global Optimization (2013).

lacerbi
la source
4
+1 C'est une excellente réponse. En particulier, ces papiers sont un excellent ajout à ce fil; en effet, je ne savais pas que la méthode générale que j'ai décrite s'appelle l'optimisation bayésienne. Mais je crains que les liens ne se détériorent avec le temps. Souhaitez-vous ajouter des informations de citation plus complètes afin que les futurs utilisateurs puissent accéder à ces documents?
Rétablir Monica le
Les documents d'optimisation bayésienne sont très utiles. Merci d'avoir répondu.
Jared Becksfort
1
@ user777: Bon point. Ajout d’une liste de références explicites à la fin qui devrait suffire à récupérer les papiers.
lacerbi
6

Je ne connais pas moi-même les algorithmes, mais je pense que le type d'algorithme que vous recherchez est l'optimisation sans dérivée , qui est utilisée lorsque l'objectif est coûteux ou bruyant .

Par exemple, jetez un coup d'œil à cet article (Björkman, M. & Holmström, K. "Optimisation globale de fonctions coûteuses non convexes à l'aide de fonctions à base radiale". Optimisation et ingénierie (2000) 1: 373. doi: 10.1023 / A: 1011584207202) dont le résumé semble indiquer que c’est exactement ce que vous voulez:

Le document examine l’optimisation globale de fonctions objectives coûteuses, c’est-à-dire le problème de la recherche du minimum global lorsque plusieurs minima locaux sont présents et que le calcul de chaque valeur de fonction prend un temps considérable. Ces problèmes se posent souvent dans les applications industrielles et financières, où la valeur d'une fonction peut résulter d'une simulation ou d'une optimisation informatique fastidieuse. Les dérivés sont le plus souvent difficiles à obtenir et les algorithmes présentés n’utilisent pas ces informations.

Mehrdad
la source
2
Veuillez inclure les informations de citation complètes pour les documents liés et autres ressources. Nous voulons créer un référentiel durable d'informations et les liens ont tendance à se détériorer avec le temps.
Réintégrer Monica
Björkman, M. & Holmström, K. "Optimisation globale de fonctions coûteuses non complexes à l'aide de fonctions à base radiale". Optimisation et ingénierie (2000) 1: 373. doi: 10.1023 / A: 1011584207202
jkdev Le
4

Tu n'es pas seul.

Les systèmes coûteux à évaluer sont très courants en ingénierie, tels que les modèles à méthode des éléments finis (MEF) et les modèles de calcul numérique par la dynamique des fluides (CFD). L’optimisation de ces modèles informatiques coûteux est très nécessaire et représente un défi, car les algorithmes évolutifs nécessitent souvent des dizaines de milliers d’évaluations du problème, ce qui n’est pas une option pour des problèmes coûteux à évaluer. Heureusement, de nombreuses méthodes (algorithmes) sont disponibles pour résoudre ce problème. Autant que je sache, la plupart d'entre eux sont basés sur des modèles de substitution (métamodèles). Certains sont énumérés ci-dessous.

  • Optimisation globale efficace (EGO) [1]. L'algorithme EGO a été mentionné ci-dessus et pourrait être l'algorithme d'optimisation à base de substituts le plus connu. Il est basé sur le modèle de Kriging et sur un critère de remplissage appelé fonction d'amélioration attendue (IE). Les packages R, y compris l'algorithme EGO, sont DiceOptim et DiceKriging.
  • Méthode d’échantillonnage en fonction du mode (MPS) [2]. L'algorithme MPS est construit sur le modèle RBF et une stratégie d'échantillonnage adaptatif est utilisée pour collecter les points candidats. Le code MATLAB est publié par les auteurs à l' adresse http://www.sfu.ca/~gwa5/software.html . L'algorithme MPS peut nécessiter plus d'évaluations pour obtenir l'optimum, mais peut traiter des problèmes plus complexes que l'algorithme EGO de mon expérience personnelle.
  • Modèles de substitution d'ensemble de Juliane Müller [3]. Elle a utilisé plusieurs mères porteuses pour améliorer la capacité de recherche. La boîte à outils MATLAB MATSuMoTo est disponible à l' adresse https://github.com/Piiloblondie/MATSuMoTo .

En résumé, ces algorithmes d'optimisation basés sur des substituts tentent de trouver l'optimum global du problème en utilisant le moins d'évaluations possible. Ceci est réalisé en utilisant pleinement les informations fournies par le substitut (substituts). Des commentaires sur l'optimisation de problèmes de calcul coûteux se trouvent dans [4-6].


Référence:

  1. DR Jones, M. Schonlau et WJ Welch, «Optimisation globale efficace de fonctions de boîte noire coûteuses», Journal of Global Optimization, vol. 13, pages 455 à 492, 1998.
  2. L. Wang, S. Shan et GG Wang, "Méthode d'échantillonnage à la poursuite de modes pour une optimisation globale de fonctions de boîte noire coûteuses", Engineering Optimization, vol. 36, pages 419 à 438, 2004.
  3. J. Müller, «Algorithmes de modèle de substitution pour des problèmes d'optimisation globale coûteux en Black-Box», Université de technologie de Tampere, 2012.
  4. GG Wang et S. Shan, "Examen des techniques de métamodélisation en appui à l'optimisation de la conception technique", Journal of Mechanical Design, vol. 129, pages 370-380, 2007.
  5. AI Forrester et AJ Keane, «Progrès récents en optimisation basée sur les substituts», Progress in Aerospace Sciences, vol. 45, pages 50 à 79, 2009.
  6. FAC Viana, TW Simpson, V. Balabanov et V. Toropov, «Le métamodelage dans l'optimisation de la conception multidisciplinaire: jusqu'où sommes-nous vraiment venus?», AIAA Journal, vol. 52, pages 670-690, 2014/04/01 2014.
Zhan Dawei
la source
3

Les deux stratégies simples que j'ai utilisées avec succès dans le passé sont les suivantes:

  1. Si possible, essayez de trouver une fonction de substitution plus simple se rapprochant de l'évaluation de votre fonction de coût - un modèle analytique typique remplaçant une simulation. Optimiser cette fonction plus simple. Puis validez et réglez la solution résultante avec votre fonction de coût exacte.
  2. Si possible, essayez de trouver un moyen d’évaluer une fonction exacte «coût-delta» - exacte plutôt que comme une approximation de l’utilisation du gradient. En d’autres termes, à partir d’un point initial à 15 dimensions pour lequel vous faites évaluer le coût total, trouvez un moyen de calculer l’évolution du coût en modifiant légèrement l’un des composants (ou plusieurs) des 15 composants de votre point actuel. Vous devrez exploiter les propriétés de localisation d'une petite perturbation, le cas échéant, et vous devrez probablement définir, mettre en cache et mettre à jour une variable d' état interne en cours de route.

Ces stratégies sont très spécifiques à chaque cas. Je ne sais pas si elles peuvent ou non être applicables dans votre cas. Désolé si elles ne le sont pas. Les deux peuvent être applicables (comme c'était le cas dans mes cas d'utilisation): appliquez la stratégie du "coût delta" à un modèle analytique plus simple - les performances peuvent être améliorées de plusieurs ordres de grandeur.

Une autre stratégie consisterait à utiliser une méthode de second ordre qui tend généralement à réduire le nombre d'itérations (mais chaque itération est plus complexe) - par exemple, l' algorithme de Levenberg – Marquardt . Mais étant donné que vous ne semblez pas avoir le moyen d'évaluer directement et efficacement le gradient, ce n'est probablement pas une option viable dans ce cas.

Patrick
la source
3

Comme d'autres personnes l'ont mentionné, un modèle de substitution (également appelé surface de réponse) constitue une approche puissante. À mon avis, une chose cruciale que les gens oublient est que vous pouvez effectuer plusieurs évaluations de fonctions en parallèle , si vous utilisez des processeurs multicœurs.

Je suggérerais de regarder ce code , il utilise un modèle de réponse simple, mais évolue sur les processeurs multicœurs, ce qui donne une accélération égale à la quantité de cœurs utilisés. Une mathématique derrière la méthode est décrite dans cet article .

Paul
la source
Je suppose que vous êtes le premier auteur sur le papier - vous devriez probablement le mentionner si c'est le cas. Le document manque de comparaison avec les méthodes de pointe telles que l'optimisation bayésienne ou d'autres méthodes de substitution (en fait, il ne fournit aucune référence du tout). Pouvez-vous dire quelque chose de plus?
Lacerbi
Je ne dis pas que ce modèle utilisé est meilleur. Je dis simplement que les gens sont trop préoccupés par la qualité du modèle et oublient parfois le parallélisme, ce qui peut être un problème lorsque de nombreux noyaux sont impliqués.
Paul
Veuillez inclure les informations de citation complètes pour les documents liés et autres ressources. Nous voulons créer un référentiel durable d'informations et les liens ont tendance à se détériorer avec le temps.
Réintégrer Monica
2
Je ne sais pas exactement dans quelle mesure la terminologie varie d'une communauté à l'autre, mais j'utilise couramment ici la surface de réponse comme synonyme de "modèle de substitution polynomiale" (typiquement un quadratique). J'ai donc tendance à penser que la modélisation de substitution est un surensemble de la modélisation de surface de réponse. (Cela peut toutefois être incorrect.)
GeoMatt22
0

De nombreuses astuces utilisées dans la descente de gradient stochastique peuvent également être appliquées à l'évaluation de la fonction objective. L'idée générale est d'essayer d' approximer la fonction objectif à l'aide d'un sous-ensemble de données .

Mes réponses dans ces deux articles expliquent pourquoi la descente de gradient stochastique fonctionne: son intuition consiste à approximer le gradient à l'aide d'un sous-ensemble de données.

Comment une descente de gradient stochastique pourrait-elle gagner du temps par rapport à une descente de gradient standard?

Comment exécuter une régression linéaire de manière parallèle / distribuée pour le paramétrage Big Data?

Le même truc s'applique à la fonction objectif.

UNEX-b2UNEUNEb

Haitao Du
la source