Multinomial - softmax regression

Generalizing logistic regression from 2 classes to $K$ classes.

The Big Picture

---

HOW: Deriving softmax from first principles

Step 1 — make things positive. The exponential $e^{z_k}$ is positive for any real $z_k$. Why this step? Logits can be negative; probabilities cannot. $e^{(\cdot)}$ is the natural positive, monotone map.

Step 2 — make them sum to 1. Divide each by the total: $p_k = \frac{e^{z_k}}{\sum_j e^{z_j}}$ Why this step? Dividing by the sum forces $\sum_k p_k = 1$ automatically — it's just normalization.

---

The Loss: Cross-Entropy (derived from Maximum Likelihood)

Derivation. For one example with true class $y$, the likelihood is $p_y$. Over $N$ independent examples: $\mathcal{L} = \prod_{i=1}^N p_{y^{(i)}}^{(i)}$ Take negative log-likelihood (NLL): $J = -\frac{1}{N}\sum_{i=1}^N \log p_{y^{(i)}}^{(i)}$ Using a one-hot label vector $\mathbf t^{(i)}$ (where $t_k = 1$ if $k=y^{(i)}$ else 0): $\boxed{\;J = -\frac{1}{N}\sum_{i=1}^N \sum_{k=1}^K t_k^{(i)}\,\log p_k^{(i)}\;}$ Why this form? The inner sum picks out only the true class's $\log p$, since all other $t_k=0$.

---

The Gradient (the beautiful result)

Derivation sketch. Key fact: $\frac{\partial p_k}{\partial z_m} = p_k(\delta_{km} - p_m)$ where $\delta_{km}=1$ if $k=m$ else 0. Then for a single example,

= -\sum_k t_k(\delta_{km} - p_m) = p_m - t_m$$ (using $\sum_k t_k = 1$). Since $z_m = \mathbf w_m^\top \mathbf x$: $$\boxed{\;\frac{\partial J}{\partial \mathbf w_m} = (p_m - t_m)\,\mathbf x\;}$$ > [!formula] Gradient descent update > $$\mathbf w_m \leftarrow \mathbf w_m - \eta\,(p_m - t_m)\,\mathbf x$$ --- ## Worked Examples > [!example] Example 1 — computing softmax > Logits $\mathbf z = (2,\,1,\,0)$. > - $e^2=7.389,\;e^1=2.718,\;e^0=1$. *Why?* Step 1: exponentiate. > - Sum $=11.107$. *Why?* Step 2: normalizer. > - $p = (0.665,\;0.245,\;0.090)$. *Why?* Divide each by the sum → probabilities summing to 1. ✅ Highest logit → highest prob. > [!example] Example 2 — shift-invariance check > Take $\mathbf z = (2,1,0)$ vs $\mathbf z' = (5,4,3)$ (added $+3$ to all). > - $e^5,e^4,e^3 = 148.4,54.6,20.1$, sum $=223.1$. > - $p' = (0.665,0.245,0.090)$ — **identical** to Example 1. > - *Why this step?* Adding constant $c$ multiplies every $e^{z_k}$ by $e^c$, which cancels in the ratio. This is why we can subtract $\max(z)$ for numerical stability. > [!example] Example 3 — one gradient step > Suppose true class $y=1$ (one-hot $\mathbf t=(1,0,0)$), predicted $p=(0.665,0.245,0.090)$. > - Error $= p - t = (-0.335,\;0.245,\;0.090)$. *Why?* Class 1 prob is too low → negative error pushes $\mathbf w_1$ to increase $z_1$. > - With $\mathbf x=(1,2)$, $\nabla_{\mathbf w_1}J = (-0.335)(1,2) = (-0.335,-0.670)$. > - Update $\mathbf w_1 \leftarrow \mathbf w_1 - \eta(-0.335,-0.670)$ increases $\mathbf w_1$ → raises $z_1$ next time. *Why?* Model learns to trust class 1 more for this input. ✅ --- ## Common Mistakes (Steel-manned) > [!mistake] "I need $K$ full independent parameter sets, all identifiable." > *Why it feels right:* one weight vector per class seems symmetric and complete. > *The fix:* Softmax is over-parameterized — adding a constant to all logits does nothing. There's effectively $(K-1)$ independent sets. You *can* fix $\mathbf w_K=0$ (like binary logistic), but in practice keeping all $K$ + regularization is fine and cleaner. > [!mistake] "Compute $e^{z_k}$ directly, then divide." > *Why it feels right:* it's the literal formula. > *The fix:* Large logits overflow ($e^{1000}=\infty$). Always use the **log-sum-exp trick**: subtract $\max_k z_k$ first. By shift-invariance the answer is unchanged but numerically safe. > [!mistake] "Cross-entropy sums over all classes, so I need each class's $\log p$." > *Why it feels right:* the formula shows $\sum_k$. > *The fix:* One-hot $t_k$ zeroes out every term except the true class, so effectively $J=-\log p_{\text{true}}$. Don't waste compute — index directly. > [!mistake] "Softmax and sigmoid are unrelated." > *Fix:* Sigmoid = softmax at $K=2$ using logit *difference*. They're the same family. --- ## Active Recall > [!recall]- What three properties must softmax outputs satisfy, and how does the formula guarantee each? > Positive (via $e^{z_k}$), sum to 1 (via dividing by $\sum_j e^{z_j}$), monotone in logits (exp is increasing). > [!recall]- Why is the softmax + cross-entropy gradient simply $(p-t)\mathbf x$? > The $\frac{1}{p_k}$ from $\log$ derivative cancels the $p_k$ in $\partial p_k/\partial z_m$, and $\sum_k t_k = 1$ collapses the rest, leaving $p_m - t_m$. > [!recall]- Why subtract $\max(z)$ before exponentiating? > Shift-invariance: it leaves probabilities unchanged but prevents numerical overflow. > [!recall]- (Feynman, explain to a 12-year-old) > Imagine judges scoring 3 contestants (raw scores can be anything, even negative). First you "boost" each score by putting it as a power of the magic number $e$ so all are positive and big scores get much bigger. Then you split the whole pie of 100% among them by how big their boosted score is. Every contestant gets a slice, all slices add to the full pie. To teach the machine, you look at who actually won: if the true winner got too small a slice, you nudge that contestant's rules to score higher next time. > [!mnemonic] **"EXP-onentiate, then SHARE the pie."** > E-S: **E**xp everything (positive), **S**hare by dividing by the total (sums to 1). And the gradient is just **"predicted minus true, times input."** --- ## Connections - [[Logistic Regression]] — softmax is its $K$-class generalization ($K=2$ ⇒ sigmoid). - [[Cross-Entropy Loss]] — derived here from maximum likelihood. - [[Maximum Likelihood Estimation]] — the principle behind the loss. - [[Gradient Descent]] — uses the $(p-t)\mathbf x$ update. - [[Log-Sum-Exp Trick]] — numerical stability for softmax. - [[Neural Network Output Layer]] — softmax is the standard multiclass head. - [[One-Hot Encoding]] — label representation $\mathbf t$. #flashcards/ai-ml Softmax formula for class k ::: $p_k = e^{z_k} / \sum_j e^{z_j}$ Why exponentiate the logits ::: To force outputs positive (and monotone), since logits can be negative. Why divide by the sum ::: To normalize so probabilities sum to 1. Softmax with K=2 reduces to ::: The sigmoid of the logit difference, $\sigma(z_1 - z_2)$. Softmax + cross-entropy gradient wrt logit m ::: $p_m - t_m$. Gradient wrt weight vector w_m ::: $(p_m - t_m)\,\mathbf{x}$. Cross-entropy loss (one-hot) ::: $J = -\frac1N\sum_i \sum_k t_k^{(i)}\log p_k^{(i)}$. Log-sum-exp / stability trick ::: Subtract $\max_k z_k$ from all logits before exp; softmax is shift-invariant. Why softmax is over-parameterized ::: Adding a constant to every logit leaves probabilities unchanged, so only K−1 sets are identifiable. Derivative identity for softmax ::: $\partial p_k/\partial z_m = p_k(\delta_{km}-p_m)$. ## 🖼️ Concept Map ```mermaid flowchart TD BIN[Binary logistic regression] NEED[Need K probabilities positive and sum to 1] LOGITS[Logits zk = wk dot x] EXP[Exponential makes positive] NORM[Divide by sum normalizes] SOFTMAX[Softmax distribution] SIGMOID[Sigmoid] SHIFT[Shift-invariance] MLE[Maximum Likelihood] CE[Cross-entropy loss] GRAD[Clean gradient p minus t] BIN -->|generalize to K classes| NEED NEED -->|requires| LOGITS LOGITS -->|Step 1| EXP EXP -->|Step 2| NORM NORM -->|yields| SOFTMAX SOFTMAX -->|K=2 reduces to| SIGMOID SOFTMAX -->|adding c changes nothing| SHIFT MLE -->|neg log-likelihood| CE SOFTMAX -->|plugged into| CE CE -->|differentiate| GRAD ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Dekho, logistic regression sirf do class (0 ya 1) ke liye kaam karta hai. Lekin agar tumhe 10 digits pehchanne hain, ya cat/dog/bird classify karna hai, tab tumhe $K$ classes chahiye. Yahan aata hai **softmax regression**. Har class ke liye ek weight vector $\mathbf w_k$ rakhte hain, aur raw score nikaalte hain jise **logit** $z_k = \mathbf w_k^\top \mathbf x$ kehte hain. Ye logits kuch bhi ho sakte hain — negative bhi. > > Ab problem: probability toh hamesha positive honi chahiye aur sabka sum 1 hona chahiye. Iska simple do-step solution: pehle har logit ko $e^{z_k}$ se exponentiate karo (isse sab positive ho jaate hain), phir sab ko unke total se divide kar do (isse sum 1 ho jaata hai). Bas — yahi softmax hai: "EXP karo, phir pie baant do". Ek mast property: agar tum sab logits mein same number add kar do, probability bilkul nahi badalti (shift-invariant). Isi wajah se overflow bachane ke liye hum $\max(z)$ subtract kar dete hain. > > Training ke liye loss hai **cross-entropy**, jo maximum likelihood se nikalta hai — matlab jo sahi class hai uski probability ko high karna. Kamaal ki baat: softmax aur cross-entropy milke gradient itna clean deta hai — sirf $(p_m - t_m)\mathbf x$. Yaani "predicted minus true, times input". Agar sahi class ki probability kam thi, gradient us class ka weight badha dega taaki agli baar zyada confident ho. Yaad rakho: $K=2$ pe softmax bilkul sigmoid ban jaata hai, toh ye sab ek hi family hai — bas ye badi generalization hai. ![[audio/2.2.12-Multinomial---softmax-regression.mp3]]