Función de conjunto submodular - Submodular set function

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 suma 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 y la 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.

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. ${\ Displaystyle \ Omega}$${\ Displaystyle f: 2 ^ {\ Omega} \ rightarrow \ mathbb {R}}$${\ Displaystyle 2 ^ {\ Omega}}$${\ Displaystyle \ Omega}$

1. Por cada con y 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 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 una función subaditiva no necesita ser submodular. Si no se asume que es finito, 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 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ó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. ${\ 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 que tengamos, es una función submodular, donde es la entropía del conjunto de variables aleatorias , un hecho conocido como desigualdad de Shannon . 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. ${\ 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 con cada elemento incluido en 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 construir incluyendo cada elemento de forma independiente en con probabilidad . Además deja . Entonces la siguiente desigualdad es verdadera . ${\ 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 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

El problema de minimización más simple es encontrar un conjunto que minimice una función submodular; este es el problema sin restricciones. Este problema es calculable en tiempo (fuertemente) polinomial . 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. ${\ 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 el 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 la función solo debe ser no negativa. Puede demostrarse 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. 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. El problema de maximizar una función submodular monótona sujeta a una restricción de cardinalidad admite un algoritmo de aproximación. 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 un algoritmo de aproximación. Muchos de estos algoritmos se pueden unificar dentro de un marco de algoritmos basado en semidiferenciales. ${\ Displaystyle 1-1 / e}$${\ 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. Desafortunadamente, este problema no solo es NP difícil, sino también inapropiable. 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. 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.

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

Ver también

• Función supermodular
• Matroide , polimatroide
• Funciones de utilidad sobre bienes indivisibles

Citas

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 , 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