Computer Science – Learning
Scientific paper
2011-11-28
Computer Science
Learning
arXiv admin note: substantial text overlap with arXiv:1010.4207
Scientific paper
Submodular functions are relevant to machine learning for mainly two reasons: (1) some problems may be expressed directly as the optimization of submodular functions and (2) the Lovasz extension of submodular functions provides a useful set of regularization functions for supervised and unsupervised learning. In this paper, we present the theory of submodular functions from a convex analysis perspective, presenting tight links between certain polyhedra, combinatorial optimization and convex optimization problems. In particular, we show how submodular function minimization is equivalent to solving a wide variety of convex optimization problems. This allows the derivation of new efficient algorithms for approximate submodular function minimization with theoretical guarantees and good practical performance. By listing many examples of submodular functions, we review various applications to machine learning, such as clustering or subset selection, as well as a family of structured sparsity-inducing norms that can be derived and used from submodular functions.
No associations
LandOfFree
Learning with Submodular Functions: A Convex Optimization Perspective does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Learning with Submodular Functions: A Convex Optimization Perspective, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning with Submodular Functions: A Convex Optimization Perspective will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-67743