On Bisubmodular Maximization

Ajit P. Singh, Andrew Guillory, Jeff A. BilmesAISTATS 2012

Introduction

Submodular maximization has become a cornerstone of machine learning, providing a robust framework for tasks such as sensor placement, feature selection, and data summarization. These problems typically involve selecting a single subset of items from a ground set to maximize a function exhibiting diminishing returns. However, many real-world scenarios require partitioning elements into multiple distinct categories. This paper, presented at AISTATS 2012 by Singh, Guillory, and Bilmes, extends the principles of submodularity to bisubmodular functions, which involve selecting and partitioning elements into two disjoint sets.

Problem Formulation

Standard submodularity handles a single set $S \subseteq V$. In contrast, a bisubmodular function $f(A, B)$ operates on two disjoint sets $A, B \subseteq V$, where $A \cap B = \emptyset$. This structure is essential for "coupled" decision-making problems:

  • Coupled Sensor Placement: Allocating a budget between two types of sensors (e.g., high-range vs. low-range) to maximize total coverage.
  • Coupled Feature Selection: Selecting features to simultaneously predict two different target variables, where features may have varying utility for each task but share a common resource constraint.
Graphical representation of a coupled selection problem where nodes are partitioned into sets A and B to maximize information about target variables.

While bisubmodular minimization was previously well-understood, maximization remained an open challenge due to the complex interactions between the two sets.

Methodology: Reduction to Submodular Maximization

The authors' primary contribution is a reduction technique that transforms bisubmodular maximization into standard submodular maximization.

The Doubled Ground Set

For a class of "simple" bisubmodular functions—where fixing one set results in a submodular function in the other—the authors prove a reduction to a doubled ground set. Specifically, a function $f(A, B)$ over $V$ can be mapped to a standard submodular function $g(S)$ over an extended set $\bar{V}$ containing two copies of every element in $V$. This allows the application of well-known greedy algorithms, such as the $(1 - 1/e)$ approximation algorithm, to solve biset problems efficiently.

Theoretical Extensions

For more complex "directed" bisubmodular functions, the paper introduces a "Submodular Extension" theorem. This theorem demonstrates that submodular functions defined only on the independent sets of a matroid can be extended to the entire power set. This provides a theoretical bridge for solving constrained biset problems that were previously intractable.

Experimental Evaluation

The approach was validated using two primary setups:

  1. Sensor Placement Grid: A $50 \times 50$ floor plan simulation where two types of sensors with different radii and costs were placed to maximize coverage.
  2. Gaussian Graphical Models: Synthetic feature selection problems involving 20 features, aimed at maximizing mutual information for two target variables.

Key Results

The experiments demonstrated that the proposed "FastJoint" reduction algorithm significantly outperforms traditional coordinate-wise maximization (which alternates between optimizing $A$ and $B$).

Comparison of the FastJoint reduction algorithm against the slower coordinate-wise approach (SlowJoint), showing superior objective values and efficiency.

In sensor placement tasks, the mixed-sensor approach (enabled by bisubmodular optimization) consistently achieved higher coverage than using only one sensor type. For instance, in specific layouts, the bisubmodular approach reached 100% of the best-found coverage, while single-type baselines lagged at approximately 82%. Furthermore, the "FastJoint" algorithm proved to be approximately optimal, whereas the coordinate-wise "SlowJoint" approach lacks such theoretical guarantees for disjoint sets.

Conclusion

This work provides the first constant-factor approximation algorithms for a wide class of bisubmodular maximization problems. By leveraging a doubled ground set reduction, the authors enable the use of mature submodular optimization tools for complex partitioning tasks. Future research directions include extending these techniques to "multiset" functions involving more than two partitions and addressing the computational complexity of testing for monotone extensions in directed functions.

Summary updated

BibTeX
@article{singh2012bisubmodular,
  author = {Ajit P. Singh and Andrew Guillory and Jeff A. Bilmes},
  title = {{On Bisubmodular Maximization}},
  journal = {AISTATS},
  year = {2012},
}
Figure