Lecture 06: Logistic Regression

Classification

In classification problems, the target variable $y$ is a discrete value. We want to develop the logistic regression algorithm to determine which class a new input should fall into.

• Classification problems:

  • Email $\rightarrow$ spam / not spam?
  • Online transactions $\rightarrow$ fraudulent (yes / no)?
  • Tumor $\rightarrow$ malignant / benign?

• Target Variable ($y$):

  • $y \in \{0, 1\}$
  • $0$: Negative class (absence of something, e.g., benign tumor, not spam)
  • $1$: Positive class (presence of something, e.g., malignant tumor, spam)

We start with binary class problems, where $y$ can take on only two values (0 or 1). Later, we will look at multiclass classification problems, which extend binary classification.

Why Not Use Linear Regression for Classification?

Consider a tumor size vs. malignancy ($0$ or $1$) dataset. We could try fitting a linear regression model $h_\theta(x) = \theta^T x$ and thresholding its output:

• Predict $y = 1$ if $h_\theta(x) \ge 0.5$
• Predict $y = 0$ if $h_\theta(x) < 0.5$

In some simple cases, linear regression with thresholding seems to do a reasonable job of stratifying data points into two classes. However, it suffers from major issues:

1. Sensitivity to Outliers: Adding a single positive training example ($y = 1$) with a very large tumor size shifts the decision line, causing the threshold to misclassify existing positive examples as negative ($y = 0$).
2. Unbounded Hypothesis: We know $y \in \{0, 1\}$, but linear regression hypothesis $h_\theta(x)$ can output values much larger than $1$ or less than $0$.

Logistic regression solves this by ensuring hypothesis values always lie strictly between $0$ and $1$. Despite the name "regression", logistic regression is a classification algorithm.

Hypothesis Representation

To output values bounded between $0$ and $1$, we modify our hypothesis function. In linear regression, we had:

For logistic regression, we wrap $\theta^T x$ inside a function $g(z)$:

Where $g(z)$ is defined as:

This function $g(z)$ is called the sigmoid function or the logistic function.

Combining these equations gives the logistic regression hypothesis representation:

The Sigmoid Function Plot

The sigmoid function crosses $0.5$ at the origin ($z = 0$) and asymptotes at $0$ (as $z \to -\infty$) and $1$ (as $z \to +\infty$).

Given this hypothesis representation, our goal is to fit the parameters $\theta$ to our training data.

Interpreting Hypothesis Output

When our hypothesis $h_\theta(x)$ outputs a number, we interpret that value as the estimated probability that $y = 1$ for a given input $x$.

Example

Suppose feature vector $x$ contains:

• $x_0 = 1$ (bias feature, as always)
• $x_1 = \text{tumorSize}$

If $h_\theta(x) = 0.7$, it tells the patient that they have a $70\%$ probability of the tumor being malignant ($y = 1$).

Formal Probability Notation

This represents: "The probability that $y = 1$, given $x$, parameterized by $\theta$."

Since this is a binary classification task where $y$ must be either $0$ or $1$, the probabilities for the two outcomes must sum to 1:

Decision Boundary

The decision boundary gives a better understanding of what the hypothesis function computes and what its decision regions look like.

To make predictions:

• Predict $y = 1$ whenever $h_\theta(x) \ge 0.5$
• Predict $y = 0$ whenever $h_\theta(x) < 0.5$

Looking at the sigmoid curve:

• $g(z) \ge 0.5$ whenever $z \ge 0$

Since $z = \theta^T x$:

• $h_\theta(x) = g(\theta^T x) \ge 0.5$ whenever $\theta^T x \ge 0$

Therefore:

• Hypothesis predicts $y = 1$ when $\theta^T x \ge 0$
• Hypothesis predicts $y = 0$ when $\theta^T x < 0$

Linear Decision Boundary Example

Consider a system with hypothesis $h_\theta(x) = g(\theta_0 + \theta_1 x_1 + \theta_2 x_2)$.

Suppose parameters are chosen as:

The model predicts $y = 1$ when:

The line $x_1 + x_2 = 3$ forms the decision boundary.

• Magenta ($+$ / $1$) region: $x_1 + x_2 > 3$ where $h_\theta(x) > 0.5$
• Blue ($o$ / $0$) region: $x_1 + x_2 < 3$ where $h_\theta(x) < 0.5$
• Straight Line: $x_1 + x_2 = 3$ where $h_\theta(x) = 0.5$ exactly.

Key Note: The decision boundary is a property of the hypothesis and its parameters $\theta$, not of the dataset itself. We fit $\theta$ using dataset training examples, but once $\theta$ is determined, the boundary is defined entirely by $\theta^T x = 0$.

Non-Linear Decision Boundaries

To fit complex non-linear data distributions, we can add higher-order polynomial features to our input vector, just like in polynomial linear regression.

Suppose our hypothesis includes quadratic terms:

Suppose parameter values are fit as:

The model predicts $y = 1$ when:

Plotting $x_1^2 + x_2^2 = 1$ yields a circular decision boundary centered at the origin with radius 1:

• Outside the circle ($x_1^2 + x_2^2 \ge 1$): Predicts $y = 1$
• Inside the circle ($x_1^2 + x_2^2 < 1$): Predicts $y = 0$

By using even higher-order polynomial features (e.g., $x_1^3, x_1^2 x_2, x_1 x_2^2, x_2^4$), logistic regression can build arbitrarily complex non-linear decision boundaries (ellipses, complex curves, etc.).

Cost Function for Logistic Regression

Given a training set of $m$ examples:

Where each example $x^{(i)} \in \mathbb{R}^{n+1}$ (with $x_0 = 1$) and $y^{(i)} \in \{0, 1\}$.

How do we fit the parameters $\theta$?

Why Squared Error Fails for Logistic Regression

In linear regression, we used the mean squared error cost function:

If we define the individual example cost as:

Then $J(\theta)$ can be rewritten as:

If we plug the non-linear sigmoid hypothesis $h_\theta(x) = \frac{1}{1 + e^{-\theta^T x}}$ into this squared error formula, $J(\theta)$ becomes a non-convex function with many local minima.

If $J(\theta)$ is non-convex, standard gradient descent is not guaranteed to converge to the global minimum because it can get trapped in local minima.

Convex Logistic Regression Cost Function

To guarantee global convergence with gradient descent, we need a convex cost function $\text{Cost}(h_\theta(x), y)$:

Intuition & Plots

1. Case $y = 1$: $\text{Cost} = -\log(h_\theta(x))$

• If $y = 1$ and $h_\theta(x) = 1$, $\text{Cost} = 0$ (perfect prediction, zero penalty).
• As $h_\theta(x) \to 0$, $\text{Cost} \to \infty$. This penalizes the model heavily if it predicts probability $0$ when $y = 1$.

2. Case $y = 0$: $\text{Cost} = -\log(1 - h_\theta(x))$

• If $y = 0$ and $h_\theta(x) = 0$, $\text{Cost} = 0$ (perfect prediction, zero penalty).
• As $h_\theta(x) \to 1$, $\text{Cost} \to \infty$. This penalizes the model heavily if it predicts probability $1$ when $y = 0$.

Using this cost function ensures that $J(\theta)$ is strictly convex and free of local minima.

Simplified Cost Function and Gradient Descent

Because $y \in \{0, 1\}$ in binary classification, we can compress the two cases of $\text{Cost}(h_\theta(x), y)$ into a single line formula:

Verification

• When $y = 1$: $\text{Cost} = -(1)\log(h_\theta(x)) - (0)\log(1 - h_\theta(x)) = -\log(h_\theta(x))$
• When $y = 0$: $\text{Cost} = -(0)\log(h_\theta(x)) - (1)\log(1 - h_\theta(x)) = -\log(1 - h_\theta(x))$

This compact formulation allows us to express the full cost function $J(\theta)$ as:

Statistical Origin: This cost function is derived from maximum likelihood estimation (MLE) under a Bernoulli likelihood assumption. It is convex and guarantees global optimization.

Gradient Descent Updates

To fit parameters $\theta$, we want to find $\theta$ that minimizes $J(\theta)$:

We use gradient descent to iteratively update each parameter $\theta_j$:

Calculating the partial derivative of $J(\theta)$ with respect to $\theta_j$:

Substituting this back gives the explicit parameter update rule:

All parameters $\theta_0, \theta_1, \dots, \theta_n$ must be updated simultaneously.

Note: While this parameter update rule looks identical to linear regression, it is NOT identical because $h_\theta(x)$ for logistic regression is $g(\theta^T x) = \frac{1}{1 + e^{-\theta^T x}}$, whereas linear regression uses $h_\theta(x) = \theta^T x$.

Vectorized Implementation

In vector notation:

Feature scaling (mean normalization, scaling by range/standard deviation) applies to logistic regression gradient descent in the exact same manner as in linear regression to speed up convergence.

Advanced Optimization

For large-scale machine learning problems with many features, standard gradient descent can be slow. Advanced optimization algorithms exist to minimize $J(\theta)$ much faster.

Prerequisites for Optimization Algorithms

To use optimization routines, we need code that takes $\theta$ as input and computes:

1. $J(\theta)$ (the cost value)
2. $\frac{\partial}{\partial \theta_j} J(\theta)$ (the partial derivative vector for $j = 0, \dots, n$)

Advanced Optimization Algorithms

• Conjugate Gradient
• BFGS (Broyden-Fletcher-Goldfarb-Shanno)
• L-BFGS (Limited-memory BFGS)

Advantages

• No manual learning rate ($\alpha$): They use an internal line search algorithm to pick optimal step sizes for each iteration.
• Faster convergence: Typically converge much faster than standard gradient descent.

Disadvantages

• More complex; should be accessed via optimized numerical libraries rather than written from scratch.

Using Advanced Optimization Algorithms (Octave / MATLAB)

Consider a simple test optimization problem with two parameters $\theta_1, \theta_2$:

1. Define the Cost Function

function [jVal, gradient] = costFunction(theta)
  jVal = (theta(1)-5)^2 + (theta(2)-5)^2;
  gradient = zeros(2,1);
  gradient(1) = 2*(theta(1)-5);
  gradient(2) = 2*(theta(2)-5);
end

2. Execute fminunc

options = optimset('GradObj', 'on', 'MaxIter', 100);
initialTheta = zeros(2,1);

[optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options);

• optimset('GradObj', 'on', 'MaxIter', 100): Tells Octave that costFunction provides explicit gradient vectors and sets maximum iterations to 100.
• fminunc: Stands for find minimum of unconstrained multivariable function.
• @costFunction: Function handle pointing to the user function.

Multiclass Classification Problems

In multiclass classification, the outcome variable $y$ can take on more than two discrete values ($y \in \{1, 2, 3, \dots, K\}$).

• Examples:
  • Email tagging: Work ($y=1$), Friends ($y=2$), Family ($y=3$), Hobby ($y=4$)
  • Medical diagnosis: Not sick ($y=1$), Cold ($y=2$), Flu ($y=3$)
  • Weather: Sunny ($y=1$), Cloudy ($y=2$), Rain ($y=3$), Snow ($y=4$)

One-vs-All (One-vs-Rest) Classification

The One-vs-All strategy transforms a $K$-class classification problem into $K$ separate binary classification problems.

Training Procedure

For a dataset with $K$ classes:

1. Class 1 vs All: Set class 1 as positive ($y = 1$) and all other classes as negative ($y = 0$). Train classifier $h_\theta^{(1)}(x)$.
2. Class 2 vs All: Set class 2 as positive ($y = 1$) and all other classes as negative ($y = 0$). Train classifier $h_\theta^{(2)}(x)$.
3. $\dots$
4. Class K vs All: Set class $K$ as positive ($y = 1$) and all other classes as negative ($y = 0$). Train classifier $h_\theta^{(K)}(x)$.

Each classifier $h_\theta^{(i)}(x)$ evaluates:

Prediction Procedure

Given a new input $x$, evaluate all $K$ trained classifiers and pick the class $i$ that yields the highest estimated probability: