top of page

NN Pruning

Writer: NOURA ALSHAREEF
NOURA ALSHAREEF
Oct 13
8 min read

A simple guide to removing the weights a neural network does not need


In the last post we used the roofline to find what slows a network down. One of the fixes was a single line: pruning means removing weights that don't matter. Fewer weights, fewer MACs.


This post explains that line. It answers two questions:

  • What is pruning?

  • How do we write pruning as a math problem?


Why remove weights at all?

Every weight costs us twice. It takes bytes in memory, and it takes one MAC every time it is used.

Memory is the expensive side. This table shows the energy of one 32-bit operation on a 45 nm chip:

Operation

Energy (pJ)

Integer add

0.1

Float add

0.9

Integer multiply

3.1

Float multiply

3.7

Read from cache (SRAM)

5

Read from memory (DRAM)

640

One read from memory costs 640 pJ. One multiply costs 3.1 pJ.

640 ÷ 3.1 ≈ 200

So reading one number from memory costs about as much energy as 200 multiplies. A weight we don't need is not free. If it is redundant, we should remove it.

كل وزن في الشبكة له عدة تكاليف: مساحة في الذاكرة، وعملية حسابية (MAC) في كل مرة نستخدمه، وقراءة الرقم من الذاكرة. القراءة تستهلك طاقة أكثر من عملية الضرب بنحو 200 مرة، لذلك الوزن الذي لا نحتاجه نحذفه.

2. What is pruning?

Pruning means removing connections that are not needed. Before we do it to a network, look at where the idea comes from.


In the human world

Your brain did it first.

Synapses are the connections between brain cells. A newborn has about 2,500 per neuron. By age 2 to 4 that grows to about 15,000, then it falls to about 7,000 in an adult.

So about half of the connections are removed, and that is a good thing. The brain keeps the connections it uses and lets go of the rest, through the years when we learn the most. Pruning is part of learning, not damage.

الوصلات بين خلايا الدماغ (synapses) ترتفع من نحو 2,500 لكل خلية عند الولادة إلى نحو 15,000 في عمر 2 إلى 4 سنوات، ثم تنخفض إلى نحو 7,000 عند البالغين. وحذف نصف الوصلات تقريبًا شيء جيد: الدماغ يُبقي ما يستخدمه ويتخلّص من الباقي، فالحذف جزء من التعلّم.

In a neural network

Now do the same thing to a network.

Pruning turns a dense network into a sparse one.

  • Dense: every neuron is connected to every neuron in the layer before it. Every cell of the weight matrix holds a number.

  • Sparse: many of those numbers are zero. Those connections are gone.


Two words come from the brain:

  • A synapse is one connection. In a network, that is one weight.

  • A neuron is one node. In a fully connected layer, that is one row of the weight matrix.

So there are two things we can prune.


Prune synapses. Set single weights to zero. The matrix keeps its shape, but now it has holes.

Prune neurons. Remove a whole neuron, with every connection going into it and out of it. One whole row leaves the weight matrix.


في الشبكة الكثيفة (Dense) كل خلية عصبية متصلة بجميع خلايا الطبقة التي تسبقها، ولكل اتصال وزن مسجّل في مصفوفة الأوزان (Weight Matrix) التشذيب (Pruning) يحوّلها إلى شبكة قليلة الاتصالات (Sparse Network)، بتصفير كثير من الأوزان وإزالة الاتصالات المرتبطة بها. ·  المشبك العصبي (Synapse) هو اتصال واحد بين خليتين، يمثّله وزن واحد. ·  الخلية العصبية (Neuron) يمثّلها صف في مصفوفة أوزان الطبقة كاملة الاتصال (Fully Connected Layer). ·  تشذيب الاتصالات Synapse pruning  تصفير أوزان منفردة مع بقاء أبعاد المصفوفة كما هي. ·  تشذيب الخلايا Neuron pruning حذف خلية وجميع اتصالاتها الداخلة والخارجة، فتُحذف أوزانها من مصفوفات الطبقات المعنية.

Example: a layer with 3 neurons and 4 inputs has 3 × 4 = 12 weights.


Look at the difference between the two:

  • Pruning synapses removed 7 of 12 weights, but the matrix is still 3 × 4 with zeros inside.

  • Pruning a neuron removed only 4 of 12 weights, but the result is a normal, smaller 2 × 4 matrix.

This difference matters a lot for speed. It is the topic of the next post.

الـ pruning يحوّل الشبكة من dense إلى sparse: إما نحذف وصلات منفردة (synapses) فتصير أصفارًا داخل المصفوفة، أو نحذف neuron كاملًا مع كل وصلاته فيختفي صف كامل من مصفوفة الأوزان.

3. Does pruning hurt accuracy?

Yes, if we only prune. No, if we prune and then train again.

The experiment below is AlexNet on ImageNet. The question is: how many weights can we remove before accuracy drops?

Method

Weights removed

Accuracy loss

Prune only

About 50%

Almost none

Prune only

About 80%

About 4%

Prune, then fine-tune

About 80%

No loss

Prune and fine-tune repeatedly

About 90%

No loss

Prune only. We remove the weights and stop. The more we remove, the lower the accuracy.

Train first, then prune. With pruning alone, AlexNet loses almost nothing at 50%, but about 4% of accuracy at 80%. The two small plots show the weights before and after pruning: the ones closest to zero are cut out.

Prune, then fine-tune. Fine-tuning means training the surviving weights a little more. They adjust to cover for the ones we removed, and the accuracy comes back.


Iterative pruning. Don't remove everything at once. Remove a little, fine-tune, remove a little more, fine-tune again. Step by step we reach 90%.


عند التشذيب فقط: نحذف الأوزان الأقل أهمية دون إعادة تدريب، وقد تنخفض الدقة كلما زاد الحذف.

عند التشذيب ثم إعادة التدريب (fine-tune): ندرّب الأوزان المتبقية لتعويض المحذوفة واستعادة الدقة.

التشذيب ثم fine-tune تدريجيًا : نكرّر الحذف وإعادة التدريب على مراحل، لحذف أوزان أكثر مع الحفاظ على الدقة.


It works on other networks too

Network

Parameters before

Parameters after

Fewer parameters

Fewer MACs

AlexNet

61 M

6.7 M

9×

3×

VGG-16

138 M

10.3 M

13×

5×

GoogleNet

7 M

2.0 M

3.5×

5×

ResNet50

26 M

7.47 M

3.4×

6.3×


Two things to notice:

  • Before pruning, the sizes are very different: 7 M to 138 M. After pruning, they are all between 2 M and about 10 M. Similar tasks seem to need a similar amount of capacity.

  • Parameters and MACs do not shrink by the same amount. AlexNet has 9× fewer parameters but only 3× fewer MACs. Most of its parameters sit in the fully connected layers, where about 90% can go. Most of its MACs sit in the convolution layers, where only about half can go.


But there is a limit

Even with iterative pruning and fine-tuning, AlexNet keeps its accuracy only up to about 90%. At 95% only 5% of the weights are left, and the model starts to sound drunk. We cannot prune everything.

الحذف وحده يُنقص الدقة. لكن إذا أعدنا تدريب الأوزان الباقية بعد الحذف (fine-tuning)، وكرّرنا ذلك خطوة خطوة، نستطيع حذف نحو 90% من أوزان AlexNet بدون خسارة في الدقة. ولكل شبكة حدّ: عند 95% يبدأ النموذج بالتخبّط.

4. How do we formulate pruning?


The simplest pruning is not training at all. We take a model that is already trained and delete the weights closest to zero. That is just deletion.

But which weights, and how many? To answer that exactly, we can also write pruning as a math problem.

Recall how training is written. We look for the weights W that give the smallest loss:

L: the loss function; x: the input; W: the original set of weights for the entire model; arg⁡_min⁡: find the weights that minimize the loss.


Pruning keeps the same loss and adds one rule: only N weights may be non-zero.


N: the target; the most non-zero weights we allow


In plain words: find the weights with the lowest loss, but keep at most N of them non-zero.

The formula describes the goal, not the steps. Deleting the smallest weights is the quick way to get close to it. Fine-tuning the weights that are left gets closer.

The formula has two parts that pull against each other:

  • The goal (min L) wants the network to stay accurate.

  • The limit (≤ N) wants the network to stay small.

Remove the limit and we are back to normal training. Remove the goal and the answer is easy but useless: set every weight to zero.


What is ‖W‖₀?

It just counts the non-zeros. For W = [3, 0, 0, −5], two numbers are not zero, so ‖W‖₀ = 2.

Why does a smaller N help?

We only need to store the non-zero weights. A smaller N means fewer bytes in memory.


أبسط طريقة للـ pruning هي الحذف المباشر: نأخذ موديل مدرَّب ونحذف الأوزان القريبة من الصفر، بدون أي تدريب. ونقدر نكتبها كمعادلة: نبحث عن الأوزان اللي تعطي أقل loss، بشرط ألّا يزيد عدد الأوزان غير الصفرية عن N.المعادلة فيها طرفين متعاكسين: الهدف (أقل loss) يحافظ على الدقة، والشرط (N) يحافظ على صغر الحجم. وكل ما صغرت N قلّت الأوزان اللي نخزّنها، فتقلّ الذاكرة المطلوبة.

A tiny example

Take one neuron with three weights. Its weights are one row of a layer’s weight matrix:

y = ReLU(10·x₀ − 8·x₁ + 0.1·x₂)

So W = [10, −8, 0.1] and ‖W‖₀ = 3. Our budget is N = 2, so one weight must go. Which one?

current Relu for [10, −8, 0.1] is 10+(-8)+0.1=2.1

Weight we remove

W_P

New output

Change

10

[0, −8, 0.1]

ReLU(−7.9) = 0

2.1

−8

[10, 0, 0.1]

ReLU(10.1) = 10.1

8.0

0.1

[10, −8, 0]

ReLU(2) = 2.0

0.1

Removing 0.1 changes the output the least. So W_P = [10, −8, 0], and ‖W_P‖₀ = 2 ≤ N. The limit is met, and the loss barely moves.

This is the whole idea of the formula in three weights: among all the ways to meet the limit, pick the one that hurts the least.


From N to sparsity

People usually don't say N. They say sparsity: the share of weights that are zero.

sparsity = 1 − N ÷ (total weights)


For AlexNet from section 3:

  • Total weights: 61 M

  • N: 6.7 M

  • Sparsity = 1 − 6.7 ÷ 61 ≈ 89%


And in bytes, with 4 bytes per float32 weight as in the last post:

  • Before: 61,000,000 × 4 = 244 MB

  • After: 6,700,000 × 4 = 26.8 MB


The real saving is a little smaller, because we must also store where the non-zero weights are


5. Easy to write, hard to solve

The formula is one line, but nobody can solve it exactly. There are too many ways to choose which weights stay.


In the tiny example we tried all the options, because there were only 3. Now take a small layer with 1,000 weights and keep 200 of them. The number of ways to choose those 200 is about 10²¹⁶. The number of atoms in the observable universe is about 10⁸⁰. And AlexNet has 61 million weights.


So in practice we don't solve the formula. We answer four simpler questions, one at a time:

  1. Granularity. In what pattern do we prune? Single weights, whole rows, whole channels?

  2. Criterion. Which weights or neurons do we remove? For example, the ones closest to zero.

  3. Ratio. How much do we prune in each layer?

  4. Fine-tuning. How do we train the pruned network to get the accuracy back?

One warning before the next post


Last time I wrote "fewer weights, fewer MACs". That is true only if the zeros are really skipped.

A zero inside a normal dense matrix still takes 4 bytes, and the processor still multiplies by it. We save bytes and MACs only when the storage format and the hardware know how to skip the zeros.


This is why the pattern of the zeros matters so much. Some hardware is already built for it: the NVIDIA A100 GPU supports a pattern called 2:4 sparsity, with 2× peak performance and a measured 1.5× speedup on BERT.

That is question 1, granularity, and it is the next post.

المعادلة سهلة الكتابة وصعبة الحل، لأن عدد طرق اختيار الأوزان المحذوفة هائل. لذلك نجيب عمليًا عن أربعة أسئلة: بأي نمط نحذف؟ أيّ الأوزان نحذف؟ كم نحذف من كل layer؟ وكيف نستعيد الدقة؟ وتذكّر: الصفر لا يوفّر شيئًا إلا إذا عرف الـ hardware كيف يتخطّاه.

I hope this article gave you a clearer understanding of that trade-off and how to approach it in practice ♡♡


Sources

  • MIT 6.5940, TinyML and Efficient AI Computing, Lecture 3: Pruning and Sparsity (Part I), Song Han. efficientml.ai

  • Han et al., "Learning Both Weights and Connections for Efficient Neural Network", NeurIPS 2015. Accuracy experiment and the before/after figure.

  • Han, "Efficient Methods and Hardware for Deep Learning", Stanford University. Parameter table.

  • Horowitz, "Computing's Energy Problem (and What We Can Do About It)", IEEE ISSCC 2014. Energy table.

  • Drachman, "Do We Have Brain to Spare?", Neurology 2004, and Walsh, "Peter Huttenlocher (1931–2013)", Nature 2013. Synapse counts.

  • The count of 10²¹⁶ is my own calculation: the number of ways to choose 200 items out of 1,000.


Comments


White Structure

STAY IN THE KNOW

Thanks for submitting!

NoraTech

i@nshareef.com

©2023 by NoraTech 

bottom of page