ABSTRACT
Many problems in machine learning and its applications are, at their core, subset selection problems. Probabilistic models for such scenarios rely on having sufficiently accurate yet tractable distributions over discrete sets. We focus on sub-families of such distributions whose special mathematical properties are the basis for fast algorithms. For example, many problems may be viewed through the lens of submodular set functions, whose close connections to convexity offer, as we will see, not only practical algorithms for exact optimization, but also for approximate inference. Another example are Determinantal Point Processes that have recently become popular in machine learning, as elegant and tractable probabilistic models of diversity. In this talk, I will introduce these two concepts, and outline applications in machine learning and algorithmic ideas that connect the two, leading to practical algorithms for sampling and inference.