Lecture 04-2 · Pruning and Sparsity II
المحاضرة 04-2 · التقليم والتناثر (Pruning and Sparsity II)
NetAdapt: latency-budgeted pruning
NetAdapt: تقليم بميزانية زمن استجابة (latency)
P2 SHOULDA rule-based, iterative way to reach a measured latency budget: every round, shave a fixed amount of latency off whichever single layer hurts accuracy least, then repeat until the budget holds.
طريقة تكرارية قائمة على قاعدة للوصول إلى ميزانية latency مقاسة: في كل جولة اقتطع مقداراً ثابتاً من الزمن من الطبقة الواحدة التي يضر تقليمها الدقة أقل ما يمكن، ثم كرّر حتى تتحقق الميزانية.
Write the loop in order (ΔR, one proposal per layer from a lookup table, short-term fine-tune, keep the best, repeat, long-term fine-tune). Explain why a measured lookup table beats counting MACs. Contrast NetAdapt with AMC. Explain why one run yields many models.
اكتب الحلقة بالترتيب (ΔR، ثم اقتراح لكل طبقة من lookup table، ثم short-term fine-tune، ثم احتفظ بالأفضل، ثم كرّر، ثم long-term fine-tune). اشرح لماذا يتفوق جدول البحث المقاس على عدّ MACs. قارن NetAdapt بـ AMC. واشرح لماذا يعطي التشغيل الواحد نماذج كثيرة.
The problem, slides 33 and 34
المشكلة، الشريحتان 33 و34
NetAdapt (Yang et al., ECCV 2018) finds a per-layer pruning ratio (here, a number of filters per layer) that meets a global resource constraint such as latency or energy. The global problem is hard, so it is broken into a chain of easy ones: at iteration i the constraint is not the final budget but the current network's latency minus a step ΔR.
يجد NetAdapt (Yang et al., ECCV 2018) نسبة تقليم لكل طبقة (هنا: عدد filters لكل طبقة) تحقق قيد مورد كلياً مثل latency أو الطاقة. المسألة الكلية صعبة، فتُجزأ إلى سلسلة مسائل سهلة: في التكرار i لا يكون القيد هو الميزانية النهائية، بل زمن الشبكة الحالية ناقص خطوة ΔR.
المسألة الكلية: عظّم Acc(Net) بشرط Res(Net) ≤ Bud. ومسألة كل تكرار: عظّم Acc(Neti) بشرط Res(Neti) ≤ Res(Neti-1) - ΔRi. أي أن الجدار يتقدم كل جولة بمقدار ΔR، والشبكة لا تحتاج إلا إلى العبور من الجدار الجديد.
The slides say ΔR is "manually defined". In the paper it is a schedule, like a learning-rate schedule: for the small MobileNetV1 it starts at 0.5 ms and decays by 0.96 every iteration (0.5, 0.48, 0.461, ...), which took 28 iterations. Larger steps finish in fewer iterations at some cost in accuracy.
تقول الشرائح إن ΔR "يُحدَّد يدوياً". وفي الورقة هو جدول متغير مثل جدول learning rate: في MobileNetV1 الصغير يبدأ بـ 0.5 ms ويتناقص بمعامل 0.96 كل تكرار (0.5, 0.48, 0.461, ...)، واستغرق ذلك 28 تكراراً. الخطوات الأكبر تنتهي في تكرارات أقل مع بعض الخسارة في الدقة.
One iteration, slides 35 to 39
تكرار واحد، الشرائح 35 إلى 39
- Set the constraint for this round: Con = Resi - ΔR.
حدد قيد هذه الجولة: Con = Resi - ΔR.
- For each layer Lk (A to Z on the slide), read from the pre-built lookup table the largest filter count whose summed latency meets Con. Keep the filters with the largest l2 norm.
لكل طبقة Lk (من A إلى Z في الشريحة)، اقرأ من lookup table المبني مسبقاً أكبر عدد من filters يحقق مجموع زمنه القيد Con. واحتفظ بالـ filters ذات أكبر l2 norm.
- Short-term fine-tune that proposal (about 10k iterations) and measure its accuracy on a holdout set.
نفّذ short-term fine-tune لهذا الاقتراح (نحو 10k تكرار) وقِس دقته على مجموعة holdout.
- Keep the proposal with the highest accuracy. It becomes the start of the next iteration.
احتفظ بالاقتراح ذي أعلى دقة. يصبح هو نقطة بداية التكرار التالي.
- Repeat while latency is above the budget. Then long-term fine-tune the final network to convergence.
كرّر ما دام الزمن فوق الميزانية. ثم نفّذ long-term fine-tune للشبكة النهائية حتى التقارب.
الشكل يجمع الشرائح من 35 إلى 39: في كل تكرار K اقتراحاً (واحد لكل طبقة)، يُسعَّر كل منها بجدول البحث ويُرتَّب بدقة short-term fine-tune، ويعود الفائز إلى بداية الحلقة، ثم long-term fine-tune واحد في النهاية.
NetAdapt removes whole filters, not individual weights, because most platforms only get faster when entire filters go. Removing filters in layer k also removes the matching input channels of layer k+1, and the table accounts for that.
يحذف NetAdapt filters كاملة لا أوزاناً منفردة، لأن معظم المنصات لا تتسارع إلا بحذف filters كاملة. وحذف filters من الطبقة k يحذف أيضاً قنوات الدخل المقابلة في الطبقة k+1، والجدول يأخذ ذلك في الحسبان.
Why a lookup table and not MACs
لماذا جدول بحث وليس MACs
There are K proposals per iteration, and timing each one on the phone is slow. Instead, before the loop, each layer is measured on the target device for every shape it might take (input channels, output channels, resolution), and a proposal's latency is the sum of its layers' entries. A table per layer grows linearly with depth; a table of whole networks would grow exponentially.
في كل تكرار K اقتراحاً، وقياس زمن كل واحد على الهاتف بطيء. لذلك تُقاس كل طبقة قبل الحلقة على الجهاز المستهدف لكل شكل قد تأخذه (قنوات الدخل والخرج والدقة المكانية)، ويكون زمن الاقتراح هو مجموع قيم طبقاته في الجدول. جدول لكل طبقة ينمو خطياً مع العمق، أما جدول للشبكات الكاملة فينمو أُسّياً.
MACs are an indirect metric: their relation to latency is non-linear and device dependent (memory traffic, kernel overheads, how well a library tiles a shape). The paper's Table 1 on a Pixel 1 CPU shows it plainly.
MACs مقياس غير مباشر: علاقتها بـ latency غير خطية وتعتمد على الجهاز (حركة الذاكرة، وكلفة تشغيل kernels، ومدى جودة تقسيم المكتبة لشكل الطبقة). والجدول 1 في الورقة على Pixel 1 CPU يوضح ذلك.
| Networkالشبكة | Top-1Top-1 | MACsMACs | Latencyزمن الاستجابة (Latency) |
|---|---|---|---|
| 25% MobileNetV1 (128)25% MobileNetV1 (128) | 45.1% | 13.6 M (100%) | 4.65 ms (100%) |
| MorphNetMorphNet | 46.0% | 15.0 M (110%) | 6.52 ms (140%) |
| NetAdapt guided by MACsNetAdapt موجَّه بـ MACs | 46.3% | 11.0 M (81%) | 6.01 ms (129%) |
في الجدول: نسخة NetAdapt الموجّهة بـ MACs فيها MACs أقل بـ 19% (11.0 / 13.6 = 0.81) ومع ذلك أبطأ بـ 29% (6.01 / 4.65 = 1.29). أي أن تقليل العمل الحسابي لا يضمن تقليل الزمن.
Four layers A to D with 32, 64, 64, 128 filters, measured 10.0 ms, budget 7.0 ms, fixed ΔR = 1.0 ms. Illustrative tables (filters: ms): A 32:3.0 16:1.8; B 64:3.0 32:1.6 8:0.5; C 64:2.5 32:1.5 8:0.5; D 128:1.5 16:0.4.
أربع طبقات A إلى D بعدد filters هو 32, 64, 64, 128، والزمن المقاس 10.0 ms، والميزانية 7.0 ms، وΔR = 1.0 ms ثابت. الجداول توضيحية.
start 3.0 + 3.0 + 2.5 + 1.5 = 10.0 ms acc 71.0 %
iter 1 Con = 10.0 - 1.0 = 9.0 ms
A 16 -> 8.8 ms 61.0 % B 32 -> 8.6 ms 68.2 %
C 32 -> 9.0 ms 69.3 % D 16 -> 8.9 ms 67.3 %
keep C (highest acc, not lowest latency) 9.0 ms
iter 2 Con = 9.0 - 1.0 = 8.0 ms
A 59.2 B 66.4 (7.6 ms) C 8 filters 65.0 D 65.5
keep B 7.6 ms
iter 3 Con = 7.6 - 1.0 = 6.6 ms
A 56.4 B 59.6 C 62.2 D 16 filters 62.7 (6.5 ms)
keep D 6.5 ms <= 7.0, stop
long-term fine-tune: 62.7 % -> 65.2 % (+2.5, inside the 1.8 to 4.5 range)
models produced: 3 (9.0, 7.6, 6.5 ms), one per iteration
The constraint each round is set from the current latency (7.6 - 1.0), not from the budget. And proposal B in iteration 1 reached 8.6 ms but earned nothing for the extra margin: only accuracy ranks proposals that meet Con.
يُحسب قيد كل جولة من الزمن الحالي (7.6 - 1.0) لا من الميزانية. والاقتراح B في التكرار الأول وصل إلى 8.6 ms لكنه لم يكسب شيئاً من الهامش الإضافي: الدقة وحدها ترتّب الاقتراحات التي تحقق Con.
Two fine-tunes, two jobs
عمليتا fine-tuning، ومهمتان
Short-term (per proposal)
قصير المدى (لكل مقترح)
About 10k iterations, K times per iteration. Its only job is to make the K accuracies comparable. Without it, a small pruned net's accuracy falls to nearly zero and the pick is noise.
نحو 10k تكرار، وK مرات في كل تكرار. وظيفته الوحيدة جعل الدقات الـ K قابلة للمقارنة. بدونه تهبط دقة الشبكة الصغيرة المقلّمة إلى ما يقارب الصفر ويصبح الاختيار ضجيجاً.
Long-term (once, at the end)
طويل المدى (مرة واحدة، في النهاية)
Trains the final architecture to convergence and recovers 1.8 to 4.5 points (3.4 on average). This is the accuracy that is reported.
يدرّب المعمارية النهائية حتى التقارب ويستعيد من 1.8 إلى 4.5 نقطة (3.4 في المتوسط). وهذه هي الدقة التي تُنشر.
One run, a whole frontier, slide 40
تشغيل واحد، وحدّ كامل من النماذج (frontier)، الشريحة 40
Every iteration leaves a valid network, so #models = #iterations, and one run traces a series of models with different costs. On the slide's accuracy versus latency chart, NetAdapt is 1.7x faster than the width-multiplier baseline (about 12.1 ms to 7.3 ms) at 0.3 percent higher accuracy, and 1.6x faster than MorphNet (about 7.0 ms to 4.4 ms) at 0.3 percent higher accuracy. Width multipliers thin every layer by the same factor; NetAdapt thins the layers whose latency is cheapest to give up.
كل تكرار يترك شبكة صالحة، إذن #models = #iterations، والتشغيل الواحد يرسم سلسلة نماذج بكلف مختلفة. في رسم الدقة مقابل الزمن في الشريحة، NetAdapt أسرع بـ 1.7x من width multipliers (من نحو 12.1 ms إلى 7.3 ms) بدقة أعلى بـ 0.3%، وأسرع بـ 1.6x من MorphNet (من نحو 7.0 ms إلى 4.4 ms) بدقة أعلى بـ 0.3%. width multipliers ترقّق كل الطبقات بنفس المعامل، أما NetAdapt فيرقّق الطبقات التي يكون التنازل عن زمنها أرخص.
| Aspectالجانب | AMCAMC | NetAdaptNetAdapt |
|---|---|---|
| Who decidesمن يقرر | DDPG agent learns a policyوكيل DDPG يتعلم سياسة (policy) | Greedy rule: best short-term accuracy winsقاعدة جشعة (greedy): الفائز صاحب أفضل دقة قصيرة المدى |
| Per stepفي كل خطوة | Visits every layer once per episodeيمر على كل طبقة مرة واحدة في كل episode | Changes one layer per iteration (all K tried)يغيّر طبقة واحدة في كل تكرار (بعد تجربة كل الـ K) |
| Cost modelنموذج الكلفة | FLOPs, or latency via optional LUTFLOPs، أو زمن الاستجابة عبر LUT اختياري | Measured per-layer latency LUT, summedLUT لزمن استجابة كل طبقة مقاس فعلياً، ويُجمع |
| Fine-tuningFine-tuning | Once, on the final networkمرة واحدة، على الشبكة النهائية | Short-term per proposal, long-term at endقصير المدى لكل مقترح، وطويل المدى في النهاية |
| Outputالمخرج | One model per targetنموذج واحد لكل هدف | A model every iteration: the frontierنموذج في كل تكرار: أي الحدّ الكامل (frontier) |
مقارنة سريعة: في AMC يتعلم وكيل DDPG سياسة ويمر على كل الطبقات في كل episode، والكلفة FLOPs أو latency عبر LUT اختياري، وfine-tuning مرة واحدة، ونموذج واحد لكل هدف. وفي NetAdapt قاعدة جشعة (greedy) تغيّر طبقة واحدة في كل تكرار، وLUT مقاس على الجهاز، وfine-tuning قصير لكل اقتراح وطويل في النهاية، ونموذج في كل تكرار.
The short-term fine-tune only ranks candidates. It is not the final accuracy and it is not optional. The reported accuracy comes after the long-term fine-tune; the short-term number is a lower bound.
short-term fine-tune يرتّب المرشحين فقط. ليس هو الدقة النهائية وليس اختيارياً. الدقة المنشورة تأتي بعد long-term fine-tune، والرقم القصير حد أدنى لها.
The winner is the highest accuracy, not the biggest latency cut. Every proposal already meets Con; extra margin is not rewarded. And only one layer changes per iteration.
الفائز هو الأعلى دقة، لا الأكبر خفضاً للزمن. كل اقتراح يحقق Con أصلاً، والهامش الإضافي لا يُكافأ. وتتغير طبقة واحدة فقط في كل تكرار.
Fewer MACs does not mean faster: 19 percent fewer MACs ran 29 percent slower. That is why the lookup table is measured on the target device.
قلة MACs لا تعني سرعة أكبر: MACs أقل بـ 19% عملت أبطأ بـ 29%. ولهذا يُقاس جدول البحث على الجهاز المستهدف.
"Shave ΔR, try every layer, keep the least painful, repeat, then heal." Short fine-tune to judge, long fine-tune to heal. Measure, do not count.
"اقتطع ΔR، جرّب كل طبقة، احتفظ بالأقل ألماً، كرّر، ثم عالِج." fine-tune قصير للحكم، وطويل للعلاج. قِس ولا تَعُدّ.
Check yourself
اختبر نفسك
In one NetAdapt iteration, which proposal becomes the next network?
في تكرار واحد من NetAdapt، أي اقتراح يصبح الشبكة التالية؟
B. All K proposals meet Con = Res - ΔR, so accuracy alone decides. A is the tempting answer, but extra latency margin is not rewarded. C repeats the MAC fallacy the method exists to avoid.
الجواب B. كل الاقتراحات الـ K تحقق Con = Res - ΔR، فالدقة وحدها تقرر. الخيار A مُغرٍ، لكن الهامش الزمني الإضافي لا يُكافأ. والخيار C يكرر مغالطة MACs التي وُجدت الطريقة لتجنبها.
What is the role of the short-term fine-tune (about 10k iterations)?
ما دور short-term fine-tune (نحو 10k تكرار)؟
C. Without it a small pruned network's accuracy drops near zero and the pick is random. The reported number comes after the long-term fine-tune, which adds 1.8 to 4.5 points. Latency comes from the lookup table, not from fine-tuning.
الجواب C. بدونه تهبط دقة الشبكة الصغيرة المقلّمة إلى ما يقارب الصفر ويصبح الاختيار عشوائياً. والرقم المنشور يأتي بعد long-term fine-tune الذي يضيف من 1.8 إلى 4.5 نقطة. أما الزمن فيأتي من جدول البحث لا من fine-tuning.
Why does NetAdapt use a measured per-layer latency lookup table instead of MACs?
لماذا يستخدم NetAdapt جدول زمن مقاساً لكل طبقة بدلاً من MACs؟
A. Latency depends on memory traffic and implementation, not just arithmetic. B is false. C is false: accuracy is measured after short-term fine-tuning. D is backwards: per-layer tables grow linearly, that is why they are used.
الجواب A. الزمن يعتمد على حركة الذاكرة والتنفيذ لا على الحساب وحده. الخيار B خاطئ. وC خاطئ: الدقة تُقاس بعد short-term fine-tune. وD معكوس: جداول الطبقات تنمو خطياً، ولهذا تُستخدم.
A NetAdapt run takes 28 iterations to reach its budget. How many usable models does it produce along the way?
تشغيل NetAdapt احتاج 28 تكراراً للوصول إلى الميزانية. كم نموذجاً صالحاً ينتج في الطريق؟
D. Slide 40: #models = #iterations, giving the accuracy versus latency frontier. C counts proposals, but only the winner of each iteration is kept. A describes AMC, which gives one model per target.
الجواب D. الشريحة 40: #models = #iterations، فيُرسم منحنى الدقة مقابل الزمن. الخيار C يعدّ الاقتراحات، لكن الفائز وحده في كل تكرار يُحتفظ به. والخيار A يصف AMC الذي يعطي نموذجاً واحداً لكل هدف.