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 Aug 09, 20135562 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
Chapter list
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