en-es
en
0.25
0.5
0.75
1.25
1.5
1.75
2
Is Intractability a Barrier for Machine Learning?
Published on 2013-08-095570 Views
One of the frustrations of machine learning theory is that many of the underlying algorithmic problems are provably intractable (e.g., NP-hard or worse) or presumed to be intractable (e.g., the many o
Related categories
Presentation
Is intractability a barrier for provable bounds in ML?00:00
A major paradigm in ML (unsupervised learning)00:40
Difficulty01:27
What NP-hardness means03:24
Our goal: “Provable bounds”07:40
Vignette 1:09:29
Nonnegative Matrix Factorization - 110:07
Nonnegative Matrix Factorization - 211:27
Nonnegative Matrix Factorization - 311:33
Intuition: noncancelling combinations12:37
New results for NMF - 114:03
New results for NMF - 214:38
New results for NMF - 317:38
New results for NMF - 418:20
Separable Factorization - 120:56
Separable Factorization - 221:04
Separable Factorization - 321:06
Separable Factorization - 421:33
Separable Factorization - 521:57
Separable Factorization - 622:04
Separable Factorization - 723:23
Separable Factorization - 823:24
Geometric restatement of NMF23:48
Finding Separable Factorization - 125:02
Finding Separable Factorization - 225:18
Finding Separable Factorization - 325:30
Finding Separable Factorization - 425:35
Finding Separable Factorization - 526:45
Application27:25
Learning Topic Models - 128:12
Learning Topic Models - 230:27
Latent DirichletAllocation - 130:48
Latent DirichletAllocation - 231:18
Status of Topic Model Learning31:19
The main difficulty (why LDA learning ≠ NMF) - 132:38
The main difficulty (why LDA learning ≠ NMF) - 233:41
Co-occurenceprobabilities33:45
LDA learning in Poly Time - 135:00
LDA learning in Poly Time - 235:38
LDA learning in Poly Time - 335:56
LDA learning in Poly Time - 436:20
Further thoughts36:51
Vignette 239:28
Supervised learning of binary classifier39:52
Our assumptions - 141:21
Our assumptions - 243:06
Why44:22
Open Problems46:03
Vignette 348:56
Suggested future directions…49:56
Deep learning: nonlinear, multistage coordinate change - 149:57
Deep learning: nonlinear, multistage coordinate change - 250:03
A complexity theory of avg.-case hard problems in ML?50:41
Inference problems on bayesnets51:26
Looking forward to many more provable bounds!52:04