Overview: Logistic regression

Logistic Regression

Logistic Regression (LogReg) is one of the most common machine learning algorithms. It can be used to predict the probability of an event occurring based on a given labeled data set.

• Email analysis (Is an email spam or not?)
• Sentiment analysis (is a movie review positive or negative?)
• Medical diagnostics (is a given diagnosis present or absent?)

Logistic regression: review

• A group of 20 students spends between 0 and 6 hours studying for an exam. How does the number of hours spent studying affect the probability of the student passing the exam?

• The logistic function has the form \[ p(x) = \frac{1}{1+e^{-\tfrac{x-\mu}{s}}} \tag{1}\]

Logistic regression: review

• In Equation 1, \(\mu\) is the location parameter (midpoint of the curve, \(\tfrac{1}{2}\), and \(s\) is the scale parameter.
• We generally rewrite this with \(\beta_0 = -\tfrac{\mu}{s}\) and \(\beta_1=\tfrac{1}{s}\), yielding

Log odds

• In our example, \(\beta_1\) is the log odds of passing for each additional hour studied

\[ \log\left(\frac{p}{1-p}\right) = \beta_o + \beta_1x \]

• In our example, \(\beta_1 = 1.505\), so each additional hour of studying increased log odds of passing by 1.5

• It is more interpretable to use the odds ratio defined as \[ e^{\beta_1} = e^{1.505}\approx 4.5 \]

• For each additional hour, we multiply the odds of passing by 4.5

• We can also perform multiple logistic regression with a vector of variables

\[ p(\mathbf{x}) = \frac{1}{1+e^{-\beta_0 + \beta_1x + \beta_2x_2+\ldots}} \tag{3}\]

The five components of Logistic Regression

LogReg: Features

For each input \(x\), we create a vector of features: \(\mathbf{x} = [x_1, x_2, \ldots, x_n]\).

There are many different ways of generating a feature vector

• Raw numerical data: If the input data is numerical with \(n\) dimensions, each of the dimensions can act as a feature
• Polynomial & interaction features: We can add interaction terms (\(x_ix_j\)) or polynomial features (e.g., \(x_i^7\)) if this makes sense for the classification task
• Images: Flatten pixel values (e.g., an \(8\times 8\) image would have 64 features)
• Text to vector: e.g., count word occurrences across a vocabulary
• Domain-specific feature engineering

Weights and bias

• Linear combination of input features
• Each data point is multiplied by weights and a bias is added
• Here, \(x_{i,j}\) refers to the \(j^{th}\) component of the \(i^{th}\) data point. \[ z_i = \sum_{j=1}^n w_ix_{i,j} + b \tag{4}\]

Equation 4 can be represented identically using dot product notation (where the bold font indicates a vector of weights (\(\mathbf{w}\)) and inputs (\(\mathbf{x}\)))

\[ z_i = \mathbf{w}\cdot \mathbf{x}_i + b \]

This is identical to the sums we will see at individual neurons in neural networks

Sigmoid

• The sigmoid \(\sigma(z)\) takes a real-valued number \(z\in [-\infty, \infty]\) and effectively squashes it to lie in the range \([0,1]\): \(0<\sigma(z) < 1\).

\[ \sigma(z) = \frac{1}{1+e^{-z}} = \frac{1}{1+\exp(-z)} \]

Sigmoid: A convenient identity

• \(1−\sigma(x) = \sigma(−x)\)

\[ \begin{align*} 1−\sigma(x) &=& 1- \frac{1}{1+e^{-x}}\\ &=& \frac{1+e^{-x} - 1}{1+e^{-x}} \\ &=& \frac{e^{-x}}{1+e^{-x}} \cdot \frac{e^{x}}{e^{x}}\\ &=& \frac{1}{1+e^{x}} \\ &=& \sigma(-x) \\ \end{align*} \]

Sigmoid: A convenient identity

\(1−\sigma(x) = \sigma(−x)\)

Logit

• Odds: The ratio of success to failure: \(p / (1-p)\).
• Logit: The natural logarithm of those odds (log odds): \(\ln (\frac{p}{1-p})\).
• The logit is the inverse of the sigmoid function:
• \(z=\sigma(\mathbf{w}\cdot\mathbf{x}+b)\) can be any real number \((-\infty, \infty)\)
• \(p\in [0, 1]\) represents a probability
• These functions are inverses of each other because \(\sigma(\text{logit}(p)) = p\)

Proof

Learning a classification rule

• We need to learn the parameters of the model \(\mathbf{w}\) and \(b\):

\[ \begin{array}{c c c c c} \mathbf{x}& \longrightarrow & \hat{y} = \sigma(z)=\sigma(\mathbf{w}\cdot\mathbf{x}+b) & \longrightarrow \\ \text{\small Input features} & & \text{\small Output probability} & \end{array} \]

• The class label \(y\) is 1 (true) or 0 (false)
• The prediction of the class label \(\hat{y}=P(y = 1|x)\) is a real number between 0 and 1

Loss function

• A good model will minimize the difference between our prediction \(\hat{y}\) and the ground truth \(y\)

• this distance is defined by the loss function (also known as the cost function).

• The same loss function is commonly used for logistic regression and for neural networks, the cross-entropy loss.

• Recall that our classifier output is \(\hat{y} = \sigma(\mathbf{w}\cdot\mathbf{x} + b)\)

• For logistic regression with binary classification, \(y\) can be either 0 or 1, but \(\hat{y}\) is a probability that ranges from 0 to 1.

• We measure the difference with the loss function \(\mathcal{L}(\hat{y}, y)\)

Loss function

• Using \(\hat{y}=\sigma(z)\), we can concisely write the loss function as: \[ \log p(y|x) = \log[\hat{y}^y(1-\hat{y})^{1-y}] = y\log\hat{y} + (1-y)\log(1-\hat{y}) \]

• Note this simplifies to either \(\log\hat{y}\) or \(\log(1-\hat{y})\) depending on whether \(y\) is 0 or 1.

• Since it is convenient to minimize the function, we multiply it by -1: The result is known as the cross-entropy loss

\[ \mathcal{L}_{CE}(\hat{y}, y) = - y\log\hat{y} - (1-y)\log(1-\hat{y}) \]

• Since we have \(\mathbf{\hat{y}} = \sigma(\mathbf{w}\cdot \mathbf{x} + b)\), this is equivalent to

\[ \mathcal{L}_{CE}(\hat{y}, y) = - y\log\sigma(\mathbf{w}\cdot \mathbf{x} + b) - (1-y)\log(1-\sigma(\mathbf{w}\cdot \mathbf{x} + b)) \]

Loss function

• \(- y\log\sigma(\mathbf{w}\cdot \mathbf{x} + b) - (1-y)\log(1-\sigma(\mathbf{w}\cdot \mathbf{x} + b))\) is equivalent to the following piecewise loss function \[ \mathcal{L}(\sigma(z), y) = \begin{cases} -\log \sigma(z) & \text{if } y_i = 1 \\ -\log 1- \sigma(z) & \text{if } y_i = 0 \\ \end{cases} \]

• If \(y_i=1\), then As \(\log \sigma(z) \rightarrow 1\), the loss approaches zero

Loss function (sanity check)

\[ \mathcal{L}_{CE}(\hat{y}, y) = - y\log\sigma(\mathbf{w}\cdot \mathbf{x} + b) - (1-y)\log(1-\mathbf{w}\cdot \mathbf{x} + b)) \]

• Note that if we predict (correctly) for a true example that \(\hat{y}=1\), then the second term drops out and we have

\[ \mathcal{L}_{CE}(\hat{y}, y) = - 1\log 1 = 0 \]

• Similar things apply for a correct prediction of a negative example as \(\hat{y}=0\)
• The loss for one example ranges from 0 to infinity (\(-\log 0\))

Optimizing the loss

• If we symbolize the parameters (weights, bias) of the logistic regression as \(\theta\), our objective function is:

\[ J(\theta) = \frac{1}{m} \sum_{i=1}^{m} \mathcal{L}(\hat{y}^{(i)}, y^{(i)}) \]

• We seek \(\hat{\theta}\), the parameters that minimize the loss

\[ \hat{\theta} = \arg\min_{\theta} J(\theta) \]

• It can be shown that the logistic regression loss function is convex (which enables us to reliably find its minimum)

Gradient descent

• Given a learning rate \(\eta\) and the gradient of the weights and bias:

• Each iteration of the GD processes Updates the weights and bias \[ \begin{eqnarray*} \mathbf{w} &\leftarrow &\mathbf{w} - \eta\Delta \mathbf{w} \\ \mathbf{b} &\leftarrow &\mathbf{b} - \eta\Delta \mathbf{b} \end{eqnarray*} \]

• We will explain how the gradient is calculated and then return to the mechanics of the gradient descent algorithm.

The Gradient

Another commonly encountered notation is the gradient, which by convention is represented as a column vector

\[ \nabla f(\mathbf{x}) = \begin{bmatrix} \dfrac{\partial f}{\partial \mathbf{x}} \end{bmatrix}^T = \begin{bmatrix} \dfrac{\partial f}{\partial x_1}\\ \dfrac{\partial f}{\partial x_2} \\ \cdots \\ \dfrac{\partial f}{\partial x_n} \end{bmatrix} \tag{5}\]

Gradient descent

• We iteratively take steps towards the minimum along the slope of the function
• But how do we calculate the slope?

Calculating derivatives

We need to update each component of the weight vector \(\mathbf{w}\), e.g., \(w_j\) based on the first derivative of the loss \(\mathcal{L}=\mathcal{L}_{CE}(\hat{y}, y)\) with respect to the component.

• Apply the chain rule twice

\[ \frac{\partial \mathcal{L}}{\partial w_j} = \frac{\partial \mathcal{L}}{\partial \sigma_i} \cdot \frac{\partial \sigma_i}{\partial w_j} = \frac{\partial \mathcal{L}}{\partial \sigma_i} \cdot \frac{\partial \sigma_i}{\partial z_i} \cdot \frac{\partial z_i}{\partial w_j} \tag{6}\]

Derivation and chain rule

• HOMEWORK To understand the derivations (and to understand backprop in the next lecture!), it is essential to be familiar with the chain rule. We will practice in the practical.

Answer

\[ \frac{dy}{dx} = \frac{d}{dx}\sin(4x+3) \]

• Use the chain rule to evaluate this expression!

• What is \(u\)?
• Let \(u = 4x+3\), so \(y = \sin(u)\)
• What is \(\tfrac{dy}{du}\)?
• \(\frac{dy}{du} = \cos(u)\)
• What is \(\tfrac{du}{dx}\)?
• \(\tfrac{du}{dx}=\tfrac{d}{dx}4x+3 = 4\)
• Use the chain rule!
• \(\frac{dy}{dx} = \tfrac{dy}{du}\cdot \tfrac{du}{dx} = \cos(u) \cdot 4 = \cos(4x+3) \cdot 4 = 4\cos(4x+3)\)

Calculating derivatives

• Let’s return to the calculation of the derivative of the loss function for coefficient \(w_j\) of logistic regression (Equation 6)

\[ \frac{\partial \mathcal{L}}{\partial w_j} = \underbrace{\frac{\partial \mathcal{L}}{\partial \sigma_i}}_{\text{Part A}} \cdot \underbrace{\frac{\partial \sigma_i}{\partial z_i}}_{\text{Part B}} \cdot \underbrace{\frac{\partial z_i}{\partial w_j}}_{\text{Part C}} \]

• In the following slides, we will calculate the three parts separately.

Part A: \(\frac{\partial \mathcal{L}}{\partial \hat{y}}\)

Part B: derivative of the sigmoid activation function

derivative of the sigmoid activation function

• Thus we get the fascinating result that

\[ \frac{d\sigma(x)}{dx} = \sigma(x)(1-\sigma(x)) \]

• Substituting and remembering that we define \[ \hat{y} = \sigma(\mathbf{w}\cdot\mathbf{x} + b) \] we get \[ \underbrace{\frac{\partial \sigma_i}{\partial z_i}}_{\text{Part B}} = \hat{y}(1- \hat{y}) \]

Part C: \(\frac{\partial z}{\partial w_j}\): Gradient of the \(z\) with respect to the Weight \(w_j\)

The Since \(z = w_1x_1 + w_2x_2 + \dots + b\), the derivative with respect to \(w_j\) is simply the feature it is multiplied by: \[ \frac{\partial z}{\partial w_j} = x_j \]

Putting it all together

\[ \frac{\partial \mathcal{L}}{\partial w_j} = \underbrace{\left[ \frac{\hat{y} - y}{\hat{y}(1-\hat{y})} \right]}_{\text{Part A}} \cdot \underbrace{\left[ \hat{y}(1-\hat{y}) \right]}_{\text{Part B}} \cdot \underbrace{x_j}_{\text{Part C}} \]

• Thanks to cancelations, we are left with

\[ \begin{align*} \frac{\partial \mathcal{L}}{\partial w_j} &= (\hat{y} - y)x_j \end{align*} \]

Bias term

• HOMEWORK You will adapt this example The term for the partial derivative of the bias can be determined analogously to be

\[ \frac{\partial \mathcal{L}}{\partial b} = (\hat{y} - y) \]

• In the homework, you will be asked to derive this formally.