Information Theory · 90

Glossary

The technical terms of this track, with short definitions (and the Persian term where available). Each term links to the lesson where it is introduced.

aggregate posterior: The average encoder distribution over the data, $q(z) = \mathbb{E}_x\, q_\phi(z \mid x)$ . Introduced in: Lesson 10
amortization gap: The extra ELBO gap that comes from using one shared encoder instead of the best $q$ for each $x$ separately. Introduced in: Lesson 9
amortized inference: Using one encoder network $q_\phi(z \mid x)$ for all data points instead of a separate optimization of $q$ for each $x$ . Introduced in: Lesson 9
approximation gap: The part of the ELBO gap that comes from the family of $q$ being too simple, $\mathrm{KL}(q^*_x\,\|\,p(z \mid x))$ for the best member $q^*_x$ of the family. Introduced in: Lesson 9
arithmetic coding: An entropy coder that codes a whole sequence as one interval in $[0, 1)$ . With a model $q$ it spends about $-\log_2 q(x_{1:n})$ bits, plus less than 2 bits for the whole sequence. Introduced in: Lesson 5
asymmetric numeral systems (ANS): A modern entropy coder that reaches the same rate as arithmetic coding but is faster. It is used, for example, in the zstd compressor. Introduced in: Lesson 5
binary cross-entropy (BCE): The cross-entropy for a two-class target $y \in \{0, 1\}$ and a predicted probability $q$ , $-y \log q - (1 - y) \log (1 - q)$ . Introduced in: Lesson 4
binary entropy: The entropy of a coin with probability $p$ of heads, $H_b(p) = -p \log_2 p - (1 - p) \log_2 (1 - p)$ bits. It is 1 bit at $p = \frac12$ . Introduced in: Lesson 1
binary symmetric channel: A channel that flips each input bit with probability $\varepsilon$ . Its capacity is $1 - H_b(\varepsilon)$ bits per use. Introduced in: Lesson 7
bit: The unit of information when the log has base 2. An outcome with probability $\frac12$ has a surprisal of 1 bit. Introduced in: Lesson 1
bits per byte: The NLL of a language model in bits divided by the number of bytes of the text. Unlike perplexity, it does not depend on the tokenizer. Introduced in: Lesson 4
bits per dimension (bpd): The NLL of an image or audio model in bits divided by the number of dimensions, $\mathrm{NLL}_{\text{nats}} / (D \ln 2)$ . Introduced in: Lesson 4
Blahut–Arimoto algorithm: An algorithm that computes points of the rate–distortion curve of a discrete source by alternating two exact minimizations, over the test channel and over the output distribution. Introduced in: Lesson 10
calibration: A model is calibrated when, among all inputs where it predicts probability $c$ , the event happens a fraction $c$ of the time. Temperature scaling on validation data fixes most miscalibration of large networks. Introduced in: Lesson 4
chain rule for entropy: $H(X, Y) = H(X) + H(Y \mid X)$ . For a sequence, $H(X_1, \dots, X_n) = \sum_t H(X_t \mid X_{<t})$ . Introduced in: Lesson 2
chain rule for mutual information: $I(X; Y, Z) = I(X; Y) + I(X; Z \mid Y)$ . Introduced in: Lesson 7
channel capacity: A channel is a conditional distribution $p(y \mid x)$ ; its capacity is $C = \max_{p(x)} I(X; Y)$ , the largest rate of reliable communication in bits per use. Introduced in: Lesson 7
conditional entropy: The average entropy of $Y$ that remains when $X$ is known, $H(Y \mid X) = \sum_x p(x)\, H(Y \mid X = x)$ . On average, conditioning does not increase entropy, $H(Y \mid X) \le H(Y)$ . Introduced in: Lesson 2
conditional mutual information: $I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z)$ , the information $Y$ gives about $X$ when $Z$ is already known. Introduced in: Lesson 7
contrastive representation learning: Training encoders so that positive pairs get high scores and negative pairs low scores, usually with the InfoNCE loss (CPC, SimCLR, MoCo, CLIP). Introduced in: Lesson 8
convex conjugate: The function $f^*(t) = \sup_u \big(t u - f(u)\big)$ , also called the Fenchel conjugate. It turns any critic into a lower bound on an f-divergence. Introduced in: Lesson 8
convex function: A function $f$ whose chord between any two points lies on or above its graph, $f(\lambda a + (1 - \lambda) b) \le \lambda f(a) + (1 - \lambda) f(b)$ for $\lambda \in [0, 1]$ . $-\log$ and $x \log x$ are convex. Introduced in: Lesson 3
critic: A learned function $T(x)$ or $T(x, y)$ that is plugged into a variational bound. The best critic is a function of the density ratio. Introduced in: Lesson 8
cross-entropy: The average surprisal under a model $q$ of data from $p$ , $H(p, q) = -\sum_x p(x) \log q(x) = H(p) + \mathrm{KL}(p\,\|\,q)$ . It is at least $H(p)$ , with equality only for $q = p$ . Introduced in: Lesson 4
data processing inequality (DPI): If $X \to Y \to Z$ is a Markov chain, then $I(X; Z) \le I(X; Y)$ . Processing $Y$ cannot create information about $X$ . Introduced in: Lesson 7
density-ratio trick: Train a classifier to tell samples of $P$ from samples of $Q$ (equal numbers). The best classifier's logit is the log density ratio $\log \frac{p(x)}{q(x)}$ . Introduced in: Lesson 8
differential entropy: The entropy of a density, $h(X) = -\int p(x) \log p(x)\,dx$ . Unlike discrete entropy, it can be negative and it changes when the units change. For $\mathcal{N}(\mu, \sigma^2)$ it is $\frac12 \log(2\pi e \sigma^2)$ . Introduced in: Lesson 6
distortion measure: A function $d(x, \hat x) \ge 0$ that scores a reconstruction, for example Hamming distortion $[x \ne \hat x]$ or squared error $(x - \hat x)^2$ . Introduced in: Lesson 10
Donsker–Varadhan bound: The lower bound $\mathrm{KL}(P\,\|\,Q) \ge \mathbb{E}_P[T] - \log \mathbb{E}_Q[e^{T}]$ for any critic $T$ . It is tighter than NWJ for the same critic. MINE maximizes it with a neural critic. Introduced in: Lesson 8
entropy: The average surprisal of a discrete random variable, $H(X) = -\sum_x p(x) \log p(x)$ , with $0 \log 0 = 0$ . It is 0 for a certain outcome and largest ( $\log K$ ) for the uniform distribution on $K$ outcomes. Introduced in: Lesson 1
evidence: The marginal likelihood of the data, $p_\theta(x) = \int p_\theta(x, z)\,dz$ . It is usually intractable in latent-variable models. Introduced in: Lesson 9
evidence lower bound (ELBO): $\mathrm{ELBO}(q) = \mathbb{E}_{q(z)}[\log p(x, z) - \log q(z)] = \log p(x) - \mathrm{KL}(q(z)\,\|\,p(z \mid x)) \le \log p(x)$ . The gap is the reverse KL from $q$ to the true posterior. Introduced in: Lesson 9
expected length: The average number of bits per symbol of a code, $L = \sum_x p(x)\, l(x)$ . Introduced in: Lesson 5
f-divergence: For a convex generator $f$ with $f(1) = 0$ , $D_f(P\,\|\,Q) = \mathbb{E}_{x \sim Q}\big[f\big(\frac{p(x)}{q(x)}\big)\big]$ . KL, reverse KL, total variation, $\chi^2$ , squared Hellinger and Jensen–Shannon are special cases. Introduced in: Lesson 8
forward KL: Fitting a model $q$ to data $p$ by minimizing $\mathrm{KL}(p\,\|\,q)$ ; this is maximum likelihood. It needs only samples of $p$ and is mode covering. Introduced in: Lesson 6
free bits: A VAE training trick that sets a floor on the rate (the KL term) per latent dimension or group, to prevent posterior collapse. Introduced in: Lesson 10
Gibbs' inequality: $\mathrm{KL}(p\,\|\,q) \ge 0$ , with equality if and only if $p = q$ . It follows from Jensen's inequality for $\log$ . Introduced in: Lesson 3
Huffman code: The prefix code with the smallest expected length for known symbol probabilities. Huffman's algorithm repeatedly merges the two nodes with the smallest weights. Introduced in: Lesson 5
ideal code length: The code length $-\log_2 q(x)$ bits that a model $q$ assigns to $x$ . With the wrong model, the average cost is $H(p) + \mathrm{KL}(p\,\|\,q)$ bits per symbol. Introduced in: Lesson 5
InfoNCE: A softmax cross-entropy that picks the positive pair among $N$ pairs in a batch. It gives the bound $I(X; Y) \ge \log N - \mathcal{L}_{\text{InfoNCE}}$ , which can never exceed $\log N$ . Introduced in: Lesson 8
information bottleneck: For a Markov chain $Y \to X \to T$ , find the representation $T$ that minimizes $I(X; T) - \beta\, I(T; Y)$ , to keep little of the input and much about the label. Introduced in: Lesson 10
information gain: The drop in entropy of a label $Y$ after a split or a measurement $S$ , $H(Y) - H(Y \mid S)$ . It is never negative and equals the mutual information $I(Y; S)$ . Introduced in: Lesson 2
IWAE bound: The importance-weighted bound $\mathcal{L}_K = \mathbb{E}\big[\log \frac1K \sum_{k=1}^K \frac{p(x, z_k)}{q(z_k)}\big]$ with $z_k \sim q$ . $\mathcal{L}_1$ is the ELBO and $\mathcal{L}_K \le \mathcal{L}_{K+1} \le \log p(x)$ . Introduced in: Lesson 9
Jensen gap: The difference $\mathbb{E}[f(X)] - f(\mathbb{E}[X]) \ge 0$ for a convex $f$ . It is 0 when $X$ is constant (or $f$ is linear on the values of $X$ ). Introduced in: Lesson 3
Jensen's inequality: For a convex $f$ , $f(\mathbb{E}[X]) \le \mathbb{E}[f(X)]$ . For a concave $f$ such as $\log$ , the inequality flips, $\mathbb{E}[\log X] \le \log \mathbb{E}[X]$ . Introduced in: Lesson 3
joint entropy: The entropy of a pair of random variables, $H(X, Y) = -\sum_{x,y} p(x, y) \log p(x, y)$ . Introduced in: Lesson 2
KL divergence: The Kullback–Leibler divergence, or relative entropy, $\mathrm{KL}(p\,\|\,q) = \sum_x p(x) \log \frac{p(x)}{q(x)}$ . It is the extra surprise of using $q$ when the data come from $p$ . It is not symmetric and not a metric. Introduced in: Lesson 3
knowledge distillation: Training a small student model on the softened output distribution of a large teacher model, with a cross-entropy or KL loss at a temperature $T$ . Introduced in: Lesson 4
Kraft inequality: Binary codeword lengths $l_1, \dots, l_K$ of a prefix code satisfy $\sum_i 2^{-l_i} \le 1$ . Conversely, any lengths that satisfy it belong to some prefix code. Introduced in: Lesson 5
KSG estimator: The $k$ -nearest-neighbour estimator of mutual information for continuous variables (Kraskov, Stögbauer and Grassberger, 2004). Introduced in: Lesson 7
label smoothing: Training with a target that mixes the one-hot label with the uniform distribution, $t = (1 - \varepsilon)\,y + \varepsilon / K$ . The loss is $H(t) + \mathrm{KL}(t\,\|\,q)$ , so the model is not pushed to give probability 1. Introduced in: Lesson 4
latent-variable model: A model $p_\theta(x, z) = p(z)\,p_\theta(x \mid z)$ with an unobserved variable $z$ . The prior is $p(z)$ and the likelihood is $p_\theta(x \mid z)$ . Introduced in: Lesson 9
log-loss: The loss $-\log q(y)$ of a model that gave probability $q(y)$ to the observed outcome $y$ . Its average over data is the negative log-likelihood (NLL) and estimates the cross-entropy. Introduced in: Lesson 4
logits: The unnormalized scores $z_k$ that a classifier outputs before the softmax. Adding the same constant to all logits does not change the probabilities. Introduced in: Lesson 4
Markov chain: $X \to Y \to Z$ is a Markov chain if $p(x, y, z) = p(x)\,p(y \mid x)\,p(z \mid y)$ , so $Z$ is computed from $Y$ alone. Introduced in: Lesson 7
maximum-entropy principle: Among all distributions with given constraints, choose the one with the largest entropy. With a fixed mean and covariance, the answer is the Gaussian. Introduced in: Lesson 6
mean-field: A factorized approximation $q(z) = \prod_i q_i(z_i)$ that treats the coordinates as independent. Reverse-KL mean-field fits of correlated distributions are too narrow. Introduced in: Lesson 6
minimum description length (MDL): The principle to choose the model that gives the shortest total code for the model plus the data coded with it. Introduced in: Lesson 5
mode covering: The behaviour of forward-KL fits. The model must put mass everywhere $p$ has mass, so a single Gaussian fit to two bumps spreads over both. Introduced in: Lesson 6
mode seeking: The behaviour of reverse-KL fits. The model avoids regions where $p$ is small, so a single Gaussian fit to two bumps often sits on one bump. Introduced in: Lesson 6
mutual information: The information that $X$ and $Y$ share, $I(X; Y) = H(Y) - H(Y \mid X) = \mathrm{KL}(p(x, y)\,\|\,p(x)\,p(y))$ . It is symmetric, never negative, and 0 if and only if $X$ and $Y$ are independent. Introduced in: Lesson 7
nat: The unit of information with the natural log. 1 nat $= 1/\ln 2 \approx 1.443$ bits. PyTorch and NumPy losses are in nats. Introduced in: Lesson 1
NWJ bound: The lower bound $\mathrm{KL}(P\,\|\,Q) \ge \mathbb{E}_P[T] - \mathbb{E}_Q[e^{T - 1}]$ of Nguyen, Wainwright and Jordan, for any critic $T$ . The optimal critic is $T^* = 1 + \log \frac{p}{q}$ . Introduced in: Lesson 8
perplexity: The exponential of the average cross-entropy per token in nats, $e^{L}$ (equal to $2^{L_2}$ for a loss $L_2$ in bits). A perplexity of $k$ means the model is as unsure as a uniform choice among $k$ tokens. Introduced in: Lesson 4
Pinsker's inequality: $\mathrm{TV}(P, Q) \le \sqrt{\mathrm{KL}(P\,\|\,Q)/2}$ , with KL in nats. Introduced in: Lesson 8
plug-in estimator: An estimate of entropy or mutual information that inserts the empirical frequencies into the formula. For mutual information it is biased upward, so independent variables get small positive scores. Introduced in: Lesson 7
pointwise mutual information (PMI): $\operatorname{pmi}(x, y) = \log \frac{p(x, y)}{p(x)\,p(y)}$ . Its average over $p(x, y)$ is the mutual information; a single value can be negative. Introduced in: Lesson 7
positive pair: In contrastive learning, a true pair $(x_i, y_i)$ drawn from $p(x, y)$ , for example two views of the same image. A negative pair $(x_i, y_j)$ , $i \ne j$ , is a sample of $p(x)\,p(y)$ . Introduced in: Lesson 8
posterior: The distribution of the latent variable given the data, $p_\theta(z \mid x) = p_\theta(x, z) / p_\theta(x)$ . Introduced in: Lesson 9
posterior collapse: A VAE failure where the decoder models $x$ without using $z$ , and the encoder sets $q(z \mid x) = p(z)$ . The KL term (the rate) is then 0 and the code carries no information. Introduced in: Lesson 9
prefix code: A code in which no codeword is the beginning of another codeword (also called prefix-free). It can be decoded symbol by symbol without separators. Introduced in: Lesson 5
rate: The number of bits per symbol that a compressor stores. In a VAE, the rate is the average KL term $\mathbb{E}_x\,\mathrm{KL}(q_\phi(z \mid x)\,\|\,p(z))$ . Introduced in: Lesson 10
rate–distortion function: $R(D) = \min I(X; \hat X)$ over test channels $q(\hat x \mid x)$ with $\mathbb{E}[d(X, \hat X)] \le D$ , the smallest rate for average distortion at most $D$ . For a Gaussian source with squared error, $R(D) = \frac12 \log_2(\sigma^2 / D)$ for $D \le \sigma^2$ . Introduced in: Lesson 10
reparameterization trick: Writing a sample as a differentiable function of the parameters and fixed noise, for example $z = \mu + \sigma \varepsilon$ with $\varepsilon \sim \mathcal{N}(0, 1)$ , so gradients flow through the sample. Introduced in: Lesson 9
reverse KL: Fitting $q$ by minimizing $\mathrm{KL}(q\,\|\,p)$ . It needs $p$ only up to a constant and samples of $q$ , as in variational inference. It is mode seeking. Introduced in: Lesson 6
reverse water-filling: The rate–distortion solution for independent Gaussian components. Each component gets distortion $\min(\theta, \sigma_i^2)$ for one water level $\theta$ ; components with variance below $\theta$ get no bits. Introduced in: Lesson 10
softmax: The map from logits $z \in \mathbb{R}^K$ to probabilities, $q_k = e^{z_k} / \sum_j e^{z_j}$ . The gradient of softmax cross-entropy with respect to the logits is $q - y$ (prediction minus target). Introduced in: Lesson 4
source coding theorem: The best prefix code for a source $p$ has expected length $L^*$ with $H(p) \le L^* < H(p) + 1$ bits. Coding blocks of symbols brings the cost per symbol close to $H(p)$ . Introduced in: Lesson 5
strictly proper scoring rule: A score for probabilistic predictions whose expected value is best only when the predicted distribution equals the true one. The log-loss is strictly proper; accuracy is not. Introduced in: Lesson 4
subadditivity: $H(X, Y) \le H(X) + H(Y)$ , with equality if and only if $X$ and $Y$ are independent. Introduced in: Lesson 2
sufficient statistic: A function $T(Y)$ of the data is sufficient for $\theta$ when $p(y \mid t, \theta)$ does not depend on $\theta$ . Then $I(\theta; T(Y)) = I(\theta; Y)$ . Introduced in: Lesson 7
support: The set of values $x$ with $p(x) > 0$ . Introduced in: Lesson 1
surprisal: The information content of one outcome, $-\log p(x)$ . Rare outcomes have large surprisal; an outcome with probability 1 has surprisal 0. Also called self-information. Introduced in: Lesson 1
test channel: The conditional distribution $q(\hat x \mid x)$ of the reconstruction given the source, over which the rate–distortion problem is minimized. Introduced in: Lesson 10
transform coding: Lossy compression that first rotates the data to (nearly) independent components, such as principal components, and then spends bits on each component as in reverse water-filling. Introduced in: Lesson 10
uniquely decodable code: A code where every finite string of bits has at most one decoding into symbols. Every prefix code is uniquely decodable. Introduced in: Lesson 5
variational autoencoder (VAE): A latent-variable model with a neural decoder $p_\theta(x \mid z)$ and a neural encoder $q_\phi(z \mid x)$ , trained by maximizing the ELBO with the reparameterization trick. Introduced in: Lesson 9
variational free energy: The negative ELBO, $-\mathrm{ELBO}$ , as physicists call it. Introduced in: Lesson 9
variational inference (VI): Approximating a posterior by the member $q$ of a chosen family that maximizes the ELBO, which is the same as minimizing $\mathrm{KL}(q\,\|\,p(z \mid x))$ . Introduced in: Lesson 9
β-VAE: A VAE that minimizes $D + \beta R$ , distortion plus $\beta$ times rate. $\beta = 1$ gives the negative ELBO; $\beta > 1$ gives a lower rate and more distortion. Introduced in: Lesson 10