Logistic Regression and Classifiers

Logistic Regression Overview

• An important analytic tool in natural and social sciences.
• It is a baseline supervised machine learning tool for classification.
• Logistic Regression is also the foundation of neural networks.

Generative vs Discriminative Classifiers

• Naive Bayes as a generative classifier contrasts with Logistic Regression, which is a discriminative classifier.
• Generative classifiers build a model of what's in an image of something like a cat, knowing about whiskers, ears, and eyes.
• Generative classifiers assign a probability to any image on how cat-like it is.
• Generative classifiers also build different models for different things of what they are trying to classify.
• To run a generative classifier, both models are run and it will determine which one fits better.
• Discriminative Classifiers just try to distinguish dogs from cats, or in the example, dogs have collars, ignoring everything else.
• Naive Bayes finds the correct class c from a document d by using argmax P(d|c)P(c) for c in C with the likelihood prior.
• Logistic Regression finds the correct class c from a document d by using argmax P(c|d) for c in C with the posterior.

Components of a Probabilistic Machine Learning Classifier

• Given m input/output pairs (x(i), y(i)), a classifier involves:
  • Feature Representation: Each input observation x(i) has a vector of features [x1, x2, ..., xn] and feature j for input x(i) is xj or x(i)j, or fj(x).
  • Classification Function: Computes ŷ, the estimated class, via p(y|x), like the sigmoid or softmax functions.
  • Objective Function: Needed for learning, such as cross-entropy loss.
  • Optimization Algorithm: Needed for optimizing the objective function, such as stochastic gradient descent.

Phases of Logistic Regression

• Training entails learning weights w and b using stochastic gradient descent and cross-entropy loss.
• Testing entails computing p(y|x) for a test example x using learned weights w and b, and returning whichever label (y = 1 or y = 0) has a higher probability.

Classification Reminder

• Examples of classifications are positive/negative sentiment classification, spam/not spam, and authorship attribution such as determining if a document was written by Hamilton or Madison.

Text Classification Definition

• The input is a document x and a fixed set of classes C = {c1, c2, ..., cj}.
• The output is a predicted class ŷ ∈ C.

Binary Classification in Logistic Regression

• A series of input/output pairs (x(i), y(i)), which represent x(i) by a feature vector [x1, x2, ..., xn] and compute an output: a predicted class ŷ(i) ∈ {0,1}.

Features in Logistic Regression

• Weight w for feature x indicates how important x is; for positive sentiment:
  • x = "review contains 'awesome'": w = +10
  • x = "review contains 'abysmal'": w = -10
  • x = "review contains 'mediocre'": w = -2

Logistic Regression for One Observation x

• The input observation is a vector x = [x1, x2, ..., xn].
• The weights are one per feature: W = [w1, w2, ..., wn], and are sometimes called the weights θ = [θ1, θ2, ..., θn].
• The output is a predicted class ŷ ∈ {0,1}.
• Multinomial logistic regression entails ŷ ∈ {0, 1, 2, 3, 4}.

How to do Classification

• For each feature x, weight w tells the importance of x, including a bias b.
• Sum all the weighted features and the bias: z = ∑(wixi) + b, can be simplified to z = w•x+b.
• If the sum is high, it can be said that y equals 1; if low, then y equals 0.
• Wanting a probabilistic classifier requires formalizing what "sum is high" means.

The Sigmoid or Logistic Function

• A principled classifier would give a probability, just like Naive Bayes did.
• The problem is that 'z' isn't a probability, so a function that goes from 0 to 1 is needed.
• The solution is then y = σ(z) = 1 / (1 + e-z) = 1 / (1 + exp(-z)).
• To compute w•x+b then it is passed through the sigmoid function to be treated as a probability. P(y=1) = σ(w•x+b) = 1 / (1 + exp(-(w•x+b))) P(y=0) = 1 - σ(w•x+b) = 1 / (1 + exp(-(w•x+b))) = exp(-(w•x+b)) / (1 + exp(-(w•x+b)))
• P(y=0) = 1- σ(w•x+b) equals σ(-(w•x+b))

Turning a Probability into a Classifier

• y = 1 if P(y = 1|x) > 0.5 otherwise it equals 0
• 0.5 is called the decision boundary.
• If P(y = 1|x) > 0.5 it is equivalent in saying if w•x+b > 0, otherwise if w•x+b < 0

Logistic Regression: Sentiment Example on Sentiment Classification

• Given a document, classifying sentiment is determining if y=1 (positive) or y=0 (negative).
• A sentiment example is, "It's hokey. There are virtually no surprises, and the writing is second-rate. So why was it so enjoyable ? For one thing, the cast is great. Another nice touch is the music. I was overcome with the urge to get off the couch and start dancing. It sucked me in, and it'll do the same to you."
  • x1 = count(positive lexicon ∈ doc) equaling 3.
  • x2 = count(negative lexicon ∈ doc) equaling 2.
  • x3 equals 1 if "no" is in doc, or 0 otherwise which is 1.
  • x4 is count(1st and 2nd pronouns ∈ doc) equaling 3.
  • x5 equals 1 if "!" ∈ doc, or 0 otherwise which is 0.
  • x6 is log(word count of doc) equaling In(66) = 4.19.
• Suppose w = [2.5, -5.0, -1.2, 0.5,2.0,0.7] and b = 0.1.
• p(+|x) = P(Y = 1|x) = σ(w•x+b) is equivalent to σ([2.5, -5.0, -1.2, 0.5,2.0,0.7] • [3,2,1,3,0,4.19] + 0.1) which would equal σ(.833), meaning it has value of 0.70.
• p(-|x) = P(Y = 0|x) = 1 - σ(w•x+b), which is equal to 0.30.

Features for Logistic Regression

• Features can be made for any classification task like period disambiguation.
• For if a period is the end of a scentence, or is not the end.
  • x1 equals 1 if "Case(wi) = Lower"
  • x2 equals 1 if "wi ∈ AcronymDict"
  • x3 equals 1 if "wi = St. & Case(wi-1) = Cap"

Classification in (Binary) Logistic Regression: Summary

• Given a set of classes with a + sentiment or - sentiment.
• Given a vector x of features [x1, x2, ..., xn], where x1= count("awesome") and x2 = log(number of words in review).
• Given a vector w of weights [w1, w2, ..., wn] with w for each feature f, P(y = 1) = σ(w•x+b) can be expressed as 1 / (1 + e-(w•x+b)).

Learning: Cross-Entropy Loss

• Supervised classification means knowing the correct label y (either 0 or 1) for each x, but the system produces an estimate, ŷ.
• The goal is to set w and b to minimize the distance between the estimate ŷ(i) and the true y(i).
• A distance estimator, or a loss/cost function, and an optimization algorithm to update w and b to minimize the loss is needed.

Learning Components

• Cross-entropy loss as the loss function.
• Stochastic gradient descent as the optimization algorithm.

Distance Between ŷ and y

• Knowing how far the classifier output is can be represented with ŷ = σ(w•x+b).
• This is measured from the true output y which equals either 0 or 1.
• Measuring the difference is represented in L(ŷ,y), which is how much ŷ differs from the true y.

Intuition of Negative Log Likelihood Loss

• Negative log likelihood loss equals cross-entropy loss.
• It is a case of conditional maximum likelihood estimation.
• The parameters w,b that maximize the log probability, of the true y labels in the training data, give the observations x.

Deriving Cross-Entropy Loss for a Single Observation x

• The Goal: maximize probability of the correct label p(y|x).
• Since there are only 2 discrete outcomes (0 or 1) the probability p(y|x) from the classifier can be expressed as ŷ(y) (1- ŷ) (1-y),
• In the scenario that y=1 this simplifies to ŷ, and if y=0 this simplifies to 1- ŷ.
• Then from there, maximize log p(y|x) where it log equals [ŷ^(y) (1- ŷ)^^(1-y)] and it is equal to ylogŷ+(1-y) log(1 – ŷ).
• Values that maximize log p(y|x) will also maximize p(y|x).
• Find a loss to minimize, flip the script with Cross-entropy loss formula and plug in ŷ:
  • LCE (ŷ,y) = – [ylog σ(w•x+b)+(1-y) log (1 – σ(w•x+b))]

How Cross Entropy Works

• The loss is smaller if the model estimate is close to correct such as the true label of y=1 and is positive.
• Loss is bigger if the model is confused.
• In the sentiment example, it is hokey. There are virtually no surprises, and the writing is second-rate . So why was it so enjoyable ? For one thing, the cast is great. Another nice touch is the music . I was overcome with the urge to get off the couch and start dancing. It sucked me in, and it'll do the same to you .
  • p(+|x) = P(Y = 1|x) = σ(w•x+b) equals σ([2.5, -5.0, -1.2, 0.5,2.0,0.7] • [3,2,1,3,0,4.19] + 0.1) which is equivalent σ(.833) and has a 0.70 value.
  • LCE (ŷ, y) equals – [ylog σ(w•x+b)+(1-y) log (1 – σ(w•x+b))], which equals– [log σ(w•x+b)] and has a final value of to .36
  • if the value was instead y=0 = 1-σ(w•x+b), it would equal 0.30 so then, LCE (ŷ, y) equals– [ylog σ(w•x+b)+(1-y) log (1 – σ(w•x+b))], and loss is 1.2
• It is lower than the loss when the model was wrong which confirms a higher loss.

Stitchastic Gradient decent

• Goal: minimize loss 1 / m ∑LCE (f(x(i)),y(i))

• For logistic regression, the loss function is convex.

• A convex function has just one minimum

• Gradient descent starting from any point is guaranteed to find the minimum.

• (Loss for neural networks is non-convex)

• Consider a single scalar 'w': the question is should it be made bigger or smaller, and it can be resolved by looking at the slope of where it is sitting.

• The gradient of a function of many variables is a vector pointing in the direction of the greatest increase in a function.

• Gradient Descent finds the gradient of the loss function at the current point and move in the opposite direction.

• The value of the gradient (slope) is weighted by a learning rate η, higher learning rate means move faster. wt+1 = wt - η * slope of the loss function

• The gradient is represented as a vector to express the directional components of the sharpest slope along the dimensions.

Real gradients have lots and lots of weights.

• For each dimension w; the gradient component i tells the slope with respect to that variable such as how much a small change in w, influence the total loss function L
• Express the slope as a partial derivative with respect to wi
• The gradient is then defined as a vector of the partials and it can be represented in function format.

Stochastic Gradient Descent Details

• Compute ŷ(i) = f(x(i); θ) = What is the estimated output ŷ?
• Compute the loss L(ŷ(i), y(i)) = How far off is ŷ(i)) from the true output y(i)?
• g←∇θL(f(x(i); θ),y(i)) = How should θ move to maximize loss?
• θ← θ - η g = Move θ the other way instead.
• The learning rate n is a hyperparameter which is a special kind of parameter for an ML model.
  • being too high, the learner will take big steps and overshoot
  • being too low, the learner will take too long
• Instead of being learned by an algorithm, they are chosen by the algorithm designer.
• There is also Batch training where it trains the entire dataset and mini-batch training where it trains by m examples.

Gradients Example

• Goal to have w1 = w2 = b = 0, given a mini-sentiment example where x1 is 3 and x2 is 2, also when with with true y=1 and (n = 0.1 as learning rate)
• Update step to new step 0t+1 = θ-η∇L(f(x; 0), y) [Wip formula]
• ∇0 L = [-0.4,-0.2, .6] [Plug into function and derivative with sigmoid]

Regularization

• A model that perfectly matches the training data has a problem, called overfitting.
  • This overfitting entails modeling noise, where a random word that perfectly predicts y, it will get a very high weight.
  • Failing to generalize to a test set without that word.
• Solve by making a model that generalizes, adding a regularization term R(0) to the loss function to penalize those large weights.

L2 Regularization

• Also known as ridge regression, L2 Regularization is found as the sum of the squares of the weights.
• The name comes from equation using L2 norm ||0||2.

L1 Regularization

• Also known as lasso regression, L1 Regularization is found as the sum of the absolute value of the weights.
• The name comes from equation using L1 norm ||W||1.

Multinomial Logistic Regression

• Using more than 2 classes may use multinomial logistic regression.
  • Softmax regression is a method, similar to multiclass Naive Bayes algorithm.
  • Examples are Positive/negative/neutral, parts of speech (noun, verb, adjective, adverb, preposition, etc.), and classifying emergency SMSs into different actionable classes
• Binary logistic regression uses only 2 output classes.

Softmax in Multinomial Logistic Regression

• A generalisation of the sigmoid is called the softmax. Takes a vector z = values Output distribution values which add up one
• The probability of everything must still sum to 1 P(positive|doc) + P(negative|doc) + P(neutral|doc) = 1
• It is still the dot product between weight vector w and input vector xBut separates weight vectors for each of the K classes.
• In binary the weight had direction, for example positive weights are in direction to y=1, multinominal has its weights for its class.