¿Las técnicas de optimización se corresponden con las técnicas de muestreo?

De cualquier algoritmo de muestreo genérico, uno puede derivar un algoritmo de optimización.

De hecho, para maximizar una función arbitraria , es suficiente para extraer muestras de . Para suficientemente pequeño, estas muestras caerán cerca del máximo global (o máximos locales en la práctica) de la función . $f: \textbf{x} \rightarrow f(\textbf{x})$ $g \sim e^{f/T}$ $T$ $f$

Por "muestreo" quiero decir, sacar una muestra pseudoaleatoria de una distribución dada una función de log-verosimilitud conocida hasta una constante. Por ejemplo, muestreo de MCMC, muestreo de Gibbs, muestreo de haz, etc. Por "optimización" me refiero al intento de encontrar parámetros que maximicen el valor de una función dada.

¿Es posible lo contrario? Dada una heurística para encontrar el máximo de una función o una expresión combinatoria, ¿podemos extraer un procedimiento de muestreo eficiente?

HMC, por ejemplo, parece aprovechar la información de gradiente. ¿Podemos construir un procedimiento de muestreo que aproveche una aproximación similar a BFGS de la arpillera? (Editar: aparentemente sí: http://papers.nips.cc/paper/4464-quasi-newton-methods-for-markov-chain-monte-carlo.pdf ) Podemos usar MCTS en problemas combinatorios, ¿podemos traducir eso? en un procedimiento de muestreo?

Contexto: una dificultad en el muestreo es a menudo que la mayor parte de la distribución de probabilidad se encuentra dentro de una región muy pequeña. Existen técnicas interesantes para encontrar tales regiones, pero no se traducen directamente en procedimientos de muestreo imparciales.

Editar: ahora tengo la sensación persistente de que la respuesta a esa pregunta es algo equivalente a la igualdad de las clases de complejidad #P y NP, lo que hace que la respuesta sea un "no". Explica por qué cada técnica de muestreo produce una técnica de optimización, pero no al revés.

sampling optimization Arthur B.
fuente

Aunque creo que tengo una comprensión convencional de la mayoría de las palabras en esta pregunta, no estoy seguro de lo que está sucediendo después. ¿Podría decir con un poco más de precisión qué quiere decir con "muestreo" y qué sería exactamente "optimizado"? Parece suponer implícitamente que sus lectores tienen en mente un entorno particular en el que está involucrada una "distribución" (¿o una familia de los mismos?) Y en la que se asume un objetivo particular, pero uno solo puede adivinar lo que realmente pretende cuando realiza declaraciones tan amplias como las que aparecen en el último párrafo.

whuber

Arthur B.

Existe un mapeo natural entre el recocido simulado y el muestreo MCMC. Hay un mapeo menos directo entre HMC y el descenso de gradiente (si entrecierra los ojos). Mi pregunta es si esto puede hacerse más sistemático. Una dificultad en el muestreo es a menudo que la mayor parte de la distribución de probabilidad se encuentra dentro de una región muy pequeña. Existen técnicas interesantes para encontrar esta región, pero no se traducen directamente en procedimientos de muestreo imparciales.

Arthur B.

Edite su pregunta para incluir estas aclaraciones. Eso es crucial porque su uso (algo especializado) de la palabra "muestreo", aunque apropiado en su contexto, difiere de lo que muchos lectores pueden entender. Además, su explicación de "optimización", aunque correcta, no parece ser útil para hacer que su significado sea lo suficientemente preciso aquí: caracterizar cuál es la "función dada" y cómo podría estar relacionado con el "muestreo" sería una adición útil.

whuber

¿Esta mejor ahora?

Arthur B.

¿Las técnicas de optimización se corresponden con las técnicas de muestreo?

Respuestas: