机器学习的算法方面 Algorithmic Aspects of Machine Learning.pdf

Algorithmic Aspects of Machine Learning Ankur Moitra @ Draft date March 30 2014
Contents Contents Preface 1 1Introduction 3 2 Nonnegative Matrix Factorization 5 2.1 Introduction . 5 2.2 Algebraic Algorithms 10 2.3 Stability and Separability 15 2.4 Topic Models 19 3 Tensor Methods 25 3.1 Basics 25 3.2 Perturbation Bounds 30 3.3 Phylogenetic Trees and HMMs . 34 3.4Community Detection 40 3.5 Extensions to Mixed Models 44 3.6 Independent Component Analysis 50 4 Sparse Recovery 53 4.1 Basics 53 4.2 Uniqueness and Uncertainty Principles 56 4.3 Pursuit Algorithms 59
ii CONTENTS 4.4 Prony’s Method 61 4.5Compressed Sensing 9 5 Dictionary Learning 71 5.1 Background 71 5.2 Full Rank Dictionaries 5.3 Overplete Dictionaries 77 6 Gaussian Mixture Models 88 6.1 History. 88 6.2 Clustering-Based Algorithms . 86 6.3Discussion of Density Estimation 89 6.4 Clustering-Free Algorithms . 91 6.5 A Univariate Algorithm 96 6.6A View from Algebraic Geometry 101 7Matrix Completion 105 7.1 Background 105 7.2Nuclear Norm 107 7.3 Quantum Golfing 111 Bibliography 115
Preface The monograph is based on the class “18.S996: Algorithmic Aspects of Machine Learning" taught at MIT in Fall 2013. Thanks to the scribes Adam Hesterberg. Adrian Vladu Matt Coudron Jan-Christian Hitter Henry Yuen Yufei Zhao Hi- lary Finucane Matthew Johnson Kayhan Batmanghelich Gautam Kamath George Chen Pratiksha Thaker Mohammad Bavarian Vlad Firoiu Madalina Persu Cameron Musco Christopher Musco Jing Lin Timothy Chu Yin-Tat Lee Josh Alman Nathan Pinsker and Adam Bouland.
CONTENTS