Σ and Π: Loops Written in Maths

Discover: two loops in a famous algorithm

In 2015 Sergey Ioffe and Christian Szegedy at Google introduced batch normalisation, a layer that rescales the numbers flowing through a network so that, over each mini-batch, they have mean 0 and variance 1. On an image classifier it reached the same accuracy in 14 times fewer training steps, and ResNet (Chamber 4) puts one after every convolution. The whole method is four lines:

You can already read much of this. The arrows are assignments and the hat marks a modified value (Chamber 1). $\mathcal{B}$ is a set, the mini-batch (Chamber 2). $\mathrm{BN}_{\gamma,\beta}$ is a function with its parameters in the subscript (Chamber 4). What's new is the tall Greek letter in the first two lines: $\sum$, capital sigma. Each one is a loop. The first adds up the $m$ values in the batch, and the second adds up their squared distances from the mean.

This chamber teaches you to read, write and manipulate those loops. You'll see why the $\frac{1}{m}$ sits outside, prove the fact the paper uses to check its own work, and run the algorithm by hand. Start with the first line.

Learn: the anatomy of a sum

Every sum has four parts:

Read it as “the sum from $i$ equals 1 to $n$ of $x$ sub $i$”. Below the $\Sigma$ sit the index $i$ and its lower bound; above it, the upper bound; after it, the term, which usually depends on the index. The index takes every integer value from the lower bound to the upper bound, both included, and the terms are added. For example,

A sum from $a$ to $b$ has $b - a + 1$ terms, not $b - a$. That “+ 1” is the fencepost problem: a fence 10 metres long with a post every metre needs 11 posts. In Python it shows up as the + 1 inside range, which stops just before its second argument:

total = 0                   # an empty sum is 0
for i in range(1, n + 1):   # i = 1, 2, ..., n
    total += i**2           # the term

or in one line, sum(i**2 for i in range(1, n + 1)). Three more habits of the notation:

• The index is a dummy variable. $\sum_{i=1}^{n} x_i$ and $\sum_{k=1}^{n} x_k$ are the same sum, just as renaming a loop variable doesn't change a loop. The index means nothing outside its sum, so write $\sum_{i}(x_i + i)$ with brackets, never $\sum_i x_i + i$.
• An empty sum is 0. If the upper bound is below the lower bound, there are no terms, and the total never leaves its starting value: $\sum_{i=1}^{0} x_i = 0$.
• Bounds are often left out. $\sum_i x_i$ means “over every $i$ that makes sense here”, usually all the data.

Now sculpt some sums yourself. Pick a term, set the bounds, and watch the notation, the expansion and the Python change together. Each of the three targets can be reached in more than one way, and product mode is there to explore when you reach products later in this chamber.

sum(i for i in range(1, 5 + 1))

Learn: the algebra of sums

Sums obey three rules, and each one is ordinary arithmetic applied to a long line of additions.

1. A constant term: $\sum_{i=1}^{n} c = nc$. Adding $c$ to itself $n$ times gives $nc$.
2. A constant factor comes out: $\sum_{i=1}^{n} c\,x_i = c\sum_{i=1}^{n} x_i$. Every term has the factor $c$, so factor it out once: $c x_1 + \cdots + c x_n = c(x_1 + \cdots + x_n)$. That's why batch normalisation writes $\frac{1}{m}\sum_{i=1}^{m} x_i$ rather than $\sum_{i=1}^{m} \frac{x_i}{m}$: they're equal, and the first divides once instead of $m$ times.
3. A sum of terms splits: $\sum_{i=1}^{n} (x_i + y_i) = \sum_{i=1}^{n} x_i + \sum_{i=1}^{n} y_i$. Addition can be reordered, so gather all the $x$'s, then all the $y$'s.

Together they say that sums are linear:

Two more moves change the bounds rather than the terms. You can split the range, $\sum_{i=1}^{n} x_i = \sum_{i=1}^{k} x_i + \sum_{i=k+1}^{n} x_i$, which lets you compute $\sum_{i=11}^{20} i$ as $\sum_{i=1}^{20} i - \sum_{i=1}^{10} i = 210 - 55 = 155$. And you can shift the index. Substituting $j = i - 1$ gives

The bounds go down by one and the subscript goes up by one, so the terms are the same. This is exactly the translation between a paper that counts from 1 and Python, which counts from 0: the paper's $x_{j+1}$ is x[j].

A proof: deviations from the mean add up to zero

Here is the rulebook in action, on the first fact the batch normalisation paper uses to check its own algorithm.

Claim. Let $\bar{x} = \frac{1}{n}\sum_{i=1}^{n} x_i$ be the mean of $x_1, \ldots, x_n$. Then $\sum_{i=1}^{n} (x_i - \bar{x}) = 0$.

Proof. The key observation is that $\bar{x}$ has no $i$ in it: inside the sum it is a constant. Split the sum (rule 3), then use the constant rule (rule 1):

By the definition of the mean, $n\bar{x} = n \cdot \frac{1}{n}\sum_{i=1}^{n} x_i = \sum_{i=1}^{n} x_i$. So the two terms cancel, and the sum is 0. $\blacksquare$

Every step names its rule, and the only idea was to notice what doesn't depend on the index. In batch normalisation the normalised values are $\widehat{x}_i = (x_i - \mu_{\mathcal{B}}) / \sqrt{\sigma^2_{\mathcal{B}} + \epsilon}$: deviations from the mean, divided by a constant. Pull the constant out and this proof shows $\sum_{i=1}^{m} \widehat{x}_i = 0$, exactly as the paper says.

Learn: Gauss's formula, two ways

What is $1 + 2 + 3 + \cdots + n$? Here are two routes to the answer. The first finds the formula; the second proves one you already have.

The derivation: pair the terms

Write the sum $S$ forwards, then backwards, and add the two lines column by column:

Every column adds up to $n + 1$, and there are $n$ columns, so $2S = n(n+1)$:

The same trick works in $\Sigma$ notation. As $i$ runs from 1 to $n$, the number $n + 1 - i$ runs through the same values backwards, so $S = \sum_{i=1}^{n} (n + 1 - i)$ as well. Add the two expressions for $S$ and use linearity: $2S = \sum_{i=1}^{n} \big(i + (n + 1 - i)\big) = \sum_{i=1}^{n} (n+1) = n(n+1)$, by the constant rule.

The proof: induction

Pairing is clever, but it doesn't generalise easily. A more mechanical technique proves statements about every positive integer $n$, and it fits sums perfectly. It's called proof by induction, and it joins the techniques of Chamber 3. You prove two things:

1. Base case: the statement is true for $n = 1$.
2. Inductive step: if it is true for some $n = k$, then it is true for $n = k + 1$.

Then it's true for every $n$: true for 1, so for 2, so for 3, and so on, like a line of dominoes where the first falls and each knocks over the next.

Claim. For every integer $n \ge 1$, $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Proof. Base case. For $n = 1$ the sum has one term, 1, and $\frac{1 \cdot 2}{2} = 1$. They agree.

Inductive step. Suppose that for some $k \ge 1$ we have $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$. This is the inductive hypothesis. Split the last term off the sum for $k + 1$, then use the hypothesis:

That is the formula with $n = k + 1$. The statement holds for $n = 1$, and whenever it holds for $k$ it holds for $k + 1$, so by induction it holds for every $n \ge 1$. $\blacksquare$

Notice where the sum notation did the work: splitting off the last term is what connects case $k + 1$ to case $k$. The same pattern proves many sum formulas, such as $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ (so $\sum_{i=1}^{10} i^2 = 385$, one of the lab's targets) and $\sum_{i=1}^{n} (2i - 1) = n^2$, which you'll assemble yourself at the end of the chamber.

Learn: the geometric series

In a geometric series each term is the previous one multiplied by a fixed ratio $r$:

The derivation: multiply and subtract

Call the sum $S$ and multiply it by $r$. Every power moves up by one:

Subtract the second line from the first. Everything in the middle cancels, leaving $S - rS = 1 - r^n$. Factor out $S$ to get $S(1 - r) = 1 - r^n$, and divide by $1 - r$, which is allowed because $r \ne 1$. In $\Sigma$ notation, the multiplication is an index shift: $rS = \sum_{i=0}^{n-1} r^{i+1} = \sum_{i=1}^{n} r^{i}$, and the two sums share every term except $r^0$ and $r^n$.

With $r = 2$ and $n = 10$ you get $\frac{1 - 2^{10}}{1 - 2} = 1023$: every bit of a 10-bit number switched on. When $|r| < 1$, the power $r^n$ shrinks to 0 as $n$ grows, and the infinite series settles at $\sum_{i=0}^{\infty} r^i = \frac{1}{1 - r}$. (What “settles” means precisely is the limit of Chamber 7.)

Geometric series turn up all over machine learning:

• In reinforcement learning, a reward $r_t$ received $t$ steps in the future is discounted by $\gamma^t$, and the return is $\sum_{t=0}^{\infty} \gamma^t r_t$. With a reward of 1 at every step and $\gamma = 0.99$, the return is $\frac{1}{1 - 0.99} = 100$, so $\gamma$ sets how far ahead the agent effectively looks.
• Adam's running average (Chamber 1) gives the gradient from $k$ steps ago a weight of $(1 - \beta)\beta^{k}$. Over $t$ steps these weights add up to $(1 - \beta)(1 + \beta + \cdots + \beta^{t-1}) = 1 - \beta^t$: exactly the denominator in Adam's bias correction $\hat{m}_t = m_t / (1 - \beta^t)$. Chamber 9 takes this further.

Learn: sums over sets, with conditions, and sums of sums

The index doesn't have to run over a range of integers. It can run over a set: $\sum_{i \in \mathcal{B}} \ell_i$ adds $\ell_i$ for every $i$ in the mini-batch $\mathcal{B}$, and the mean loss over the batch is $\frac{1}{|\mathcal{B}|}\sum_{i \in \mathcal{B}} \ell_i$, with $|\mathcal{B}|$ the batch size from Chamber 2. It can also carry conditions. $\sum_{j \ne i} x_j$ adds every $x_j$ except $x_i$, and $\sum_{i \,:\, y_i = 1} x_i$ adds only the examples whose label is 1. In code, a condition under the $\Sigma$ becomes an if inside the loop.

Here is a famous example, from the paper that introduced word2vec's skip-gram model:

Read it from the outside in. The text is a sequence of words $w_1, \ldots, w_T$. The outer sum visits every position $t$. The inner sum visits the offsets $j$ from $-c$ to $c$, the window around the word, and the condition $j \ne 0$ skips the word itself. Each term is the log probability the model gives to seeing the neighbour $w_{t+j}$ near the centre word $w_t$, and the $\frac{1}{T}$ turns the total into an average. Training makes this number as large as possible.

That was a double sum: a sum whose term is itself a sum. It's two nested loops. Over a grid of numbers $a_{ij}$ with $m$ rows and $n$ columns,

The left side adds row by row and the right side column by column. Both add every entry once, so for finite sums you may swap the order freely. When the term splits into a part for $i$ and a part for $j$, the double sum factorises: $\sum_{i}\sum_{j} x_i\,y_j = \left(\sum_i x_i\right)\left(\sum_j y_j\right)$.

When the inner bounds depend on the outer index, swapping takes care. $\sum_{i=1}^{n}\sum_{j=1}^{i} a_{ij}$ adds the lower triangle of the grid, the pairs with $1 \le j \le i \le n$. To add the same triangle column by column, fix $j$ first; then $i$ runs from $j$ to $n$:

Draw the triangle and both sides are obvious. You'll meet this shape again in language models, where a causal attention mask lets position $i$ look only at positions $j \le i$.

Learn: products, factorials and logs

Capital pi does for multiplication what capital sigma does for addition:

read “the product from $i$ equals 1 to $n$ of $x$ sub $i$”. An empty product is 1, for the same reason an empty sum is 0: a running product starts at 1, and multiplying by nothing leaves it there. The most famous product is the factorial, $n! = \prod_{k=1}^{n} k$, the number of ways to put $n$ things in order: $5! = 120$. By the empty-product rule, $0! = 1$.

Products matter in ML because probabilities multiply. If a model gives probability $p_i$ to each of $n$ independent observations, the probability of all of them together, the likelihood, is $\prod_{i=1}^{n} p_i$. That is a problem for a computer. With $p_i = 0.5$ and $n = 1100$, the product is $0.5^{1100} \approx 10^{-331}$, smaller than the smallest positive number a standard float can hold, so Python returns exactly 0.0.

Chamber 4's product rule for logs fixes it. Apply $\log(ab) = \log a + \log b$ over and over, one factor at a time:

The log-likelihood of those 1100 observations is $1100 \log 0.5 \approx -762.5$, a perfectly ordinary number. And because $\log$ is strictly increasing, whatever parameters make the log-likelihood largest also make the likelihood largest. That's why papers maximise sums of logs, and why a loss function is so often a $\sum$ of $\log$s.

Learn: mean and variance are sums

Two of the most common expressions in all of statistics are sums you can now read. The mean is the average, and the variance is the average squared distance from the mean:

Read them as “mu” and “sigma squared”. The standard deviation $\sigma = \sqrt{\sigma^2}$ measures spread in the same units as the data. Batch normalisation's first two lines are exactly these, computed over one mini-batch and labelled with a subscript $\mathcal{B}$.

Take the batch $2, 4, 9$ from the quiz. The mean is 5, the deviations are $-3, -1, 4$ (which add up to 0, as proved above), their squares are $9, 1, 16$, and the variance is $\frac{26}{3} \approx 8.67$. The third line of Algorithm 1 divides each deviation by $\sqrt{\sigma^2 + \epsilon} \approx 2.94$, so the normalised values have mean 0 and a spread of about 1, whatever the scale of the numbers you started with.

Two practical notes. First, there's another way to compute the variance, as the mean of the squares minus the square of the mean: $\sigma^2 = \frac{1}{n}\sum_i x_i^2 - \mu^2$. You'll prove it in Your turn. Second, statisticians often divide by $n - 1$ instead of $n$ when estimating the variance of a whole population from a sample (Bessel's correction). Algorithm 1 divides by $m$. The paper switches to $\frac{m}{m-1}$ only for the statistics it keeps for use after training. Tools differ too: NumPy's np.var divides by $n$ by default, while Python's statistics.variance divides by $n - 1$. When you implement a formula, check which one it means.

Read beyond the course

Papers and lectures

The batch normalisation paper is a good one to open now. Read Section 3 up to Algorithm 1 on page 3, and the paragraph just after it. The paragraph before the algorithm sets up the notation ($\mathcal{B}$, $m$ and $\mathrm{BN}_{\gamma,\beta}$), and the one after explains why the normalised values have mean 0 and variance 1, using the sums $\sum_{i=1}^{m} \widehat{x}_i = 0$ and $\frac{1}{m}\sum_{i=1}^{m} \widehat{x}_i^2 = 1$. Then flip back to the introduction, where the training objective appears as a sum over the whole training set, $\frac{1}{N}\sum_{i=1}^{N} \ell(\mathrm{x}_i, \Theta)$. Skip the derivatives that close Section 3, and the experiments, for now.

For word2vec, read Section 2 up to Eq. (2). Eq. (1) is the double sum you've just met, and Eq. (2) is a softmax, whose denominator is a sum over the entire vocabulary. The paper's point is that this sum is too expensive when the vocabulary has millions of words, and much of the rest of the paper is about ways around it.

Watch

A short introduction to reading and expanding a $\Sigma$. Watch it if the anatomy of a sum still feels shaky, and pause before each expansion to do it yourself.

Andrew Ng writes out batch normalisation's equations step by step. Watch for the same sums in slightly different clothes: he writes the $i$-th example as $z^{(i)}$, with the bracketed superscript of Chamber 1, and calls the result $\tilde{z}^{(i)}$.

Your turn

Expand, translate, prove and code. The two proofs use this chamber's big ideas, induction and linearity, and the coding problems end with two real algorithms run by hand.

Proofs

Put the induction proof in order, then prove the variance shortcut yourself with the algebra of sums.

Code it up

Every $\Sigma$ becomes a loop and every condition an if. Read each statement's bounds carefully: they're where most bugs hide.