Chance: The Notation of Probability

Discover: one line that switches neurons off

Dropout is one of the simplest tricks in deep learning, and one of the most widely used. While a network trains, you switch off a random selection of its units at every step, so that no unit can lean too heavily on any other. Here is how the 2014 journal paper on dropout writes that idea down:

You can already read half of it. From Chamber 1: $r_j^{(l)}$ is an $r$ with two addresses, unit $j$ in layer $l$, and the bracketed superscript is an index, not a power. The bold $\mathbf{y}^{(l)}$ is the vector of layer $l$'s outputs, and the tilde on $\widetilde{\mathbf{y}}^{(l)}$ marks a modified copy. The $*$ is this paper's symbol for multiplying two vectors entry by entry (Chamber 6 writes it $\odot$).

What's new is the language of chance: the $\sim$ and the word $\mathrm{Bernoulli}(p)$. Each $r_j^{(l)}$ is a coin toss that comes up 1 (keep the unit) or 0 (drop it), and multiplying by it zeroes out the dropped units. By the end of this chamber you'll read every symbol of this line, and of the much more intimidating objective that trains a generative adversarial network (GAN).

Learn: outcomes, events and P

Every probability statement starts with an experiment whose result is uncertain: rolling a die, picking a training example, initialising a network. The set of every possible outcome is the sample space, written $\Omega$ (capital omega). For one roll of a die, $\Omega = \{1, 2, 3, 4, 5, 6\}$.

An event is a set of outcomes, so it's a subset $A \subseteq \Omega$, in the language of Chamber 2. “The roll is even” is the event $A = \{2, 4, 6\}$. The probability $P(A)$, read “P of A”, is a number between 0 and 1 saying how likely $A$ is. For a fair die, every outcome has probability $\tfrac16$, so $P(A) = \tfrac36 = \tfrac12$.

Three rules, known as Kolmogorov's axioms, are all the theory needs:

• $P(A) \ge 0$ for every event $A$.
• $P(\Omega) = 1$: something happens.
• If $A$ and $B$ can't happen together ($A \cap B = \emptyset$), then $P(A \cup B) = P(A) + P(B)$.

Everything else follows. For example, $A$ and its complement $A^c$ (“not $A$”) never happen together, and between them they cover all of $\Omega$. So the third rule and then the second give $P(A) + P(A^c) = P(\Omega) = 1$, which means $P(A^c) = 1 - P(A)$. That's a complete proof, three lines long.

Set operations from Chamber 2 become sentences about chance. $P(A \cap B)$ is “P of A and B”: both happen. Papers often write it with a comma, $P(A, B)$, because in probability a comma means “and”. $P(A \cup B)$ is “P of A or B”, where “or” means at least one of them. With $B = \{4, 5, 6\}$, “at least 4”:

The union formula is inclusion–exclusion again: without the subtraction, the outcomes 4 and 6 would be counted twice.

Learn: the vertical bar means “given”

Information changes probabilities. Suppose a friend peeks at the die and tells you only “it's at least 4”. The chance that it's even is no longer $\tfrac12$: the world has shrunk to $B = \{4, 5, 6\}$, and two of those three outcomes are even. That's conditional probability:

Read it “P of A given B”. The recipe is to keep only the part of $A$ that lies inside $B$, then divide by $P(B)$ so that the new, smaller world has total probability 1. For the die, $P(A \mid B) = \frac{2/6}{3/6} = \frac23$.

Multiplying both sides by $P(B)$ gives the product rule, $P(A \cap B) = P(A \mid B)\,P(B)$: the chance of both is the chance of $B$, times the chance of $A$ once $B$ has happened.

Two events are independent when knowing one tells you nothing about the other: $P(A \mid B) = P(A)$. By the product rule that's the same as $P(A \cap B) = P(A)\,P(B)$. Independence can surprise you. On a fair die, “even” and “at most 2” are independent: $P(\{2\}) = \tfrac16$, which is exactly $\tfrac12 \cdot \tfrac13$.

Learn: Bayes' rule, derived

The product rule works in both directions, and that's all you need to derive the most famous formula in probability. Here is the derivation in full.

1. 1

   Write the joint probability one way

   Condition on $B$: $P(A \cap B) = P(A \mid B)\,P(B)$.

2. 2

   Write it the other way

   $A \cap B$ is the same event as $B \cap A$, so we can also condition on $A$: $P(A \cap B) = P(B \mid A)\,P(A)$.

3. 3

   Set the two equal and divide

   Both right-hand sides equal $P(A \cap B)$, so they equal each other. Dividing by $P(B) > 0$:

   $$P(A \mid B) = \frac{P(B \mid A)\,P(A)}{P(B)}.$$
4. 4

   Expand the bottom

   $B$ happens either together with $A$ or together with $A^c$, never both, so the third axiom and the product rule give the law of total probability:

   $$P(B) = P(B \mid A)\,P(A) + P(B \mid A^c)\,P(A^c).$$

That's Bayes' rule. It turns a probability you can measure, $P(B \mid A)$, into the one you actually want, $P(A \mid B)$. In machine learning, $A$ is usually a hypothesis $h$ and $B$ is data $D$, and each piece has a name:

A worked example shows why it matters. A condition affects 1% of people. A test detects it 90% of the time, but also comes back positive for 9% of healthy people. You test positive. How worried should you be?

About 9%, not 90%. Picture 1,000 people: 10 are ill and 9 of them test positive, but about 89 of the 990 healthy people test positive too. Only 9 of the roughly 98 positives are actually ill. The prior, 1%, matters enormously.

Learn: random variables and the little p

Most of the time we care about numbers, not events: the number rolled, a pixel's brightness, a model's loss. A random variable is a number whose value depends on chance. Convention: a capital letter $X$ for the random variable, and a lower-case $x$ for a particular value it might take. So $P(X = x)$ reads “P of big X equals little x”, the probability that $X$ comes out as $x$.

Papers abbreviate this constantly. $p(x)$, with a lower-case $p$, is the distribution of $X$ at the value $x$:

• For a discrete $X$ (finitely many values, like a die), $p(x) = P(X = x)$. This is a probability mass function (pmf), and its values add up to 1.
• For a continuous $X$ (any real number, like a height), $p(x)$ is a probability density function (pdf). A single value has probability zero, and probabilities are areas: $P(a \le X \le b) = \int_a^b p(x)\,dx$, the continuous sum of Chamber 7. A density can be larger than 1. Only the total area must be 1.

With two random variables, $p(x, y)$ is their joint distribution. Here is a small one, for tomorrow's weather $X$ and whether someone carries an umbrella $Y$:

The marginal distribution of one variable comes from adding the other one up: $p(\text{rain}) = \sum_y p(\text{rain}, y) = 0.30 + 0.10 = 0.40$. The name is literal: those totals are written in the margins of the table. For continuous variables the sum becomes an integral, $p(x) = \int p(x, y)\,dy$. Either way, people say that $y$ has been summed out, or marginalised out.

The conditional distribution works just like conditional probability: $p(y \mid x) = p(x, y) / p(x)$. So $p(\text{umbrella} \mid \text{rain}) = 0.30 / 0.40 = 0.75$. And $X$ and $Y$ are independent, written $X \perp\!\!\!\perp Y$, when $p(x, y) = p(x)\,p(y)$ for every pair. Here they're not: $p(\text{rain})\,p(\text{umbrella}) = 0.4 \times 0.35 = 0.14$, far from $0.30$.

Now the most important line in this chamber for machine learning. A classifier with parameters $\theta$ doesn't just output a label. It outputs a whole distribution over labels, written

read “p theta of y given x”: the probability the model gives to label $y$ when it sees input $x$. The subscript is Chamber 4's $f_\theta$ again, saying which model's probabilities these are.

Learn: drawing samples

To say that $x$ is a sample from a distribution $p$, papers write $x \sim p$, read “x is drawn from p” or “x is distributed as p”. It's a different symbol from Chamber 1's $\approx$, and a different job from the tilde decoration on $\tilde{x}$.

A handful of distributions have their own names:

• Bernoulli, $\mathrm{Bernoulli}(p)$: a biased coin. The value is 1 with probability $p$ and 0 with probability $1 - p$. Dropout's masks are Bernoulli.
• Normal (or Gaussian), $\mathcal{N}(\mu, \sigma^2)$: the bell curve centred at the mean $\mu$ with spread $\sigma$. $\mathcal{N}(0, 1)$ is the standard normal.
• Uniform, $\mathcal{U}(a, b)$: every value between $a$ and $b$ equally likely.

The normal distribution's density is worth reading once, symbol by symbol. It's Chamber 4's $\exp$ applied to a squared distance from $\mu$, scaled by $\sigma^2$, with a constant in front that makes the total area 1:

When a whole dataset is drawn, papers add “i.i.d.”: $x_1, \ldots, x_n \overset{\text{i.i.d.}}{\sim} p$ means independent and identically distributed. Every sample comes from the same $p$, and none influences another. It's the standing assumption behind the dataset $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{n}$ of Chamber 2.

You'll meet $\sim$ everywhere: random initial weights such as $W_{ij} \sim \mathcal{N}(0, 0.01)$, noise $\varepsilon \sim \mathcal{N}(0, 1)$ added to data, a minibatch sampled from the training set, and dropout's coins. In Chamber 9 you'll see a variational autoencoder draw $\varepsilon \sim \mathcal{N}(0, 1)$ and set $z = \mu + \sigma\varepsilon$, which gives $z \sim \mathcal{N}(\mu, \sigma^2)$.

Learn: expectation, the long-run average

The expectation (or expected value) of $X$ is its average, with each value weighted by its probability:

Read $\mathbb{E}[X]$ as “the expectation of X”; the $\mathbb{E}$ is blackboard bold (Chamber 1). For a fair die, $\mathbb{E}[X] = \frac{1 + 2 + 3 + 4 + 5 + 6}{6} = 3.5$: a value the die never actually shows, but the balance point of its distribution.

Often we want the average of some function of a random variable. The subscript says what's random and where it comes from:

read “the expectation of f of x, with x drawn from p”. You'll meet this shape in the GAN objective at the end of this chamber. And here's the idea that makes it usable: if $x_1, \ldots, x_n \overset{\text{i.i.d.}}{\sim} p$, then

and the approximation gets better as $n$ grows. That's the law of large numbers. It's why a training loss, $\frac{1}{n}\sum_{i} \ell(\theta; x_i, y_i)$, is a sensible stand-in for the expected loss on data you haven't seen, and why a minibatch gradient is a sensible stand-in for the full gradient.

A proof: expectation is linear

Here is a complete proof of the property you'll use most, for a discrete random variable.

Claim. For any constants $a$ and $b$, $\mathbb{E}[aX + b] = a\,\mathbb{E}[X] + b$.

Proof. The random variable $aX + b$ takes the value $ax + b$ whenever $X = x$, so by the definition of expectation applied to $f(x) = ax + b$,

The middle step splits one sum into two and pulls the constants out (Chamber 5's linearity of sums). The last step uses the definition of $\mathbb{E}[X]$ for the first sum, and the fact that probabilities add up to 1 for the second. $\blacksquare$

The same argument shows $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$ for any two random variables, independent or not.

Two more summaries measure spread. The variance is the expected squared distance from the mean, and its square root is the standard deviation $\sigma$:

For the die, $\mathrm{Var}(X) = \frac{35}{12} \approx 2.92$ and $\sigma \approx 1.71$. The covariance $\mathrm{Cov}(X, Y) = \mathbb{E}\big[(X - \mathbb{E}[X])(Y - \mathbb{E}[Y])\big]$ asks whether two variables move together. Positive means they tend to be high together, negative means one is high when the other is low. Independent variables have covariance zero.

Now watch the law of large numbers happen. Each sample is unpredictable, but their running average $\bar{x}_n = \frac{1}{n}\sum_{i=1}^{n} x_i$ (Chamber 1's bar) is not.

Things to try:

1. With the fair die, draw one sample at a time for a while. The running mean jumps around. Then add a thousand and watch it flatten onto the dashed line at 3.5.
2. Compare Bernoulli with $p = 0.5$ against the die. Which settles within 0.05 of its expectation faster? The typical distance after $n$ samples is about $\sigma / \sqrt{n}$, so the smaller $\sigma$ wins.
3. Pick the normal distribution and set $\sigma = 2$. Check that the histogram's width matches the second argument of $\mathcal{N}(\mu, \sigma^2)$ as the lab writes it: $\sigma^2 = 4$, not 2.

Learn: likelihood and KL divergence

Two more pieces of notation turn probability into training objectives.

Given a dataset $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{n}$ of i.i.d. examples, independence lets the probability of the whole dataset factorise into a product. Read as a function of $\theta$, it's the likelihood:

Multiplying thousands of numbers below 1 underflows to 0 on a computer, so papers take the log, which turns the product into a sum (Chamber 5):

Maximum likelihood picks $\hat{\theta} = \argmax_\theta \sum_i \log p_\theta(y_i \mid x_i)$, the argmax of Chamber 7 wearing the hat of Chamber 1. Flip the sign and average, and you have the most common loss in deep learning, the cross-entropy or negative log-likelihood: $\mathcal{L}(\theta) = -\frac{1}{n}\sum_i \log p_\theta(y_i \mid x_i)$.

Finally, papers often need to say how different two distributions are. The Kullback–Leibler (KL) divergence is

read “the KL divergence of p from q”. You don't need to compute with it yet, only to read it. Three facts are enough: it's never negative, it's zero exactly when $p = q$, and it is not symmetric. For a fair coin $p = (\tfrac12, \tfrac12)$ and a biased one $q = (\tfrac34, \tfrac14)$, $D_{\mathrm{KL}}(p \,\Vert\, q) \approx 0.144$ but $D_{\mathrm{KL}}(q \,\Vert\, p) \approx 0.131$. The double bar is only a separator between the two arguments. It has nothing to do with the norm $\Vert\mathbf{x}\Vert$ of Chamber 6.

Read beyond the course

Probability rewards seeing it from several angles: pictures, careful definitions, and the way machine-learning books use it. These are all free.

Papers and lectures

You met the dropout paper at the top of this chamber. It's long, but the part you need is short. Open it at Section 4, Model Description: one page, with Figure 3 drawing a standard layer next to a dropout layer. Read the equations aloud with this chamber's tables, then read the paragraph beneath them. If you want more, Section 10 compares Bernoulli masks with Gaussian ones and states their mean and variance, which is exactly what you'll prove below.

The GAN paper is a harder read, but its heart is also one page. Read Section 3, Adversarial nets, which ends in Equation 1. Then look at Proposition 1 at the start of Section 4.1, which states the best possible discriminator in one fraction. Skip the convergence proof and the experiments for now.

Watch

Grant Sanderson derives Bayes' rule from a picture of all the possibilities, drawn as areas. Watch for the idea that evidence restricts the space of possibilities, and that the answer is a proportion of what's left: the same recipe as the definition of $P(A \mid B)$ above.

Your turn

Translate between symbols, words and code. Then prove two facts about expectations and dropout masks, and finish with three problems, the last taken straight from the GAN paper.