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

Submodular functions have been studied extensively in machine learning and\ndata mining. In particular, the optimization of submodular functions over the\ninteger lattice (integer submodular functions) has recently attracted much\ninterest, because this domain relates naturally to many practical problem\nsettings, such as multilabel graph cut, budget allocation and revenue\nmaximization with discrete assignments. In contrast, the use of these functions\nfor probabilistic modeling has received surprisingly little attention so far.\nIn this work, we firstly propose the Generalized Multilinear Extension, a\ncontinuous DR-submodular extension for integer submodular functions. We study\ncentral properties of this extension and formulate a new probabilistic model\nwhich is defined through integer submodular functions. Then, we introduce a\nblock-coordinate ascent algorithm to perform approximate inference for those\nclass of models. Finally, we demonstrate its effectiveness and viability on\nseveral real-world social connection graph datasets with integer submodular\nobjectives.\n