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

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

Related categories

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