Hispanopedia Wiki
Articulo de referencia

Función de conjunto submodular

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 conju...

Hispanopedia WikiContenido en espanolLectura gratuita

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 añadir más de una entrada tiene un beneficio adicional decreciente ( rendimientos decrecientes ). La propiedad natural de rendimientos decrecientes 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 utilidad en varios problemas del mundo real en aprendizaje automático e inteligencia artificial , incluyendo resumen automático , resumen de múltiples documentos , selección de características , aprendizaje activo , ubicación de sensores, resumen de colecciones de imágenes y muchos otros dominios. [ 1 ] [ 2 ] [ 3 ] [ 4 ]

Definición

SiΩ{\displaystyle \Omega }es un conjunto finito , una función submodular es una función de conjuntoF:2Ω→R{\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }, dónde2Ω{\displaystyle 2^{\Omega }}denota el conjunto potencia deΩ{\displaystyle \Omega }, que satisface una de las siguientes condiciones equivalentes. [ 5 ]

  1. Por cadaincógnita,Y⊆Ω{\displaystyle X,Y\subseteq \Omega }conincógnita⊆Y{\displaystyle X\subsetequ Y}y cadaincógnita∈Ω∖Y{\displaystyle x\in \Omega \setminus Y}tenemos esoF(incógnita∪{incógnita})−F(incógnita)≥F(Y∪{incógnita})−F(Y){\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}.
  2. Por cadaS,T⊆Ω{\displaystyle S,T\subseteq \Omega }tenemos esoF(S)+F(T)≥F(S∪T)+F(S∩T){\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}.
  3. Por cadaincógnita⊆Ω{\displaystyle X\subseteq \Omega }yincógnita1,incógnita2∈Ω∖incógnita{\displaystyle x_{1},x_{2}\in \Omega \backslash X}de tal manera queincógnita1≠incógnita2{\displaystyle x_{1}\neq x_{2}}tenemos esoF(incógnita∪{incógnita1})+F(incógnita∪{incógnita2})≥F(incógnita∪{incógnita1,incógnita2})+F(incógnita){\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)}, o equivalentemente,F(incógnita∪{incógnita1})−F(incógnita)≥F(incógnita∪{incógnita1,incógnita2})−F(incógnita∪{incógnita2}){\displaystyle f(X\cup \{x_{1}\})-f(X)\geq f(X\cup \{x_{1},x_{2}\})-f(X\cup \{x_{2}\})}.

Una función submodular no negativa también es una función subaditiva , pero una función subaditiva no tiene por qué ser submodular.Ω{\displaystyle \Omega }Si no se asume que es finito, entonces las condiciones anteriores no son equivalentes. En particular, una función F{\displaystyle f}definido porF(S)=1{\displaystyle f(S)=1}siS{\displaystyle S}es finito yF(S)=0{\displaystyle f(S)=0}siS{\displaystyle S}es infinito satisface la primera condición anterior, pero la segunda condición falla cuandoS{\displaystyle S}yT{\displaystyle T}son conjuntos infinitos con intersección finita.

Tipos y ejemplos de funciones submodulares

Monótono

Una función de conjuntoF{\displaystyle f}es monótono si para cadaT⊆S{\displaystyle T\subseteq S}tenemos esoF(T)≤F(S){\displaystyle f(T)\leq f(S)}Ejemplos de funciones submodulares monótonas incluyen:

Funciones lineales (modulares)
Cualquier función de la formaF(S)=∑i∈Swi{\displaystyle f(S)=\sum _{i\in S}w_{i}}se denomina función lineal. Además, si∀i,wi≥0{\displaystyle \forall i,w_{i}\geq 0}entonces f es monótona.
Funciones que se suman al presupuesto
Cualquier función de la formaF(S)=min{B, ∑i∈Swi}{\displaystyle f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}}para cadawi≥0{\displaystyle w_{i}\geq 0}yB≥0{\displaystyle B\geq 0}se denomina aditivo presupuestario. [ 6 ]
Funciones de cobertura
DejarΩ={mi1,mi2,…,minorte}{\displaystyle \Omega =\{E_{1},E_{2},\ldots,E_{n}\}}ser una colección de subconjuntos de algún conjunto baseΩ′{\displaystyle \Omega '}. La funciónF(S)=|⋃mii∈Smii|{\displaystyle f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|}paraS⊆Ω{\displaystyle S\subseteq \Omega }Se denomina función de cobertura. Esta puede generalizarse añadiendo ponderaciones no negativas a los elementos.
Entropía
DejarΩ={incógnita1,incógnita2,…,incógnitanorte}{\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}Sea un conjunto de variables aleatorias . Entonces, para cualquierS⊆Ω{\displaystyle S\subseteq \Omega }tenemos esoH(S){\displaystyle H(S)}es una función submodular, dondeH(S){\displaystyle H(S)}es la entropía del conjunto de variables aleatoriasS{\displaystyle S}, un hecho conocido como la desigualdad de Shannon . [ 7 ] Se sabe que se cumplen otras desigualdades para la función de entropía, véase vector entrópico .
Funciones de clasificación de matroid
DejarΩ={mi1,mi2,…,minorte}{\displaystyle \Omega =\{e_{1},e_{2},\dots,e_{n}\}}Sea el conjunto base sobre el cual se define un matroide. Entonces, la función de rango del matroide es una función submodular. [ 8 ]

No monótono

Una función submodular que no es monótona se llama no monótona . En particular, una función se llama no monótona si tiene la propiedad de que agregar más elementos a un conjunto puede disminuir el valor de la función. Más formalmente, la funciónF{\displaystyle f}no es monótono si hay conjuntosS,T{\displaystyle S,T}en su dominio stS⊂T{\displaystyle S\subset T}yF(S)>F(T){\displaystyle f(S)>f(T)}.

Simétrico

Una función submodular no monótonaF{\displaystyle f}se llama simétrico si para cadaS⊆Ω{\displaystyle S\subseteq \Omega }tenemos esoF(S)=F(Ω−S){\displaystyle f(S)=f(\Omega -S)}Algunos ejemplos de funciones submodulares simétricas no monótonas son:

Recortes de gráficos
DejarΩ={v1,v2,…,vnorte}{\displaystyle \Omega =\{v_{1},v_{2},\dots,v_{n}\}}sean los vértices de un grafo . Para cualquier conjunto de vérticesS⊆Ω{\displaystyle S\subseteq \Omega }dejarF(S){\displaystyle f(S)}denota el número de aristasmi=(tú,v){\displaystyle e=(u,v)}de tal manera quetú∈S{\displaystyle u\in S}yv∈Ω−S{\displaystyle v\en \Omega -S}Esto se puede generalizar añadiendo pesos no negativos a las aristas.
Información mutua
DejarΩ={incógnita1,incógnita2,…,incógnitanorte}{\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}Sea un conjunto de variables aleatorias . Entonces, para cualquierS⊆Ω{\displaystyle S\subseteq \Omega }tenemos esoF(S)=I(S;Ω−S){\displaystyle f(S)=I(S;\Omega -S)}es una función submodular, dondeI(S;Ω−S){\displaystyle I(S;\Omega -S)}es la información mutua.

Asimétrico

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

Recortes dirigidos
DejarΩ={v1,v2,…,vnorte}{\displaystyle \Omega =\{v_{1},v_{2},\dots,v_{n}\}}sean los vértices de un grafo dirigido . Para cualquier conjunto de vérticesS⊆Ω{\displaystyle S\subseteq \Omega }dejarF(S){\displaystyle f(S)}denota el número de aristasmi=(tú,v){\displaystyle e=(u,v)}de tal manera quetú∈S{\displaystyle u\in S}yv∈Ω−S{\displaystyle v\en \Omega -S}Esto se puede generalizar añadiendo pesos no negativos a las aristas dirigidas.

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 conjuntoF:2Ω→R{\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }con|Ω|=norte{\displaystyle |\Omega |=n}puede representarse como una función en{0,1}norte{\displaystyle \{0,1\}^{n}}, asociando cada unoS⊆Ω{\displaystyle S\subseteq \Omega }con un vector binarioincógnitaS∈{0,1}norte{\displaystyle x^{S}\in \{0,1\}^{n}}de tal manera queincógnitaiS=1{\displaystyle x_{i}^{S}=1}cuandoi∈S{\displaystyle i\in S}, yincógnitaiS=0{\displaystyle x_{i}^{S}=0}de lo contrario. Una extensión continua deF{\displaystyle f}es una función continuaF:[0,1]norte→R{\displaystyle F:[0,1]^{n}\rightarrow \mathbb {R} }, que coincide con el valor deF{\displaystyle f}enincógnita∈{0,1}norte{\displaystyle x\in \{0,1\}^{n}}, es decirF(incógnitaS)=F(S){\displaystyle F(x^{S})=f(S)}.

A continuación se describen varios tipos de extensiones continuas de funciones submodulares.

Extensión de Lovász

Esta extensión lleva el nombre del matemático László Lovász . [ 9 ] Considere cualquier vectorincógnita={incógnita1,incógnita2,…,incógnitanorte}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}de tal manera que cada0≤incógnitai≤1{\displaystyle 0\leq x_{i}\leq 1}. Entonces la extensión de Lovász se define como

FL(incógnita)=mi(F({i|incógnitai≥λ})){\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}

donde la expectativa ha terminadoλ{\displaystyle \lambda }elegido de la distribución uniforme en el intervalo[0,1]{\displaystyle [0,1]}La extensión de Lovász es una función convexa si y solo siF{\displaystyle f}es una función submodular.

Extensión multilineal

Consideremos cualquier vectorincógnita={incógnita1,incógnita2,…,incógnitanorte}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}de tal manera que cada0≤incógnitai≤1{\displaystyle 0\leq x_{i}\leq 1}. Entonces la extensión multilineal se define como [ 10 ] [ 11 ]F(incógnita)=∑S⊆ΩF(S)∏i∈Sincógnitai∏i∉S(1−incógnitai){\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 el elemento i sea elegido para el conjunto. Para cada conjunto S , los dos productos escalares 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

Consideremos cualquier vectorincógnita={incógnita1,incógnita2,…,incógnitanorte}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}de tal manera que cada0≤incógnitai≤1{\displaystyle 0\leq x_{i}\leq 1}Entonces, el cierre convexo se define comoF−(incógnita)=min(∑SαSF(S):∑SαS1S=incógnita,∑SαS=1,αS≥0){\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 función de conjunto es convexa sobre[0,1]norte{\displaystyle [0,1]^{n}}.

Cierre cóncavo

Consideremos cualquier vectorincógnita={incógnita1,incógnita2,…,incógnitanorte}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}de tal manera que cada0≤incógnitai≤1{\displaystyle 0\leq x_{i}\leq 1}Entonces, el cierre cóncavo se define comoF+(incógnita)=máximo(∑SαSF(S):∑SαS1S=incógnita,∑SαS=1,αS≥0){\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 analizadas anteriormente, se puede demostrar queF+(incógnita)≥F(incógnita)≥F−(incógnita)=FL(incógnita){\displaystyle f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )}cuandoF{\displaystyle f}es submodular. [ 12 ]

Propiedades

  1. La clase de funciones submodulares es cerrada bajo combinaciones lineales no negativas . Consideremos cualquier función submodular.F1,F2,…,Fk{\displaystyle f_{1},f_{2},\ldots ,f_{k}}y números no negativosα1,α2,…,αk{\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}. Luego la funcióngramo{\displaystyle g}definido porgramo(S)=∑i=1kαiFi(S){\displaystyle g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)}es submodular.
  2. Para cualquier función submodularF{\displaystyle f}, la función definida porgramo(S)=F(Ω∖S){\displaystyle g(S)=f(\Omega \setminus S)}es submodular.
  3. La funcióngramo(S)=min(F(S),do){\displaystyle g(S)=\min(f(S),c)}, dóndedo{\displaystyle c}es un número real , es submodular siempre queF{\displaystyle f}es monótono submodular. Más generalmente,gramo(S)=h(F(S)){\displaystyle g(S)=h(f(S))}es submodular, para cualquier función cóncava no decrecienteh{\displaystyle h}.
  4. Consideremos un proceso aleatorio donde un conjuntoT{\displaystyle T}se elige con cada elemento enΩ{\displaystyle \Omega }estar incluido enT{\displaystyle T}independientemente con probabilidadpag{\displaystyle p}Entonces, la siguiente desigualdad es verdadera.mi[F(T)]≥pagF(Ω)+(1−pag)F(∅){\displaystyle \mathbb {E} [f(T)]\geq pf(\Omega )+(1-p)f(\varnothing )}dónde∅{\displaystyle \varnothing }es el conjunto vacío . De forma más general, consideremos el siguiente proceso aleatorio donde un conjuntoS{\displaystyle S}se construye de la siguiente manera. Para cada uno de1≤i≤l,Ai⊆Ω{\displaystyle 1\leq i\leq l,A_{i}\subseteq \Omega }construirSi{\displaystyle S_{i}}al incluir cada elemento enAi{\displaystyle A_{i}}independientemente enSi{\displaystyle S_{i}}con probabilidadpagi{\displaystyle p_{i}}Además, dejemos que...S=∪i=1lSi{\displaystyle S=\cup _{i=1}^{l}S_{i}}Entonces, la siguiente desigualdad es verdadera.mi[F(S)]≥∑R⊆[l]Πi∈RpagiΠi∉R(1−pagi)F(∪i∈RAi){\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 poseen propiedades muy similares a las de las funciones convexas y cóncavas . Por ello, un problema de optimización que consista en 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 la función de conjunto submodular

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 grafo es un caso especial de este problema de minimización.
  2. El problema de minimizar una función submodular con una cota inferior de cardinalidad es NP-difícil , con cotas inferiores de factor polinomial en el factor de aproximación. [ 17 ] [ 18 ]

Maximización de la función de conjunto submodular

A diferencia del caso de minimización, maximizar una función submodular genérica es NP-difícil incluso en el contexto sin restricciones. Por lo tanto, la mayoría de los trabajos en este campo se centran en algoritmos de aproximación de 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 grafo 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 una1−1/mi{\displaystyle 1-1/e}algoritmo de aproximación. [ 21 ] [ 22 ] El problema de cobertura máxima es un caso especial de este problema.
  3. El problema de maximizar una función submodular monótona sujeta a una restricción de matroide (que engloba el caso anterior) también admite una1−1/mi{\displaystyle 1-1/e}algoritmo de aproximación. [ 23 ] [ 24 ] [ 25 ]

Muchos de estos algoritmos pueden unificarse dentro de un marco de algoritmos basado en diferencias semi-diferenciales. [ 18 ]

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 solo 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 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 el problema del bienestar submodular, que también admite garantías de aproximación limitadas (véase maximización del bienestar ).

Aplicaciones

Las funciones submodulares aparecen de forma natural en diversas aplicaciones del mundo real, como en economía , teoría de juegos , aprendizaje automático y visión artificial [ 4 ] [ 29 ] , así como en inteligencia artificial general [ 30 ] . Debido a la propiedad de rendimientos decrecientes, las funciones submodulares modelan de forma natural los costes de los artículos, ya que suele haber un mayor descuento al aumentar la cantidad de artículos comprados. Las funciones submodulares modelan las nociones de complejidad, similitud y cooperación cuando aparecen en problemas de minimización. En los problemas de maximización, por otro lado, modelan las nociones de diversidad, información y cobertura.

Véase también

Citas

  1. ↑ H. Lin y J. Bilmes, Una clase de funciones submodulares para la generación de resúmenes de documentos, ACL-2011.
  2. ↑ S. Tschiatschek, R. Iyer, H. Wei y J. Bilmes, Aprendizaje de mezclas de funciones submodulares para la generación de resúmenes de colecciones de imágenes, NIPS-2014.
  3. ↑ A. Krause y C. Guestrin, Valor de información casi óptimo y no miope en modelos gráficos, UAI-2005.
  4. 1 2 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.). Manual de algoritmos de aproximación y metaheurísticas, segunda edición: metodologías y aplicaciones tradicionales . Chapman and Hall/CRC. doi : 10.1201/9781351236423 . ISBN 9781351236423.
  7. ↑ "Procesamiento de la información y aprendizaje" (PDF) . cmu.
  8. ^ Fujishige (2005) p.22
  9. ↑ Lovász, L. (1983). "Funciones submodulares y convexidad". Programación matemática: 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, Jan (17 de mayo de 2008). «Aproximación óptima para el problema de bienestar submodular en el modelo de oráculo de valor» . 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: Lección 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. 1 2 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, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.
  20. ↑ N. Buchbinder, M. Feldman, J. Naor y R. Schwartz, Una aproximación lineal ajustada en tiempo (1/2) para la maximización submodular sin restricciones, Actas de la 53.ª FOCS (2012), págs. 649-658.
  21. ↑ Nemhauser, George ; Wolsey, LA; Fisher, ML (1978). "Análisis de aproximaciones para maximizar funciones de conjuntos submodulares I". Mathematical Programming . 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, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.
  24. ↑ M. Feldman, J. Naor y R. Schwartz, Un algoritmo unificado continuo y voraz para la maximización submodular, Actas de la 52.ª FOCS (2011).
  25. ↑ Y. Filmus, J. Ward, Un algoritmo combinatorio ajustado para la maximización submodular sujeta a una restricción de matroide, Actas de la 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 cobertura submodular y de mochila submodular, en Advances of NIPS (2013).
  29. ↑ J. Bilmes, Submodularidad en aplicaciones de aprendizaje automático, Tutorial en AAAI-2015.
  30. ↑ Bilmes, Jeff (31 de enero de 2022). "Submodularidad en aprendizaje automático e inteligencia artificial". arXiv : 2202.00132 [ cs.LG ].

Referencias

  • http://www.cs.berkeley.edu/~stefje/references.html contiene una bibliografía más extensa.
  • http://submodularity.org/ incluye más material sobre el tema.
Lecturas relacionadas
6 articulos
Establecer funciónEn matemáticas, especialmente en teoría de la medida , una función de conjunto es una función cuyo dominio es una familia de subconjuntos de un con...Rendimientos decrecientesRendimientos decrecientesEn economía , los rendimientos decrecientes son la disminución de la producción marginal (incremental) de un proceso de producción a medida que la ...{\displaystyle \Delta +1}Algoritmo de aproximaciónEn informática e investigación operativa , los algoritmos de aproximación son algoritmos eficientes que encuentran soluciones aproximadas a problem...Teoría de juegosTeoría de juegosLa teoría de juegos es el estudio de modelos matemáticos de interacciones estratégicas. [1] Tiene aplicaciones en muchos campos de las ciencias soc...Red eléctricaRed eléctricaUna red eléctrica es una interconexión de componentes eléctricos (por ejemplo, baterías , resistencias , inductores , condensadores , interruptores...Aprendizaje automáticoAprendizaje automáticoEl aprendizaje automático ( ML ) es un campo de estudio en inteligencia artificial que se ocupa del desarrollo y estudio de algoritmos estadísticos...