Submodular Point Processes with Applications to Machine Learning
Rishabh Iyer, Jeffrey A. Bilmes

Citation
Rishabh Iyer, Jeffrey A. Bilmes. "Submodular Point Processes with Applications to Machine Learning". International Conference on Artificial Intelligence and Statistics, 9, May, 2015.

Abstract
We introduce a class of discrete point processes that we call the Submodular Point Processes (SPPs). These processes are charac- terized via a submodular (or super modular) function, and naturally model notions of information, coverage and diversity, as well as cooperation. Unlike Log-submodular and Log-supermodular distributions (Log-SPPs) such as determinantal point processes (DPPs), SPPs are themselves submodular (or supermodular). In this paper, we analyze the computational complexity of probabilistic inference in SPPs. We show that computing the partition function for SPPs (and Log-SPPs), requires exponential complexity in the worst case, and also provide algorithms which approximate SPPs up to polynomial factors. Moreover, for several subclasses of interesting submodular functions that occur in applications, we show how we can provide efficient closed form expressions for the partition func- tions, and thereby marginals and conditional distributions. We also show how SPPs are closed under mixtures, thus enabling maximum likelihood based strategies for learning mixtures of submodular functions. Finally, we argue how SPPs complement existing Log- SPP distributions, and are a natural model for several applications.

Electronic downloads

Internal. This publication has been marked by the author for TerraSwarm-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Rishabh Iyer, Jeffrey A. Bilmes. <a
  href="http://www.terraswarm.org/pubs/493.html"
  >Submodular Point Processes with Applications to Machine
  Learning</a>, International Conference on Artificial
  Intelligence and Statistics, 9, May, 2015.

• Plain text

  Rishabh Iyer, Jeffrey A. Bilmes. "Submodular Point
  Processes with Applications to Machine Learning".
  International Conference on Artificial Intelligence and
  Statistics, 9, May, 2015.

• BibTeX

  @inproceedings{IyerBilmes15_SubmodularPointProcessesWithApplicationsToMachineLearning,
      author = {Rishabh Iyer and Jeffrey A. Bilmes},
      title = {Submodular Point Processes with Applications to
                Machine Learning},
      booktitle = {International Conference on Artificial
                Intelligence and Statistics},
      day = {9},
      month = {May},
      year = {2015},
      abstract = {We introduce a class of discrete point processes
                that we call the Submodular Point Processes
                (SPPs). These processes are charac- terized via a
                submodular (or super modular) function, and
                naturally model notions of information, coverage
                and diversity, as well as cooperation. Unlike
                Log-submodular and Log-supermodular distributions
                (Log-SPPs) such as determinantal point processes
                (DPPs), SPPs are themselves submodular (or
                supermodular). In this paper, we analyze the
                computational complexity of probabilistic
                inference in SPPs. We show that computing the
                partition function for SPPs (and Log-SPPs),
                requires exponential complexity in the worst case,
                and also provide algorithms which approximate SPPs
                up to polynomial factors. Moreover, for several
                subclasses of interesting submodular functions
                that occur in applications, we show how we can
                provide efficient closed form expressions for the
                partition func- tions, and thereby marginals and
                conditional distributions. We also show how SPPs
                are closed under mixtures, thus enabling maximum
                likelihood based strategies for learning mixtures
                of submodular functions. Finally, we argue how
                SPPs complement existing Log- SPP distributions,
                and are a natural model for several applications.},
      URL = {http://terraswarm.org/pubs/493.html}
  }
  

Posted by Barb Hoversten on 9 Feb 2015.
Groups: services