Learning with submodular functions : a convex optimization perspective

Aprendizaje mediante funciones submodulares : una perspectiva de optimización convexa

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.

Structured convex optimization under submodular constraints

Optimización convexa estructurada bajo restricciones submodulares

Varios problemas de optimización continua y discreta en aprendizaje automático están relacionados con problemas de minimización convexa bajo restricciones submodulares. Este documento se enfoca en una función submodular con una estructura de grafos directa. Se muestra que un amplio intervalo de problemas de optimización convexa bajo restricciones submodulares se pueden resolver de un modo mucho más eficiente que con los métodos de optimización submodular general por medio de una reducción a un problema de flujo máximo.