Żądanie referencji: minimalizacja submodularna i monotoniczne funkcje boolowskie

13

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 wtedyEG=(V,E)xθi(xi):iVθij(xi,xj):ijE

E(x)=iVθi(xi)+ijEθij(xi,xj)

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ę, .xxxθij(0,0)+θij(1,1)θij(0,1)+θij(1,0)x=argminxE(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)θi(xi=1) dla dowolnego xi (tj. Zwiększymy jego preferencję, aby była „prawdziwa”), wówczas optymalne przypisanie dowolnej zmiennej xix można zmienić tylko z 0 na 1 („fałsz” na „prawda”). Jeśli wszystkie θi są ograniczone do 0 lub 1, to mamy |V|monotoniczne funkcje boolowskie:

fi(θ)=xi

gdzie jak wyżej, x=argminxE(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?θijE|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.

dan_x
źródło

Odpowiedzi:

7

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.

András Salamon
źródło
Chociaż link (preprint) zabiera mnie do innego artykułu niż doi: link.
dan_x,
@dan x: naprawiono link, dzięki za heads-up.
András Salamon,