Lecture 05-1 · Quantization I

المحاضرة 05-1 · التكميم (Quantization I)

K-means weight quantization and fine-tuning

تكميم الأوزان بـ K-means والضبط الدقيق (fine-tuning)

Slides 26–32الشرائح 26–32 P1 MUST

Cluster the weights into 2N groups, store each weight as an N-bit cluster index, and keep one float centroid per cluster in a codebook. Then fine-tune the centroids by summing the gradients of every weight in each cluster.

جمّع الأوزان في 2N مجموعة، وخزّن كل وزن كفهرس مجموعة من N bit، واحتفظ بـ centroid عشري واحد لكل مجموعة في codebook. ثم اضبط الـ centroids بـ fine-tuning عبر جمع تدرّجات (gradients) كل الأوزان في كل مجموعة.

High exam riskاحتمال عالٍ في الامتحان

Expect to compute the storage of indices plus codebook and the compression ratio (the 3.2x), to apply the general 32/N rule, and to do one centroid update from a grouped gradient. Also expect a reasoning question on why K-means saves storage but not compute.

توقّع أن تحسب تخزين الفهارس مع الـ codebook ونسبة الضغط (3.2x)، وأن تطبّق القاعدة العامة 32/N، وأن تنفّذ تحديثاً واحداً لـ centroid من تدرّج مجمَّع. وتوقّع أيضاً سؤالاً تعليلياً: لماذا يوفّر K-means التخزين ولا يوفّر الحساب؟

Step 1: cluster, index, codebook

الخطوة 1: التجميع، والفهرسة، والـ codebook

With 2-bit quantization there are 22 = 4 clusters. Running K-means on the 16 weights (Deep Compression, Han et al., ICLR 2016) gives four centroids: index 3 = 2.00, index 2 = 1.50, index 1 = 0.00, index 0 = -1.00. Every weight is replaced by the index of its cluster; the centroids form the codebook. Decoding (index to centroid) gives the reconstructed weights, and original minus reconstructed is the quantization error.

مع تكميم 2-bit يوجد 22 = 4 مجموعات. تشغيل K-means على الأوزان الـ 16 (Deep Compression, Han et al., ICLR 2016) يعطي أربعة centroids: الفهرس 3 = 2.00، والفهرس 2 = 1.50، والفهرس 1 = 0.00، والفهرس 0 = -1.00. يُستبدل كل وزن بفهرس مجموعته، وتشكّل الـ centroids الـ codebook. فك الترميز (من الفهرس إلى الـ centroid) يعطي الأوزان المعاد بناؤها (reconstructed weights)، والأصل ناقص المعاد بناؤه هو خطأ التكميم.

WEIGHTS (FP32) 2.09 -0.98 1.48 0.09 0.05 -0.14 -1.08 2.12 -0.91 1.92 0 -1.03 1.87 0 1.53 1.49 cluster CLUSTER INDEX (2-BIT) 3 0 2 1 1 1 0 3 0 3 1 0 3 1 2 2 CODEBOOK 3: 2.00 2: 1.50 1: 0.00 0: -1.00 decode RECONSTRUCTED 2.00 -1.00 1.50 0.00 0.00 0.00 -1.00 2.00 -1.00 2.00 0.00 -1.00 2.00 0.00 1.50 1.50 ERROR = W - RECON 0.09 0.02 -0.02 0.09 0.05 -0.14 -0.08 0.12 0.09 -0.08 0 -0.03 -0.13 0 0.03 -0.01 512 bit = 64 B 2 x 16 = 32 bit = 4 B 4 x 32 = 16 B 4 B + 16 B = 20 B, so 64 / 20 = 3.2x smaller
Slide 27. Colours mark the cluster: blue 2.00 (index 3), violet 1.50 (index 2), green 0.00 (index 1), red -1.00 (index 0). The largest error magnitude is 0.14 (the weight -0.14 rounded to 0.00).
الشريحة 27. الألوان تحدد المجموعة (cluster): الأزرق 2.00 (الفهرس 3)، والبنفسجي 1.50 (الفهرس 2)، والأخضر 0.00 (الفهرس 1)، والأحمر -1.00 (الفهرس 0). أكبر مقدار للخطأ هو 0.14 (الوزن -0.14 الذي قُرّب إلى 0.00).

The centroids are not arbitrary: each one is the mean of its members, which is what K-means converges to. You can check this on the slide's numbers.

الـ centroids ليست عشوائية: كل واحد منها هو متوسط أعضاء مجموعته، وهذا ما يتقارب إليه K-means. يمكنك التحقق من ذلك بأرقام الشريحة.

IndexالفهرسMembersالأعضاءCountالعددSumالمجموعMean = centroidالمتوسط = الـ centroid
32.09, 2.12, 1.92, 1.8748.002.00
21.48, 1.53, 1.4934.501.50
10.09, 0.05, -0.14, 0, 050.000.00
0-0.98, -1.08, -0.91, -1.034-4.00-1.00

يعرض الجدول أعضاء كل مجموعة ومجموعها ومتوسطها. المجموع الكلي للأعداد هو 4 + 3 + 5 + 4 = 16 وزناً، وكل متوسط يطابق الـ centroid في الشريحة تماماً.

Step 2: the storage arithmetic

الخطوة 2: حساب التخزين

Slide 27's bottom half is the most testable part of the lecture. Count bits for the indices and for the codebook separately, then add.

النصف السفلي من الشريحة 27 هو الجزء الأكثر قابلية للاختبار في المحاضرة. احسب بتات الفهارس وبتات الـ codebook كلاً على حدة، ثم اجمعهما.

Workedمثال محلول 
Original   32 bit x 16 weights           = 512 bit = 64 B

K-means    indices   2 bit x 16          =  32 bit =  4 B
           codebook 32 bit x 4 centroids = 128 bit = 16 B
           total                                     = 20 B

ratio      64 B / 20 B = 3.2x smaller

General: N-bit, M weights, M >> 2^N
           original  32 x M  = 32M bit
           indices    N x M  =  NM bit
           codebook  32 x 2^N = 2^(N+5) bit   (negligible when M >> 2^N)
           ratio    ~ 32M / NM = 32/N

           N = 2  -> 16x       N = 4 -> 8x       N = 8 -> 4x

The toy matrix gets only 3.2x, not the 16x that 32/2 promises, because 16 bytes of its 20 are codebook. The codebook is fixed size, so it vanishes only when the tensor is large.

المصفوفة الصغيرة تحصل على 3.2x فقط، لا على 16x التي تعد بها 32/2، لأن 16 بايت من أصل 20 هي codebook. حجم الـ codebook ثابت، فلا يصبح مهملاً إلا عندما تكون المصفوفة كبيرة.

ratio = 32 · MN · M + 32 · 2N   →   32 / N when M ≫ 2N

Take the extreme the other way: 16 weights at 4 bits. Indices cost 4 x 16 = 64 bits, but the codebook has 24 = 16 entries x 32 bits = 512 bits. Total 576 bits, which is larger than the original 512. With as many centroids as weights, the codebook just copies the weights.

خذ الطرف المعاكس: 16 وزناً بـ 4 bit. الفهارس تكلّف 4 x 16 = 64 bit، لكن الـ codebook فيه 24 = 16 مدخلاً x 32 bit = 512 bit. المجموع 576 bit، وهو أكبر من الأصل 512. عندما يكون عدد الـ centroids مساوياً لعدد الأوزان، فإن الـ codebook ينسخ الأوزان فقط.

Step 3: fine-tuning the centroids

الخطوة 3: الضبط الدقيق للـ centroids

After clustering, accuracy drops a little, so the network is retrained. The indices are frozen; only the centroids are trained. Because every weight in a cluster is the centroid (wi = ck), the chain rule makes the centroid's gradient the sum of the gradients of its member weights. Slides 28 and 29 do this in three moves: group by cluster index, reduce (sum), then subtract learning rate times the sum.

بعد التجميع تنخفض الدقة قليلاً، فتُعاد تدريب الشبكة. الفهارس تُجمَّد، والـ centroids وحدها تُدرَّب. ولأن كل وزن في المجموعة هو الـ centroid نفسه (wi = ck)، فإن قاعدة السلسلة (chain rule) تجعل تدرّج الـ centroid هو مجموع تدرّجات أوزانه. الشريحتان 28 و29 تفعلان ذلك بثلاث خطوات: group by حسب فهرس المجموعة، ثم reduce (جمع)، ثم طرح معدل التعلّم مضروباً في المجموع.

∂L∂ck = Σi : idx(i) = k ∂L∂wi      ck ← ck - lr · ∂L∂ck
GRADIENT dL/dW -0.03 -0.01 0.03 0.02 -0.01 0.01 -0.02 0.12 -0.01 0.02 0.04 0.01 -0.07 -0.02 0.01 -0.02 group by GROUPED BY CLUSTER INDEX -0.03 0.12 0.02 -0.07 0.03 0.01 -0.02 0.02 -0.01 0.01 0.04 -0.02 -0.01 -0.02 -0.01 0.01 sum SUM 3: 0.04 2: 0.02 1: 0.04 0: -0.03 c - lr x sum FINE-TUNED 3: 1.96 2: 1.48 1: -0.04 0: -0.97 2.00 - 0.04 1.50 - 0.02 0.00 - 0.04 -1.00 + 0.03
Slide 29. Group the 16 gradients by cluster (4, 3, 5 and 4 values), sum each group, and subtract from the centroid. The slide's fine-tuned centroids come out exactly as c - sum, i.e. the picture uses an effective lr of 1.
الشريحة 29. جمّع التدرجات (gradients) الـ 16 حسب المجموعة (4 و3 و5 و4 قيم)، واجمع كل مجموعة، ثم اطرح المجموع من الـ centroid. الـ centroids المضبوطة في الشريحة تخرج بالضبط c - sum، أي أن الرسم يستخدم معدل تعلم فعلياً lr = 1.
Workedمثال محلول 
Cluster 3 (centroid 2.00): grads -0.03, 0.12, 0.02, -0.07
          sum = -0.03 + 0.12 + 0.02 - 0.07 = 0.04
          new = 2.00 - 0.04 = 1.96

Cluster 2 (1.50):  0.03 + 0.01 - 0.02               =  0.02  -> 1.48
Cluster 1 (0.00):  0.02 - 0.01 + 0.01 + 0.04 - 0.02 =  0.04  -> -0.04
Cluster 0 (-1.00): -0.01 - 0.02 - 0.01 + 0.01       = -0.03  -> -0.97

With a real learning rate, e.g. lr = 0.5 on cluster 3:
          new = 2.00 - 0.5 x 0.04 = 1.98

Every one of the four weights tagged 3 now decodes to 1.96. One update moves all of them together, which is why the indices never have to change.

كل الأوزان الأربعة التي تحمل الفهرس 3 تُفك الآن إلى 1.96. تحديث واحد يحرّكها جميعاً معاً، ولهذا لا تحتاج الفهارس إلى التغيير أبداً.

What it buys: AlexNet on ImageNet

ما الذي نكسبه: AlexNet على ImageNet

Slides 30 to 32 plot accuracy loss against model size ratio after compression (smaller x is more compression). Quantization only stays within about 0.5 percent loss down to about 8 percent of the original size, then collapses steeply just below about 7 percent. Pruning only degrades more gradually, losing about 1 percent near 7 percent of the size and about 4 percent near 4.5 percent. Pruning + quantization keeps essentially zero loss down to about 3 to 4 percent of the original size and only falls off a cliff just under 3 percent.

ترسم الشرائح من 30 إلى 32 خسارة الدقة مقابل نسبة حجم النموذج بعد الضغط (كلما صغرت قيمة المحور الأفقي زاد الضغط). الـ quantization only يبقى ضمن خسارة نحو 0.5% حتى نحو 8% من الحجم الأصلي، ثم ينهار بحدة تحت نحو 7%. الـ pruning only يتدهور تدريجياً أكثر، فيخسر نحو 1% قرب 7% من الحجم، ونحو 4% قرب 4.5%. أما pruning + quantization فيحافظ على خسارة شبه صفرية حتى نحو 3% إلى 4% من الحجم الأصلي، ولا يسقط إلا تحت 3% بقليل.

The lesson: pruning removes weights, quantization removes bits per weight, and the two savings are largely independent, so combining them reaches a size neither can reach alone.

الدرس: الـ pruning يزيل أوزاناً، والـ quantization يزيل بتات من كل وزن، والتوفيران مستقلان إلى حد كبير، فالجمع بينهما يصل إلى حجم لا يصل إليه أي منهما وحده.

Trapفخ

Do not forget the codebook. 2 bits x 16 = 4 B is not the answer; the 16 B codebook brings it to 20 B, and the ratio is 3.2x, not 16x. For small tensors or many bits, the codebook can even make the "compressed" tensor bigger.

لا تنسَ الـ codebook. 2 bit x 16 = 4 B ليس هو الجواب، فالـ codebook ذو 16 B يرفعه إلى 20 B، والنسبة 3.2x لا 16x. وفي المصفوفات الصغيرة أو مع بتات كثيرة قد يجعل الـ codebook المصفوفة "المضغوطة" أكبر من الأصل.

Sum, do not average. The centroid gradient is the sum over the cluster (slide 29's "reduce"). Averaging would give 0.01 for cluster 3, not 0.04, and a centroid of 1.99 instead of 1.96. Only average if a question explicitly says so.

اجمع، لا تأخذ المتوسط. تدرّج الـ centroid هو المجموع على المجموعة (خطوة reduce في الشريحة 29). المتوسط يعطي 0.01 للمجموعة 3 بدلاً من 0.04، وcentroid قيمته 1.99 بدلاً من 1.96. لا تأخذ المتوسط إلا إذا نصّ السؤال على ذلك.

Indices bits = N, not 2N. 4 clusters need 2-bit indices; 2N is the number of codebook entries.

بتات الفهرس = N لا 2N. أربع مجموعات تحتاج فهارس من 2 bit، و2N هو عدد مدخلات الـ codebook.

Memory hookمفتاح للحفظ

N bits of index, 2N floats of codebook, 32/N times smaller. Training: group, sum, subtract.

N بت للفهرس، و2N عدداً عشرياً للـ codebook، وأصغر بمقدار 32/N. التدريب: جمّع، اجمع، اطرح.

Check yourself

اختبر نفسك

A 4 x 4 FP32 weight matrix is K-means quantized to 2 bits. Including the codebook, what is the compression ratio?

مصفوفة أوزان 4 x 4 بصيغة FP32 كُمّمت بـ K-means إلى 2 bit. مع احتساب الـ codebook، ما نسبة الضغط؟

C. Original 64 B; indices 2 x 16 = 32 bit = 4 B; codebook 4 x 32 = 128 bit = 16 B; total 20 B; 64 / 20 = 3.2. A is 32/N, which ignores the codebook and only holds for M ≫ 2N. D is 64 / 16, counting the codebook alone.

C. الأصل 64 B، والفهارس 2 x 16 = 32 bit = 4 B، والـ codebook 4 x 32 = 128 bit = 16 B، فالمجموع 20 B، و64 / 20 = 3.2. الخيار A هو 32/N، وهو يتجاهل الـ codebook ولا يصح إلا عندما M ≫ 2N. والخيار D هو 64 / 16، أي أنه يحسب الـ codebook وحده.

A layer has 1 million weights and is K-means quantized to 4 bits. Approximately how much smaller is it than FP32?

طبقة فيها مليون وزن كُمّمت بـ K-means إلى 4 bit. تقريباً كم مرة أصبحت أصغر من FP32؟

B. M = 106 ≫ 24 = 16, so the 16 x 32 = 512-bit codebook is negligible and the ratio is 32/N = 32/4 = 8. A is the ratio for 8 bits. C confuses the number of clusters (16) with the ratio.

B. M = 106 ≫ 24 = 16، لذلك فالـ codebook بحجم 16 x 32 = 512 bit مهمل، والنسبة 32/N = 32/4 = 8. الخيار A هو النسبة عند 8 bit. والخيار C يخلط بين عدد المجموعات (16) والنسبة.

A cluster has centroid 1.50 and its three member weights have gradients 0.03, 0.01 and -0.02. With lr = 1 (as on slide 29), what is the fine-tuned centroid?

مجموعة لها centroid قيمته 1.50، وتدرّجات أوزانها الثلاثة 0.03 و0.01 و-0.02. مع lr = 1 (كما في الشريحة 29)، ما قيمة الـ centroid بعد الضبط؟

A. Sum = 0.03 + 0.01 - 0.02 = 0.02, and 1.50 - 0.02 = 1.48. B adds the gradient instead of descending. C uses the average (0.0067). D sums absolute values (0.06).

A. المجموع 0.03 + 0.01 - 0.02 = 0.02، و1.50 - 0.02 = 1.48. الخيار B يضيف التدرج بدلاً من النزول عكسه. والخيار C يستخدم المتوسط (0.0067). والخيار D يجمع القيم المطلقة (0.06).

Why does K-means weight quantization not speed up the arithmetic of a layer?

لماذا لا يسرّع K-means weight quantization حساب الطبقة؟

D. Slide 42: weights are decompressed with a lookup table at runtime, and all computation and memory access stay floating point. The MAC count is unchanged (B is false), indices are N bits (A is false), and the codebook is fixed after fine-tuning (C is false).

D. الشريحة 42: تُفك الأوزان بجدول بحث (lookup table) وقت التشغيل، ويبقى كل الحساب والوصول إلى الذاكرة عشرياً. عدد الـ MAC لا يتغير (B خطأ)، والفهارس من N bit (A خطأ)، والـ codebook ثابت بعد الضبط الدقيق (C خطأ).

On slide 32 (AlexNet, ImageNet), which method keeps essentially zero accuracy loss at the smallest model size?

في الشريحة 32 (AlexNet على ImageNet)، أي طريقة تحافظ على خسارة دقة شبه صفرية عند أصغر حجم للنموذج؟

C. The combined curve stays flat to roughly 3 to 4 percent of the original size. Quantization only collapses below about 7 percent, and pruning only already loses about 1 percent near 7 percent and about 4 percent near 4.5 percent.

C. المنحنى المدمج يبقى مستوياً حتى نحو 3 إلى 4 بالمئة من الحجم الأصلي. أما التكميم وحده فينهار تحت نحو 7 بالمئة، والتقليم وحده يخسر نحو 1 بالمئة قرب 7 بالمئة، ونحو 4 بالمئة قرب 4.5 بالمئة.