Logistic Regression

Logistic regression is a binary classifier that outputs probabilities with confidence, not just hard decisions. It shares the same prediction rule as perceptron ($\text{sign}(⟨w,x⟩)$) but optimizes a convex log-likelihood that works on non-separable data and gives calibrated confidences.

Intuition

Labels are in $\{0,1\}$ (not $\pm 1$ like perceptron). Model the label as Bernoulli:

• $\mathrm{Pr}[y=1\mid x,w]=p(x,w)\in (0,1)$
• $\mathrm{Pr}[y=0\mid x,w]=1-p(x,w)$

Parameterization via the Logit Transform

Naive attempt: $p(x,w)=⟨x,w⟩$ fails because LHS $\in [0,1]$ while RHS $\in \mathbf{R}$.

The fix: equate the linear score with the log-odds (“logit”):

$$\log \frac{p(x,w)}{1-p(x,w)}=⟨x,w⟩$$

This works because as $p$ ranges over $(0,1)$, the logit ranges over $\mathbf{R}$. Solving for $p$:

$$p(x,w)=\frac{1}{1+\exp (-⟨x,w⟩)}\triangleq \text{sigmoid}(⟨x,w⟩)$$

The choice of sigmoid is somewhat arbitrary: any monotone function $\mathbf{R}\to [0,1]$ works. Taking $\text{sign}(⟨x,w⟩)$ recovers the perceptron.

Intuition

Sigmoid squashes an unbounded linear score into a probability. Far from the boundary ($|⟨w,x⟩|\gg 0$) the output saturates near 0 or 1 (high confidence), and near the boundary it is close to 0.5 (uncertain). The linear score is the log-odds: doubling $⟨w,x⟩$ squares the odds ratio, not the probability.

Prediction

Predict $\hat{y}=1$ if $p(x,w)>\frac{1}{2}$, else $\hat{y}=0$. Since $\text{sigmoid}(0)=\frac{1}{2}$, this is equivalent to $\hat{y}=\text{sign}(⟨x,w⟩)$, same decision boundary as perceptron.

What’s different from perceptron:

1. Objective is convex and defined on non-separable data
2. Magnitude of $p(x,w)$ is a confidence, hence “regression”

MLE Derivation

$$\hat{w}=\arg \underset{w}{\max }\prod _{i=1}^{n}p(x_i,w{)}^{y_i}(1-p(x_i,w){)}^{1-y_i}$$

Take log, negate, and this is the cross-entropy loss:

$$\hat{w}=\arg \underset{w}{\min }-\sum _{i=1}^n\left[y_i\log p_i+(1-y_i)\log (1-p_i)\right]$$

Equivalently, with ${\tilde{y}}_i=+1$ if $y_i=1$ and ${\tilde{y}}_i=-1$ if $y_i=0$:

$$\hat{w}=\arg \underset{w}{\min }\frac{1}{n}\sum _{i=1}^n\log (1+\exp (-{\tilde{y}}_i⟨x_i,w⟩))$$

This is the logistic loss, a smooth, convex surrogate for 0-1 loss.

Optimization

No closed form (unlike linear regression). The loss is convex so we find the point where ${\sum }_i{\nabla }_w{\ell }_w(x_i,y_i)=0$.

Gradient: ${\nabla }_w{\ell }_w(x_i,y_i)=(p_i(x_i,w)-y_i)x_i$.

The gradient has a clean reading: the update is proportional to (prediction error) times (feature vector). A confident-and-right prediction contributes nothing, a confident-and-wrong prediction contributes a big $x_i$-aligned push. Same structure as perceptron’s $y_i{x}_i$ update, but weighted smoothly by how wrong you are instead of all-or-nothing.

Methods:

• Gradient Descent: $w_t=w_{t-1}-{\eta }_t\cdot \frac{1}{n}{\sum }_i\nabla {\ell }_w$
• Stochastic Gradient Descent: subsample $B\subseteq [n]$
• Newton’s method: uses Hessian, fewer steps but costly per step

Multiclass Logistic Regression (Softmax)

$$\mathrm{Pr}[y=k\mid x,w]=\frac{\exp ⟨w_k,x⟩}{{\sum }_{\ell =1}^c\exp ⟨w_{\ell },x⟩}$$

This is the softmax function. Training with cross-entropy loss generalizes directly.

From CS480 lec4.

Related

• Perceptron (same prediction rule, different objective)
• Cross-Entropy Loss
• Sigmoid
• Softmax
• MLE
• Gradient Descent
• Newton’s Method
• CS480