Lecture 04-1 · Pruning and Sparsity I

المحاضرة 04-1 · التقليم والتناثر (Pruning and Sparsity I)

Why prune and the pruning formulation

لماذا نقلّم (prune)، وصياغة التقليم

Slides 1–6 الشرائح 1–6 P2 SHOULD

Memory traffic is the energy bill, pruning cuts the number of weights you fetch, and the whole idea fits in one constrained optimization with an L0 "norm" in it.

حركة الذاكرة هي فاتورة الطاقة، وpruning يقلّل عدد الأوزان التي تجلبها، والفكرة كلها تُكتب في مسألة تحسين واحدة مقيّدة فيها "معيار" L0.

What gets asked ما الذي يُسأل عنه

Three things come out of these six slides: the energy ratios (DRAM vs arithmetic), the formulation argmin L(x; W_P) s.t. ||W_P||₀ ≤ N with what each symbol means, and the sparsity arithmetic (sparsity, density, reduction factor). Expect a short numeric question on the last one.

يخرج من هذه الشرائح الست ثلاثة أشياء: نسب الطاقة (DRAM مقابل العمليات الحسابية)، والصيغة argmin L(x; W_P) s.t. ||W_P||₀ ≤ N مع معنى كل رمز فيها، وحساب sparsity وdensity وreduction factor. توقّع سؤالاً رقمياً قصيراً على الأخير.

The pruning pipeline: four questions

خط التقليم: أربعة أسئلة

Slide 2 is the lecture outline, and it doubles as the recipe for every pruning method you will meet. Each stage answers one question:

الشريحة 2 هي مخطط المحاضرة، وهي في الوقت نفسه الوصفة التي تتبعها كل طريقة pruning ستقابلها. كل مرحلة تجيب عن سؤال واحد:

Formulate. What is pruning, written as an optimization problem? (this page)
الصياغة. ما هو pruning مكتوباً كمسألة تحسين؟ (هذه الصفحة)
Granularity. In what pattern do we delete: single weights, rows, kernels, whole channels?
الدقّة (granularity). بأي نمط نحذف: أوزان مفردة، أم صفوف، أم kernels، أم قنوات كاملة؟
Criterion. Which synapses or neurons are least important and should go?
المعيار (criterion). أي synapses أو neurons هي الأقل أهمية فتُحذف؟
Ratio. What target sparsity should each layer get?
النسبة (ratio). ما target sparsity المناسبة لكل طبقة؟
Fine-tune. How do we recover the accuracy the cut cost us?
إعادة الضبط (fine-tune). كيف نسترجع الدقة التي خسرناها بسبب القطع؟

Lecture 04-1 covers the first three (formulation, granularity, criterion). Ratio and fine-tuning are lecture 04-2. If an exam asks "which question does a sensitivity sweep answer", the answer is the ratio, not the criterion.

المحاضرة 04-1 تغطي الثلاثة الأولى (الصياغة، granularity، criterion). أما ratio وfine-tuning ففي المحاضرة 04-2. إذا سألك الامتحان "أي سؤال يجيب عنه sensitivity sweep؟" فالجواب هو ratio وليس criterion.

Why prune: data movement is the energy bill

لماذا نقلّم: نقل البيانات هو فاتورة الطاقة

Slide 3's headline is a chain: data movement → more memory references → more energy. The table (Horowitz, ISSCC 2014, 45 nm at 0.9 V) is the evidence:

عنوان الشريحة 3 سلسلة: حركة البيانات ← مراجع ذاكرة أكثر ← طاقة أكثر. والجدول (Horowitz, ISSCC 2014، تقنية 45 nm عند 0.9 V) هو الدليل:

Operationالعملية	Energy (pJ)الطاقة (pJ)	Relative to int ADDنسبةً إلى int ADD
32-bit int ADDجمع صحيح 32-bit int ADD	0.1	1x
32-bit float ADDجمع عشري 32-bit float ADD	0.9	9x
32-bit register fileملف المسجلات 32-bit register file	1	10x
32-bit int MULTضرب صحيح 32-bit int MULT	3.1	31x
32-bit float MULTضرب عشري 32-bit float MULT	3.7	37x
32-bit SRAM cacheذاكرة مخبئية 32-bit SRAM cache	5	50x
32-bit DRAM memoryذاكرة 32-bit DRAM memory	640	6400x

يعرض الجدول طاقة كل عملية بالـ picojoule ونسبتها إلى أرخص عملية وهي جمع الأعداد الصحيحة. ما يجب أن تلاحظه: كل العمليات الحسابية والذاكرة القريبة (register وSRAM) تقع بين 0.1 و5 pJ، ثم تقفز DRAM إلى 640 pJ، أي أكثر من مئة ضعف أغلى عملية حسابية. هذه القفزة هي سبب المحاضرة كلها.

Slide 3 on a log axis. The arrow is the slide's red "200x" between DRAM and a 32-bit integer multiply. Fetching a weight from DRAM, not multiplying by it, is what dominates the energy of a large model.

الشريحة 3 على محور لوغاريتمي. السهم هو الـ "200x" الأحمر في الشريحة بين DRAM وضرب صحيح بـ 32-bit. جلب الوزن من DRAM، لا الضرب فيه، هو ما يهيمن على طاقة النموذج الكبير.

الرسم أعلاه هو الشريحة 3 على محور لوغاريتمي، والسهم هو "200x" الأحمر بين DRAM وضرب الأعداد الصحيحة 32-bit. الذي يستهلك الطاقة في النموذج الكبير هو جلب الوزن من DRAM، وليس الضرب فيه.

Worked example مثال محلول

The two ratios the slide wants you to be able to produce:

النسبتان اللتان تريد الشريحة أن تستطيع حسابهما:

DRAM / int MULT = 640 / 3.1 = 206.5   ~ 200x   (slide: "1 DRAM = 200x +")
DRAM / int ADD  = 640 / 0.1 = 6400x
DRAM / SRAM     = 640 / 5   = 128x

Now scale it to a whole network. Take a net with 1 billion connections (weights) running at 20 frames per second, and assume each weight is fetched from DRAM once per frame:

الآن طبّقها على شبكة كاملة. خُذ شبكة فيها مليار اتصال (وزن) تعمل بمعدل 20 إطاراً في الثانية، وافترض أن كل وزن يُجلب من DRAM مرة واحدة في كل إطار:

fetches per second = 1e9 weights x 20 Hz        = 2e10 fetches/s
energy per fetch   = 640 pJ                      = 640e-12 J
power              = 2e10 x 640e-12 J/s          = 12.8 W

12.8 W for DRAM fetches alone, before a single multiply. A phone's whole power budget is a few watts, so this network cannot run on a phone as is. Every weight you prune is a 640 pJ fetch you never pay for, which is why pruning comes before quantization in this course.

12.8 W لجلب البيانات من DRAM وحده، قبل أي عملية ضرب. وميزانية الطاقة الكاملة للهاتف هي بضعة watts، فلا يمكن تشغيل هذه الشبكة على هاتف كما هي. كل وزن تحذفه هو عملية جلب بكلفة 640 pJ لن تدفعها أبداً، ولهذا يأتي pruning قبل quantization في هذا المقرر.

Synapse pruning vs neuron pruning

تقليم المشابك (synapse pruning) مقابل تقليم العصبونات (neuron pruning)

Slide 4 shows two kinds of deletion on the same network. Pruning synapses deletes individual connections (weights): the neurons stay, they just have fewer inputs. Pruning neurons deletes a whole node, and with it every connection into and out of it.

تعرض الشريحة 4 نوعين من الحذف على الشبكة نفسها. Pruning synapses يحذف اتصالات مفردة (أوزاناً): تبقى neurons لكن بمدخلات أقل. أما pruning neurons فيحذف عقدة كاملة، ومعها كل اتصال داخل إليها وخارج منها.

In matrix terms, for a fully connected layer y = W_lx with W_l of shape [out, in], neuron j of layer l owns row j of W_l (its incoming weights) and column j of W_l+1 (its outgoing weights, because its output is an input to the next layer). Deleting the neuron deletes both.

بلغة المصفوفات، في طبقة fully connected هي y = W_lx حيث شكل W_l هو [out, in]، فإن neuron رقم j في الطبقة l يملك الصف j من W_l (أوزانه الداخلة) والعمود j من W_l+1 (أوزانه الخارجة، لأن مخرجه مدخل للطبقة التالية). حذف neuron يحذف الاثنين معاً.

Deleting hidden neuron j (red) in a 5-4-3 MLP. It takes out row j of W₁ (5 incoming weights) and column j of W₂ (3 outgoing weights). The two matrices shrink but remain dense, which is why neuron pruning is a coarse-grained, hardware-friendly cut.

حذف العصبون المخفي j (بالأحمر) في MLP بأبعاد 5-4-3. يُزيل ذلك الصف j من W₁ (5 أوزان داخلة) والعمود j من W₂ (3 أوزان خارجة). تصغر المصفوفتان لكنهما تبقيان كثيفتين، ولهذا يُعدّ تقليم العصبونات قطعاً خشن الحبيبات (coarse-grained) ومناسباً للعتاد.

حذف neuron المخفي j (الأحمر) في شبكة MLP بأبعاد 5-4-3: يُزال الصف j من W₁ (5 أوزان داخلة) والعمود j من W₂ (3 أوزان خارجة)، أي 8 أوزان من 32. تصغر المصفوفتان لكنهما تبقيان كثيفتين (dense)، ولهذا يُعدّ حذف neurons قطعاً خشناً (coarse-grained) يناسب العتاد.

Synapse pruning gives more freedom (any single weight can go) but leaves an irregular sparse matrix of the same shape. Neuron pruning gives less freedom but a smaller dense matrix. That trade-off is exactly the granularity spectrum two pages ahead.

Synapse pruning يعطي حرية أكبر (أي وزن مفرد يمكن حذفه) لكنه يترك مصفوفة متفرقة غير منتظمة بالشكل نفسه. أما neuron pruning فحريته أقل لكنه ينتج مصفوفة كثيفة أصغر. هذه المقايضة هي بالضبط طيف granularity الذي يأتي بعد صفحتين.

The formulation

الصياغة

Slide 5 writes pruning as a constrained optimization:

تكتب الشريحة 5 عملية pruning كمسألة تحسين مقيّدة:

arg min_{W_P} L(x; W_P) subject to ||W_P||₀ ≤ N

The symbols

الرموز

L: the training objective (loss). x: the input. W: the original dense weights. W_P: the pruned weights you are solving for. N: the target number of nonzeros.

L: دالة الهدف في التدريب (loss). x: المدخل. W: الأوزان الأصلية الكثيفة. W_P: الأوزان بعد الحذف وهي المجهول الذي نحلّ له. N: العدد المستهدف من القيم غير الصفرية.

Reading it

كيف تقرؤها

"Find the weights with the lowest loss among all weight settings that have at most N nonzeros." Unpruned training is the same problem without the constraint: arg min_W L(x; W).

"جد الأوزان ذات أقل loss من بين كل إعدادات الأوزان التي لا يتجاوز عدد قيمها غير الصفرية N." والتدريب العادي هو المسألة نفسها بدون القيد: arg min_W L(x; W).

What ||·||₀ is, and why it is awkward

ما هو ||·||₀، ولماذا يصعب التعامل معه

||W_P||₀ counts the nonzero entries of W_P. It is called the L0 "norm" by convention, but it is not a true norm: a norm must satisfy ||aW|| = |a| · ||W||, and scaling a vector by 5 does not change how many nonzeros it has. So ||5W||₀ = ||W||₀, not 5||W||₀.

||W_P||₀ يعدّ القيم غير الصفرية في W_P. يُسمّى "معيار" L0 بحكم العادة، لكنه ليس norm حقيقياً: فالـ norm يجب أن يحقق ||aW|| = |a| · ||W||، وضرب المتجه في 5 لا يغيّر عدد قيمه غير الصفرية. إذن ||5W||₀ = ||W||₀ وليس 5||W||₀.

It is also a step function of the weights: it jumps by 1 when a weight crosses zero and is flat everywhere else. Its gradient is zero almost everywhere and undefined at the jumps, so you cannot just add it to the loss and run SGD. The problem is combinatorial (which N of the weights to keep), which is why practical methods use heuristics: rank weights by an importance criterion such as magnitude, cut the lowest, then retrain.

وهو أيضاً دالة درجية في الأوزان: يقفز بمقدار 1 عندما يعبر وزن ما الصفر، وثابت في كل مكان آخر. gradient له صفر في كل مكان تقريباً وغير معرّف عند القفزات، فلا يمكنك إضافته إلى loss وتشغيل SGD ببساطة. المسألة توافقية (أي N من الأوزان نُبقي)، ولهذا تستخدم الطرق العملية أساليب تقريبية: رتّب الأوزان بمعيار أهمية مثل المقدار (magnitude)، واحذف الأدنى، ثم أعد التدريب.

W = [0.8, 0, -0.3, 0, 0.05]

||W||_0 = 3          (three nonzeros: 0.8, -0.3, 0.05)
||W||_1 = 0.8 + 0.3 + 0.05 = 1.15
||5W||_0 = 3         (still 3: L0 ignores scale, so it is not a norm)

مثال صغير: المتجه W = [0.8, 0, -0.3, 0, 0.05] فيه ثلاث قيم غير صفرية فيكون ||W||₀ = 3، بينما ||W||₁ = 1.15. وبعد ضربه في 5 يبقى ||5W||₀ = 3، لأن L0 يتجاهل المقياس، ولذلك ليس norm.

Erratum on slide 5 خطأ في الشريحة 5

The bullet text writes the constraint as ||W_p||₀ < N (strict), while the figure on the same slide writes ≤ N, and the slide itself defines N as "the target #nonzeros". A model with exactly N nonzeros must be allowed, so ≤ is correct and the strict < is a typo. Write ≤ in the exam.

نص النقطة يكتب القيد ||W_p||₀ < N (أصغر تماماً)، بينما الرسم في الشريحة نفسها يكتب ≤ N، والشريحة تعرّف N بأنه "the target #nonzeros". النموذج الذي فيه N قيمة غير صفرية بالضبط يجب أن يكون مقبولاً، إذن ≤ هو الصحيح و< خطأ مطبعي. اكتب ≤ في الامتحان.

Sparsity, density, reduction factor

التناثر (sparsity) والكثافة (density) ومعامل التخفيض (reduction factor)

Three numbers describe the same cut, and exams mix them on purpose. With |W| total weights and N kept:

ثلاثة أرقام تصف القطع نفسه، والامتحانات تخلط بينها عن قصد. إذا كان العدد الكلي للأوزان |W| وأبقينا N:

Density

الكثافة (density)

d = N / |W|

Fraction of weights kept.

نسبة الأوزان المُبقاة.

Sparsity

التناثر (sparsity)

s = 1 − N / |W|

Fraction removed (zeros). Same as "pruning ratio".

نسبة الأوزان المحذوفة (الأصفار). وهي نفسها "pruning ratio".

Reduction factor

معامل التخفيض (reduction factor)

|W| / N = 1 / (1 − s)

How many times smaller the weight count is.

كم مرة أصغر صار عدد الأوزان.

Worked example مثال محلول

AlexNet goes from 61M parameters to 6.7M after pruning (lecture 04-1, slide 11). All three numbers:

ينتقل AlexNet من 61M معامل إلى 6.7M بعد الحذف (المحاضرة 04-1، الشريحة 11). الأرقام الثلاثة:

|W| = 61M,  N = 6.7M

density          d = 6.7 / 61      = 0.110    -> 11.0 % kept
sparsity         s = 1 - 0.110     = 0.890    -> 89.0 % zeros
reduction factor   = 61 / 6.7      = 9.1      -> "9x" on the slide

check: 1 / (1 - 0.890) = 1 / 0.110 = 9.1

In the formulation, this is the problem with N = 6.7M. Note that 89 percent sparsity gives 9x, not 89x and not 10x.

في الصياغة، هذه هي المسألة عند N = 6.7M. لاحظ أن sparsity بنسبة 89% تعطي 9x، وليس 89x ولا 10x.

Pruning in the human brain

التقليم في الدماغ البشري

Slide 6 plots synapses per neuron over a human life: about 2,500 at birth, rising to a peak of about 15,000 at 2 to 4 years, then falling through adolescence to about 7,000 in adults (Drachman 2004; Huttenlocher). The brain overprovisions connections early, then removes the ones it does not use.

ترسم الشريحة 6 عدد synapses لكل neuron عبر حياة الإنسان: حوالي 2,500 عند الولادة، ترتفع إلى ذروة حوالي 15,000 بين سنتين وأربع سنوات، ثم تنخفض خلال المراهقة إلى حوالي 7,000 عند البالغين (Drachman 2004؛ Huttenlocher). الدماغ يُفرط في بناء الاتصالات مبكراً، ثم يزيل ما لا يستخدمه.

peak to adult: (15000 - 7000) / 15000 = 0.53  -> about 53 % of synapses pruned

من الذروة إلى البلوغ: (15000 - 7000) / 15000 = 0.53، أي أن حوالي 53% من synapses تُحذف.

The parallel to neural nets is "train a big, overparameterized model, then prune it". Treat it as motivation, not proof: the brain analogy does not tell you which weights to cut or how much accuracy you keep. The evidence that pruning works is the accuracy curves on the next page.

التشابه مع الشبكات العصبية هو: "درّب نموذجاً كبيراً زائد المعاملات، ثم احذف منه". تعامل معه على أنه دافع وليس برهاناً: تشبيه الدماغ لا يخبرك أي الأوزان تقطع ولا كم من الدقة ستحتفظ بها. الدليل على أن pruning ينجح هو منحنيات الدقة في الصفحة التالية.

Exam trap فخ امتحاني

Sparsity vs density vs reduction factor. 89 percent sparsity = 11 percent density = 9x reduction. If a question says "pruned to 10 percent", that is the density (90 percent sparsity, 10x).
Sparsity مقابل density مقابل reduction factor. sparsity بنسبة 89% = density بنسبة 11% = تقليل 9x. وإذا قال السؤال "pruned to 10 percent" فهذه هي density (أي sparsity 90% و10x).
< vs ≤. The constraint is ||W_P||₀ ≤ N. The strict form on the slide bullet is a typo.
< مقابل ≤. القيد هو ||W_P||₀ ≤ N، والصيغة الصارمة في نص الشريحة خطأ مطبعي.
L0 is not a norm and has no useful gradient. It counts nonzeros, ignores magnitude, and is piecewise constant.
L0 ليس norm وليس له gradient مفيد. هو يعدّ القيم غير الصفرية، ويتجاهل المقدار، وثابت على أجزاء.
The 200x is DRAM vs int multiply, not DRAM vs int add (that is 6400x) and not DRAM vs SRAM (128x).
الـ 200x هي DRAM مقابل ضرب الأعداد الصحيحة، وليست مقابل الجمع (فتلك 6400x) ولا مقابل SRAM (128x).
Neuron pruning removes two things: its row in this layer's matrix and its column in the next layer's matrix. Counting only the row undercounts.
حذف neuron يزيل شيئين: صفّه في مصفوفة هذه الطبقة وعموده في مصفوفة الطبقة التالية. عدّ الصف وحده يعطي رقماً ناقصاً.

Check yourself

اختبر نفسك

Using slide 3's table, roughly how many 32-bit integer additions cost the same energy as one 32-bit DRAM access?

باستخدام جدول الشريحة 3، تقريباً كم عملية جمع أعداد صحيحة 32-bit تساوي في الطاقة وصولاً واحداً إلى DRAM؟

C. 640 pJ / 0.1 pJ = 6400. A is the slide's highlighted ratio, but that compares DRAM to an int multiply (640 / 3.1 ≈ 206). B is DRAM vs SRAM (640 / 5). D forgets to divide by the 0.1 pJ cost of the add.

الجواب C. 640 pJ / 0.1 pJ = 6400. الخيار A هو النسبة المميّزة في الشريحة، لكنها تقارن DRAM بعملية الضرب (640 / 3.1 ≈ 206). والخيار B هو DRAM مقابل SRAM (640 / 5). والخيار D ينسى القسمة على كلفة الجمع 0.1 pJ.

A network with 1 billion weights runs at 20 Hz, and every weight is fetched from DRAM once per inference at 640 pJ per fetch. What power goes to DRAM fetches?

شبكة فيها مليار وزن تعمل بتردد 20 Hz، وكل وزن يُجلب من DRAM مرة في كل استدلال بكلفة 640 pJ. ما القدرة المستهلكة في جلب البيانات من DRAM؟

B. 1e9 × 20 = 2e10 fetches per second, times 640e-12 J = 12.8 J/s = 12.8 W. A is the energy of one full pass (1e9 × 640 pJ = 0.64 J) mistaken for power, without the 20 per second. C and D are off by a factor of 10 from a slipped exponent.

الجواب B. 1e9 × 20 = 2e10 عملية جلب في الثانية، مضروبة في 640e-12 J تعطي 12.8 J/s = 12.8 W. الخيار A هو طاقة تمريرة واحدة (0.64 J) أُخذت على أنها قدرة بدون الضرب في 20. والخياران C وD مخطئان بعامل 10 بسبب أس منزلق.

In arg min_{W_P} L(x; W_P) s.t. ||W_P||₀ ≤ N, what does ||W_P||₀ compute?

في arg min_{W_P} L(x; W_P) s.t. ||W_P||₀ ≤ N، ماذا يحسب ||W_P||₀؟

D. Slide 5: "||W_p||₀ calculates the #nonzeros in W_P, and N is the target #nonzeros". A is the L1 norm, B is the L∞ norm, C is the L2 norm. L0 is the odd one out: it ignores magnitude entirely, which is also why it is not a true norm.

الجواب D. الشريحة 5: "||W_p||₀ calculates the #nonzeros in W_P". الخيار A هو L1 norm، وB هو L∞ norm، وC هو L2 norm. أما L0 فيتجاهل المقدار تماماً، ولهذا أيضاً ليس norm حقيقياً.

A model is pruned from 61M to 6.7M parameters. Which statement is correct?

نموذج حُذف منه حتى انتقل من 61M إلى 6.7M معامل. أي عبارة صحيحة؟

A. Density = 6.7/61 = 0.110, sparsity = 1 − 0.110 = 0.890, reduction = 61/6.7 = 9.1. B and D swap sparsity with density. C reads the sparsity percentage as a reduction factor. The factor is 1/(1 − s), not s.

الجواب A. density = 6.7/61 = 0.110، وsparsity = 1 − 0.110 = 0.890، وreduction = 61/6.7 = 9.1. الخياران B وD يبدّلان sparsity مع density. والخيار C يقرأ نسبة sparsity على أنها reduction factor، والصحيح أن العامل هو 1/(1 − s).

In an MLP with layers of 6, 8 and 5 neurons (fully connected, no biases), you prune one neuron from the 8-neuron hidden layer. How many weights disappear?

في شبكة MLP بطبقات من 6 و8 و5 neurons (متصلة كلياً، بدون bias)، حذفت neuron واحداً من الطبقة المخفية ذات 8. كم وزناً يختفي؟

C. The neuron's row in W₁ (8 × 6) holds its 6 incoming weights, and its column in W₂ (5 × 8) holds its 5 outgoing weights: 6 + 5 = 11. A counts only the incoming row, B only the outgoing column. D is the whole of W₁.

الجواب C. صف neuron في W₁ (8 × 6) يحمل أوزانه الداخلة الستة، وعموده في W₂ (5 × 8) يحمل أوزانه الخارجة الخمسة: 6 + 5 = 11. الخيار A يعدّ الصف الداخل فقط، وB العمود الخارج فقط، وD هو W₁ كاملة.