Entropy and KL divergence

1.3.18 · AI-ML › Probability & Statistics

Overview

Entropy average uncertainty ya information content ko measure karta hai ek probability distribution mein. KL divergence measure karta hai ki ek probability distribution doosre se kitni alag hai. Dono machine learning ke liye foundational hain: entropy decision trees, loss functions, aur compression ko guide karta hai; KL divergence variational inference, GANs, aur policy optimization ko power karta hai.

Shannon Entropy

First Principles Se Derivation

Goal: "Average surprise" ka ek measure design karo jo ye satisfy kare:

1. Additivity: Independent events ki information add hoti hai
2. Monotonicity: Rare events zyada surprise carry karte hain
3. Continuity: Chhoti probability changes → chhoti entropy changes

Step 1: Ek single outcome ke liye surprise

• Agar outcome $x$ ki probability $p(x)$ hai, toh uska surprisal (information content) define karo: $I(x)=-{\log }_{2}p(x)$

Ye step kyun? Humein surprise ko probability badhne ke saath ghatana chahiye. Ek certain event ($p=1$) ka surprise zero hona chahiye: $-{\log }_2(1)=0$. Ek rare event ($p=0.01$) ka surprise high hota hai: $-{\log }_2(0.01)\approx 6.64$ bits. Log ki wajah se independent events ki information add hoti hai: $I(x,y)=I(x)+I(y)$ jab $x,y$ independent hon.

Step 2: Saare outcomes par average surprise $H(X)={\mathbb{E}}_{x\sim p}[I(x)]={\sum }_{x}p(x)\cdot (-{\log }_{2}p(x))=-{\sum }_{x}p(x){\log }_{2}p(x)$

Ye step kyun? Entropy wo expected information hai jo tumhe $X$ observe karne par milti hai. Probability ke hisaab se weighted average.

Maximum Entropy ka Proof (uniform distribution ise achieve karta hai): Maano $u(x)=\frac{1}{n}$ kisi $n$ outcomes par uniform distribution hai. Gibbs' inequality use karo: kisi bhi do distributions $p,q$ ke liye, $-{\sum }_{x}p(x)\log p(x)\le -{\sum }_{x}p(x)\log q(x)$ equality tab jab $p=q$.

$q=u$ set karo: $H(X)=-{\sum }_{x}p(x)\log p(x)\le -{\sum }_{x}p(x)\log \frac{1}{n}=\log n$ Equality tab jab $p(x)=\frac{1}{n}$ saare $x$ ke liye.

Kullback-Leibler (KL) Divergence

Derivation: Ye Formula Kyun?

Context: Tum distribution $p$ ke liye ek optimal code design kar rahe ho, lekin galti se $q$ ke liye optimize kiya hua code use kar lete ho. Kitni extra information transmit hogi?

Step 1: $p$ ke liye optimal code length $p$ ka code use karte hue, average message length = $H(p)=-{\sum }_{x}p(x)\log p(x)$

Step 2: $q$ ka code use karne par actual code length Agar tum $q$ ka code use karke encode karo (jo outcome $x$ ko $-\log q(x)$ bits assign karta hai), lekin outcomes $p$ ko follow karen, toh average length = $-{\sum }_{x}p(x)\log q(x)$ (ise cross-entropy $H(p,q)$ kehte hain).

Step 3: Extra cost $D_{KL}(p\Vert q)=H(p,q)-H(p)=-{\sum }_{x}p(x)\log q(x)-\left(-{\sum }_{x}p(x)\log p(x)\right)$ $={\sum }_{x}p(x)[\log p(x)-\log q(x)]={\sum }_{x}p(x)\log \frac{p(x)}{q(x)}$

Ye step kyun? Cross-entropy $q$ ke under code length hai, entropy $p$ ke under optimal length hai. Difference inefficiency hai.

Non-negativity ka Proof (Gibbs' inequality): $D_{KL}(p\Vert q)=-{\sum }_{x}p(x)\log \frac{q(x)}{p(x)}$ Concave function $\log$ par Jensen's inequality use karo: $-{\sum }_{x}p(x)\log \frac{q(x)}{p(x)}\ge -\log \left({\sum }_{x}p(x)\frac{q(x)}{p(x)}\right)=-\log \left({\sum }_{x}q(x)\right)=-\log 1=0$ Equality iff $\frac{q(x)}{p(x)}$ constant ho, yani $p=q$.

Cross-Entropy

Machine learning mein, jab $p$ true label distribution ho (aksar one-hot) aur $q$ model ki predicted probabilities ho, toh cross-entropy minimize karna = KL divergence minimize karna (kyunki $H(p)$ constant hai).

Machine Learning Mein Applications

1. Decision Trees: Split criterion information gain use karta hai = entropy reduction $\text{Gain}=H(\text{parent})-{\sum }_{\text{children}}\frac{|child|}{|parent|}H(\text{child})$

2. Classification: Neural networks ke liye cross-entropy loss $\mathcal{L}=-{\sum }_i{y}_i\log {\hat{y}}_i$ jahan $y$ true distribution (one-hot) hai, $\hat{y}$ predicted probabilities hain.

3. Variational Inference: Posterior approximate karne ke liye $D_{KL}(q\varphi (z)\Vert p(z|x))$ minimize karo

4. GANs: Discriminator cross-entropy maximize karta hai; generator JS divergence (KL se related) minimize karta hai

5. Reinforcement Learning: Policy gradient methods policy collapse rokne ke liye KL penalties use karte hain

Connections

• Mutual Information - Entropy use karta hai: $I(X;Y)=H(X)+H(Y)-H(X,Y)$
• Maximum Entropy Principle - Probability distributions justify karta hai
• Cross-Entropy Loss - Neural networks mein direct application
• Variational Autoencoders - ELBO = reconstruction - KL divergence
• Jensen-Shannon Divergence - KL ka symmetric version
• Information Gain - Decision trees mein entropy reduction
• Evidence Lower Bound (ELBO) - Bayesian inference ke liye KL divergence use karta hai
• F-divergences - Divergences ki family jisme KL bhi shamil hai

#flashcards/ai-ml

Shannon entropy kya hai? :: Ek random variable observe karne par mili information ka average amount (bits mein); $H(X)=-{\sum }_{x}p(x){\log }_{2}p(x)$

Concept Map