Demande de référence: minimisation submodulaire et fonctions booléennes monotones

Contexte: En apprentissage automatique, nous travaillons souvent avec des modèles graphiques pour représenter des fonctions de densité de probabilité dimensionnelle élevée. Si nous rejetons la contrainte qu'une densité intègre (somme) à 1, nous obtenons une fonction d'énergie structurée graphiquement non normalisée .

Supposons que nous ayons une telle fonction d'énergie, , définie sur un graphique G = ( V , E ) . Il y a une variable x pour chaque sommet du graphique, et il y a des fonctions unaires et par paires de valeur réelle, θ i ( x i ) : i ∈ V et θ i j ( x i , x j ) : i j ∈ E , respectivement. La pleine énergie est alors$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)$$

Si tous les sont binaires, nous pouvons penser à un x comme indiquant l'appartenance à un ensemble et avec juste un petit abus de terminologie, parler de sous-modularité. Dans ce cas, une fonction d'énergie est sous-modulaire si θ i j ( 0 , 0 ) + θ i j ( 1 , 1 ) ≤ θ i j ( 0 , 1 ) + θ i j ( 1 , 0 $x \in \mathbf{x}$$x$$\theta_{ij}(0, 0) + \theta_{ij}(1, 1) \le \theta_{ij}(0, 1) + \theta_{ij}(1, 0)$. Nous sommes généralement intéressés à trouver la configuration qui minimise l'énergie, .$\mathbf{x}^* = \arg \min_{\mathbf{x}} E(\mathbf{x})$

Il semble y avoir un lien entre la minimisation d'une fonction d'énergie sous-modulaire et les fonctions booléennes monotones: si nous diminuons l'énergie de certains pour tout x i (c.-à-d., Augmentons sa préférence pour qu'elle soit «vraie»), alors l'affectation optimale de toute variable x ∗ i ∈ x ∗ ne peut passer que de 0 à 1 ("faux" à "vrai"). Si tous les θ i sont restreints à 0 ou 1, alors nous avons | V | fonctions booléennes monotones:$\theta_i(x_i=1)$$x_i$$x_i^* \in \mathbf{x}^*$$\theta_i$$|\mathcal{V}|$

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

où comme ci-dessus, .$\mathbf{x^*} = \arg \min_{\mathbf{x}} E(\mathbf{x})$

Question: Peut-on représenter toutes les fonctions booléennes monotones en utilisant cette configuration en faisant varier les termes par paire, ? Et si nous permettons à E d'être une fonction d'énergie submodulaire arbitraire? Inversement, pouvons-nous représenter tous les problèmes de minimisation sous-modulaires comme un ensemble de | V | fonctions booléennes monotones?$\theta_{ij}$$E$$|\mathcal{V}|$

Pouvez-vous suggérer des références qui m'aideront à mieux comprendre ces liens? Je ne suis pas un informaticien théorique, mais j'essaie de comprendre s'il existe des informations sur les fonctions booléennes monotones qui ne sont pas capturées par la pensée en termes de minimisation submodulaire.

Pour autant que je sache, le cas de minimisation sous-modulaire capture tout ce qu'il y a à dire sur le cas booléen monotone, et les fonctions booléennes sous-modulaires binaires peuvent exprimer toutes les fonctions booléennes sous-modulaires. Cependant, si le domaine n'est pas booléen, les fonctions sous-modulaires binaires ne sont pas suffisantes pour exprimer toutes les fonctions sous-modulaires, même si des variables cachées peuvent être introduites. (Toutes mes excuses si j'ai manqué une subtilité dans la formulation précise de votre problème.)

L'état de l'art est discuté dans ce bel article qui a beaucoup de liens avec des travaux connexes, et qui rend également les liens avec la vision par ordinateur assez explicites:

• Stanislav Živný, David A. Cohen, Peter G. Jeavons, The expressive power of binary submodular functions , DAM 157 3347–3358, 2009. doi: 10.1016 / j.dam.2009.07.001 ( préimpression )

Dans le cas où votre prochaine question porte sur l'approximation, ce document récent examine la version d'approximation:

• Dorit S. Hochbaum, Problèmes sous - modulaires - approximations et algorithmes , arXiv: 1010.1945

Edit: lien fixe.