K-means weight quantization: codebook, storage and centroid fine-tuningتكميم الأوزان بـK-means: دفتر الترميز والتخزين وضبط المراكز

Look at the 16 weights of the example layer. Four of them are 2.09, 2.12, 1.92 and 1.87. Four more are -0.98, -1.08, -0.91 and -1.03. Three hover around 1.5, and five sit near zero. The matrix holds sixteen numbers, but really only four ideas.

انظر إلى الأوزان الـ 16 في طبقة المثال. أربعة منها هي 2.09 و 2.12 و 1.92 و 1.87. وأربعة أخرى هي -0.98 و -1.08 و -0.91 و -1.03. ثلاثة تحوم حول 1.5، وخمسة تقع قرب الصفر. المصفوفة تحمل ستة عشر رقمًا، لكنها في الحقيقة تحمل أربع أفكار فقط.

From an observation to an algorithmمن ملاحظة إلى خوارزمية

Weight sharing makes that observation official: all weights in one group are replaced by one shared value. The question is how to choose the groups and the values. K-means-based weight quantization answers with one-dimensional K-means. You fix the number of clusters $k$ in advance, then minimise the within-cluster sum of squares, the total squared distance from each weight to the value that will replace it.

Weight sharing (مشاركة الأوزان) تجعل هذه الملاحظة رسمية: كل الأوزان في مجموعة واحدة تُستبدل بقيمة مشتركة واحدة. السؤال هو كيف نختار المجموعات والقيم. K-means-based weight quantization تجيب باستخدام K-means أحادي البعد. تحدد عدد المجموعات $k$ مسبقًا، ثم تقلّل مجموع المربعات داخل المجموعات (within-cluster sum of squares)، أي مجموع مربعات المسافات من كل وزن إلى القيمة التي ستحل محله.

The standard way to minimise it is Lloyd's algorithm. Start with $k$ guesses for the shared values. Then repeat two steps until nothing changes. First, assign every weight to its nearest guess. Second, move every guess to the mean of the weights assigned to it. Neither step can raise the objective, so the loop always stops, though possibly at a local rather than global minimum, which is why the starting guesses matter.

الطريقة المعيارية لتقليله هي خوارزمية Lloyd. ابدأ بـ $k$ تخمينات للقيم المشتركة. ثم كرّر خطوتين حتى لا يتغير شيء. أولًا، أسند كل وزن إلى أقرب تخمين. ثانيًا، انقل كل تخمين إلى متوسط الأوزان المسندة إليه. لا يمكن لأي من الخطوتين أن ترفع قيمة الهدف، لذلك تتوقف الحلقة دائمًا، لكن ربما عند قيمة صغرى محلية (local minimum) لا عامة (global)، ولهذا تهمّ التخمينات الابتدائية.

The representative value of a cluster is its Centroid. Because the second Lloyd step sets it to the mean, you can check the slide by hand. Every centroid on slide 27 is the exact mean of its members:

القيمة الممثِّلة للمجموعة هي centroid (المركز). ولأن خطوة Lloyd الثانية تضعه عند المتوسط، يمكنك التحقق من الشريحة يدويًا. كل مركز في الشريحة 27 هو المتوسط الدقيق لأعضائه:

A useful consequence: since a centroid is a mean, the errors inside each cluster cancel. In the blue cluster, 0.09 + 0.12 - 0.08 - 0.13 = 0. That is a quick consistency check in an exam when you are handed a clustering and asked whether it is a converged K-means solution.

نتيجة مفيدة: بما أن المركز متوسط، فإن الأخطاء داخل كل مجموعة يلغي بعضها بعضًا. في المجموعة الزرقاء، 0.09 + 0.12 - 0.08 - 0.13 = 0. هذا فحص سريع للاتساق في الاختبار عندما تُعطى تجميعًا ويُسأل هل هو حل K-means متقارب (converged).

Where the starting guesses come fromمن أين تأتي التخمينات الابتدائية

Han et al. compared three initialisations: random (Forgy), density-based and linear. Linear spaces the starting centroids evenly between the smallest and largest weight. It won, because large-magnitude weights are rare but important, and the other two methods crowd the centroids into the dense middle of the distribution, leaving the few large weights badly represented. For the example, linear initialisation between -1.08 and 2.12 converges in one update to exactly the slide's four centroids.

قارن Han et al. بين ثلاث طرق للتهيئة (initialisation): العشوائية (Forgy)، والمعتمدة على الكثافة (density-based)، والخطية (linear). الطريقة الخطية توزّع المراكز الابتدائية بالتساوي بين أصغر وزن وأكبر وزن. وقد فازت، لأن الأوزان الكبيرة في القيمة المطلقة نادرة لكنها مهمة، والطريقتان الأخريان تحشران المراكز في الوسط الكثيف من التوزيع، فتبقى الأوزان الكبيرة القليلة ممثَّلة بشكل سيئ. في المثال، التهيئة الخطية بين -1.08 و 2.12 تتقارب في تحديث واحد إلى المراكز الأربعة نفسها الموجودة في الشريحة بالضبط.

Once the clustering is fixed, the original matrix can be thrown away. In its place you store two things: a 4 × 4 matrix of small integers saying which cluster each weight belongs to, and a list of four floats saying what each cluster's value is.

بمجرد تثبيت التجميع يمكن التخلص من المصفوفة الأصلية. وتخزّن مكانها شيئين: مصفوفة 4 × 4 من أعداد صحيحة صغيرة تقول إلى أي مجموعة ينتمي كل وزن، وقائمة من أربعة أعداد عشرية تقول ما قيمة كل مجموعة.

Two tables replace oneجدولان بدلًا من جدول واحد

The integer matrix is the map of Cluster index values. With $k = 4$ clusters an index needs $\log_2 4 = 2$ bits, so slide 27 labels it 2-bit int. Its first row is 3, 0, 2, 1. The list of floats is the Codebook: 3: 2.00, 2: 1.50, 1: 0.00, 0: -1.00. Notice the indexes are numbered in increasing centroid order, so index 0 is the most negative value.

مصفوفة الأعداد الصحيحة هي خريطة قيم cluster index (فهرس المجموعة). مع $k = 4$ مجموعات يحتاج الفهرس إلى $\log_2 4 = 2$ بت، ولذلك تسمّيها الشريحة 27 باسم 2-bit int. صفها الأول هو 3, 0, 2, 1. أما قائمة الأعداد العشرية فهي codebook (دفتر الرموز): 3: 2.00 و 2: 1.50 و 1: 0.00 و 0: -1.00. لاحظ أن الفهارس مرقّمة بترتيب تصاعدي للمراكز، فالفهرس 0 هو القيمة الأكثر سالبية.

To use the layer you rebuild each weight by looking up its index in the codebook. Index 3 becomes 2.00, index 0 becomes -1.00, and so on. The rebuilt matrix is:

لاستخدام الطبقة تعيد بناء كل وزن بالبحث عن فهرسه في دفتر الرموز. الفهرس 3 يصبح 2.00، والفهرس 0 يصبح -1.00، وهكذا. المصفوفة المعاد بناؤها هي:

The rebuilt weights are still 32-bit floats, which is why slide 27 labels them that way. K-means saves storage, not arithmetic: at inference the indexes are decoded through the codebook and the layer runs in floating point, the Decode (lookup) at inference step a later part covers.

الأوزان المعاد بناؤها ما زالت أعدادًا عشرية بحجم 32-bit، ولهذا تسمّيها الشريحة 27 بهذا الاسم. K-means يوفّر في التخزين لا في الحساب: عند الاستدلال (inference) تُفك الفهارس عبر دفتر الرموز وتعمل الطبقة بالفاصلة العائمة، وهي خطوة decode (lookup) التي يشرحها جزء لاحق.

What is lost: the quantization errorما الذي نخسره: خطأ التكميم

Subtracting gives the Quantization error at each position, original minus reconstructed:

الطرح يعطي quantization error (خطأ التكميم) عند كل موضع، أي الأصلي ناقص المعاد بناؤه:

The largest error in magnitude is -0.14, the weight -0.14 forced to 0.00. These small errors are what the network pays for compression, and what the fine-tuning in the next two concepts tries to win back.

أكبر خطأ في القيمة المطلقة هو -0.14، وهو الوزن -0.14 الذي أُجبر على أن يصبح 0.00. هذه الأخطاء الصغيرة هي الثمن الذي تدفعه الشبكة مقابل الضغط، وهي ما يحاول الـ fine-tuning في المفهومين التاليين استعادته.

The storage billفاتورة التخزين

Count bits. The original layer is 16 floats of 32 bits: 32 × 16 = 512 bit = 64 B. The quantized layer stores 16 indexes of 2 bits, 32 bit = 4 B, plus 4 centroids of 32 bits, 128 bit = 16 B. Total 20 B, so the layer is 64 / 20 = 3.2× smaller. That is the Compression ratio on the slide.

عُدّ البتات. الطبقة الأصلية هي 16 عددًا عشريًا كل منها 32 بت: 32 × 16 = 512 bit = 64 B. الطبقة المكمَّمة تخزّن 16 فهرسًا كل منها 2 بت، أي 32 bit = 4 B، زائد 4 مراكز كل منها 32 بت، أي 128 bit = 16 B. المجموع 20 B، فالطبقة أصغر بمقدار 64 / 20 = 3.2×. هذه هي compression ratio (نسبة الضغط) في الشريحة.

Now generalise. Take $N$-bit indexes, so $k = 2^N$ clusters, and $M$ parameters. The original costs $32M$ bits. The indexes cost $NM$ bits and the codebook $32 \cdot 2^N = 2^{N+5}$ bits.

الآن عمّم. خذ فهارس من $N$ بت، أي $k = 2^N$ مجموعة، و $M$ معاملًا. الأصل يكلّف $32M$ بت. الفهارس تكلّف $NM$ بت، ودفتر الرموز $32 \cdot 2^N = 2^{N+5}$ بت.

The codebook term does not grow with $M$. In a real layer with M = 1,000,000 and N = 4, the codebook is 16 × 32 = 512 bit against 4,000,000 bit of indexes, about 0.013% of the total. That is why the slide crosses it out.

حدّ دفتر الرموز لا يكبر مع $M$. في طبقة حقيقية فيها M = 1,000,000 و N = 4، يكون دفتر الرموز 16 × 32 = 512 bit مقابل 4,000,000 bit من الفهارس، أي نحو 0.013% من المجموع. ولهذا تشطبه الشريحة.

The 4 × 4 example misses 32/2 = 16× by a wide margin because its assumption $M \gg 2^N$ fails: with only 16 weights, the 16 B codebook is 80% of the 20 B total. Push it further and the method backfires. At N = 4 on these 16 weights, the indexes cost 64 bit but the codebook costs 512 bit, 72 B in all, larger than the 64 B original.

مثال 4 × 4 يبتعد كثيرًا عن 32/2 = 16× لأن افتراضه $M \gg 2^N$ لا يتحقق: مع 16 وزنًا فقط، يمثّل دفتر الرموز البالغ 16 B نسبة 80% من المجموع 20 B. وإذا ذهبت أبعد تنقلب الطريقة ضدك. عند N = 4 على هذه الأوزان الـ 16، تكلّف الفهارس 64 bit لكن دفتر الرموز يكلّف 512 bit، أي 72 B إجمالًا، وهذا أكبر من الأصل البالغ 64 B.

The simulator runs K-means on the slide's weights. At k = 4 it reproduces slide 27 exactly. Switch to k = 2: the ratio rises to 6.4× but the errors grow to about 0.6. Switch to k = 8: the errors barely improve, three centroids own no weight at all, and the ratio falls to 1.68× because the codebook doubles.

المحاكي يشغّل K-means على أوزان الشريحة. عند k = 4 يعيد إنتاج الشريحة 27 بالضبط. انتقل إلى k = 2: ترتفع النسبة إلى 6.4× لكن الأخطاء تكبر إلى نحو 0.6. انتقل إلى k = 8: الأخطاء بالكاد تتحسن، وثلاثة مراكز لا يملك أي منها أي وزن، وتنخفض النسبة إلى 1.68× لأن دفتر الرموز يتضاعف.

Quantizing a trained network nudges every weight by its quantization error, and the accuracy usually drops a little. The fix is to keep training. But what exactly is there to train, now that the weights no longer exist as sixteen independent numbers?

تكميم شبكة مدرَّبة يزيح كل وزن بمقدار خطأ التكميم الخاص به، وعادة تنخفض الدقة قليلًا. والحل هو مواصلة التدريب. لكن ما الذي يمكن تدريبه بالضبط، بعد أن لم تعد الأوزان موجودة كستة عشر رقمًا مستقلًا؟

Only the codebook is free to moveدفتر الرموز وحده حرّ في الحركة

After quantization the layer is described by the index map and the codebook. The index map is a grid of integers: there is no meaningful small step from index 2 to index 2.01, so it has no gradient. The four centroids are ordinary floats, and the forward pass uses them through $\hat W_{ij} = C_{I_{ij}}$. So Centroid fine-tuning trains the codebook and keeps every index exactly where K-means put it. The Deep Compression paper describes this as a level of indirection in both the forward and backward pass.

بعد التكميم توصف الطبقة بخريطة الفهارس ودفتر الرموز. خريطة الفهارس شبكة من الأعداد الصحيحة: لا توجد خطوة صغيرة ذات معنى من الفهرس 2 إلى الفهرس 2.01، لذلك ليس لها gradient. أما المراكز الأربعة فهي أعداد عشرية عادية، والتمرير الأمامي (forward pass) يستخدمها عبر $\hat W_{ij} = C_{I_{ij}}$. ولذلك فإن centroid fine-tuning يدرّب دفتر الرموز ويُبقي كل فهرس بالضبط حيث وضعه K-means. وتصف ورقة Deep Compression ذلك بأنه مستوى من الإحالة غير المباشرة (indirection) في التمرير الأمامي والخلفي معًا.

Backpropagation still produces one gradient per weightالـ backpropagation ما زال ينتج gradient واحدًا لكل وزن

The forward pass runs with the reconstructed weights, so ordinary backpropagation returns the usual 4 × 4 matrix $\partial L / \partial W_{ij}$, one number per position. Slide 28 shows it: first row -0.03, -0.01, 0.03, 0.02, and the largest entry is 0.12 at row 2, column 4. These numbers are gradients for positions, but the parameters are centroids. The chain rule connects the two.

التمرير الأمامي يعمل بالأوزان المعاد بناؤها، لذلك يعيد الـ backpropagation العادي مصفوفة 4 × 4 المعتادة $\partial L / \partial W_{ij}$، رقمًا واحدًا لكل موضع. تعرضها الشريحة 28: الصف الأول -0.03, -0.01, 0.03, 0.02، وأكبر عنصر هو 0.12 في الصف 2 والعمود 4. هذه الأرقام gradients للمواضع، لكن المعاملات هي المراكز. وقاعدة السلسلة (chain rule) تربط بين الاثنين.

Centroid $C_k$ appears in every position whose index is $k$, and nowhere else. So $\partial W_{ij} / \partial C_k$ is 1 when $I_{ij} = k$ and 0 otherwise. Summing over all positions:

المركز $C_k$ يظهر في كل موضع فهرسه $k$، ولا يظهر في أي مكان آخر. لذلك فإن $\partial W_{ij} / \partial C_k$ تساوي 1 عندما $I_{ij} = k$ و 0 في غير ذلك. وبالجمع على كل المواضع:

This is the same rule that governs any shared parameter, such as one convolution filter used at every image position: a parameter used in several places receives the sum of the gradients from all of them.

هذه هي نفس القاعدة التي تحكم أي معامل مشترك، مثل مرشّح convolution واحد يُستخدم في كل موضع من الصورة: المعامل المستخدم في عدة أماكن يتلقى مجموع الـ gradients من كل تلك الأماكن.

Slide 29 turns the formula into three mechanical moves you can do with a pencil: group the gradients by colour, reduce each group to one number, then take a gradient-descent step on each centroid.

الشريحة 29 تحوّل الصيغة إلى ثلاث حركات آلية يمكنك تنفيذها بالقلم: جمّع الـ gradients حسب اللون، واختزل كل مجموعة إلى رقم واحد، ثم خذ خطوة gradient descent على كل مركز.

Group, reduce, updateجمّع، اختزل، حدّث

1. Group by index. Lay the gradient matrix over the index map. Every gradient joins the group of the index at the same position. Read in row-major order, blue (index 3) collects -0.03, 0.12, 0.02, -0.07.التجميع حسب الفهرس (group by index). ضع مصفوفة الـ gradients فوق خريطة الفهارس. كل gradient ينضم إلى مجموعة الفهرس الموجود في الموضع نفسه. بالقراءة صفًا بعد صف (row-major)، يجمع الأزرق (الفهرس 3) القيم -0.03, 0.12, 0.02, -0.07.
2. Reduce by sum. Add up each group. The result is $\partial L / \partial C_k$.الاختزال بالجمع (reduce by sum). اجمع كل مجموعة. الناتج هو $\partial L / \partial C_k$.
3. Update. Multiply by the learning rate and subtract from the old centroid.التحديث (update). اضرب في معدل التعلم واطرح الناتج من المركز القديم.

Watch the signs. A positive summed gradient means the loss rises as the centroid rises, so the centroid moves down: blue falls from 2.00 to 1.96. Green's sum is negative, so it moves up, from -1.00 to -0.97. Step through it with a different learning rate below.

انتبه للإشارات. الـ gradient المجموع الموجب يعني أن الخسارة ترتفع عندما يرتفع المركز، لذلك يتحرك المركز إلى الأسفل: الأزرق ينخفض من 2.00 إلى 1.96. مجموع الأخضر سالب، لذلك يتحرك إلى الأعلى، من -1.00 إلى -0.97. جرّب الخطوات بمعدل تعلم مختلف في الأسفل.