From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models

Aytunc Sahin, Yatao Bian, Joachim Buhmann, Andreas Krause
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:8388-8397, 2020.

Abstract

Submodular functions have been studied extensively in machine learning and data mining. In particular, the optimization of submodular functions over the integer lattice (integer submodular functions) has recently attracted much interest, because this domain relates naturally to many practical problem settings, such as multilabel graph cut, budget allocation and revenue maximization with discrete assignments. In contrast, the use of these functions for probabilistic modeling has received surprisingly little attention so far. In this work, we firstly propose the Generalized Multilinear Extension, a continuous DR-submodular extension for integer submodular functions. We study central properties of this extension and formulate a new probabilistic model which is defined through integer submodular functions. Then, we introduce a block-coordinate ascent algorithm to perform approximate inference for this class of models and finally, we demonstrate its effectiveness and viability on several real-world social connection graph datasets with integer submodular objectives.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-sahin20a, title = {From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models}, author = {Sahin, Aytunc and Bian, Yatao and Buhmann, Joachim and Krause, Andreas}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {8388--8397}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/sahin20a/sahin20a.pdf}, url = {https://proceedings.mlr.press/v119/sahin20a.html}, abstract = {Submodular functions have been studied extensively in machine learning and data mining. In particular, the optimization of submodular functions over the integer lattice (integer submodular functions) has recently attracted much interest, because this domain relates naturally to many practical problem settings, such as multilabel graph cut, budget allocation and revenue maximization with discrete assignments. In contrast, the use of these functions for probabilistic modeling has received surprisingly little attention so far. In this work, we firstly propose the Generalized Multilinear Extension, a continuous DR-submodular extension for integer submodular functions. We study central properties of this extension and formulate a new probabilistic model which is defined through integer submodular functions. Then, we introduce a block-coordinate ascent algorithm to perform approximate inference for this class of models and finally, we demonstrate its effectiveness and viability on several real-world social connection graph datasets with integer submodular objectives.} }
Endnote
%0 Conference Paper %T From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models %A Aytunc Sahin %A Yatao Bian %A Joachim Buhmann %A Andreas Krause %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-sahin20a %I PMLR %P 8388--8397 %U https://proceedings.mlr.press/v119/sahin20a.html %V 119 %X Submodular functions have been studied extensively in machine learning and data mining. In particular, the optimization of submodular functions over the integer lattice (integer submodular functions) has recently attracted much interest, because this domain relates naturally to many practical problem settings, such as multilabel graph cut, budget allocation and revenue maximization with discrete assignments. In contrast, the use of these functions for probabilistic modeling has received surprisingly little attention so far. In this work, we firstly propose the Generalized Multilinear Extension, a continuous DR-submodular extension for integer submodular functions. We study central properties of this extension and formulate a new probabilistic model which is defined through integer submodular functions. Then, we introduce a block-coordinate ascent algorithm to perform approximate inference for this class of models and finally, we demonstrate its effectiveness and viability on several real-world social connection graph datasets with integer submodular objectives.
APA
Sahin, A., Bian, Y., Buhmann, J. & Krause, A.. (2020). From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:8388-8397 Available from https://proceedings.mlr.press/v119/sahin20a.html.

Related Material