Importance sampling in stochastic programming : a markov chain monte carlo approach

Muestreo de importancia en programación estocástica : un enfoque de monte carlo-cadena de markov

Los modelos de programación estocástica son problemas de optimización a gran escala que se usan para facilitar la toma de decisiones bajo incertidumbre. Los algoritmos de optimización para tales problemas necesitan evaluar los costos futuros esperados de decisiones presentes, a menudo referidos como la función con recurso (recourse function).

En la práctica, este cálculo es computacionalmente complejo, ya que requiere la evaluación de una integral multidimensional cuyo integrando es un problema de optimización. A su vez, la función con recurso debe estimarse empleando técnicas tales árboles de escenario o métodos de Monte Carlo, los cuales exigen numerosas evaluaciones funcionales para producir resultados exactos para problemas a gran escala con periodos múltiples. En este documento se introduce un marco de muestreo de importancia para programación estocástica que puede producir estimados exactos de la función con recurso utilizando un número pequeño de muestras.

Adaptive submodularity: theory and applications in active learning and stochastic optimization

Submodularidad adaptativa : teoría y aplicaciones en aprendizaje activo y optimización estocástica

Varios problemas en inteligencia artificial exigen realizar de manera adaptativa una secuencia de resultados de decisiones bajo incertidumbre bajo observabilidad parcial. Resolver tales problemas de optimización estocástica es desafío fundamental, aunque particularmente difícil.

En este documento se introduce el concepto de submodularidad adaptativa, generalizando las funciones de conjuntos submodulares para políticas adaptativas. Se demuestra que, si un problema satisface esta propiedad, es suficiente con un simple algoritmo voraz adaptativo para que sea competitivo con la política óptima. Además de brindar garantías de desempeño para optimización y cobertura estocásticas, la submodularidad adaptativa se puede emplear para acelerar considerablemente el algoritmo voraz utilizando evaluaciones perezosas (lazy evaluations).

Se ilustra la utilidad del concepto proporcionando varios ejemplos de objetivos submodulares adaptativos que surgen en diversas aplicaciones de inteligencia artificial, incluyendo gestión de recursos sensibles, marketing viral y aprendizaje activo. Probar la submodularidad adaptativa para estos problemas permite recuperar resultados existentes en estas aplicaciones, tales como casos especiales, mejorar garantías de aproximación y dominar generalizaciones naturales.