Función de conjunto submodular

Mapa de valores reales con rendimientos decrecientes

En matemáticas, una función de conjunto submodular (también conocida como función submodular ) es una función de conjunto que, informalmente, describe la relación entre un conjunto de entradas y una salida, donde agregar más de una entrada tiene un beneficio adicional decreciente ( rendimientos decrecientes ). La propiedad natural de los rendimientos decrecientes 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 utilidad en varios problemas del mundo real en el aprendizaje automático y la inteligencia artificial , incluido el resumen automático , el resumen de múltiples documentos , la selección de características , el aprendizaje activo , la colocación de sensores, 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 potencia 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. Para cada uno con y cada uno tenemos eso . ${\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 uno de nosotros tenemos eso . ${\displaystyle S,T\subseteq \Omega }$ ${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$
3. Por todo y tal 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 una función subaditiva no necesita ser submodular. Si no se supone finito, entonces las condiciones anteriores no son equivalentes. En particular, una función definida 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. ${\displaystyle \Omega }$ ${\displaystyle f}$ ${\displaystyle f(S)=1}$ ${\displaystyle S}$ ${\displaystyle f(S)=0}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle T}$

Tipos y ejemplos de funciones submodulares

Monótono

Una función de conjunto es monótona si para cada caso tenemos que . Algunos ejemplos de funciones submodulares monótonas son: ${\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 f es monótona. ${\displaystyle f(S)=\sum _{i\in S}w_{i}}$ ${\displaystyle \forall i,w_{i}\geq 0}$

Funciones aditivas de presupuesto

Cualquier función de la forma para cada y se llama presupuesto aditivo. ^[6] ${\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 un conjunto básico . La función para se denomina función de cobertura. Esto se puede generalizar añadiendo 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 cualquier tenemos que es una función submodular, donde es la entropía del conjunto de variables aleatorias , un hecho conocido como desigualdad de Shannon . ^[7] Se sabe que se cumplen otras desigualdades para la función de entropía, véase 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 de matroide

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

No monótono

Una función submodular que no es monótona se llama no monótona .

Simétrico

Una función submodular no monótona se denomina simétrica si para cada caso tenemos que . Algunos ejemplos de funciones submodulares no monótonas simétricas son: ${\displaystyle f}$ ${\displaystyle S\subseteq \Omega }$ ${\displaystyle f(S)=f(\Omega -S)}$

Recortes de gráficos

Sean los vértices de un grafo . Para cualquier conjunto de vértices, denotemos el número de aristas tales que y . Esto se puede generalizar agregando pesos no negativos a las aristas. ${\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 cualquier tenemos que es una función submodular, donde es 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 las aristas dirigidas. ${\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 de funciones de conjuntos submodulares

A menudo, dada una función de conjunto submodular que describe los valores de varios conjuntos, necesitamos calcular los valores de conjuntos fraccionarios . Por ejemplo: sabemos que el valor de recibir la casa A y la casa B es V, y queremos saber el valor de recibir el 40% de la casa A y el 60% de la casa B. Para ello, necesitamos una extensión continua de la función de conjunto submodular.

Formalmente, una función de conjunto con se puede representar como una función en , asociando cada una con un vector binario tal que cuando , y en caso contrario. Una extensión continua de es una función continua , que coincide con el valor de en , es decir . ${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$ ${\displaystyle |\Omega |=n}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle S\subseteq \Omega }$ ${\displaystyle x^{S}\in \{0,1\}^{n}}$ ${\displaystyle x_{i}^{S}=1}$ ${\displaystyle i\in S}$ ${\displaystyle x_{i}^{S}=0}$ ${\displaystyle f}$ ${\displaystyle F:[0,1]^{n}\rightarrow \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle F(x^{S})=f(S)}$

Comúnmente se utilizan varios tipos de extensiones continuas de funciones submodulares, que se describen a continuación.

Ampliación de Lovász

Esta extensión recibe su nombre del matemático László Lovász . ^[9] Considere cualquier vector tal que cada . Entonces la extensión de Lovász se define como ${\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 \}))}$

donde la expectativa es sobre 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 \lambda }$ ${\displaystyle [0,1]}$ ${\displaystyle f}$

Extensión multilineal

Consideremos cualquier vector tal que cada . Entonces la extensión multilineal se define como ^{[10] [11]} . ${\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})}$

Intuitivamente, x _i representa la probabilidad de que se elija el elemento i para el conjunto. Para cada conjunto S , los dos productos internos representan la probabilidad de que el conjunto elegido sea exactamente S . Por lo tanto, la suma representa el valor esperado de f para el conjunto formado al elegir cada elemento i al azar con probabilidad xi, independientemente de los otros elementos.

Cierre convexo

Considere cualquier vector tal que cada . Entonces el cierre convexo se define como . ${\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)}$

El cierre convexo de cualquier función de conjunto es convexo sobre . ${\displaystyle [0,1]^{n}}$

Cierre cóncavo

Considere cualquier vector tal que cada . 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)}$

Relaciones entre extensiones continuas

Para las extensiones discutidas anteriormente, se puede demostrar que cuando es submodular. ^[12] ${\displaystyle f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )}$ ${\displaystyle f}$

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 submodular monótona. En términos más generales, 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. Consideremos un proceso aleatorio en el que se elige un conjunto en el que cada elemento de se incluye en independientemente con probabilidad . Entonces la siguiente desigualdad es verdadera donde es el conjunto vacío. De manera más general, consideremos el siguiente proceso aleatorio en el que se construye un conjunto de la siguiente manera. Para cada uno de construya incluyendo cada elemento de independientemente en con probabilidad . Además, sea . 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 muy similares a las funciones convexas y cóncavas . Por este motivo, 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 ciertas restricciones.

Minimización de funciones de conjuntos submodulares

La dificultad de minimizar una función de conjunto submodular depende de las restricciones impuestas al problema.

1. El problema sin restricciones de minimizar una función submodular se puede calcular en tiempo polinomial , ^{[13] [14]} e incluso en tiempo fuertemente polinomial . ^{[15] [16]} Calcular el corte mínimo en un gráfico es un caso especial de este problema de minimización.
2. El problema de minimizar una función submodular con un límite inferior de cardinalidad es NP-duro , con límites inferiores de factor polinomial en el factor de aproximación. ^{[17] [18]}

Maximización de la función del conjunto submodular

A diferencia del caso de minimización, maximizar una función submodular genérica es NP-hard incluso en el entorno sin restricciones. Por lo tanto, la mayoría de los trabajos en este campo se ocupan de algoritmos de aproximación en tiempo polinomial, incluidos algoritmos voraces o algoritmos de búsqueda local .

1. El problema de maximizar una función submodular no negativa admite un algoritmo de aproximación 1/2. ^{[19] [20]} Calcular el corte máximo de un gráfico es un caso especial de este problema.
2. El problema de maximizar una función submodular monótona sujeta a una restricción de cardinalidad admite un algoritmo de aproximación. ^{[21] [22]} El problema de cobertura máxima es un caso especial de este problema. ${\displaystyle 1-1/e}$
3. El problema de maximizar una función submodular monótona sujeta a una restricción matroide (que subsume el caso anterior) también admite un algoritmo de aproximación. ^{[23] [24] [25]} ${\displaystyle 1-1/e}$

Muchos de estos algoritmos se pueden unificar dentro de un marco de algoritmos basado en semidiferenciales. ^[18]

Problemas de optimización relacionados

Además de la minimización y maximización submodular, existen otros problemas de optimización naturales relacionados con funciones submodulares.

1. Minimizar la diferencia entre dos funciones submodulares ^[26] no sólo es NP difícil, sino también inaproximable. ^[27]
2. La minimización/maximización de una función submodular sujeta a una restricción de conjunto de nivel submodular (también conocida como optimización submodular sujeta a una restricción de cobertura submodular o de mochila submodular) admite garantías de aproximación acotadas. ^[28]
3. La partición de datos en función de una función submodular para maximizar el bienestar promedio se conoce como el problema de bienestar submodular, que también admite garantías de aproximación acotadas (ver maximización del bienestar ).

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 . ^{[4] [29]} 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 uno compra. Las funciones submodulares modelan nociones de complejidad, similitud y cooperación cuando aparecen en problemas de minimización. En problemas de maximización, por otro lado, modelan nociones de diversidad, información y cobertura.

Véase 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 el 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 colecciones 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ág.766)
6. Buchbinder, Niv; Feldman, Moran (2018). "Problemas de maximización de funciones submodulares". En Gonzalez, Teofilo F. (ed.). Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications . Chapman y Hall/CRC. doi :10.1201/9781351236423. ISBN 9781351236423.
7. "Procesamiento de información y aprendizaje" (PDF) . cmu.
8. Fujishige (2005) pág. 22
9. Lovász, L. (1983). "Funciones submodulares y convexidad". Programación matemática: el estado del arte . págs. 235–257. doi :10.1007/978-3-642-68874-4_10. ISBN 978-3-642-68876-8.S2CID117358746  .​
10. Vondrak, Jan (17 de mayo de 2008). "Aproximación óptima para el problema de bienestar submodular en el modelo de oráculo de valores". Actas del cuadragésimo simposio anual de la ACM sobre teoría de la computación . STOC '08. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 67–74. doi :10.1145/1374376.1374389. ISBN 978-1-60558-047-0.S2CID 170510  .
11. Calinescu, Gruia; Chekuri, Chandra; Pál, Martín; Vondrák, Jan (enero de 2011). "Maximización de una función submodular monótona sujeta a una restricción matroide". Revista SIAM de Computación . 40 (6): 1740-1766. doi : 10.1137/080733991. ISSN  0097-5397.
12. Vondrák, Jan. "Técnicas poliédricas en optimización combinatoria: Conferencia 17" (PDF) .
13. Grötschel, M. ; Lovasz, L. ; Schrijver, A. (1981). "El método del elipsoide y sus consecuencias en la optimización combinatoria". Combinatorica . 1 (2): 169–197. doi :10.1007/BF02579273. hdl : 10068/182482 . S2CID  43787103.
14. Cunningham, WH (1985). "Sobre la minimización de funciones submodulares". Combinatorica . 5 (3): 185–192. doi :10.1007/BF02579361. S2CID  33192360.
15. 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.
16. Schrijver, A. (2000). "Un algoritmo combinatorio que minimiza funciones submodulares en tiempo fuertemente polinomial". J. Combin. Theory Ser. B . 80 (2): 346–355. doi : 10.1006/jctb.2000.1989 .
17. Z. Svitkina y L. Fleischer, Aproximación submodular: algoritmos basados ​​en muestreo y límites inferiores, SIAM Journal on Computing (2011).
18. R. Iyer, S. Jegelka y J. Bilmes, Optimización de funciones submodulares basada en semidiferenciales rápidos, Proc. ICML (2013).
19. U. Feige , V. Mirrokni y J. Vondrák, Maximización de funciones submodulares no monótonas, Actas del 48.º FOCS (2007), págs. 461–471.
20. N. Buchbinder, M. Feldman, J. Naor y R. Schwartz, Una aproximación lineal temporal ajustada (1/2) para la maximización submodular sin restricciones, Proc. del 53.º FOCS (2012), págs. 649-658.
21. Nemhauser, George ; Wolsey, LA; Fisher, ML (1978). "Un análisis de aproximaciones para maximizar funciones de conjuntos submodulares I". Programación matemática . 14 (14): 265–294. doi :10.1007/BF01588971. S2CID  206800425.
22. Williamson, David P. "Uniendo la optimización continua y discreta: lección 23" (PDF) .
23. 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.
24. M. Feldman, J. Naor y R. Schwartz, Un algoritmo voraz continuo unificado para la maximización submodular, Proc. del 52.º FOCS (2011).
25. Y. Filmus, J. Ward, Un algoritmo combinatorio estricto para la maximización submodular sujeto a una restricción matroide, Proc. del 53.º FOCS (2012), págs. 659-668.
26. M. Narasimhan y J. Bilmes, Un procedimiento submodular-supermodular con aplicaciones al aprendizaje de estructuras discriminativas, en Proc. UAI (2005).
27. R. Iyer y J. Bilmes, Algoritmos para la minimización aproximada de la diferencia entre funciones submodulares, en Proc. UAI (2012).
28. R. Iyer y J. Bilmes, Optimización submodular sujeta a restricciones de cubierta submodular y de mochila submodular, en Advances of NIPS (2013).
29. 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), Un 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 , Elsevier, ISBN 0-444-82523-1
• Oxley, James G. (1992), Teoría de matroides , Oxford Science Publications, Oxford: Oxford University Press , ISBN 0-19-853563-5, Zbl0784.05002 ​

Enlaces externos

• http://www.cs.berkeley.edu/~stefje/references.html tiene una bibliografía más larga
• http://submodularity.org/ incluye más material sobre el tema.