Submodulare Set-Funktion - Submodular set function

In der Mathematik ist eine submodulare Mengenfunktion (auch als submodulare Funktion bezeichnet ) eine Mengenfunktion, deren Wert informell die Eigenschaft hat, dass die Differenz des inkrementellen Werts der Funktion, die ein einzelnes Element beim Hinzufügen zu einer Eingabemenge macht, mit abnimmt Die Größe des Eingabesatzes nimmt zu. Submodulare Funktionen haben eine natürliche abnehmende Renditeeigenschaft , die sie für viele Anwendungen geeignet macht, einschließlich Approximationsalgorithmen , Spieltheorie (als Funktionen zur Modellierung von Benutzerpräferenzen) und elektrische Netzwerke . In jüngster Zeit haben submodulare Funktionen auch bei verschiedenen Problemen der realen Welt beim maschinellen Lernen und bei der künstlichen Intelligenz einen immensen Nutzen gefunden , einschließlich automatischer Zusammenfassung , Zusammenfassung mehrerer Dokumente , Merkmalsauswahl , aktivem Lernen , Sensorplatzierung, Zusammenfassung der Bildersammlung und vielen anderen Bereichen.

Definition

Wenn es sich um eine endliche Menge handelt , ist eine submodulare Funktion eine Mengenfunktion , wobei die Potenzmenge von bezeichnet wird , die eine der folgenden äquivalenten Bedingungen erfüllt. ${\ displaystyle \ Omega}$${\ displaystyle f: 2 ^ {\ Omega} \ rightarrow \ mathbb {R}}$${\ displaystyle 2 ^ {\ Omega}}$${\ displaystyle \ Omega}$

1. Für jeden mit und für jeden haben wir das . ${\ displaystyle X, Y \ subseteq \ Omega}$${\ displaystyle X \ subseteq Y}$${\ displaystyle x \ in \ Omega \ setminus Y}$${\ Anzeigestil f (X \ cup \ {x \}) - f (X) \ geq f (Y \ cup \ {x \}) - f (Y)}$
2. Für jeden haben wir das . ${\ displaystyle S, T \ subseteq \ Omega}$${\ Anzeigestil f (S) + f (T) \ geq f (S \ Tasse T) + f (S \ Kappe T)}$
3. Für jeden und so , dass wir das haben . ${\ 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)}$

Eine nichtnegative submodulare Funktion ist auch eine subadditive Funktion, aber eine subadditive Funktion muss nicht submodular sein. Wenn nicht endlich angenommen wird, sind die obigen Bedingungen nicht äquivalent. Insbesondere eine Funktion durch definiert ist, wenn endlich und wenn unendlich ist, erfüllt die erste Bedingung , oben, aber die zweite Bedingung nicht , wenn und unendliche Mengen mit endlicher Kreuzung sind. ${\ displaystyle \ Omega}$${\ displaystyle f}$${\ displaystyle f (S) = 1}$${\ displaystyle S}$${\ displaystyle f (S) = 0}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle T}$

Arten von submodularen Funktionen

Monoton

Eine submodulare Funktion ist monoton, wenn wir das für jeden haben . Beispiele für monotone submodulare Funktionen sind: ${\ displaystyle f}$${\ displaystyle T \ subseteq S}$${\ displaystyle f (T) \ leq f (S)}$

Lineare (modulare) Funktionen

Jede Funktion des Formulars wird als lineare Funktion bezeichnet. Zusätzlich, wenn dann f monoton ist. ${\ displaystyle f (S) = \ sum _ {i \ in S} w_ {i}}$${\ displaystyle \ forall i, w_ {i} \ geq 0}$

Budgetadditive Funktionen

Jede Funktion des Formulars für jedes und wird als Budgetadditiv bezeichnet. ${\ displaystyle f (S) = \ min \ left \ {B, ~ \ sum _ {i \ in S} w_ {i} \ right \}}$${\ displaystyle w_ {i} \ geq 0}$${\ displaystyle B \ geq 0}$

Abdeckungsfunktionen

Sei eine Sammlung von Teilmengen einer Grundmenge . Die Funktion für wird als Abdeckungsfunktion bezeichnet. Dies kann verallgemeinert werden, indem den Elementen nicht negative Gewichte hinzugefügt werden. ${\ 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

Sei eine Menge von Zufallsvariablen . Dann ist für jede, die wir haben, eine submodulare Funktion, wobei die Entropie der Menge von Zufallsvariablen ist , eine Tatsache, die als Shannons Ungleichung bekannt ist . Weitere Ungleichheiten für die Entropie - Funktion an Halt bekannt, siehe entropischen Vektor . ${\ displaystyle \ Omega = \ {X_ {1}, X_ {2}, \ ldots, X_ {n} \}}$${\ displaystyle S \ subseteq \ Omega}$${\ displaystyle H (S)}$${\ displaystyle H (S)}$${\ displaystyle S}$

Matroid Rang Funktionen

Sei der Grundsatz, auf dem eine Matroid definiert ist. Dann ist die Rangfunktion der Matroid eine submodulare Funktion. ${\ displaystyle \ Omega = \ {e_ {1}, e_ {2}, \ dots, e_ {n} \}}$

Nicht monoton

Eine nicht monotone submodulare Funktion wird als nicht monoton bezeichnet .

Symmetrisch

Eine nicht monotone submodulare Funktion heißt symmetrisch, wenn wir das für jede haben . Beispiele für symmetrische nicht monotone submodulare Funktionen sind: ${\ displaystyle f}$${\ displaystyle S \ subseteq \ Omega}$${\ displaystyle f (S) = f (\ Omega-S)}$

Grafikschnitte

Sei der Eckpunkt eines Graphen . Für jeden Satz von Eckpunkten bezeichnen wir die Anzahl der Kanten, so dass und . Dies kann verallgemeinert werden, indem den Kanten nicht negative Gewichte hinzugefügt werden. ${\ 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}$

Gegenseitige Information

Sei eine Menge von Zufallsvariablen . Dann ist für jeden, den wir haben, eine submodulare Funktion, wo die gegenseitige Information ist. ${\ 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)}$

Asymmetrisch

Eine nicht monotone submodulare Funktion, die nicht symmetrisch ist, wird als asymmetrisch bezeichnet.

Gerichtete Schnitte

Sei der Eckpunkt eines gerichteten Graphen . Geben Sie für jeden Satz von Eckpunkten die Anzahl der Kanten an, so dass und . Dies kann verallgemeinert werden, indem den gerichteten Kanten nicht negative Gewichte hinzugefügt werden. ${\ 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}$

Kontinuierliche Erweiterungen

Lovász Erweiterung

Diese Erweiterung ist nach dem Mathematiker László Lovász benannt . Betrachten Sie jeden Vektor so, dass jeder . Dann wird die Lovász-Erweiterung so definiert, dass die Erwartung aus der gleichmäßigen Verteilung des Intervalls übergewählt wird . Die Lovász-Erweiterung ist genau dann eine konvexe Funktion, wenn es sich um eine submodulare Funktion handelt. ${\ 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}$

Multilineare Verlängerung

Betrachten Sie jeden Vektor so, dass jeder . Dann wird die multilineare Erweiterung definiert als . ${\ 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})}$

Konvexer Verschluss

Betrachten Sie jeden Vektor so, dass jeder . Dann ist der konvexe Verschluss definiert als . Das konvexe Schließen einer festgelegten Funktion ist konvex . Es kann gezeigt werden, dass für submodulare Funktionen. ${\ 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})}$

Konkaver Verschluss

Betrachten Sie jeden Vektor so, dass jeder . Dann ist der konkave Verschluss definiert als . ${\ 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)}$

Eigenschaften

1. Die Klasse der submodularen Funktionen wird unter nicht negativen Linearkombinationen geschlossen . Berücksichtigen Sie alle submodularen Funktionen und nicht negativen Zahlen . Dann ist die durch definierte Funktion 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. Für jede submodulare Funktion ist die durch definierte Funktion submodular. ${\ displaystyle f}$${\ displaystyle g (S) = f (\ Omega \ setminus S)}$
3. Die Funktion , bei der es sich um eine reelle Zahl handelt, ist immer dann submodular, wenn sie monoton submodular ist. Im Allgemeinen ist es für jede nicht abnehmende konkave Funktion submodular . ${\ displaystyle g (S) = \ min (f (S), c)}$${\ displaystyle c}$${\ displaystyle f}$${\ displaystyle g (S) = h (f (S))}$${\ displaystyle h}$
4. Betrachten wir einen Zufallsprozess , bei dem ein Satz mit jedem Element ausgewählt wird in eingeschlossen werden in mit Wahrscheinlichkeit unabhängig . Dann ist die folgende Ungleichung wahr, wo sich die leere Menge befindet. Betrachten Sie allgemeiner den folgenden zufälligen Prozess, bei dem eine Menge wie folgt aufgebaut ist. Für jedes Konstrukt, indem jedes Element mit Wahrscheinlichkeit unabhängig in eingeschlossen wird . Weiterhin lassen . Dann ist die folgende Ungleichung wahr . ${\ 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})}$

Optimierungsprobleme

Submodulare Funktionen haben Eigenschaften, die konvexen und konkaven Funktionen sehr ähnlich sind . Aus diesem Grund kann ein Optimierungsproblem, das die Optimierung einer konvexen oder konkaven Funktion betrifft, auch als das Problem der Maximierung oder Minimierung einer submodularen Funktion unter bestimmten Einschränkungen beschrieben werden.

Minimierung der submodularen Satzfunktion

Das einfachste Minimierungsproblem besteht darin, eine Menge zu finden, die eine submodulare Funktion minimiert. Dies ist das uneingeschränkte Problem. Dieses Problem ist in (stark) polynomieller Zeit berechenbar . Die Berechnung des minimalen Schnitts in einem Diagramm ist ein Sonderfall dieses allgemeinen Minimierungsproblems. Das Hinzufügen selbst einer einfachen Einschränkung wie einer Kardinalitätsuntergrenze macht das Minimierungsproblem NP jedoch schwierig , wobei der Approximationsfaktor durch den Polynomfaktor niedriger begrenzt wird. ${\ displaystyle S \ subseteq \ Omega}$

Maximierung der submodularen Satzfunktion

Im Gegensatz zur Minimierung ist die Maximierung submodularer Funktionen selbst in der uneingeschränkten Umgebung NP-schwer . Theorie- und Aufzählungsalgorithmen zum Auffinden lokaler und globaler Maxima (Minima) submodularer (supermodularer) Funktionen finden sich in B. Goldengorin. European Journal of Operational Research 198 (1): 102-112, DOI: 10.1016 / j.ejor.2008.08.022. Zum Beispiel ist Max Cut ein Sonderfall, auch wenn die Funktion nur nicht negativ sein muss. Es kann gezeigt werden, dass das uneingeschränkte Problem nicht annähernd ist, wenn es negativ sein darf. Es wurden umfangreiche Arbeiten zur Maximierung eingeschränkter submodularer Funktionen durchgeführt, wenn die Funktionen nicht negativ sind. Typischerweise basieren die Approximationsalgorithmen für diese Probleme entweder auf gierigen Algorithmen oder auf lokalen Suchalgorithmen . Das Problem der Maximierung einer nicht negativen symmetrischen submodularen Funktion lässt einen 1/2 Approximationsalgorithmus zu. Die Berechnung des maximalen Schnitts eines Diagramms ist ein Sonderfall dieses Problems. Das allgemeinere Problem der Maximierung einer nicht negativen submodularen Funktion lässt auch einen 1/2 Approximationsalgorithmus zu. Das Problem der Maximierung einer monotonen submodularen Funktion, die einer Kardinalitätsbeschränkung unterliegt, lässt einen Approximationsalgorithmus zu. Das Problem der maximalen Abdeckung ist ein Sonderfall dieses Problems. Das allgemeinere Problem der Maximierung einer monotonen submodularen Funktion, die einer Matroid- Einschränkung unterliegt, lässt auch einen Approximationsalgorithmus zu. Viele dieser Algorithmen können in einem semi-differentiellen Framework von Algorithmen vereinheitlicht werden. ${\ displaystyle 1-1 / e}$${\ displaystyle 1-1 / e}$

Verwandte Optimierungsprobleme

Neben der submodularen Minimierung und Maximierung ist ein weiteres natürliches Problem der Unterschied der submodularen Optimierung. Leider ist dieses Problem nicht nur NP-schwer, sondern auch nicht annähernd. Ein verwandtes Optimierungsproblem ist das Minimieren oder Maximieren einer submodularen Funktion, die einer Submodular-Level-Set-Einschränkung unterliegt (auch als submodulare Optimierung bezeichnet, die einer submodularen Abdeckung oder einer submodularen Rucksack-Einschränkung unterliegt). Dieses Problem lässt begrenzte Annäherungsgarantien zu. Ein weiteres Optimierungsproblem besteht darin, Daten basierend auf einer submodularen Funktion zu partitionieren, um das durchschnittliche Wohlbefinden zu maximieren. Dieses Problem wird als submodulares Wohlfahrtsproblem bezeichnet.

Anwendungen

Submodulare Funktionen treten natürlich in verschiedenen realen Anwendungen auf, in den Bereichen Wirtschaft , Spieltheorie , maschinelles Lernen und Computer Vision . Aufgrund der abnehmenden Retoureneigenschaft modellieren submodulare Funktionen natürlich die Kosten von Artikeln, da häufig ein größerer Rabatt mit einer Erhöhung der gekauften Artikel besteht. Submodulare Funktionen modellieren Vorstellungen von Komplexität, Ähnlichkeit und Zusammenarbeit, wenn sie in Minimierungsproblemen auftreten. Bei Maximierungsproblemen hingegen modellieren sie Vorstellungen von Vielfalt, Information und Abdeckung. Weitere Informationen zu Anwendungen der Submodularität, insbesondere beim maschinellen Lernen, finden Sie unter

Siehe auch

• Supermodulare Funktion
• Matroid , Polymatroid
• Nutzenfunktionen für unteilbare Waren

Zitate

Verweise

• Schrijver, Alexander (2003), Kombinatorische Optimierung , Springer , ISBN   3-540-44389-4
• Lee, Jon (2004), Ein erster Kurs in kombinatorischer Optimierung , Cambridge University Press , ISBN   0-521-01012-8
• Fujishige, Satoru (2005), Submodulare Funktionen und Optimierung , Elsevier , ISBN   0-444-52086-4
• Narayanan, H. (1997), Submodular Functions and Electrical Networks , ISBN   0-444-82523-1
• Oxley, James G. (1992), Matroidentheorie , Oxford Science Publications, Oxford: Oxford University Press , ISBN   0-19-853563-5 , Zbl   0784.05002

Externe Links

• http://www.cs.berkeley.edu/~stefje/references.html hat eine längere Bibliographie