<p>As far as I understand, the submodular minimization case captures all there is to be said about the monotone Boolean case, and binary submodular Boolean functions can express all submodular Boolean functions.  However, if the domain is non-Boolean, then binary submodular functions are not enough to express all submodular functions, even if hidden variables may be introduced.  (Apologies if I have missed a subtlety in your precise problem phrasing.)</p>

<p>The state of the art is discussed in this nice paper which has lots of links to related work, and that also makes the links to computer vision quite explicit:</p>

<ul>
<li>Stanislav Živný, David A. Cohen, Peter G. Jeavons, <em>The expressive power of binary submodular functions</em>, DAM <strong>157</strong> 3347–3358, 2009.  doi: <a href="http://dx.doi.org/10.1016/j.dam.2009.07.001">10.1016/j.dam.2009.07.001</a> (<a href="http://zivny.cz/publications/zcj09dam-preprint.pdf">preprint</a>)</li>
</ul>

<p>In case your next question is about approximation, this recent paper looks at the approximation version:</p>

<ul>
<li>Dorit S. Hochbaum, <em>Submodular problems - approximations and algorithms</em>, arXiv: <a href="http://arxiv.org/abs/1010.1945">1010.1945</a></li>
</ul>

<p><em>Edit:</em> fixed link.</p>

CC BY-SA 2.5
2010-10-19T15:28:02.953Z
Although the (preprint) link takes me to a different paper than the doi: link does.
dan_x
CC BY-SA 2.5
2010-10-19T15:51:52.847Z
@dan x: fixed the link, thanks for the heads-up.
András Salamon
CC BY-SA 2.5
2010-10-19T15:15:17.770Z
2010-10-19T15:33:46.870Z
2010-10-19T15:33:46.870Z
András Salamon
<p><strong>Background:</strong> In machine learning, we often work with <em>graphical models</em> to represent high dimensional probability density functions.  If we discard the constraint that a density integrates (sums) to 1, we get an unnormalized <em>graph-structured energy function</em>.</p>

<p>Suppose we have such an energy function, $E$, defined on a graph $G = (\mathcal{V}, \mathcal{E})$.  There is one variable $x$ for each vertex of the graph, and there are real-valued unary and pairwise functions, $\theta_i(x_i) : i \in \mathcal{V}$ and $\theta_{ij}(x_i, x_j) : ij \in \mathcal{E}$, respectively.  The full energy is then</p>

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

<p>If all $x \in \mathbf{x}$ are binary, we can think of an $x$ as indicating set membership and with just a small abuse of terminology talk about submodularity.  In this case, an energy function is submodular iff $\theta_{ij}(0, 0) + \theta_{ij}(1, 1) \le \theta_{ij}(0, 1) + \theta_{ij}(1, 0)$.  We are typically interested in finding the configuration that minimizes the energy, $\mathbf{x}^* = \arg \min_{\mathbf{x}} E(\mathbf{x})$.</p>

<p>There seems to be a connection between minimizing a submodular energy function and monotone boolean functions: if we lower the energy of some $\theta_i(x_i=1)$ for any $x_i$ (i.e., increase its preference to be "true"), then the optimal assignment of any variable $x_i^* \in \mathbf{x}^*$ can only change from 0 to 1 ("false" to "true").  If all $\theta_i$ are restricted to be either 0 or 1, then we have $|\mathcal{V}|$ monotone boolean functions:</p>

<p>$$f_i(\mathbf{\theta}) = x_i^*$$</p>

<p>where as above, $\mathbf{x^*} = \arg \min_{\mathbf{x}} E(\mathbf{x})$.</p>

<p><strong>Question:</strong> Can we represent all monotone boolean functions using this setup by varying the pairwise terms, $\theta_{ij}$?  What if we allow $E$ to be an arbitrary submodular energy function?  Conversely, can we represent all submodular minimization problems as a set of $|\mathcal{V}|$ monotone boolean functions?</p>

<p>Can you suggest references that will help me towards better understanding these connections?  I'm not a theoretical computer scientist, but I'm trying to understand if there are insights about monotone boolean functions that are not captured by thinking in the submodular minimization terms.</p>

<reference-request><machine-learning><lg.learning><boolean-functions>
Reference Request: Submodular Minimization and Monotone Boolean Functions
dan_x
# Reference Request: Submodular Minimization and Monotone Boolean Functions

(Asked by: username_0 on 2010-10-19)

**Background:** In machine learning, we often work with *graphical models* to represent high dimensional probability density functions. If we discard the constraint that a density integrates (sums) to 1, we get an unnormalized *graph-structured energy function*.

Suppose we have such an energy function, $E$, defined on a graph $G = (\mathcal{V}, \mathcal{E})$. There is one variable $x$ for each vertex of the graph, and there are real-valued unary and pairwise functions, $\theta\_i(x\_i) : i \in \mathcal{V}$ and $\theta\_{ij}(x\_i, x\_j) : ij \in \mathcal{E}$, respectively. The full energy is then

$$E(\mathbf{x}) = \sum\_{i \in \mathcal{V}} \theta\_i(x\_i) + \sum\_{ij \in \mathcal{E}} \theta\_{ij}(x\_i, x\_j)$$

If all $x \in \mathbf{x}$ are binary, we can think of an $x$ as indicating set membership and with just a small abuse of terminology talk about submodularity. In this case, an energy function is submodular iff $\theta\_{ij}(0, 0) + \theta\_{ij}(1, 1) \le \theta\_{ij}(0, 1) + \theta\_{ij}(1, 0)$. We are typically interested in finding the configuration that minimizes the energy, $\mathbf{x}^\* = \arg \min\_{\mathbf{x}} E(\mathbf{x})$.

There seems to be a connection between minimizing a submodular energy function and monotone boolean functions: if we lower the energy of some $\theta\_i(x\_i=1)$ for any $x\_i$ (i.e., increase its preference to be "true"), then the optimal assignment of any variable $x\_i^\* \in \mathbf{x}^\*$ can only change from 0 to 1 ("false" to "true"). If all $\theta\_i$ are restricted to be either 0 or 1, then we have $|\mathcal{V}|$ monotone boolean functions:

$$f\_i(\mathbf{\theta}) = x\_i^\*$$

where as above, $\mathbf{x^\*} = \arg \min\_{\mathbf{x}} E(\mathbf{x})$.

**Question:** Can we represent all monotone boolean functions using this setup by varying the pairwise terms, $\theta\_{ij}$? What if we allow $E$ to be an arbitrary submodular energy function? Conversely, can we represent all submodular minimization problems as a set of $|\mathcal{V}|$ monotone boolean functions?

Can you suggest references that will help me towards better understanding these connections? I'm not a theoretical computer scientist, but I'm trying to understand if there are insights about monotone boolean functions that are not captured by thinking in the submodular minimization terms.

**Tags:** reference-request, machine-learning, lg.learning, boolean-functions

---

## 1 answers

### Answer by username_1 on 2010-10-19. Score: 7 | Accepted answer

As far as I understand, the submodular minimization case captures all there is to be said about the monotone Boolean case, and binary submodular Boolean functions can express all submodular Boolean functions. However, if the domain is non-Boolean, then binary submodular functions are not enough to express all submodular functions, even if hidden variables may be introduced. (Apologies if I have missed a subtlety in your precise problem phrasing.)

The state of the art is discussed in this nice paper which has lots of links to related work, and that also makes the links to computer vision quite explicit:

* 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](http://dx.doi.org/10.1016/j.dam.2009.07.001) ([preprint](http://zivny.cz/publications/zcj09dam-preprint.pdf))

In case your next question is about approximation, this recent paper looks at the approximation version:

* Dorit S. Hochbaum, *Submodular problems - approximations and algorithms*, arXiv: [1010.1945](http://arxiv.org/abs/1010.1945)

*Edit:* fixed link.

> **Comments:**
> **username_0**: Although the (preprint) link takes me to a different paper than the doi: link does.  
> **username_1**: @dan x: fixed the link, thanks for the heads-up.  

---

