10.4 Multinomial Classification

Introduction

Multinomial (multi-class) classification extends binary classification to K > 2 classes. This is essential for real-world applications like image recognition (1000+ classes), language models (vocabulary of 50K+ tokens), and document categorization. We explore softmax regression and strategies for multi-class problems.

1. From Binary to Multi-Class

Binary logistic regression uses sigmoid to model probability of two classes. For K classes, we need:

• K probability outputs (one per class)
• Probabilities must sum to 1
• All probabilities between 0 and 1

Solution: Softmax function generalizes sigmoid to multiple classes.

2. Softmax Function

For K classes, compute K linear combinations (logits): $$z_k = \mathbf{w}_k^T \mathbf{x} + b_k \quad \text{for } k = 1, 2, ..., K$$

Softmax converts logits to probabilities: $$P(y = k | \mathbf{x}) = \text{softmax}(z_k) = \frac{e^{z_k}}{\sum_{j=1}^{K} e^{z_j}}$$

Properties

• Output: \(P(y=k|\mathbf{x}) \in (0, 1)\) for all k
• Sum: \(\sum_{k=1}^{K} P(y=k|\mathbf{x}) = 1\)
• Monotonic: Larger logit → larger probability
• For K=2, softmax reduces to sigmoid
• Temperature parameter controls confidence (higher temp → more uniform)

3. Softmax Regression Model

For input \(\mathbf{x} \in \mathbb{R}^d\) and K classes, we have:

• Weight matrix \(\mathbf{W} \in \mathbb{R}^{K \times d}\) (one weight vector per class)
• Bias vector \(\mathbf{b} \in \mathbb{R}^K\) (one bias per class)

Model: $$P(y = k | \mathbf{x}, \mathbf{W}, \mathbf{b}) = \frac{\exp(\mathbf{w}_k^T \mathbf{x} + b_k)}{\sum_{j=1}^{K} \exp(\mathbf{w}_j^T \mathbf{x} + b_j)}$$

Prediction: $$\hat{y} = \arg\max_{k} P(y = k | \mathbf{x})$$

4. Cross-Entropy Loss

For multi-class classification, use categorical cross-entropy: $$L(\mathbf{W}, \mathbf{b}) = -\frac{1}{n}\sum_{i=1}^{n} \sum_{k=1}^{K} \mathbb{1}[y_i = k] \log P(y = k | \mathbf{x}_i)$$

Using one-hot encoding \(\mathbf{y}_i \in \{0,1\}^K\) where \(y_{ik} = 1\) if \(x_i\) belongs to class k: $$L = -\frac{1}{n}\sum_{i=1}^{n} \mathbf{y}_i^T \log \hat{\mathbf{y}}_i$$

where \(\hat{\mathbf{y}}_i\) is vector of predicted probabilities for all K classes.

5. Gradient Computation

Gradient with respect to weights for class k: $$\frac{\partial L}{\partial \mathbf{w}_k} = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}_{ik} - y_{ik}) \mathbf{x}_i$$

where:

• \(\hat{y}_{ik}\) = predicted probability for class k
• \(y_{ik}\) = 1 if true class is k, else 0

Same elegant form as binary: (prediction - truth) × feature

6. One-vs-Rest (One-vs-All)

Alternative approach: Train K binary classifiers, one per class.

Algorithm

1. For each class k = 1, ..., K:
2. Create binary dataset: class k vs all other classes
3. Train binary classifier \(f_k(\mathbf{x})\)
4. Prediction: \(\hat{y} = \arg\max_k f_k(\mathbf{x})\)

Advantages

• Simple: Reuse binary classification methods
• Parallelizable: Train K classifiers independently
• Works with any binary classifier (SVM, logistic regression, etc.)

Disadvantages

• Imbalanced training data (1 class vs K-1 classes)
• Scores from different classifiers not directly comparable
• Less statistically efficient than softmax

7. One-vs-One

Another strategy: Train binary classifier for every pair of classes.

Algorithm

1. Train \(\binom{K}{2} = \frac{K(K-1)}{2}\) binary classifiers
2. Each classifier distinguishes between classes i and j
3. Prediction: Voting scheme (class with most votes wins)

Comparison

Method	# Classifiers	Training Data per Classifier	Prediction
Softmax	1 (multi-output)	All data	Single forward pass
One-vs-Rest	K	All data (imbalanced)	K evaluations
One-vs-One	K(K-1)/2	Subset (balanced)	K(K-1)/2 evaluations + voting

8. Temperature Scaling

Softmax with temperature parameter T: $$P(y = k | \mathbf{x}) = \frac{\exp(z_k / T)}{\sum_{j=1}^{K} \exp(z_j / T)}$$

• T = 1: Standard softmax
• T → 0: Approaches argmax (one-hot, peaked distribution)
• T → ∞: Approaches uniform distribution (1/K for all classes)

Used in LLMs to control sampling diversity (high temperature = more creative, low = more deterministic).

9. Label Smoothing

Instead of hard one-hot labels, use soft labels: $$y_k^{\text{smooth}} = \begin{cases} 1 - \epsilon & \text{if } k = \text{true class} \\ \frac{\epsilon}{K-1} & \text{otherwise} \end{cases}$$

where \(\epsilon \in [0, 1)\) is smoothing parameter (typically 0.1).

Benefits

• Prevents overconfidence (model never predicts probability 1)
• Improved calibration (predicted probabilities match true frequencies)
• Better generalization
• Regularization effect

10. Hierarchical Classification

For large K, hierarchical structure can be more efficient and interpretable.

Two-Level Hierarchy Example

• Level 1: Classify into coarse categories (e.g., animal, vehicle, object)
• Level 2: Within category, classify into specific class (e.g., cat, dog, bird)

Benefits: Faster prediction, incorporates domain knowledge, handles class imbalance better.

11. Calibration

Well-calibrated classifier: predicted probability matches true frequency.

Example: Among predictions with probability 0.7, approximately 70% should be correct.

Calibration Plot

Plot predicted probability vs observed frequency. Perfect calibration: diagonal line.

12. Application to LLMs

Softmax is fundamental in language models:

• Next token prediction: Softmax over entire vocabulary (50K+ classes)
• Output layer: Final layer produces logits, softmax converts to probabilities
• Sampling: Temperature controls generation diversity
• Top-k sampling: Sample from k most likely tokens
• Nucleus (top-p) sampling: Sample from smallest set with cumulative probability p

13. Computational Considerations

Numerical Stability

Computing softmax directly can cause overflow/underflow. Use log-sum-exp trick: $$\text{softmax}(z_k) = \frac{\exp(z_k - \max_j z_j)}{\sum_j \exp(z_j - \max_j z_j)}$$

Large K

For very large number of classes (e.g., LLM vocabulary):

• Hierarchical softmax: Binary tree structure, O(log K) instead of O(K)
• Negative sampling: Sample small subset of negative classes
• Adaptive softmax: Different computation for frequent vs rare tokens

Key Takeaways

• Softmax extends sigmoid to multiple classes, ensuring valid probability distribution
• Multi-class cross-entropy is natural loss function for softmax regression
• One-vs-Rest and One-vs-One convert multi-class to binary problems
• Temperature scaling controls confidence and diversity in predictions
• Label smoothing prevents overconfidence and improves calibration
• Calibration ensures predicted probabilities match true frequencies
• Softmax is fundamental to LLM output layers and token prediction
• Numerical stability and efficiency important for large vocabularies