Softmax Regression

1. Regularized Logistic Regression¶

Problem: Overfitting when model is too complex or data is limited.

L2 Regularization (Ridge):

Note: Bias term $w_0$ is typically NOT regularized.

L1 Regularization (Lasso):

Gradient for L2-Regularized Logistic Regression:¶

(ignoring $w_0$ in the regularization term)

2. MAP Interpretation of Regularization¶

Bayesian View: Treat parameters $w$ as random variables with prior $P(w)$.

Maximum A Posteriori (MAP) Estimation:

Taking logs:

L2 Regularization = Gaussian Prior:

This yields L2-regularized logistic regression where $\lambda = 1/\sigma^2$.

L1 Regularization = Laplace Prior:

3. Multi-Class Classification¶

Problem: $y \in \{1, 2, \ldots, C\}$ where $C > 2$

Examples:

• Weather: $\{\text{sunny}, \text{cloudy}, \text{rain}, \text{snow}\}$

• Email tags: $\{\text{work}, \text{family}, \text{friends}, \text{hobby}\}$

4. One-vs-All (OvA) Approach¶

Method: For each class $j \in \{1, \ldots, C\}$, train a binary classifier $f_{w_j}(x)$ where:

• Class $j$: positive examples

• All other classes: negative examples

Prediction:

Pros: Simple, easy to implement, can parallelize

Cons:

• Requires training C separate models

• Predicted probabilities don’t necessarily sum to 1

• Class imbalance in each binary problem

5. Softmax Regression (Multinomial Logistic Regression)¶

Idea: Directly model class probabilities $P(y=j|x)$ for all $j$ simultaneously.

Model Definition:¶

For each class $j$, define a linear score:

Parameter Matrix: $W = [w_1, w_2, \ldots, w_C] \in \mathbb{R}^{(d+1)\times C}$

Softmax Function: Converts scores to probabilities

Properties:

• $f_W^{(j)}(x) \in [0, 1]$ for all $j$

• $\sum_{j=1}^C f_W^{(j)}(x) = 1$

Prediction Rule:

Cross-Entropy Loss for Softmax:¶

For training example $(x_i, y_i)$, define:

• Ground-truth (one-hot): $P(y=j|x_i, y_i) = \mathbb{I}(y_i = j)$

• Predicted: $P(y=j|x_i; W) = f_W^{(j)}(x_i)$

Per-example Loss:

Overall Objective:

Convexity Proof Sketch:¶

The softmax objective is convex because:

1. The log-sum-exp function $g(z) = \log(\sum_c \exp(z_c))$ is convex

2. The softmax loss can be written as: $\text{cost}_i = -w_{y_i}^\top x_i + \log(\sum_c \exp(w_c^\top x_i))$

3. This is an affine function plus a convex function (log-sum-exp)

4. Therefore, the overall objective is convex in $W$

6. Gradient Descent for Softmax Regression¶

Gradient with respect to $w_j$:

Proof:

From $J(W) = -\frac{1}{m} \sum_i \log(f_W^{(y_i)}(x_i))$, where:

Let $\sigma_j = f_W^{(j)}(x_i)$ for brevity.

For a single example $(x, y)$ with $z_j = w_j^\top x$:

Case 1: $j = y$ (true class):

Case 2: $j \neq y$:

Combining both cases using indicator function:

Update Rule (SGD): For randomly sampled $(x_i, y_i)$:

Remark: This is a natural extension of logistic regression gradient descent. For $C=2$, it reduces to the logistic regression update.