Reductions in Pseudo-Boolean Optimization

This post is about reduction methods in pseudo-Boolean optimization and a recent paper to appear at CVPR 2011.

1. Problem formulation

Consider a pseudo-Boolean function {f: \mathbf{B}^n \rightarrow \bf \mathbf{R}} where {\mathbf{B}=\{0,1\}} and suppose {f} is represented by a multilinear polynomial of the form

\displaystyle  	f(\boldsymbol{x}) = \sum_i a_ix_i + \sum_{i<j} a_{ij}x_ix_j + \sum_{i<j<k} a_{ijk}x_ix_jx_k + \ldots, \ \ \ \ \ (1)

of {\mathrm{degree}(f)=m}. An optimization problem commonly arising in computer vision and many other fields is to minimize {f}:

\displaystyle  \min_{\boldsymbol{x} \in \mathbf{B}^n} f(\boldsymbol{x}).  \ \ \ \ \ (2)

2. Reductions

If {m=2}, one standard method of solving (2) is using roof duality. It gives a lower bound of the optimal value and possibly also a partial assignment of variables.

If {m>2}, one can always employ reductions to obtain an equivalent quadratic problem with additional variables. One possible reduction is

\displaystyle  	-x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3).

There are other possibilities, for example,

\displaystyle  	-x_1x_2x_3=\min_{z\in\mathbf{B}}z(-x_1+x_2+x_3)-x_1x_2-x_1x_3+x_1.

Different reductions lead to different results. Take for example the following cubic polynomial:

\displaystyle  	f(\boldsymbol{x})=-2x_1+x_2-x_3+4x_1x_2+4x_1x_3-2x_2x_3-2x_1x_2x_3.

Using the first reduction followed by roof duality, we obtain a lower bound of -3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2 and the optimal assignment of every variable (which is {(0,1,1)}).

3. Choosing between reductions

Andrew C. Gallagher, Dhruv Batra and Devi Parikh have a paper at the upcoming CVPR 2011 titled Inference for Order Reduction in Markov Random Fields, in which they try to choose between different possible reductions. They limit themselves to the case {m=3} and create a labeling problem in which each term of degree 3 is assigned one of many possible reductions. Since it does not seem to be possible to maximize, say, the number of labeled variables in the resulting quadratic problem, they minimize the “non-submodular magnitude”, which is the sum of the positive coefficients of the resulting quadratic polynomial. Solving (2) is then a two-step procedure:

  1. Solve the labeling problem which assigns each term of degree 3 one of many possible reductions.
  2. Perform the reductions and solve the resulting quadratic problems using roof duality.

Step 1 is generally a very difficult problem and can therefore only be solved approximately. Also, it is not completely clear that minimizing the “non-submodular magnitude” generally results in more labeled variables or a better lower bound on (2). But the authors perform several experiments which suggests that this approach works quite well.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s