Entropy and KL divergence: Exercises — Hinglish deep dive

1.3.18 · D4 · AI-ML › Probability & Statistics › Entropy aur KL divergence

Yeh page Entropy and KL divergence ki self-testing ke liye hai. Har problem ek complete worked solution chhupati hai — pehle khud try karo, phir reveal karo. Levels L1 Recognition se L5 Mastery tak charhte hain. Har level ke end mein ek trap hai jismein aasaani se fas sakte ho — usse is tarah explain kiya gaya hai ki galat raasta kyun sahi lagta hai.

Intuition Is page par jo notation use hogi — pehle samajh lo

Symbols problems mein aane se pehle, yahan bataya gaya hai ki har ek kya hai, simple shabdon mein:

$p (x)$ — probability ki random cheez outcome $x$ par land karegi. $0$ aur $1$ ke beech ka ek number; sab milake $1$ hote hain.
$lo g_{2}$ — poochha jaata hai "2 ki kaunsi power yeh number deti hai?" Hum base $2$ use karte hain kyunki information ko bits mein measure karte hain (haan/nahi ke jawab). $lo g_{2} 8 = 3$ kyunki $2^{3} = 8$ .
$ln$ (natural log, base $e \approx 2.718$ ) — wohi sawaal, alag base. Iska unit nats hai. Convert karo $lo g_{2} x = ln x / ln 2$ se.
$H (X) = - \sum_{x} p (x) lo g_{2} p (x)$ — entropy, har observation par average bits of surprise.
$D_{K L} (p ∥ q) = \sum_{x} p (x) lo g \frac{p ( x )}{q ( x )}$ — KL divergence, extra bits jo waste hoti hain jab model $q$ use karo jabki sach $p$ hai.
$H (p, q) = - \sum_{x} p (x) lo g q (x)$ — cross-entropy, $q$ ke under code length jab sach $p$ hai.

Level 1 — Recognition

Exercise 1.1 (L1)

Ek coin fair hai: $p (H) = p (T) = 0.5$ . Bits mein $H (X)$ kya hai?

Recall Solution

Kya karte hain: $H (X) = - \sum p lo g_{2} p$ mein plug in karo. $H (X) = - [0.5 lo g_{2} 0.5 + 0.5 lo g_{2} 0.5]$ Kyun: $lo g_{2} 0.5 = - 1$ kyunki $2^{- 1} = 0.5$ . $= - [0.5 (- 1) + 0.5 (- 1)] = 1 bit$ Answer: $1$ bit. Ek binary sawaal ("heads?") sab settle kar deta hai.

Exercise 1.2 (L1)

Ek variable deterministic hai: $p (5) = 1$ aur baaki har outcome ki probability $0$ hai. $H (X)$ kya hai?

Recall Solution

Sirf $x = 5$ wala term bachta hai (baaki ke liye convention $0 lo g 0 = 0$ use hoti hai): $H (X) = - 1 \cdot lo g_{2} 1 = - 1 \cdot 0 = 0 bits$ Answer: $0$ bits. Koi surprise nahi — tum pehle se outcome jaante ho.

Exercise 1.3 (L1)

Kaun sa sach hai, aur kyun? (a) $D_{K L} (p ∥ q) = D_{K L} (q ∥ p)$ hamesha. (b) $D_{K L} (p ∥ q) \geq 0$ hamesha.

Recall Solution

(a) galat hai — KL asymmetric hai; dono arguments alag roles play karte hain (kaun "truth" hai aur kaun "model"). (b) sach hai — Gibbs' inequality se, KL kabhi negative nahi hoti, aur equals $0$ sirf tab jab $p = q$ . Answer: (b).

Level 2 — Application

Exercise 2.1 (L2)

Ek biased coin mein $p (H) = 0.9, p (T) = 0.1$ hai. Bits mein $H (X)$ compute karo.

Recall Solution

$H (X) = - [0.9 lo g_{2} 0.9 + 0.1 lo g_{2} 0.1]$ $lo g_{2} 0.9 = - 0.152$ , $lo g_{2} 0.1 = - 3.322$ . $= - [0.9 (- 0.152) + 0.1 (- 3.322)] = 0.137 + 0.332 = 0.469 bits$ Answer: $\approx 0.469$ bits. Fair coin ke $1$ bit se kam uncertainty — zyada tar heads aata hai, toh seekhne ko kam hai.

Exercise 2.2 (L2)

Ek fair 8-sided die: $p (x) = \frac{1}{8}$ for $x = 1, \dots, 8$ . $H (X)$ aath terms sum kiye bina nikalo.

Recall Solution

Kya karte hain: maximum-entropy shortcut use karo. $n$ outcomes par uniform distribution ke liye, $H (X) = lo g_{2} n .$ Kyun: har term $\frac{1}{n} lo g_{2} n$ hai, aur $n$ terms hain, toh sab $lo g_{2} n$ mein collapse ho jaate hain. $H (X) = lo g_{2} 8 = 3 bits$ Answer: $3$ bits. Teen haan/nahi sawaal (binary search) aath faces mein se ek identify kar dete hain.

Exercise 2.3 (L2)

True label $p = [0, 1, 0]$ (class 2); model prediction $q = [0.1, 0.7, 0.2]$ . Nats mein cross-entropy $H (p, q)$ compute karo.

Recall Solution

$H (p, q) = - [0 \cdot ln 0.1 + 1 \cdot ln 0.7 + 0 \cdot ln 0.2] = - ln 0.7$ Kyun zeros gayab hote hain: ek one-hot label saara weight class 2 par daalta hai, toh sirf uska term bachta hai. $= - (- 0.357) = 0.357 nats$ Answer: $\approx 0.357$ nats. Yeh is ek example ke liye bilkul classification loss hai.

Level 3 — Analysis

Exercise 3.1 (L3)

True coin $p = (0.5, 0.5)$ , model $q = (0.7, 0.3)$ . Bits mein $D_{K L} (p ∥ q)$ compute karo.

Recall Solution

$D_{K L} (p ∥ q) = 0.5 lo g_{2} \frac{0.5}{0.7} + 0.5 lo g_{2} \frac{0.5}{0.3}$ $lo g_{2} (0.5/0.7) = lo g_{2} 0.714 = - 0.485$ , $lo g_{2} (0.5/0.3) = lo g_{2} 1.667 = + 0.737$ . $= 0.5 (- 0.485) + 0.5 (0.737) = - 0.243 + 0.369 = 0.126 bits$ Answer: $\approx 0.126$ bits. Model $q$ use karne ka extra cost per flip jab sach $p$ hai.

Exercise 3.2 (L3)

Wohi do coins, lekin reverse $D_{K L} (q ∥ p)$ compute karo. Exercise 3.1 se compare karo.

Recall Solution

$D_{K L} (q ∥ p) = 0.7 lo g_{2} \frac{0.7}{0.5} + 0.3 lo g_{2} \frac{0.3}{0.5}$ $lo g_{2} 1.4 = 0.485$ , $lo g_{2} 0.6 = - 0.737$ . $= 0.7 (0.485) + 0.3 (- 0.737) = 0.340 - 0.221 = 0.119 bits$ Answer: $\approx 0.119$ bits. $0.126$ se alag hai — yeh seedha proof hai ki KL asymmetric hai. Ab truth $q$ hai aur $p$ model hai; aage ka weighting badal gaya.

Exercise 3.3 (L3)

$p = (0.5, 0.5)$ , $q = (0.7, 0.3)$ ke liye identity $D_{K L} (p ∥ q) = H (p, q) - H (p)$ numerically verify karo (bits use karo).

Recall Solution

$H (p) = 1$ bit (fair coin, Ex 1.1). $H (p, q) = - [0.5 lo g_{2} 0.7 + 0.5 lo g_{2} 0.3] = - [0.5 (- 0.515) + 0.5 (- 1.737)] = 0.257 + 0.868 = 1.126 bits$ Phir $H (p, q) - H (p) = 1.126 - 1 = 0.126$ bits — Exercise 3.1 se match karta hai. ✓ Answer: identity confirmed; $0.126$ bits dono taraf se.

Level 4 — Synthesis

Exercise 4.1 (L4)

Do-outcome distribution $p = (t, 1 - t)$ ke liye, entropy binary entropy $H_{b} (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t)$ hai. Dikhao ki yeh $t = 0.5$ par maximize hoti hai, derivative zero kahan hai yeh nikaal ke.

Recall Solution

Kya karte hain: $t$ ke saath differentiate karo. Natural log use karke phir convert karke, $\frac{d}{d t} H_{b} (t) = lo g_{2} \frac{1 - t}{t}$ . Kyun derivative: ek smooth concave curve ka maximum wahan hota hai jahan uski slope $0$ ho. Set karo $lo g_{2} \frac{1 - t}{t} = 0 \Rightarrow \frac{1 - t}{t} = 1 \Rightarrow t = 0.5$ . Kaisa dikhta hai: neeche figure mein $\cap$ -shaped curve bilkul center mein $t = 0.5$ par peak karti hai, height $1$ bit, aur dono ends par $0$ tak girti hai. Answer: $t = 0.5$ , jisse $H_{b} = 1$ bit milta hai — maximum.

Exercise 4.2 (L4)

True label class 2 wale ek training example ke liye cross-entropy loss, $p = [0, 1, 0]$ . Model ke logits $q = [0.2, 0.5, 0.3]$ dete hain. Nats mein loss compute karo. Phir batao kya hota hai loss ko jab model improve hota hai aur $q (class 2) \to 1$ .

Recall Solution

$H (p, q) = - ln q_{2} = - ln 0.5 = 0.693 nats$ Limiting behaviour: jab $q_{2} \to 1$ , $- ln q_{2} \to - ln 1 = 0$ — loss gayab ho jaata hai. Jab $q_{2} \to 0$ , $- ln q_{2} \to + \infty$ — infinitely confident galat prediction infinitely penalize hoti hai (KL convention se match karta hai: $p > 0, q = 0 \Rightarrow \infty$ ). Answer: $0.693$ nats; loss $\to 0$ jab model sahi class certain ho jaata hai, $\to \infty$ agar yeh true class ko zero drive kar de.

Level 5 — Mastery

Exercise 5.1 (L5)

Ek source symbols ${A, B, C, D}$ emit karta hai true probabilities $p = (0.5, 0.25, 0.125, 0.125)$ ke saath. (a) Bits mein $H (p)$ nikalo. (b) Tum uniform model $q = (0.25, 0.25, 0.25, 0.25)$ ke liye bane code se compress karte ho. Average bits used, $H (p, q)$ , nikalo. (c) Wasted bits $D_{K L} (p ∥ q)$ nikalo aur confirm karo ki $H (p, q) = H (p) + D_{K L} (p ∥ q)$ .

Recall Solution

(a) Probabilities $2$ ki powers hain, toh surprisals clean integers hain: $H (p) = - [0.5 lo g_{2} 0.5 + 0.25 lo g_{2} 0.25 + 0.125 lo g_{2} 0.125 + 0.125 lo g_{2} 0.125]$ $= - [0.5 (- 1) + 0.25 (- 2) + 0.125 (- 3) + 0.125 (- 3)] = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits$ (b) $q$ ke under, har symbol $- lo g_{2} 0.25 = 2$ bits cost karta hai, toh average $= 2$ bits regardless of $p$ : $H (p, q) = - \sum_{x} p (x) lo g_{2} 0.25 = 2 \sum_{x} p (x) = 2 bits$ (c) Wasted: $D_{K L} (p ∥ q) = H (p, q) - H (p) = 2 - 1.75 = 0.25 bits$ Identity check: $H (p) + D_{K L} = 1.75 + 0.25 = 2 = H (p, q)$ . ✓ Answer: $H (p) = 1.75$ , $H (p, q) = 2$ , $D_{K L} = 0.25$ bits. Uniform code quarter bit per symbol waste karta hai kyunki yeh ignore karta hai ki $A$ common hai.

Exercise 5.2 (L5)

Mixture / connective reasoning. Mixture $m = \frac{1}{2} (p + q)$ define karo aur Jensen–Shannon quantity $JSD (p, q) = \frac{1}{2} D_{K L} (p ∥ m) + \frac{1}{2} D_{K L} (q ∥ m)$ . $p = (1, 0)$ aur $q = (0, 1)$ ke liye bits mein JSD compute karo.

Recall Solution

Mixture: $m = (0.5, 0.5)$ . Pehla KL: $D_{K L} (p ∥ m) = 1 \cdot lo g_{2} \frac{1}{0.5} + 0 \cdot (\dots) = lo g_{2} 2 = 1$ bit ( $q$ -side term mein $p = 0$ weight hai → $0$ ). Doosra KL: symmetry se $D_{K L} (q ∥ m) = 1$ bit. $JSD = \frac{1}{2} (1) + \frac{1}{2} (1) = 1 bit$ Answer: $JSD = 1$ bit — maximum, correctly finite even though $D_{K L} (p ∥ q) = \infty$ yahan hai (kyunki jahan $p > 0$ wahan $q = 0$ hai). Yahi exactly wajah hai ki Jensen-Shannon Divergence ek symmetric, hamesha-finite alternative ke roop mein prefer ki jaati hai, aur KL Evidence Lower Bound (ELBO) aur Variational Autoencoders mein kaise enter karta hai.

Recall Quick self-check (cloze)

$n$ outcomes par Uniform entropy ::: $lo g_{2} n$ KL zero exactly tab hota hai jab ::: $p = q$ har jagah Cross-entropy minus entropy equal hai ::: $D_{K L} (p ∥ q)$ Binary entropy peak karta hai $t =$ par ::: $0.5$ , giving $1$ bit Ek confident wrong prediction ( $q \to 0$ jahan $p > 0$ ) loss ko banata hai ::: $\to \infty$

Dekho bhi: Mutual Information, Maximum Entropy Principle, Cross-Entropy Loss, Information Gain, F-divergences.