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}, a fact known as Shannon's inequality.[7] Further inequalities for the entropy function are known to hold, see entropic vector.
Matroidrank functions
Let Ω={e1,e2,…,en}{\displaystyle \Omega =\{e_{1},e_{2},\dots,e_{n}\}} be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.[8]

Non-monotone

A submodular function that is not monotone is called non-monotone. In particular, a function is called non-monotone if it has the property that adding more elements to a set can decrease the value of the function. More formally, the function f{\displaystyle f} is non-monotone if there are sets S,T{\displaystyle S,T} in its domain s.t. S⊂T{\displaystyle S\subset T} and f(S)>f(T){\displaystyle f(S)>f(T)}.

Symmetric

A non-monotone submodular function f{\displaystyle f} is called symmetric if for every S⊆Ω{\displaystyle S\subseteq \Omega } we have that f(S)=f(Ω−S){\displaystyle f(S)=f(\Omega -S)}. Examples of symmetric non-monotone submodular functions include:

Graph cuts
Let Ω={v1,v2,…,vn}{\displaystyle \Omega =\{v_{1},v_{2},\dots,v_{n}\}} be the vertices of a graph. For any set of vertices S⊆Ω{\displaystyle S\subseteq \Omega } let f(S){\displaystyle f(S)} denote the number of edges e=(u,v){\displaystyle e=(u,v)} such that u∈S{\displaystyle u\in S} and v∈Ω−S{\displaystyle v\en \Omega -S}. This can be generalized by adding non-negative weights to the edges.
Mutual information
Let Ω={X1,X2,…,Xn}{\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}} be a set of random variables. Then for any S⊆Ω{\displaystyle S\subseteq \Omega } we have that f(S)=I(S;Ω−S){\displaystyle f(S)=I(S;\Omega -S)} is a submodular function, where I(S;Ω−S){\displaystyle I(S;\Omega -S)} is the mutual information.

Asymmetric

A non-monotone submodular function which is not symmetric is called asymmetric.

Directed cuts
Let Ω={v1,v2,…,vn}{\displaystyle \Omega =\{v_{1},v_{2},\dots,v_{n}\}} be the vertices of a directed graph. For any set of vertices S⊆Ω{\displaystyle S\subseteq \Omega } let f(S){\displaystyle f(S)} denote the number of edges e=(u,v){\displaystyle e=(u,v)} such that u∈S{\displaystyle u\in S} and v∈Ω−S{\displaystyle v\en \Omega -S}. This can be generalized by adding non-negative weights to the directed edges.

Continuous extensions of submodular set functions

Often, given a submodular set function that describes the values of various sets, we need to compute the values of fractional sets. For example: we know that the value of receiving house A and house B is V, and we want to know the value of receiving 40% of house A and 60% of house B. To this end, we need a continuous extension of the submodular set function.

Formally, a set function f:2Ω→R{\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} } with |Ω|=n{\displaystyle |\Omega |=n} can be represented as a function on {0,1}n{\displaystyle \{0,1\}^{n}}, by associating each S⊆Ω{\displaystyle S\subseteq \Omega } with a binary vector xS∈{0,1}n{\displaystyle x^{S}\in \{0,1\}^{n}} such that xiS=1{\displaystyle x_{i}^{S}=1} when i∈S{\displaystyle i\in S}, and xiS=0{\displaystyle x_{i}^{S}=0} otherwise. A continuous extension of f{\displaystyle f} is a continuous function F:[0,1]n→R{\displaystyle F:[0,1]^{n}\rightarrow \mathbb {R} }, that matches the value of f{\displaystyle f} on x∈{0,1}n{\displaystyle x\in \{0,1\}^{n}}, i.e. F(xS)=f(S){\displaystyle F(x^{S})=f(S)}.

Several kinds of continuous extensions of submodular functions are commonly used, which are described below.

Lovász extension

This extension is named after mathematician László Lovász.[9] Consider any vector x={x1,x2,…,xn}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}} such that each 0≤xi≤1{\displaystyle 0\leq x_{i}\leq 1}. Then the Lovász extension is defined as

fL(x)=E(f({i|xi≥λ})){\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}

where the expectation is over λ{\displaystyle \lambda } chosen from the uniform distribution on the interval [0,1]{\displaystyle [0,1]}. The Lovász extension is a convex function if and only if f{\displaystyle f} is a submodular function.

Multilinear extension

Consider any vector x={x1,x2,…,xn}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}} such that each 0≤xi≤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 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 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...