Entropy and KL divergence: Visual walkthrough — Hinglish deep dive

1.3.18 · D2 · AI-ML › Probability & Statistics › Entropy and KL divergence

Ye page parent topic ka central result — KL divergence formula — sirf ek coin aur ek sawaal se rebuild karta hai. Har step ko hum draw karenge. End tak aap dekh paoge kyun

$D_{K L} (p ∥ q) = \sum_{x} p (x) lo g \frac{p ( x )}{q ( x )}$

exactly "wo extra bits hain jo aap waste karte ho jab aap duniya ke baare mein galat story believe karte ho."

Yahan ye assume nahi kiya gaya ki aap jaante ho ki logarithm kis liye hota hai, "bits" ka matlab kya hai, ya hum sum kyun karte hain. Har piece ko hum pehle ek picture pe build karte hain.

Step 1 — Ek "message" kya hota hai aur hum bits kyun count karte hain?

KYA hum set up karte hain: ek random outcome (ek coin, ek die, ek weather label) aur ek rule jo har possible outcome ko 0s aur 1s ki string mein convert karta hai. Wo rule ek code hai.

KYU hum care karte hain: kam bits = saste messages = better compression = (baad mein) better loss functions. Is page pe har quantity secretly ek bit count hai.

PICTURE: neeche, char possible outcomes ko chhote binary tags milte hain. Giniye kitne haan/na splits lagte hain har leaf tak pahunchne mein — woh count us outcome ki bit-length hai.

Step 2 — Outcome $x$ ke liye best length $- lo g_{2} p (x)$ kyun hoti hai

Yahan logarithm enter karta hai. Hume justify karna hoga kyun log, aur koi doosra function nahi.

KYA hum claim karte hain: agar outcome $x$ , probability $p (x)$ se hota hai, toh sabse chhota possible average code use ek length deta hai

$bits for x ℓ (x) = "surprisal" - lo g_{2} p (x) .$

LOG KYU? Har yes/no split abhi-bhi-possible outcomes ki count roughly aadhi kar deta hai. Ek outcome ko $n$ equally likely choices mein se pin down karne ke liye aapko $n$ ko $1$ tak halve karna hoga — matlab $lo g_{2} n$ halvings. Agar ek outcome ki probability $p$ hai, toh woh $\frac{1}{p}$ equally likely choices mein se ek choice jaisa behave karta hai, isliye use $lo g_{2} \frac{1}{p} = - lo g_{2} p$ splits chahiye. Log literally "kitni baar main halve kar sakta hun jab tak sure nahi ho jaata?" hai. Koi doosra function halvings count nahi karta.

Formula ko term by term padhiye:

$p (x)$ — outcome $x$ kitna common hai. Bada $p$ → common → kam bits.
$\frac{1}{p ( x )}$ — "kitne mein se ek" ye outcome lagta hai.
$lo g_{2}$ — "kitne mein se ek" ko "kitne yes/no halvings" mein convert karta hai.
minus sign — kyunki $p \leq 1$ se $lo g_{2} p$ negative hota hai; hum ise flip karte hain taaki lengths positive aayein.

PICTURE: curve $- lo g_{2} p$ . Certain events ( $p = 1$ ) height $0$ pe hain — koi bits nahi, koi surprise nahi. Rare events upar jaate hain.

Step 3 — Surprises ka average lena entropy $H (p)$ deta hai

KYA hum karte hain: outcomes sabka cost same nahi hota, isliye hum average bit-length lete hain, har outcome ko weight karte hue uski actual frequency se.

$H (p) = sab outcomes pe add karo x \sum kitni baar x hota hai p (x) \cdot uski bit-length (- lo g_{2} p (x)) .$

$p (x)$ se weight kyun karo? Kyunki ek rare outcome expensive hota hai lekin rarely bheja jaata hai, isliye long-run average mein use kam count karna chahiye. "Expected value" = probability-weighted sum. Exactly yahi $\sum_{x} p (x) (\dots)$ pattern ka matlab hai.

PICTURE: surprisal height $- lo g_{2} p (x)$ ke bars, har ek apni width $p (x)$ se shrunk; shaded total area $H (p)$ hai — average message length agar aap $p$ ke liye best code use karo.

Step 4 — Galti: $q$ ke liye coding karna jab reality $p$ hai

Ab woh twist jo KL divergence create karta hai.

KYA hota hai: aap believe karte ho ki outcomes ek distribution $q$ follow karti hain (aapka model, aapka guess). Toh aap $q$ ke liye optimal code banate ho: outcome $x$ ko length $- lo g_{2} q (x)$ milti hai. Lekin reality actually $p$ follow karti hai. Aapke messages abhi bhi us frequency pe bheje jaate hain jo $p$ dictate karta hai.

KYU ye matter karta hai: aapki bit-lengths $q$ se aati hain, lekin kitni-baar wali weighting $p$ se aati hai. Average length ab yeh hai

$H (p, q) = \sum_{x} real frequency p (x) \cdot aapke galat code se length (- lo g_{2} q (x)) .$

Yeh mismatched average cross-entropy $H (p, q)$ hai.

PICTURE: same outcomes ke liye do codes side by side. Left (blue) $q$ ke liye banaya gaya hai — yeh us outcome ko short banata hai jise $q$ common samajhta hai. Lekin reality (pink bars, $p$ follow karte hue) ek alag outcome sabse zyada bhejti hai, toh galat code pe real frequent outcome ek lamba branch pe pada. Yellow mein wasted length.

Step 5 — Subtract karo: waste hi KL divergence hai

KYA hum compute karte hain: extra bits jo aap galat code use karne ke liye pay karte ho = (jo aapne actually pay kiya) − (jo aap best case mein pay kar sakte the).

$D_{K L} (p ∥ q) = q ke code se pay kiya H (p, q) - best, p ke code se H (p) .$

SUBTRACT KYU? Kyunki "waste" sirf best possible ke relative sense mein samajh aata hai. Dono terms same real frequencies $p$ ke under average bit-lengths hain; unka difference aapke galat belief ka pure penalty hai.

Ab dono expand karo aur dekho terms combine hote hue:

$D_{K L} (p ∥ q) = (- \sum_{x} p (x) lo g_{2} q (x)) - (- \sum_{x} p (x) lo g_{2} p (x))$

Common $p (x)$ aur common sum ko saath kheechio:

$= \sum_{x} p (x) [ek ratio ka log lo g_{2} p (x) - lo g_{2} q (x)] = \sum_{x} p (x) lo g_{2} \frac{p ( x )}{q ( x )} .$

Bracket mein ek rule use hua: $lo g a - lo g b = lo g \frac{a}{b}$ — logs subtract karna = andar divide karna. Yahi poori algebra hai.

PICTURE: lamba cross-entropy bar minus chhota entropy bar; bacha hua slab (yellow) $D_{K L}$ hai — extra bits, term by term.

Term-by-term, right wahan jahan har symbol hai:

$p (x)$ (bahar) — real frequency: jo outcomes kabhi actually hote hi nahi unke penalties ignore hote hain.
$\frac{p ( x )}{q ( x )}$ — "reality aapke model ke thought se kitni zyada (ya kam) common hai."
$lo g_{2}$ — us ratio ko bits mein convert karta hai; ratio $= 1$ (aap sahi the) → $lo g_{2} 1 = 0$ → koi penalty nahi.

Step 6 — Yeh kabhi negative kyun nahi hota (Jensen ki ek picture)

KYA hum prove karte hain: $D_{K L} (p ∥ q) \geq 0$ , aur yeh $0$ hai sirf tabhi jab $q = p$ har jagah ho. Aap galat hokar kabhi bits save nahi kar sakte.

KYUN believe karein? Ratio flip karo aur log curve ke baare mein ek fact use karo: $lo g$ concave hota hai (neeche jhukta hai, frown jaisa). Ek concave curve ke liye, curve ki heights ka average, average input ke upar curve ke neeche hota hai — yahi Jensen's inequality hai.

$D_{K L} (p ∥ q) = - \sum_{x} p (x) lo g_{2} \frac{q ( x )}{p ( x )} \geq - lo g_{2} (= \sum_{x} q (x) = 1 x \sum p (x) \frac{q ( x )}{p ( x )}) = - lo g_{2} 1 = 0.$

$p (x)$ denominator ke $p (x)$ ko cancel kar deta hai, bacha rehta hai $\sum_{x} q (x) = 1$ kyunki $q$ ek probability distribution hai. Toh poori cheez $\geq - lo g_{2} 1 = 0$ hai.

PICTURE: concave $lo g$ curve; uske neeche ek straight chord; "heights ka average" aur "average ki height" ke beech ka gap exactly KL penalty hai — yeh zero tab hi band hota hai jab saare ratios $1$ ke equal hon.

Recall Zero sirf tab kyun jab p = q ho

Jensen mein equality kab hold hoti hai ::: Jab input $\frac{q ( x )}{p ( x )}$ har $x$ ke liye same constant ho; kyunki dono sum to 1 hain, woh constant 1 hai, yaani $q = p$ .

Step 7 — Degenerate cases (reader ko kabhi stuck mat rehne do)

Formulas zeros pe break hote hain. Yahan har edge hai, drawn.

PICTURE: ratio-to-penalty curve $lo g_{2} r$ jisme teen regimes mark hain: $r = 1$ zero penalty ka pit, $r \to \infty$ (model reality ke against zyada confident hai) rising, aur $q = 0$ wall $+ \infty$ pe.

Step 8 — Picture pe numbers (worked, dono directions mein)

Ek-picture summary

Upar jo kuch bhi hai woh ek subtraction hai: aapki average message length (galat story $q$ use karke) minus sabse chhoti possible length (true story $p$ ). Jo bachta hai woh $D_{K L}$ hai.

Recall Feynman retelling (zor se bolo)

Ek dost aapko coin results haan/na answers ke roop mein bhejta rehta hai. Agar aap true odds $p$ jaante, aap ek codebook design karte jo common outcomes ko chhote tags deta — aapka bill average $H (p)$ bits hota, sabse sasta possible. Lekin aapne sirf odds $q$ guess kiye, isliye aapne codebook $q$ ke liye banaya. Reality abhi bhi outcomes rate $p$ pe bhejti hai, toh aapka bill ab $H (p, q)$ hai, jo bada hota hai jab bhi aapka guess galat tha. Overcharge — galat story believe karne ke wasted bits — $D_{K L} (p ∥ q) = \sum_{x} p (x) lo g_{2} \frac{p ( x )}{q ( x )}$ hai. Yeh kabhi negative nahi hota (aap true codebook ko beat nahi kar sakte — Jensen iska guarantee deta hai), exactly zero sirf tab hota hai jab aapka guess perfect tha, infinity tak explode hota hai agar aapne kisi aisi cheez pe zero bet lagaya jo actually hoti hai, aur symmetric nahi hai kyunki overcharge is baat pe depend karta hai ki kaun actually flip kar raha hai. Is overcharge ko minimize karna hi woh hai jo ek classifier, ek ELBO, ya ek VAE train karna quietly kar raha hota hai.

Aage kahan jaata hai: Mutual Information (ek joint aur uski independent copy ke beech KL), Maximum Entropy Principle (Step 3 apni limit tak push kiya), Information Gain (ek split se entropy drop), aur F-divergences (KL ek poori family ka ek member hai).