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
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ę, .
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) dla dowolnego (tj. Zwiększymy jego preferencję, aby była „prawdziwa”), wówczas optymalne przypisanie dowolnej zmiennej można zmienić tylko z 0 na 1 („fałsz” na „prawda”). Jeśli wszystkie są ograniczone do 0 lub 1, to mamy monotoniczne funkcje boolowskie:
gdzie jak wyżej, .
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?
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.