Función de conjunto submodular

Mapa establecido en real 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, de manera informal, 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 los hace adecuados 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 utilidad en varios problemas del mundo real en aprendizaje automático e inteligencia artificial , incluido el resumen automático , el resumen de múltiples documentos , la selección de funciones , el aprendizaje activo , la ubicación de sensores, el resumen de 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. Por cada con y por cada 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 tenemos eso . ${\displaystyle S,T\subseteq \Omega }$ ${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$
3. Para 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 supone 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 y ejemplos de funciones submodulares.

Monótono

Una función establecida es monótona si para cada 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ótono. ${\displaystyle f(S)=\sum _{i\in S}w_{i}}$ ${\displaystyle \forall i,w_{i}\geq 0}$

Funciones aditivas al presupuesto

Cualquier función de la forma para cada uno se llama aditivo presupuestario. ^[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 algún conjunto básico . La función para se llama 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 tenemos que es una función submodular, donde es la entropía del conjunto de variables aleatorias , hecho conocido como desigualdad de Shannon . ^[7] 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 conjunto de bases sobre el cual se define una matroide. Entonces la función de rango de la 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 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 tenemos que 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 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 establecida 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 on , 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)}$

Se utilizan habitualmente varios tipos de extensiones continuas de funciones submodulares, que se describen a continuación.

Extensión de Lovász

Esta extensión lleva el 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 se elige en exceso de la distribución uniforme en el intervalo . La extensión de Lovász es una función convexa si y sólo si es una función submodular. ${\displaystyle \lambda }$ ${\displaystyle [0,1]}$ ${\displaystyle f}$

Extensión multilineal

Considere 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 demás 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)}$

La clausura convexa de cualquier conjunto de funciones es convexa 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. 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 se cumple la siguiente desigualdad donde está el conjunto vacío. De manera más general, considere el siguiente proceso aleatorio en el que se construye un conjunto de la siguiente manera. Para cada uno de construya incluyendo cada elemento de forma independiente en con probabilidad . Además deja . Entonces la siguiente desigualdad es cierta . ^{[ cita necesaria ]} ${\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 esta razón, un problema de optimización que concierne 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

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 es computable 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-difícil , con límites inferiores del factor polinómico en el factor de aproximación. ^{[17] [18]}

Maximización de funciones de conjuntos submodulares

A diferencia del caso de la minimización, maximizar una función submodular genérica es NP-difícil incluso en un entorno sin restricciones. Por tanto, la mayoría de los trabajos en este campo se ocupan de algoritmos de aproximación en tiempo polinómico, incluidos los algoritmos codiciosos o los 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] [ página necesaria ] [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 incluye 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 semidiferencial. ^[18]

Problemas de optimización relacionados

Además de la minimización y maximización submodulares, existen otros problemas de optimización natural 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 niveles submodular (también conocida como optimización submodular sujeta a cobertura submodular o restricción de mochila submodular) admite garantías de aproximación acotadas. ^[28]
3. La partición de datos basada en una función submodular para maximizar el bienestar promedio se conoce como 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 los problemas de maximización, por otro lado, modelan nociones de diversidad, información y cobertura.

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 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 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ág.766)
6. Buchbinder, Niv; Feldman, Morán (2018). "Problemas de maximización de funciones submodulares". En González, Teófilo F. (ed.). Manual de metaheurísticas y algoritmos de aproximación, segunda edición: metodologías y aplicaciones tradicionales . Chapman y Hall/CRC. doi :10.1201/9781351236423. ISBN 9781351236423.
7. "Procesamiento y aprendizaje de la información" (PDF) . cmu.
8. Fujishige (2005) p.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. S2CID  117358746.
10. Vondrak, enero (17 de mayo de 2008). "Aproximación óptima al problema de bienestar submodular en el modelo de oráculo de valor". Actas del cuadragésimo simposio anual de ACM sobre teoría de la informática . STOC '08. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. 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, enero. "Técnicas poliédricas en optimización combinatoria: Conferencia 17" (PDF) .
13. Grötschel, M .; Lovász, L .; Schrijver, A. (1981). "El método del elipsoide y sus consecuencias en la optimización combinatoria". Combinatoria . 1 (2): 169–197. doi :10.1007/BF02579273. hdl : 10068/182482 . S2CID  43787103.
14. Cunningham, WH (1985). "Sobre la minimización de funciones submodulares". Combinatoria . 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. Combinar. Teoría 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 basadas en semidiferencial rápido, Proc. ICML (2013).
19. U. Feige , V. Mirrokni y J. Vondrák, Maximización de funciones submodulares no monótonas, Proc. del 48º FOCS (2007), págs. 461–471.
20. N. Buchbinder, M. Feldman, J. Naor y R. Schwartz, Una aproximación de tiempo lineal ajustado (1/2) para maximización submodular sin restricciones, Proc. de 53.° FOCS (2012), págs. 649-658.
21. Nemhäuser, George ; Wolsey, Luisiana; Pescador, 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: Conferencia 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 codicioso continuo unificado para la maximización submodular, Proc. de la 52ª FOCS (2011).
25. Y. Filmus, J. Ward, Un algoritmo combinatorio estricto para la maximización submodular sujeto a una restricción matroide, Proc. de 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. AUI (2005).
27. R. Iyer y J. Bilmes, Algoritmos para la minimización aproximada de la diferencia entre funciones submodulares, en Proc. AUI (2012).
28. R. Iyer y J. Bilmes, Optimización submodular sujeta a restricciones de cubierta submodular y mochila submodular, en avances de 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 en 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 matroide , Oxford Science Publications, 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
• http://submodularity.org/ incluye más material sobre el tema.