Logistic Regression - Rutgers University

1 Logistic RegressionInstructor: Ping LiDepartment of Statistics and BiostatiticsDepartment of Computer ScienceRutgers University20151 Calculus Review: DerivativesSimple derivatives:[logx] =1x,[xn] =nxn 1,[ex] =ex,[ax] =axlogaChain rule:[f(h(x))] =f (h(x))h (x) log ax2+e2x =1(ax2+e2x) ax2+e2x =2ax+ 2e2x(ax2+ex) multivariate derivatives:f(x, y) =ax+xny+cy2, f(x, y) x=axloga+nxn 1y, f(x, y) y=xn+ 2cy2 Quick Review of Numerical OptimizationSlides 4 - 15 are for reviewing some basic stuff about numerical optimization, which isessential in modern Likelihood Estimation (MLE)Observationsxi,i= 1ton, are samples from a distribution with probability densityfunctionfX(x; 1, 2, .., k),where j,j= 1tok, are parameters to be maximum likelihood estimator seeks the to maximize the joint likelihood =argmax nYi=1fX(xi; )Or, equivalently, to maximize thelogjoint likelihood =argmax nXi=1logfX(xi; )This is aconvexoptimization Example: Normal DistributionIfX N , 2 , thenfX x; , 2 =1 2 e (x )22 2 Fix 2= 1,x= x; , 2 logfX x; , 2 2 fX (x; , 2) 2 1012 3 2 1 log fX(x; , 2)It is Not concave, but it is a-log convex, , a unique MLE solution of Exact MLE samples,xi N( , 2),i= x1, x2.

2 , xn; , 2 =nXi=1logfX(xi; , 2)= 12 2nXi=1(xi )2 12nlog(2 2) l =12 22nXi=1(xi ) = 0 = =1nnXi=1xi l 2=12 4nXi=1(xi )2 n2 2= 0 = 2=1nnXi=1(xi ) FunctionsA functionf(x)is convex if the second derivativef (x) 0. 2 101201234xf(x)=x2f(x) = (x)=xlog(x)f(x) = xlog(x)f(x) =x2= f = 2>0, ,f(x) =x2is convex for (x) =xlogx= f =1x, ,f(x) =xlogxis convex ifx > are widely used in statistics and data mining as loss functions,= computationally tractable algorithms: least square, Logistic panel:f(x) =1 2 e x22is-log convex, 2[ logf(x)] x2= 1> f(x) 1001020304002468xlog f(x)Right panel: a mixture of normals is not-log convexf(x) =1 2 e x22+1 2 10e (x 10)2200 The mixture of normals is an extremely useful model in general, only a local minimum can be Descentyy=f(x)xxx012x34xxProcedure:Start with an initial f (x0), where is the step the processxt+1=xt f (xt).Until some criterion is met, ,f(xt+1) f(xt)The meaning of steepest is more clear in the two-dimensional Example of Steepest Descent:f(x) =x2f(x) =x2.

3 The minimum is attained atx= 0,f (x) = steepest descent iteration formulaxt+1=xt f (xt) =xt 2 10 50510 Iteration = = = the step size is important (even whenf(x)is convex).Too small = slow convergence, , many iterations,Too large = oscillations, , also many Descent in PracticeSteepest descent is one of the most widely techniques in realworld It is extremely simple It only requires knowing the first derivative It is numerically stable (for above reasons) For real applications, it is often affordable to use very small In machine learning, is often calledlearning rate It is used in Neural Nets and Gradient Boosting (MART)11 Newton s MethodRecall the goal is to find thex to minimizef(x).Iff(x)is convex, it is equivalent to finding thex such thatf (x ) = (x) =f (x). Take Taylor expansion about the optimum solutionx :h(x ) =h(x) + (x x)h (x) + negligible higher order termsBecauseh(x ) =f (x ) = 0, we know approximately0 h(x) + (x x)h (x) = x x h(x)h (x)=x f (x)f (x)12 The procedure of Newton s MethodStart with an initial guessx0 Updatex1=x0 f (x0)f (x0)Repeatxt+1=xt f (xt)f (xt)Until some stopping criterion is reached, ,xt+1 example:f(x) = (x c) (x) = 2(x c),f (x) = f (x0)f (x0)= x1=x0 2(x0 c)2=cBut we already know thatx=cminimizesf(x) = (x c) s method may find the minimum solution using only one Example of Newton s Method:f(x) =xlogxf (x) = logx+ 1,f (x) = +1=xt logxt+11 x0 = = 10 10x0 = 1 10 10 Whenx0is close to optimum solution, the convergence is very fastWhenx0is far from the optimum, the convergence is slow initiallyWhenx0is badly chosen, no convergence.

4 This example requires0< x0< Descent forf(x) =xlogxf (x) = logx+ 1,xt+1=xt (logxt+ 1)0102030400246810 Iterationxt x0 = 0, = = 10, = = 10, = ofx0, convergence is guaranteed iff(x)is be oscillating if step size is too largeConvergence is slow near the optimum AnalysisTo assess the quality of the estimator of , it is common to usebias,variance, andMSE(mean square error):Bias :E( ) Var :E E( ) 2=E( 2) E2( )MSE :E 2=V ar+Bias2 The last equality is known as thebias variance trade-off. For unbiased estimators, it isdesirable to have smaller variance as possible. As the sample size increases, the MLE (undercertain conditions) becomes unbiased and achieves the smallest variance. Therefore, theMLE is often a desirable estimator. However, in some cases, biased estimators may achievesmaller MSE than the Expectations and Variances of Common DistributionsThe derivations of variances are not required in this course. Nevertheless, it is useful to knowthe expectations and variances of common distributions.

5 Binomial:X binomail(n, p),E(X) =np,V ar(X) =np(1 p). Normal:X N( , 2),E(X) = ,V ar(X) = 2. Chi-square:X 2(k),E(X) =k,V ar(X) = 2k. Exponential:X exp( ),E(X) =1 ,V ar(X) =1 2. Poisson:X P ois( ),E(X) = ,V ar( ).17 Multinomial DistributionThe multinomial is a natural extension to the binomial and denote the observations by(n1, n2, .., nc), which follow ac-cellmultinomial distribution with the underlying probabilities( 1, 2, .., c)(withPci=1 i= 1). Denoten=Pci=1ni. We write(n1, n2, .., nc) M ultinomial(n, 1, 2, .., c)The expectations are (fori= 1tocandi6=j)E(ni) =n i, V ar(ni) =n i(1 i), Cov(ninj) = n i that the cells are negatively correlated (why?).18 Logistic RegressionLogistic Regression is one of the most widely used statistical tools for predicting setup for binary Logistic regressionnobservations:{xi, yi}, i= be a {0,1}. For example, 1 = YES and 0 = NO .Definep(xi) =Pr(yi= 1|xi) = (xi) ,Pr(yi= 0|xi) = 1 p(xi).19 The major assumption of Logistic regressionlogp(xi)1 p(xi)= 0+ 1xi,1+.

6 + pxi,p=pXj=0 jxi, , we treatxi,0= 1. We can also use vector notation to writelogp(xi; )1 p(xi; )=xi .Here, we viewxias a row-vector and as a model in vector notationp(xi; ) =exi 1 +exi ,1 p(xi; ) =11 +exi ,Log likelihood for theith observation:li( |xi) =(1 yi) log [1 p(xi; )] +yilogp(xi; )= logp(xi; )ifyi= 1log [1 p(xi; )]ifyi= 0To understand this, consider binomial with only one samplebinomial(1, p(xi))( ,Bernouli). Whenyi= 1, the log likelihood islogp(xi)and whenyi= 0, the log likelihood islog (1 p(xi)). These two formulas can be written into log likelihood fornobservations:l( |x1, .., xn) =nXi=1li( |xi)=nXi=1(1 yi) log [1 p(xi; )] +yilogp(xi; )=nXi=1yilogp(xi; )1 p(xi; )+ log [1 p(xi; )]=nXi=1yixi log 1 +exi The remaining task is to solve the optimization problem by Regression with Only One VariableBasic assumptionlogit( (xi))= logp(xi; )1 p(xi; )= 0+ 1xiJoint Log likelihoodl( |x1, .., xn) =nXi=1 yi( 0+xi 1) log 1 +e 0+xi 1 Next, we solve the optimization problem for maximizing the joint likelihood, given the derivatives l( ) 0=nXi=1yi p(xi), l( ) 1=nXi=1xi(yi p(xi)),Second derivatives 2l( ) 20= nXi=1p(xi) (1 p(xi)), 2l( ) 21= nXi=1x2ip(xi) (1 p(xi)), 2l( ) 0 1= nXi=1xip(xi) (1 p(xi))Solve the MLE by Newton s Method or steepest descent (two-dim problem).

7 24 Logistic Regression without Intercept ( 0= 0)The simplified modellogit( (xi))= logp(xi)1 p(xi)= xiEquivalently,p(xi) =e xi1 +e xi= (xi),1 p(xi) =11 +e xi,Joint log likelihood fornobservations:l( |x1, .., xn) =nXi=1xiyi log 1 +e xi 25 First derivativel ( ) =nXi=1xi(yi p(xi)),Second derivativel ( ) = nXi=1x2ip(xi) (1 p(xi)),Newton s Method updating formula t+1= t l ( t)l ( t)Steepest descent (in factascent) updating formula t+1= t+ l ( t)26A Numerical Example of Logistic RegressionDatax={8,14, 7,6,5,6, 5,1,0, 17}y={1,1,0,0,1,0,1,0,0,0}Log likelihood function 1 60 40 200 l( ) t = 0 = s MethodSteepest Descent0102030 t = 0 = s MethodSteepest DescentSteepest descent is quite sensitive to the step size .Too large leads to , 0means the initial value of .2805101520 6 4 20246 Iteration t = 0 = s MethodSteepest Descent01020300510 Iteration t = 0 =10 Newton s MethodSteepest DescentNewton s Method is sensitive to the starting point 0. May not converge at starting point (mostly) only affects computing time of steepest descent.

8 In general, with multiple variables, we need to use the matrix formulation, which in fact iseasier to implement in s Method for Logistic Regression with 0and 1 Analogous to the one variable case, theNewton s updateformula is new= old " 2l( ) T 1 l( ) # oldwhere = 0 1 , l( ) =" ni=1yi p(xi) ni=1xi(yi p(xi))#= T y1 p(x1)y2 p(x2)..yn p(xn) =XT(y p)30 2l( ) T = Pni=1p(xi) (1 p(xi)) Pni=1xip(xi) (1 p(xi)) Pni=1xip(xi) (1 p(xi)) Pni=1x2ip(xi) (1 p(xi)) = XTWXW= p(x1)(1 p(x1)) (x2)(1 p(x2)) p(xn)(1 p(xn)) 31 multivariate Logistic Regression Solution in Matrix FormNewton update formula new= old " 2l( ) T 1 l( ) # oldwhere, in a matrix form l( ) =nXi=1xi(yi p(xi; )) =XT(y p) 2l( ) T= nXi=1xTixip(xi; ) (1 p(xi; )) = XTWXWe can write the update formula in a matrix form new= XTWX 1 XTWz,z=X old+W 1(y p)32X= 1x1,1x1, x1,p1x2,1x2, x2, ,1xn, xn,p Rn (p+1)W= p1(1 p1) (1 p2) pn(1 pn) Rn nwherepi=p(xi; old).33 Derivation new= old " 2l( ) T 1 l( ) # old= old+ XTWX 1XT(y p)= XTWX 1 XTWX old+ XTWX 1XT(y p)= XTWX 1 XTW X old+W 1(y p) = XTWX 1 XTWzNote that XTWX 1 XTWzlooks a lot like (weighted) least major practical issues: The inverse may not (usually does not) exist, especially with large datasets.

9 Newton update steps may be too agressive and lead to Logistic Regression with a Learning RateAt timet, update each coefficient vector: t= (t 1)+ XTWX 1XT(y p) t 1whereW=diag[pi(1 pi)]ni=1 The magic parameter can be viewed as the learning rate to help make sure that theprocedure converges. Practically, it is often set to be = The Simple Example with Only One Datax={8,14, 7,6,5,6, 5,1,0, 17}y={1,1,0,0,1,0,1,0,0,0}Log likelihood function 1 60 40 200 l( )36 Newton s Method with Learning Rate = 10102030 t = 1 0 = 0 = 0 = initial 0= , the method coverges. When 0= , it does not s Method with Learning Rate = t = 0 = 0 = 0 = Logistic Regression With RegularizationThe almost correct update formula: t= (t 1)+ XTWX+ I 1XT(y p) t 1 Adding the regularization parameter usually improves the numerical stability and sometimes may even result in better test are also good statsitical Logistic Regression With RegularizationThe update formula: t= (t 1)+ XTWX+ I 1 XT(y p) t 1To understand the formula, consider the following modified (regularized) likelihood function:l( ) =nXi=1{yilogpi+ (1 yi) log(1 pi)} 2pXj=0 2j40 Newton s Method with No Regularization = 0( = )0102030 10 50510 Iteration t = , = 0 0 = 1 0 = 5 0 = 1041 Newton s Method with Regularization = 1( = )0102030 10 50510 Iteration t = , = 1 0 = 1 0 = 5 0 = 1042 Newton s Method with Regularization = 1( = )0102030 50050 Iteration t = , = 1 0 = 10 0 = 20 0 = 5043 Multi-Class Logistic RegressionData.

10 {xi, yi}ni=1,xi Rn p,yi {0,1,2, .., K 1}.Probability modelpi,k=Pr{yi=k|xi},k= 0,1, .., K 1,K 1Xk=0pk= 1,(onlyK 1degrees of freedom).Label assignment yi|xi=argmaxk pi,k44 Multi-Class Example: USPS ZipCode RecognitionPerson 1:24681012141624681012141624681012141624 6810121416246810121416246810121416246810 1214162468101214162468101214162468101214 16 Person 2:24681012141624681012141624681012141624 6810121416246810121416246810121416246810 1214162468101214162468101214162468101214 16 Person 3:24681012141624681012141624681012141624 6810121416246810121416246810121416246810 1214162468101214162468101214162468101214 16 This task can be cast (simplified) as aK= 10-class classification Logit Probability Modelpi,k=eFi,kPK 1s=0eFi,swhereFi,k=Fk(xi)is the function to be learned from the Logistic Regression :Fi,k=Fk(xi) =xi kNote that, k= [ k,0, k,1, .., k,p]T46 Multinomial Maximum LikelihoodMutlinomial likelihood:Supposeyi=k,Lik p0i,0 .. pi,k1 .. p0i,K 1=pi,klog likelihood:li= logpi,k,ifyi=kTotal log-likelihood in a double summation form:l( ) =nXi=1li=nXi=1(K 1Xk=0ri,klogpi,k)ri,k= 1ifyi=k0otherwise47 Derivatives of Multi-Class Log-likelihoodThe first derivative: li Fi,k= (ri,k pi,k)Proof: pi,k Fi,k=hPK 1s=0eFi,sieFi,k e2Fi,khPK 1s=0eFi,si2=pi,k(1 pi,k) pi,k Fi,t= eFi,keFi,thPK 1s=0eFi,si2= pi,kpi,t48 li Fi,k=K 1Xs=0ri,s1pi,s pi,s Fi,k=ri,k1pi,kpi,k(1 pi,k) +Xs6=kri,s1pi,s pi,s Fi,k=ri,k(1 pi,k) Xs6=kri,spi,k=ri,k K 1Xs=0ri,spi,k=ri,k pi,k The second derivatives: 2li F2i,k= pi,k(1 pi,k), 2li Fi,kFi,s= pi,kpi,s49 Multi-class Logistic Regression can be fairly complicated.