Introduction to Machine Learning 67577 - Fall, 2008 arXiv:0904.3664v1 [cs.LG] 23 Apr 2009 Amnon Shashua School of Computer Science and Engineering The Hebrew University of Jerusalem Jerusalem, Israel Contents 1 Bayesian Decision Theory 1.1 Independence Constraints 1.1.1 Example: Coin Toss 1.1.2 Example: Gaussian Density Estimation 1.2 Incremental Bayes Classifier 1.3 Bayes Classifier for 2-class Normal Distributions 2 Maximum Likelihood/ Maximum Entropy Duality 2.1 ML and Empirical Distribution 2.2 Relative Entropy 2.3 Maximum Entropy and Duality ML/MaxEnt 3 EM Algorithm: ML over Mixture of Distributions 19 3.1 The EM Algorithm: General 21 3.2 EM with i.i.d. Data 24 3.3 Back to the Coins Example 24 3.4 Gaussian Mixture 26 3.5 Application Examples 27 3.5.1 Gaussian Mixture and Clustering 27 3.5.2 Multinomial Mixture and ”bag of words” Application 27 4 Support Vector Machines and Kernel Functions 30 4.1 Large Margin Classifier as a Quadratic Linear Programming 31 4.2 The Support Vector Machine 34 4.3 The Kernel Trick 36 4.3.1 The Homogeneous Polynomial Kernel 37 4.3.2 The non-homogeneous Polynomial Kernel 38 4.3.3 The RBF Kernel 39 4.3.4 Classifying New Instances 39 iii page 1 5 7 7 9 10 12 12 14 15 iv Contents 5 Spectral Analysis I: PCA, LDA, CCA 5.1 PCA: Statistical Perspective 5.1.1 Maximizing the Variance of Output Coordinates 5.1.2 Decorrelation: Diagonalization of the Covariance Matrix 5.2 PCA: Optimal Reconstruction 5.3 The Case n >> m 5.4 Kernel PCA 5.5 Fisher’s LDA: Basic Idea 5.6 Fisher’s LDA: General Derivation 5.7 Fisher’s LDA: 2-class 5.8 LDA versus SVM 5.9 Canonical Correlation Analysis 41 42 43 6 Spectral Analysis II: Clustering 6.1 K-means Algorithm for Clustering 6.1.1 Matrix Formulation of K-means 6.2 Min-Cut 6.3 Spectral Clustering: Ratio-Cuts and Normalized-Cuts 6.3.1 Ratio-Cuts 6.3.2 Normalized-Cuts 58 59 60 62 63 64 65 7 The Formal (PAC) Learning Model 7.1 The Formal Model 7.2 The Rectangle Learning Problem 7.3 Learnabili