0.25
0.5
0.75
1.25
1.5
1.75
2
Learning with Submodular Functions: A Convex Optimization Perspective
Published on Jan 25, 20127613 Views
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 su
Related categories
Chapter list
Learning with Submodular Functions: A Convex Optimization Perspective00:00
Convex optimization with combinatorial structure00:24
Outline - 101:35
Outline - 202:22
Submodular functions02:34
Submodular functions - Examples04:12
Submodular functions - Lovász extension04:40
Submodular functions - Submodular polyhedra - 106:32
Submodular functions - Submodular polyhedra - 207:58
Submodular functions - Optimization09:05
Separable optimization on base polyhedron09:52
From convex to combinatorial optimization and vice-versa...12:15
Outline - 313:39
Sparsity in supervised machine learning13:49
Sparsity in unsupervised machine learning14:45
Why structured sparsity? - 115:34
Structured sparse PCA - 116:03
Structured sparse PCA - 216:31
Structured sparse PCA - 316:48
Structured sparse PCA - 416:57
Why structured sparsity? - 217:16
Modelling of text corpora17:25
ℓ1-norm = convex envelope of cardinality of support17:49
Convex envelopes of general functions of the support (Bach, 2010)19:00
Submodular functions and structured sparsity - 119:54
Submodular functions and structured sparsity - 220:36
Polyhedral unit balls22:28
Submodular functions and structured sparsity - Examples - 122:37
Selection of contiguous patterns in a sequence24:45
Extensions of norms with overlapping groups25:47
Submodular functions and structured sparsity - Examples - 226:31
Unified optimization algorithms27:19
Comparison of optimization algorithms30:22
Extensions31:16
Polyhedral unit balls32:03
Outline - 433:08
Approximate submodular function minimization33:09
Approximate quadratic optimization on B(F) - 134:39
Conditional gradient with line search36:16
Approximate quadratic optimization on B(F) - 237:20
From quadratic optimization on B(F) to submodular function minimization38:38
Simulations on standard benchmark “DIMACS Genrmf-wide”, p = 57539:59
Simulations on standard benchmark40:02
Conclusion40:02