Statistical Classification Rong Jin Classification Problems Input X f X Y Given Y Output input X x1 x2 xm Predict the class label y Y Y 1 1 binary class classification problems Y 1 2 3 c multiple class classification problems Goal need to learn the function f X Y Examples of Classification Problem Text categorization Doc Months of campaigning and weeks of round the clock efforts in Iowa all came down to a final push Sunday Topic Non politics Input features X Politics Word frequency campaigning 1 democrats 2 basketball 0 Class label y Y 1 politics Y 1 non politics Examples of Classification Problem Text categorization Doc Months of campaigning and weeks of round the clock efforts in Iowa all came down to a final push Sunday Topic Non politics Input features X Politics Word frequency campaigning 1 democrats 2 basketball 0 Class label y Y 1 politics Y 1 not politics Examples of Classification Problem Image Classification Which images are birds which are not Input features X Color histogram red 1004 red 23000 Class label y Y 1 bird image Y 1 non bird image Examples of Classification Problem Image Classification Which images are birds which are not Input features X Color histogram red 1004 blue 23000 Class label y Y 1 bird image Y 1 non bird image Classification Problems Input X f X Y Y Output Doc Months of campaigning and weeks of round the clock efforts in Iowa all came down to a final push Sunday f doc topic How to obtain f f image topic Politics Not politics Birds Not Birds Learn classification function f from examples Learning from Examples Training examples r r r Dtrain x1 y1 x2 y2 xn yn n the number of training examples r xi d xi 1 xi 2 xi d yi Y Binary class Y 1 1 Multiple class Y 1 2 c Identical Independent Distribution i i d Each training example is drawn independently from the identical source Training examples are similar to testing examples Learning from Examples Training examples r r r Dtrain x1 y1 x2 y2 xn yn n the number of training examples r xi d xi 1 xi 2 xi d yi Y Binary class Y 1 1 Multiple class Y 1 2 c Identical Independent Distribution i i d Each training example is drawn independently from the identical source Learning from Examples Given training examples r r r Dtrain x1 y1 x2 y2 xn yn Goal learn a classification function f x X Y that is consistent with training examples What is the easiest way to do it K Nearest Neighbor kNN Approach How many neighbors should we count k 1 k 4 Cross Validation Divide training examples into two sets A training set 80 and a validation set 20 Predict the class labels of the examples in the validation set by the examples in the training set Choose the number of neighbors k that maximizes the classification accuracy Leave One Out Method For k 1 2 K Err k 0 1 Randomly select a training data point and hide its class label 2 Using the remaining data and given K to predict the class label for the left data point 3 Err k Err k 1 if the predicted label is different from the true label Repeat the procedure until all training examples are tested Choose the k whose Err k is minimal Leave One Out Method For k 1 2 K Err k 0 1 Randomly select a training data point and hide its class label 2 Using the remaining data and given K to predict the class label for the left data point 3 Err k Err k 1 if the predicted label is different from the true label Repeat the procedure until all training examples are tested Choose the k whose Err k is minimal Leave One Out Method For k 1 2 K Err k 0 1 Randomly select a training data point and hide its class label 2 Using the remaining data and given k to predict the class label for the left data point 3 Err k Err k 1 if the predicted label is different from the true label k 1 Repeat the procedure until all training examples are tested Choose the k whose Err k is minimal Leave One Out Method For k 1 2 K Err k 0 1 Randomly select a training data point and hide its class label 2 Using the remaining data and given k to predict the class label for the left data point 3 Err k Err k 1 if the predicted label is different from the true label k 1 Err 1 1 Repeat the procedure until all training examples are tested Choose the k whose Err k is minimal Leave One Out Method For k 1 2 K Err k 0 1 Randomly select a training data point and hide its class label 2 Using the remaining data and given k to predict the class label for the left data point 3 Err k Err k 1 if the predicted label is different from the true label Err 1 1 Repeat the procedure until all training examples are tested Choose the k whose Err k is minimal Leave One Out Method For k 1 2 K Err k 0 1 Randomly select a training data point and hide its class label 2 Using the remaining data and given k to predict the class label for the left data point 3 Err k Err k 1 if the predicted label is different from the true label Err 1 3 k 2 Err 2 2 Err 3 6 Repeat the procedure until all training examples are tested Choose the k whose Err k is minimal Probabilistic interpretation of KNN Estimate the probability density function Pr y x around the location of x Count of data points in class y in the neighborhood of x Bias and variance tradeoff A small neighborhood large variance unreliable estimation A large neighborhood large bias inaccurate estimation Weighted kNN Weight the contribution of each close neighbor based on their distances Weight function 2 x xi 2 w x xi exp 2 2 Prediction i w x xi y yi Pr y x i w x xi 1 y yi 0 y yi y yi Estimate 2 in the Weight Function Leave one cross validation Training dataset D is divided into two sets Validation set x1 y1 Training set D 1 x2 y2 x3 y3 xn yn Compute the Pr y1 x1 D 1 Estimate 2 in the Weight Function w x1 xi y1 yi n Pr y1 x1 D 1 i 2 w x1 xi n i 2 x 1 x i 2 2 exp y1 yi 2 2 i 2 n x 1 x i 2 2 exp 2 2 i 2 n Pr y x1 D 1 is a function of 2 Estimate 2 in the Weight Function w x1 xi y1 yi n Pr y1 x1 D 1 i 2 w x1 xi n i 2 x 1 x i 2 2 exp y1 yi 2 2 …