Aprendizaje con funciones submodulares: Una perspectiva de optimización convexa

Título original:

Learning with Submodular Functions: A Convex Optimization Perspective

Contenido del libro:

Las funciones submodulares son relevantes para el aprendizaje automático al menos por dos razones: (1) algunos problemas pueden expresarse directamente como la optimización de funciones submodulares, y (2) la extensión de Lovsz de las funciones submodulares proporciona un conjunto útil de funciones de regularización para el aprendizaje supervisado y no supervisado. En Learning with Submodular Functions: A Convex Optimization Perspective, la teoría de las funciones submodulares se presenta de forma autocontenida desde una perspectiva de análisis convexo, presentando estrechos vínculos entre ciertos poliedros, la optimización combinatoria y los problemas de optimización convexa.

En particular, se describe cómo la minimización de funciones submodulares es equivalente a la resolución de una amplia variedad de problemas de optimización convexa. Esto permite derivar nuevos algoritmos eficientes para la minimización aproximada y exacta de funciones submodulares con garantías teóricas y buen rendimiento práctico.

Mediante la enumeración de numerosos ejemplos de funciones submodulares, se revisan diversas aplicaciones al aprendizaje automático, como la agrupación, el diseño experimental, la colocación de sensores, el aprendizaje de estructuras de modelos gráficos o la selección de subconjuntos, así como una familia de normas estructuradas inductoras de dispersión que pueden derivarse y utilizarse a partir de funciones submodulares. Aprendizaje con funciones submodulares: A Convex Optimization Perspective es una referencia ideal para investigadores, científicos o ingenieros interesados en aplicar funciones submodulares a problemas de aprendizaje automático.