Machine Learning Work Shop - Why Submodularity is Important to Machine Learning
25Machine Learning Work Shop - Session 2 - Jeff Bilmes - 'Why Submodularity is Important to Machine Learning' It is well known that submodular functions have a set of tight subdifferentials. It is not well known that they also have tight superdifferentials, some of which are easy to obtain. In this talk, we'll survey some recent problems that have utilized superdifferentials in their efficient solution. This includes certain algorithms for the cooperative cut problem, new algorithms for minimizing the difference between submodular functions, and Bregman-like divergences on vertices of the hypercube. In each case, we see how the above can address machine learning applications in computer vision, probabilistic inference, and clustering.