Logistic Regression - Stanford University

1 1 Will MonroeCS 109 Lecture Notes #22 August 14, 2017 Logistic RegressionBased on a chapter by Chris PiechLogistic regressionis a classification algorithm1that works by trying to learn a function thatapproximatesP(Y|X). It makes the central assumption thatP(Y|X)can be approximated as asigmoid function applied to a linear combination of input features. It is particularly important tolearn because Logistic Regression is the basic building block of artificial neural , for a single training data point (x,y), Logistic Regression assumes:P(Y=1|X=x)= (z)wherez= 0+m i=1 ixiThis assumption is often written in the equivalent forms:P(Y=1|X=x)= ( Tx)where we always setx0to be 1P(Y=0|X=x)=1 ( Tx)by total law of probabilityUsing these equations for probability ofY|Xwe can create an algorithm that selects values oftheta that maximize that probability for all data.

2 I am first going to state the log probability functionand partial derivatives with respect to theta. Then later we will (a) show an algorithm that can choseoptimal values of theta and (b) show how the equations were important thing to realize is that: given the best values for the parameters ( ), Logistic regressionoften can do a great job of estimating the probability of different class labels. However, given bad,or even random, values of it does a poor job. The amount of intelligence that your logisticregression machine learning algorithm has depends on how good its values of we get started I want to make sure that we are all on the same page with respect to Logistic Regression , is a vector of parameters of lengthmand we are going to learn the valuesof those parameters based off ofntraining examples.

3 The number of parameters should be equal tothe number of features of each data point (see section 1).Two pieces of notation that we use often in Logistic Regression that you may not be familiar with: Tx=m i=1 ixi= 1x1+ 2x2+ + mxm (z)=11+e zThe superscriptTin Txrepresents a matrix transpose; the operation Txis equivalent to takingthedot productof the vectors andx, or simply a weighted sum of the components ofx(with containing the weights).1 Yes, this is a terribly confusing name, given thatregressionrefers to tasks that require predicting continuousvalues. Perhapslogistic classificationwould have been better.

4 2 The function (z)=11+e zis called thelogistic function(orsigmoid function); it looks like this: (z)zAn important quality of this function is that it maps all real numbers to the range (0, 1). In logisticregression, (z)turns an arbitrary score zinto a number between 0 and 1 that is interpreted as aprobability. Positive numbers become high probabilities; negative numbers become low LikelihoodIn order to chose values for the parameters of Logistic Regression , we use maximum likelihoodestimation (MLE). As such we are going to have two steps: (1) write the log-likelihood functionand (2) find the values of that maximize the log-likelihood labels that we are predicting are binary, and the output of our Logistic Regression function issupposed to be the probability that the label is one.

5 This means that we can (and should) interpreteach label as a Bernoulli random variable:Y Ber(p)wherep= ( Tx).To start, here is a super slick way of writing the probability of one data point (recall this is theequation form of the probability mass function of a Bernoulli):P(Y=y|X=x)= ( Tx)y [1 ( Tx)](1 y)Now that we know the probability mass function, we can write the likelihood of all the data:L( )=n i=1P(Y=y(i)|X=x(i))the likelihood of independent training labels=n i=1 ( Tx(i))y(i) [1 ( Tx(i))](1 y(i))substituting the likelihood of a BernoulliAnd if you take the log of this function, you get the log likelihood for Logistic Regression .

6 The loglikelihood equation is:L L( )=n i=1y(i)log ( Tx(i))+(1 y(i))log[1 ( Tx(i))]Recall that in MLE the only remaining step is to chose parameters ( ) that maximize log likelihood. 3 Gradient of Log LikelihoodNow that we have a function for log-likelihood, we simply need to chose the values of theta thatmaximize it. Unfortunately, if we try just setting the derivative equal to zero, we ll quickly getfrustrated: there s no closed form for the maximum. However, we can find the best values of thetaby using an optimization algorithm. The optimization algorithm we will use requires the partialderivative of log likelihood with respect to each parameter.

7 First I am going to give you the partialderivative (so you can see how it is used); we ll derive it a bit later: L L( ) j=n i=1[y(i) ( Tx(i))]x(i)jGradient Ascent OptimizationOur goal is to choosing parameters ( ) that maximize likelihood, and we know the partial derivativeof log likelihood with respect to each parameter. We are ready for our optimization the case of Logistic Regression we can t solve for mathematically. Instead we use a computer tochose . To do so we employ an algorithm called gradient ascent (a classic in optimization theory).The idea behind gradient ascent is that gradients point uphill.

8 If you continuously take small stepsin the direction of your gradient, you will eventually make it to a local maximum. In the case oflogistic Regression you can prove that the result will always be a global update to our parameters that results in each small step can be calculated as: newj= oldj+ L L( old) oldj= oldj+ n i=1[y(i) ( Tx(i))]x(i)jWhere is the magnitude of the step size that we take. If you keep updating using the equationabove, you will converge on the best values of . You now have an intelligent model. Here is thegradient ascent algorithm for Logistic Regression in pseudo-code:It is also common to have a parameter 0that is added as a constant to the Txinside the than computing special derivatives for 0, we can simply define an additional featurex0thatalways takes the value 1.

9 Taking a weighted average then results in adding 0, the weight forx0. 4 DerivationsIn this section we provide the mathematical derivations for the gradient of log-likelihood. Thederivations are worth knowing because these ideas are heavily used in Artificial Neural goal is to calculate the derivative of the log likelihood with respect to each theta. To start, hereis the definition for the derivative of a sigmoid function with respect to its inputs: z (z)= (z)[1 (z)]to get the derivative with respect to , use the chain ruleTake a moment and appreciate the beauty of the derivative of the sigmoid function.

10 The reason thatsigmoid has such a simple derivative stems from the natural exponent in the sigmoid the likelihood function is a sum over all of the data, and in calculus the derivative of a sumis the sum of derivatives, we can focus on computing the derivative of one example. The gradientof theta is simply the sum of this term for each training data I am going to show you how to compute the derivative the hard way. Then we are going tolook at an easier method. The derivative of gradient for one data point(x,y): L L( ) j= jylog ( Tx)+ j(1 y)log[1 ( Tx]derivative of sum of terms=[y ( Tx) 1 y1 ( Tx)] j ( Tx)derivative of logf(x)=[y ( Tx) 1 y1 ( Tx)] ( Tx)[1 ( Tx)]xjchain rule + derivative of =[y ( Tx) ( Tx)[1 ( Tx)]] ( Tx)[1 ( Tx)]xjalgebraic manipulation=[y ( Tx)]xjcancelling termsDerivatives Without TearsThat was the hard way.)