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?)

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{1}\]

Equation 1 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*} \]

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

\[ \begin{align*} \sigma(\text{logit}(p)) &= \frac{1}{1 + e^{-\left[ \ln \left( \frac{p}{1-p} \right) \right]}} &&\bullet \text{Substitute Logit into Sigmoid } z \\ &= \frac{1}{1 + e^{\left[ \ln \left( \frac{1-p}{p} \right) \right]}} && \bullet\text{Apply } -\ln(A) = \ln(1/A) \\ &= \frac{1}{1 + \frac{1-p}{p}} && \bullet\text{Identity: } e^{\ln(x)} = x \\ &= \frac{1}{\frac{p + 1 - p}{p}} && \\ &= \frac{1}{1/p} && \bullet\text{Simplify} \\ &= p && \end{align*} \]

• Therefore :The logit is the inverse of the sigmoid function.

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 & \sigma(z)=\sigma(\mathbf{w}\cdot\mathbf{x}+b) & \longrightarrow & \hat{y}\\ \text{\small Input features} & & \text{\small Output probability} & & \text{\small Prediction of class label} \end{array} \]

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

• Consider 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} \]

As \(\log \sigma(z) \rightarrow 1\), the loss approaches zero

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 (sanity check)

\[ \mathcal{L}_{CE}(\hat{y}, y) = - y\log\sigma(\mathbf{Xw} + b) - (1-y)\log(1-\sigma(\mathbf{Xw} + 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 biases:

• Each iteration of the GD processes Updates the weights and biases of each layer \[ \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{2}\]

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 firstderivative 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} \]

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.

Calculating derivatives

\[ \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}}\): Gradient of the Loss with respect to Prediction

\[ \begin{align*} \frac{\partial \mathcal{L}}{\partial \hat{y}} & = -\frac{\partial }{\partial \hat{y}} [y \ln \hat{y} + (1-y) \ln(1-\hat{y})] && \bullet \text{Using } \hat{y}=\sigma(wx+b) \\ & = -y \frac{\partial }{\partial \hat{y}}\ln \hat{y} - (1-y)\frac{\partial }{\partial \hat{y}}\ln(1-\hat{y}) && \bullet \text{Move constants out of derivative}\\ & = -\frac{y}{\hat{y}} - (1-y) \frac{-1}{1-\hat{y}} && \bullet \text{Recall } \frac{d \ln x}{dx} = \frac{1}{x} \\ & = -\frac{y}{\hat{y}} + \frac{1-y}{1-\hat{y}} && \bullet \text{Simplify signs} \\ & = \frac{-y(1-\hat{y}) + \hat{y}(1-y)}{\hat{y}(1-\hat{y})} && \bullet \text{Common denominator} \\ & = \frac{-y + y\hat{y} + \hat{y} - y\hat{y}}{\hat{y}(1-\hat{y})} && \bullet \text{Expand numerator} \\ & = \frac{\hat{y} - y}{\hat{y}(1-\hat{y})} && \bullet \text{Final result} \end{align*} \]

Part B: derivative of the sigmoid activation function

\[ \begin{align*} \dfrac{d\sigma(x)}{dx} & = \dfrac{d}{dx} \dfrac{1}{1+e^{-x}} \\ & = \dfrac{-1}{(1+e^{-x})^2}\cdot (-e^{-x}) && \bullet \text{chain rule} \\ & = \dfrac{e^{-x}}{(1+e^{-x})^2} && \bullet \text{simplify}\\ & = \dfrac{1}{1+e^{-x}} \cdot \dfrac{e^{-x}}{1+e^{-x}} && \bullet \text{rearrange}\\ & = \sigma(x) \cdot \dfrac{e^{-x}}{1+e^{-x}} && \bullet \text{definition of } \sigma(x)\\ & = \sigma(x) \cdot \dfrac{1 + e^{-x} - 1}{1+e^{-x}} && \bullet \text{add and subtract 1}\\ & = \sigma(x) \cdot \left( \dfrac{1 + e^{-x} }{1+e^{-x}} -\dfrac{1}{1+e^{-x}} \right) && \bullet \text{rearrange}\\ & = \sigma(x) \cdot \left( 1 -\sigma(x) \right) && \bullet \text{simplify using definition of } \sigma(x) \end{align*} \]

derivative of the sigmoid activation function

• Thus we get the fascinating result that

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

• Substituing 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.