Why prune: energy, definition and formulationلماذا نقلّم: الطاقة والتعريف والصياغة

Suppose you have a trained object detector that is accurate on your validation set but will not fit on the board you are targeting. Before you touch a single weight, four questions need answers, and the outline slide of this lecture is exactly that checklist. It reappears on slides 14 and 26 as a progress marker, so treat it as the map you return to as each section closes.

افترض أن لديك نموذج كشف أجسام (object detector) مدرّبًا ودقيقًا على مجموعة التحقق (validation set)، لكنه لا يتسع على اللوحة التي تستهدفها. قبل أن تلمس وزنًا واحدًا، هناك أربعة أسئلة تحتاج إلى إجابة، وشريحة المخطط العام (outline) في هذه المحاضرة هي قائمة التحقق هذه بالضبط. تعود الشريحة للظهور في الشريحتين 14 و26 كمؤشر للتقدم، فتعامل معها كالخريطة التي ترجع إليها كلما انتهى قسم.

Pruning makes a network smaller by removing the synapses and neurons whose removal hurts performance least. That one sentence hides a sequence of design decisions. First you must formulate the problem: what exactly is being minimized, and under what budget. Then you choose the granularity, the pattern in which weights are removed, from single scattered weights up to whole channels. Then a criterion, the rule that scores which synapses or neurons are least important. Then a ratio, the target sparsity for each layer. Finally you fine-tune or retrain the pruned network so the accuracy you lost comes back.

الـ Pruning (التقليم) يصغّر الشبكة بإزالة الوصلات (synapses) والعصبونات (neurons) التي يضرّ حذفها بالأداء أقل ما يمكن. هذه الجملة الواحدة تخفي سلسلة من قرارات التصميم. أولًا يجب أن تصوغ المسألة: ما الذي نقلّله بالضبط، وتحت أي ميزانية. ثم تختار الـ granularity (درجة التفصيل)، أي النمط الذي تُزال به الأوزان، من أوزان منفردة متفرقة إلى قنوات (channels) كاملة. ثم تختار criterion (معيارًا)، أي القاعدة التي تعطي درجة لكل وصلة أو عصبون لتحديد الأقل أهمية. ثم تختار ratio (نسبة)، أي الـ sparsity المستهدفة لكل طبقة. وأخيرًا تُجري fine-tune أو تعيد تدريب الشبكة بعد التقليم حتى تعود الدقة التي فقدتها.

This lecture, Pruning and Sparsity I, covers the formulation, the granularity and the criteria. The ratio and the fine-tuning belong to Pruning and Sparsity II, the next lecture. The split mirrors the two pruning lectures of the MIT course the deck is built on, and it explains why the outline slide is highlighted only at the top: the yellow marker moves down as the lecture proceeds.

هذه المحاضرة، Pruning and Sparsity I، تغطي الصياغة والـ granularity والمعايير. أما النسبة (ratio) والـ fine-tuning فينتميان إلى Pruning and Sparsity II، أي المحاضرة التالية. هذا التقسيم يطابق محاضرتي الـ pruning في مقرر MIT الذي بُني عليه هذا العرض، وهو يفسّر لماذا تكون شريحة المخطط العام مظلّلة في أعلاها فقط: العلامة الصفراء تنزل للأسفل كلما تقدمت المحاضرة.

Take one weight of a fully connected layer. It is fetched from off-chip DRAM and multiplied by an activation. The fetch costs 640 pJ. The 32-bit integer multiply costs 3.1 pJ. Divide them: 640 / 3.1 ≈ 206. Fetching the weight costs as much energy as about two hundred multiplies. That single ratio is the reason this lecture exists.

خذ وزنًا واحدًا من طبقة متصلة بالكامل (fully connected). يُجلب هذا الوزن من ذاكرة DRAM خارج الشريحة ثم يُضرب في قيمة تنشيط (activation). عملية الجلب تكلّف 640 pJ. أما عملية ضرب الأعداد الصحيحة بعرض 32-bit فتكلّف 3.1 pJ. اقسم أحدهما على الآخر: 640 / 3.1 ≈ 206. جلب الوزن يكلّف من الطاقة ما يعادل نحو مئتي عملية ضرب. هذه النسبة الواحدة هي سبب وجود هذه المحاضرة.

The numbers come from Mark Horowitz's ISSCC 2014 keynote, measured for a 45 nm process at 0.9 V, and reproduced in Han et al. (2015), which the slide follows. The full ladder is worth knowing by heart, because it is the quantitative case for every compression technique in this course. Read it top to bottom as an ordering of operations by cost, and notice that the four arithmetic rows and the register file all sit below 4 pJ while the two memory rows, SRAM and DRAM, close the table at 5 pJ and 640 pJ.

هذه الأرقام مأخوذة من الكلمة الرئيسية التي ألقاها Mark Horowitz في ISSCC 2014، وهي مقيسة لتقنية تصنيع 45 nm عند جهد 0.9 V، وأعاد نشرها Han et al. (2015)، وهي الورقة التي تتبعها الشريحة. يستحق السُّلّم كاملًا أن تحفظه عن ظهر قلب، لأنه الحجة الكمية لكل تقنية ضغط في هذا المقرر. اقرأه من الأعلى إلى الأسفل على أنه ترتيب للعمليات بحسب كلفتها، ولاحظ أن صفوف العمليات الحسابية الأربعة وملف المسجلات (register file) كلها أقل من 4 pJ، بينما يُختتم الجدول بصفّي الذاكرة، SRAM وDRAM، عند 5 pJ و640 pJ.

Han et al. summarize the ladder in one sentence: memory access is three orders of magnitude more energy expensive than simple arithmetic. Sze et al. make the same point in their survey: DRAM accesses require up to several orders of magnitude more energy than computation, and DRAM consumes two orders of magnitude more energy per access than a small on-chip memory of a few kilobytes. Measured against the rows of the ladder, one DRAM access costs as much as each of the following.

يلخّص Han et al. السُّلّم في جملة واحدة: الوصول إلى الذاكرة أغلى من العمليات الحسابية البسيطة بثلاث رتب عشرية (orders of magnitude) من حيث الطاقة. ويطرح Sze et al. الفكرة نفسها في مسحهم البحثي: الوصول إلى DRAM يتطلب طاقة أكبر من الحساب بما يصل إلى عدة رتب عشرية، وDRAM تستهلك لكل وصول طاقة أكبر برتبتين عشريتين من ذاكرة صغيرة داخل الشريحة حجمها بضعة كيلوبايتات. وبالمقارنة مع صفوف السُّلّم، فإن وصولًا واحدًا إلى DRAM يكلّف ما يعادل كل واحدة مما يلي.

The slide's icon line, one DRAM stick equals 200 ×+, rounds the chart's arrow: that arrow runs from the DRAM bar to the 32-bit int MULT bar, so the 200 is 640 / 3.1 ≈ 206 rounded down. Pricing one MAC instead (3.1 + 0.1 = 3.2 pJ) gives 640 / 3.2 = 200. Either way the answer is about two hundred.

سطر الأيقونات في الشريحة، حيث شريحة DRAM واحدة تساوي 200 ×+، هو تقريب لسهم المخطط: ذلك السهم يمتد من عمود DRAM إلى عمود ضرب الأعداد الصحيحة 32-bit int MULT، لذا فإن الـ 200 هي 640 / 3.1 ≈ 206 مقرّبة إلى الأسفل. وإذا حسبت كلفة MAC واحدة بدلًا من ذلك (3.1 + 0.1 = 3.2 pJ) تحصل على 640 / 3.2 = 200. في الحالتين الجواب نحو مئتين.

The chain from weights to wattsالسلسلة من الأوزان إلى الواط

The slide states the consequence as a chain: data movement, more memory references, more energy. Every weight that does not fit on chip is a DRAM reference on every inference. A network with more weights moves more bytes, more bytes mean more DRAM references, and each reference costs 640 pJ. The compute, the MACs that the earlier lectures counted so carefully, turns out to be the cheap part. This is the memory access energy problem, and pruning attacks it at the root by reducing the number of weights that have to move at all.

تعرض الشريحة النتيجة على شكل سلسلة: حركة البيانات، فمزيد من مرات الوصول إلى الذاكرة، فمزيد من الطاقة. كل وزن لا يتسع داخل الشريحة يعني وصولًا إلى DRAM في كل عملية استدلال (inference). الشبكة ذات الأوزان الأكثر تنقل بايتات أكثر، والبايتات الأكثر تعني مرات وصول أكثر إلى DRAM، وكل وصول يكلّف 640 pJ. أما الحساب، أي عمليات الـ MAC التي عددناها بعناية في المحاضرات السابقة، فيتضح أنه الجزء الرخيص. هذه هي مشكلة memory access energy (طاقة الوصول إلى الذاكرة)، والـ pruning يعالجها من جذورها بتقليل عدد الأوزان التي يجب نقلها أصلًا.

There is a second payoff hiding in the ladder. Once a pruned model is small enough, its weights stop living in DRAM at all and sit in on-chip SRAM, where an access costs 5 pJ instead of 640 pJ. That is the argument of Deep Compression: pruning plus quantization shrinks both networks to a few megabytes, small enough to fit in on-chip SRAM cache rather than off-chip DRAM.

هناك مكسب ثانٍ مخفي في السُّلّم. حين يصبح النموذج بعد الـ pruning صغيرًا بما يكفي، تتوقف أوزانه عن الإقامة في DRAM أصلًا وتستقر في ذاكرة SRAM داخل الشريحة، حيث يكلّف الوصول 5 pJ بدلًا من 640 pJ. هذه هي حجة Deep Compression: الـ pruning مع الـ quantization يقلّصان كلتا الشبكتين إلى بضعة ميغابايتات، وهو حجم صغير بما يكفي ليتسع في ذاكرة SRAM cache داخل الشريحة بدلًا من DRAM خارجها.

Separately, benchmarking the pruned fully connected layers on CPU, GPU and mobile GPU measured 3x to 7x less energy per layer. Fewer weights is the first win; crossing the SRAM boundary is the second.

وبشكل منفصل، أظهر قياس أداء الطبقات المتصلة بالكامل بعد الـ pruning على CPU وGPU وGPU المحمول انخفاضًا في الطاقة لكل طبقة بين 3x و7x. تقليل الأوزان هو المكسب الأول؛ وعبور حد SRAM هو المكسب الثاني.

The slide's before-and-after picture, taken from Han et al. (2015), is a small fully connected network with layers of 5, 4, 3 and 2 nodes. Count the edges: 5 × 4 + 4 × 3 + 3 × 2 = 20 + 12 + 6 = 38 synapses and 14 neurons. After pruning the layers read 5, 3, 2, 2. One hidden neuron is gone from the second layer, one from the third, and most of the remaining edges have vanished. Two different things were removed, and the slide labels them with two different arrows.

صورة «قبل وبعد» في الشريحة، المأخوذة من Han et al. (2015)، هي شبكة صغيرة متصلة بالكامل طبقاتها فيها 5, 4, 3 و2 عقد. عُدّ الحواف: 5 × 4 + 4 × 3 + 3 × 2 = 20 + 12 + 6 = 38 وصلة (synapse) و14 عصبونًا. بعد الـ pruning تصبح الطبقات 5, 3, 2, 2. اختفى عصبون مخفي واحد من الطبقة الثانية، وآخر من الثالثة، واختفت معظم الحواف المتبقية. أُزيل شيئان مختلفان، والشريحة تسمّيهما بسهمين مختلفين.

A synapse is one weight w_ij, one edge between neuron j of one layer and neuron i of the next. Synapse pruning sets that single entry to zero, and the neurons at both ends survive with one fewer connection. A neuron is a node. Neuron pruning removes the node and therefore every edge incident to it at once: all of its incoming weights and all of its outgoing weights. Nothing about the neuron remains, so nothing that fed it or read from it needs to exist either.

الوصلة (synapse) هي وزن واحد w_ij، أي حافة واحدة بين العصبون j في طبقة والعصبون i في الطبقة التالية. الـ Synapse pruning يجعل هذا العنصر الواحد صفرًا، ويبقى العصبونان على طرفيه مع وصلة أقل بواحدة. أما العصبون فهو عقدة. الـ Neuron pruning يزيل العقدة، وبالتالي يزيل دفعة واحدة كل حافة متصلة بها: كل أوزانها الداخلة وكل أوزانها الخارجة. لا يبقى شيء من العصبون، لذا لا حاجة لوجود أي شيء كان يغذّيه أو يقرأ منه.

The matrix view makes the difference concrete. A linear layer holds its weights in a matrix W of shape [out, in], one row per output neuron and one column per input neuron. Synapse pruning zeroes scattered entries of that matrix, and the matrix keeps its shape; the result is a sparse matrix that must be stored with indices to say where the survivors are. Neuron pruning deletes a whole row of this layer's W(the neuron's inputs) and the matching column of the next layer's W (its outputs); both matrices become smaller dense matrices with no bookkeeping at all. This is the seed of the granularity spectrum in Part 03: fine-grained pruning lives at the synapse end and coarse-grained pruning at the neuron end.

النظر إلى المصفوفات يجعل الفرق ملموسًا. الطبقة الخطية (linear layer) تحفظ أوزانها في مصفوفة W شكلها [out, in]، صف لكل عصبون خرج وعمود لكل عصبون دخل. الـ synapse pruning يصفّر عناصر متفرقة من هذه المصفوفة، وتحتفظ المصفوفة بشكلها؛ والنتيجة مصفوفة متناثرة (sparse) يجب تخزينها مع indices (فهارس) توضّح أين توجد القيم الباقية. أما الـ neuron pruning فيحذف صفًا كاملًا من W في هذه الطبقة (مداخل العصبون) والعمود المقابل من W في الطبقة التالية (مخارجه)؛ فتصبح المصفوفتان مصفوفتين كثيفتين (dense) أصغر دون أي حسابات إضافية لتتبع المواقع. هذه هي بذرة طيف الـ granularity في الجزء 03: الـ fine-grained pruning يقع عند طرف الوصلات، والـ coarse-grained pruning عند طرف العصبونات.

Han et al. describe the effect of synapse pruning on a layer in one line: this pruning converts a dense, fully-connected layer to a sparse layer. They also stress that retraining the surviving weights is critical, because zeroing connections drops accuracy immediately. Part 02 shows that curve and how fine-tuning recovers it.

يصف Han et al. أثر الـ synapse pruning على الطبقة في سطر واحد: هذا الـ pruning يحوّل الطبقة الكثيفة المتصلة بالكامل إلى طبقة متناثرة. ويؤكدون أيضًا أن إعادة تدريب الأوزان الباقية أمر حاسم، لأن تصفير الوصلات يُسقط الدقة فورًا. الجزء 02 يعرض هذا المنحنى وكيف يستعيده الـ fine-tuning.

• Synapse pruning: unit is one weight, neurons survive, the matrix keeps its shape but becomes sparse.Synapse pruning: الوحدة وزن واحد، والعصبونات تبقى، والمصفوفة تحتفظ بشكلها لكنها تصبح متناثرة.
• Neuron pruning: unit is one node, all incident weights go, a row and a column disappear, matrices stay dense.Neuron pruning: الوحدة عقدة واحدة، وكل الأوزان المتصلة بها تُحذف، ويختفي صف وعمود، وتبقى المصفوفات كثيفة.
• Both reduce the number of weights that must be fetched; only the second reduces it in a shape hardware likes.كلاهما يقلّل عدد الأوزان التي يجب جلبها؛ لكن الثاني وحده يقلّله بشكل يناسب العتاد.

Start with a weight vector small enough to see whole: W = [0.8, -0.05, 0.3, -0.01]. It has four nonzero entries. Give yourself a budget of two. One candidate is W_P = [0.8, 0, 0.3, 0], which has exactly two nonzeros. Is it the best candidate? That depends on the training loss it produces, and the pruning formulation on the slide is precisely the question: among all weight vectors with at most two nonzeros, which one makes the loss smallest?

ابدأ بمتجه أوزان صغير بما يكفي لتراه كاملًا: W = [0.8, -0.05, 0.3, -0.01]. فيه أربعة عناصر غير صفرية. ضع لنفسك ميزانية من عنصرين. أحد المرشحين هو W_P = [0.8, 0, 0.3, 0]، وفيه عنصران غير صفريين بالضبط. هل هو أفضل مرشح؟ يعتمد ذلك على قيمة دالة الخسارة (loss) التي ينتجها في التدريب، وpruning formulation (صياغة الـ pruning) في الشريحة هي هذا السؤال بالضبط: من بين كل متجهات الأوزان التي فيها عنصران غير صفريين على الأكثر، أيّها يجعل الخسارة أصغر ما يمكن؟

The left half of the slide figure is ordinary training: pick W to minimize L, with the whole dense network available. The right half adds one line. The search variable becomes W_P, the pruned weights, and a constraint limits how many of its entries may be nonzero. Everything else, the loss, the data, the architecture, is unchanged. Pruning is training with a budget.

النصف الأيسر من شكل الشريحة هو التدريب العادي: اختر W بحيث تقلّل L، والشبكة الكثيفة كلها متاحة. النصف الأيمن يضيف سطرًا واحدًا. يصبح متغير البحث W_P، أي الأوزان بعد الـ pruning، ويحدّ قيدٌ عدد عناصره التي يُسمح أن تكون غير صفرية. كل ما عدا ذلك، أي الخسارة والبيانات والمعمارية، يبقى دون تغيير. الـ pruning هو تدريب بميزانية.

Why the constraint needs heuristicsلماذا يحتاج القيد إلى حلول تقريبية (heuristics)

The L0 norm counts nonzeros, and despite its name it is not a norm at all. A norm must scale with its argument, so that doubling the vector doubles the norm. Doubling our example gives ||2W||_0 = 4 = ||W||_0, not 8. Worse, as a function of the weights it is piecewise constant: nudge any nonzero weight and the count does not change, so the gradient is zero almost everywhere and undefined exactly at zero. Louizos, Welling and Kingma state it plainly: the L0 norm of weights is non-differentiable, so it cannot be incorporated directly as a regularization term. Gradient descent, the only tool that scales to millions of weights, gets no signal from the constraint.

الـ L0 norm يعدّ العناصر غير الصفرية، ورغم اسمه فهو ليس norm أصلًا. يجب أن يتناسب الـ norm مع مدخله، بحيث يتضاعف عند مضاعفة المتجه. لكن مضاعفة مثالنا تعطي ||2W||_0 = 4 = ||W||_0، لا 8. والأسوأ أنه كدالة في الأوزان ثابت على فترات (piecewise constant): حرّك أي وزن غير صفري قليلًا ولن يتغير العدد، لذا فالـ gradient صفر في كل مكان تقريبًا وغير معرّف عند الصفر بالضبط. ويقولها Louizos وWelling وKingma بوضوح: الـ L0 norm للأوزان غير قابل للاشتقاق، لذا لا يمكن إدخاله مباشرة كحد regularization. والـ gradient descent، وهو الأداة الوحيدة التي تتوسع لملايين الأوزان، لا يتلقى أي إشارة من هذا القيد.

The constraint is also combinatorial. Choosing which N of the |W| entries survive is a subset selection. With 16 weights and a budget of 8 there are C(16, 8) = 12,870 masks to compare, each requiring a retrained loss to evaluate. With a million weights and a budget of a hundred thousand the count is astronomically large. Exact search is out of the question.

والقيد أيضًا توافقي (combinatorial). اختيار أي N من بين |W| عنصرًا سيبقى هو مسألة اختيار مجموعة جزئية (subset selection). مع 16 وزنًا وميزانية 8 هناك C(16, 8) = 12,870 من الـ masks (الأقنعة) للمقارنة، وكل منها يتطلب حساب الخسارة بعد إعادة التدريب لتقييمه. ومع مليون وزن وميزانية مئة ألف يصبح العدد ضخمًا بشكل فلكي. البحث الدقيق غير وارد إطلاقًا.

So the field replaces the exact problem by the pipeline of the first concept. A criterion assigns each weight or neuron an importance score, such as its magnitude |w|, and the least important are zeroed; that is a greedy stand-in for the search over masks. A ratio fixes N for each layer; that is the budget. Fine-tuning then re-minimizes L over the surviving entries, which is the only part gradient descent can do. The formulation is exact; everything after it is an approximation, and the quality of the approximation is what the rest of this lecture and the next are about.

لذلك يستبدل المجال المسألة الدقيقة بسلسلة الخطوات في المفهوم الأول. الـ criterion (المعيار) يعطي كل وزن أو عصبون درجة أهمية، مثل مقداره |w|، ويُصفَّر الأقل أهمية؛ وهذا بديل جشع (greedy) للبحث في كل الأقنعة. والـ ratio (النسبة) يحدد N لكل طبقة؛ وهذه هي الميزانية. ثم يعيد الـ fine-tuning تقليل L على العناصر الباقية، وهو الجزء الوحيد الذي يستطيع الـ gradient descent القيام به. الصياغة دقيقة؛ وكل ما بعدها تقريب، وجودة هذا التقريب هي موضوع بقية هذه المحاضرة والمحاضرة التالية.

From N to sparsityمن N إلى الـ sparsity

In the tiny example, keeping 2 of 4 entries is 50% sparsity; the mask visual above keeps 8 of 24, which is 67%. The glossary defines the pruning ratio as the percentage of parameters pruned away, and when every zero comes from pruning the two quantities coincide.

في المثال الصغير، إبقاء 2 من 4 عناصر يعني sparsity بنسبة 50%؛ والشكل التوضيحي للقناع أعلاه يُبقي 8 من 24، أي 67%. يعرّف المسرد (glossary) نسبة الـ pruning بأنها النسبة المئوية للمعاملات التي أُزيلت، وحين يكون كل صفر ناتجًا عن الـ pruning تتطابق الكميتان.

A newborn's cortical neuron carries about 2,500 synapses. By the age of two to four the figure is near 15,000. An adult settles around 7,000. The brain grows to six times its newborn connection count, then removes more than half of that peak. Growth to a peak, then elimination: the curve on the slide is the shape of train-dense-then-prune, drawn by biology decades before anyone pruned a neural network.

يحمل العصبون القشري لدى المولود نحو 2,500 وصلة (synapse). وبين عمر سنتين وأربع سنوات يقترب الرقم من 15,000. ثم يستقر لدى البالغ عند نحو 7,000. ينمو الدماغ حتى يصل إلى ستة أضعاف عدد وصلاته عند الولادة، ثم يزيل أكثر من نصف تلك القمة. نمو حتى قمة، ثم إزالة: المنحنى في الشريحة هو شكل «درّب الشبكة كثيفة ثم قلّمها»، رسمته البيولوجيا قبل عقود من أن يقلّم أحد شبكة عصبية.

This is synaptic pruning, and Han et al. invoke it in the introduction of the paper the slide follows: their method learns the network connectivity in addition to the weights, much as in the mammalian brain, where synapses are created in the first few months of a child's development, followed by gradual pruning of little-used connections, falling to typical adult values. The parallel to the pipeline is exact in shape. Overprovision (train a large dense network), score by use (the criterion), remove the weak connections (prune), and let the remaining ones strengthen (fine-tune).

هذا هو synaptic pruning (التقليم المشبكي)، ويستشهد به Han et al. في مقدمة الورقة التي تتبعها الشريحة: طريقتهم تتعلم بنية اتصال الشبكة إضافة إلى الأوزان، تمامًا كما في دماغ الثدييات، حيث تُنشأ الوصلات في الأشهر الأولى من نمو الطفل، ثم يتبعها تقليم تدريجي للوصلات قليلة الاستخدام، فتنخفض إلى القيم المعتادة لدى البالغين. والتوازي مع سلسلة الخطوات دقيق في شكله. بناء فائض (درّب شبكة كثيفة كبيرة)، ثم تقييم بحسب الاستخدام (المعيار)، ثم إزالة الوصلات الضعيفة (الـ pruning)، ثم ترك الوصلات الباقية تتقوّى (fine-tune).