1 Probability in Reasoning, Inference, and Learning

1.1 Probability as the language of uncertainty

How do we represent information and uncertainty mathematically? When you type “good” into your phone, the keyboard offers a few likely continuations: perhaps “morning”, “luck”, and “night”. These suggestions reflect a state of knowledge: “morning” may follow with probability \(0.45\), “luck” with probability \(0.25\), “night” with probability \(0.15\), and other words with the remaining \(0.15\) (the numbers are illustrative). A probability distribution over the possible next words captures both what the options are and how strongly each is expected. It also encodes uncertainty: your phone does not know for sure what you are going to write next.

Probability theory is our main tool for representing knowledge and uncertainty. Additionally, it provides a framework for formulating assumptions. In this chapter, we will study the role of probability in reasoning, inference, and machine learning. We first describe these tasks, bearing in mind that there is no universally accepted definition for them.

When considering these problems, we deal with uncertainty. Sources of uncertainty, for example in machine learning, include:

• Noise: aggregate contribution of factors that we do not (wish to) consider (models focus on the most important quantities). For example, your height can be predicted well from your parents’ heights and general patterns of nutrition and sleep, which we can include in our model. But it may also depend on every meal you ate and how much you slept each night throughout your youth, which we cannot include.

• Finite sample size: finite size of data makes it impossible to fully determine relationships (i.e., probability distributions) as some configuration may never happen or happen a few times in finite data.

1.1.1 Relationships, distributions, and probabilistic reasoning

Is there any relationship between the arrival times of two people working at a business (opening at 9:00 am), both living in the same area? If so, how can we represent this relationship? How can we make predictions about one being late given the other is late (e.g., if we need at least one person to be present)?

In the same way that we can encode our information about a random quantity as a distribution, we can encode information about random quantities, as well as their relationships, as joint distributions.

In our example, there’s obviously a relationship, that is, the arrival times are not independent. For example, both are affected by traffic. Let \[\begin{align*} T_O&: \text{normal traffic}\\ T_H&: \text{heavy traffic}\\ A_O&: \text{Alice is on time}\\ A_L&: \text{Alice is late}\\ B_O&: \text{Bob is on time}\\ B_L&: \text{Bob is late} \end{align*}\] and assume \[\begin{align*} \Pr(T_O) &= 0.75,\\ \Pr(A_O|T_O) &= 0.8,\\ \Pr(B_O|T_O) &= 0.6,\\ \Pr(A_O|T_H) &= 0.6,\\ \Pr(B_O|T_H) &= 0.2. \end{align*}\] Finally, conditioned on the traffic situation, Alice and Bob’s arrival times are independent. This information completely determines all probabilities. As we will see in greater depth later, the fact that Alice and Bob’s arrival times are only related through traffic can be shown graphically as

Causal reasoning: \[\begin{align*} \Pr(A_O) &= \Pr(T_O)\Pr(A_O|T_O)+\Pr(T_H)\Pr(A_O|T_H)\\ &= (0.75 \times 0.8) + (0.25 \times 0.6) = 0.75,\\ \Pr(B_O) &= \Pr(T_O)\Pr(B_O|T_O)+\Pr(T_H)\Pr(B_O|T_H)\\ &= (0.75 \times 0.6) + (0.25 \times 0.2) = 0.5. \end{align*}\]

Evidential reasoning (inverse probabilities, uses Bayes rule): \[\begin{align*} \Pr(T_O|A_O) &= \Pr(A_O|T_O)\Pr(T_O)/\Pr(A_O) = 0.8 \times 0.75 / 0.75 = 0.8 \\ \Pr(T_O|B_O) &= \Pr(B_O|T_O)\Pr(T_O)/\Pr(B_O) = 0.6 \times 0.75 / 0.5 = 0.9 \end{align*}\]

The common cause makes the events \(A_i\) and \(B_i\) dependent. Recall that two events \(E_1\) and \(E_2\) are independent, denoted \(E_1{\mathrel{\perp\mkern-10mu\perp}}E_2\) if \(\Pr(E_1 E_2)=\Pr(E_1)\Pr(E_2)\), or, if \(\Pr(E_2)\neq0\), \(\Pr(E_1|E_2)=\Pr(E_1)\). We have \[\begin{align*} \Pr(A_O|B_O) &= \Pr(A_OB_O)/\Pr(B_O)\\ \Pr(A_OB_O) &= (0.75\times0.8\times0.6) + (0.25\times0.6\times0.2) = 0.39\\ \Pr(A_O|B_O) &= 0.39/0.5 = 0.78\neq \Pr(A_O)\\ \Pr(B_O|A_O) &= 0.39/0.75 = 0.52\neq \Pr(B_O) \end{align*}\] So \(A_O\mathrel{\rlap{\mkern5.5mu/}{\perp\mkern-10mu\perp}}B_O\).

However, they are conditionally independent, by assumption \[\Pr(A_OB_O|T_O) = \Pr(A_O|T_O)\Pr(B_O|T_O),\]

which is denoted as \(A_O{\mathrel{\perp\mkern-10mu\perp}}B_O|T_O\).

What is the source of uncertainty in this problem? Since we have assumed the distribution is known, sample size is not an issue. The source is noise. For example, if we had information about other factors affecting Bob, e.g., how reliable his car is, if he needs to drop off his kids, etc., we could reduce the amount of noise and make better predictions.

1.2 Inference and machine learning

The reasoning in the previous section relied on distributions that were fully known: five numbers specified the model, and probability answered every question we asked. The other two problem types, inference and machine learning, begin instead from data, because the distributions they need are unknown. Each is illustrated here briefly, together with its sources of uncertainty. The full treatments come in later chapters.

1.2.1 Inference

Inference is the process of using data to draw conclusions about the real world; for example, estimating an unknown quantity. Suppose that the probability that someone with a given allele of a gene will develop a certain disease is \(\theta\). We are interested in determining \(\theta\); an answer is a number for \(\theta\) together with a statement of how sure we are about it. To find one, we collect data: among a sample of 100 people with this allele, 2 have the disease. How we approach this problem depends on whether we view \(\theta\) as deterministic or random: the same data and the same question, but two different notions of what “unknown” means.

1.2.1.1 The frequentist view

In the frequentist view, \(\theta\) is fixed and deterministic, but unknown. The frequentist framework does not prescribe a single way to estimate \(\theta\) from data; many estimators are possible. Suppose we take the sample mean \(\hat\theta=2/100=0.02\) as our estimate. How accurate is this estimate? We cannot know: judging it would require knowing the true value of \(\theta\). What we can ask is how accurate the estimator is, and that depends on two things:

• how well a random sample represents the true value, and

• how well the method (here, the sample mean) extracts information from the sample.

Accuracy in the frequentist view is instead a property of the procedure, evaluated over all the samples we could have gotten. If \(\theta\) were really \(0.02\), the number of diseased people in a sample of 100 would have the distribution \(\mathop{\mathrm{\mathrm{Bin}}}(100,0.02)\) and \(\hat\theta\) would be that number divided by 100; the resulting distribution of \(\hat\theta\) is shown below. The estimate equals \(0.02\) only about 27% of the time. Quantifying this spread, and resolving the apparent contradiction of assuming we know \(\theta\) in order to study the estimator, are the subjects of the chapter on frequentist parameter estimation.

1.2.1.2 The Bayesian view

In the Bayesian view, \(\theta\) is a random variable: we could be living in a universe where \(\theta\) is \(0.01\), or \(0.05\), or any other value, and in many cases we will never find out which. Treating \(\theta\) as a fixed number would then be a contradiction. We describe our initial belief about \(\theta\) using a prior distribution, say a uniform distribution over \([0,1]\), and update it using the two observed cases to obtain the posterior distribution \(p(\theta\mid\text{data})\). How to calculate the posterior from the prior and the data is the subject of the chapter on Bayesian parameter estimation; for our data it is shown below. The posterior is peaked at \(0.02\), its mode, with mean \(0.029\), but still allows other values. It is the whole answer: a number for \(\theta\) and how sure we are about it, in one distribution.

1.2.1.3 Source of uncertainty

In both views, the source of uncertainty is finite sample size. If we knew the disease status of 20 out of 1000 people with the allele, the same rate with ten times the data, both the distribution of the estimate \(\hat\theta\) and the posterior distribution of \(\theta\) would be more concentrated, with lower variance. Estimating \(\theta\) from the sample and quantifying the remaining uncertainty are the subjects of the chapters on frequentist and Bayesian parameter estimation.

1.2.2 Supervised machine learning

Consider the house-price problem from the start of the chapter: predict the sale price of a house from features such as location, lot size, square footage, and number of bedrooms. More generally, supervised machine learning problems have the following components:

• Data: \({\mathcal{D}}= \{(x_1, y_1),\dots,(x_n, y_n)\}, x_i \in {\mathcal{X}}, y_i \in {\mathcal{Y}}\). \({\mathcal{X}}\) is called the feature space, and \({\mathcal{Y}}\) is called the label space. As an example, each \(x_i\) could be a vector providing information about a house, e.g., (location, lot size, square footage, number of bedrooms, \(\dots\)), and \(y_i\) can be the sale price of the house.

• Goal: Find the “best” function \(f\) to predict \(y\) corresponding to a given \(x\). In other words, the function \(f\) produces an estimate \(\hat y=f(x)\) of \(y\) given features \(x\). Continuing our example, \(y\) would be the true but unknown price of the house with features \(x\), and \(f(x)\) would be a prediction (similar to what Zillow does).

• Evaluation: How do we define “best”? For a given data point \((x,y)\), evaluate the success of \(f\) using a loss function \(L(y, f(x))\), e.g., \(L(y, f(x))=|y-f(x)|\). Ideally, we would like to minimize the expected loss over all possible outcomes weighted by their probabilities, so we define \[\begin{equation} {\mathcal{L}}(f) = \mathop{\mathrm{{\mathbb{E}}}}[L(Y, f(X))], \end{equation}\tag{1.1}\] also known as the population risk, where the expectation is over the distribution \(p(x,y)\) of \((X,Y)\).

• Learning Algorithm: The algorithm that tries to find \[\begin{equation} f^* = \arg\min_{f} {\mathcal{L}}(f)=\arg\min_{f} \mathop{\mathrm{{\mathbb{E}}}}[L(Y, f(X))]. \end{equation}\tag{1.2}\]

If we have the joint distribution \(p(x,y)\), we can solve this problem exactly, at least in principle (see Section 1.2.2.2). But what we actually have is the data set \({\mathcal{D}}\). We will discuss how to address this mismatch through empirical risk minimization or by estimating the unknown distribution \(p(x,y)\) from \({\mathcal{D}}\) and then predicting with the estimate.

1.2.2.1 Source of uncertainty

Both sources of uncertainty appear in the house-price problem. The features do not determine the price: two houses identical on paper can sell for different amounts. There is noise from factors left out of the model. The relationship between features and prices must also be learned from a finite record of past sales, so finite sample size introduces uncertainty about that relationship. Section 1.3 makes this limitation concrete by showing how quickly finite data runs out when a language model is learned by counting.

1.2.2.2 What would knowing the distribution give us?

If the joint distribution \(p(x,y)\) of the features \(X\) and the target \(Y\) were known exactly, the supervised-learning problem would be solved: the expected loss could be evaluated, and the optimal predictor \(f^*\) could be found without learning from a finite dataset. Two common problems in supervised learning illustrate this:

• Regression: \({\mathcal{Y}}\) consists of scalars or vectors of reals. For example, predicting stock price based on financial information, or determining the score someone will assign a movie based on previous scores. A common loss function is the quadratic or squared error loss function: \[\begin{equation} L(y, f(x)) = (y-f(x))^2. \end{equation}\tag{1.3}\] For this loss, if the distribution is known, the best predictor is \[\begin{equation} f^*(x) = \mathop{\mathrm{{\mathbb{E}}}}[Y|X=x]. \end{equation}\tag{1.4}\] For a fixed \(x\), \(\mathop{\mathrm{{\mathbb{E}}}}[(Y-c)^2\mid X=x]\) is smallest at \(c=\mathop{\mathrm{{\mathbb{E}}}}[Y\mid X=x]\), so predicting the conditional mean minimizes the expected loss at every \(x\), and hence overall.

• Classification: \({\mathcal{Y}}\) consists of classes or categories. For example, speech recognition, handwriting recognition, the presence or absence of a disease. A common loss function is the 0-1 loss: \[\begin{equation} L(y, f(x)) = \begin{cases} 1, & \text{if $y \neq f(x) $}.\\ 0, & \text{if $y = f(x)$}. \end{cases} \end{equation}\tag{1.5}\] In this case, if the distribution is known, then the best classifier is \[\begin{equation} f^*(x) = \arg \max_{y\in{\mathcal{Y}}} p(y|x). \end{equation}\tag{1.6}\] Given \(x\), the probability of error is \(1-p(f(x)|x)\), which is smallest when \(f(x)\) is the most likely class.

We emphasize again that to solve the problem optimally as in (1.4) and (1.6), we need to know the joint distribution of \((X,Y)\) or the conditional distribution of \(Y\) given \(X\).

Knowing the joint buys one more thing: generation. We can sample a fresh pair \((X,Y)\) from \(p(x,y)\), or, given \(x\), sample \(Y\) from \(p(y|x)\), using the sampling methods of Chapter 0. In the context of large language models, discussed later, the task may be to generate a response \(y\) given a prompt \(x\).

1.3 From Coin Flips to Language Models

A Bernoulli random variable is about as simple as a model gets: one number, the probability of heads, says everything there is to say about a biased coin. A month of daily weather asks for more, because a model of the whole record has to say how each day depends on the days before it. A model of English asks for much more again, since it must give a probability to every sentence anyone might write, and with a vocabulary of ten thousand words there are \(10^{80}\) strings of twenty words to account for. All three are joint distributions over the quantities we care about. What separates them is how complex they are and how much structure we impose to keep the model small enough to learn from data.

The tools for imposing that structure are already in Chapter 0: the chain rule, which factors a joint distribution into conditional distributions, and conditional independence, which lets each factor forget most of what it conditions on. This section applies them to sequences and follows one construction the whole way, from a sequence of Bernoulli variables recording rain or no rain to the next-token models that large language models are built from.

1.3.1 Why the full joint distribution grows so quickly

Suppose we record the weather at one location for \(d\) days. Let \(X_t=1\) mean that it rains on day \(t\), and let \(X_t=0\) mean that it does not. Our goal is to model the complete sequence \[X_{1:d}=(X_1,\dotsc,X_d),\] not just the weather on one particular day. With such a model, we could assign a probability to an event such as a week of continuous rain, or we could generate possible weather sequences.

For three days, there are eight possible sequences: \[000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111.\] In general, \(d\) binary observations have \(2^d\) possible sequences. A table that gives a probability to every sequence therefore needs \[\begin{equation} 2^d-1 \end{equation}\tag{1.7}\] free parameters. The subtraction by one appears because all the probabilities must sum to one. For a 30-day record, the number is \[2^{30}-1=1{,}073{,}741{,}823.\] We would have trouble even filling such a table with useful estimates: an ordinary weather dataset would contain little or no information about most of the possible 30-day sequences.

1.3.2 The joint distribution in autoregressive form

The rain record showed how fast a distribution over a whole sequence grows. The chain rule rewrites such a distribution as a chain of next-step predictions.

That form matches how sequences are used. Words arrive one after another, and what we usually want from a model is the distribution of the next word given what has been written so far, whether we are generating text, scoring a sentence, or filling in a blank. A model of those next-step distributions is already a model of the whole sequence, with nothing lost.

It is also the form in which approximations can be made. A table over all sequences has one number for each of them and no structure to take advantage of. Once the distribution is written as a chain, every factor conditions on a history, and the history is where an assumption can be applied: keep the last few tokens and drop the rest, or summarize the history with a function that has a fixed number of parameters. Either one turns an unusable table into a model that can be estimated from a finite corpus, and both are developed in the rest of this section.

Text will be our running example, though the construction applies to any ordered data, including music, DNA, and a sequence of measurements. We write the vocabulary of possible tokens as \({\mathcal{V}}\) and its size as \(V=|{\mathcal{V}}|\).

Let \(W_1,W_2,\dotsc,W_T\) be the random tokens in a sequence, and let \(w_1,w_2,\dotsc,w_T\) denote a particular sequence of values. The chain rule gives \[\begin{equation} p(w_1,\dotsc,w_T) =p(w_1)\prod_{t=2}^{T}p(w_t\mid w_1,\dotsc,w_{t-1}). \end{equation}\tag{1.8}\] It is convenient to abbreviate \((w_1,\dotsc,w_{t-1})\) as \(w_{1:t-1}\), so the same factorization can be written as \[p(w_{1:T})=\prod_{t=1}^{T}p(w_t\mid w_{1:t-1}),\] where the factor for \(t=1\) is \(p(w_1)\). It says that we can describe the first token, then the second given the first, then the third given the first two, and so on. Equation (1.8) is an identity: it makes no independence assumption and discards no part of the history. For the same reason it does not by itself make the model any smaller. If every next-token distribution may depend on the entire history, the conditional tables together hold as many free parameters as the joint distribution they came from, which for the 30-day weather record is the same \(2^{30}-1\) numbers as before.

Thus a model that predicts only the next token is also a model of the entire sequence. The product of all of its next-token probabilities gives the joint probability of that sequence. Conversely, sampling once from each conditional distribution, from left to right, produces a sample from the joint distribution.

Sentences do not all have the same length, so it is useful to add a special end-of-sequence token \(\mathrm{EOS}\). If \(w_{T+1}=\mathrm{EOS}\), then \[\begin{equation} p(w_{1:T},\mathrm{EOS}) =\prod_{t=1}^{T+1}p(w_t\mid w_{1:t-1}). \end{equation}\tag{1.9}\] The probability of ending is therefore treated in exactly the same way as the probability of producing any other token.¹ We will also use a special beginning-of-sequence token, written \(\mathrm{BOS}\). It is an artificial token placed before the first real token of every sequence: it tells the model that generation is starting. For example, the first prediction can be written \(p(w_1\mid\mathrm{BOS})\). Thus possible next tokens belong to \({\mathcal{V}}\cup\{\mathrm{EOS}\}\), while a context may also contain \(\mathrm{BOS}\).

1.3.3 Finite-context approximations

The exact factorization in (1.8) becomes difficult to use as the sequence grows. The conditional distribution at position \(t\) may depend on an arbitrarily long prefix, and a separate table row would be needed for every possible prefix. A finite-order model replaces the entire prefix by a fixed-length context.

The context \(w_{t-k:t-1}\) plays the role of the state. The cases \(k=0,1,2\) are especially helpful for understanding the assumption:

We will use the same context-to-next-token distribution at every position in the sequence. In other words, the conditional probability does not depend on \(t\), which makes the model a time-homogeneous Markov chain whose state is the last \(k\) tokens. Its transition table has one row for each of the \(V^k\) contexts.

Finite context makes the model manageable, but its size still grows rapidly. Ignoring boundary symbols, an order-\(k\) model has as many as \(V^k\) contexts. For every context it must specify a categorical distribution over \(V\) possible next tokens. Such a distribution has \(V-1\) free parameters: the probabilities of the \(V\) possible next tokens must sum to one, so once \(V-1\) are chosen, the last is determined. Thus a complete conditional table has as many as \[\begin{equation} V^k(V-1) \end{equation}\tag{1.11}\] free parameters. This count omits the initial or \(\mathrm{BOS}\) row. For the binary order-1 rain model, it gives two transition parameters, and the probability of rain on the first day makes three numbers in all. Equivalently, the table contains on the order of \(V^{k+1}\) entries. If \(V=10{,}000\), even an order-2 table has up to \(10^8\) contexts and on the order of \(10^{12}\) entries. Most of these contexts will not appear in a realistically sized corpus.

The approximation also determines which relationships the model can express. For example, in \[\text{``The cats that I saw yesterday at the park \underline{\hspace{8mm}}.''}\] the correct choice “were” depends on “cats,” which is many words earlier. Any context that does not reach back to “cats” must predict without that information. Increasing \(k\) can include more such relationships, but it also increases the number of contexts that must be learned.

1.3.4 Learning conditional tables from counts

Suppose we are given a corpus \({\mathcal{D}}\) of token sequences. For an order-\(k\) model, let \(c\in({\mathcal{V}}\cup\{\mathrm{BOS}\})^k\) denote a context of length \(k\), and define \[\begin{align*} N(c,w)&=\text{the number of times token $w$ follows context $c$ in ${\mathcal{D}}$},\\ N(c)&=\sum_{u\in{\mathcal{V}}\cup\{\mathrm{EOS}\}}N(c,u). \end{align*}\] Here \(N(c)\) is the total number of observed continuations of \(c\). For an observed context, define the empirical conditional distribution, or relative-frequency estimate, by \[\begin{equation} \hat p_k(w\mid c)=\frac{N(c,w)}{N(c)}. \end{equation}\tag{1.12}\] This estimate is defined only for an observed context with \(N(c)>0\), and it assigns probability zero to a continuation with \(N(c,w)=0\).² The entries in every observed row form a probability distribution because \[\sum_{w\in{\mathcal{V}}\cup\{\mathrm{EOS}\}}\hat p_k(w\mid c) =\frac{\sum_{w\in{\mathcal{V}}\cup\{\mathrm{EOS}\}}N(c,w)}{N(c)}=1.\] This is a count-based estimate constructed from the corpus. The next chapter will show that it is also the maximum-likelihood estimate for a categorical next-token distribution.

For each context, count its observed continuations and divide by the row total. The result is a categorical next-token distribution for that context.

1.3.5 Generating a sequence one token at a time

Once the conditional table is available, generation is a repeated categorical sampling procedure. For an order-\(k\) model:

1. Initialize the context with \(k\) copies of \(\mathrm{BOS}\).

2. Sample the next token \(w\) from \(\hat p_k(\mathord\cdot\mid c)\).

3. If \(w=\mathrm{EOS}\), stop. Otherwise append \(w\) to the sequence.

4. Form the new context by discarding the oldest context token and appending \(w\), and then return to step 2. For \(k=0\), the context remains empty.

Each draw can be carried out by the categorical inverse-CDF procedure from the probability review: divide \([0,1)\) into intervals whose lengths are the row probabilities and use a uniform draw to select an interval.

Sampling is different from always selecting the most probable next token. Always taking the largest-probability continuation produces a single deterministic path (apart from ties). Sampling preserves the alternatives and their probabilities, so repeated runs can produce different sequences.

1.3.6 Expressiveness versus data

The order \(k\) controls both what the model can represent and how much data it needs. These two effects pull in opposite directions.

If \(k\) is small, many distinct histories are mapped to the same context. This allows the model to pool counts and estimate each row from more observations, but it also forces histories with genuinely different next-token behavior to share a distribution. An order-0 word model, for example, can learn that “the” is common but cannot learn that “the cat” is more natural than “the the.” A small-context model therefore tends to underfit: it ignores useful structure that is present in the sequence.

If \(k\) is large, the model can distinguish more histories. It is more expressive, but the \(V^k\) possible contexts divide a fixed corpus into many small groups. Most contexts may occur once or not at all. A context seen once has a row that assigns probability one to its single observed continuation, while an unseen context has no estimated row. As the context approaches the length of a training sequence, generation increasingly reproduces pieces of the corpus instead of combining evidence across related contexts. This is memorization caused by sparse data, not proof that the sequence is deterministic.

The small corpus above makes the distinction concrete. An order-1 model pools all occurrences of “cat,” regardless of what precedes it. Since “cat” is followed twice by “sat” and once by “slept,” it assigns \[\hat p_1(\text{sat}\mid\text{cat})=\frac23, \qquad \hat p_1(\text{slept}\mid\text{cat})=\frac13.\] It can therefore generate the new combination “a cat slept.” The order-2 model makes the more specific distinction between \((\text{the},\text{cat})\) and \((\text{a},\text{cat})\); on this small dataset, that extra expressiveness also prevents it from making the new combination. Neither behavior is always correct. We need enough context to express important dependencies and enough observations to estimate the resulting conditional distributions.

1.3.7 Beyond a separate table for every context

The order-1 and order-2 examples leave us with an uncomfortable choice. The order-1 model combines many histories into the same short context, so it has more observations for each row but forgets useful information. The order-2 model remembers more, but learns the rows for \((\text{the},\text{cat})\) and \((\text{a},\text{cat})\) separately. What if we want to remember a richer context without treating every context as a completely separate case?

The count table cannot give us that. It keeps one row for every context, so its size is not something we choose: it is whatever the vocabulary and the context length make it. With \(V=10{,}000\), the count (1.11) is about \(10^{12}\) free parameters at \(k=2\) and about \(10^{24}\) at \(k=5\). A model whose number of parameters grows in this way, with the number of distinct contexts rather than being fixed in advance, is called non-parametric.

Storage is the smaller of the two problems. Each row is estimated from the occurrences of its own context and from nothing else, while a corpus of \(10^{9}\) tokens contains at most \(10^{9}\) contexts however many rows the table has. At \(k=5\), all but a vanishing fraction of the rows are therefore empty, and an empty row means the model has learned nothing whatsoever about what follows that context. Past a modest \(k\), the table can no longer be learned at all, whatever the storage budget.

Instead of looking up a row in a table, we can use one function for all contexts. We give it a context \(c\), and it returns the probabilities of the possible next tokens: \[\begin{equation} c\longmapsto f_\theta(c)=\boldsymbol{\pi}_\theta(c), \qquad p_\theta(W_t=w\mid c)=\pi_{\theta,w}(c). \end{equation}\tag{1.13}\] Instead of storing an independent answer for every context, we use one adjustable function for all contexts. Here \(\theta\) collects all the adjustable numbers in the function, and its length is chosen when the model is designed. A parametric model is a model controlled by such a fixed set of parameters. The important difference is how the parameters are used: a lookup table spends a separate row on every context, whereas \(f_\theta\) answers every context with the same \(\theta\). As a result, what the model learns from one context can affect its predictions in another. The trade-off is that the function cannot choose every context row independently. It works well when patterns learned in one context are useful in another.

Two ideas make such a function possible. The first is to stop treating tokens as unrelated symbols. In a count table, the rows for \((\text{the},\text{cat})\) and \((\text{a},\text{kitten})\) have nothing to do with each other, because two symbols are either identical or unrelated and counts collected for one row never inform another. A parametric model instead represents each token by a vector of real numbers, called an embedding, so that a context becomes a collection of vectors rather than a collection of symbols. Vectors admit degrees of similarity: “cat” and “kitten” can sit close together, and a function that varies smoothly with its input then returns similar next-token distributions for the two contexts above. The embeddings are themselves part of \(\theta\) and are learned along with everything else, so the model decides which tokens belong near each other.

The second idea is to build \(f_\theta\) by composing many simple steps, each a linear map of its input followed by a fixed nonlinear function applied to every coordinate. This is a neural network, and we do not need its internal details here. The nonlinearity is what makes the composition worth anything, since composing linear maps only produces another linear map; with it, a moderate number of parameters describes a rich family of functions of the context vectors. The size of \(\theta\) is set by the widths of those maps and not by the number of contexts, so the context can be made longer without the parameter count following \(V^{k}\). That is how a language model conditions on thousands of previous tokens:

The two tables assume \(V=10{,}000\), and the last row is the range spanned by the language models in use today. The neural model reaches back hundreds of times further than the order-5 table while holding far fewer parameters, because its parameters are shared across contexts rather than divided among them.

Changing how we obtain the next-token probabilities does not change the autoregressive model itself. We still have \[\begin{equation} p_\theta(w_{1:T}) =\prod_{t=1}^{T}p_\theta(w_t\mid w_{1:t-1}), \end{equation}\tag{1.14}\] and generation still means obtaining a distribution, sampling a token, appending it to the context, and repeating.

One question remains: how should we choose \(\theta\)? For the table, we counted the observed continuations and normalized each row. For a more general function, there may be no such direct formula. The next chapter develops the general answer: choose parameters that make the observed data probable. The connection to this section comes from \[\log p_\theta(w_{1:T}) =\sum_{t=1}^{T}\log p_\theta(w_t\mid w_{1:t-1}).\] The probability of a sequence is a product of next-token probabilities, so its log probability is a sum of next-token terms. We will make use of this fact when we study how to learn the parameters.

1.4 Information theory and machine learning

Information theory deals with quantifying information and the rules that govern its transmission, storage, and transformation from one form to another. It has applications in communications, data storage, machine learning, and biology. In machine learning it can be used to help better understand relationships between knowns and unknowns, design loss functions, and establish fundamental limits on how well we can do with a certain amount of data (regardless of the type of algorithm and computational resources).

1.4.1 Quantifying uncertainty

Let \(X\) be a Bernoulli random variable that is equal to 1 if it is raining in Seattle and 0 otherwise. Similarly, let \(Y\) indicate whether it’s raining in Phoenix. How much information do \(X\) and \(Y\) provide us? Alternatively, before they are revealed, how uncertain are we about \(X\) and about \(Y\)? Can we measure the information content of a random variable, or equivalently, our uncertainty about it?

Let’s look at specific outcomes for each variable:

So as a function of probability, the amount of information of a given statement decreases as the probability increases. If the probability of an outcome is \(p\), what is a good function describing the amount of information we gain from learning that the outcome has occurred? A good choice is the self-information function \(i(p)=\log\frac{1}{p}\), shown in Figure 1.1 when the base of the log is 2. Then the information content of the statement ‘\(X=x_i\)’ is \[i(p(x_i))=\log\frac{1}{p(x_i)}.\] And the amount of information on average for a random variable \(X\) that takes values in the set \({\mathcal{X}}=\{x_1,\dotsc,x_m\}\) is the entropy, \[\begin{equation} H(X)=\mathop{\mathrm{{\mathbb{E}}}}\left[\log\frac{1}{p(X)}\right]=\sum_{i=1}^m p(x_i)\log \frac{1}{p(x_i)}, \end{equation}\tag{1.15}\] where for continuous RVs, the sum must be replaced with an integral. If the log is base 2, then the unit is a bit.

If there are \(m\) different possible outcomes, then \[0\le H(X)\le \log m,\] with \(H(X)=0\) when the outcome is certain and \(H(X)=\log m\) when all outcomes are equally likely. For example, a fair die has entropy \(\log_2 6\simeq 2.58\) bits, the maximum possible for six outcomes.

This special case is common enough to have its own name and notation: the binary entropy function \[H_b(p)=p\log \frac1p+(1-p)\log\frac1{1-p}\] is the entropy of any experiment with two outcomes of probabilities \(p\) and \(1-p\). For example, \[\begin{align*} H(\text{Fair coin})&=H_b\left(\frac12\right)=1,\\ H(\text{6 on a die})&=H_b\left(\frac16\right)=0.65,\\ H(\text{Rain/no rain in Seattle})&=H_b\left(\frac{150}{365}\right)=0.977,\\ H(\text{Rain/no rain in Phoenix})&=H_b\left(\frac{33}{365}\right)=0.438,\\ H(\text{Rain/no rain in the Sahara})&=H_b\left(\frac{1}{365}\right)=0.0273. \end{align*}\] The plot for binary entropy is given in Figure 1.1. The maximum entropy is 1 bit. This makes sense since we can represent the outcome with 1 bit. Random variables with equal chances of 0 and 1 have the highest entropy (and maximum uncertainty). Those with predictable outcomes have lower entropies.

Entropy was introduced by Shannon in his article “A mathematical theory of communication” in 1948, where he also popularized the term bit (binary digit).

1.4.2 Data compression and the meaning of entropy

Entropy measures average uncertainty, but it also has a direct operational meaning: it provides a fundamental bound on how compactly we can represent information. Specifically, entropy bounds the performance of lossless data compression: no data compression method, regardless of computational complexity, can beat entropy.

Suppose we want to represent the outcomes of a random variable as binary strings. That is we want to construct a source code, consisting of codewords, where each codeword represents an outcome. We aim for a code that is as short as possible on average. The strategy is intuitive: assign short codewords to likely outcomes and long codewords to unlikely ones. The question is how well we can do.

It turns out that the ideal code length for an outcome with probability \(p\) is \(\log_2(1/p)\) bits, exactly the self-information introduced earlier. A likely outcome (\(p\) close to 1) needs a short codeword; a surprising outcome (\(p\) close to 0) can have a long one. Averaging over outcomes, the minimum achievable average code length is the entropy \(H(X)\). This is Shannon’s source coding theorem.

1.4.3 Relative entropy, or what if we get the distribution wrong?

The previous subsection showed that knowing the true distribution \(p\) lets us compress down to \(H(X)\) bits per symbol. But what if we do not know \(p\) and instead design our code for a different distribution \(q\)?

Let \(X\) be a random variable with possible values \({\mathcal{X}}\) and distribution \(p\), and let \(q\) be another distribution over \({\mathcal{X}}\). A code optimized for \(q\) assigns roughly \(\log(1/q(x))\) bits to outcome \(x\). When the data actually follow \(p\), the average code length becomes the cross-entropy \[\begin{equation} H(p,q) = \sum_{x\in{\mathcal{X}}} p(x)\log\frac{1}{q(x)}. \end{equation}\tag{1.16}\] We also write \(H(p)\) for the entropy of a distribution \(p\); it is the same number as \(H(X)\) whenever \(p\) is the distribution of \(X\), and the same as \(H(p,p)\). The arguments tell the uses of \(H\) apart: with distributions, \(H(p,q)\) is the cross-entropy, and with random variables, \(H(X,Y)\) is the joint entropy introduced below.

Since the best possible average length is \(H(p)\), the penalty for using the wrong distribution is \[H(p,q) - H(p) = D(p\|q),\] the relative entropy, or Kullback–Leibler (KL) divergence: \[\begin{equation} D(p\|q)=\sum_{x\in{\mathcal{X}}} p(x)\log\frac{p(x)}{q(x)}. \end{equation}\tag{1.17}\]

The compression picture makes the key properties of relative entropy intuitive.

Non-negativity. No code can beat the entropy bound \(H(p)\), so compressing with the wrong distribution \(q\) can never be cheaper than using the true \(p\). Therefore \(D(p\|q)=H(p,q)-H(p)\ge 0\), with equality if and only if \(q=p\).

When relative entropy is large or infinite. If \(q\) assigns a tiny probability to an outcome that \(p\) considers common, the code designed for \(q\) wastes a huge number of bits on that outcome: \(\log(1/q(x))\) is large when \(q(x)\) is small. In the extreme case where \(q(x)=0\) for some \(x\) with \(p(x)>0\), the code for \(q\) has no codeword at all for an outcome that actually occurs; no finite number of bits suffices, and \(D(p\|q)=\infty\). In words, if the approximate distribution considers an event impossible but the true distribution does not, no amount of coding can compensate for that mistake.

Asymmetry: choosing the direction. Relative entropy is not symmetric: \(D(p\|q)\neq D(q\|p)\) in general.

1.4.3.1 Relative entropy as a cost function

So far \(D(p\|q)\) has measured the price of compressing with the wrong distribution. The same number measures how good an approximation \(q\) is to \(p\): it is zero exactly when the two agree, it grows as they separate, and it is infinite when \(q\) rules out an outcome that \(p\) allows. That makes it a natural quantity to minimize when fitting a model \(q\) to data drawn from \(p\), which is how it usually reaches machine learning.

The two directions also answer different compression questions. In \(D(p\|q)\), we compress data from the true distribution \(p\) using a code designed for our estimate \(q\); this is the “forward” direction used above. In \(D(q\|p)\), we compress data from our model \(q\) using a code designed for the truth \(p\). When does the reverse direction matter?

Suppose we are fitting an approximate distribution \(q\) to a true distribution \(p\). Minimizing \(D(p\|q)\) forces \(q\) to place probability mass wherever \(p\) does (otherwise the penalty is infinite), so \(q\) tends to cover all of \(p\)’s support, sometimes spreading mass too broadly. Minimizing \(D(q\|p)\) instead penalizes \(q\) for placing mass where \(p\) does not: if \(q(x)>0\) but \(p(x)=0\), then the term \(q(x)\log(q(x)/p(x))\) is \(+\infty\), so such a \(q\) is never chosen. So \(q\) concentrates on a high-probability region of \(p\), potentially ignoring some modes. Both directions arise in machine learning: \(D(p\|q)\) as the training objective for generative models via maximum likelihood, and \(D(q\|p)\) as the objective in variational inference, where \(q\) is a tractable approximation to an intractable posterior \(p\).

For a concrete case, let \(p\) be an equal mixture of two Gaussians, \[\begin{equation} p=\tfrac12\,\mathop{\mathrm{{\mathcal{N}}}}(-2,0.7^2)+\tfrac12\,\mathop{\mathrm{{\mathcal{N}}}}(2,0.7^2), \end{equation}\tag{1.18}\] and let the model \(q\) be a single Gaussian \(\mathop{\mathrm{{\mathcal{N}}}}(\mu,\sigma^2)\), which cannot reproduce two modes. Minimizing \(D(p\|q)\) gives the Gaussian with the same mean and variance as \(p\), namely \(\mu=0\) and \(\sigma=2.12\); it stretches across both modes and puts its own peak at \(x=0\), where \(p\) has almost no mass at all. Minimizing \(D(q\|p)\) gives \(\mu=1.98\) and \(\sigma=0.73\), a narrow Gaussian sitting on one mode and giving up the other; \(\mu=-1.98\) is equivalent by symmetry. Fig. 1.2 shows the two fits.

The two answers differ because of which distribution the average is taken under. \(D(p\|q)\) averages under \(p\), so it adds to the penalty wherever \(p\) has mass and \(q\) does not, because of the \(\log(p(x)/q(x))\) term, and so \(q\) has to cover everything \(p\) does. \(D(q\|p)\) averages under \(q\), so \(q\) is charged only where it places mass itself, and abandoning a mode costs nothing. Both behaviors, and the wider family of divergences that interpolates between them, are analyzed in [2, Fig. 1]. In short, relative entropy penalizes the second distribution being smaller than the first, especially if that smaller value is close to 0.

Since \(D(p\|q) = H(p,q) - H(p)\), for a fixed \(p\), minimizing cross-entropy over \(q\) is the same as minimizing the relative entropy, the form in which these measures typically appear as loss functions in machine learning.

1.4.4 Joint and Conditional Entropy; and Mutual Information

We can also measure the information in multiple random variables using entropy. The information in both \(X\) and \(Y\) is denoted \(H(X,Y)\) and is defined as \[H(X,Y)=\mathop{\mathrm{{\mathbb{E}}}}\left[\log\frac{1}{p(X,Y)}\right]=\sum_{x\in{\mathcal{X}}}\sum_{y\in{\mathcal{Y}}}p(x,y)\log\frac{1}{p(x,y)}.\] If we know \(Y\), how much information is left in \(X\)? This is denoted \(H(X|Y)\). If, for example \(X=Y+2\), then \(H(X|Y)=0\) since if we know \(Y\), we also know \(X\). Conditional entropy is defined as \[H(X|Y)=\sum_{y\in{\mathcal{Y}}}p(y) H(X|Y=y)=\mathop{\mathrm{{\mathbb{E}}}}\left[\log\frac{1}{p(X|Y)}\right]=H(X,Y)-H(Y).\]

Mutual information, \(I(X;Y)\), represents the amount of information that one random variable has about the other, and is defined as \[I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X).\] Equivalently, it can be written as a divergence: \[I(X;Y)=D(p_{X,Y}\,\Vert\, p_Xp_Y).\]

For two random variables these quantities fit together in a diagram, Fig. 1.3. Think of the area of the left circle as \(H(X)\) and that of the right circle as \(H(Y)\). Their overlap is the mutual information \(I(X;Y)\), the part that is left of each circle is a conditional entropy, and the total area covered is the joint entropy \(H(X,Y)\). Every identity above can be read off the picture: \(H(X,Y)=H(Y)+H(X|Y)\) is the right circle plus the left crescent, and \(I(X;Y)=H(X)-H(X|Y)\) removes the left crescent from the left circle. The picture also makes it clear that \(I(X;Y)\le\min\{H(X),H(Y)\}\), since an overlap cannot be larger than either circle. It should be used as a mnemonic and not as a proof, and it does not extend cleanly to three or more variables.

Three consequences of these definitions are used below. The first is the chain rule, immediate from \(H(X|Y)=H(X,Y)-H(Y)\): \[H(X,Y)=H(Y)+H(X|Y),\qquad H(X,Y|Z)=H(Y|Z)+H(X|Y,Z),\] where the second form is the same statement with every term conditioned on a third variable \(Z\). The second is that \(I(X;Y)\ge0\), since it is a relative entropy and relative entropy is non-negative (Exercise 1.18); equivalently, \[H(X|Y)\le H(X),\] with equality exactly when \(X\) and \(Y\) are independent. Observing \(Y\) can only reduce our average uncertainty about \(X\), although a particular outcome \(Y=y\) may well increase it. The third is the same fact in the presence of a further variable, \(H(X|Y,Z)\le H(X|Z)\): conditioning on more can only help.

1.4.5 Data processing and sufficient statistics

We rarely use data as it arrives. We average it, extract features from it, normalize it, drop the parts that look irrelevant, and pass it through the layers of a network. Every one of these steps replaces a variable by something computed from it. Can any of this increase what the data tells us about the quantity we care about?

The answer is no: Processing does not increase relevant information (although it has other benefits, clearly). This implies that if our input data is irrelevant, no amount of computation can do much. Precisely, for any two random variables \(U\) and \(V\) and any function \(g\), \[\begin{equation} I(g(V);U)\ \le\ I(V;U), \end{equation}\tag{1.19}\] which is called the data processing inequality. To see why, note that \(g(V)\) is determined by \(V\), so knowing \(V\) means knowing \(g(V)\), and hence \(H(U|V)=H(U|V,g(V))\le H(U|g(V))\). Subtracting each side from \(H(U)\) gives (1.19). The inequality also holds when the processing uses randomness. If its output is \(Z\), the required condition is that \(U\), \(V\), and \(Z\) form a Markov chain: once \(V\) is known, \(Z\) provides no further information about \(U\), or equivalently \[p(z|u,v)=p(z|v).\] This relationship is denoted \(U\to V\to Z\). Whatever \(Z\) learns about \(U\), it learns through \(V\), as a message passes along a chain of messengers. A deterministic output \(Z=g(V)\) is the simplest example, since \(g\) sees nothing but \(V\). In the game of telephone, the first player whispers a message \(U\), the second player hears \(V\) and passes it on, and the third player hears \(Z\). The third player hears only the second, so anything lost on the way to \(V\) is lost for good. In image editing, \(U\) is the scene, \(V\) is the photo of it, and \(Z\) is the edited version of the photo. Given the photo, the scene and the edited photo are independent.

In examples above \(V\) is produced from \(U\) and \(Z\) from \(V\), and it is tempting to read the arrows as cause and effect. The arrows record only which variable stands in the middle. Let \(V\) be the full state of a patient’s illness (which disease, and how severe), \(U\) their temperature, and \(Z\) their blood oxygen level. Assume that, conditional on the illness state, temperature and blood oxygen are independent. Then \(U\to V\to Z\) holds, even though the illness drives both readings and neither drives the other. The condition is symmetric, and \(Z\to V\to U\) is the same statement. The other orderings need not be Markov chains. \(V\to U\to Z\) would mean that once the temperature is known, the illness says nothing more about the blood oxygen, and \(U\to Z\to V\) that once the blood oxygen is known, the temperature says nothing more about the illness. Neither condition follows from the assumed independence given the illness state.

For a learning problem, take \(V=X\) to be the features, \(U=Y\) the label, and \(g=f\) a predictor. Whatever the predictor does with the features, all it ever reports about the label is its output \(\hat Y=f(X)\), and by (1.19), \[I(\hat Y;Y)\le I(X;Y).\] So no transformation of the features, no choice of model, and no variation in training on the same data can make that output say more about the label than the features already said.

The same inequality answers a question in statistics. Take the Bayesian view of Section 1.2.1.2: the parameter is a random variable \(\Theta\) with a prior distribution, and given \(\Theta=\theta\) the sample \(X=(X_1,\dotsc,X_n)\) has distribution \(p(x|\theta)\). Let \(S(X)\) be a statistic, that is, any function of the sample, such as the sample mean, the sample variance, or the largest observation. Then (1.19) with \(V=X\), \(U=\Theta\), and \(g=S\) gives \[I(\Theta;S(X))\le I(\Theta;X):\] so summarizing the data cannot increase what it says about the parameter. Usually a summary loses something. Which summaries lose nothing? Those for which the inequality also holds in the other direction, \(I(\Theta;X)\le I(\Theta;S(X))\). By the data processing inequality once more, it does if \(\Theta\to S(X)\to X\) is a Markov chain, that is, if \(X\) and \(\Theta\) are independent given \(S(X)\).

Equivalently, \(p(x|s,\theta)=p(x|s)\): once the summary is known, the parameter has no further effect on the sample. This is the form we usually check. For a sufficient statistic, then, the data processing inequality holds with equality, \[I(\Theta;S(X))=I(\Theta;X).\] So we can keep a sufficient statistic in place of the data and lose no information about the parameter.

The sample proportion \(S/n\) is also the maximum-likelihood estimator of \(\theta\) here, and it is a function of the count. Good estimators are usually functions of a sufficient statistic.

1.4.6 Fano’s inequality and the limits of prediction

Mutual information tells us, in a single number, how much the features say about the label. Does that number tell us how accurately the label can be predicted? Section 1.4.5 showed that no algorithm can increase it, but it did not say what a given amount of information buys. Fano’s inequality converts \(I(X;Y)\), or equivalently the uncertainty \(H(Y|X)=H(Y)-I(X;Y)\) left after the features are seen, into a lower bound on the error probability of every predictor. This is the third use of information theory mentioned at the start of the section, a limit on how well we can do regardless of the algorithm and the computational resources.

Let the label \(Y\) take one of \(m\ge2\) values in \({\mathcal{Y}}\). A predictor is any function \(\hat Y=f(X)\). We assume nothing about how \(f\) was obtained, so it may be a lookup table, a decision tree, or a neural network of any size. Its error probability is \[P_e=\Pr[\hat Y\ne Y].\]

Both terms on the right of (1.20) are near zero when \(P_e\) is, so a predictor can be rarely wrong only if the features leave almost no uncertainty about the label. In the other direction, uncertainty that the features do not remove has to show up as errors.

Using \(H_b(P_e)\le1\) and \(\log_2(m-1)\le\log_2 m\) gives a weaker but more readable form. In bits, \[\begin{equation} P_e\ \ge\ \frac{H(Y|X)-1}{\log_2 m}\ =\ \frac{H(Y)-I(X;Y)-1}{\log_2 m}. \end{equation}\tag{1.21}\] The label carries \(H(Y)\) bits of uncertainty and the features provide \(I(X;Y)\) of them, so \(H(Y|X)\) bits are left over, and all but one of these have to be paid for in errors. If \(H(Y|X)<1\), (1.21) says nothing, and (1.20) itself is needed.

For binary labels the second term of (1.20) vanishes, since \(\log(m-1)=\log 1=0\), and Fano’s inequality becomes \[\begin{equation} H_b(P_e)\ \ge\ H(Y|X). \end{equation}\tag{1.22}\] Since \(H_b\) is increasing on \([0,1/2]\), this says that \(P_e\) is at least the smaller of the two solutions of \(H_b(t)=H(Y|X)\). For example, if the features leave half a bit of uncertainty about a binary label, then no predictor can be wrong less than about \(11\%\) of the time, because \(H_b(0.11)\simeq0.5\).

1.4.7 Fisher information: when the unknown is not random

Mutual information \(I(X;Y)\) measures what \(X\) tells us about \(Y\), and exists only because \(Y\) is a random variable. In the frequentist view of Section 1.2.1.1 the unknown is not random: the parameter \(\theta^*\) is a fixed number that we happen not to know, and the data \({{\boldsymbol{X}}}\sim p({{\boldsymbol{x}}};\theta^*)\) are the only random objects in the problem. How much does the data tell us about \(\theta\)? In the Bayesian view \(\Theta\) has a distribution and \(I(\Theta;{{\boldsymbol{X}}})\) is available, which is how Section 1.4.5 defined sufficiency. The frequentist view needs a different measure of information.

What makes \(\theta^*\) easy or hard to determine is how much the distribution of the data changes as \(\theta\) moves. If \(p(\cdot\,;\theta)\) and \(p(\cdot\,;\theta')\) are the same for two different values \(\theta\) and \(\theta'\), no procedure can tell the two apart, however much data it sees. If they are very similar, many observations are needed to tell \(\theta\) from \(\theta'\), and the closer the two distributions, the more it takes. If a small change in \(\theta\) visibly reshapes the distribution, a modest sample is enough.

Relative entropy measures how distinguishable two distributions are. Fix \(\theta\) and consider \(D(p_\theta\|p_{\theta+\delta})\) as a function of \(\delta\), using natural logarithms, as is conventional here. It is zero at \(\delta=0\) and non-negative everywhere, so \(\delta=0\) is a minimum, its first derivative vanishes there, and its leading term is quadratic.³ The Fisher information at \(\theta\) is twice the coefficient of that quadratic term, \[\begin{equation} \begin{gathered} {\mathcal{I}}(\theta)=\lim_{\delta\to0}\frac{2}{\delta^2}\,D(p_\theta\,\|\,p_{\theta+\delta}),\\ \text{equivalently}\quad D(p_\theta\,\|\,p_{\theta+\delta})=\tfrac12\,{\mathcal{I}}(\theta)\,\delta^2+o(\delta^2) \end{gathered} \end{equation}\tag{1.23}\] as \(\delta\to0\), written \({\mathcal{I}}\) to keep it apart from the mutual information \(I(X;Y)\). So \({\mathcal{I}}(\theta)\) is the curvature of the divergence at its minimum: the narrower the valley around \(\theta\), the more a small change in the parameter changes the distribution of the data, and the more each observation tells us about \(\theta\). Fig. 1.5 shows the valley for a coin.

In the chapter on parameter estimation, we will see how Fisher information can be used to bound the accuracy of estimators quantitatively.

While this overview is sufficient for our purposes in this course, if you are interested, you can check out the slides for this Short Lecture on Information Theory, or the course Mathematics of Information. The standard reference for the subject is Cover and Thomas [1].

References