Constrained Interacting Submodular Groupings
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:10761085, 2018.
Abstract
We introduce the problem of grouping a finite ground set into blocks where each block is a subset of the ground set and where: (i) the blocks are individually highly valued by a submodular function (both robustly and in the average case) while satisfying blockspecific matroid constraints; and (ii) block scores interact where blocks are jointly scored highly, thus making the blocks mutually nonredundant. Submodular functions are good models of information and diversity; thus, the above can be seen as grouping the ground set into matroid constrained blocks that are both intra and interdiverse. Potential applications include forming ensembles of classification/regression models, partitioning data for parallel processing, and summarization. In the nonrobust case, we reduce the problem to nonmonotone submodular maximization subject to multiple matroid constraints. In the mixed robust/average case, we offer a bicriterion guarantee for a polynomial time deterministic algorithm and a probabilistic guarantee for randomized algorithm, as long as the involved submodular functions (including the interblock interaction terms) are monotone. We close with a case study in which we use these algorithms to find high quality diverse ensembles of classifiers, showing good results.
Related Material


