Pruning and sparsity I

AOverview

A trained network carries far more weights than it needs, and every one of those weights has to be fetched from memory before it can be multiplied. This lecture is about deleting the ones that do not matter. It opens with a single number, 640 pJ for a DRAM access against 3.1 pJ for a multiply, and by the end it has turned that number into a discipline: a formulation, a spectrum of shapes to cut, and a family of criteria that say which weight, row or channel goes first.

As a PhD student you need it in three places. Exams hand you a small weight matrix and ask for element-wise and row-wise importances, the pruned result and the sparsity, or ask you to derive the Optimal Brain Damage saliency and name the assumption that removes each Taylor term. Your research project puts a detector on an embedded board, and the first compression step in that pipeline is almost always pruning, so its evaluation section has to say what granularity you chose, which criterion ranked the channels and why the board got faster. And any efficient system you build or review is judged by the lesson this lecture hammers home: a matrix that is 90% zeros is only faster when the zeros sit in a shape the hardware can skip.

The path has five stops. You start with the energy argument and the formulation of pruning as minimizing the loss under an L0 budget, with the brain's own overprovision-then-prune curve as motivation. You watch Han et al. prove that train, prune and retrain removes 9x of AlexNet with no accuracy loss, and learn why the retraining step is the one that matters. You open a convolution weight along its four dimensions and order the five granularities from irregular to regular, then meet the three that ship: fine-grained pruning with EIE-style hardware, the NVIDIA 2:4 pattern, and channel pruning with per-layer ratios found by AMC. Finally you learn to rank what gets removed, first by magnitude and batch norm scaling factors, then by curvature, activations and layer reconstruction.

Numbers you will own by the end

These are the anchors the parts derive and the exam and reference sheet return to. By the last part you will have computed or justified every one of them rather than quoted it.

Success looks like

• Argue from the 45 nm energy table why fewer weights means less energy, and write the pruning formulation with every symbol named and the reason the L0 constraint forces heuristic criteria.
• Read accuracy loss and reduction factor off the pruning-ratio chart for one-shot, retrained and iterative pruning, and explain from layer tables why parameters shrink 9x while MACs shrink only 3x.
• Read a convolution weight as [c_o, c_i, k_h, k_w], order the five granularities from fine-grained to channel-level, and count the weights and the surviving shape after removing a kernel, an input channel or a filter.
• Define N:M sparsity, derive the 2:4 compressed layout and its memory saving, and say which granularity gives real speedup on commodity GPUs and why.
• Compute element-wise and row-wise importances with L1, L2 and general Lp norms, produce the pruned matrix for a target sparsity, and explain why batch norm gamma is a free channel score.
• Derive 1/2 h_ii w_i^2 from the Taylor expansion, name the assumption that removes each term, and show a case where magnitude and Optimal Brain Damage rank two weights differently.
• Compute APoZ for a channel from its activation maps, state the regression-based channel pruning objective with its L0 constraint, and say what data each criterion needs before you can run it.

How to study this lecture

1. Read the parts in order. The energy argument of part one justifies part two, the granularity ladder of part three is what part four tests against hardware, and parts five and six answer the question parts three and four leave open: which unit to remove.
2. Keep a pencil next to every small matrix. Each worked example hides one computation behind a question, so compute the norms, the sparsity and the pruned result yourself before you reveal them.
3. Answer every recall prompt in your head before opening it. The numbers and derivations that stick are the ones you retrieved, not the ones you read.
4. Take each quiz and read the explanation even when you are right. The wrong options are the exam traps.
5. Mark a concept understood only when you could redo its formula and its headline number from a blank page. Unmarked concepts show you where to return.
6. Keep the glossary open for terms and the reference sheet for the energy table, the granularity ladder, the norm formulas and the criteria comparison when you solve problems.
7. Come back after a few days and prune a layer of your own project detector cold, choosing a granularity and a criterion and justifying both. Spaced practice on a new network is what turns a formula into a skill.

BThe 6 parts

1. 01Why prune: energy, definition and formulationMemory access dominates the energy bill of deep learning, so fewer weights means less data movement; pruning removes synapses and neurons and is posed as minimizing loss under an L0 budget, echoing synaptic pruning in the human brain.5 conceptsSlides 1-630 min
   1. 1.1Pruning is a pipeline of four decisions
   2. 1.2Memory traffic, not arithmetic, sets the energy bill
   3. 1.3What pruning removes: synapses, neurons, or both
   4. 1.4Pruning as an optimization problem with an L0 budget
   5. 1.5The brain overprovisions and then prunes
2. 02Train, prune, fine-tune: what pruning achievesThe Han et al. pipeline of training connectivity, pruning and retraining, how iterative pruning pushes the pruning ratio past 90 percent without accuracy loss, the resulting parameter and MAC reductions, and hardware support for sparsity.6 conceptsSlides 7-1336 min
   1. 2.1Train first, then cut the small weights: what one-shot pruning costs
   2. 2.2Fine-tuning gives the loss back and reshapes the weights
   3. 2.3Iterate: prune a little, retrain, repeat
   4. 2.4Reading the reduction table: parameters shrink 9x, compute only 3x
   5. 2.5Pruning is not only for CNNs: the NeuralTalk LSTM at 10 percent density
   6. 2.6A pruned matrix is only faster when hardware skips the zeros
3. 03Pruning granularity: from irregular to regularFine-grained versus coarse-grained pruning on a 2D weight matrix, the four dimensions of a convolution weight tensor, and the five commonly used granularities from fine-grained to channel-level.3 conceptsSlides 14-1818 min
   1. 3.1Granularity: the shape of what you remove sets flexibility against speed
   2. 3.2Four dimensions of a convolution weight, and how to count them
   3. 3.3Five granularities on one tensor, from irregular to regular
4. 04Fine-grained, N:M and channel pruning in practiceTrade-offs of each granularity with real numbers: fine-grained compression ratios, NVIDIA 2:4 pattern sparsity with its compressed format and accuracy table, and channel pruning with non-uniform per-layer sparsity versus uniform shrinking.5 conceptsSlides 19-2530 min
   1. 4.1Fine-grained pruning: maximum flexibility, minimum hardware friendliness
   2. 4.2N:M sparsity: a pattern that hardware can count on
   3. 4.3Does 2:4 cost accuracy? The evidence across seven tasks
   4. 4.4Channel pruning: direct speedup, smaller compression
   5. 4.5AMC: the proof that per-layer ratios beat one global ratio
5. 05Pruning criteria: magnitude and scaling factorsWhat makes a parameter less important, magnitude-based importance at element and row level with L1, L2 and general Lp norms, and scaling-based filter pruning that reuses batch normalization gamma factors.4 conceptsSlides 26-3324 min
   1. 5.1Which parameter to remove: the less important, the better
   2. 5.2Element-wise magnitude: importance is the absolute value
   3. 5.3Scoring a whole row: L1, L2 and the general Lp norm of a structural set
   4. 5.4Scaling factors: let training say which channel to drop, using batch norm gamma
6. 06Second-order, activation and regression criteriaOptimal Brain Damage's Taylor-expansion importance 1/2 h_ii w_i^2, neuron pruning as coarse-grained weight pruning, APoZ activation-sparsity scoring, and regression-based channel pruning that minimizes layer output reconstruction error.6 conceptsSlides 34-4336 min
   1. 6.1Pruning is a perturbation, and Taylor tells you what it costs
   2. 6.2Optimal Brain Damage: three assumptions leave one half h w squared
   3. 6.3Removing a neuron is removing a whole row of weights
   4. 6.4Average Percentage of Zeros: let the data vote on each channel
   5. 6.5Regression-based pruning: reproduce the layer's output, not the loss
   6. 6.6Where the criteria come from, and what to read next

CGlossary and reference

• GlossaryEvery term from the lecture, defined once, with links back to the slides that use it.
• Reference sheetThe lecture on one printable page, for revision before a quiz or exam.