En matemáticas, una función de conjunto submodular (también conocida como función submodular ) es una función de conjunto cuyo valor, informalmente, tiene la propiedad de que la diferencia en el valor incremental de la función que hace un solo elemento cuando se agrega a un conjunto de entrada disminuye a medida que aumenta el tamaño del conjunto de entrada. Las funciones submodulares tienen una propiedad natural de rendimientos decrecientes que las hace adecuadas para muchas aplicaciones, incluidos los algoritmos de aproximación , la teoría de juegos (como funciones que modelan las preferencias del usuario) y las redes eléctricas . Recientemente, las funciones submodulares también han encontrado una inmensa utilidad en varios problemas del mundo real en el aprendizaje automático.e inteligencia artificial , incluido el resumen automático , el resumen de varios documentos , la selección de funciones , el aprendizaje activo , la ubicación del sensor, el resumen de la colección de imágenes y muchos otros dominios. [1] [2] [3] [4]
Definición
Si es un conjunto finito , una función submodular es una función de conjunto, dónde denota el conjunto de poder de, que satisface una de las siguientes condiciones equivalentes. [5]
- Para cada con y cada tenemos eso .
- Para cada tenemos eso .
- Para cada y tal que tenemos eso .
Una función submodular no negativa también es una función subaditiva , pero no es necesario que una función subaditiva sea submodular. Sino se asume finito, entonces las condiciones anteriores no son equivalentes. En particular una función definido por Si es finito y Si es infinito satisface la primera condición anterior, pero la segunda condición falla cuando y son conjuntos infinitos con intersección finita.
Tipos de funciones submodulares
Monótono
Una función submodular es monótono si para cada tenemos eso . Ejemplos de funciones submodulares monótonas incluyen:
- Funciones lineales (modulares)
- Cualquier función de la forma se llama función lineal. Además si entonces f es monótona.
- Funciones presupuestarias aditivas
- Cualquier función de la forma para cada y se llama aditivo presupuestario. [ cita requerida ]
- Funciones de cobertura
- Dejar ser una colección de subconjuntos de algún conjunto básico. La función por se llama función de cobertura. Esto se puede generalizar agregando pesos no negativos a los elementos.
- Entropía
- Dejar ser un conjunto de variables aleatorias . Entonces para cualquier tenemos eso es una función submodular, donde es la entropía del conjunto de variables aleatorias , un hecho conocido como desigualdad de Shannon . [6] Se sabe que se cumplen otras desigualdades para la función de entropía, ver vector entrópico .
- Funciones de rango matroide
- Dejar ser el terreno sobre el que se define una matroide. Entonces, la función de rango del matroide es una función submodular. [7]
No monótono
Una función submodular que no es monótona se denomina no monótona .
Simétrico
Una función submodular no monótona se llama simétrico si para cada tenemos eso . Ejemplos de funciones submodulares simétricas no monótonas incluyen:
- Cortes de gráficos
- Dejar ser los vértices de una gráfica . Para cualquier conjunto de vértices dejar denotar el número de aristas tal que y . Esto se puede generalizar agregando pesos no negativos a los bordes.
- Información mutua
- Dejar ser un conjunto de variables aleatorias . Entonces para cualquier tenemos eso es una función submodular, donde es la información mutua.
Asimétrico
Una función submodular no monótona que no es simétrica se llama asimétrica.
- Cortes dirigidos
- Dejar ser los vértices de un grafo dirigido . Para cualquier conjunto de vértices dejar denotar el número de aristas tal que y . Esto se puede generalizar agregando pesos no negativos a los bordes dirigidos.
Extensiones continuas
Extensión de Lovász
Esta extensión lleva el nombre del matemático László Lovász . Considere cualquier vector tal que cada . Entonces la extensión Lovász se define como donde la expectativa se acabó elegido de la distribución uniforme en el intervalo. La extensión de Lovász es una función convexa si y solo si es una función submodular.
Extensión multilineal
Considere cualquier vector tal que cada . Entonces la extensión multilineal se define como.
Cierre convexo
Considere cualquier vector tal que cada . Entonces el cierre convexo se define como. El cierre convexo de cualquier función establecida es convexo sobre. Se puede demostrar que para funciones submodulares.
Cierre cóncavo
Considere cualquier vector tal que cada . Entonces el cierre cóncavo se define como.
Propiedades
- La clase de funciones submodulares está cerrada bajo combinaciones lineales no negativas . Considere cualquier función submodular y números no negativos . Entonces la función definido por es submodular.
- Para cualquier función submodular , la función definida por es submodular.
- La función , dónde es un número real, es submodular siempre que es submodular monótono. Más generalmente, es submodular, para cualquier función cóncava no decreciente .
- Considere un proceso aleatorio donde un conjunto se elige con cada elemento en ser incluido en independientemente con probabilidad . Entonces la siguiente desigualdad es verdadera dónde es el conjunto vacío. De manera más general, considere el siguiente proceso aleatorio donde un conjuntose construye de la siguiente manera. Para cada uno de construir incluyendo cada elemento en independientemente en con probabilidad . Además deja. Entonces la siguiente desigualdad es verdadera. [ cita requerida ]
Problemas de optimización
Las funciones submodulares tienen propiedades que son muy similares a las funciones convexas y cóncavas . Por esta razón, un problema de optimización que se refiere a optimizar una función convexa o cóncava también puede describirse como el problema de maximizar o minimizar una función submodular sujeta a algunas restricciones.
Minimización de funciones de conjuntos submodulares
El problema de minimización más simple es encontrar un conjunto que minimiza una función submodular; este es el problema ilimitado. Este problema se puede calcular en (fuertemente) [8] [9] tiempo polinomial . [10] [11] Calcular el corte mínimo en un gráfico es un caso especial de este problema general de minimización. Sin embargo, agregar incluso una restricción simple, como un límite inferior de cardinalidad, dificulta el problema de minimización NP , con límites inferiores del factor polinomial en el factor de aproximación. [12] [13]
Maximización de la función del conjunto submodular
A diferencia del caso de la minimización, maximizar las funciones submodulares es NP-difícil incluso en un entorno sin restricciones. Los algoritmos de teoría y enumeración para encontrar máximos (mínimos) locales y globales de funciones submodulares (supermodulares) se pueden encontrar en B. Goldengorin. Revista europea de investigación operativa 198 (1): 102-112, DOI: 10.1016 / j.ejor.2008.08.022. Por ejemplo, el corte máximo es un caso especial incluso cuando se requiere que la función solo sea no negativa. Se puede demostrar que el problema no restringido es inapropiable si se permite que sea negativo. Se ha trabajado mucho sobre la maximización de funciones submodulares restringidas cuando las funciones no son negativas. Normalmente, los algoritmos de aproximación para estos problemas se basan en algoritmos codiciosos o en algoritmos de búsqueda local . El problema de maximizar una función submodular simétrica no negativa admite un algoritmo de aproximación 1/2. [14] Calcular el corte máximo de un gráfico es un caso especial de este problema. El problema más general de maximizar una función submodular no negativa también admite un algoritmo de aproximación 1/2. [15] El problema de maximizar una función submodular monótona sujeta a una restricción de cardinalidad admite unaalgoritmo de aproximación. [16] [ página necesaria ] [17] El problema de cobertura máxima es un caso especial de este problema. El problema más general de maximizar una función submodular monótona sujeta a una restricción matroide también admite unaalgoritmo de aproximación. [18] [19] [20] Muchos de estos algoritmos se pueden unificar dentro de un marco de algoritmos basado en semidiferenciales. [13]
Problemas de optimización relacionados
Aparte de la minimización y maximización submodular, otro problema natural es la diferencia de optimización submodular. [21] [22] Desafortunadamente, este problema no solo es NP difícil, sino también inapropiable. [22] Un problema de optimización relacionado es minimizar o maximizar una función submodular, sujeta a una restricción de conjunto de nivel submodular (también llamada optimización submodular sujeta a cobertura submodular o restricción de mochila submodular). Este problema admite garantías de aproximación acotadas. [23] Otro problema de optimización involucra la partición de datos basada en una función submodular, para maximizar el bienestar promedio. Este problema se denomina problema de bienestar submodular. [24]
Aplicaciones
Las funciones submodulares ocurren naturalmente en varias aplicaciones del mundo real, en economía , teoría de juegos , aprendizaje automático y visión por computadora . Debido a la propiedad de rendimientos decrecientes, las funciones submodulares modelan naturalmente los costos de los artículos, ya que a menudo hay un descuento mayor, con un aumento en los artículos que se compran. Las funciones submodulares modelan nociones de complejidad, similitud y cooperación cuando aparecen en problemas de minimización. En los problemas de maximización, por otro lado, modelan nociones de diversidad, información y cobertura. Para obtener más información sobre las aplicaciones de la submodularidad, particularmente en el aprendizaje automático, consulte [4] [25] [26]
Ver también
- Función supermodular
- Matroide , polimatroide
- Funciones de utilidad sobre bienes indivisibles
Citas
- ^ H. Lin y J. Bilmes, una clase de funciones submodulares para resumen de documentos, ACL-2011.
- ^ S. Tschiatschek, R. Iyer, H. Wei y J. Bilmes, Aprendizaje de mezclas de funciones submodulares para el resumen de la colección de imágenes, NIPS-2014.
- ^ A. Krause y C. Guestrin, Valor no miope casi óptimo de la información en modelos gráficos, UAI-2005.
- ^ a b A. Krause y C. Guestrin, Más allá de la convexidad: submodularidad en el aprendizaje automático, Tutorial en ICML-2008
- ↑ (Schrijver 2003 , §44, p. 766)
- ^ "Procesamiento y aprendizaje de la información" (PDF) . cmu.
- ^ Fujishige (2005) p.22
- ^ Iwata, S .; Fleischer, L .; Fujishige, S. (2001). "Un algoritmo combinatorio fuertemente polinomial para minimizar funciones submodulares". J. ACM . 48 (4): 761–777. doi : 10.1145 / 502090.502096 . S2CID 888513 .
- ^ Schrijver, A. (2000). "Un algoritmo combinatorio que minimiza funciones submodulares en tiempo fuertemente polinomial" . J. Combin. Teoría Ser. B . 80 (2): 346–355. doi : 10.1006 / jctb.2000.1989 .
- ^ Grötschel, M .; Lovasz, L .; Schrijver, A. (1981). "El método elipsoide y sus consecuencias en la optimización combinatoria". Combinatorica . 1 (2): 169-197. doi : 10.1007 / BF02579273 . hdl : 10068/182482 . S2CID 43787103 .
- ^ Cunningham, WH (1985). "Sobre minimización de funciones submodulares". Combinatorica . 5 (3): 185-192. doi : 10.1007 / BF02579361 . S2CID 33192360 .
- ^ Z. Svitkina y L. Fleischer, Aproximación submodular: algoritmos basados en muestreo y límites inferiores, SIAM Journal on Computing (2011).
- ^ a b R. Iyer, S. Jegelka y J. Bilmes, Optimización de función submodular basada en semidiferencial rápida, Proc. ICML (2013).
- ^ U. Feige , V. Mirrokni y J. Vondrák, Maximización de funciones submodulares no monótonas, Proc. of 48th FOCS (2007), págs. 461–471.
- ^ N. Buchbinder, M. Feldman, J. Naor y R. Schwartz, Un tiempo lineal ajustado (1/2) -aproximación para la maximización submodular ilimitada, Proc. de 53a FOCS (2012), págs. 649-658.
- ^ GL Nemhauser , LA Wolsey y ML Fisher, Un análisis de aproximaciones para maximizar las funciones de conjuntos submodulares I, Programación matemática 14 (1978), 265-294.
- ^ Williamson, David P. "Uniendo la optimización continua y discreta: Conferencia 23" (PDF) .
- ^ G. Calinescu, C. Chekuri, M. Pál y J. Vondrák, Maximización de una función de conjunto submodular sujeta a una restricción matroide, SIAM J. Comp. 40: 6 (2011), 1740-1766.
- ^ M. Feldman, J. Naor y R. Schwartz, Un algoritmo codicioso continuo unificado para la maximización submodular, Proc. de la 52ª FOCS (2011).
- ^ Y. Filmus, J. Ward, Un algoritmo combinatorio estricto para la maximización submodular sujeto a una restricción matroide, Proc. de 53a FOCS (2012), págs. 659-668.
- ^ M. Narasimhan y J. Bilmes, Un procedimiento submodular-supermodular con aplicaciones al aprendizaje de estructuras discriminativas, In Proc. AUI (2005).
- ^ a b R. Iyer y J. Bilmes, Algoritmos para la minimización aproximada de la diferencia entre funciones submodulares, In Proc. AUI (2012).
- ^ R. Iyer y J. Bilmes, Optimización submodular sujeta a restricciones de cobertura submodular y mochila submodular, en avances de NIPS (2013).
- ^ J. Vondrák, Aproximación óptima para el problema de bienestar submodular en el modelo de oráculo de valor, Proc. de STOC (2008), págs. 461–471.
- ^ http://submodularity.org/ .
- ^ J. Bilmes, Submodularidad en aplicaciones de aprendizaje automático, Tutorial en AAAI-2015.
Referencias
- Schrijver, Alexander (2003), Optimización combinatoria , Springer , ISBN 3-540-44389-4
- Lee, Jon (2004), primer curso de optimización combinatoria , Cambridge University Press , ISBN 0-521-01012-8
- Fujishige, Satoru (2005), Funciones submodulares y optimización , Elsevier , ISBN 0-444-52086-4
- Narayanan, H. (1997), Funciones submodulares y redes eléctricas , ISBN 0-444-82523-1
- Oxley, James G. (1992), teoría matroide , publicaciones científicas de Oxford, Oxford: Oxford University Press , ISBN 0-19-853563-5, Zbl 0784.05002
enlaces externos
- http://www.cs.berkeley.edu/~stefje/references.html tiene una bibliografía más extensa