Lecture 04-1 · Pruning and Sparsity I

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

Neuron pruning, APoZ and regression-based

تقليم الخلايا العصبية، وAPoZ، والتقليم المبني على الانحدار (regression)

Slides 38–43 الشرائح 38–43 P1 MUST

Two data-driven ways to choose which neurons or channels to delete. APoZ counts how often a channel is silent after ReLU. Regression-based pruning keeps the input channels that can best rebuild the layer's output.

طريقتان مبنيّتان على البيانات لاختيار الـ neurons أو القنوات التي نحذفها. APoZ يعدّ كم مرة تكون القناة صامتة بعد ReLU. أما regression-based pruning فيُبقي قنوات الدخل التي تستطيع أفضل من غيرها إعادة بناء خرج الطبقة.

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

Expect a counting question: the slide 40 grids, or new grids, with a request for each channel's APoZ and which channel to prune. Expect a short answer on the regression objective: write it, name β and Nc, and give the two alternating steps.

توقّع سؤال عدّ: شبكات الشريحة 40، أو شبكات جديدة، ويُطلب منك APoZ لكل قناة وأي قناة تُحذف. وتوقّع سؤالاً قصيراً عن هدف regression: اكتبه، وسمِّ β وNc، واذكر الخطوتين المتناوبتين.

Neuron pruning is coarse-grained weight pruning, slide 38

تقليم الخلايا العصبية هو تقليم أوزان خشن الحبيبات (coarse-grained)، الشريحة 38

Slide 38's rule is that the less useful the removed neurons are, the better the pruned network performs. What matters is what a removed neuron takes with it. In a linear layer with W of shape (co, ci), output neuron o owns row W[o, :], all ci of its incoming weights. Delete the neuron and the whole row goes, so the matrix becomes (co − 1, ci), a smaller dense matrix.

قاعدة الشريحة 38: كلما كانت الـ neurons المحذوفة أقل فائدة، كان أداء الشبكة بعد التقليم أفضل. المهم هو ما يأخذه الـ neuron معه عند حذفه. في طبقة linear أوزانها W بالشكل (co, ci)، يملك neuron الخرج o الصف W[o, :]، أي كل أوزانه الداخلة وعددها ci. احذف الـ neuron فيذهب الصف كله، فتصبح المصفوفة (co − 1, ci)، وهي مصفوفة dense أصغر.

In a conv layer with W of shape (co, ci, kh, kw), removing output channel o removes the whole filter W[o, :, :, :], which is ci kernels of kh x kw. Its output map disappears too, so the next layer also loses input channel o: Wnext[:, o, :, :]. One channel removal shrinks two layers.

في طبقة conv أوزانها (co, ci, kh, kw)، حذف قناة الخرج o يحذف الـ filter كاملاً W[o, :, :, :]، أي ci من الـ kernels بحجم kh x kw. وتختفي خريطة خرجه أيضاً، فتفقد الطبقة التالية قناة الدخل o: Wnext[:, o, :, :]. حذف قناة واحدة يقلّص طبقتين.

Unit removedالوحدة المحذوفةSlice deletedالشريحة المحذوفة من المصفوفةWeights deletedالأوزان المحذوفةShape afterالشكل بعد الحذف
Output neuron of a linear layerخلية إخراج في طبقة خطيةW[o, :]ci(co − 1, ci)
Output channel of a conv layerقناة إخراج في طبقة التفافW[o, :, :, :]ci kh kw(co − 1, ci, kh, kw)
Matching input channel of the next convقناة الإدخال المقابلة في طبقة الالتفاف التاليةWnext[:, o, :, :]co,next kh kw(co,next, ci,next − 1, kh, kw)

يلخّص الجدول ما تأخذه كل وحدة محذوفة معها: neuron في طبقة linear يأخذ صفاً من ci وزناً، وقناة conv تأخذ filter من ci kh kw وزناً، ثم تأخذ أيضاً قناة الدخل المقابلة في الطبقة التالية.

That is why slide 38 calls neuron pruning coarse-grained weight pruning: it is weight pruning where a whole row or filter is the unit. The result needs no index storage and no sparse kernel, so it gives real speedup on any hardware. The open question is only the criterion: how to measure "useful". Lecture 04-1 already gave one answer (the L1 or L2 norm of the row). The next two sections give data-driven answers.

ولهذا تسمّي الشريحة 38 تقليم الـ neurons بـ coarse-grained weight pruning: هو تقليم أوزان وحدته صف كامل أو filter كامل. النتيجة لا تحتاج تخزين فهارس ولا sparse kernel، فتعطي تسريعاً حقيقياً على أي عتاد. ويبقى السؤال الوحيد هو المعيار: كيف نقيس "الفائدة". المحاضرة 04-1 أعطت جواباً من قبل (L1 أو L2 norm للصف). والقسمان التاليان يعطيان جوابين مبنيين على البيانات.

APoZ: Average Percentage of Zeros, slides 39 and 40

APoZ: متوسط نسبة الأصفار (Average Percentage of Zeros)، الشريحتان 39 و40

ReLU sets every negative pre-activation to zero. A channel whose output map is mostly zero, image after image, passes almost nothing to the next layer, whatever its weights look like. Hu et al. turned that into a score: run a batch (or a validation set) through the network and count, for each channel, the fraction of its post-ReLU outputs that are exactly zero.

ReLU يجعل كل pre-activation سالب يساوي صفراً. القناة التي تكون خريطة خرجها في الغالب أصفاراً، صورة بعد صورة، لا تمرّر شيئاً تقريباً إلى الطبقة التالية، مهما كانت أوزانها. حوّل Hu et al. هذه الملاحظة إلى درجة: مرّر batch (أو مجموعة تحقق) عبر الشبكة، وعُدّ لكل قناة نسبة مخرجاتها بعد ReLU التي تساوي صفراً بالضبط.

APoZc = #zeros in channel c over the batchbatch · H · W

The direction is the whole point: larger APoZ means less important. A channel that is zero most of the time contributes little, so the channel with the largest APoZ is pruned. Slide 40 states it as "the smaller APoZ is, the more important the neuron is" (the slide's own wording has a typo, "more importance the neuron has").

الاتجاه هو جوهر الموضوع: APoZ الأكبر يعني أهمية أقل. القناة التي تكون صفراً معظم الوقت تساهم بالقليل، فالقناة ذات APoZ الأكبر هي التي تُحذف. الشريحة 40 تقولها هكذا: "كلما صغر APoZ كان الـ neuron أهم" (وفي صياغة الشريحة خطأ مطبعي: "more importance the neuron has").

BATCH 1 BATCH 2 APoZ = zeros / (2 x 4 x 4) ch 0 0 .1 .5 1 1.2 .6 .3 .2 0 .5 0 .3 .2 0 0 .8 5 zeros .5 0 .2 .1 0 .2 1.2 0 1.2 0 .2 .3 .2 .4 0 0 6 zeros 11/32 = 0.344 keep ch 1 .1 .5 0 0 .2 .3 0 1 .1 0 0 .5 .1 .6 .7 .1 5 zeros .1 .5 0 0 0 .8 0 1 .1 0 .1 1 .2 0 1 0 7 zeros 12/32 = 0.375 keep ch 2 0 0 .8 0 .7 0 .6 .1 1.2 1 0 .2 .5 0 .3 .5 6 zeros 0 .8 .1 0 .2 0 0 .3 0 .4 0 .5 .2 0 .3 0 8 zeros 14/32 = 0.438 largest APoZ: prune
The six post-ReLU maps from slides 39 and 40 (batch 2, three channels, 4 x 4 maps), zeros shaded. Every channel is judged over 2 x 4 x 4 = 32 positions. Channel 2 is silent most often and is crossed out on slide 40.
خرائط ما بعد ReLU الست من الشريحتين 39 و40 (batch حجمها 2، وثلاث قنوات، وخرائط 4 x 4)، والأصفار مظللة. كل قناة تُقيَّم على 2 x 4 x 4 = 32 موضعاً. القناة 2 هي الأكثر صمتاً، وهي المشطوبة في الشريحة 40.
Worked مثال محلول 
denominator = batch x H x W = 2 x 4 x 4 = 32

channel 0   batch 1 rows: 1 + 0 + 2 + 2 = 5
            batch 2 rows: 1 + 2 + 1 + 2 = 6
            APoZ = (5 + 6) / 32 = 11/32 = 0.344

channel 1   batch 1 rows: 2 + 1 + 2 + 0 = 5
            batch 2 rows: 2 + 2 + 1 + 2 = 7
            APoZ = (5 + 7) / 32 = 12/32 = 0.375

channel 2   batch 1 rows: 3 + 1 + 1 + 1 = 6
            batch 2 rows: 2 + 2 + 2 + 2 = 8
            APoZ = (6 + 8) / 32 = 14/32 = 0.438   largest

importance order: channel 0 > channel 1 > channel 2
prune channel 2

Count zeros row by row in each 4 x 4 map, add the two batches per channel, then divide by 32. Write the denominator before you divide: examiners look for batch · H · W and for the sentence "largest APoZ is pruned".

عُدّ الأصفار صفاً صفاً في كل خريطة 4 x 4، واجمع الـ batch الاثنين لكل قناة، ثم اقسم على 32. اكتب المقام قبل القسمة: المصحّح يبحث عن batch · H · W وعن جملة "الـ APoZ الأكبر هو الذي يُحذف".

The paper (Network Trimming, Hu, Peng, Tai and Tang, arXiv 2016) measured APoZ over a large validation set, found that deeper layers are much more silent (VGG-16 CONV5-3 mean APoZ about 93 percent against about 47 percent for CONV1-1), and trimmed neurons whose APoZ is more than one standard deviation above the layer mean, then retrained from the surviving weights and repeated a few layers at a time.

الورقة (Network Trimming، Hu, Peng, Tai and Tang، arXiv 2016) قاست APoZ على مجموعة تحقق كبيرة، ووجدت أن الطبقات العميقة أكثر صمتاً بكثير (متوسط APoZ في VGG-16 CONV5-3 نحو 93% مقابل نحو 47% في CONV1-1)، وقلّمت الـ neurons التي يزيد APoZ لها عن متوسط الطبقة بأكثر من انحراف معياري واحد، ثم أعادت التدريب انطلاقاً من الأوزان الباقية، وكررت ذلك على طبقات قليلة في كل مرة.

Regression-based pruning, slides 41 and 42

التقليم المبني على الانحدار (regression-based)، الشريحتان 41 و42

APoZ looks at what a channel emits. He, Zhang and Sun (ICCV 2017) ask a different question: instead of the pruning error of the whole objective L(x; W), minimize the reconstruction error of this layer's output. Sample b positions, unroll the inputs into X (b x ci), and the layer output is a matrix product that splits into one term per input channel.

APoZ ينظر إلى ما تُخرجه القناة. أما He, Zhang and Sun (ICCV 2017) فيسألون سؤالاً مختلفاً: بدلاً من خطأ التقليم في دالة الهدف كاملة L(x; W)، قلّل reconstruction error لخرج هذه الطبقة. خذ b موضعاً، وافرد المدخلات في X بحجم (b x ci)، فيكون خرج الطبقة ضرب مصفوفات ينقسم إلى حد واحد لكل قناة دخل.

Z = X WT = Σc=0ci−1 Xc WcT argminW, β ‖Z − Ẑ‖F2 = ‖Z − Σc βc Xc WcT‖F2   subject to   ‖β‖0 ≤ Nc

β is a coefficient vector of length ci; βc = 0 means input channel c is pruned. Nc is the number of nonzero (surviving) channels, so the L0 constraint is a channel budget. The Frobenius norm squared is just the sum of squared errors over every entry of the b x co output. The loss and the labels do not appear at all.

β متجه معاملات طوله ci؛ وβc = 0 يعني أن قناة الدخل c قُلّمت. Nc هو عدد القنوات غير الصفرية (الباقية)، فقيد L0 هو ميزانية قنوات. ومربع Frobenius norm هو ببساطة مجموع مربعات الأخطاء على كل عناصر الخرج b x co. دالة الخسارة والتسميات لا تظهر إطلاقاً.

Z HAT = SUM OVER c OF BETA_c X_c W_c^T, WITH BETA = (1, 0, 1, 1) X0 X1 X2 X3 X (b x c_i) x W0^T W1^T W2^T W3^T W^T (c_i x c_o) = Z hat (b x c_o) column 1 of X and row 1 of W^T vanish together; the output width c_o does not change minimize ||Z - Z hat||_F^2 subject to ||beta||_0 <= N_c
Slide 41's picture with ci = 4. β1 = 0 deletes column X1 and row W1T as a pair. Ẑ keeps the shape b x co, so the next layer sees an input of the same shape.
رسم الشريحة 41 مع ci = 4. β1 = 0 يحذف العمود X1 والصف W1T معاً كزوج. ويحتفظ Ẑ بالشكل b x co، فترى الطبقة التالية مدخلاً بالشكل نفسه.

Solve it by alternating

الحل بالتناوب

  1. Fix W, solve β for channel selection. The L0 constraint is NP-hard, so the paper relaxes it to an L1 penalty λ‖β‖1: this is LASSO regression, which drives some βc exactly to zero. Raise λ until only Nc channels survive.

    ثبّت W وحُلّ β لاختيار القنوات. قيد L0 مسألة NP-hard، فتستبدله الورقة بعقوبة L1 هي λ‖β‖1: وهذا هو LASSO regression الذي يدفع بعض βc إلى الصفر تماماً. ارفع λ حتى لا يبقى إلا Nc قناة.

  2. Fix β, solve W to minimize reconstruction error. With the surviving channels fixed, refit their weights by ordinary least squares so they rebuild Z as closely as possible.

    ثبّت β وحُلّ W لتقليل reconstruction error. بعد تثبيت القنوات الباقية، أعد حساب أوزانها بطريقة least squares العادية لتعيد بناء Z بأقرب ما يمكن.

Result quoted in the paper: VGG-16 at 4x speedup with only 1.0 percent more top-5 error. Pruning layer by layer works because every layer is regressed toward the original network's output, so errors do not pile up silently.

النتيجة المذكورة في الورقة: VGG-16 بتسريع 4x مع زيادة 1.0% فقط في top-5 error. التقليم طبقة بعد طبقة ينجح لأن كل طبقة تُطابَق مع خرج الشبكة الأصلية، فلا تتراكم الأخطاء بصمت.

APoZ

APoZ

Reads post-ReLU activations from a forward pass. Scores output neurons or channels. One number per channel, prune the largest. Cheap, but blind to how the next layer uses the signal.

يقرأ التنشيطات بعد ReLU من forward pass. يقيّم الـ neurons أو قنوات الخرج. رقم واحد لكل قناة، ويُحذف الأكبر. رخيص، لكنه لا يرى كيف تستخدم الطبقة التالية الإشارة.

Regression-based

المبني على الانحدار (Regression-based)

Reads sampled inputs X and outputs Z of one layer. Selects input channels (β has length ci) by LASSO, then refits W by least squares. More expensive, but it directly protects what the next layer receives.

يقرأ عينات المدخلات X والمخرجات Z لطبقة واحدة. يختار قنوات الدخل (طول β هو ci) بواسطة LASSO، ثم يعيد ملاءمة W بـ least squares. أغلى، لكنه يحمي مباشرة ما تستقبله الطبقة التالية.

Trap فخ

High APoZ means prune, not keep. APoZ counts silence. Slide 40 crosses out channel 2 at 14/32, the largest value. Do not be misled by the typo "the more importance the neuron has": the meaning is "smaller APoZ, more important".

APoZ المرتفع يعني احذف، لا أبقِ. APoZ يعدّ الصمت. الشريحة 40 تشطب القناة 2 عند 14/32، وهي القيمة الأكبر. لا يضلّلك الخطأ المطبعي "the more importance the neuron has": المعنى هو "APoZ أصغر يعني أهمية أكبر".

The denominator is batch x H x W, not H x W. 11/16 would be wrong for channel 0; the zeros of both batch items are pooled over 32 positions.

المقام هو batch x H x W وليس H x W. 11/16 خطأ للقناة 0؛ أصفار عنصري الـ batch تُجمع على 32 موضعاً.

β indexes input channels. It has length ci and removes a column of X with its row of WT. The output width co stays the same.

β يفهرس قنوات الدخل. طوله ci، ويحذف عموداً من X مع الصف المقابل له في WT. عرض الخرج co يبقى كما هو.

Dates. The slides cite Network Trimming as arXiv 2017; the arXiv paper (1607.03250) is from 2016. Channel pruning (He et al.) is ICCV 2017.

التواريخ. الشرائح تنسب Network Trimming إلى arXiv 2017؛ لكن ورقة arXiv (1607.03250) من عام 2016. أما channel pruning لـ He et al. فهي في ICCV 2017.

Memory hook خطّاف للذاكرة

APoZ counts silence: the quietest channel goes. Regression asks "can the survivors still rebuild Z?": LASSO picks the survivors, least squares refits them.

APoZ يعدّ الصمت: القناة الأهدأ تُحذف. وregression يسأل "هل تستطيع القنوات الباقية إعادة بناء Z؟": LASSO يختار الباقين، وleast squares يعيد ملاءمتهم.

Check yourself

اختبر نفسك

A batch of 4 images gives 3 x 3 post-ReLU maps. Channel A has 18 zeros in total over the batch. What is its APoZ?

batch من 4 صور يعطي خرائط بحجم 3 x 3 بعد ReLU. القناة A فيها 18 صفراً في المجموع على الـ batch. ما قيمة APoZ لها؟

The denominator is batch x H x W = 4 x 3 x 3 = 36, so APoZ = 18/36 = 0.5. A fraction of zeros can never exceed 1, which rules out A, B and D immediately: they divide by H x W only, by batch x H, or by batch only.

المقام هو batch x H x W = 4 x 3 x 3 = 36، إذن APoZ = 18/36 = 0.5. نسبة الأصفار لا يمكن أن تتجاوز 1، وهذا يستبعد A وB وD فوراً: فهي تقسم على H x W فقط، أو على batch x H، أو على batch فقط.

Three channels have APoZ 0.20, 0.55 and 0.35. Under the APoZ criterion, which channel is pruned first?

ثلاث قنوات قيم APoZ لها 0.20 و0.55 و0.35. وفق معيار APoZ، أي قناة تُحذف أولاً؟

Larger APoZ means the channel is zero more often, so it is less important and goes first. The channel at 0.20 is the most important. APoZ is computed per neuron or channel from activations, so D is wrong.

APoZ الأكبر يعني أن القناة صفر في أغلب الأحيان، فهي الأقل أهمية وتُحذف أولاً. القناة ذات 0.20 هي الأهم. وAPoZ يُحسب لكل neuron أو قناة من التنشيطات، فالخيار D خطأ.

A linear layer has W of shape (8, 16). You prune 3 output neurons. How many weights of this layer disappear, and what else shrinks?

طبقة linear شكل أوزانها (8, 16). قلّمت 3 neurons من الخرج. كم وزناً يختفي من هذه الطبقة، وما الذي يصغر أيضاً؟

Each output neuron owns one row of 16 weights, so 3 x 16 = 48 disappear and W becomes (5, 16), a smaller dense matrix with nothing stored for the removed rows. The next layer no longer receives those 3 outputs, so its weight matrix loses 3 input columns.

كل neuron خرج يملك صفاً من 16 وزناً، فيختفي 3 x 16 = 48 وزناً وتصبح W بالشكل (5, 16)، مصفوفة dense أصغر لا يُخزَّن فيها شيء للصفوف المحذوفة. والطبقة التالية لم تعد تستقبل هذه المخرجات الثلاثة، فتفقد مصفوفة أوزانها 3 أعمدة دخل.

In regression-based channel pruning, which statement is correct?

في regression-based channel pruning، أي عبارة صحيحة؟

β has length ci and masks input channels. The objective is the layer's reconstruction error ‖Z − Ẑ‖F2, not the network loss (B describes OBD). The L1-relaxed selection step is on β (LASSO); the reconstruction step refits W by least squares. C swaps the solvers.

طول β هو ci وهو يحجب قنوات الدخل. الهدف هو reconstruction error للطبقة ‖Z − Ẑ‖F2، لا خسارة الشبكة (الخيار B يصف OBD). خطوة الاختيار المرخّاة بـ L1 تكون على β (LASSO)؛ وخطوة إعادة البناء تعيد ملاءمة W بـ least squares. الخيار C يبدّل الطريقتين.