Resumen

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.

• Materias:Optimización matemática Investigación operacional Administración
• Subjects:Mathematical optimization Operations research Management
• Palabras claves:Ciencias de la administración, Optimización estocástica, Programación estocástica, Optimización estocástica adaptativa, Submodularidad adaptativa, Política voraz adaptativa, Algoritmo voraz adaptativo, Garantí
• Keywords:Administration sciences, Stochastic optimization, Stochastic programming, Adaptive stochastic optimization, Adaptive submodularity, Adaptive ravenous policy, Adaptive random algorithm, Guaranteed