Resumen

Las funciones submodulares son relevantes para el aprendizaje automático o de máquinas (machine learning) al menos por dos razones: (1) algunos problemas pueden expresarse de modo directo como la optimización de funciones submodulares y (2) la extensión de Lovász de tales funciones brinda un conjunto útil de funciones de regularización para el aprendizaje supervisado y sin supervisión.

En esta monografía se presenta la teoría de las funciones submodulares desde una perspectiva del análisis convexo, mostrando fuertes lazos entre ciertos poliedros, la optimización combinatoria y problemas de optimización convexa. En particular, se revela cómo la minimización de funciones submodulares equivale a la solución de una amplia variedad de problemas de optimización convexa. Esto permite la generación de nuevos algoritmos eficientes para una minimización aproximada y exacta de funciones submodulares con garantías teóricas y un buen desempeño práctico.

Mediante el listado de varios ejemplos de funciones submodulares, se revisan aplicaciones diversas para el aprendizaje automático, tales como clustering, diseño experimental, colocación de sensores, aprendizaje gráfico de estructura de modelos o selección de subconjuntos, así como una familia de normas de inducción de dispersión estructuradas (structured sparsity-inducing norms) que pueden derivarse y utilizarse a partir de funciones submodulares.

• Materias:Administración Administración de empresas Investigación operacional
• Subjects:Management Business enterprises Operations research
• Palabras claves:Ciencias de la administración, Optimización, Convexidad, Optimización convexa, Optimización convexa no suave, Funciones submodulares, Minimización de funciones submodulares, Submodularidad
• Keywords:Administration sciences, Optimization, Convexity, Convex optimization, Non-soft convex optimization, Submodular functions, Minimization of submodular functions, Submodularity