CMU高级机器学习非参数学习

Advanced Machine LearningNonparametric methodsEric XingLecture 2, August 10, 2009Reading:© Eric Xing @ CMU, 2006-2009Univariate prediction without using a model: good or bad?Nonparametric Classifier (Instance-based learning)Nonparametric density estimation K-nearest-neighbor classifier Optimality of kNNSpectrum clusteringClustering Graph partition and normalized cut The spectral clustering algorithmVery little “learning” is involved in these methods© Eric Xing @ CMU, 2006-20091ClassificationRepresenting data:Hypothesis (classifier)© Eric Xing @ CMU, 2006-2009Clustering© Eric Xing @ CMU, 2006-20092Decision-making as dividing a high-dimensional spaceClassification-specific Dist.: P(X|Y)p ( X | Y = 1) r = p1 ( X ; µ1 , Σ1 )p ( X | Y = 2) r = p2 ( X ; µ2 , Σ2 )Class prior (i.e., "weight"): P(Y)© Eric Xing @ CMU, 2006-2009The Bayes RuleWhat we have just did leads to the following general expression:P(Y | X ) =P ( X | Y ) p (Y ) P( X )This is Bayes Rule© Eric Xing @ CMU, 2006-20093The Bayes Decision Rule for Minimum ErrorThe a posteriori probability of a sampleP(Y = i | X ) =π i pi ( X | Y = i ) p( X | Y = i ) P(Y = i ) = ≡ qi ( X ) p( X ) ∑i π i pi ( X | Y = i)Bayes Test:Likelihood Ratio:l( X ) =Discriminant function:h( X ) =© Eric Xing @ CMU, 2006-2009Example of Decision RulesWhen each class is a normal …We can write the decision boundary analytically in some cases … homework!!© Eric Xing @ CMU, 2006-20094Bayes ErrorWe must calculate the probability of errorthe probability that a sample is assigned to the wrong classGiven a datum X, what is the risk?The Bayes error (the expected risk):© Eric Xing @ CMU, 2006-2009More on Bayes ErrorBayes error is the lower bound of probability of classification errorBayes classifier is the theoretically best classifier that minimize probability of classification error Computing Bayes error is in general a very complex problem. Why?Density estimation: Integrating density function:© Eric Xing @ CMU, 2006-20095Learning ClassifierThe decision rule:Learning strategiesGenerative Learning Discriminative Learning Instance-based Learning (Store all past experience in memory)A special case of nonparametric classifier© Eric Xing @ CMU, 2006-2009Supervised LearningK-Nearest-Neighbor Classifier:where the h(X) is represented by all the data, and by an algorithm© Eric Xing @ CMU, 2006-20096Recall: Vector Space RepresentationEach document is a vector, one component for each term (= word).Doc 1Word 1 Word 2 Word 3Doc 2 0 8 1 1 0Doc 3 0 1 10 3 0... ... ... ... ... ...3 0 12 0 0... ...Normalize to unit length. High-dimensional vector space:Terms are axes, 10,000+ dimensions, or even 100,000+ Docs are vectors in this space© Eric Xing @ CMU, 2006-2009Classes in a Vector SpaceSports Science Arts© Eric Xing @ CMU, 2006-20097Test Document = ?Sports Science Arts© Eric Xing @ CMU, 2006-2009K-Nearest Neighbor (kNN) classifierVoting kNNSports Science Arts© Eric Xing @ CMU, 2006-20098kNN Is Close to OptimalCover and Hart 1967 Asymptotically, the error rate of 1-nearest-neighbor classification is less than twice the Bayes rate [error rate ofclassifier knowing model that generated data]In particular, asymptotic error rate is 0 if Bayes rate is 0. Where does kNN come from?Nonparametric density estimation© Eric Xing @ CMU, 2006-2009Nearest-Neighbor Learning AlgorithmLearning is just storing the representations of the training examples in D. Testing instance x:Compute similarity between x and all examples in D. Assign x the category of the most similar example in D.Does not explicitly compute a generalization or category prototypes. Also called:Case-based learning Memory-based learning Lazy learning© Eric Xing @ CMU, 2006-20099kNN is an instance of Instance-Based LearningWhat makes an Instance-Based Learner?A distance metricHow many nearby neighbors to look at?A weighting function (optional)How to relate to the local points?© Eric Xing @ CMU, 2006-2009Euclidean Distance MetricD ( x, x ' ) =Or equivalently,∑σi2 i( xi − xi ' )2D ( x, x ' ) = ( x − x ' )T Σ( x − x ' )Other metrics:L1 norm: |x-x'| L∞ norm: max |x-x'| (elementwise …) Mahalanobis: where Σ is full, and symmetric Correlation Angle Hamming distance, Manhattan distance …© Eric Xing @ CMU, 2006-200910Case Study: kNN for Web ClassificationDataset20 News Groups (20 classes) Download :(/jrennie/20Newsgroups/) 61,118 words, 18,774 documents Class labels descriptions© Eric Xing @ CMU, 2006-2008 © Eric Xing @ CMU, 2006-2009Results: Binary ClassesAccuracyalt.atheism vs. comp.graphics rec.autos vs. rec.sport.baseball comp.windows.x vs. rec.motorcyclesk© Eric Xing @ CMU, 2006-2009 2006-200811Results: Multiple ClassesRandom select 5-out-of-20 classes, repeat 10 runs and averageAccuracyAll 20 classesk© Eric Xing @ CMU, 2006-2009 2006-2008Is kNN ideal?© Eric Xing @ CMU, 2006-200912Is kNN ideal? … more later© Eric Xing @ CMU, 2006-2009Effect of ParametersSample sizeThe more the better Need efficient search algorithm for NNDimensionalityCurse of dimensionalityDensityHow smooth?MetricThe relative scalings in the distance metric affect region shapes.WeightSpurious or less relevant points need to be downweightedK© Eric Xing @ CMU, 2006-200913Clustering© Eric Xing @ CMU, 2006-2009Data ClusteringTwo different criteriaCompactness, e.g., k-means, mixture models Connectivity, e.g., spectral clusteringCompactness© Eric Xing @ CMU, 2006-2009Connectivity14Graph-based ClusteringData GroupingiWijjWijWij = f (d ( xi , x j ))G = {V,E}Image sigmentationW = [ wi , j ] Degree matrix: D = diag (d i ) Laplacian matrix: L = D − WAffinity matrix: (bipartite) partition vector:x = [ x1 ,...,x N ] = [1,1,K1,−1,−1, K − 1]© Eric Xing @ CMU, 2006-2009Affinity Function− Xi −X2 j 2Wi , j = eσ2Affinities grow as σ grows How the choice of σ value affects the results? What would be the optimal choice for σ?© Eric Xing @ CMU, 2006-200915A Spectral Clustering AlgorithmNg, Jordan, and Weiss 2003Given a set of points S={s1,…sn}− Si − S j2 2Form the affinity matrixwi , j = eσ2,∀i ≠ j ,wi ,i = 0Define diagonal matrix Dii= Σκ aik Form the matrixL = D −1 / 2WD −1 / 2| | ⎤ ⎡| ⎢x x L x ⎥ X =⎢ 1 2 k⎥ ⎢| | | ⎥ ⎣ ⎦Stack the k largest eigenvectors of L to for the columns of the new matrix X:Renormalize each of X’s rows to have unit length and get new matrix Y. Cluster rows of Y as points in R k© Eric Xing @ CMU, 2006-2009Why it works?K-means in the spectrum space !© Eric Xing @ CMU, 2006-200916More formally …Spectral clustering is equivalent to minimizing a generalized normalized cutk ⎛ cut ( Ar , Ar ) ⎞ ⎟ min Ncut( A1 , A2 K Ak ) = ∑ ⎜ ⎜ ⎟ d Ar r =1 ⎝ ⎠segmentsmin Y DT−1 / 2 TWD−1 / 2Ypixelss.t. Y Y = IY© Eric Xing @ CMU, 2006-2009Toy examplesImages from Matthew Brand (TR-2002-42)© Eric Xing @ CMU, 2006-200917Spectral ClusteringAlgorithms that cluster points using eigenvectors of matrices derived from the data Obtain data representation in the low-dimensional space that can be easily clustered Variety of methods that use the eigenvectors differently (we have seen an example) Empirically very successful Authors disagree:Which eigenvectors to use How to derive clusters from these eigenvectors© Eric Xing @ CMU, 2006-2009SummaryTwo nonparametric methods:kNN classifier Spectrum clusteringA nonparametric method does not rely on any assumption concerning the structure of the underlying density function.Good news:Simple and powerful methods; Flexible and easy to apply to many problems. kNN classifier asymptotically approaches the Bayes classifier, which is theoretically the best classifier that minimizes the probability of classification error. Spectrum clustering optimizes the normalized cutBad news:High memory requirements Very dependant on the scale factor for a specific problem.© Eric Xing @ CMU, 2006-200918。