Żądanie referencji: minimalizacja submodularna i monotoniczne funkcje boolowskie

Tło: W uczeniu maszynowym często pracujemy z modelami graficznymi reprezentującymi funkcje gęstości prawdopodobieństwa o wysokim wymiarze. Jeśli odrzucimy ograniczenie, które gęstość całkuje (sumuje) do 1, otrzymujemy nienormalizowaną funkcję energii o strukturze grafowej .

Załóżmy, że mamy taką funkcję energetyczną zdefiniowaną na wykresie . Na każdy wierzchołek wykresu przypada jedna zmienna oraz funkcje jednoargumentowe i wartościach rzeczywistych, i . Pełna energia jest wtedy$E$$G = (\mathcal{V}, \mathcal{E})$$x$$\theta_i(x_i) : i \in \mathcal{V}$$\theta_{ij}(x_i, x_j) : ij \in \mathcal{E}$

$$E(\mathbf{x}) = \sum_{i \in \mathcal{V}} \theta_i(x_i) + \sum_{ij \in \mathcal{E}} \theta_{ij}(x_i, x_j)$$

Jeśli wszystkie są binarne, możemy myśleć o jako o wskazaniu członkostwa w zestawie i tylko z niewielkim nadużyciem terminologii mówić o podmodelowości. W tym przypadku funkcją energii jest submodular iff . Zazwyczaj jesteśmy zainteresowani znalezieniem konfiguracji, która minimalizuje energię, .$x \in \mathbf{x}$$x$$\theta_{ij}(0, 0) + \theta_{ij}(1, 1) \le \theta_{ij}(0, 1) + \theta_{ij}(1, 0)$$\mathbf{x}^* = \arg \min_{\mathbf{x}} E(\mathbf{x})$

Wydaje się, że istnieje związek między minimalizowaniem funkcji energii podmodularnej a monotonicznymi funkcjami logicznymi: jeśli obniżymy energię niektórych \ theta_i (x_i = 1)$\theta_i(x_i=1)$ dla dowolnego $x_i$ (tj. Zwiększymy jego preferencję, aby była „prawdziwa”), wówczas optymalne przypisanie dowolnej zmiennej $x_i^* \in \mathbf{x}^*$ można zmienić tylko z 0 na 1 („fałsz” na „prawda”). Jeśli wszystkie $\theta_i$ są ograniczone do 0 lub 1, to mamy $|\mathcal{V}|$monotoniczne funkcje boolowskie:

$$f_i(\mathbf{\theta}) = x_i^*$$

gdzie jak wyżej, $\mathbf{x^*} = \arg \min_{\mathbf{x}} E(\mathbf{x})$ .

Pytanie: Czy możemy reprezentować wszystkie monotoniczne funkcje boolowskie przy użyciu tej konfiguracji, zmieniając pary par, ? Co jeśli pozwolimy być dowolną funkcją energii podmodularnej? I odwrotnie, czy możemy przedstawić wszystkie problemy minimalizacji podmodularnej jako zbiórmonotoniczne funkcje boolowskie?$\theta_{ij}$$E$$|\mathcal{V}|$

Czy możesz zasugerować referencje, które pomogą mi lepiej zrozumieć te połączenia? Nie jestem teoretycznym informatykiem, ale staram się zrozumieć, czy istnieją spostrzeżenia na temat monotonicznych funkcji boolowskich, które nie zostałyby uchwycone przez myślenie w warunkach submodularnej minimalizacji.

O ile rozumiem, przypadek minimalizacji podmodularnej przechwytuje wszystko, co można powiedzieć o monotonnym przypadku boolowskim, a binarne podmodularne funkcje boolowskie mogą wyrażać wszystkie podmodularne funkcje boolowskie. Jeśli jednak domena nie jest logiczna, binarne funkcje podmodularne nie wystarczą do wyrażenia wszystkich funkcji podmodularnych, nawet jeśli można wprowadzić ukryte zmienne. (Przepraszam, jeśli przeoczyłem subtelność w precyzyjnym sformułowaniu problemu.)

Stan techniki omówiono w tym ładnym artykule, który zawiera wiele linków do powiązanych prac, a także wyraźnie pokazuje linki do wizji komputerowej:

• Stanislav Živný, David A. Cohen, Peter G. Jeavons, Ekspresyjna moc binarnych funkcji submodularnych , DAM 157 3347–3358, 2009. doi: 10.1016 / j.dam.2009.07.001 ( preprint )

W przypadku, gdy twoje następne pytanie dotyczy przybliżenia, ten ostatni artykuł analizuje wersję przybliżenia:

• Dorit S. Hochbaum, Problemy submodularne - aproksymacje i algorytmy , arXiv: 1010.1945

Edycja: naprawiono link.