Lecture 04-1 · Pruning and Sparsity I
المحاضرة 04-1 · التقليم والتناثر (Pruning and Sparsity I)
Magnitude criteria: element, L1, L2, Lp
معايير المقدار (magnitude): العنصر وL1 وL2 وLp
P1 MUSTThe criterion answers "which weights go". Magnitude says: the ones closest to zero. Everything on this page is one rule, |w|, applied to a single weight or summed over a group.
المعيار (criterion) يجيب عن سؤال: أي الأوزان تُحذف؟ ومعيار magnitude يقول: الأقرب إلى الصفر. كل ما في هذه الصفحة قاعدة واحدة، |w|، تُطبَّق على وزن واحد أو تُجمع على مجموعة.
Almost certainly a hand calculation: given a small matrix and a sparsity, produce the pruned matrix element-wise, row-wise with L1, or row-wise with L2. Also a "which weight would you remove" question like slide 27, and the general Lp formula.
في الغالب سؤال حساب يدوي: مصفوفة صغيرة ونسبة sparsity، والمطلوب المصفوفة بعد التقليم على مستوى العنصر (element-wise)، أو على مستوى الصف بـ L1، أو على مستوى الصف بـ L2. وأيضاً سؤال "أي وزن تحذف" مثل الشريحة 27، والصيغة العامة لـ Lp.
What a pruning criterion is, slides 26 and 27
ما هو معيار التقليم، الشريحتان 26 و27
After granularity (the pattern) comes the criterion: a score of importance for each weight or each group. Prune the lowest scores. The principle on slide 27: the less important the removed parameters are, the better the pruned network performs.
بعد granularity (أي النمط) يأتي المعيار (criterion): درجة أهمية لكل وزن أو لكل مجموعة، ثم يُحذف الأقل درجة. والمبدأ في الشريحة 27: كلما كانت المعاملات المحذوفة أقل أهمية، كان أداء الشبكة المقلَّمة أفضل.
slide 27: y = ReLU(10 x0 - 8 x1 + 0.1 x2), W = [10, -8, 0.1] remove ONE weight. which? remove 10 -> y loses 10 x0 huge change remove -8 -> y loses -8 x1 huge change (sign does not save it) remove 0.1 -> y loses 0.1 x2 tiny change <- remove this for inputs of similar scale, the contribution w_i x_i is proportional to |w_i|. smallest |w| = smallest damage.
Element-wise magnitude, slide 28
المقدار على مستوى العنصر (element-wise)، الشريحة 28
For fine-grained pruning, score each weight by its absolute value and zero the smallest ones until the target sparsity is reached. The absolute value matters: -5 is a large weight.
في fine-grained pruning تُعطى كل قيمة درجة تساوي قيمتها المطلقة، ثم تُصفَّر الأصغر حتى تبلغ نسبة sparsity المطلوبة. والقيمة المطلقة مهمة: الوزن -5 وزن كبير.
W = [[ 3, -2],
[ 1, -5]] target 50% sparsity (2 of 4 weights)
element-wise: |W| = [[3, 2], [1, 5]]
sorted: 1, 2, 3, 5 -> zero the two smallest (1 and -2)
W_pruned = [[3, 0],
[0, -5]]
Row-wise L1 and L2, slides 29 and 30
L1 وL2 على مستوى الصف، الشريحتان 29 و30
For structured pruning, the unit removed is a group S (a row, a filter, a channel). Its importance is the norm of the weights in that group, written W(S), "the structural set S of parameters".
في structured pruning تكون الوحدة المحذوفة مجموعة S (صف، أو مرشح، أو قناة). وأهميتها هي norm الأوزان داخل تلك المجموعة، وتُكتب W(S)، أي "المجموعة البنيوية S من المعاملات".
L1 (slide 29)
L1 (الشريحة 29)
Sum of absolute values.
مجموع القيم المطلقة.
L2 (slide 30)
L2 (الشريحة 30)
Square root of the sum of squares.
الجذر التربيعي لمجموع المربعات.
same W, prune ONE row (50%)
L1 row-wise
row 0: |3| + |-2| = 5
row 1: |1| + |-5| = 6 -> prune row 0
L2 row-wise
row 0: sqrt(9 + 4) = sqrt(13) = 3.61
row 1: sqrt(1 + 25) = sqrt(26) = 5.10 -> prune row 0
both: W_pruned = [[0, 0],
[1, -5]]
compare with element-wise [[3, 0], [0, -5]]: the structured
version had to throw away the 3 and keep the 1, because rows
live or die together. that is the accuracy price of structure.
The general Lp norm, slide 31
المعيار العام Lp norm، الشريحة 31
p = 1 gives the L1 sum, p = 2 gives the L2 Euclidean length, and as p grows the norm approaches the largest |wi| in the group (the L∞ norm). Slide 31 cites Wen et al. (structured sparsity learning) for this group view.
قيمة p = 1 تعطي مجموع L1، وp = 2 تعطي الطول الإقليدي L2، وكلما كبرت p اقتربت القيمة من أكبر |wi| في المجموعة (أي L∞ norm). وتستشهد الشريحة 31 بورقة Wen et al. (structured sparsity learning) لهذه النظرة على مستوى المجموعة.
When L1 and L2 disagree
عندما يختلف L1 وL2
The larger p is, the more the norm rewards one dominant weight over many moderate ones. L1 favors a group with many moderate weights; L2 favors a group with one large weight.
كلما كبرت p زادت مكافأة norm لوزن واحد مهيمن على حساب أوزان كثيرة متوسطة. فـ L1 يفضّل المجموعة ذات الأوزان المتوسطة الكثيرة، وL2 يفضّل المجموعة ذات الوزن الواحد الكبير.
| Rowالصف | L1 | L2 |
|---|---|---|
| [3, 3] | 6 | √18 = 4.24 |
| [0, 5] | 5 | 5 |
| Row prunedالصف المحذوف | [0, 5] | [3, 3] |
يقارن الجدول صفّين: [3, 3] له L1 = 6 وL2 = 4.24، و[0, 5] له L1 = 5 وL2 = 5. والذي يجب أن تلاحظه: L1 يحذف [0, 5] بينما L2 يحذف [3, 3]، فالمعياران يختاران صفّين مختلفين.
extra exercise, 3x3 matrix
W = [[ 4, -1, 1 ],
[-2, 2, -2.5],
[ 0.5,-5, 0.2]]
(a) element-wise, prune the 4 smallest |w|
|w| sorted: 0.2, 0.5, 1, 1, 2, 2, 2.5, 4, 5
zero 0.2, 0.5, -1, 1
W = [[ 4, 0, 0 ],
[-2, 2, -2.5],
[ 0,-5, 0 ]] sparsity 4/9 = 44%
(b) row-wise L1, prune 1 row
row 0: 4 + 1 + 1 = 6
row 1: 2 + 2 + 2.5 = 6.5
row 2: 0.5 + 5 + 0.2 = 5.7 <- smallest, prune row 2
(c) row-wise L2, prune 1 row
row 0: sqrt(16 + 1 + 1) = sqrt(18) = 4.243
row 1: sqrt(4 + 4 + 6.25) = sqrt(14.25) = 3.775 <- smallest, prune row 1
row 2: sqrt(0.25 + 25 + 0.04) = sqrt(25.29) = 5.029
L1 kills row 2, L2 kills row 1. row 2 holds the single
biggest weight (-5), which L2 protects and L1 does not.
Always take the absolute value first. Ranking signed values would call -5 the smallest weight in [[3, -2], [1, -5]] and prune it, which removes the most important weight in the matrix. Importance is |w|, never w.
خُذ القيمة المطلقة أولاً دائماً. لو رتّبت القيم بإشاراتها لاعتبرت -5 أصغر وزن في [[3, -2], [1, -5]] وحذفته، فتحذف أهم وزن في المصفوفة. الأهمية هي |w|، وليست w أبداً.
Do not assume L1 and L2 agree. They agree on slides 29 and 30 by coincidence of the numbers. When one row is "one big weight" and another is "many medium weights", compute both and expect different answers.
لا تفترض أن L1 وL2 يتفقان. اتفاقهما في الشريحتين 29 و30 مصادفة في الأرقام. فإذا كان صف "وزناً واحداً كبيراً" وصف آخر "أوزاناً متوسطة كثيرة"، فاحسب الاثنين وتوقّع جوابين مختلفين.
Also: the slide labels the element-wise arrow "L1-norm". For a single weight, L1, L2 and every Lp all equal |w|, so the label is harmless.
وأيضاً: تكتب الشريحة على سهم element-wise عبارة "L1-norm". ولوزن واحد فإن L1 وL2 وكل Lp تساوي |w|، فالتسمية لا تضر.
"Bars, then sum, then root." Absolute value bars first, then sum (raised to p), then the p-th root. For L1 the root is the 1st root, so you stop after the sum.
"Bars, then sum, then root." أي: القيمة المطلقة أولاً، ثم الجمع (بعد الرفع للأس p)، ثم الجذر من الدرجة p. وفي L1 الجذر من الدرجة الأولى، فتتوقف بعد الجمع.
Check yourself
اختبر نفسك
y = ReLU(10 x0 - 8 x1 + 0.1 x2). Under magnitude pruning, which single weight is removed?
y = ReLU(10 x0 - 8 x1 + 0.1 x2). حسب magnitude pruning، أي وزن واحد يُحذف؟
Importance is |w|: 10, 8 and 0.1. The smallest is 0.1, whose removal changes the pre-activation least. Option A ranks signed values. Option D is wrong because ReLU acts on the sum, not on each term, so -8 x1 can still change y.
الأهمية هي |w|: 10 و8 و0.1. والأصغر 0.1، وحذفه يغيّر المجموع قبل التنشيط بأقل قدر. الخيار A يرتّب القيم بإشاراتها. والخيار D خاطئ لأن ReLU تعمل على المجموع لا على كل حد، فـ -8 x1 ما زال يغيّر y.
W = [[3, -2], [1, -5]]. Element-wise magnitude pruning at 50 percent sparsity gives:
W = [[3, -2], [1, -5]]. التقليم على مستوى العنصر بنسبة 50% يعطي:
|W| = [[3, 2], [1, 5]]. Zero the two smallest, 1 and 2, keeping 3 and -5. Option B is the row-wise result. Option D zeros -5 by ranking signed values.
|W| = [[3, 2], [1, 5]]. صفّر الأصغرين، 1 و2، واحتفظ بـ 3 و-5. الخيار B هو نتيجة التقليم على مستوى الصف. والخيار D يصفّر -5 لأنه رتّب القيم بإشاراتها.
A row is [-4, 3]. What are its L1 and L2 importances?
صف قيمه [-4, 3]. ما أهميته حسب L1 وحسب L2؟
L1 = |-4| + |3| = 7. L2 = sqrt(16 + 9) = sqrt(25) = 5. Option A forgets the absolute value. Option B forgets the square root.
L1 = |-4| + |3| = 7. وL2 = sqrt(16 + 9) = sqrt(25) = 5. الخيار A ينسى القيمة المطلقة، والخيار B ينسى الجذر التربيعي.
Two rows, [3, 3] and [0, 5]. One row must be pruned. Which does each criterion prune?
صفّان، [3, 3] و[0, 5]، ويجب حذف أحدهما. أيهما يحذف كل معيار؟
L1: 6 versus 5, so [0, 5] is less important. L2: sqrt(18) = 4.24 versus 5, so [3, 3] is less important. L2 rewards the single dominant weight; L1 rewards many moderate weights.
في L1: 6 مقابل 5، فـ [0, 5] أقل أهمية. وفي L2: sqrt(18) = 4.24 مقابل 5، فـ [3, 3] أقل أهمية. L2 يكافئ الوزن المهيمن الواحد، وL1 يكافئ الأوزان المتوسطة الكثيرة.
As p grows very large, the Lp norm of a group of weights approaches:
كلما كبرت p جداً، تقترب Lp norm لمجموعة أوزان من:
Raising to a large p makes the biggest |wi| dominate the sum, and the p-th root then returns that value: the L∞ norm, max |wi|. Option A is p = 1. Option B is the L0 "norm" (a count).
الرفع إلى أس كبير يجعل أكبر |wi| يهيمن على المجموع، ثم يعيد الجذر من الدرجة p تلك القيمة: L∞ norm، أي max |wi|. الخيار A هو p = 1. والخيار B هو L0 (عدّ).