Sign inSign up
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees thumbnail
Pause
Mute
Subtitles
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees

Published on May 15, 20143242 Views

Pravesh Kothari

We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube {0,1}n. Our main result is the following structural th

COLT 2013 - Princeton

Related categories

Machine Learning

Chapter list

Representation, Approximation and Learning of Submodular Functions Using Low-Rank Decision Trees00:00
Submodular Functions - 100:15
Submodular Functions - 201:01
Learning Submodular Functions - 101:17
Learning Submodular Functions - 202:51
Learning Submodular Functions - 303:52
Learning Submodular Functions - 505:02
Learning Submodular Functions - 405:42
Learning Submodular Functions - 606:02
Learning Submodular Functions - 706:12
Learning Submodular Functions - 806:41
Learning Submodular Functions - 907:00
Learning Submodular Functions - 1007:18
Learning Submodular Functions - 1107:34
Learning Submodular Functions - 1208:17
Learning Submodular Functions - 1308:29
Learning Submodular Functions - 1409:08
Overview of Structural Results09:35
Representation of Submodular Functions10:19
Representing Submodular Functions by Decision Trees - 110:24
Representing Submodular Functions by Decision Trees - 211:05
Representing Submodular Functions by Decision Trees - 311:08
Rank of a Decision Tree - 111:13
Rank of a Decision Tree - 211:28
Our Results - 111:58
Our Results - 212:13
Representing Submodular Functions by DTs - 112:25
Representing Submodular Functions by DTs - 212:46
Representing Submodular Functions by DTs - 313:01
Representing Submodular Functions by DTs - 413:04
Representing Submodular Functions by DTs - 513:09
Representing Submodular Functions by DTs - 613:16
Representing Submodular Functions by DTs - 713:46
Approximating Submodular Functions14:05
Representing Submodular Functions by Decision Trees - 414:09
Approximating Submodular Functions - 114:15
Approximating Submodular Functions - 214:18
Our Results - 114:58
Our Results - 215:14
Our Results - 315:29
Our Results - 415:39
Our Results - 515:51
Our Results - 615:57
Our Results - 716:15
Our Results - 816:22
Learning16:33
Applications - 116:38
Applications - 217:03
Applications - 317:36
Our Results - 918:12
Our Results - 1018:39
Our Results - 1218:59
Our Results - 1119:07
Our Results - 1219:13
Summary19:19
Follow-Up Work19:28
Open Questions20:13
Questions?20:30