Large-Scale Deep Learning

Many weak units working together

Deep learning rests on connectionism. One neuron, or one feature in an ordinary model, is not intelligent. A large population of them acting together can be. The book stresses that the number of units has to be large. Network sizes have grown exponentially over the past three decades, and the book compares today’s networks with the nervous systems of insects.

Picture a jury of people who each guess right only some of the time. The jury can still reach a reliable verdict by majority vote, if its members judge independently. The demo below is a toy of exactly that picture. It is not from the book.

The majority is right when more than half of the voters are right. For voters, each right with chance , the formula is below. It is a standard binomial sum. It is added here for this page and is not printed in the book. The curve in the demo is this formula evaluated for every odd .

The toy depends on one assumption: the voters are independent and equally good. Real neurons are neither, so the toy shows the principle and not the size of the effect in a network. The book makes the point in words, with a large population of neurons, and this toy gives it a number.

Fast CPU code and cache lines

Traditionally, networks were trained on the CPU of one machine. The book says careful code for a particular CPU can change the speed a great deal. In 2011 the best CPUs ran network workloads faster in fixed-point arithmetic than in floating point, and a tuned fixed-point version gained a threefold speedup over a strong floating-point system (Vanhoucke et al., 2011). The book also advises organizing data structures to avoid cache misses, and using vector instructions. It adds two cautions: many researchers neglect these details, yet when speed limits the size of a model, its accuracy suffers; and each CPU generation behaves differently, so floating point is sometimes faster too.

The cache is a small, fast memory. A memory read does not fetch one number. It fetches a cache line, a block of neighboring numbers, and keeps it. The next read is cheap if it lands in the same line, and a walk that jumps between lines pays for every jump. The number of numbers in one line is .

The matrix below is stored row by row, so the numbers of one row sit next to each other in memory. Read the walk as a list of memory addresses , numbered by the step . A load happens whenever the line of step differs from the line of the step before:

This rule is a toy, and it is added here. It keeps only the most recent line, so it counts a load each time the walk leaves a line. Real caches keep many lines, and the principle is the same.

Row by row, each line is loaded once and every number in it is used. Column by column, neighboring steps sit a full row apart in memory. When the matrix is at least one line wide (C at least L), every column step loads a new line, so the ratio of the two load counts equals the line length L. If C is smaller than L, one line holds numbers from several columns, and the ratio drops. The book’s advice to organize data for cache hits is this idea in practice.

GPUs, warps and memory segments

Graphics processors were built to draw scenes, which means doing the same simple arithmetic on huge numbers of vertices and pixels at once. The book explains that this suits neural networks too. They hold large buffers of parameters and activations, and they branch very little. Early work ran a two-layer network on a GPU and reported a threefold speedup (Steinkrau et al., 2005). GPU code is a specialist task, so most researchers build models from a library of fast operations, as the book describes for Theano, cuda-convnet, TensorFlow and Torch. The book also notes that most writable GPU memory is not cached. On a GPU it can therefore be faster to compute a value twice than to compute it once and read it back. NVIDIA’s CUDA language is what made general-purpose GPU code practical.

The unit that matters here is the warp, a small group of threads that run in lockstep. All threads in a warp execute the same instruction in each cycle. Two rules follow.

• Branches cost passes. If threads in one warp need different code paths, the paths run one after another. A warp that splits between two branches takes two passes.
• Coalesced reads are cheap. When the threads of a warp read neighboring numbers, the hardware can serve them in one memory transaction. Reads spread across memory need one transaction for each block they touch.

The toy warp has eight threads, two branches and blocks of eight numbers. Real GPUs use other sizes, and the book notes that the exact rules differ between models. The lesson carries over: a branch that splits a warp is paid for in passes, and scattered reads are paid for in transactions. This is one reason the book suggests writing models in terms of a library of operations, so that the fast code is written once by specialists.

Distributed updates and stale gradients

When one machine is not enough, the book describes two ways to split the work. Data parallelism gives each machine different examples. Model parallelism gives each machine a different part of one model. Inference is easy to split, because each input can go to its own machine. Training is harder. A bigger minibatch gives less than linear returns, and the standard gradient descent is a sequential chain: the gradient at step t depends on the parameters that step t − 1 produced.

The book’s answer is asynchronous stochastic gradient descent. Several workers share one parameter vector. Each worker reads the parameters without a lock, computes a gradient on what it read, and writes its update without a lock. Some updates overwrite each other, so each one helps a little less. Many more updates arrive per second, so training is faster overall. A parameter server can hold the shared parameters for many machines, as in Dean et al. (2012). The book says this remains the main strategy for training large deep networks in industry.

The toy below isolates the cost of a stale read. The loss is for a single parameter , so each gradient equals . Each of workers adds one update per time unit. In this toy, update computes its gradient at , which is updates older than the latest parameter . The gradient is stale by that many updates. The model is added here and is not printed in the book.

In words: the new parameter is the latest one, minus the step times the gradient evaluated at the older value . With this is ordinary gradient descent, because the gradient is taken at the latest value.

Compare the readout with your prediction. With eight workers the loss can grow where one worker would shrink, because each gradient is several updates old when it is applied. Lower the step size and the eight workers settle. The stale read costs progress per update, and the extra updates add progress per time unit. Which one wins depends on the step size. For this toy, the largest stable step is about 0.21 with eight workers and about 0.45 with four. These limits are added here and were checked numerically.

Compression: a small student from a large teacher

In many products the cost that matters is inference, the cost of running a model for each user, not the cost of training it. An ensemble of several models often generalizes best, but running every member is expensive. Sometimes one large model, such as one regularized with dropout, generalizes best as well. Model compression trains a smaller model to replace the large one. The large model is the teacher and the small one is the student. The book notes that compression applies when the large model is large mainly to prevent overfitting.

Here the teacher is a fixed function , and the student is a polynomial of degree . The student learns by copying the teacher at chosen inputs. The book’s advice concerns where those inputs come from. Once the teacher is known, you can create as many training inputs as you like, so they should look like the inputs the student will meet later. The book suggests corrupting training examples, or drawing points from a generative model trained on the original set. The student is fitted by least squares, written below. This formula is added here and is not printed in the book.

The teacher is , a wave. The test error is the mean squared gap between student and teacher on an even grid over [−2, 2]. The training inputs are spaced evenly over [−, ]. The toy uses evenly spaced inputs, not random samples, so that every number on this page can be reproduced. The shaded band in the plot is the training window.

Two details belong to this toy and are not general rules. The teacher is an odd function and the inputs are symmetric, so even degrees add nothing: degree 2 gives the same curve as degree 1, and degree 4 the same as degree 3. The book also mentions a second route. The student can copy other features of the teacher, such as its distribution over the wrong classes, not only the hard answers (Hinton et al., 2014, 2015). That route is not shown in the demo.

Dynamic structure: cascades and gaters

Dynamic structure means that the work done for an input depends on the input. A system can run only the models it needs. The book’s first example is the cascade, which suits rare objects. Most inputs contain nothing, so a cheap first stage can reject them, and only the few that pass reach an expensive second stage. The first stage should have high recall, so that it rarely rejects a real object. The last stage should have high precision. Viola and Jones (2001) built a face detector this way for handheld cameras, and the book describes a two-step cascade for reading street numbers. There the first model locates the number and the second reads it, which the book calls a sort of hard attention.

Here is the fraction of inputs that contain the object, is the fraction of real objects that pass stage 1, and is the fraction of empty inputs that pass it. The chance that an input is sent on to stage 2 is

Stage 1 costs per input and stage 2 costs . The average cost, as a fraction of running stage 2 on every input, is written , and it is the number the demo reports:

These two formulas are added here and are not printed in the book. In the demo, stage 2 is assumed to be correct on every input it receives. That toy assumption keeps the picture to one decision.

Decision trees are dynamic too, since each node decides which branch an input takes. The book also mentions a tree whose nodes each use a neural network to make the split (Guo and Gelfand, 1992).

The second idea is the gater. A small network chooses which of several experts computes the output. In the mixture of experts the gater gives each expert a weight through a softmax, and the output is the weighted sum. Every expert still runs, so this saves no work. The hard version picks one expert per input, and that can speed up training and inference. The book adds that the choice works well when the number of gating decisions is small, and that gating over many combinations needs other tools, such as policy gradients.

With these experts, the gate gives expert 1 the weight at input , and expert 2 the rest. The output is , the curve the demo draws. Hard routing sends the input to one expert, so the output is the sign of , with ties going to expert 1.

The gate formula is added here. It is the softmax that the book names for the gater. The book also notes that a hard switch has not yet proven effective at large scale, and that modern attention uses a weighted average. Dynamic structure is harder to parallelize. Different inputs take different branches, so a minibatch no longer shares one matrix multiplication, and load can become uneven across machines that each handle one stage of a cascade.

Specialized hardware and low precision

Designers have tried to build special chips for neural networks for decades. The designs range from digital circuits to analog ones that hold values as voltages or currents, and from custom chips to reprogrammable FPGAs. The reason to keep going is that a single core is no longer getting much faster, so the gains now come from more parallel cores. Specialized hardware can also serve phones and other low-power devices.

Precision is the main lever. A standard number takes 32 or 64 bits. The book says recent work suggests that between 8 and 16 bits can suffice to use or train a network with backpropagation, and that more precision is needed during training than at inference. A fixed-point format stores numbers in one fixed range. A dynamic fixed-point format shares one range among a set of numbers, such as all the weights of one layer. Fewer bits mean less hardware area, less power and less computing time.

A format with bits stores numbers in the range on a grid with spacing . Each weight is stored at the nearest grid point inside the range. The rule is added here and is not printed in the book:

Two facts follow. The largest error is set by the spacing, and each extra bit halves the spacing. Also, the largest value that fits sits one step below the top of the range, so a weight close to the top can lose a whole step. With , a layer whose weights are all small spends most of its bits on range it never uses. A shared range that matches the layer removes that waste.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 12.1 (pages 443–451), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.