--- title: Probability & Information Theory module: Mathematical Background moduleNumber: 0 lessonNumber: 2 order: 2 summary: > This lesson assembles the probabilistic vocabulary a network is trained in (random variables, densities, the chain rule, expectation and covariance, the handful of distributions that recur everywhere) and then the information theory that turns a probabilistic model into a loss: self-information, entropy, and the KL divergence whose asymmetry is the cross-entropy objective itself. topics: [Mathematical Background] sources: - book: Goodfellow ref: "Ch. 3 — Probability and Information Theory" - book: Goodfellow ref: "§3.13 — Information Theory; §3.14 Structured Probabilistic Models" --- A trained network does not output a number; it outputs a _distribution_. A classifier emits $p_\theta(y \mid x)$ over labels, a language model $p_\theta(x_t \mid x_{ **Definition (Probability mass function).** For a discrete random variable > $\mathrm{x}$, a PMF $P(\mathrm{x}=x)$ maps each value to its probability, > subject to $0 \le P(x) \le 1$, $\sum_{x} P(x) = 1$. > **Definition (Probability density function).** For a continuous random variable > $\mathrm{x}$, a PDF $p(x) \ge 0$ does _not_ give a probability directly; it > gives probability per unit volume, so $\int p(x)\,dx = 1$ and > $P(a \le \mathrm{x} \le b) = \int_a^b p(x)\,dx$. The distinction matters in code: a PMF value is a probability and lies in $[0,1]$; a PDF value is a _density_ and may exceed $1$ (a narrow Gaussian peaks above $1$), only the integral is constrained.[^gf-prob] | | PMF $P(x)$ | PDF $p(x)$ | | --- | --- | --- | | domain | discrete | continuous | | value is | a probability | a density (prob. per unit volume) | | range | $[0,1]$ | $[0,\infty)$ | | normalization | $\sum_x P(x) = 1$ | $\int p(x)\,dx = 1$ | | point mass | $P(\mathrm{x}=x)$ | $P(\mathrm{x}=x) = 0$; use intervals | ### Marginal and conditional probability Given a joint distribution over several variables, two operations recover the pieces. **Marginalization** sums (or integrates) a variable away; **conditioning** fixes one variable's value and renormalizes. > **Definition (Marginal probability).** The distribution of a subset of variables, > obtained by summing the joint over the rest: $P(\mathrm{x}=x) = \sum_y > P(\mathrm{x}=x, \mathrm{y}=y)$, or $p(x) = \int p(x,y)\,dy$ in the continuous case. > **Definition (Conditional probability).** The probability of one event given that > another has occurred, $P(\mathrm{y}=y \mid \mathrm{x}=x) = \dfrac{P(\mathrm{x}=x, > \mathrm{y}=y)}{P(\mathrm{x}=x)}$, defined whenever $P(\mathrm{x}=x) > 0$. Geometrically, a joint density over $(x,y)$ is a surface; the marginal $p(x)$ is its shadow projected onto the $x$-axis, while the conditional $p(y \mid x_0)$ is a vertical _slice_ at $x = x_0$ rescaled to integrate to one. $$ % caption: A joint density $p(x,y)$: the marginal $p(x)$ is its projection onto % the $x$-axis; the conditional $p(y\mid x_0)$ is a renormalized vertical slice. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % axes \draw[->, thick] (-0.3,0) -- (6.2,0) node[right, font=\footnotesize] {x}; \draw[->, thick] (0,-0.3) -- (0,4.6) node[above, font=\footnotesize] {y}; % joint contours: tilted ellipses centered at (3, 2.2) \foreach \r in {0.55,1.05,1.55} { \draw[acc, thick, rotate around={28:(3,2.2)}] (3,2.2) ellipse ({\r*1.5} and \r); } \node[acc, font=\footnotesize, anchor=south west] at (4.7,3.7) {\texttt{joint} density}; % marginal p(x): a bump along the bottom (shadow) \draw[acc, very thick] plot[domain=0.4:5.6, samples=70] (\x, {1.05*exp(-0.5*(\x-3)*(\x-3))}); \node[acc, font=\footnotesize, anchor=south west] at (4.5,0.45) {marginal}; % conditional slice at x0 = 1.7 \draw[red, dashed, thick] (1.7,0) -- (1.7,4.3); \node[red, font=\footnotesize, anchor=south] at (1.7,4.3) {slice at $x_0$}; \fill[red] (1.7,0) circle (1.6pt); \node[red, font=\footnotesize, anchor=north] at (1.7,-0.1) {$x_0$}; \end{tikzpicture} $$ ### The chain rule of probability Any joint distribution factors into a product of conditionals. Apply the conditional-probability definition repeatedly: $$ P(\mathrm{x}_1, \dots, \mathrm{x}_n) = P(\mathrm{x}_1)\prod_{i=2}^{n} P(\mathrm{x}_i \mid \mathrm{x}_1, \dots, \mathrm{x}_{i-1}). $$ > **Definition (Chain rule).** The factorization $P(\mathrm{x}_1,\dots,\mathrm{x}_n) > = \prod_{i} P(\mathrm{x}_i \mid \mathrm{x}_{1:i-1})$, valid for _any_ ordering of > the variables. It turns a joint over $n$ variables into a sequence of conditionals. This is the identity an **autoregressive** model exploits directly: a language model writes $p(x_1,\dots,x_T) = \prod_t p(x_t \mid x_{ **Definition (Independence).** $\mathrm{x} \perp \mathrm{y}$ iff $p(x,y) = p(x)\,p(y)$ > for all $x,y$; equivalently $p(y \mid x) = p(y)$. > **Definition (Conditional independence).** $\mathrm{x} \perp \mathrm{y} \mid > \mathrm{z}$ iff $p(x,y \mid z) = p(x \mid z)\,p(y \mid z)$ for all $x,y,z$. Conditional independence is strictly weaker than independence and the more useful of the two: a child's height and vocabulary are correlated marginally, but conditionally independent given age. Whole families of models (naive Bayes, hidden Markov models, the [structured probabilistic models](/deep-learning/probabilistic-methods/structured-probabilistic-models) below) are built by _asserting_ such conditional independencies to make a joint tractable. ## Expectation, variance, covariance The **expectation** of a function under a distribution is its probability-weighted average, the single most-used operation in the subject, since every loss is an expectation and every gradient an expectation of a gradient. > **Definition (Expectation).** $\mathbb{E}_{\mathrm{x}\sim P}[f(\mathrm{x})] = > \sum_x P(x)\,f(x)$ (discrete) or $\int p(x)\,f(x)\,dx$ (continuous). Expectation is > **linear**: $\mathbb{E}[\alpha f(\mathrm{x}) + \beta g(\mathrm{x})] = \alpha\, > \mathbb{E}[f] + \beta\,\mathbb{E}[g]$. **Variance** measures spread around the mean; **covariance** measures how two variables move together; **correlation** is covariance normalized to $[-1,1]$. $$ \Var(\mathrm{x}) = \mathbb{E}\brackets{(\mathrm{x} - \mathbb{E}[\mathrm{x}])^2} = \mathbb{E}[\mathrm{x}^2] - \mathbb{E}[\mathrm{x}]^2, $$ $$ \Cov(\mathrm{x},\mathrm{y}) = \mathbb{E}\brackets{(\mathrm{x} - \mathbb{E}[\mathrm{x}])(\mathrm{y} - \mathbb{E}[\mathrm{y}])} = \mathbb{E}[\mathrm{x}\mathrm{y}] - \mathbb{E}[\mathrm{x}]\,\mathbb{E}[\mathrm{y}], $$ $$ \rho_{\mathrm{x}\mathrm{y}} = \frac{\Cov(\mathrm{x},\mathrm{y})} {\sqrt{\Var(\mathrm{x})}\,\sqrt{\Var(\mathrm{y})}} \in [-1, 1]. $$ For a random vector $\mathbf{x} \in \mathbb{R}^d$ the pairwise covariances collect into the **covariance matrix** $\Sigma_{ij} = \Cov(\mathrm{x}_i, \mathrm{x}_j)$, with the variances on its diagonal. $\Sigma$ is symmetric and positive semi-definite. > **Remark (Independence vs. zero covariance).** Independence implies zero > covariance, but not conversely: covariance only detects _linear_ dependence. > $\mathrm{x}\sim\text{Unif}[-1,1]$ and $\mathrm{y}=\mathrm{x}^2$ have > $\Cov(\mathrm{x},\mathrm{y}) = 0$ yet are fully dependent. ### A worked covariance Let $(\mathrm{x},\mathrm{y})$ take four equally likely values: $(1,2)$, $(2,1)$, $(3,5)$, $(4,4)$. Compute the moments by the definitions above. $$ \mathbb{E}[\mathrm{x}] = \tfrac{1+2+3+4}{4} = 2.5, \qquad \mathbb{E}[\mathrm{y}] = \tfrac{2+1+5+4}{4} = 3. $$ $$ \mathbb{E}[\mathrm{x}\mathrm{y}] = \tfrac{1}{4}\parens{1{\cdot}2 + 2{\cdot}1 + 3{\cdot}5 + 4{\cdot}4} = \tfrac{2+2+15+16}{4} = \tfrac{35}{4} = 8.75. $$ $$ \Cov(\mathrm{x},\mathrm{y}) = \mathbb{E}[\mathrm{x}\mathrm{y}] - \mathbb{E}[\mathrm{x}]\,\mathbb{E}[\mathrm{y}] = 8.75 - (2.5)(3) = 8.75 - 7.5 = 1.25. $$ The sign is positive, so $\mathrm{x}$ and $\mathrm{y}$ tend to rise together. To read it on the bounded scale, normalize: with $\Var(\mathrm{x}) = \tfrac{1{+}4{+}9{+}16}{4} - 2.5^2 = 1.25$ and $\Var(\mathrm{y}) = \tfrac{4{+}1{+}25{+}16}{4} - 3^2 = 2.5$, $$ \rho_{\mathrm{x}\mathrm{y}} = \frac{1.25}{\sqrt{1.25}\,\sqrt{2.5}} = \frac{1.25}{1.7678} \approx 0.707. $$ ## Common distributions A short catalogue carries most of deep learning. Each row is a model for the _output_ of some layer or the _noise_ in some assumption. | name | PMF / PDF | parameters | support | use in DL | | --- | --- | --- | --- | --- | | Bernoulli | $\phi^{x}(1-\phi)^{1-x}$ | $\phi \in [0,1]$ | $\{0,1\}$ | binary output unit (sigmoid) | | Categorical | $\prod_k \phi_k^{[x=k]}$ | $\phi \in \Delta^{K-1}$ | $\{1,\dots,K\}$ | softmax classifier head | | Gaussian | $\frac{1}{\sqrt{2\pi}\sigma}\exp\parens{-\frac{(x-\mu)^2}{2\sigma^2}}$ | $\mu,\ \sigma^2>0$ | $\mathbb{R}$ | weight init, regression noise, VAE latents | | Multivariate Gaussian | $\frac{1}{\sqrt{(2\pi)^d\det\Sigma}}\exp\parens{-\tfrac12 (x-\mu)^\top\Sigma^{-1}(x-\mu)}$ | $\mu\in\mathbb{R}^d,\ \Sigma\succ 0$ | $\mathbb{R}^d$ | latent priors, Laplace approx. | | Exponential | $\lambda e^{-\lambda x}\,[x\ge 0]$ | $\lambda > 0$ | $[0,\infty)$ | sparse / nonnegative variables | | Laplace | $\frac{1}{2b}\exp\parens{-\frac{\abs{x-\mu}}{b}}$ | $\mu,\ b>0$ | $\mathbb{R}$ | heavy tails; $L^1$ / sparse prior | | Dirac | $\delta(x-\mu)$ | $\mu$ | $\{\mu\}$ | a point mass; building block of empirical | | Empirical | $\frac1n\sum_i \delta(x-x^{(i)})$ | data $\{x^{(i)}\}$ | data points | the training set as a distribution | | Gaussian mixture | $\sum_k \pi_k\,\mathcal{N}(x;\mu_k,\Sigma_k)$ | $\pi\in\Delta^{K-1},\ \mu_k,\Sigma_k$ | $\mathbb{R}^d$ | multimodal density; universal approximator | The **Gaussian** is ubiquitous for two reasons: the central limit theorem makes it the default model of summed noise, and among all distributions with a given variance it is the maximum-entropy choice — the least-committal assumption you can make.[^gf-gaussian] Its bell shape is fixed by two numbers, the mean $\mu$ (location) and the variance $\sigma^2$ (spread). $$ % caption: Two Gaussians with shared mean: smaller variance (blue) is taller and % narrower, larger variance (black) shorter and wider. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % axes \draw[->, thick] (-4.2,0) -- (4.4,0) node[right, font=\footnotesize] {x}; \draw[->, thick] (0,-0.25) -- (0,3.3) node[above, font=\footnotesize] {density}; % mean marker \draw[black, dashed] (0,0) -- (0,3.0); \node[font=\footnotesize, anchor=north east] at (-0.05,-0.05) {mean}; % narrow gaussian: var small, height ~ 3 \draw[acc, very thick] plot[domain=-4:4, samples=120] (\x, {3.0*exp(-0.5*\x*\x/0.36)}); \node[acc, font=\footnotesize, anchor=west] at (0.55,2.7) {small variance}; % wide gaussian: var larger, height ~ 1.4 — distinct solid black \draw[black, very thick] plot[domain=-4:4, samples=120] (\x, {1.4*exp(-0.5*\x*\x/1.6)}); \node[black, font=\footnotesize, anchor=west] at (1.7,1.0) {large variance}; % spread arrows for the wide one \draw[<->, red, thick] (-1.265,0.55) -- (1.265,0.55); \node[red, font=\footnotesize, anchor=west] at (2.55,0.62) {one std dev}; \end{tikzpicture} $$ The **empirical distribution** is the most important row for practice: it is the training set itself, viewed as a sum of Dirac spikes, one at each data point. Every expectation under it is a plain average over the data, $\mathbb{E}_{\hat{p}}[f] = \frac1n\sum_i f(x^{(i)})$ — the empirical risk a network minimizes. A **Gaussian mixture** stacks several bells with mixing weights $\pi_k$ summing to one. With enough components it approximates any smooth density, and its multimodality is what a single Gaussian cannot capture. $$ % caption: Three weighted component bells (black) sum to one multimodal mixture % density (blue) that a single Gaussian cannot represent. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} % axes \draw[->, thick] (-0.4,0) -- (9.6,0) node[right, font=\footnotesize] {x}; \draw[->, thick] (0,-0.25) -- (0,3.0) node[above, font=\footnotesize] {density}; % three components: centers 2, 4.5, 7 — distinct solid black \draw[black, thick] plot[domain=0:9.4, samples=120] (\x, {1.5*exp(-0.5*(\x-2)*(\x-2)/0.55)}); \draw[black, thick] plot[domain=0:9.4, samples=120] (\x, {0.8*exp(-0.5*(\x-4.5)*(\x-4.5)/0.9)}); \draw[black, thick] plot[domain=0:9.4, samples=120] (\x, {1.7*exp(-0.5*(\x-7)*(\x-7)/0.7)}); \node[black, font=\footnotesize, anchor=south] at (4.5,0.85) {components}; % the mixture (sum), solid accent \draw[acc, very thick] plot[domain=0:9.4, samples=200] (\x, {1.5*exp(-0.5*(\x-2)*(\x-2)/0.55) + 0.8*exp(-0.5*(\x-4.5)*(\x-4.5)/0.9) + 1.7*exp(-0.5*(\x-7)*(\x-7)/0.7)}); \node[acc, font=\footnotesize, anchor=south west] at (7.3,2.0) {mixture}; \end{tikzpicture} $$ ## Bayes' rule Bayes' rule inverts a conditional: it turns $P(x \mid y)$, which you can model, into $P(y \mid x)$, which you want to infer. It is a one-line consequence of the chain rule. > **Theorem (Bayes' rule).** For events with $P(\mathrm{x}) > 0$, > $$ > P(\mathrm{y} \mid \mathrm{x}) = \frac{P(\mathrm{x} \mid \mathrm{y})\,P(\mathrm{y})}{P(\mathrm{x})}, > \qquad > P(\mathrm{x}) = \sum_{y} P(\mathrm{x} \mid \mathrm{y})\,P(\mathrm{y}). > $$ > **Proof.** The chain rule expands the joint two ways, by either ordering: > $P(\mathrm{x},\mathrm{y}) = P(\mathrm{x}\mid\mathrm{y})\,P(\mathrm{y}) > = P(\mathrm{y}\mid\mathrm{x})\,P(\mathrm{x})$. Equate the two right-hand sides and > divide by $P(\mathrm{x})$, which is positive by assumption: > $P(\mathrm{y}\mid\mathrm{x}) = P(\mathrm{x}\mid\mathrm{y})\,P(\mathrm{y})/P(\mathrm{x})$. > The denominator is the marginal of $\mathrm{x}$, recovered by summing the joint > over $\mathrm{y}$ (the law of total probability). $\qed$ The four pieces have standard names: $P(y)$ the **prior**, $P(x \mid y)$ the **likelihood**, $P(x)$ the **evidence** (a normalizer), and $P(y \mid x)$ the **posterior**. ### A worked example A disease afflicts $1\%$ of a population. A test detects it with $99\%$ sensitivity and has a $5\%$ false-positive rate. A patient tests positive; what is the probability they are sick? Let $\mathrm{y}=1$ denote disease and $\mathrm{x}=1$ a positive test. $$ P(\mathrm{y}{=}1) = 0.01, \quad P(\mathrm{x}{=}1 \mid \mathrm{y}{=}1) = 0.99, \quad P(\mathrm{x}{=}1 \mid \mathrm{y}{=}0) = 0.05. $$ The evidence is the total positive rate, sick and healthy paths combined: $$ P(\mathrm{x}{=}1) = \underbrace{0.99 \cdot 0.01}_{\text{true positive}} + \underbrace{0.05 \cdot 0.99}_{\text{false positive}} = 0.0099 + 0.0495 = 0.0594. $$ $$ P(\mathrm{y}{=}1 \mid \mathrm{x}{=}1) = \frac{0.99 \cdot 0.01}{0.0594} = \frac{0.0099}{0.0594} \approx 0.167. $$ A positive test leaves the patient only $\approx 17\%$ likely to be sick: the base rate is so low that false positives swamp true ones. The tree makes the arithmetic visible — of every $10{,}000$ people, only $99$ true positives compete against $495$ false positives, so a positive result is wrong five times out of six. $$ % caption: The disease example as a frequency tree over 10,000 people. The 99 true % positives are outnumbered by 495 false positives, giving a 99/594 posterior. \begin{tikzpicture}[>=stealth, font=\footnotesize, b/.style={draw, minimum width=20mm, minimum height=7mm, fill=black!5}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \node[b] (root) at (0,0) {10,000 people}; \node[b, draw=acc, fill=acc!12, text=black] (sick) at (-3,-1.7) {100 sick}; \node[b] (well) at (3,-1.7) {9,900 well}; \node[b, draw=acc, fill=acc!12, text=acc] (tp) at (-4.5,-3.4) {99 test +}; \node[b] (fn) at (-1.7,-3.4) {1 test -}; \node[b, draw=red, fill=red!8, text=red] (fp) at (1.7,-3.4) {495 test +}; \node[b] (tn) at (4.6,-3.4) {9,405 test -}; \draw[->] (root) -- (sick) node[midway, above left, inner sep=1pt] {1\%}; \draw[->] (root) -- (well) node[midway, above right, inner sep=1pt] {99\%}; \draw[->] (sick) -- (tp); \draw[->] (sick) -- (fn); \draw[->] (well) -- (fp); \draw[->] (well) -- (tn); \node[align=center] at (0,-4.6) {99 true vs.\ 495 false \texttt{positives} give posterior 99/594 = 0.167}; \end{tikzpicture} $$ This **base-rate neglect** is the most common probabilistic error; Bayes' rule corrects it.[^gf-bayes] ## Information theory Information theory quantifies _surprise_. The guiding intuition: a likely event carries little information, an unlikely event carries a lot, and the information of independent events adds. The unique function (up to base) satisfying these is the logarithm.[^gf-info] > **Definition (Self-information).** The information content of an outcome $x$ is > $I(x) = -\log P(x)$. In nats (natural log) or bits ($\log_2$): a certain event > ($P=1$) carries $0$; a one-in-a-million event carries $\approx 20$ bits. Self-information of a single outcome, averaged over the distribution, is the **Shannon entropy**: the expected surprise, or the irreducible number of bits needed to encode draws from $P$. > **Definition (Shannon entropy).** $H(P) = \mathbb{E}_{\mathrm{x}\sim P}[I(\mathrm{x})] > = -\sum_x P(x)\log P(x)$ (with $0\log 0 := 0$). It is maximal for the uniform > distribution and zero for a deterministic one. For a single binary variable with $P(\mathrm{x}{=}1) = p$, entropy is the **binary entropy function** $H(p) = -p\log p - (1-p)\log(1-p)$. It peaks where uncertainty is greatest — a fair coin — and vanishes at the certain ends. $$ % caption: Binary entropy in bits: maximal (one bit) at the fair $p=\tfrac12$, % zero at $p=0$ and $p=1$ where the outcome is certain. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % axes: x = p in [0,1] scaled to 6 units; y = H in [0,1] scaled to 3 units \draw[->, thick] (-0.2,0) -- (6.6,0) node[right, font=\footnotesize] {p}; \draw[->, thick] (0,-0.2) -- (0,3.4) node[above, font=\footnotesize] {\texttt{entropy} (bits)}; % gridlines \draw[black, dashed] (3,0) -- (3,3.0); \draw[black, dashed] (0,3.0) -- (3,3.0) node[black, left, font=\footnotesize] at (0,3.0) {$1$}; \node[font=\footnotesize, anchor=north] at (3,-0.05) {$\tfrac12$}; \node[font=\footnotesize, anchor=north] at (6,-0.05) {$1$}; % H(p) curve: x in [0,6] maps p=x/6; H = -p log2 p - (1-p) log2(1-p), scaled *3 \draw[acc, very thick] plot[domain=0.02:5.98, samples=160] (\x, {3*( -(\x/6)*log2(\x/6) - (1-\x/6)*log2(1-\x/6) )}); % peak marker \fill[red] (3,3.0) circle (1.8pt); \node[red, font=\footnotesize, anchor=south] at (3.1,3.02) {fair coin}; \end{tikzpicture} $$ ### KL divergence To compare two distributions $P$ and $Q$ over the same variable, measure the extra cost of encoding $P$'s data with a code built for $Q$. That is the **Kullback–Leibler divergence**. > **Definition (KL divergence).** $D_{KL}(P\,\|\,Q) = \mathbb{E}_{\mathrm{x}\sim P} > \brackets{\log\dfrac{P(\mathrm{x})}{Q(\mathrm{x})}} = \sum_x P(x)\log > \dfrac{P(x)}{Q(x)}$. It is the expected log-ratio, with the expectation taken > under the _first_ argument $P$. For example, take $P = (0.9, 0.1)$ and $Q = (0.5, 0.5)$ over two outcomes, in nats: $$ D_{KL}(P\,\|\,Q) = 0.9\ln\tfrac{0.9}{0.5} + 0.1\ln\tfrac{0.1}{0.5} \approx 0.368, \quad D_{KL}(Q\,\|\,P) = 0.5\ln\tfrac{0.5}{0.9} + 0.5\ln\tfrac{0.5}{0.1} \approx 0.511. $$ The two numbers differ, so KL is not a metric. Which direction to minimize is a modeling choice with visible consequences, spelled out below. Two properties make it the right tool, and one caveat makes it tricky. > **Theorem (Gibbs' inequality).** $D_{KL}(P\,\|\,Q) \ge 0$, with equality iff > $P = Q$ almost everywhere. > **Proof.** Write $-D_{KL}(P\|Q) = \sum_x P(x)\log\frac{Q(x)}{P(x)}$. Since $\log$ > is concave, Jensen's inequality gives $\mathbb{E}[\log Z] \le \log \mathbb{E}[Z]$; > apply it with $Z = Q(\mathrm{x})/P(\mathrm{x})$ under $P$: > $$ > -D_{KL}(P\|Q) = \mathbb{E}_P\brackets{\log\frac{Q}{P}} > \le \log \mathbb{E}_P\brackets{\frac{Q}{P}} > = \log \sum_x P(x)\frac{Q(x)}{P(x)} = \log\sum_x Q(x) = \log 1 = 0. > $$ > Hence $D_{KL}(P\|Q) \ge 0$. Strict concavity of $\log$ forces equality only when > $Q/P$ is constant, i.e. $P = Q$. $\qed$ The KL divergence is **not symmetric**: in general $D_{KL}(P\,\|\,Q) \neq D_{KL}(Q\,\|\,P)$, so it is not a distance. The asymmetry matters in practice. $D_{KL}(P\,\|\,Q)$ is weighted by $P$, so it penalizes a $Q$ that puts low mass where $P$ is high. Fitting $Q$ to $P$ this way makes $Q$ **mass-covering** (spread out to cover all of $P$'s support). The reverse $D_{KL}(Q\,\|\,P)$ is weighted by $Q$ and makes $Q$ **mode-seeking** (it picks one mode of $P$ and ignores the rest), the form variational inference minimizes.[^gf-kl] $$ % caption: KL is asymmetric: fitting a single Gaussian $Q$ (red) to a bimodal $P$ % (blue) either covers both modes or collapses onto one, depending on direction. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % axes \draw[->, thick] (-0.4,0) -- (9.6,0) node[right, font=\footnotesize] {x}; \draw[->, thick] (0,-0.25) -- (0,3.0) node[above, font=\footnotesize] {density}; % P: bimodal (two bells), solid accent. modes at 2.5 and 6.5 \draw[acc, very thick] plot[domain=0:9.4, samples=200] (\x, {1.6*exp(-0.5*(\x-2.5)*(\x-2.5)/0.5) + 1.6*exp(-0.5*(\x-6.5)*(\x-6.5)/0.5)}); \node[acc, font=\footnotesize, anchor=south] at (2.5,1.65) {$P$ (\texttt{two} modes)}; % Q: single wide gaussian centered between — distinct solid red. mean 4.5 \draw[red!75, very thick] plot[domain=0:9.4, samples=160] (\x, {1.25*exp(-0.5*(\x-4.5)*(\x-4.5)/2.4)}); \node[red!75, font=\footnotesize, anchor=south] at (4.5,1.4) {$Q$ (one mode)}; \end{tikzpicture} $$ ### Cross-entropy and the loss **Cross-entropy** is the entropy of $P$ plus the divergence from $P$ to $Q$, the total bits to encode $P$'s data using $Q$'s code. The decomposition is immediate from the definitions. $$ H(P, Q) = -\sum_x P(x)\log Q(x). $$ $$ H(P, Q) = -\sum_x P(x)\log Q(x) = \underbrace{-\sum_x P(x)\log P(x)}_{H(P)} \;+\; \underbrace{\sum_x P(x)\log\tfrac{P(x)}{Q(x)}}_{D_{KL}(P\|Q)}. $$ > **Definition (Cross-entropy).** $H(P,Q) = H(P) + D_{KL}(P\,\|\,Q)$. Since $H(P)$ > does not depend on $Q$, **minimizing cross-entropy in $Q$ is identical to > minimizing $D_{KL}(P\,\|\,Q)$** — driving $Q$ toward $P$. This is the bridge from information theory to the training loop. Set $P = \hat{p}$, the empirical distribution of the labels, and $Q = p_\theta$, the network's predictive distribution. Cross-entropy then equals the **negative log-likelihood**, the standard classification loss: $$ H(\hat{p}, p_\theta) = -\frac1n \sum_{i=1}^{n} \log p_\theta(y^{(i)} \mid x^{(i)}) = \mathcal{L}(\theta). $$ > **Remark (Why cross-entropy is the default loss).** Minimizing it is maximum > likelihood _and_ minimizing $D_{KL}(\hat{p}\,\|\,p_\theta)$ — fitting the model > distribution to the data distribution. The constant $H(\hat{p})$ drops out of the > gradient, leaving exactly the negative log-likelihood the > [output units](/deep-learning/neural-networks/loss-functions-and-output-units) > are derived from. For a one-hot label $y$ and softmax output $\hat{y} = p_\theta(\cdot \mid x)$ over $K$ classes, the per-example cross-entropy collapses to a single term, the negative log-probability the model assigned to the true class: $$ \ell(\hat{y}, y) = -\sum_{k=1}^{K} y_k \log \hat{y}_k = -\log \hat{y}_{c}, \qquad c = \text{the true class}. $$ ```algorithm caption: $\textsc{CrossEntropyLoss}(\text{logits } z, \text{label } c)$ — softmax NLL over $K$ classes $m \gets \max_k z_k$ // for numerical stability $Z \gets \sum_{k} \exp(z_k - m)$ // log-sum-exp normalizer for $k \gets 1$ to $K$ do $\hat{y}_k \gets \exp(z_k - m) / Z$ // softmax probability $\ell \gets -(z_c - m) + \log Z$ // $= -\log \hat{y}_c$, stable form return $\ell$ ``` The shifted-logit form computes $-\log\hat{y}_c$ without ever forming the tiny probability $\hat{y}_c$ explicitly, the same log-sum-exp trick the [numerical computation](/deep-learning/mathematical-background/numerical-computation) lesson develops in full. ## Graphical models: distributions as factorizations A joint over many variables is astronomically large — $K^n$ entries for $n$ $K$-valued variables. **Structured probabilistic models** (graphical models) address this by writing the joint as a product of factors over small subsets of variables, encoding the conditional independencies that make most of those entries redundant. | | directed (Bayesian network) | undirected (Markov random field) | | --- | --- | --- | | factor | conditional $p(x_i \mid \text{pa}(x_i))$ | clique potential $\phi_c(x_c)$ | | factorization | $p(x) = \prod_i p(x_i \mid \text{pa}(x_i))$ | $p(x) = \frac1Z \prod_c \phi_c(x_c)$ | | normalized | automatically | needs partition function $Z$ | | reads as | causal / generative ordering | symmetric affinities | The two families are two ways to draw the _same_ idea (a joint is the product of local factors, one per edge group of a graph), and the chain rule is the directed case made fully explicit (every variable conditioned on all predecessors). $$ % caption: Two graphical factorizations of a joint over $a,b,c,d$: a directed % model (left, arrows as conditionals) and an undirected one (right, edge cliques). \begin{tikzpicture}[>=stealth, font=\small, v/.style={circle, draw, minimum size=8mm, inner sep=0pt, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} % --- directed (left) --- \node[v] (a) at (0,1.4) {a}; \node[v] (b) at (1.6,1.4) {b}; \node[v] (c) at (0.8,0) {c}; \node[v] (d) at (0.8,-1.4) {d}; \draw[->, acc, thick] (a) -- (c); \draw[->, acc, thick] (b) -- (c); \draw[->, acc, thick] (c) -- (d); \node[font=\footnotesize] at (0.8,-2.3) {directed}; % --- undirected (right) --- \begin{scope}[xshift=6cm] \node[v] (p) at (0,1.4) {a}; \node[v] (q) at (1.6,1.4) {b}; \node[v] (r) at (0,-0.2) {c}; \node[v] (s) at (1.6,-0.2) {d}; \draw[acc, thick] (p) -- (q); \draw[acc, thick] (p) -- (r); \draw[acc, thick] (q) -- (s); \draw[acc, thick] (r) -- (s); \node[font=\footnotesize] at (0.8,-1.2) {undirected}; \end{scope} \end{tikzpicture} $$ We develop inference and learning in these models (belief propagation, sampling, the partition function's intractability) in the [structured probabilistic models](/deep-learning/probabilistic-methods/structured-probabilistic-models) chapter. For now the takeaway is structural: a graph _is_ a set of conditional independence assumptions, and without them a joint over millions of pixels or tokens would not be learnable at all. ## Which KL you minimize The information-theoretic quantities here are the objectives of whole model families, and the direction of the KL is the design choice that separates them. **Which KL you minimize is which model you get.** The variational autoencoder (Kingma and Welling, 2013) minimizes the _forward_, mass-covering $D_{KL}(q \,\|\, p)$ inside its evidence lower bound, which is why VAE samples tend to be blurry averages that cover the data's support. A GAN's discriminator drives the generator toward a more _mode-seeking_ objective, which is why GAN samples are sharp but can collapse to a few modes. The mass-covering / mode-seeking split this lesson draws from a bimodal toy is, at scale, the difference between the two dominant families of generative models. **Making the expectation differentiable.** Training these models needs the gradient of an expectation $\mathbb{E}_{z \sim q_\theta}[f(z)]$ where the _distribution_ depends on $\theta$. The **reparameterization trick** (Kingma and Welling, 2013) rewrites a Gaussian draw as $z = \mu_\theta + \sigma_\theta \odot \epsilon$ with $\epsilon \sim \mathcal{N}(0, I)$ fixed, moving $\theta$ out of the sampling step so back-propagation can flow through it — a direct application of the change-of-variable view of a distribution. **Cross-entropy, softened.** The cross-entropy loss derived above assumes a one-hot target, which pushes the model toward infinite-confidence logits. **Label smoothing** (Szegedy et al., 2016) replaces the one-hot target with a slightly spread distribution, so the objective is cross-entropy against a target of nonzero entropy — a calibrated, better-generalizing classifier that the KL decomposition $H(P,Q) = H(P) + D_{KL}(P\|Q)$ explains exactly: raising $H(P)$ lifts the loss floor and discourages overconfidence.[^vae][^labelsmooth] ## Takeaways - A network outputs a **distribution**; PMFs (discrete, values in $[0,1]$) and PDFs (continuous, _densities_ that may exceed $1$) describe it. **Marginalize** to drop a variable, **condition** to fix one. - The **chain rule** $p(x_{1:n}) = \prod_i p(x_i \mid x_{