Funcția de set submodular - Submodular set function

În matematică, o funcție de set submodular (cunoscută și sub numele de funcție submodulară ) este o funcție de set a cărei valoare, în mod informal, are proprietatea că diferența în valoarea incrementală a funcției pe care un singur element o face atunci când este adăugată la un set de intrare scade ca dimensiunea setului de intrare crește. Funcțiile submodulare au o proprietate de returnare naturală , care le face adecvate pentru multe aplicații, inclusiv algoritmi de aproximare , teoria jocurilor (ca funcții care modelează preferințele utilizatorului) și rețelele electrice . Recent, funcțiile submodulare au găsit, de asemenea, o utilitate imensă în mai multe probleme din lumea reală în învățarea automată și inteligența artificială , inclusiv rezumarea automată , rezumarea multi-document , selecția caracteristicilor , învățarea activă , plasarea senzorilor, rezumarea culegerii de imagini și multe alte domenii.

Definiție

Dacă este un set finit , o funcție submodulară este o funcție de set , unde denotă setul de putere al , care îndeplinește una dintre următoarele condiții echivalente. ${\ displaystyle \ Omega}$${\ displaystyle f: 2 ^ {\ Omega} \ rightarrow \ mathbb {R}}$${\ displaystyle 2 ^ {\ Omega}}$${\ displaystyle \ Omega}$

1. Pentru fiecare cu și fiecare avem asta . ${\ 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. Pentru fiecare avem asta . ${\ displaystyle S, T \ subseteq \ Omega}$${\ displaystyle f (S) + f (T) \ geq f (S \ cup T) + f (S \ cap T)}$
3. Pentru fiecare și așa ceva încât avem asta . ${\ 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)}$

O funcție submodulară non-negativă este, de asemenea, o funcție subadditivă , dar o funcție subadditivă nu trebuie să fie submodulară. Dacă nu se presupune finit, atunci condițiile de mai sus nu sunt echivalente. În special, o funcție definită de dacă este finită și dacă este infinită satisface prima condiție de mai sus, dar a doua condiție eșuează când și sunt mulțimi infinite cu intersecție finită. ${\ displaystyle \ Omega}$${\ displaystyle f}$${\ displaystyle f (S) = 1}$${\ displaystyle S}$${\ displaystyle f (S) = 0}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle T}$

Tipuri de funcții submodulare

Monoton

O funcție submodulară este monotonă dacă pentru fiecare avem asta . Exemple de funcții submodulare monotone includ: ${\ displaystyle f}$${\ displaystyle T \ subseteq S}$${\ displaystyle f (T) \ leq f (S)}$

Funcții liniare (modulare)

Orice funcție a formei se numește funcție liniară. În plus, dacă f este monoton. ${\ displaystyle f (S) = \ sum _ {i \ in S} w_ {i}}$${\ displaystyle \ forall i, w_ {i} \ geq 0}$

Funcții buget-aditive

Orice funcție a formularului pentru fiecare și se numește buget aditiv. ${\ displaystyle f (S) = \ min \ left \ {B, ~ \ sum _ {i \ in S} w_ {i} \ right \}}$${\ displaystyle w_ {i} \ geq 0}$${\ displaystyle B \ geq 0}$

Funcții de acoperire

Fie o colecție de subseturi ale unor seturi de sol . Funcția pentru se numește funcție de acoperire. Acest lucru poate fi generalizat adăugând greutăți non-negative elementelor. ${\ 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}$

Entropie

Fie un set de variabile aleatorii . Apoi, pentru orice avem, este o funcție submodulară, unde este entropia setului de variabile aleatorii , fapt cunoscut sub numele de inegalitatea lui Shannon . Se știe că există alte inegalități pentru funcția de entropie, vezi vectorul entropic . ${\ displaystyle \ Omega = \ {X_ {1}, X_ {2}, \ ldots, X_ {n} \}}$${\ displaystyle S \ subseteq \ Omega}$${\ displaystyle H (S)}$${\ displaystyle H (S)}$${\ displaystyle S}$

Funcții de rang matroid

Fie terenul pe care este definit un matroid. Atunci funcția de rang a matroidului este o funcție submodulară. ${\ displaystyle \ Omega = \ {e_ {1}, e_ {2}, \ dots, e_ {n} \}}$

Non-monotonă

O funcție submodulară care nu este monotonă se numește non-monotonă .

Simetric

O funcție submodulară non-monotonă se numește simetrică dacă pentru fiecare avem asta . Exemple de funcții submodulare non-monotone simetrice includ: ${\ displaystyle f}$${\ displaystyle S \ subseteq \ Omega}$${\ displaystyle f (S) = f (\ Omega -S)}$

Tăieturi grafice

Fie vârfurile unui grafic . Pentru orice set de vârfuri, să denotăm numărul de muchii astfel încât și . Acest lucru poate fi generalizat prin adăugarea de greutăți non-negative la margini. ${\ 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}$

Informații reciproce

Fie un set de variabile aleatorii . Apoi, pentru orice avem, este o funcție submodulară, unde este informația reciprocă. ${\ 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)}$

Asimetric

O funcție submodulară non-monotonă care nu este simetrică se numește asimetrică.

Tăieturi regizate

Fie vârfurile unui grafic direcționat . Pentru orice set de vârfuri, să denotăm numărul de muchii astfel încât și . Acest lucru poate fi generalizat prin adăugarea de greutăți non-negative la marginile îndreptate. ${\ 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}$

Extensii continue

Prelungirea Lovász

Această extensie poartă numele matematicianului László Lovász . Luați în considerare orice vector astfel încât fiecare . Apoi, extensia Lovász este definită ca unde așteptarea este peste aleasă din distribuția uniformă pe interval . Extensia Lovász este o funcție convexă dacă și numai dacă este o funcție 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}$

Extensie multiliniară

Luați în considerare orice vector astfel încât fiecare . Apoi , extensia multiliniare este definită ca fiind . ${\ 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})}$

Închidere convexă

Luați în considerare orice vector astfel încât fiecare . Apoi închiderea convexă este definită ca fiind . Închiderea convexă a oricărei funcții setate este convexă . Se poate arăta că pentru funcțiile submodulare. ${\ 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})}$

Închidere concavă

Luați în considerare orice vector astfel încât fiecare . Apoi închiderea concavă este definită ca fiind . ${\ 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)}$

Proprietăți

1. Clasa funcțiilor submodulare este închisă în combinații liniare non-negative . Luați în considerare orice funcție submodulară și numere non-negative . Atunci funcția definită de este 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. Pentru orice funcție submodulară , funcția definită de este submodulară. ${\ displaystyle f}$${\ displaystyle g (S) = f (\ Omega \ setminus S)}$
3. Funcția , unde este un număr real, este submodulară ori de câte ori este submodulară monotonă. Mai general, este submodular, pentru orice funcție concavă care nu scade . ${\ displaystyle g (S) = \ min (f (S), c)}$${\ displaystyle c}$${\ displaystyle f}$${\ displaystyle g (S) = h (f (S))}$${\ displaystyle h}$
4. Luați în considerare un proces aleatoriu în care un set este ales cu fiecare element în a fi inclus în mod independent de probabilitate . Apoi următoarea inegalitate este adevărată unde este setul gol. În general, luați în considerare următorul proces aleatoriu în care un set este construit după cum urmează. Pentru fiecare dintre construct prin includerea fiecărui element în mod independent în cu probabilitate . Mai mult decât atât . Atunci următoarea inegalitate este adevărată . ${\ 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 \ în R} A_ {i})}$

Probleme de optimizare

Funcțiile submodulare au proprietăți care sunt foarte asemănătoare cu funcțiile convexe și concave . Din acest motiv, o problemă de optimizare care se referă la optimizarea unei funcții convexe sau concavă poate fi, de asemenea, descrisă ca problema maximizării sau minimizării unei funcții submodulare supusă unor constrângeri.

Minimizarea funcției setului submodular

Cea mai simplă problemă de minimizare este de a găsi un set care minimizează o funcție submodulară; aceasta este problema necontrolată. Această problemă este calculabilă în timp (puternic) polinomial . Calculul tăieturii minime într-un grafic este un caz special al acestei probleme generale de minimizare. Cu toate acestea, adăugarea chiar și a unei constrângeri simple, cum ar fi o limită inferioară a cardinalității, face ca problema de minimizare să fie dificilă , cu limite polimerice inferioare ale factorului de aproximare. ${\ displaystyle S \ subseteq \ Omega}$

Maximizarea funcției setului submodular

Spre deosebire de cazul minimizării, maximizarea funcțiilor submodulare este NP-hard chiar și în condiții fără restricții. Algoritmi de teorie și enumerare pentru găsirea maximelor (minime) locale și globale ale funcțiilor submodulare (supermodulare) pot fi găsite în B. Goldengorin. European Journal of Operational Research 198 (1): 102-112, DOI: 10.1016 / j.ejor.2008.08.022. De exemplu, tăierea maximă este un caz special chiar și atunci când funcția este necesară doar pentru a fi negativă. Problema fără restricții poate fi dovedită a fi inaproximabilă dacă se permite să fie negativă. Au existat lucrări ample privind maximizarea funcției submodulare constrânse atunci când funcțiile sunt non-negative. De obicei, algoritmii de aproximare pentru aceste probleme se bazează fie pe algoritmi lacome sau algoritmi de căutare locale . Problema maximizării unei funcții submodulare simetrice non-negative admite un algoritm de aproximare 1/2. Calculul tăieturii maxime a unui grafic este un caz special al acestei probleme. Problema mai generală a maximizării unei funcții submodulare non-negative admite, de asemenea, un algoritm de aproximare 1/2. Problema maximizării unei funcții submodulare monotone supuse unei constrângeri de cardinalitate admite un algoritm de aproximare. Problema de acoperire maximă este un caz special al acestei probleme. Problema mai generală a maximizării unei funcții submodulare monotone supuse unei constrângeri matroid admite, de asemenea, un algoritm de aproximare. Mulți dintre acești algoritmi pot fi uniți într-un cadru semi-diferențial de algoritmi. ${\ displaystyle 1-1 / e}$${\ displaystyle 1-1 / e}$

Probleme legate de optimizare

În afară de minimizarea și maximizarea submodulară, o altă problemă naturală este Diferența optimizării submodulare. Din păcate, această problemă nu este doar NP dură, ci și inaproximabilă. O problemă de optimizare legată este de a minimiza sau de a maximiza o funcție submodulară, supusă unei constrângeri de nivel submodular (numită și optimizare submodulară supusă unei acoperiri submodulare sau a unei constrângeri a rucsacului submodular). Această problemă admite garanții de aproximare mărginite. O altă problemă de optimizare implică partiționarea datelor pe baza unei funcții submodulare, astfel încât să maximizăm bunăstarea medie. Această problemă se numește problema bunăstării submodulare.

Aplicații

Funcțiile submodulare apar în mod natural în mai multe aplicații din lumea reală, în economie , teoria jocurilor , învățarea automată și viziunea computerizată . Datorită diminuării proprietății de returnare, funcțiile submodulare modelează în mod natural costurile articolelor, deoarece există adesea o reducere mai mare, cu o creștere a articolelor cumpărate. Funcțiile submodulare modelează noțiuni de complexitate, similitudine și cooperare atunci când apar în probleme de minimizare. Pe de altă parte, în problemele de maximizare, ele modelează noțiuni de diversitate, informații și acoperire. Pentru mai multe informații despre aplicațiile submodularității, în special în învățarea automată, a se vedea

Vezi si

• Funcția supermodulară
• Matroid , Polymatroid
• Funcții de utilitate pe bunuri indivizibile

Citații

Referințe

• Schrijver, Alexander (2003), Optimizare combinatorie , Springer , ISBN   3-540-44389-4
• Lee, Jon (2004), Un prim curs de optimizare combinatorie , Cambridge University Press , ISBN   0-521-01012-8
• Fujishige, Satoru (2005), Submodular Functions and Optimization , Elsevier , ISBN   0-444-52086-4
• Narayanan, H. (1997), Submodular Functions and Electrical Networks , ISBN   0-444-82523-1
• Oxley, James G. (1992), Teoria Matroid , Oxford Science Publications, Oxford: Oxford University Press , ISBN   0-19-853563-5 , Zbl   0784.05002

linkuri externe

• http://www.cs.berkeley.edu/~stefje/references.html are o bibliografie mai lungă