Review Rong Jin Comparison of Different Classification Models The goal of all classifiers Predicating class label y for an input x Estimate p y x K Nearest Neighbor kNN Approach k 4 k 1 Probability interpretation estimate p y x as p y x x y y i i i y xi N x N x N x is the neighborhood around x K Nearest Neighbor Approach KNN What is the appropriate size for neighborhood N x Leave one out approach Weight K nearest neighbor Neighbor is defined through a weight function x x i wi x exp 2s 2 Estimate p y x 2 2 w x d y yi i i p y x i wi x How to estimate the appropriate value for 2 K Nearest Neighbor Approach KNN What is the appropriate size for neighborhood N x Leave one out approach Weight K nearest neighbor Neighbor is defined through a weight function x x i wi x exp 2s 2 Estimate p y x 2 2 w x d y yi i i p y x i wi x How to estimate the appropriate value for 2 K Nearest Neighbor Approach KNN What is the appropriate size for neighborhood N x Leave one out approach Weight K nearest neighbor Neighbor is defined through a weight function x x i wi x exp 2s 2 Estimate p y x 2 2 w x d y yi i i p y x i wi x How to estimate the appropriate value for 2 Weighted K Nearest Neighbor Leave one out maximum likelihood Estimate leave one out probability w x j d y j yi 1 i wi x j d y j yi i j i p yj xj 1 i wi x j i j wi x j Leave one out likelihood of training data n j 1 n j 1 lLOO log p y j x j 1 i wi x j d y j yi log 1 wi x j i Search the optimal 2 by maximizing the leave one out likelihood Weight K Nearest Neighbor Leave one out maximum likelihood Estimate leave one out probability w x j d y j yi 1 i wi x j d y j yi i j i p yj xj 1 i wi x j i j wi x j Leave one out likelihood of training data n j 1 n j 1 lLOO log p y j x j 1 i wi x j d y j yi log 1 wi x j i Search the optimal 2 by maximizing the leave one out likelihood Gaussian Generative Model p y x p x y p y posterior likelihood prior Estimate p x y and p y Allocate a separate set of parameters for each class 1 2 c p xly p x y Maximum likelihood estimation p x y N 1 2ps y 2 2 x my exp 2 2 s y N 1 l log p xi yi log p yi log 2ps yi 2 i 1 i 1 2 xi myi 2 log p yi 2s y2i Gaussian Generative Model p y x p x y p y posterior likelihood prior Estimate p x y and p y Allocate a separate set of parameters for each class 1 2 c p xly p x y Maximum likelihood estimation p x y N 1 2ps y 2 2 x my exp 2 2 s y N 1 l log p xi yi log p yi log 2ps yi 2 i 1 i 1 2 xi myi 2 log p yi 2s y2i Gaussian Generative Model Difficult to estimate p x y if x is of high dimensionality Na ve Bayes r p x y q p x1 y q p x2 y q p xd y q Essentially a linear model How to make a Gaussian generative model discriminative m m of each class are only based on the data belonging to that class lack of discriminative power Gaussian Generative Model 1 p y x p x y p y c y 1 p x y p y 2ps y 2 c y 1 2 x my exp p y 2 2s y 1 2ps y 2 2 x my exp p y 2 2s y Maximum likelihood estimation How to optimize this objective function N l log p yi xi i 1 c 2 2 x m p x m 1 i yi i y y log 2ps y2i log p yi log exp 2 2 2 2 s y 1 2ps y 2 i 1 2s y yi N Gaussian Generative Model Bound optimization algorithm q m1 s 1 p1 mc s c pc parameter of current iteration q m1 s 1 p1 mc s c pc parameter of last iteration l q l q 1 s y2 p m m 2 x m myi y y y i y i i i i i log log 2 2 s y 2 p yi 2s yi N i c 2 2 c i 1 py py xi my xi my log exp exp log 2 2 2 2 2 s 2 s y 1 2ps y y 1 2ps y y y Gaussian Generative Model Using log x x 1 We have decomposed the interaction of parameters between different classes l q l q 1 s y2 p m m 2 x m m y y y i y y i i i i log i log i 2 2 s y 2 p yi 2s yi i 2 N c p x m i y y exp 2 2 2s y i 1 y 1 2ps y 2 c py xi my exp 2 2 y 1 2ps y 2s y how to handle x Question with multiple features Logistic Regression Model A linear decision boundary w x b r r w x b 0 positive r r w x b 0 negative A probabilistic model p y x r r w x b 1 r 1 p y 1 x r r 1 exp y w x b Maximum likelihood approach for estimating weights w and threshold b r r N N l Dtrain i 1 log p xi i 1 log p xi N i 1 log 1 1 N log i 1 r r r r 1 exp w xi b 1 exp w x b i Logistic Regression Model Overfitting issue Example text classification Words that appears in only one document will be assigned with infinite large weight Solution regularization r r r N N l Dtrain i 1 log p xi i 1 log p xi s w N i 1 log Regularization term 2 1 1 N m 2 log s w i 1 j 1 j r r r r1 exp w xi b 1 exp w xi b Non linear Logistic Regression Model Kernelize logistic regression model r r r r r r N x f x w i 1a if xi r r r r r r N w x K w x i 1a i K xi x r 1 1 p …