Les techniques d'optimisation correspondent-elles aux techniques d'échantillonnage?

18

De tout algorithme d'échantillonnage générique, on peut dériver un algorithme d'optimisation.

En effet, pour maximiser une fonction arbitraire , il suffit de tirer des échantillons de . Pour suffisamment petit, ces échantillons tomberont près du maximum global (ou maxima local en pratique) de la fonction .f:x→f(x)g∼ef/TfTf

Par «échantillonnage», je veux dire, le prélèvement d'un échantillon pseudo-aléatoire à partir d'une distribution étant donné une fonction de log-vraisemblance connue jusqu'à une constante. Par exemple, l'échantillonnage MCMC, l'échantillonnage Gibbs, l'échantillonnage de faisceau, etc. Par «optimisation», j'entends la tentative de trouver des paramètres maximisant la valeur d'une fonction donnée.

L'inverse est-il possible? Compte tenu d'une heuristique pour trouver le maximum d'une fonction ou d'une expression combinatoire, peut-on extraire une procédure d'échantillonnage efficace?

La console HMC, par exemple, semble tirer parti des informations sur le gradient. Pouvons-nous construire une procédure d'échantillonnage qui tire parti d'une approximation de type BFGS de la Hesse? (modifier: apparemment oui: http://papers.nips.cc/paper/4464-quasi-newton-methods-for-markov-chain-monte-carlo.pdf ) Nous pouvons utiliser les SCTM dans les problèmes combinatoires, pouvons-nous traduire cela dans une procédure d'échantillonnage?

Contexte: une difficulté d'échantillonnage est souvent que la majeure partie de la masse de la distribution de probabilité se situe dans une très petite région. Il existe des techniques intéressantes pour trouver de telles régions, mais elles ne se traduisent pas directement en procédures d'échantillonnage non biaisées.

Edit: J'ai maintenant le sentiment persistant que la réponse à cette question est quelque peu équivalente à l'égalité des classes de complexité #P et NP, ce qui rend la réponse probablement "non". Cela explique pourquoi chaque technique d'échantillonnage donne une technique d'optimisation mais pas l'inverse.

sampling optimization Arthur B.
la source
Bien que je pense avoir une compréhension conventionnelle de la plupart des mots de cette question, je ne suis pas sûr de ce qu'il cherche après. Pourriez-vous préciser un peu plus précisément ce que vous entendez par «échantillonnage» et ce qui serait exactement «optimisé»? Vous semblez supposer implicitement que vos lecteurs ont en tête un cadre particulier dans lequel une "distribution" (ou une famille de ceux-ci?) Est impliquée et dans lequel un objectif particulier est supposé, mais on ne peut que deviner ce que vous avez réellement l'intention de faire des déclarations aussi larges que celles qui figurent dans le dernier paragraphe.
whuber
Par «échantillonnage», je veux dire, le prélèvement d'un échantillon pseudo-aléatoire à partir d'une distribution étant donné une fonction de log-vraisemblance connue jusqu'à une constante. Par exemple, l'échantillonnage MCMC, l'échantillonnage Gibbs, l'échantillonnage de faisceau, etc. Par «optimisation», j'entends la tentative de trouver des paramètres maximisant la valeur d'une fonction donnée. Par exemple, la descente de gradient, l'algorithme simplex, le recuit simulé sont des techniques d'optimisation.
Arthur B.19
Il existe une cartographie naturelle entre le recuit simulé et l'échantillonnage MCMC. Il y a une correspondance moins directe entre HMC et descente de gradient (si vous plissez les yeux). Ma question est de savoir si cela peut être rendu plus systématique. Une difficulté d'échantillonnage est souvent que la majeure partie de la masse de la distribution de probabilité se trouve dans une très petite région. Il existe des techniques intéressantes pour trouver cette région, mais elles ne se traduisent pas directement en procédures d'échantillonnage non biaisées.
Arthur B.19
Veuillez modifier votre question pour inclure ces clarifications. Ceci est crucial car votre utilisation (quelque peu spécialisée) du mot «échantillonnage», bien que appropriée dans votre contexte, diffère de ce que de nombreux lecteurs peuvent comprendre. En outre, votre explication de "l'optimisation", bien que correcte, ne semble pas utile pour rendre sa signification suffisamment précise ici: caractériser ce qu'est la "fonction donnée" et comment elle pourrait être liée à "l'échantillonnage" serait des ajouts utiles.
whuber
Est-ce mieux maintenant?
Arthur B.19

Réponses:

0

Une possibilité est de trouver le CDF de l'heuristique. Ensuite, d'après la théorie de Monte Carlo, nous savons que pour , où F est le cdf de la distribution que vous recherchez. Si vous ne trouvez pas exactement le cdf, vous pouvez utiliser une simple heuristique basée sur l'acceptation-rejet.F - 1 ( U ) ∼ FU∼unif[0,1]F−1(U)∼F

Sid
la source