Introduction à l'optimisation bayésienne

J'ai récemment entendu parler de l'optimisation bayésienne, alors je l'ai résumé. Je ne suis pas un spécialiste, donc j'ai peut-être écrit quelque chose de mal, mais si je le trouve, je vous serais reconnaissant si vous pouviez le signaler.

Motivation pour l'optimisation bayésienne

Il y a beaucoup de choses dans le monde qui sont difficiles à expérimenter. Je veux donc concevoir l'expérience de manière systématique. L'optimisation bayésienne consiste à concevoir la prochaine expérience "à la Bayes" basée à chaque fois sur les résultats des expériences précédentes. Par exemple, les champs réellement utilisés

Publicité (comment tester A / B)
Biologie (lorsque vous voulez déterminer un ADN qui a l'air bien et expérimenter sur celui-ci?)
Physique ou chimie (conception des matériaux)
Hyper recherche de paramètres en machine learning (Deep Learning, etc.)
Apprentissage amélioré

Il semble y avoir quelque chose comme. Dans l'exemple le plus basique de recherche hyper-paramètre de l'apprentissage automatique, je pense que cela se fait souvent manuellement, ou si cela se fait automatiquement, cela se fait par recherche de grille ou aléatoire. Mais vous pouvez faire mieux avec l'optimisation bayésienne. Dans l'optimisation bayésienne, une fonction alternative (fonction d'acquisition) qui prédit le résultat de l'expérience suivante est créée sur la base des données jusqu'à présent, le point pour maximiser la fonction est trouvé et l'expérience suivante y est effectuée.

Description intuitive de l'optimisation bayésienne

Je pense que c'est une explication qui revient souvent dans l'apprentissage par renforcement, mais on oscille entre l'exploration et l'utilisation. L'utilisation consiste à utiliser quelque chose qui est déjà connu pour être bon dans une certaine mesure, et l'exploration consiste à défier quelque chose d'inconnu et à acquérir une expérience complètement différente. L'optimisation bayésienne peut être facilement décrite comme une méthode de sélection de la prochaine action à sélectionner en considérant à la fois les concepts d'utilisation et d'exploration dans le cadre de l'optimisation. En d'autres termes, utilisez la fonction d'acquisition qui prend en compte l'utilisation et l'exploration. On peut également dire que les humains effectuent inconsciemment une optimisation bayésienne dans des situations telles que l'achat de quelque chose ou essayer quelque chose pour la première fois.

Description spécifique de l'optimisation bayésienne

Le gif ci-dessus est une explication approximative de l'optimisation bayésienne. Tout d'abord, la ligne jaune sur la gauche est la vraie fonction. La tâche est de prendre progressivement des points des contraintes ((-20,20) cette fois) pour trouver le point qui maximise cette fonction. Cette fois, l'évaluation des points (expérience) est terminée en un instant, mais veuillez noter qu'il faut du temps pour l'évaluer. La ligne rouge montre la valeur moyenne des valeurs prédites prédites à partir des points de données jusqu'à présent. La zone verte représente l'intervalle de confiance ($ moyenne \ pm distribution $). Cette moyenne et cette variance sont calculées en utilisant le processus gaussien basé sur les points de données obtenus.

Utilisez l'optimisation bayésienne lors de la sélection des points en raison de la question de savoir comment marquer. Disons que vous choisissez le premier point au hasard. Parmi les points suivants, sélectionnez le point avec la fonction d'acquisition la plus élevée. Cette fonction d'acquisition est représentée par la ligne bleue à droite. En d'autres termes, les points forts de la fonction bleue sont sûrement prometteurs, alors faisons-le ensuite. Comme mentionné précédemment, la création d'une fonction d'acquisition qui prend en compte la recherche et l'utilisation peut être considérée comme la clé de l'optimisation bayésienne.

Une description un peu plus détaillée de l'optimisation bayésienne

Tout d'abord, je vais expliquer GP, puis je présenterai quelques types de fonctions d'acquisition. Après cela, j'ai résumé d'autres choses importantes dans la littérature que j'ai lue.

Introduction du processus gaussien (GP)

Tout d'abord, GP est un processus stochastique. Un processus stochastique est un ensemble de variables stochastiques {$ X_ {t} } ( t \ in T $). (Dans le traitement du signal, $ T $ est le temps. Dans le contexte de la GP en apprentissage automatique, c'est la zone d'entrée.)

Par exemple, si $ T $ est discret, il y a le processus de Markov discret, et s'il est continu, il y a le processus de Wiener. Il est assez important que le processus stochastique puisse être considéré comme une fonction du temps ou simplement comme une variable stochastique découpée à un certain moment en changeant ce qui est fixe. Le premier est souvent appelé le chemin de l'échantillon. De plus, l'existence d'un processus stochastique continu est garantie lorsque la «cohérence» est satisfaite. [^ 1] Dans le processus gaussien, la distribution simultanée de y pour tout ensemble de x suit une distribution gaussienne. A ce moment, la "cohérence" satisfaisante garantit l'existence d'un tel processus stochastique continu. La distribution gaussienne est déterminée uniquement une fois que la variance et la moyenne sont déterminées. Le processus stochastique, où la moyenne est 0 et la variance est exprimée en tant que noyau, est le processus gaussien dans le contexte de l'apprentissage automatique.

[^ 1]: C'est une affirmation facile à comprendre que la cohérence doit être respectée lorsqu'elle est marginalisée, mais la preuve est assez compliquée. Prouvé par Kolmogorov. Discuter exactement des processus stochastiques sur un temps continu peut être une tâche ardue.

Description de la régression du noyau

L'interprétation la plus simple de la régression du noyau est de remplacer la régression de crête par le noyau, mais dans le contexte de l'optimisation bayésienne, l'interprétation en tant que processus gaussien est importante, donc j'écrirai cela. Tout d'abord, supposons que vous ayez $ x $, $ y $, $ t $. x est l'entrée et y est la sortie. t est y avec bruit (la dispersion est $ \ beta $) et représente la valeur réelle observée. Tout d'abord, soit le prieur de y $ N (0, K) $ (K est la matrice de gramme par le noyau). Ensuite, la distribution postérieure (distribution prédite) de $ t_ {N + 1} $ après l'observation du point N est déterminée pour $ x_ {N + 1} $. Cette distribution postérieure est gaussienne et la moyenne et la variance sont les suivantes.

$ \ mu_ {N + 1} = k ^ {T} (K + \ beta I) ^ {-1} t_ {1: N} $ ($ k (x_ {n}, x_ {N + 1}) $ Le côte à côte est $ k $)

$ \sigma_{N+1}= k(x_{N+1},x_{N+1})-k^{T}(K+\beta I)^{-1}k$

Conception de la fonction d'acquisition

Définissez la fonction d'acquisition ($ a (x) $) pour sélectionner le $ x_ {N + 1} $ ci-dessus. Comme mentionné ci-dessus, créez une fonction qui capture avec succès le compromis entre l'utilisation et la recherche. Du point de vue de "l'utilisation", le point avec une moyenne élevée devrait être choisi, et du point de vue de la "recherche", le point avec une dispersion élevée devrait être choisi. Dorénavant, $ f_ {+} $ représentera la sortie maximale aux points obtenus jusqu'au Nième point. Pour le moment, le code est donné ici. https://github.com/Ma-sa-ue/practice/blob/master/machine%20learning(python)/bayeisan_optimization.ipynb

Probability of Improvement(PI)

Z = \frac {\mu(x)-f^{+}- \xi}{\sigma(x)},a_{PI}(x)= \Phi (Z)

$ \ Phi $ est un cdf normalement distribué. Vous pouvez voir sur le gif que ce n'est pas si bon. $ \ Xi $ est fourni pour éviter qu'il ne devienne trop gourmand, mais il a toujours tendance à être plus utilisé. Expected Improvement(EI)

a_{EI}(x)=(\mu (x)-f_{+}-\xi)\Phi (Z)+\sigma (x)\phi (Z)

$ \ phi $ est un pdf normalement distribué. C'est une bien meilleure méthode que PI. En prenant la valeur attendue de l'amélioration ($ f_ {N + 1} (x) -f ^ {+} $) donne ce qui précède. Il semble qu'environ 0,01 soit recommandé pour $ \ xi $.

GP Upper (lower) Confidence Band

a_{UCB}(x)=\mu (x)+k_{N} \sigma (x)

Il s'agit également d'une méthode simple (Upprt Confidence Bound) dans laquelle le coefficient appliqué à l'origine à la variance est une constante. Cependant, cela ne fonctionne pas très bien, donc GP-UCB ajuste le coefficient pour chaque mise à jour. Vous pouvez voir qu'il montre la même tendance que l'IE.

Thomson sampling

Prenez un exemple de chemin et utilisez-le comme fonction d'acquisition.

Information-theoretic approaches

Utilisez des fonctions basées sur la théorie de l'information.

Autres

Je pense que le concept de base est probablement la fin de ce qui a été écrit jusqu'à présent, mais diverses études ont été faites sur la base de ces choses. Pour le moment, pendant que je saisissais les grandes lignes, j'ai essayé de résumer ce qui semble important bien que cela ne soit pas écrit ci-dessus.

Qu'en est-il de l'exploration en haute dimension?

Un procédé a été proposé dans lequel l'hypothèse de diversité est valable pour l'entrée de la recherche, c'est-à-dire que l'optimisation est effectuée tout en abaissant la dimension sur la base de l'hypothèse qu'il s'agit d'une sous-variable de faible dimension. Cela semble être une très bonne technique. http://arxiv.org/pdf/1301.1942.pdf

Efficacité de la déformation d'entrée

Si vous mettez un noyau normal, cela représentera un processus stochastique stable. Cependant, les données du monde réel sont souvent non stationnaires. L'idée est d'effectuer une optimisation bayésienne en déformant l'entrée avec une fonction entièrement monomorphe pour représenter un tel processus stochastique non stationnaire. http://jmlr.org/proceedings/papers/v32/snoek14.pdf

Quel noyau choisissez-vous en premier lieu?

La manière de choisir un noyau est très importante. Dans l'expérience, j'en ai utilisé un simple avec un exposant quadratique, mais il semble qu'il existe différents noyaux pour l'optimisation bayésienne.

Que faire des hyperparamètres du noyau?

Comment définir les hyperparamètres du noyau est un problème ennuyeux. Par exemple, la méthode utilisée dans la célèbre bibliothèque de la menthe verte semble intégrer et éliminer approximativement les hyperparamètres. https://papers.nips.cc/paper/4522-practical-bayesian-optimization-of-machine-learning-algorithms.pdf

N'est-ce pas vraiment simple?

L'optimisation bayésienne elle-même existe depuis un certain temps. Il semble que l'optimisation bayésienne soit à nouveau relancée pour la recherche d'hyperparamètres avec le développement de l'apprentissage automatique. J'ai peut-être écrit quelque chose au début de moi-même pendant longtemps, mais au niveau de la recherche récente, j'ai fait divers développements en termes de théorie et d'application.

Comment maximiser la fonction d'acquisition?

Il est à noter que l'optimisation bayésienne est effectuée sur l'hypothèse que l'observation de la fonction objectif est gênante. Vous pouvez obtenir $ y $ tout de suite pour la vidéo, mais bien sûr, vous ne pouvez pas l'obtenir tout de suite. En revanche, l'évaluation de la fonction d'acquisition est aisée. Cependant, il n'y a aucune garantie qu'il soit convexe ou différentiable, nous utilisons donc une méthode primitive telle que la division de l'intervalle pour trouver la valeur maximale. (peut être)

Le coût d'observation de la fonction objectif n'est-il pas différent pour chaque entrée?

On suppose que le coût de l'observation sera raisonnable, mais il n'en demeure pas moins que le coût diffère en fonction de l'intrant. Il semble y avoir un modèle qui prend cela en considération.

Références (Honnêtement, il vaut mieux lire cet article que de lire cet article)

Ceci est un tutoriel créé par des chercheurs qui font des recherches énergiques sur la balance des paiements à Harvard (anciennement toronto). La personne qui a fabriqué la menthe verte. Un bref aperçu et une application sont fournis. https://papers.nips.cc/paper/4522-practical-bayesian-optimization-of-machine-learning-algorithms.pdf
La même diapositive que ci-dessus. Ce que j'ai écrit est inclus dans cette diapositive. http://www.iro.umontreal.ca/~bengioy/cifar/NCAP2014-summerschool/slides/Ryan_adams_140814_bayesopt_ncap.pdf
Ceci est une diapositive de mlss du chercheur d'Oxford (maintenant Deepmind?). http://www.mlss2014.com/files/defreitas_slides1.pdf
Ceci est la conférence de la personne précédente. Les diapositives utilisées sont presque les mêmes que ci-dessus. C'est très facile à comprendre. Https://www.youtube.com/watch?v=vz3D36VXefI
Ceci est le tuorial fait par la personne précédente. Je pense que c'était la chose la plus utile que j'ai lue. Http://arxiv.org/pdf/1012.2599.pdf
Il existe une fonction d'acquisition légèrement inhabituelle. Http://gpss.cc/gpss15/talks/gpgo-gpss2015.pdf
Ceci est la page Bayesopt. C'est un logiciel qui semble assez célèbre. Vous pouvez voir qu'il existe de nombreuses variantes dans la sélection du noyau réel et des hyperparamètres utilisés. http://rmcantin.bitbucket.org/html/bopttheory.html