Función de conjunto submodular

Función en subconjuntos que tiene una propiedad de rendimientos decrecientes

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 algoritmos de aproximación , teoría de juegos (como funciones que modelan las preferencias del usuario) y 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 , donde denota el conjunto de potencias de , que satisface una de las siguientes condiciones equivalentes. ^[5]${\displaystyle \Omega }$${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$${\displaystyle 2^{\Omega }}$${\displaystyle \Omega }$

1. Por cada con y cada que tenemos que .${\displaystyle X,Y\subseteq \Omega }$${\displaystyle X\subseteq Y}$${\displaystyle x\in \Omega \setminus Y}$${\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}$
2. Por cada que tenemos eso .${\displaystyle S,T\subseteq \Omega }$${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$
3. Por todos y cada uno de los que tenemos eso .${\displaystyle X\subseteq \Omega }$${\displaystyle x_{1},x_{2}\in \Omega \backslash X}$${\displaystyle x_{1}\neq x_{2}}$${\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)}$

Una función submodular no negativa también es una función subaditiva , pero no es necesario que una función subaditiva sea submodular. Si no se asume que es finito, entonces las condiciones anteriores no son equivalentes. En particular, una función definida por if es finita y if es infinita satisface la primera condición anterior, pero la segunda condición falla cuando y son conjuntos infinitos con intersección finita.${\displaystyle \Omega }$${\displaystyle f}$${\displaystyle f(S)=1}$${\displaystyle S}$${\displaystyle f(S)=0}$${\displaystyle S}$${\displaystyle S}$${\displaystyle T}$

Tipos de funciones submodulares

Monótono

Una función submodular es monótona si por cada uno tenemos eso . Ejemplos de funciones submodulares monótonas incluyen:${\displaystyle f}$${\displaystyle T\subseteq S}$${\displaystyle f(T)\leq f(S)}$

Funciones lineales (modulares)

Cualquier función de la forma se llama función lineal. Además, si entonces f es monótona.${\displaystyle f(S)=\sum _{i\in S}w_{i}}$${\displaystyle \forall i,w_{i}\geq 0}$

Funciones presupuestarias aditivas

Cualquier función de la forma para cada uno y se llama presupuesto aditivo. ^{[ cita requerida ]}${\displaystyle f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}}$${\displaystyle w_{i}\geq 0}$${\displaystyle B\geq 0}$

Funciones de cobertura

Sea una colección de subconjuntos de algún conjunto básico . La función para se denomina función de cobertura. Esto se puede generalizar agregando pesos no negativos a los elementos.${\displaystyle \Omega =\{E_{1},E_{2},\ldots ,E_{n}\}}$ ${\displaystyle \Omega '}$${\displaystyle f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|}$${\displaystyle S\subseteq \Omega }$

Entropía

Sea un conjunto de variables aleatorias . Entonces, para cualquiera que tengamos, 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 .${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle H(S)}$${\displaystyle H(S)}$${\displaystyle S}$

Funciones de rango matroide

Sea el terreno sobre el que se define una matroide. Entonces, la función de rango del matroide es una función submodular. ^[7]${\displaystyle \Omega =\{e_{1},e_{2},\dots ,e_{n}\}}$

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étrica si para cada tenemos eso . Ejemplos de funciones submodulares simétricas no monótonas incluyen:${\displaystyle f}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)=f(\Omega -S)}$

Cortes de gráficos

Sean los vértices de una gráfica . Para cualquier conjunto de vértices , denotemos el número de aristas tales que y . Esto se puede generalizar agregando pesos no negativos a los bordes.${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)}$${\displaystyle e=(u,v)}$${\displaystyle u\in S}$${\displaystyle v\in \Omega -S}$

Información mutua

Sea un conjunto de variables aleatorias . Entonces, para cualquiera que tengamos, esa es una función submodular, donde está la información mutua.${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)=I(S;\Omega -S)}$${\displaystyle I(S;\Omega -S)}$

Asimétrico

Una función submodular no monótona que no es simétrica se llama asimétrica.

Cortes dirigidos

Sean los vértices de un grafo dirigido . Para cualquier conjunto de vértices , denotemos el número de aristas tales que y . Esto se puede generalizar agregando pesos no negativos a los bordes dirigidos.${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)}$${\displaystyle e=(u,v)}$${\displaystyle u\in S}$${\displaystyle v\in \Omega -S}$

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 uno . Entonces, la extensión de Lovász se define como donde se supera la expectativa elegida 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. ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}$${\displaystyle \lambda }$${\displaystyle [0,1]}$${\displaystyle f}$

Extensión multilineal

Considere cualquier vector tal que cada uno . Entonces la extensión multilineal se define como .${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle F(\mathbf {x} )=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})}$

Cierre convexo

Considere cualquier vector tal que cada uno . Entonces el cierre convexo se define como . El cierre convexo de cualquier función establecida es convexo . Se puede demostrar que para funciones submodulares. ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle f^{-}(\mathbf {x} )=\min \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}$${\displaystyle [0,1]^{n}}$${\displaystyle f^{L}(\mathbf {x} )=f^{-}(\mathbf {x} )}$

Cierre cóncavo

Considere cualquier vector tal que cada uno . Entonces el cierre cóncavo se define como .${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle f^{+}(\mathbf {x} )=\max \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}$

Propiedades

1. 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 definida por es submodular.${\displaystyle f_{1},f_{2},\ldots ,f_{k}}$${\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}$${\displaystyle g}$${\displaystyle g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)}$
2. Para cualquier función submodular , la función definida por es submodular.${\displaystyle f}$${\displaystyle g(S)=f(\Omega \setminus S)}$
3. La función , donde es un número real, es submodular siempre que sea ​​monótona submodular. De manera más general, es submodular, para cualquier función cóncava no decreciente .${\displaystyle g(S)=\min(f(S),c)}$${\displaystyle c}$${\displaystyle f}$${\displaystyle g(S)=h(f(S))}$${\displaystyle h}$
4. Considere un proceso aleatorio en el que se elige un conjunto en el que cada elemento se incluye de forma independiente con probabilidad . Entonces la siguiente desigualdad es verdadera donde está el conjunto vacío. De manera más general, considere el siguiente proceso aleatorio en el que un conjunto se construye de la siguiente manera. Para cada uno de construya al incluir cada elemento de forma independiente en con probabilidad . Además dejemos . Entonces la siguiente desigualdad es verdadera . ^{[ cita requerida ]}${\displaystyle T}$${\displaystyle \Omega }$${\displaystyle T}$${\displaystyle p}$${\displaystyle \mathbb {E} [f(T)]\geq pf(\Omega )+(1-p)f(\varnothing )}$${\displaystyle \varnothing }$${\displaystyle S}$${\displaystyle 1\leq i\leq l,A_{i}\subseteq \Omega }$${\displaystyle S_{i}}$${\displaystyle A_{i}}$${\displaystyle S_{i}}$${\displaystyle p_{i}}$${\displaystyle S=\cup _{i=1}^{l}S_{i}}$${\displaystyle \mathbb {E} [f(S)]\geq \sum _{R\subseteq [l]}\Pi _{i\in R}p_{i}\Pi _{i\notin R}(1-p_{i})f(\cup _{i\in R}A_{i})}$

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 minimice 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 polinómico en el factor de aproximación. ^{[12] [13]}${\displaystyle S\subseteq \Omega }$

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 oalgoritmos 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 un algoritmo 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${\displaystyle 1-1/e}$La restricción matroide también admite un algoritmo de aproximación. ^{[18] [19] [20]} Muchos de estos algoritmos se pueden unificar dentro de un marco de algoritmos basado en semidiferenciales. ^[13]${\displaystyle 1-1/e}$

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

1. H. Lin y J. Bilmes, una clase de funciones submodulares para resumen de documentos, ACL-2011.
2. 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.
3. A. Krause y C. Guestrin, Valor no miope casi óptimo de la información en modelos gráficos, UAI-2005.
4. A. Krause y C. Guestrin, Más allá de la convexidad: submodularidad en el aprendizaje automático, Tutorial en ICML-2008
5. (Schrijver  2003 , §44, p. 766)
6. "Procesamiento y aprendizaje de la información" (PDF) . cmu.
7. Fujishige (2005) p.22
8. 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 . 
9. 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 .
10. 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 . 
11. Cunningham, WH (1985). "Sobre minimización de funciones submodulares". Combinatorica . 5 (3): 185-192. doi : 10.1007 / BF02579361 . S2CID 33192360 . 
12. Z. Svitkina y L. Fleischer, Aproximación submodular: algoritmos basados ​​en muestreo y límites inferiores, SIAM Journal on Computing (2011).
13. R. Iyer, S. Jegelka y J. Bilmes, Optimización de función submodular basada en semidiferencial rápida, Proc. ICML (2013).
14. 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.
15. 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.
16. 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.
17. Williamson, David P. "Puente entre optimización continua y discreta: Conferencia 23" (PDF) .
18. 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.
19. M. Feldman, J. Naor y R. Schwartz, Un algoritmo codicioso continuo unificado para la maximización submodular, Proc. de la 52ª FOCS (2011).
20. 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.
21. M. Narasimhan y J. Bilmes, Un procedimiento submodular-supermodular con aplicaciones al aprendizaje de estructuras discriminativas, In Proc. AUI (2005).
22. R. Iyer y J. Bilmes, Algoritmos para la minimización aproximada de la diferencia entre funciones submodulares, In Proc. AUI (2012).
23. R. Iyer y J. Bilmes, Optimización submodular sujeta a restricciones de cobertura submodular y mochila submodular, en avances de NIPS (2013).
24. 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.
25. http://submodularity.org/ .
26. 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