| The central thesis of this dissertation is that a number of problems in machine learning can be reduced to submodular function minimization. The role of submodularity in combinatorial optimization and economics has been widely recognized and exploited. In combinatorial optimization, submodular functions play a role similar to that of convex functions in continuous optimization. It is generally accepted that the tractability of many combinatorial optimization problems, such as network flows, graph cuts, and minimum spanning trees, arises from the submodularity (or matroidal structure) inherent in them. Submodular functions also arise naturally in economics because they capture notions such as economies of scale and diminishing returns, and hence are useful for modeling concepts such as costs, utility functions and the core of convex games.; While submodularity also arises naturally (and frequently) in applications in machine learning, its presence here has not been as widely recognized. Information theoretic concepts like entropy and mutual information are in fact submodular functions and are widely used in machine learning applications. It is therefore, natural to expect that results from the theory of submodular functions can be used to attack both theoretical and practical issues that arise in machine learning applications. In this dissertation it is shown that submodular function minimization can be used to resolve some outstanding issues in PAC learning the structure of graphical models and in clustering. |
